System for redundant storage of data

• US 7,152,077 B2
• Filed: 05/16/2003
• Issued: 12/19/2006
• Est. Priority Date: 05/16/2003
• 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, Spence, Susan, Frolund, Svend, Saito, Yasusuhi
• Primary Examiner(s): Gaffin, Jeffrey
• Assistant Examiner(s): PYO, MONICA M
• Application Number:
  US10/440,531
• Publication Number:
  US 20040230596A1
• Time in Patent Office: 1,313 Days
• Field of Search: 707/204, 707/203, 707/205, 715/511, 714/6
• US Class Current: 714/6.1
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1662 the resynchronized component or unit being a persistent storage device re-synchronization of failed mirror storage G06F11/2082; rebuild or reconstruction of parity RAID storage G06F11/1008
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

Data structure and timestamp management techniques for redundant storage. A plurality of storage devices are interconnected by a communication medium. At least two of the storage devices are designated devices for storing a block of data. Each designated device stores a version of the data and a first timestamp that is indicative of when the version of data was last updated. A second timestamp is indicative of a pending update to the block of data. When the update to the block of data is completed at one of the designated devices, the device discards the second timestamp. A storage device acting as coordinator instructs the device to discard the second timestamp. The designated storage devices store a plurality of blocks of data and corresponding timestamps according to a data structure. At least some of the entries in the data structure correspond to a range of data blocks that share a common timestamp. Entries in the data structure are arranged such that the ranges do not overlap.

Claims

1. A system for redundant storage of data comprising:

a plurality of storage devices and a communication medium for interconnecting the storage devices;

wherein at least two of the storage devices are designated storage devices for storing a block of data; and

wherein each designated storage device stores;

a version of the data; and

a first timestamp that is indicative of when the version of

data was last updated; and

a second timestamp that is indicative of a pending update to

the block of data;

wherein when the update to the block of data is completed at one of the designated storage devices, the one of the designated storage devices discards the second timestamp.

2. The system according to claim 1, wherein one of the storage devices acts as coordinator for a data update operation, and wherein the coordinator instructs the storage device to discard the second timestamp.

3. The system according to claim 1, wherein one of the storage devices acts as coordinator for a data update operation, and wherein the coordinator instructs the device to discard the first timestamp.

4. The system according to claim 1, wherein the designated storage devices each store a plurality of blocks of data and also store timestamps corresponding to ranges of the data blocks in a data structure.

5. The system according to claim 4, further comprising non-volatile memory at each designated storage device for storing the data structure.

6. The system according to claim 4, wherein at least some entries in the data structure correspond to a range of data blocks chat share a common timestamp.

7. The system according to claim 4, wherein each designated storage device inserts entries into the data structure such that the ranges do not overlap.

8. The system according to claim 7, wherein each designated storage device inserts a new entry to be added to the data structure by determining whether an existing entry in the data structure has a range that overlaps the range of the entry to be added and if an existing entry in the data structure has a range that does not overlap the range of the entry to be added, inserting the entry to be added at the identified position.

9. The system according to claim 8, wherein if an existing entry in the data structure has a range that overlaps the range of the entry to be added, the designated storage device identifies an existing entry in the data structure having a range that overlaps the range of the entry to be added and replaces the existing entry with one or more new entries including a new entry for any portion of the range of the existing entry that is not overlapped by the entry to be added, the new entry for the portion of the existing entry not overlapped having the timestamp of the existing entry, and the one or more new entries further including an entry for the portion of the range of the entry to be added that overlaps the range of the existing entry, the entry for the portion that overlaps having the timestamp of the entry to be added.

10. A system for redundant storage of data comprising:

a plurality of storage devices and a communication medium for interconnecting the storage devices,

wherein at least two of the storage devices are designated devices for storing a plurality of blocks of data,

wherein each designated storage device stores;

the plurality of blocks of data;

a first timestamp for each block of data that is indicative of when the data was last updated and, when a plurality of the blocks of data are updated concurrently, the first timestamp corresponds to a range of the data blocks; and

a second timestamp for a subset of the blocks of data indicating a pending update, when the pending update is completed, the designated storage device discards the second timestamp.

11. The system according to claim 10, wherein the timestamps are arranged according to a data structure.

12. The system according to claim 11, further comprising non-volatile memory at each designated storage device for storing the data structure.

13. The system according to claim 11, wherein at least some of the entries in the data structure correspond to a range of data blocks that share a common timestamp.

14. The system according to claim 13, wherein each designated storage device inserts entries into the data structure such that the ranges do not overlap.

15. The system according to claim 14, wherein each designated storage device inserts a new entry to be added to the data structure by determining whether an existing entry in the data structure has a range that overlaps the range of the entry to be added and if an existing entry in the data structure has a range that does not overlap the range of the entry to be added, inserting the entry to be added at the identified position.

16. The system according to claim 15, wherein if an existing entry in the data structure has a range that overlaps the range of the entry to be added, the designated storage device identifies an existing entry in the data structure having a range that overlaps the range of the entry to be added and replaces the existing entry with one or more new entries including a new entry for any portion of the range of the existing entry that is not overlapped by the entry to be added, the new entry for the portion of the existing entry not overlapped having the timestamp of the existing entry, and the one or more new entries further including an entry for the portion of the range of the entry to be added that overlaps the range of the existing entry, the entry for the portion that overlaps having the timestamp of the entry to be added.

17. The system according to claim 16, wherein if an additional existing entry in the data structure has a range that overlaps the range of the entry to be added, the additional existing entry is replaced with one or more new entries.