Multi-tier caching

Patent metadata

Field	Value
Publication number	US-9959279-B2
Application number	US-201615133872-A
Country	US
Kind code	B2
Filing date	Apr 20, 2016
Priority date	Jun 11, 2010
Publication date	May 1, 2018
Grant date	May 1, 2018

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.

First claim

What is claimed is:

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 a partition managed by the first zone manager, bytes pointed at by a first sub-list among all the key-value pairs in a key-value relation;
allocating, from a partition managed by the second zone manager, bytes pointed at by a second 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 sub-list, 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 , wherein the first sub-list is younger than the second sub-list.

3. The method of claim 1 , wherein the first sub-list is least recently used as compared to the second sub-list.

4. 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 the one sub-list.

5. The method of claim 4 , wherein the storing comprises:
allocating bytes from at least one of the zone managers for storing a sorted list of key-value pairs or secondary index pairs;
dividing the sorted list being indexed into a range comprising at least one key-value pair; and
storing a secondary index pair to indicate a beginning of the range.

6. The method of claim 5 , wherein the secondary index pair is a key and a value where the key is equivalent to a key of a tuple in the range and the value of an offset of the tuple in the range.

7. The method of claim 1 , the hierarchy structure comprising a first compact negative cache in the first non-volatile memory device and a second compact negative cache in the second non-volatile memory device, wherein the first compact negative cache has a lower latency than the second compact negative cache.

8. The method of claim 7 , wherein at least one of the compact negative caches is a Bloom Filter.

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

10. The method of claim 1 , the hierarchy 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 hierarchy structure from the second non-volatile memory device to the first non-volatile memory device.

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

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

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

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

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

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

17. The method of claim 1 , wherein at least one of the sub-lists is stored using a SAMT data structure.

18. 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.

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

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

21. 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.

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

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

24. The method of claim 1 , wherein the at least one lower-latency non-volatile memory storage device comprises at least of a solid state disk and a random access memory and the at least one higher-latency non-volatile memory storage device comprises at least one of a hard disk and a network file system.

Assignees

• Univ New York State Res Found

Inventors

• Archak Shrikar
• Dixit Sagar
• Spillane Richard P
• Zadok Erez

Classifications

• C12Q1/6886

  for cancer (immunoassay for cancer G01N33/575) · CPC title

• G06F16/134 Primary

  Distributed indices · CPC title

• G06F16/172 Primary

  Caching, prefetching or hoarding of files · CPC title

• G06F12/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 title

• G06F2212/225

  Hybrid cache memory, e.g. having both volatile and non-volatile portions · CPC title