Method of operating replicated cache

• US 20070192544A1
• 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: Merchant, Arif, Veitch, Alistair, Frolund, Svend, Reuter, James, Jackson, James
• Granted Patent: US 7,761,663 B2
• Time in Patent Office: Days
• US Class Current: 711/135
• 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/183 by voting, the voting not being performed by the redundant components
• CPC Class Codes: G06F 12/0808 with cache invalidating means G06F12/0815 takes precedence
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache

Abstract

An embodiment of a method of operating a replicated cache includes generating a timestamp. A unit of data is read from memory of the replicated cache. The replicated cache comprises a plurality of independent computing devices. Each independent computing device comprises a processor and a portion of the memory. Confirmations are received from at least a majority of the independent computing devices that a flush operation for the unit of data was initiated no later than a time indicated by the timestamp and that a more recent version of the unit of data has not been flushed. The unit of data is provided to storage.

Claims

1. A method of operating a replicated cache comprising the steps of:

generating a timestamp;

reading a unit of data from memory of the replicated cache, the replicated cache comprising a plurality of independent computing devices, each independent computing device comprising a processor and a portion of the memory;

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

providing the unit of data to storage.

2. A method of operating a replicated cache comprising the steps of:

writing data and a value timestamp to memory of each of at least a first majority of independent computing devices;

generating a new timestamp;

reading the data and the value timestamp from at least one of the independent computing devices;

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

providing the data and the value timestamp to the storage.

3. The method of claim 2 wherein the step of writing the data and the value timestamp is performed by a write coordinator.

4. The method of claim 3 wherein the steps of generating the new timestamp, reading the data and the value timestamp, receiving the confirmations, and providing the data and the value timestamp to the storage are performed by a flush coordinator.

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

6. The method of claim 5 further comprising saving the value timestamp as a new version of the export timestamp and the new timestamp as a new version of the flush timestamp on at least the second majority of the independent computing devices.

7. The method of claim 6 further comprising receiving a confirmation from the storage that the data and the value timestamp have been written to the storage.

8. The method of claim 7 further comprising saving the export timestamp as a new version of the value timestamp on at least a third majority of the independent computing devices.

9. The method of claim 8 further comprising overwriting the data with an empty indicator on at least the third majority of the independent computing devices.

10. The method of claim 9 further comprising writing a new version of the data and a new value timestamp to the memory of each of at least a fourth majority of the independent computing devices.

11. The method of claim 10 further comprising:

reading the new version of the data and the new value timestamp from at least one of the independent computing devices; and

confirming that at least a fifth majority of the independent devices hold the new value timestamp and that no responding independent computing device has an order timestamp more recent than the new value timestamp.

12. The method of claim 9 further comprising reading the empty indicator and the new version of the value timestamp from at least one of the independent computing devices and confirming that at least a fourth majority of the independent computing devices hold the new version of the value timestamp.

13. The method of claim 12 further comprising reading the data and the value timestamp from the storage.

14. The method of claim 9 further comprising reading the empty indicator and the new version of the value timestamp from at least one of the independent computing devices and determining that at least one of the independent computing devices holds a more recent version of the value timestamp.

15. The method of claim 14 further comprising performing a recover operation.

16. The method of claim 6 further comprising:

receiving a new version of the data;

generating a new value timestamp;

generating a cache-bypass timestamp;

confirming that at least a third majority of the independent computing devices have the flush timestamp that is no later than the cache-bypass timestamp and the export timestamp that is no later than the new value timestamp; and

writing the new version of the data and the new value timestamp to storage.

17. The method of claim 16 further comprising receiving a confirmation from the storage that the new version of the data and the new value timestamp have been written to the storage.

18. The method of claim 17 further comprising saving the export timestamp as a newest version of the value timestamp on at least a fourth majority of the independent computing devices.

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

20. A computer readable medium comprising computer code for implementing a method of operating a replicated cache, the method of operating the replicated cache comprising the steps of:

generating a timestamp;

reading a unit of data from memory of the replicated cache, the replicated cache comprising a plurality of independent computing devices, each independent computing device comprising a processor and a portion of the memory;

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

providing the unit of data to storage.