Distributed data-storage system

• US 20070208790A1
• Filed: 03/06/2006
• Published: 09/06/2007
• Est. Priority Date: 03/06/2006
• Status: Abandoned Application

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Jackson, James, Veitch, Alistair, Reuter, James, Voigt, Douglas
• Application Number:
  US11/369,240
• Publication Number:
  US 20070208790A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory

Abstract

Various embodiments of the present invention provide methods, in distributed data-storage systems that associate one or more timestamps with each data block in each data-storage-component, for deciding whether or not a data block has been written. In certain embodiments of the present invention, a sparse database of timestamps associated with data blocks is maintained, each timestamp having a field that contains one of an indication of a time or sequence and a sentinel value indicating that the timestamp is garbage collected. When a timestamp is not found associated with a data block in a timestamp database, the data block is associated with a garbage-collected-timestamp state. In various embodiments of the present invention, data structures are maintained that store status information indicating whether or not any of a number of data blocks in each of a number of data-block-allocation units have been written. During replication, migration, or reconfiguration of a current segment of data blocks to a new segment of data blocks in these various embodiments, a data block is determined to be written or to be unwritten by determining, from the data structures, whether or not a data block-allocation unit containing the data block is written or unwritten.

Claims

1. A method, in a distributed data storage system that associates one or more timestamps with data blocks stored in data-storage-components, for deciding whether or not a data block has been written, the method comprising:

maintaining a sparse database of timestamps associated with data blocks, each timestamp having a field that contains one of an indication of a time or sequence and a sentinel value indicating that the timestamp is garbage collected; and

when a timestamp is not found associated with a particular data block in the sparse database of timestamps, associating the particular data block with a garbage-collected-timestamp state.

2. The method of claim 1 further including:

maintaining status data structures that store status information indicating whether or not any of a number of data blocks in each of a number of data-block-allocation units has been written; and

during replication, migration, or reconfiguration of a current segment of data blocks to a new segment of data blocks, determining whether or not a data block has been written by determining from the status data structures whether or not a data-block-allocation unit containing the data block is written or unwritten.

3. The method of claim 2 further including:

during replication, migration, or reconfiguration of the current segment of data blocks to the new segment of data blocks, when a timestamp is not found associated with a data block of the new segment of data blocks in the sparse database of timestamps, associating the data block with an unwritten state.

4. The method of claim 3 wherein replication, migration, or reconfiguration of a current segment to a new segment further includes:

copying written data blocks from the current segment of data blocks to the new segment of data blocks on a per-data-block-allocation-unit basis;

synchronizing the copied data blocks of the new segment of data blocks with corresponding data blocks of the current segment of data blocks; and

preventing reconstruction of a data block for which a timestamp mismatch is detected during a READ operation directed to the data block as a result of the data block being associated with a garbage-collected-timestamp state in the current segment and an unwritten state in the new segment.

5. Computer instructions stored within a computer-readable medium that implement the method of claim 1.

6. A distributed data storage system comprising:

component data-storage systems;

distributed data objects composed of data blocks, each distributed data object stored on one or more component data-storage systems under one or more redundancy schemes; and

a sparse timestamp database in each component data-storage system that stores current timestamps associated with each data block, wherein data blocks for which timestamps cannot be found in the sparse database of timestamps are assumed to occupy a garbage-collected-timestamp state.

7. The distributed data storage system of claim 6 further including data structures in the component data-storage system that store information concerning whether or not data blocks are allocated, initialized, unwritten, or written on a per-data-block-allocation-unit basis;

and

wherein, during replication, migration, or reconfiguration of a current data object to a new data object, when a timestamp is not found associated with a data block of the new data object, associating the data block with an unwritten state.

8. The distributed data storage system of claim 7 wherein control logic within a component data-storage system detects a timestamp mismatch during a READ operation directed to a data block, the timestamp mismatch occurring as a result of the data block being associated with a garbage-collected-timestamp state in a current data object and being associated with an unwritten state in a new data object, and prevents quorum-based data block reconstruction of the data block due to the timestamp mismatch.

9. A distributed data-storage system comprising:

component data-storage systems;

segments of data blocks belonging to virtual disk images distributed across the component data-storage systems, each segment of data blocks distributed according to a redundancy scheme, or according to two redundancy schemes during migration from a first redundancy scheme to a second redundancy scheme, and each segment of data blocks distributed according to a configuration, or according to two or more configurations during reconfiguration of the segment of data blocks; and

control logic within component data-storage systems that carries out segment-by-segment migration of all or a portion of the segments of data blocks of a virtual disk image to change a redundancy scheme by which the virtual-disk-image segments, or the portion of the virtual-disk-image segments, are distributed over a number of component data-storage systems.

10. The distributed data-storage system of claim 9 wherein the control logic within component data-storage systems carries out segment-by-segment migration of all or a portion of the segments of data blocks of a virtual disk image to both change the redundancy scheme by which the virtual-disk-image segments, or the portion of the virtual-disk-image segments, are distributed over a number of component data-storage systems as well as a set of component data-storage systems over which the virtual-disk-image segments, or the portion of the virtual-disk-image segments, are distributed.

11. The distributed data-storage system of claim 9 wherein a migration operation carried out on all or a portion of the segments of data blocks of a virtual disk image in an initial data state may be carried out to one of:

completion;

a mixed-redundancy state in which a portion of the segments of data blocks of the virtual disk image have migrated from a first redundancy scheme to a second redundancy scheme;

a mixed-redundancy and mixed-configuration state in which a portion of the segments of data blocks of the virtual disk image have migrated from a first redundancy scheme to a second redundancy scheme and have migrated from being distributed over a first set of component data-storage systems to a second set of component data-storage systems;

or

the initial data state, following a partial migration.

12. The distributed data-storage system of claim 9 wherein unwritten data blocks are not copied during migration.

13. The distributed data-storage system of claim 9 wherein reduced-redundancy data blocks are copied before full-redundancy data blocks during migration.

14. A distributed data-storage system comprising:

component data-storage systems;

segments of data blocks belonging to virtual disk images distributed across the component data-storage systems, each segment of data blocks distributed according to a configuration, or according to two or more configurations during reconfiguration of the segment of data blocks; and

control logic within component data-storage systems that carries out segment-by-segment reconfiguration of all or a portion of the segments of data blocks of a virtual disk image to change the sets of component data-storage systems over which the virtual disk image segments, or the portion of the virtual disk image segments, are distributed.

15. The distributed data-storage system of claim 14 wherein a reconfiguration operation carried out on all or a portion of the segments of data blocks of a virtual disk image in an initial data state may be carried out to one of:

completion;

a mixed-configuration state in which a portion of the segments of data blocks of the virtual disk image have been reconfigured from a first set of component data-storage systems to a second set of component data-storage systems;

or

the initial data state, following a partial reconfiguration.

16. The distributed data-storage system of claim 14 wherein unwritten data blocks are not copied during reconfiguration.

17. The distributed data-storage system of claim 14 wherein reduced-redundancy data blocks are copied before full-redundancy data blocks during reconfiguration.

18. A method, in a distributed data storage system that associates one or more timestamps with data blocks stored in data-storage-components, for deciding whether or not a particular data block has been written, the method comprising:

a means for determining a time or sequence for a particular data block as well as a sentinel value that indicates whether or not the time or sequence is current, or is instead garbage collected;

a means for determining whether or not any of a number of data blocks in a data-block-allocation units has been written;

when the means for determining a time or sequence for a particular data block does not provide time, sequence, or garbage-collected indication for a particular data block, associating the particular data block with a garbage-collected-timestamp state; and

during replication, migration, or reconfiguration of a current segment of data blocks to a new segment of data blocks, determining whether or not a data block has been written by determining from the status data structures whether or not a data-block-allocation unit containing the data block is written or unwritten.