HIERARCHICAL STORAGE FOR LSM-BASED NoSQL STORES

Abstract

Logically arranged hierarchy or tiered storage may comprise a layer of storage being a faster access storage (e.g. solid state drive (SSD)) and another (e.g., next) layer being a traditional disk (e.g. HDD). In one embodiment, compaction occurs within the higher layer, e.g., until there is no more room and then during the compaction sequence the data may be moved down to the lower layer. In another embodiment, compaction and migration to a lower layer may occur within the higher layer, e.g., based on one or more policies, even if the higher layer is not full. In one embodiment, the data between layers are maintained as disjoint. In one embodiment, the more recent versions are always in the higher layer and the older versions are always in the lower layer.

We claim: 
     
         1 . A system for storing data, comprising:
 a storage hierarchy comprising a plurality of memory and storage devices with different characteristics;   a computer module operable to execute on a processor and further operable to place data in uppermost storage layer of the storage hierarchy, the module further operable to flush the data from the uppermost storage layer to a next lower storage layer in the storage hierarchy, wherein the storage hierarchy is logically arranged from upper to lower layers in order of increasing access latency, the module further operable to determine whether the data stored in the next lower storage layer should be compacted and migrated, and in response to determining that the data stored in the next lower storage layer should be compacted and migrated, the module further operable to merge the data with other data stored in the next lower storage layer and migrating the data to a storage layer next to the next lower storage layer,   wherein each storage layer in the storage hierarchy stores data that is disjoint from its upper storage layer.   
     
     
         2 . The system of  claim 1 , wherein the storage hierarchy stores versioned data of a log structured merge tree. 
     
     
         3 . The system of  claim 1 , wherein the module determines whether the data stored in the next lower storage layer should be compacted and migrated based on one or more policies. 
     
     
         4 . The system of  claim 3 , wherein the one or more policies are based on at least an age of the data or a size of the data or combinations thereof. 
     
     
         5 . The system of  claim 1 , wherein whether the data stored in the next lower storage layer should be compacted and migrated is determined based on whether the next lower storage layer is filled to a defined capacity. 
     
     
         6 . The system of  claim 1 , wherein the storage hierarchy comprises three or more combinations of DRAM, PCM, SSD and HDD. 
     
     
         7 . A computer readable storage device storing a program of instructions executable by a machine to perform a method of storing data, the method comprising:
 placing data in uppermost storage layer of a storage hierarchy, the storage hierarchy comprising a plurality of memory and storage devices with different characteristics, wherein the storage hierarchy is logically arranged from upper to lower layers in order of increasing access latency;   flushing the data from the uppermost storage layer to a next lower storage layer in the storage hierarchy;   determining whether the data stored in the next lower storage layer should be compacted and migrated; and   in response to determining that the data stored in the next lower storage layer should be compacted and migrated, merging the data with other data stored in the next lower storage layer and migrating the data to a storage layer next to the next lower storage layer,   wherein each storage layer in the storage hierarchy stores data that is disjoint from its upper storage layer.   
     
     
         8 . The computer readable storage medium of  claim 7 , wherein the determining is performed based on one or more policies defined based on at least one of age of the data and volume of the data. 
     
     
         9 . The computer readable storage medium of  claim 7 , wherein whether the data stored in the next lower storage layer should be compacted and migrated is determined based on whether the next lower storage layer is filled to a defined capacity. 
     
     
         10 . The computer readable storage medium of  claim 7 , wherein the uppermost storage layer comprises volatile memory, and the next lower storage layer and the storage layer next to the next lower storage layer comprise non-volatile storage devices of respective different characteristics.