Decoupling data and metadata in hierarchical cache system

• US 9,430,387 B2
• Filed: 07/16/2014
• Issued: 08/30/2016
• Est. Priority Date: 07/16/2014
• Status: Active Grant

• Current Assignee: ClearSky Data Co.
• Original Assignee: ClearSky Data, Inc. (Amazon.com, Inc.)
• Inventors: Vekiarides, Lazarus, Suman, Daniel, Lacy, Janice Ann
• Primary Examiner(s): Bragdon, Reginald
• Assistant Examiner(s): VO, THANH DUC
• Application Number:
  US14/332,489
• Publication Number:
  US 20160019147A1
• Time in Patent Office: 776 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 2212/284 being distributed
• CPC Class Codes: G06F 2212/62 Details of cache specific to multiprocessor cache arrangements
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching

Abstract

A coordinating node creates virtual storage from a hierarchy of local and remote cache storage resources by maintaining global logical block address (LBA) metadata maps. A size of the metadata maps at each level of the hierarchy is independent of an amount of data allocated to a respective cache store at each level.

Claims

1. A system for operating on data comprising:

a storage endpoint serving as an interface to a Level 2 (L2) cache;

a coordinator node serving as an interface to a Level 3 (L3) cache, the coordinator node connected to the storage endpoint over a first network connection and also connected to cloud storage acting as a Level 4 (L4) cache over a second network connection;

each of the storage endpoint, coordinator node, and cloud storage maintaining a metadata map indicating locations for data for with they are respectively responsible for storing in their respective caches;

wherein a size of the metadata maps is not dependent on a size of a respective cache; and

further in that the metadata map maintained at the storage endpoint is smaller than the metadata map maintained at the coordinator node, and the metadata map maintained at the coordinator node is smaller than a size of the metadata map maintained at the cloud is storage;

an amount of data stored at the L2 cache is greater than an amount of data stored at the L3 cache, wherein the data stored at L3 cache is decoupled from the data stored at L2 cache; and

an amount of data stored in the cloud storage is greater than an amount of data stored in the L3 cache.

2. The system of claim 1 wherein the coordinator node further

maintains a global logical block address (LBA) metadata map;

and

distributes respective portions of the global LBA metadata map to the storage endpoint and to the cloud storage.

3. The system of claim 1 wherein the coordinator node responds to write requests received from the storage endpoint as a write back cache, such that the write request is acknowledged to the storage endpoint even if a logical block address associated with the write request is not presently assigned to the L3 cache in the before associated data is written to the cloud storage.

4. The system of claim 1 wherein the amount of data stored at the L3 cache depends on a latency of a connection over the second network.

5. The system of claim 1 wherein the storage endpoint further, upon receiving a write request, determines a hash from data associated with the write request, and looks up the hash in its respective metadata store.

6. A method comprising;

at a coordinator node;

serving as an interface to a Level 2 (L2) cache;

serving as an interface to a Level 3 (L3) cache;

connecting to a storage endpoint over a first network connection;

connecting to cloud storage acting as a Level 4 (L4) cache over a second network connection; and

maintaining a metadata map indicating locations where data is to be stored in each of the storage endpoint, coordinator node, and cloud storage, such that a size of the metadata maps is not dependent on a size of a respective L2, L3 or L4 cache;

maintaining the metadata map for the storage endpoint to be smaller than the metadata map maintained for the coordinator node;

maintaining the metadata map for the coordinator node to be smaller than a size of the metadata map for the cloud storage;

forwarding an amount of data stored at the L2 cache which is greater than an amount of data stored at the L3 cache, wherein the data stored at the L3 cache is decoupled from the data stored at L2 cache; and

forwarding an amount of data stored in the cloud storage which is greater than either an amount of data forwarded to the L3 cache or the L2 cache.

7. The method of claim 6 further comprising:

maintaining a global logical block address (LBA) metadata map; and

distributing respective portions of the global LBA metadata map to the storage endpoint and to the cloud storage.

8. The method of claim 6 further comprising:

responding to write requests received from the storage endpoint as a write back cache, such that the write request is acknowledged to the storage endpoint even if a logical block address associated with the write request is not presently assigned to the L3 cache in the before associated data is written to the cloud storage.

9. The method of claim 6 wherein the amount of data stored at the L3 cache depends on a latency of a connection over the second network.

10. The method of claim 6 additionally comprising:

at the storage endpoint,

upon receiving a write request, determining a hash from data associated with the write request; and

looking up the hash in its respective metadata store.