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.