Method of operating distributed storage system

• US 20070192542A1
• Filed: 02/16/2006
• Published: 08/16/2007
• Est. Priority Date: 02/16/2006
• 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: Jackson, James, Merchant, Arif, Veitch, Alistair, Frolund, Svend, Reuter, James
• Granted Patent: US 7,725,655 B2
• Time in Patent Office: Days
• US Class Current: 711/119
• CPC Class Codes: G06F 11/1064 in cache or content addressable memories
• CPC Class Codes: G06F 11/1666 where the redundant component is memory or memory area
• CPC Class Codes: G06F 11/182 based on mutual exchange of the output between redundant processing components
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache

Abstract

An embodiment of a method of operating a distributed storage system includes reading m data blocks from a distributed cache. The distributed cache comprises memory of a plurality of independent computing devices that include redundancy for the m data blocks. The m data blocks and p parity blocks are stored across m plus p independent computing devices. Each of the m plus p independent computing devices stores a single block selected from the m data blocks and the p parity blocks.

Claims

1. A method of operating a distributed storage system comprising the steps of:

reading m data blocks from a distributed cache, the distributed cache comprising memory of a plurality of independent computing devices that include redundancy for the m data blocks; and

storing the m data blocks and p parity blocks across m plus p independent computing devices, each of the m plus p independent computing devices storing a single block selected from the m data blocks and the p parity blocks.

2. The method of claim 1:

wherein reading the m data blocks from the distributed cache comprises reading the m data blocks from m replicated caches, each replicated cache comprising p plus one independent computing devices, each independent computing device of a replicated cache holding a particular data block in memory; and

further comprising determining the p parity blocks from the m data blocks.

3. The method of claim 2 further comprising generating a timestamp.

4. The method of claim 3 further comprising receiving confirmations from at least a majority of the independent computing devices from each replicated cache that a flush operation for the particular data block was initiated no later than a time indicated by the timestamp and that a more recent version of the particular data block has not been flushed.

5. The method of claim 2 further comprising generating m timestamps.

6. The method of claim 5 further comprising associating each of the m timestamps to a particular read operation for the particular data block.

7. The method of claim 6 further comprising receiving confirmations from at least a majority of the independent computing devices from each replicated cache that a flush operation for the particular data block was initiated no later than a time indicated by a particular timestamp and that a more recent version of the particular data block has not been flushed.

8. The method of claim 2 wherein the m data blocks form a first stripe of data and the replicated caches are first replicated caches and further comprising reading a second stripe of data from second replicated caches.

9. The method of claim 8 wherein the first and second replicated caches intersect in at least one independent computing device.

10. The method of claim 2 further comprising receiving a new version of the m data blocks.

11. The method of claim 10 further comprising determining a new version of the p parity blocks from the new version of the m data blocks.

12. The method of claim 11 further comprising storing the new version of the m data blocks and the new version of the p parity blocks across the m plus p independent computing devices.

13. A method of operating a distributed storage system comprising the steps of:

generating a timestamp;

reading m data blocks from m replicated caches, each replicated cache comprising p plus one independent computing devices, each independent computing device of a replicated cache holding a particular data block in memory;

receiving confirmations from at least a majority of the independent computing devices of each replicated cache that a flush operation for the particular data block was initiated no later than a time indicated by the timestamp and that a more recent version of the particular data block has not been flushed;

determining p parity blocks from the m data blocks; and

storing the m data blocks and the p parity blocks across m plus p independent computing devices, each of the m plus p independent computing devices storing a single block selected from the m data blocks and the p parity blocks.

14. The method of claim 13 wherein the reading of each of the m data blocks further comprises reading a value timestamp, thereby reading m value timestamps.

15. The method of claim 14 wherein each confirmation indicates that a replying independent computing device determined that a flush timestamp was no later than the timestamp and that an export timestamp was no later than the value timestamp.

16. The method of claim 15 further comprising saving the value timestamp as a new version of the flush timestamp and the timestamp as a new version of the export timestamp on at least the majority of the independent computing devices of each replicated cache.

17. The method of claim 16 further comprising receiving storage-device confirmations from the m plus p independent computing devices that the m data blocks have been written to storage.

18. The method of claim 17 further comprising saving the export timestamp as a new version of the value timestamp on at least a second majority of the independent computing devices of each replicated cache.

19. The method of claim 18 further comprising overwriting the data with an empty indicator on at least the second majority of the independent computing devices of each replicated cache.

20. A computer readable medium comprising computer code for implementing a method of operating a distributed storage system, the method of operating the distributed storage system comprising the steps of:

reading m data blocks from a distributed cache, the distributed cache comprising memory of a plurality of independent computing devices that include redundancy for the m data blocks; and

storing the m data blocks and p parity blocks across m plus p independent computing devices, each of the m plus p independent computing devices storing a single block selected from the m data blocks and the p parity blocks.