MULTI-TIER CACHING

• US 20120072656A1
• Filed: 06/13/2011
• Published: 03/22/2012
• 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: Zadok, Erez, Archak, Shrikar, Dixit, Sagar, Spillane, Richard P.
• Granted Patent: US 9,355,109 B2
• Time in Patent Office: Days
• US Class Current: 711/104
• 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 non-transitory computer readable medium embodying instructions executed by a processor to perform a method for maintaining an index in multi-tier data structure, the method comprising:

providing a plurality of a storage devices forming the multi-tier data structure;

caching a list of key-value pairs stored on one or more tiers of the multi-tier data structure as a plurality of sub-lists according to a caching method, 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 block allocators recording which blocks 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 block allocators, wherein each zone manager maintains a header object pointing to data to be stored in all allocated blocks.

2. The computer readable medium of claim 1, wherein the multi-tier data structure includes a random access memory (RAM) and the index exceeds a size of the RAM, the method further comprising a base insertion throughput to a portion of the index on disk.

3. The computer readable medium of claim 1, wherein the multi-tier data structure includes memory systems having different memory capacities, speeds, and/or costs.

4. The computer readable medium of claim 1, wherein the caching further comprises caching the list of key-values pairs as an index of key-value pairs across a plurality of tiers of the multi-tier data structure.

5. The computer readable medium of claim 4, further comprising extending the index across multiple computer readable mediums embodying the multi-tier data structure, wherein the multiple computer readable mediums are connected by respective processors over a network connection, a bus, or any other suitable communication medium.

6. The computer readable medium of claim 1, wherein the key-values pairs each further include a sub-array of one of the data value and the data pointer with a sub-index for performing a column store operation.

7. The computer readable medium of claim 1, further comprising splitting the list of list of key-value pairs into a read data sub-list and a write data sub-list.

8. The computer readable medium of claim 1, further comprising maintaining a plurality of sub-lists of the list of key-value pairs, each sub-list containing more frequently accessed key-value pairs in more efficient machine tiers.

9. The computer readable medium of claim 8, further comprising transferring less frequently accessed sub-lists are transferred to less efficient machine tiers according to a merging method.

10. The computer readable medium of claim 1, further comprising merging entries in the multi-tiered structure to preferentially cache sub-lists in a most efficient machine tier having sufficient space.

11. A non-transitory computer readable medium embodying instructions executed by a processor to perform a method for inserting and retrieving key-value pairs in a machine in communication with multiple storage devices managed in a hierarchy of tiers, the method steps comprising:

inserting the key-value pairs in the machine comprising;

transferring first lists of sorted key-value pairs from a first memory on the machine to a highest storage tier of the machine according to a merging method, if there is space available on the highest storage tier;

transferring second lists from the higher storage tiers to the lower storage tiers within the machine according to the merging method to create space in the higher storage tiers; and

transferring third lists from higher machine tiers including the machine to lower machine tiers according to the merging method and conflict resolution algorithm to create space in the higher storage tiers; and

retrieving the key-value pairs from the machine comprising;

searching for a first value with a valid key in the first memory on the machine;

searching for a second value with the valid key in the highest storage tier of the machine if not present in first memory on the machine;

searching for a value with the valid key in the lower storage tiers of the machine if not present on the highest storage tier of the machine; and

searching for a value with the valid key in lower machine tiers if not present on higher machine tiers of the machine.

12. The computer readable medium of claim 11, wherein encryption is used to transmit lists across network links in a network of machines including the machine.

13. The computer readable medium of claim 11, further comprising performing a filtering method to store a negative cache corresponding to values in on a higher machine tier.

14. The computer readable medium of claim 11, wherein the merging method uses a write-optimized indexing structure and wherein the write-optimized indexing structure is one of a COLA (cache oblivious look-ahead array data structure), a SAMT (sorted array merge tree), a Log Structured Merge-Tree, a Buffer Tree, or an FD-Tree.

15. The computer readable medium of claim 11, wherein a conflict resolution method is a lock resolution.

16. The computer readable medium of claim 15, wherein the lock resolution method comprises an acquisition and a resolution, wherein an acquisition occurs when a client performs an insertion, and resolution occurs when lists from multiple higher-tier machines are merged together by the merging algorithm.

17. The computer readable medium of claim 16, wherein the acquisition comprises:

a client specifies or utilizes an existing authoritative machine for a subset of keys;

the client notifies the authoritative machine of a lock on a subset of keys; and

the authoritative machine optionally stores the lock in a locking structure.

18. The computer readable medium of claim 16, wherein the resolution comprises:

a machine or storage tier merging multiple lists is called a merger. such a machine is merging multiple lists from higher-tier storage devices and/or machines and determines that two key-value pairs conflict; and

the merger determines which key-value pair to include in the output list and which key-value pairs to omit by inspecting the key-value pair and included codes and flags, and by optionally consulting with the locking structure.

19. A non-transitory computer readable medium embodying instructions executed by a processor to perform a method for maintaining an index in multi-tier data structure, the method comprising:

managing a plurality of resources within a multi-tier storage system;

inserting a copy of at least one of the resources into the multi-tier storage system;

detecting, at a selective time, the copy of the at least one resource; and

performing a merging method to redistribute the plurality of resources within the multi-tier storage system.

20. The computer readable medium of claim 19, wherein the detecting is deferred until after the merging method, wherein the merging method outputs a list containing the copy of at least one resource.

21. The computer readable medium of claim 19, wherein the detecting is performed prior to the merging method.

22. The computer readable medium of claim 19, further comprising notifying a data block allocator and manager the copy of at least one resource and moving the resource to a different tier of the multi-tier storage system.

23. The computer readable medium of claim 19, further comprising notifying a data block allocator and manager the copy of at least one resource and removing the copy of at least one resource.

24. The computer readable medium of claim 19, wherein the resource is a data block.

25. A non-transient computer readable medium embodying instructions executed by a processor to perform a method for maintaining an index in multi-tier data structure, the method comprising:

managing a plurality of resources within a multi-tier storage system; and

performing a merging method to redistribute the plurality of resources within the multi-tier storage system, wherein the merging method is automatically tuned for a workload without disabling the machine.

26. The computer readable medium of claim 25, further comprising analyzing the workload to determine a workload type, wherein the workload type is one of insertion intensive or scan intensive.