Storage management in hybrid drives

Abstract

Methods for deciding whether to store data in a non-volatile semiconductor memory (NVSM) storage portion of a hybrid drive including the NVSM storage portion and a disk storage portion are provided. One such method involves generating a queue for storing candidate addresses and a priority level for each of the candidate addresses, receiving a read command and a range of addresses for the disk storage portion, determining a relative distance between reads of a first address corresponding with a second address within the range of addresses, storing, when the relative distance is less than a relative distance threshold, a first candidate address, corresponding to the second address, and a respective priority level in the queue, and storing, when the priority level of the first candidate address is greater than a priority level threshold, data corresponding to the first candidate address in the NVSM storage portion.

What is claimed is: 
     
         1 . A method for deciding whether to store data in a non-volatile semiconductor memory (NVSM) storage portion of a hybrid drive comprising the NVSM storage portion and a disk storage portion, the method comprising:
 generating a queue for storing a plurality of candidate addresses and a priority level for each of the plurality of candidate addresses;   receiving a read command and a range of addresses for the disk storage portion of the hybrid drive, wherein the range of addresses corresponds to the read command;   determining a relative distance between reads of a first address corresponding with a second address within the range of addresses;   storing, when the relative distance is less than a relative distance threshold, a first candidate address, corresponding to the second address, and a respective priority level in the queue; and   storing, when the priority level of the first candidate address is greater than a priority level threshold, data corresponding to the first candidate address in the NVSM storage portion of the hybrid drive.   
     
     
         2 . The method of  claim 1 , further comprising:
 increasing, when one or more read commands of the second address is performed, the priority level for the first candidate address.   
     
     
         3 . The method of  claim 2 , further comprising:
 decreasing, when one or more write commands of the second address is performed, the priority level for the first candidate address.   
     
     
         4 . The method of  claim 1 , wherein the storing, when the relative distance is less than the relative distance threshold, the first candidate address, corresponding to the second address, and the respective priority level in the queue comprises:
 determining the respective priority level for the first candidate address based on the relative distance; and   storing, when the relative distance is less than the relative distance threshold, the first candidate address, corresponding to the second address, and the respective priority level in the queue.   
     
     
         5 . The method of  claim 1 , further comprising:
 determining a relative distance between reads of a third address corresponding with a fourth address within the range of addresses;   storing, when the relative distance of the third address is less than the relative distance threshold, a second candidate address, corresponding to the fourth address, and a respective priority level in the queue; and   determining an aggregate of the priority level for the first candidate address and the second candidate address;   wherein the storing, when the priority level of the first candidate address is greater than the priority level threshold, the data corresponding to the first candidate address in the NVSM storage portion of the hybrid drive comprises:
 storing, when the aggregate is greater than a second preselected threshold, the data corresponding to the first candidate address and data corresponding to the second candidate address in the NVSM storage portion of the hybrid drive. 
   
     
     
         6 . The method of  claim 1 , wherein the first address and the second address are identical. 
     
     
         7 . The method of  claim 1 , wherein the first address comprises a truncated version of the second address. 
     
     
         8 . The method of  claim 7 , further comprising:
 removing a first preselected number of sequential bits starting at the least significant bit of the second address to form the first address.   
     
     
         9 . The method of  claim 7 , further comprising:
 splitting the first address into a slot value and a residual value, wherein the queue is implemented using an array having at least one index of slot values.   
     
     
         10 . The method of  claim 7 , further comprising:
 hashing the first address to remove locality; and   splitting the hashed first address into a slot value and a residual value, wherein the queue is implemented using an array having at least one index of slot values.   
     
     
         11 . The method of  claim 1 , further comprising:
 maintaining a count of entries in the queue at each priority level in the plurality of priority levels; and   decreasing a priority level of a preselected entry in the queue if the count of entries for the priority level of the preselected entry is greater than a priority level threshold.   
     
     
         12 . The method of  claim 1 , further comprising:
 maintaining a count of entries in the queue at each priority level in the plurality of priority levels;   maintaining a list of candidate addresses for each priority level in the plurality of priority levels;   determining whether the count of entries of a first priority level in the plurality of priority levels is greater than a priority level threshold;   selecting, if the count of entries of the first priority level is greater than the priority level threshold, a victim from the list of candidate addresses at the first priority level; and   decreasing, if the count of entries of the first priority level is greater than the priority level threshold, a priority level of the entry in the queue corresponding to the victim.   
     
     
         13 . The method of  claim 1 , further comprising:
 maintaining a list of candidate addresses for each priority level in the plurality of priority levels;   identifying a second candidate address in the queue for a priority promotion;   selecting a victim from the list of candidate addresses having a priority level higher than that of the second candidate address;   storing the priority level of the second candidate address as a former priority level;   setting the priority level of the second candidate address to the priority level of the victim; and   setting the priority level of the victim to the former priority level of the second candidate address.   
     
     
         14 . The method of  claim 1 , further comprising:
 maintaining a count of entries in the queue at each priority level in the plurality of priority levels; and   setting a maximum count threshold for each priority level based on a size of storage available in the NVSM storage portion of the hybrid drive.