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

• US 20060112222A1
• Filed: 11/04/2005
• Published: 05/25/2006
• Est. Priority Date: 11/05/2004
• Status: Active Grant

• Current Assignee: Storcentric DIP Lender LLC
• Original Assignee: Data Robotics Incorporated
• Inventors: Barrall, Geoffrey S.
• Granted Patent: US 7,814,273 B2
• Time in Patent Office: Days
• 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 expandable and contractible fault-tolerant storage system permits variously sized storage devices. Data is stored redundantly across one or more storage devices if possible. The layout of data across the one or more storage devices is automatically reconfigured as storage devices are added or removed in order to provide an appropriate level of redundancy for the data to the extent possible. A hash-based compression technique may be used to reduce storage consumption. Techniques for freeing unused storage blocks are also disclosed.

Claims

1. A method of storing data in a set of storage devices, the set having at least one storage device, the method comprising:

automatically determining a mixture of redundancy schemes, from among a plurality of redundancy schemes, for storing the data in the set of storage devices in order to provide fault tolerance and, when the set of storage devices happens to include a plurality of devices of different storage capacities, enhanced storage efficiency; and

storing the data in the set of storage devices using the mixture of redundancy schemes.

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

automatically reconfiguring data previously stored on a first arrangement of storage devices using a first redundancy scheme to being stored using one of (a) a second redundancy scheme on the same arrangement of storage devices, (b) a second redundancy scheme on a different arrangement of storage devices, and (c) the same redundancy scheme on a different arrangement of storage devices for accommodating without data loss at least one of expansion of capacity by the addition of another storage device to the set and contraction of capacity by the removal of a storage device from the set.

4. A method according to any of claims 1, 2, or 3, wherein the redundancy schemes are selected from the group including mirroring, striping with parity, RAID6, dual parity, diagonal Parity, Low Density Parity Check codes, and turbo codes.

5. A method according to any of claims 2 or 3, wherein reconfiguring the data comprises:

converting a mirrored pattern across two storage devices to a mirrored pattern on a single storage device.

6. A method according to any of claims 2 or 3, wherein reconfiguring the data comprises:

converting a mirrored pattern across a first pair of storage devices to a mirrored pattern across a second pair of storage devices.

7. A method according to any of claims 2 or 3, wherein reconfiguring the data comprises:

converting a striped pattern across three storage devices to a mirrored pattern across two storage devices.

8. A method according to any of claims 2 or 3, wherein reconfiguring the data comprises:

converting a first striped pattern across a first plurality of storage devices to a second striped pattern across a second plurality of storage devices.

9. A method according to any of claims 2 or 3, wherein reconfiguring the data comprises:

converting a mirrored pattern across one storage device to a mirrored pattern across two storage devices.

10. A method according to any of claims 2 or 3, wherein reconfiguring the data comprises:

converting a mirrored pattern on one storage device to a mirrored pattern on another storage device.

11. A method according to any of claims 2 or 3, wherein reconfiguring the data comprises:

converting a mirrored pattern across two storage devices to striped pattern across three storage devices.

12. A method according to any of claims 2 or 3, wherein reconfiguring the data comprises:

converting a first striped pattern across a first plurality of storage devices to a second striped pattern across a second plurality of storage devices including a storage device added to the set.

13. A method according to any of claims 1, 2, or 3, further comprising:

parsing an object into chunks, each chunk having particular content; and

storing in the storage system only chunks having unique content.

14. A method according to claim 13, wherein storing only chunks having unique content comprises:

storing in the storage system only chunks identified as having unique content based on a predetermined hash function.

15. A method according to claim 14, wherein storing only chunks identified as being unique based upon a predetermined hash function comprises:

computing a hash number for each chunk; and

storing in the storage system a unique identifier for the object linked to hash numbers for the stored chunks and location information therefor.

16. A method according to any of claims 15, wherein storing a unique identifier for the object includes using an object table that lists the unique identifier for the object and the hash numbers for the stored chunks.

17. A method according to any of claims 15, wherein storing location information includes storing in a chunk table a listing for each chunk stored therein including a representation of its physical location in the storage system.

18. A method according any of claims 13, further comprising:

translating objects stored in the storage system into a representation of at least one of a single storage device and a file system and an object storage system.

19. A method according to any of claims 13, further comprising:

managing physical allocation of storage of chunks in the storage system so as to provide fault-tolerant storage, even when the storage system may include storage devices of varying capacity.

20. A method according to any of claims 15, further comprising:

upon retrieving a particular chunk from the storage system, verifying the contents of the retrieved chunk based on the stored hash number for the chunk.

21. A method according to claim 20, wherein verifying the contents of the retrieved chunk based on the stored hash number for the chunk comprises:

computing a hash number for the retrieved chunk; and

comparing the computed hash number with the corresponding stored hash number for the chunk.

3. A method of storing data in a set of storage devices in a manner permitting dynamic expansion and contraction of the set, the set having at least one storage device, the method comprising:

storing data on the set of storage devices using a first redundancy scheme; and

upon a change in the composition of the set of storage devices, automatically reconfiguring the data on the set of storage devices using one of (a) a second redundancy scheme on the same arrangement of storage devices, (b) a second redundancy scheme on a different arrangement of storage devices, and (c) the same redundancy scheme on a different arrangement of storage devices.

22. A method of storing data in a set of storage devices, the method comprising:

storing data on the set of storage devices using at least one redundancy scheme;

detecting removal of a storage device from the set;

reconfiguring a portion of the data from the removed storage device using the remaining storage devices;

detecting reinsertion of the removed storage device into the set;

freeing regions of the reinserted storage device corresponding to said portion; and

refreshing any remaining regions of the reinserted storage device that may have been modified between removal and reinsertion.

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

a set of storage devices, the set having at least one storage device; and

a storage manager for storing the data in the set of storage devices using a mixture of redundancy schemes, the storage manager automatically determining the mixture of redundancy schemes, from among a plurality of redundancy schemes, for storing the data in the set of storage devices in order to provide fault tolerance and, when the set of storage devices happens to include a plurality of devices of different storage capacities, enhanced storage efficiency.

24. A system according to claim 23, wherein the storage manager automatically reconfigures data previously stored on a first arrangement of storage devices using a first redundancy scheme to being stored using one of (a) a second redundancy scheme on the same arrangement of storage devices, (b) a second redundancy scheme on a different arrangement of storage devices, and (c) the same redundancy scheme on a different arrangement of storage devices for accommodating without data loss at least one of expansion of capacity by the addition of another storage device to the set, and the contraction of capacity by the removal of a storage device from the set.

26. A system according to any of claims 23, 24, or 25, wherein the redundancy schemes are selected from the group including mirroring, striping with parity, RAID6, dual parity, diagonal Parity, Low Density Parity Check codes, and turbo codes.

27. A system according to any of claims 24 or 25, wherein the storage manager converts a mirrored pattern across two storage devices to a mirrored pattern on a single storage device.

28. A system according to any of claims 24 or 25, wherein the storage manager converts a mirrored pattern across a first pair of storage devices to a mirrored pattern across a second pair of storage devices.

29. A system according to any of claims 24 or 25, wherein the storage manager converts a striped pattern across three storage devices to a mirrored pattern across two storage devices.

30. A system according to any of claims 24 or 25, wherein the storage manager converts a first striped pattern across a first plurality of storage devices to a second striped pattern across a second plurality of storage devices.

31. A system according to any of claims 24 or 25, wherein the storage manager converts a mirrored pattern across one storage device to a mirrored pattern across two storage devices.

32. A system according to any of claims 24 or 25, wherein the storage manager converts a mirrored pattern on one storage device to a mirrored pattern on another storage device.

33. A system according to any of claims 24 or 25, wherein the storage manager converts a mirrored pattern across two storage devices to striped pattern across three storage devices.

34. A system according to any of claims 24 or 25, wherein the storage manager converts a first striped pattern across a first plurality of storage devices to a second striped pattern across a second plurality of storage devices including a storage device added to the set.

35. A system according to any of claims 23, 24, or 25, further comprising:

a chunk parser, for parsing an object into chunks, each chunk having particular content, wherein the storage manager stores in the set of storage devices only chunks having unique content.

36. A system according to claim 35, further comprising:

a hash code generator for generating a hash number for each chunk, the hash code generator and the physical storage manager in communication with an object table store and a chunk table store so that the object table lists a unique identifier for the object linked to hash numbers for the stored chunks and the chunk table lists for each chunk stored therein a representation of its physical location in the set of storage devices.

37. A system according to claim 35, further comprising:

a fault tolerant manager, in communication with the storage manager, for managing physical allocation of storage of chunks in the set of storage devices so as to provide fault-tolerant storage, even when the set of storage devices may include storage devices of varying capacity.

38. A system according any of claims 36, wherein, upon retrieving a particular chunk from the set of storage devices, the physical storage manager verifies the contents of the retrieved chunk based on the stored hash number for the chunk.

39. A system according to claim 38, wherein the physical storage manager computes a hash number for the retrieved chunk and compares the computed hash number with the corresponding stored hash number for the chunk.

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

a set of storage devices, the set having at least one storage device; and

a storage manager for storing the data in the set of storage devices, the storage manager storing data on the set of storage devices using a first redundancy scheme and, upon a change in the composition of the set of storage devices, automatically reconfiguring the data on the set of storage devices using one of (a) a second redundancy scheme on the same arrangement of storage devices, (b) a second redundancy scheme on a different arrangement of storage devices, and (c) the same redundancy scheme on a different arrangement of storage devices.

40. A method for freeing unused storage blocks in a storage system, the method comprising:

identifying a free block;

determining a logical sector address for the free block;

identifying a cluster access table entry for the free block based on the logical sector address;

decrementing a reference count associated with the cluster access table entry; and

freeing the block if the decremented reference count is zero.

41. A method according to claim 40, wherein identifying a free block comprises:

identifying a free block bitmap associated with the host filesystem; and

parsing the free block bitmap to identify clusters that are no longer being used by the filesystem.

42. A method according to claim 41, wherein identifying the free block bitmap associated with the host filesystem comprises:

maintaining a partition table;

parsing the partition table to locate an operating system partition;

parsing the operating system partition to locate a superblock; and

identifying the host filesystem based on the superblock.

43. A method according to claim 41, further comprising:

making a working copy of the free block bitmap, wherein the working copy of the free block bitmap is parsed to identify clusters that are no longer being used by the filesystem.