Dynamically upgradeable fault-tolerant storage system permitting variously sized storage devices and method

• US 7,814,272 B2
• Filed: 11/04/2005
• Issued: 10/12/2010
• Est. Priority Date: 11/05/2004
• Status: Active Grant

• Current Assignee: Storcentric DIP Lender LLC
• Original Assignee: Data Robotics Incorporated
• Inventors: Terry, Julian M., Barrall, Geoffrey S.
• Primary Examiner(s): Shah; Sanjiv
• Assistant Examiner(s): DILLON, SAMUEL A
• Application Number:
  US11/267,836
• Publication Number:
  US 20060143380A1
• Time in Patent Office: 1,803 Days
• Field of Search: 711/114, 711/170, 711/173, 711/162, 711/165
• US Class Current: 711/114
• CPC Class Codes: G06F 11/1084 Degraded mode, e.g. caused by single or multiple storage removals or disk failures
• CPC Class Codes: G06F 11/1096 Parity calculation or recalculation after configuration or reconfiguration of the system
• CPC Class Codes: G06F 11/1658 Data re-synchronization of a redundant component, or initial sync of replacement, additional or spare unit
• 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/2069 Management of state, configuration or failover
• CPC Class Codes: G06F 11/2087 with a common controller
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 11/325 by lamps or LED's
• CPC Class Codes: G06F 2211/1004 Adaptive RAID, i.e. RAID system adapts to changing circumstances, e.g. RAID1 becomes RAID5 as disks fill up
• CPC Class Codes: G06F 2211/1023 Different size disks, i.e. non uniform size of disks in RAID systems with parity
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• 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/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: G11B 2220/415 Redundant array of inexpensive disks [RAID] systems
• CPC Class Codes: G11B 2220/65 wherein solid state memory is used for storing indexing information or metadata
• CPC Class Codes: G11B 27/11 by using information not detectable on the record carrier
• CPC Class Codes: G11B 27/329 on a disc [VTOC]

Abstract

A dynamically upgradeable fault-tolerant storage system permits a storage device to be replaced with a larger storage device. Data stored redundantly across multiple storage devices is reproduced on the replacement device, and the additional storage space on the replacement device is made available for redundantly storing additional data.

Claims

1. A method of storing data in a number of storage devices, the storage devices being under control of a storage manager external to the storage devices, the method comprising:

under control of the storage manager, storing fixed-size blocks of data in a first set of storage devices including at least a first storage device;

under control of the storage manager, causing a selected portion of the blocks to be stored, in a fault tolerant manner using block-based mirroring, in only the first storage device when the selected portion cannot be stored in a fault tolerant manner across a plurality of the storage devices; and

in response to a change of composition of the first set of storage devices resulting in a second set of storage devices, the second set including at least the first storage device and a new storage device, causing, under control of the storage manager, automatic reconfiguring of storage of the selected portion of the blocks, using information from the first storage device, such reconfiguring including using the new storage device as part of a storage pattern providing fault tolerance for the selected portion across a plurality of the storage devices in the second set, so that at least some storage space, on the first storage device, that had been utilized to provide fault tolerance for the selected portion becomes available for storage of other blocks of data.

2. A method according to claim 1, wherein the new storage device is added to the first set of storage devices to form the second set.

3. A method according to claim 1, wherein the new storage device replaces a storage device of the first set of storage devices to form the second set.

4. A method according to claim 3, further comprising:

making additional storage capacity from the new storage device available for storing additional data, if the new storage device has a larger storage capacity than the storage device it replaced.

5. A method according to claim 1, wherein data are stored in the first set of storage devices using a mixture of storage schemes.

6. A method according to claim 5, wherein the mixture of storage schemes is selected from among a plurality of storage schemes including at least a fault intolerant storage scheme, a fault tolerant storage scheme using only a single storage device, a fault tolerant storage scheme using two storage devices, and a fault tolerant storage scheme using at least three storage devices.

7. A method according to claim 6, wherein the fault tolerant storage schemes include at least one of mirroring, striping with parity, RAID6, dual parity, diagonal Parity, Low Density Parity Check codes, and turbo codes.

8. A method according to claim 1, wherein automatically reconfiguring the portion comprises storing the portion in a fault tolerant manner within the new storage device.

9. A method according to claim 8, wherein the portion is stored within the new storage device using one of mirroring, striping with parity, RAID6, dual parity, diagonal Parity, Low Density Parity Check codes, and turbo codes.

10. A method according to claim 1, wherein automatically reconfiguring the portion comprises storing the portion in a fault tolerant manner across multiple storage devices in the second set of storage devices, including the new storage device.

11. A method according to claim 10, wherein the portion is stored across the multiple storage devices using one of mirroring, striping with parity, RAID6, dual parity, diagonal Parity, Low Density Parity Check codes, and turbo codes.

12. A method according to claim 1, further comprising:

advertising a storage capacity for the number of storage devices greater than an actual storage capacity for the number of storage devices; and

mapping requests to store data in locations outside of the actual storage capacity to locations within the actual storage capacity.

13. A method according to claim 12, wherein mapping requests comprises:

maintaining a lookup table mapping requested locations to actual locations; and

indexing the lookup table according to the requested location to obtain the actual location.

14. A system for storing data, the system comprising:

a first set of storage devices having at least a first storage device; and

a storage manager, external to the storage devices, the storage manager being configured;

(i) to store fixed-size blocks of data in the first set of storage devices,

(ii) to cause a selected portion of the blocks to be stored, in a fault tolerant manner using block-based mirroring, in only the first storage device when the selected portion cannot be stored in a fault tolerant manner across a plurality of the storage devices, and

(iii) in response to a change of composition of the first set of storage devices resulting in a second set of storage devices including at least the first storage device and a new storage device, to automatically reconfigure storage of the selected portion of the blocks, using information from the first storage device, such reconfiguring including using the new storage device as part of a storage pattern providing fault tolerance for the selected portion across a plurality of the storage devices in the second set, so that at least some storage space, on the first storage device, that had been utilized to provide fault tolerance for the selected portion becomes available for storage of other blocks of data.

15. A system according to claim 14, wherein the new storage device is added to the first set of storage devices to form the second set.

16. A system according to claim 14, wherein the new storage device replaces a storage device of the first set of storage devices to form the second set.

17. A system according to claim 16, wherein the storage manager makes additional storage capacity from the new storage device available for storing additional data, if the new storage device has a larger storage capacity than the storage device it replaced.

18. A system according to claim 14, wherein the storage manager stores data in the first set of storage devices using a mixture of storage schemes.

19. A system according to claim 18, wherein the storage manager selects the mixture of storage schemes from among a plurality of storage schemes including at least a fault intolerant storage scheme, a fault tolerant storage scheme using only a single storage device, a fault tolerant storage scheme using two storage devices, and a fault tolerant storage scheme using at least three storage devices.

20. A system according to claim 19, wherein the fault tolerant storage schemes include at least one of mirroring, striping with parity, RAID6, dual parity, diagonal Parity, Low Density Parity Check codes, and turbo codes.

21. A system according to claim 14, wherein the storage manager stores the portion in a fault tolerant manner within the new storage device.

22. A system according to claim 21, wherein the storage manager stores the portion within the new storage device using one of mirroring, striping with parity, RAID6, dual parity, diagonal Parity, Low Density Parity Check codes, and turbo codes.

23. A system according to claim 14, wherein the storage manager stores the portion in a fault tolerant manner across multiple storage devices in the second set of storage devices including the new storage device.

24. A system according to claim 23, wherein the storage manager stores the portion across the multiple storage devices using one of mirroring, striping with parity, RAID6, dual parity, diagonal Parity, Low Density Parity Check codes, and turbo codes.

25. A system according to claim 14, wherein the storage manager is configured to advertise a storage capacity for the number of storage devices greater than an actual storage capacity for the number of storage devices, and configured to map requests to store data in locations outside of the actual storage capacity to locations within the actual storage capacity.

26. A system according to claim 25, wherein the storage manager maintains a lookup table mapping requested locations to actual locations, and indexes the lookup table according to the requested location to obtain the actual location.