Multi-tier caching

• US 9,355,109 B2
• Filed: 06/13/2011
• Issued: 05/31/2016
• Est. Priority Date: 06/11/2010
• Status: Active Grant

• Current Assignee: The Research Foundation for The State University of New York (State University of New York)
• Original Assignee: The Research Foundation for The State University of New York (State University of New York)
• Inventors: Dixit, Sagar, Archak, Shrikar, Spillane, Richard P., Zadok, Erez
• Primary Examiner(s): TSAI, SHENG JEN
• Application Number:
  US13/159,039
• Publication Number:
  US 20120072656A1
• Time in Patent Office: 1,814 Days
• Field of Search: 711/118, 711/104, 711/E12.041
• US Class Current: 1/1
• CPC Class Codes: C12Q 1/6886 for cancer immunoassay for cancer G01N33/574
• CPC Class Codes: C12Q 2600/158 Expression markers
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 16/134 Distributed indices
• CPC Class Codes: G06F 16/172 Caching, prefetching or hoarding of files
• CPC Class Codes: G06F 2212/225 Hybrid cache memory, e.g. having both volatile and non-volatile portions

Abstract

A method for maintaining an index in multi-tier data structure includes providing a plurality of a storage devices forming the multi-tier data structure, caching an index of key-value pairs across the multi-tier data structure, wherein each of the key-value pairs includes a key, and one of a data value and a data pointer, the key-value pairs stored in the multi-tier data structure, providing a journal for interfacing with the multi-tier data structure, providing a plurality of zone allocators recording which zones of the multi-tier data structure are in used, and providing a plurality of zone managers for controlling access to cache lines of the multi-tier data structure through the journal and zone allocators, wherein each zone manager maintains a header object pointing to data to be stored in an allocated zone.

Claims

1. A method of storing data as a plurality of key-value pairs in a multi-tier storage system, the system comprising at least one lower-latency non-volatile memory storage device and at least one higher-latency non-volatile memory storage device, the method comprising:

generating a first zone manager for managing a first partition of storage of a first non-volatile memory device among the lower-latency non-volatile memory storage devices to generate a tier of the multi-tier storage system;

generating a second zone manager for managing a second partition of storage of a second non-volatile memory device among the higher-latency non-volatile memory storage devices to generate another tier of the multi-tier storage system;

allocating, from the first zone manager, bytes pointed at by a more frequently accessed sub-list among all the key-value pairs in a key-value relation;

allocating, from the second zone manager, bytes pointed at by a less frequently accessed sub-list among all the key-value pairs in the key-value relation;

allocating bytes from the first zone manager for storing meta-data, where the meta-data comprises at least one association of the key-value relation with an array of pointers to sub-lists belonging to the relation, wherein each sub-list includes at least one pointer to bytes allocated for sorted key-value pairs comprising the corresponding sublist,

wherein each partition comprises at least one block of a given size, and

wherein the system maintains a hierarchy structure in one of the tiers that stores the key-value relation and enables the key-value pairs to be stored in any one of the tiers.

2. The method of claim 1, further comprising storing in one of the sub-lists a pointer to a secondary index and a pointer to bytes for data of the sorted list, said secondary index stores an index to the sorted list stored in bytes pointed at by this sub-list.

3. The method of claim 2, wherein the storing comprises:

allocating bytes from at least one of the zone managers for storing a sorted list of key-offset pairs or secondary index pairs;

dividing the sorted list being indexed into a set of finite ranges of key-value pairs; and

storing a secondary index pair to indicate the beginning of each range of key-value pairs stored in the list being indexed.

4. The method of claim 3, wherein the secondary index pair is a key and a value where the key is equivalent to the key of a first tuple in the range being indicated and the value of the offset of the first tuple in the range being indicated.

5. The method of claim 1, the structure comprising a compact negative cache in the first non-volatile memory device for at least one of the sublists in the second non-volatile memory device.

6. The method of claim 5, wherein the compact negative cache is a Bloom Filter.

7. The method of claim 1, wherein at least one of the key-value pairs is a variable length key-value pair.

8. The method of claim 1, the structure comprising a compact negative cache in the second non-volatile memory device for each sub-list in the second non-volatile memory device, and then transferring the structure from the second non-volatile memory device to the first non-volatile memory device.

9. The method of claim 8, wherein the compact negative cache is a Bloom Filter.

10. The method of claim 1, wherein the system further comprises a cache that stores one or more of the frequently used sublists from one or more of the tiers, wherein a storage device used for the cache has a lower latency than the at least one lower-latency non-volatile memory storage device for sequential or random access.

11. The method of claim 10, wherein the cache is one of a volatile memory or a non-volatile memory.

12. The method of claim 1, wherein at least one of the sublists is stored using a red-black tree.

13. The method of claim 1, wherein at least one of the sublists is stored using a B-tree data structure.

14. The method of claim 1, wherein at least one of the sublists is stored using an R-COLA data structure.

15. The method of claim 1, wherein at least one of the sublists is stored using a SAMT data structure.

16. The method of claim 1, where the allocating performed by at least one of the zone managers is with respect to bytes at multiple offsets.

17. The method of claim 1, where at least one of the sub-lists contains one or more key-value pairs indicating a deleted item.

18. The method of claim 1 where at least one of the sub-lists contains one or more key-value pairs indicating an updated item.

19. The method of claim 1, further comprising compacting a group of the sub-lists in one of the tiers into a fewer number of sub-lists according to a merging method.

20. The method of claim 19, further comprising reclaiming space resulting from the compacting from the corresponding zone manager.

21. The method of claim 20, further comprising transferring another group of the sub-lists into the reclaimed space.