Stream selection for multi-stream storage devices

Abstract

Systems and techniques for stream selection from multi-stream storage devices. Notification of a KVS tree write request for a multi-stream storage device is received. The notification includes a KVS tree scope corresponding to data in the write request. A stream identifier (ID) is assigned to the write request based on the KVS tree scope and a stability value of the write request. The stream ID is returned to govern stream assignment to the write request, the stream assignment modifying a write operation of the multi-stream storage device.

What is claimed is: 
     
         1 . A system comprising processing circuitry configured to perform operations comprising:
 receiving notification of a key-value set tree write request for a multi-stream storage device, the notification comprising a key-value set tree scope for a key-value set tree, the key-value set tree scope corresponding to data in the key-value set tree write request, the key-value set tree being a data structure comprising nodes, a node of the key-value set tree comprising a temporally ordered sequence of key-value sets (kvsets), the temporally ordered sequence comprising an oldest kvset at one end of the temporally ordered sequence and a newest kvset at another end of the temporally ordered sequence;   assigning a stream identifier to the key-value set tree write request based on the key-value set tree scope; and   returning the stream identifier to govern stream assignment to the key-value set tree write request, the stream assignment modifying a write operation of the multi-stream storage device.   
     
     
         2 . The system of  claim 1 , wherein the operations further comprise:
 assigning a stability value based on the key-value set tree scope.   
     
     
         3 . The system of  claim 2 , wherein the stability value is one of a predefined set of stability values. 
     
     
         4 . The system of  claim 3 , wherein the predefined set of stability values comprises a value representing HOT, a value representing WARM, and a value representing COLD, and wherein the value representing HOT indicates a lowest expected lifetime of the data on the multi-stream storage device and the value representing COLD indicates a highest expected lifetime of the data on the multi-stream storage device. 
     
     
         5 . The system of  claim 2 , wherein the assigning the stability value comprises locating the stability value from a data structure using a portion of the key-value set tree scope. 
     
     
         6 . The system of  claim 5 , wherein the portion of the key-value set tree scope comprises a tree identifier for the data. 
     
     
         7 . The system of  claim 5 , wherein the portion of the key-value set tree scope comprises a level identifier for the data. 
     
     
         8 . The system of  claim 5 , wherein the portion of the key-value set tree scope comprises a type for the data. 
     
     
         9 . The system of  claim 2 , wherein the assigning the stability value comprises:
 maintaining a set of frequencies of stability value assignments for level identifiers, each member of the set of frequencies corresponding to a unique level identifier;   retrieving a frequency from the set of frequencies that corresponds to a level identifier in the key-value set tree scope; and   selecting a stability value from a mapping of stability values to frequency ranges based on the frequency.   
     
     
         10 . The system of  claim 1 , wherein the assigning the stream identifier to the key-value set tree write request based on the key-value set tree scope and a stability value of the key-value set tree write request comprises:
 creating a stream-scope value from the key-value set tree scope;   performing a lookup in a selected-stream data structure using the stream-scope value; and   returning a stream identifier corresponding to the stream-scope from the selected-stream data structure.   
     
     
         11 . The system of  claim 10 , wherein the performing the lookup in the selected-stream data structure comprises:
 failing to find the stream-scope value in the selected-stream data structure;   performing a lookup on an available-stream data structure using the stability value;   receiving a result of the lookup that comprises a stream identifier; and   adding an entry to the selected-stream data structure that comprises the stream identifier, the stream-scope value, and a timestamp of a time when the entry is added.   
     
     
         12 . The system of  claim 11 , wherein the operations further comprise:
 initializing the available-stream data structure by:
 obtaining a number of streams available from the multi-stream storage device; 
 obtaining a stream identifier for all streams available from the multi-stream storage device, each stream identifier being unique; 
 adding stream identifier s to stability value groups; and 
 creating a record in the available-stream data structure for each stream identifier, the record comprising the stream identifier, a device identifier for the multi-stream storage device, and a stability value corresponding to a stability value group of the stream identifier. 
   
     
     
         13 . The system of  claim 10 , wherein the performing the lookup in the selected-stream data structure comprises:
 failing to find the stream-scope value in the selected-stream data structure;   locating a stream identifier from at least one of the selected-stream data structure or an available-stream data structure based on contents of the selected stream data structure; and   creating an entry to the selected-stream data structure that comprises the stream identifier, the stream-scope value, and a timestamp of a time when the entry is added.   
     
     
         14 . The system of  claim 13 , wherein the locating the stream identifier from at least one of the selected-stream data structure or an available-stream data structure based on the contents of the selected stream data structure comprises:
 comparing a first number of entries from the selected-stream data structure to a second number of entries from the available-stream data structure to determine that the first number of entries and the second number of entries are equal;   locating a group of entries from the selected-stream data structure that correspond to the stability value; and   returning a stream identifier of an entry in the group of entries that has an oldest timestamp.   
     
     
         15 . At least one machine readable medium comprising instructions that, when executed by a machine, cause the machine to perform operations comprising:
 receiving notification of a key-value set tree write request for a multi-stream storage device, the notification comprising a key-value set tree scope for a key-value set tree, the key-value set tree scope corresponding to data in the key-value set tree write request, the key-value set tree being a data structure comprising nodes, a node of the key-value set tree comprising a temporally ordered sequence of key-value sets (kvsets), the temporally ordered sequence comprising an oldest kvset at one end of the temporally ordered sequence and a newest kvset at another end of the temporally ordered sequence;   assigning a stream identifier to the key-value set tree write request based on the key-value set tree scope; and   returning the stream identifier to govern stream assignment to the key-value set tree write request, the stream assignment modifying a write operation of the multi-stream storage device.   
     
     
         16 . The at least one machine readable medium of  claim 15 , wherein the operations further comprise:
 assigning a stability value based on the key-value set tree scope.   
     
     
         17 . The at least one machine readable medium of  claim 16 , wherein the stability value is one of a predefined set of stability values. 
     
     
         18 . The at least one machine readable medium of  claim 17 , wherein the predefined set of stability values comprises a value representing HOT, a value representing WARM, and a value representing COLD, and wherein the value representing HOT indicates a lowest expected lifetime of the data on the multi-stream storage device and the value representing COLD indicates a highest expected lifetime of the data on the multi-stream storage device. 
     
     
         19 . The at least one machine readable medium of  claim 16 , wherein the assigning the stability value comprises locating the stability value from a data structure using a portion of the key-value set tree scope. 
     
     
         20 . A method comprising:
 receiving, by processing circuitry, notification of a key-value set tree write request for a multi-stream storage device, the notification comprising a key-value set tree scope for a key-value set tree, the key-value set tree scope corresponding to data in the key-value set tree write request, the key-value set tree being a data structure comprising nodes, a node of the key-value set tree comprising a temporally ordered sequence of key-value sets (kvsets), the temporally ordered sequence comprising an oldest kvset at one end of the temporally ordered sequence and a newest kvset at another end of the temporally ordered sequence;
 assigning, by the processing circuitry, a stream identifier to the key-value set tree write request based on the key-value set tree scope; and 
 returning, by the processing circuitry, the stream identifier to govern stream assignment to the key-value set tree write request, the stream assignment modifying a write operation of the multi-stream storage device.