Hash discriminator process for hierarchical cache system

• US 9,652,389 B2
• Filed: 07/16/2014
• Issued: 05/16/2017
• Est. Priority Date: 07/16/2014
• Status: Active Grant

• Current Assignee: ClearSky Data Co.
• Original Assignee: ClearSky Data, Inc. (Amazon.com, Inc.)
• Inventors: Suman, Daniel, Lacy, Janice Ann, Vekiarides, Lazarus
• Primary Examiner(s): Bragdon, Reginald
• Assistant Examiner(s): VO, THANH DUC
• Application Number:
  US14/332,508
• Publication Number:
  US 20160019148A1
• Time in Patent Office: 1,035 Days
• 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/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 2212/154 Networked environment
• CPC Class Codes: G06F 2212/314 In storage network, e.g. network attached cache
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0655 Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A coordinating node maintains globally consistent logical block address (LBA) metadata for a hierarchy of caches, which may be implemented in local and cloud based storage resources. Associated storage endpoints initially determine a hash associated with each access request, but forward the access request to the coordinating node to determine a unique discriminator for each hash.

Claims

1. A system for operating on data comprising:

a coordinator node connected to local Level 3 (L3) cache storage, the coordinator node also connected to a Level 2 (L2) storage endpoint over a first network connection, and the coordinator node also connected to cloud storage over a second network connection;

the coordinator node maintaining a metadata map indicating locations for data to be stored, and forwarding the metadata map to the L2 storage endpoint and cloud storage;

the metadata map including a metadata map between a plurality of logical block addresses (LBAs) and signatures, the signatures each including a hash determined from a data associated with the corresponding LBA and a unique discriminator associated with the hash;

such that upon a request for data access, the L2 storage endpoint calculates a hash for the data, and looks up the hash in the metadata map associated with the L2 storage endpoint to determine if the data access can or cannot be served from an L2 cache local to the L2 storage endpoint, and

if the data access cannot be served from the L2 cache, the L2 storage endpoint forwards the access request, the data and the hash to the coordinator node; and

the coordinator node then

determining the unique discriminator to be associated with the hash.

2. The system of claim 1 wherein the coordinator node further returns the unique discriminator to the L2 storage endpoint associated with the hash, and the L2 storage endpoint then updating its metadata map with the hash and the unique discriminator.

3. The system of claim 1 wherein the unique discriminator depends on a universal time indicator.

4. The system of claim 1 wherein the unique discriminator depends on a volume identifier associated with the data access request.

5. The system of claim 1 additionally comprising:

the coordinator node responding to a write request from the L2 storage endpoint as a write back cache, such that the write request is acknowledged to the L2 storage endpoint even if data associated with the write request is not presently stored in its respective local cache; and

the coordinator node storing data associated with the write request in its respective local cache before forwarding the data associated with the write request to the cloud storage.

6. The system of claim 5 wherein the coordinator node further deduplicates data in the local cache before forwarding data to the cloud storage.

7. The system of claim 6 wherein the coordinator node assigns a unique discriminator to an LBA map entry associated with the deduplicated data.

8. The system of claim 6 wherein the coordinator node further deduplicates data in the local cache as a background process.

9. The system of claim 1 wherein the unique discriminator is used to further determine where to store data in the respective cache.

10. The system of claim 1 wherein if the data access can be served from the local L2 cache, the L2 storage endpoint forwards the hash to the coordinator node, and the coordinator node updates a global metadata map.

11. The system of claim 1 wherein the unique discriminator uniquely identifies the data across an address space associated with the cloud storage.

12. A method comprising:

forwarding data for storage in a local Level 3 (L3) cache;

connecting to a Level 2 (L2) storage endpoint over a first network connection;

connecting to cloud storage over a second network connection;

maintaining metadata indicating where data is stored in each of the Level 3 (L3) cache, L2 storage endpoint, and cloud storage, the metadata providing a metadata map between a plurality of logical block addresses (LBAs) and signatures, the signatures each including a hash determined from a data associated with each corresponding LBA and a unique discriminator;

upon receiving a request for data access,

calculating a hash for the data;

looking up the hash in the metadata map associated with the L2 storage endpoint to determine if the data access can or cannot be served from the L2 storage endpoint;

if the data access cannot be served from the L2 storage endpoint,

forwarding the access request, the data and the hash to the L3 cache; and

determining a new unique discriminator to be associated with the hash.

13. The method of claim 12 additionally comprising:

returning the unique discriminator to the L2 storage endpoint associated with the hash.

14. The method of claim 12 wherein the unique discriminator depends on a universal time indicator.

15. The method of claim 12 wherein the unique discriminator depends on a volume identifier associated with the data access request.

16. The method of claim 12 additionally comprising:

responding to a write request from the L2 storage endpoint as a write back cache, such that the write request is acknowledged to the L2 storage endpoint even if data associated with the write request is not presently stored in its respective local cache; and

storing data associated with the write request in the L3 cache before forwarding the data associated with the write request to the cloud storage.

17. The method of claim 16 further comprising:

deduplicating data in the local cache before forwarding data to the cloud storage.

18. The method of claim 17 additionally comprising:

assigning a unique discriminator to an LBA map entry associated with the deduplicated data.

19. The method of claim 17 additionally comprising:

deduplicating data in the local cache as a background process.

20. The method of claim 12 further comprising:

using the unique discriminator to further determine where to store data in the respective cache.

21. The method of claim 12 wherein if the data access can be served from the local L2 storage endpoint, further forwarding the hash to the coordinator node.

22. The method of claim 12 wherein the unique discriminator uniquely identifies the data across LBA, associated with the cloud storage.