Flash memory cache including for use with persistent key-value store

Abstract

Described is using flash memory, RAM-based data structures and mechanisms to provide a flash store for caching data items (e.g., key-value pairs) in flash pages. A RAM-based index maps data items to flash pages, and a RAM-based write buffer maintains data items to be written to the flash store, e.g., when a full page can be written. A recycle mechanism makes used pages in the flash store available by destaging a data item to a hard disk or reinserting it into the write buffer, based on its access pattern. The flash store may be used in a data deduplication system, in which the data items comprise chunk-identifier, metadata pairs, in which each chunk-identifier corresponds to a hash of a chunk of data that indicates. The RAM and flash are accessed with the chunk-identifier (e.g., as a key) to determine whether a chunk is a new chunk or a duplicate.

1 . In a computing environment, a system comprising, a storage mechanism configured to maintain data items in pages, with at least some pages in a secondary storage device;
 a RAM-based index; and   the storage mechanism accessing the RAM-based index to determine whether a data item is retrievable, the index returning information corresponding to one or more pages in which the data item is maintained, or returning information indicating that the data item cannot be found.   
     
     
         2 . The system of  claim 1  wherein the RAM-based index has a compact footprint and includes a truncated cuckoo hash table, in which each entry of the index comprises a compact footprint checksum and a pointer to a page, the index of each data item configured for storage in one of a plurality of locations in the table, and wherein the checksum validates whether the data item is stored in the page. 
     
     
         3 . The system of  claim 1  wherein the data items comprise key-value pairs, with the key and associated value comprising arbitrary byte arrays. 
     
     
         4 . The system of  claim 1  wherein the secondary storage device comprises a non-volatile memory devices or a hard drive device, or both a non-volatile memory device and a hard drive device. 
     
     
         5 . The system of  claim 1  wherein the storage mechanism writes data items to the storage device, including writing data items to a page and inserting a compact index of the data items into the RAM-based index. 
     
     
         6 . The system of  claim 1 , wherein the storage mechanism further comprises a RAM-based write buffer that maintains data items to be written to the secondary storage, and wherein the storage mechanism writes a page of data items from the RAM-based write buffer to the secondary storage when the data items fill a page, or writes less than a page of data items from the RAM-based write buffer to the secondary store device when a coalesce time is reached. 
     
     
         7 . The system of  claim 1  wherein the secondary storage device comprises a flash store, and further comprising disk-based storage and a recycle mechanism that makes a page in the flash store again available for use by destaging at least some of the data items from the flash store to the disk-based storage. 
     
     
         8 . The system of  claim 7 , wherein the recycle mechanism includes an oldest first policy, least recently used policy, or first-in, first out policy. 
     
     
         9 . The system of  claim 1  wherein the secondary storage device comprises a flash store, and further comprising a data structure that includes information that indicates to a high probability whether a data item has been recently accessed, and a recycle mechanism that makes a page in the flash store available by processing valid data items on the page, including destaging a data item from the page in the flash store to a disk-based storage or reinserting the data item into a RAM-based write buffer to be written back to the flash store, based on whether the information in the data structure indicates that the data item has been recently accessed. 
     
     
         10 . The system of  claim 1  further comprising a RAM-based read/write cache above the secondary storage, and wherein the storage mechanism looks up a data item in the RAM-based read/write cache before accessing the RAM-based index to locate data items in the secondary storage. 
     
     
         11 . In a computing environment, a method performed on at least one processor, comprising:
 maintaining key-value pairs in a secondary storage device;   maintaining a RAM-based index with compact footprint that contains information for locating the key-value pairs maintained in the secondary storage device; and   looking for a key by accessing the RAM-based index to look for one or more locations of the key-value pair in the secondary storage device.   
     
     
         12 . The method of  claim 11 , wherein writing the key-value pairs comprises writing a key-value pair to the secondary storage device, and adding an entry into the RAM-based index for that key. 
     
     
         13 . The method of  claim 12  wherein looking for the key of the key-value pair is performed by a first thread, wherein writing the key-value pair is performed by a second thread, and wherein a recycling process is performed by a third thread, in which at least one of the threads uses a locking mechanism. 
     
     
         14 . The method of  claim 11 , wherein the RAM-based index comprises a truncated cuckoo hash table, wherein each entry of the index comprises a compact checksum and an additional pointer, wherein each key may be stored in one of multiple locations in the index with locations determined by multiple hash functions, wherein a compact checksum is calculated for each location and key, wherein looking up the key comprises checking in multiple locations in the index whether the stored checksum matches the checksum of the key, and wherein the pointers of any locations with a checksum match are each returned as a pointer to a location in which the key-value pairs can be stored. 
     
     
         15 . The method of  claim 14 , wherein when the key does not exist in the storage device no pointers are retrieved, or if one or more pointers are retrieved, the method further comprises checking content pointed to by the pointers to validate if the key is stored in the location, and if so, returning the value of the key-value pair. 
     
     
         16 . The method of  claim 11 , wherein some of the key-value pairs are stored in RAM, and wherein the pointer is divided into a first subspace and a second subspace, in which the first subspace points to a location in RAM, and the second subspace points to a location in the secondary storage. 
     
     
         17 . The method of  claim 11 , wherein writing the key-value pairs into the secondary storage device includes appending the key-value pair to a logical end of the secondary storage device, retrieving one or more pointers of the existing key in the RAM-index, checking existing pointers to determine if a previous version of the key-value pair is stored in the secondary storage device and RAM-based index, and
 if a previous version exists, replacing the pointer to the previous version of the key-value pair with the pointer to a new version of the key-value pair and rendering the previous version of the key-value pair as not pointed to by any pointers in the RAM-index to thereby be processed by a recycling process, and   if no previous version exists, storing the pointer of a new version of the key-value pair in an unoccupied locations if one exists, and if and if no unoccupied location is found, relocating a pointer stored in a location to an alternative location or destaging the pointer and the associated key-value pair to another storage device.   
     
     
         18 . The method of  claim 17 , wherein relocating the pointer includes:
 (a) retrieving keys associated with the pointer as potential relocation candidates,   (b) finding an alternative location for each of the relocation candidates,   (c) if an unoccupied alternative location is found, relocating the relocation candidate,   (d) and if all alternative locations of all relocation candidates are occupied, adding the keys at all the alternative locations as relocation candidates and repeating from step (a).   
     
     
         19 . The method of  claim 17  wherein the recycling process treats the content stored in the secondary storage device as a stream, and for each key-value pair in the secondary storage device, checks if it is pointed by a pointer in the RAM-index, and if pointed to, performs:
 copying the key-value pair into a new stream; 
 garbage collecting at least a portion of a previous stream, and 
 periodically checkpointing the RAM-based index into a storage device in association with a current end position of the key-value store stream for use in crash recovery. 
 
     
     
         20 . In a computing environment, a system comprising, a secondary storage device, a compact RAM-based index corresponding to data items in the secondary storage device, and a mechanism that resolves RAM-based index collisions comprising more than one data item having a common storage location with a common checksum in the RAM-based index, the mechanism resolving the collision by moving at least one index entry to another location that does not correspond to a collision, or if no other location is found after one or more attempts, by destaging a data item from the secondary storage device to a third storage device and removing a corresponding index entry for that data item from the hash table index.