Method of cooperative caching for distributed storage system

• US 20060174063A1
• Filed: 02/03/2005
• Published: 08/03/2006
• Est. Priority Date: 02/03/2005
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Merchant, Arif, Saito, Yasushi, Wilkes, John, Soules, Craig, Veitch, Alistair C.
• Granted Patent: US 8,055,845 B2
• Time in Patent Office: Days
• US Class Current: 711/118
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0862 with prefetch

Abstract

An embodiment of a method of cooperative caching for a distributed storage system begins with a step of requesting data from storage devices which hold the data. The method continues with a step of receiving any cached blocks and expected response times for providing non-cached blocks from the storage devices. The method concludes with a step of requesting a sufficient number of the non-cached blocks from one or more particular storage devices which provides an expectation of optimal performance.

Claims

1. A method of cooperative caching for a distributed storage system comprising the steps of:

requesting data from caches of storage devices which hold the data;

receiving any cached blocks of the data and expected response performances for providing any non-cached blocks of the data from the storage devices; and

requesting a sufficient number of the non-cached blocks from one or more particular storage devices which provide an expectation of optimal performance.

2. The method of claim 1 wherein the expected response performances comprise expected response costs and the expectation of optimal performance comprises an expectation of minimal response cost for providing a remainder of the data.

3. The method of claim 1 wherein the expected response performances comprise combinations of an expected response cost and an expected response time, and the expectation of optimal performance comprises an optimal combination of an expectation of a response cost for providing a remainder of the data and an expectation of a response time for receiving the remainder of the data.

4. The method of claim 1 wherein the expected response performances comprise expected response times and the expectation of optimal performance comprises an expectation of minimal response time for receiving a remainder of the data.

5. A method of cooperative caching for a distributed storage system comprising the steps of:

requesting data from caches of storage devices which hold the data;

receiving any cached blocks of the data and expected response times for providing non-cached blocks of the data from the storage devices; and

requesting a sufficient number of the non-cached blocks from one or more particular storage devices which provide a remainder of the data with an expectation of a minimal response time.

6. The method of claim 5 wherein the cached blocks, if any, are held in a cache-level of a storage hierarchy and the non-cached blocks are held a slower-response level of the storage hierarchy.

7. The method of claim 5 wherein the cached blocks, if any, are held in a cache memory and the non-cached blocks are held in a slower-response memory or storage.

8. The method of claim 5 wherein the data comprises copies of the data.

9. The method of claim 8 wherein the copies of the data comprise replicated data.

10. The method of claim 8 wherein the copies of the data comprise mirrored data.

11. The method of claim 8 wherein the step of requesting the sufficient number of the non-cached blocks from the one or more particular storage devices which provide the expectation of the minimal response time for receiving the remainder of the copies of the data comprises requesting subsets of the remainder of the data blocks from a set of the storage devices which each provide a low expected response time.

12. The method of claim 5 wherein the data comprises erasure coded data.

13. The method of claim 12 wherein a stripe of the erasure coded data comprises data blocks and parity blocks.

14. The method of claim 5 wherein the step of requesting the sufficient number of the non-cached blocks from the one or more particular storage devices which provide the expectation of the minimal response time for receiving the remainder of the data includes considering available network bandwidth and network latencies between a requestor and the storage devices.

15. The method of claim 5 wherein each expected response time comprises a load on a responding storage device.

16. The method of claim 15 wherein the load comprises a weighted sum of outstanding cache-read requests, outstanding cache-write requests, outstanding disk-read requests, and outstanding disk write requests.

17. The method of claim 5 wherein the expectation of the minimal response time is based upon the expected response times provided by the storage devices.

18. The method of claim 5 wherein the expectation of the minimal response time is based upon a combination of the expected response times provided by the storage devices and historical correction factors.

19. A method of cooperative caching for a distributed storage system comprising the steps of:

requesting data blocks of replicated data from caches of storage devices which hold the replicated data;

receiving cached data blocks of the replicated data, if any, and an expected response time for providing non-cached data blocks of the replicated data from one or more responding storage devices; and

requesting a remainder of the data blocks of the replicated data from a particular storage device having a minimal expected response time.

20. The method of claim 19 wherein the expected response time for the responding storage device comprises a load on the responding storage device.

21. The method of claim 20 wherein the load comprises a weighted sum of outstanding cache-read requests, outstanding cache-write requests, outstanding disk-read requests, and outstanding disk write requests.

22. The method of claim 19 wherein the step of receiving the cached data blocks, if any, and the expected response time for providing the non-cached data blocks from at least one of the storage devices comprises:

receiving first level cached data blocks, if any, from at least one of the storage devices;

requesting the data blocks less received cached data blocks from a second level cache from the storage devices; and

receiving the second level cached data blocks, if any, and the expected response time from at least one of the storage devices.

23. The method of claim 19 wherein the step of receiving the cached data blocks, if any, and the expected response time for providing the non-cached data blocks from at least one of the storage devices comprises:

receiving first level cached data blocks, if any, from at least one of the storage devices;

requesting the data blocks less received first level cached data blocks from a second level cache from the storage devices;

receiving the second level cached data blocks, if any, from at least one of the storage devices;

requesting the data blocks less received first and second level cached data blocks from a third level cache from the storage devices; and

receiving the third level cached data blocks, if any, and the expected response time from at least one of the storage devices.

24. The method of claim 19 wherein the cached blocks are held in a memory and the memory comprises a hierarchy of a cache memory and a slower memory.

25. The method of claim 24 wherein the expected response time indicates the expected response time for providing the non-cached blocks from the slower memory if the non-cached blocks reside in the slower memory.

26. The method of claim 24 wherein each storage device first looks for cached data blocks in the cache memory and, if needed, then looks for the cached data blocks in the slower memory.

27. The method of claim 19 wherein the responding storage device further comprises storage and wherein the non-cached data blocks reside in the storage.

28. The method of claim 19 wherein the step of requesting the data blocks of the replicated data from the storage devices staggers the requests over time.

29. The method of claim 19 wherein the step of requesting the data blocks of the replicated data from the storage devices first requests the data blocks from the storage devices having a better performance history.

30. The method of claim 19 further comprising the step of canceling any outstanding requests once the data blocks have been received.

31. A method of cooperative caching for a distributed storage system comprising the steps of:

requesting a stripe of erasure coded data from caches of storage devices which hold the erasure coded data, the stripe of erasure coded data comprising data blocks and one or more parity blocks;

if the cache of any of the storage devices holds one of the data blocks or the one or more parity blocks, receiving a cached block from each of a subset of the storage devices, the cached block comprising a cached data block or a cached parity block held in the memory of a responding storage device;

receiving an expected response time for providing a non-cached block from each of remaining storage devices, the non-cached block comprising the data block or the parity block not held in the memory of the responding storage device; and

requesting that each of a minimum number of the remaining storage devices having a minimal expected response time provide the data block or the parity block that it holds in order to receive a minimum number of blocks needed to reconstruct the stripe of erasure coded data.

32. A computer readable media comprising computer code for implementing a method of cooperative caching for a distributed storage system, the method of cooperative caching comprising the steps of:

requesting data from caches of storage devices which hold the data;

receiving any cached blocks of the data and expected response times for providing any non-cached blocks of the data from the storage devices; and

requesting a sufficient number of the non-cached blocks from one or more particular storage devices which provide an expectation of optimal performance.

33. A computer readable media comprising computer code for implementing a method of cooperative caching for a distributed storage system, the method of cooperative caching comprising the steps of:

requesting data from caches of storage devices which hold the data;

receiving any cached blocks of the data and expected response times for providing non-cached blocks of the data from the storage devices; and

requesting a sufficient number of the non-cached blocks from one or more particular storage devices which provide a remainder of the data with an expectation of a minimal response time.

34. The computer readable media of claim 33 wherein the data comprises replicated data.

35. The computer readable media of claim 33 wherein the data comprises erasure coded data.

36. A computer readable media comprising computer code for implementing a method of cooperative caching for a distributed storage system, the method of cooperative caching comprising the steps of:

requesting data blocks of replicated data from caches of storage devices which hold the replicated data;

receiving cached data blocks of the replicated data, if any, and an expected response time for providing non-cached data blocks of the replicated data from one or more responding storage devices; and

requesting a remainder of the data blocks of the replicated data from a particular storage device having a minimal expected response time.

37. A computer readable media comprising computer code for implementing a method of cooperative caching for a distributed storage system, the method of cooperative caching comprising the steps of:

requesting a stripe of erasure coded data from caches of storage devices which hold the erasure coded data, the stripe of erasure coded data comprising data blocks and one or more parity blocks;

if the cache of any of the storage devices holds one of the data blocks or the one or more parity blocks, receiving a cached block from each of a subset of the storage devices, the cached block comprising a cached data block or a cached parity block held in the memory of a responding storage device;

receiving an expected response time for providing a non-cached block from each of remaining storage devices, the non-cached block comprising the data block or the parity block not held in the memory of the responding storage device; and

requesting that each of a minimum number of the remaining storage devices having a minimal expected response time provide the data block or the parity block that it holds in order to receive a minimum number of blocks needed to reconstruct the stripe of erasure coded data.