Methods and systems for hierarchical management of distributed data

• US 20070214314A1
• Filed: 03/07/2006
• Published: 09/13/2007
• Est. Priority Date: 03/07/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: Reuter, James
• Application Number:
  US11/369,653
• Publication Number:
  US 20070214314A1
• Time in Patent Office: Days
• US Class Current: 711/114
• 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/2056 by mirroring
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 2211/1059 Parity-single bit-RAID5, i.e. RAID 5 implementations
• CPC Class Codes: G06F 2211/1061 Parity-single bit-RAID4, i.e. RAID 4 implementations
• CPC Class Codes: G06F 3/0607 by facilitating the process of upgrading existing storage systems, e.g. for improving compatibility between host and storage device
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0667 at data level, e.g. file, record or object virtualisation
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Various method and system embodiments of the present invention are directed to hierarchical control logic within each component data-storage system of a distributed data-storage system composed of networked component data-storage systems over which virtual disks, optionally replicated as virtual-disk images, composed of data segments in turn composed of data blocks, are distributed at the granularity of segments. Each data segment is distributed according to a configuration. The hierarchical control logic includes, in one embodiment of the present invention, a top-level coordinator, a virtual-disk-image-level coordinator, a segment-configuration-node-level coordinator, a configuration-group-level coordinator, and a configuration-level coordinator.

Claims

1. Hierarchical control logic within each component data-storage system of a distributed data-storage system composed of networked component data-storage systems over which virtual disks, optionally replicated as virtual-disk images, composed of data segments in turn composed of data blocks, are distributed at the granularity of segments, each data segment distributed according to a configuration, the hierarchical control logic comprising:

a top-level coordinator;

a virtual-disk-image-level coordinator;

a segment-configuration-node-level coordinator;

a configuration-group-level coordinator; and

a configuration-level coordinator.

2. The hierarchical control logic of claim 1 wherein each of the different coordinators carries out a storage-register-model-based consistency method associated with the level of the coordinator.

3. The hierarchical control logic of claim 2 wherein storage-register-model-based consistency methods include:

a quorum-based storage-register-model-based consistency method;

an m-quorum-based storage-register-model-based consistency method; and

a totality-based storage-register-model-based consistency method.

4. The hierarchical control logic of claim 3 wherein the top-level coordinator is associated with a virtual-disk level of a hierarchical data-storage model that describes a data state of the distributed data-storage system.

5. The hierarchical control logic of claim 4 wherein the virtual-disk level of the hierarchical data-storage model contains virtual-disk tables containing entries representing virtual disk images, the top-level coordinator managing access to virtual disks.

6. The hierarchical control logic of claim 3 wherein the virtual-disk-image-level coordinator is associated with a virtual-disk-image level of a hierarchical data-storage model that describes a data state of the distributed data-storage system.

7. The hierarchical control logic of claim 6 wherein the virtual-disk-image level of the hierarchical data-storage model contains a number of virtual-disk-image tables, each virtual-disk-image table representing one replicate of a virtual disk, generally stored on a subset of geographically co-located component data-storage systems, each virtual-disk-image table containing entries that represent virtual-disk segments, the virtual-disk-image-level coordinator managing access virtual disk images.

8. The hierarchical control logic of claim 3 wherein the segment-configuration-node-level coordinator is associated with a segment-configuration-node level of a hierarchical data-storage model that describes a data state of the distributed data-storage system and wherein the segment-configuration-node-level coordinator employs totality-based storage-register-model-based consistency.

9. The hierarchical control logic of claim 8 wherein the segment-configuration-node level of the hierarchical data-storage model contains a number of segment configurations nodes, each segment configuration node representing one or more virtual disk segment distributed according to one or two redundancy schemes over a number of component data-storage systems, the segment-configuration-node-level coordinator managing migration of a virtual disk segment from a first redundancy scheme to a second redundancy scheme.

10. The hierarchical control logic of claim 3 wherein the configuration-group-level coordinator is associated with a configuration-group level of a hierarchical data-storage model that describes a data state of the distributed data-storage system and wherein the configuration-group-level coordinator employs quorum-based techniques for configuration groups using mirroring redundancy schemes and employs m-quorum-based techniques for configuration groups using erasure coding redundancy schemes.

11. The hierarchical control logic of claim 10 wherein the configuration-group level of the hierarchical data-storage model contains a number of configuration-group data-structure elements, each configuration-group data-structure element representing one or more virtual disk segments distributed in a distribution configuration according to a redundancy scheme over a number of component data-storage systems, the configuration-group-level coordinator managing reconfiguration of a virtual disk segment.

12. The hierarchical control logic of claim 3 wherein the configuration-level coordinator is associated with a configuration level of a hierarchical data-storage model that describes a data state of the distributed data-storage system and wherein a configuration-level coordinator employs quorum-based techniques for configurations using mirroring redundancy schemes and employs m-quorum-based techniques for configurations using erasure coding redundancy schemes.

13. The hierarchical control logic of claim 12 wherein the configuration level of the hierarchical data-storage model contains a number of configuration data-structure elements, each configuration data-structure element representing one or more virtual disk segments distributed in a distribution configuration according to a redundancy scheme over a number of component data-storage systems, the configuration-level coordinator determining component data-storage-system health status and facilitating handling of component data-storage-system failure.

14. A method for managing data within a distributed data-storage system composed of networked component data-storage systems, the method comprising:

distributing data at the granularity of segments across component data-storage systems, the data hierarchically organized within virtual disks, optionally replicated as virtual-disk images, composed of data segments, the data segments in turn composed of data blocks;

maintaining a hierarchical data structure representing a data state of the distributed data, the hierarchical data structure including a virtual disk level, a virtual-disk-image level, a segment-configuration-node-level, a configuration-group level, and a configuration level; and

executing hierarchically ordered coordinator routines, each coordinator routine associated with a hierarchical-data-structure level, each hierarchical coordinator routine managing data access and data consistency at the hierarchical level represented by the hierarchical data-structure level with which the hierarchical coordinator routine is associated.

15. The method of claim 14 wherein the hierarchical coordinator routines include:

a top-level coordinator;

a virtual-disk-image-level coordinator;

a segment-configuration-node-level coordinator;

a configuration-group-level coordinator; and

a configuration-level coordinator.

16. The method of claim 15 wherein each of the different coordinators carries out a storage-register-model-based consistency method associated with the level of the coordinator.

17. The method of claim 16 wherein storage-register-model-based consistency methods include:

a quorum-based storage-register-model-based consistency method;

an m-quorum-based storage-register-model-based consistency method; and

a totality-based storage-register-model-based consistency method.

18. The method of claim 17 wherein the top-level coordinator is associated with a virtual-disk level of a hierarchical data-storage model that describes a data state of the distributed data-storage system.

19. The method of claim 18 wherein the virtual-disk level of the hierarchical data-storage model contains virtual-disk tables containing entries representing virtual disk images, the top-level coordinator managing access to virtual disks.

20. The method of claim 17 wherein the virtual-disk-image-level coordinator is associated with a virtual-disk-image level of a hierarchical data-storage model that describes a data state of the distributed data-storage system.

21. The method of claim 20 wherein the virtual-disk-image level of the hierarchical data-storage model contains a number of virtual-disk-image tables, each virtual-disk-image table representing one replicate of a virtual disk, generally stored on a subset of geographically co-located component data-storage systems, each virtual-disk-image table containing entries that represent virtual-disk segments, the virtual-disk-image-level coordinator managing access virtual disk images.

22. The method of claim 17 wherein the segment-configuration-node-level coordinator is associated with a segment-configuration-node level of a hierarchical data-storage model that describes a data state of the distributed data-storage system and wherein the segment-configuration-node-level coordinator employs totality-based storage-register-model-based consistency.

23. The method of claim 22 wherein the segment-configuration-node level of the hierarchical data-storage model contains a number of segment configurations nodes, each segment configuration node representing one or more virtual disk segments distributed according to one or two redundancy schemes over a number of component data-storage systems, the segment-configuration-node-level coordinator managing migration of a virtual disk segment from a first redundancy scheme to a second redundancy scheme.

24. The method of claim 17 wherein the configuration-group-level coordinator is associated with a configuration-group level of a hierarchical data-storage model that describes a data state of the distributed data-storage system and wherein the configuration-group-level coordinator employs quorum-based techniques for configuration groups using mirroring redundancy schemes and employs m-quorum-based techniques for configuration groups using erasure coding redundancy schemes.

25. The method of claim 24 wherein the configuration-group level of the hierarchical data-storage model contains a number of configuration-group data-structure elements, each configuration-group data-structure element representing a virtual disk segment distributed in a distribution configuration according to a redundancy scheme over a number of component data-storage systems, the configuration-group-level coordinator managing reconfiguration of a virtual disk segment.

26. The method of claim 17 wherein the configuration-level coordinator is associated with a configuration level of a hierarchical data-storage model that describes a data state of the distributed data-storage system and wherein a configuration-level coordinator employs quorum-based techniques for configurations using mirroring redundancy schemes and employs m-quorum-based techniques for configurations using erasure coding redundancy schemes.

27. The method of claim 26 wherein the configuration level of the hierarchical data-storage model contains a number of configuration data-structure elements, each configuration data-structure element representing a virtual disk segment distributed in a distribution configuration according to a redundancy scheme over a number of component data-storage systems, the configuration-level coordinator determining component data-storage-system health status and facilitating handling of component data-storage-system failure.

28. Computer instructions, stored in a computer-readable memory, that encode a method for managing data within a distributed data-storage system composed of networked component data-storage systems, the method comprising:

distributing data at the granularity of segments across component data-storage systems, the data hierarchically organized within virtual disks, optionally replicated as virtual-disk images, composed of data segments, the data segments in turn composed of data blocks;

maintaining a hierarchical data structure representing a data state of the distributed data, the hierarchical data structure including a virtual disk level, a virtual-disk-image level, a segment-configuration-node-level, a configuration-group level, and a configuration level; and

executing hierarchically ordered coordinator routines, each coordinator routine associated with a hierarchical-data-structure level, each hierarchical coordinator routine managing data access and data consistency at the hierarchical level represented by the hierarchical data-structure level with which the hierarchical coordinator routine is associated.

29. A distributed data-storage system comprising:

a number of component data-storage systems across which one or more segments of data blocks are distributed according to one or more redundancy schemes; and

hierarchical control logic within the number of component data-storage systems that manages access to, and manages consistency of, the one or more segments of data blocks, the hierarchical control logic comprising a first control-logic level responsible for managing consistency of the one or more segments of data blocks during migration and a second control-logic level responsible for managing consistency of the one or more segments of data blocks during reconfiguration of the one or more segments of data blocks.

30. The distributed data-storage system of claim 29 wherein the first and second control-logic levels manage consistency by a consistency method selected from consistency methods including:

a quorum-based storage-register-model-based consistency method;

an m-quorum-based storage-register-model-based consistency method; and

a totality-based storage-register-model-based consistency method.

31. A distributed data-storage system comprising:

a number of component data-storage systems across which one or more segments of data blocks are distributed according to one or more redundancy schemes; and

a means for managing access to, and consistency of, one or more virtual disks that each includes a number of segments of data blocks distributed according to one or more redundancy schemes across a number of component data-storage systems of the distributed data-storage system in a hierarchical fashion, including

a means for managing access to, and consistency of, one or more virtual disks during replication at a first level,

a means for managing access to, and consistency of, one or more segments of data blocks during migration at a second level, and

a means for managing access to, and consistency of, one or more segments of data blocks during reconfiguration at a third level.