Apparatus, system, and method for data storage using progressive raid

• US 8,015,440 B2
• Filed: 12/06/2007
• Issued: 09/06/2011
• Est. Priority Date: 12/06/2006
• Status: Active Grant

• Current Assignee: Jpmorgan Chase Bank NA As The Agent
• Original Assignee: Fusion-IO Incorporated (Western Digital Corporation)
• Inventors: Flynn, David, Atkisson, David, Thatcher, Jonathan, Zappe, Michael
• Primary Examiner(s): Beausoliel, Jr.; Robert W
• Assistant Examiner(s): Lottich; Joshua P
• Application Number:
  US11/952,115
• Publication Number:
  US 20080168304A1
• Time in Patent Office: 1,370 Days
• Field of Search: 711/114, 714/6, 714/7, 714/6.2, 714/6.21, 714/6.22, 714/6.24
• US Class Current: 714/6.24
• CPC Class Codes: G06F 1/183 Internal mounting support structures, e.g. for printed circuit boards, internal connecting means for buses G06F13/409
• CPC Class Codes: G06F 11/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 13/28 using burst mode transfer, e.g. direct memory access DMA, cycle steal G06F13/32 takes precedence
• CPC Class Codes: G06F 13/4022 using switching circuits, e.g. switching matrix, connection or expansion network G06F13/4009 takes precedence
• CPC Class Codes: G06F 13/426 using an embedded synchronisation, e.g. Firewire bus, Fibre Channel bus, SSA bus
• CPC Class Codes: G06F 2211/002 Bus
• CPC Class Codes: G06F 2211/103 Hybrid, i.e. RAID systems with parity comprising a mix of RAID types
• CPC Class Codes: G06F 2212/1032 Reliability improvement, data loss prevention, degraded operation etc
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/2022 Flash memory
• CPC Class Codes: G06F 2212/222 Non-volatile memory
• CPC Class Codes: G06F 2212/70 Details relating to dynamic memory management
• CPC Class Codes: G06F 2212/7203 Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7208 : Multiple device management, e.g. distributing data over multiple flash devices
• CPC Class Codes: G06F 3/0604 : Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0608 : Saving storage space on storage systems
• CPC Class Codes: G06F 3/0613 : in relation to throughput
• CPC Class Codes: G06F 3/0619 : in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0643 : Management of files
• CPC Class Codes: G06F 3/065 : Replication mechanisms
• CPC Class Codes: G06F 3/0652 : Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0656 : Data buffering arrangements
• CPC Class Codes: G06F 3/0659 : Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0679 : Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 3/0685 : Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays
• CPC Class Codes: G06F 3/0688 : Non-volatile semiconductor memory arrays
• CPC Class Codes: G06F 9/52 : Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/54 : Interprogram communication
• CPC Class Codes: H04L 67/02 : based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/1097 : for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H05K 7/1444 : Complex or three-dimensional-arrangements; Stepped or dual mother boards
• CPC Class Codes: H05K 7/1487 : Blade assemblies, e.g. blade cases or inner arrangements within a blade
• CPC Class Codes: Y02D 10/00 : Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

An apparatus, system, and method are disclosed for data storage with progressive redundant array of independent drives (“RAID”). A storage request receiver module, a striping module, a parity-mirror module, and a parity progression module are included. The storage request receiver module receives a request to store data of a file or of an object. The striping module calculates a stripe pattern for the data. The stripe pattern includes one or more stripes, and each stripe includes a set of N data segments. The striping module writes the N data segments to N storage devices. Each data segment is written to a separate storage device within a set of storage devices assigned to the stripe. The parity-mirror module writes a set of N data segments to one or more parity-mirror storage devices within the set of storage devices. The parity progression module calculates a parity data segment on each parity-mirror device in response to a storage consolidation operation, and stores the parity data segments. The storage consolidation operation is conducted to recover storage space and/or data on a parity-minor storage device.

Claims

1. An apparatus for reliable, high performance storage of data, the apparatus comprising:

a striping module that calculates a stripe pattern for data to be stored and writes N data segments of a stripe to N storage devices within a set of storage devices, wherein each of the N data segments is written to a separate storage device;

a parity-mirror module that writes the N data segments of the stripe to a parity-mirror storage device within the set of storage devices, the parity-mirror storage device being in addition to the N storage devices;

a parity progression module that calculates one or more parity data segments for the stripe and stores the one or more parity data segments for the stripe on the parity-mirror storage device, and

wherein one or more of the striping module, the parity-minor module, and the parity progression module comprise one or more of logic hardware and executable code stored on one or more computer readable storage media and executed by a processor.

2. The apparatus of claim 1, further comprising a parity alternation module that alternates, for each stripe, which of the storage devices within the storage device set are assigned to be the parity-mirror storage device for the stripe.

3. The apparatus of claim 1, wherein the storage device set comprises a first storage device set and further comprising a mirrored set module that creates one or more storage device sets in addition to the first storage device set, wherein each of the one or more additional storage device sets comprise at least an associated striping module that writes the N data segments to N storage devices of each of the one or more additional storage device sets.

4. The apparatus of claim 3, wherein each of the one or more additional storage device sets comprise an associated parity-minor module for storing a set of the N data segments and a parity progression module for calculating one or more parity data segments.

5. The apparatus of claim 1, further comprising an update module that updates a data segment by:

receiving an updated data segment, the updated data segment corresponding to an existing data segment of the N data segments stored on the N storage devices;

copying the updated data segment to a storage device of a stripe where the existing data segment is stored and to the parity-mirror storage device;

replacing the existing data segment stored on the storage device of the N storage devices with the updated data segment;

replacing the corresponding existing data segment stored on the parity-mirror storage device with the updated data segment in response to the parity progression module not having generated the one or more parity data segments on the parity-mirror storage device.

6. The apparatus of claim 1, wherein the storage device set comprises a first storage device set, the apparatus further comprising a mirror restoration module that recovers a data segment stored on a storage device of the first storage device set, the storage device of the first storage device set being unavailable, the data segment recovered from a minor storage device containing a copy of the data segment, the mirror storage device comprising one of a set of one or more storage devices storing a copy of the N data segments.

7. The apparatus of claim 6, wherein the minor restoration module recovers the data segment in response to a read request from a client to read the data segment.

8. The apparatus of claim 7, wherein the minor restoration module further comprises a direct client response module that sends the requested data segment to the client from the mirror storage device.

9. The apparatus of claim 1, further comprising a pre-consolidation restoration module that recovers a data segment stored on a storage device of the storage set in response to a request to read the data segment, the storage device being unavailable, the data segment recovered from the parity-mirror storage device prior to the parity progression module generating the one or more parity data segments on the parity-mirror storage device.

10. The apparatus of claim 1, further comprising a post-consolidation restoration module that recovers a data segment stored on a storage device of the storage set, the storage device being unavailable, the data segment recovered using one or more parity data segments stored on the parity-mirror storage device after the parity progression module generates the one or more parity data segments in response to a storage consolidation operation.

11. The apparatus of claim 1, further comprising

a data rebuild module that stores a recovered data segment on a replacement storage device in a rebuild operation, the recovered data segment matching an unavailable data segment stored on an unavailable storage device, the unavailable storage device comprising one of the N storage devices, the rebuild operation to restore data segments onto the replacement storage device to match data segments stored previously on the unavailable storage device, the recovered data segment recovered for the rebuild operation from one of

a matching data segment stored on the parity-mirror storage device if the matching data segment resides on the parity-mirror storage device;

a mirror storage device containing a copy of the unavailable data segment if the recovered data segment does not reside on the parity-mirror storage device, the mirror storage device comprising one of a set of one or more storage devices storing a copy of the N data segments; and

a regenerated data segment that is regenerated from one or more parity data segments and available data segments of the N data segments if the recovered data segment does not reside on the parity-mirror storage device or the mirror storage device.

12. The apparatus of claim 1, further comprising:

a parity rebuild module that rebuilds a recovered parity data segment on a replacement storage device in a parity rebuild operation, the recovered parity data segment matching an unavailable parity data segment stored on an unavailable parity-mirror storage device, the unavailable parity-mirror storage device comprising the parity-mirror storage device, the parity rebuild operation to restore parity data segments onto the replacement storage device to match parity data segments stored previously on the unavailable parity-minor storage device, the recovered parity data segment regenerated for the rebuild operation using one of

a parity data segment stored on a parity-minor storage device in a second set of storage devices storing a mirror copy of the stripe;

the N data segments stored on one of the N storage devices if the N data segments are available on the N storage devices;

one or more storage devices of the second set of storage devices storing copies of the N data segments if one or more of the N data segments are unavailable from the N storage devices and a matching parity data segment is not available on the second set of storage devices; and

the available data segments and non-matching parity data segments regardless of their location within the one or more sets of storage devices.

13. The apparatus of claim 1, wherein at least one of calculating a stripe pattern and writing N data segments to the N storage devices, writing a set of N data segments to a parity-minor storage device, and calculating the parity data segment occur on one of

a storage device of the set of storage devices;

a client; and

a third party RAID management device.

14. The apparatus of claim 1, wherein the parity progression module calculates one or more parity data segments for the stripe in response to a storage consolidation operation.

15. The apparatus of claim 1, wherein the parity progression module calculates the one or more parity data segments for the stripe from the N data segments stored on the parity-mirror storage device.

16. An apparatus for updating data in a progressive redundant array of independent drives (“

RAID”

) group, the apparatus comprising;

an update receiver module that receives an updated data segment corresponding to an existing data segment of an existing strip comprising N data segments and one or more corresponding parity data segments, the N data segments stored on storage devices of a set of storage devices assigned to the stripe, each of the parity data segments stored on one or more parity-mirror storage devices assigned to the stripe;

an update copy module that copies the updated data segment to a storage device where a corresponding existing data segment is stored and copies the updated data segment to the one or more parity-minor storage devices corresponding to the existing stripe; and

a parity update module that calculates one or more updated parity data segments for the one or more parity-minor storage devices of the existing stripe and stores the updated parity data segments on the one or more parity-mirror storage devices, and

wherein one or more of the update receiver module, the update copy module, and the parity update module comprise one or more of logic hardware and executable code stored on one or more computer readable storage media and executed by a processor.

17. The apparatus of claim 16, wherein the updated parity data segment is calculated from the existing parity data segment, the updated data segment, and the existing data segment.

18. The apparatus of claim 17, wherein the existing data segment is one or more of

maintained in place prior to reading the existing data segment for generation of the updated parity data segment;

copied to the parity-mirror storage device in response to the storage device of the N storage devices where the existing data segment is stored receiving a copy of the updated data segment; and

copied to the parity-mirror storage device in response to a storage consolidation operation on the storage device of the N storage devices where the existing data segment is stored.

19. The apparatus of claim 16, wherein the updated parity data segment is calculated from the existing parity data segment, the updated data segment, and a delta data segment, the delta data segment generated as a difference between the updated data segment and the existing data segment.

20. The apparatus of claim 19, wherein the delta data segment is one or more of

stored on the storage device storing the existing data segment prior to reading the delta data segment for generation of the updated parity data segment;

copied to the parity-mirror storage device in response to the storage device where the existing data segment is stored receiving a copy of the updated data segment; and

copied to the parity-mirror storage device in response to a storage consolidation operation on the storage device where the existing data segment is stored.

21. The apparatus of claim 16, wherein at least one of receiving an updated data segment, copying the updated data segment, and calculating the updated parity data segment occur on one of

a storage device of the set of storage devices;

a client, and

a third-party RAID management device.

22. The apparatus of claim 16, wherein the parity update module calculates the one or more updated parity data segments in response to a storage consolidation operation.

23. A system for reliable, high performance storage of data, the system comprising:

a set of storage devices assigned to a stripe, the set of storage devices comprising N storage devices and one or more parity-minor storage devices in addition to the N storage devices;

a striping module that calculates a stripe pattern for data to be stored and writes N data segments of a stripe to the N storage devices, wherein each of the N data segments is written to a separate storage device;

a parity-minor module that writes the N data segments of the stripe to each of the one or more parity-minor storage devices; and

a parity progression module that calculates one or more parity data segments for the stripe from the N data segments stored on the one or more parity-minor storage devices and stores a parity data segment on each of the one or more parity-minor storage devices,

wherein one or more of the striping module, the parity-minor module, and the parity progression module comprise one or more of logic hardware and executable code stored on one or more computer readable storage media and executed by a processor.

24. The system of claim 23, further comprising one or more servers that include the N storage devices and the one or more parity-mirror storage devices.

25. The system of claim 23, wherein the parity progression module calculates one or more parity data segments for the stripe in response to a storage consolidation operation.

26. A computer program product comprising a computer readable medium having computer usable program code executable to perform operations for reliable, high performance storage of data, the operations of the computer program product comprising:

calculating a stripe pattern for data to be stored and writing N data segments to N storage devices within a set of storage devices, wherein each of the N data segments is written to a separate storage device;

writing the N data segments of the stripe to one or more parity-minor storage devices within the set of storage devices, the one or more parity-mirror storage devices being in addition to the N storage devices; and

calculating a parity data segment for the stripe from the N data segments stored on a parity-mirror storage device and storing the parity data segment on the parity-mirror storage device.

27. A computer program product comprising a computer readable medium having computer usable program code executable to perform operations for reliable, high performance storage of updated data, the operations of the computer program product comprising:

receiving an updated data segment corresponding to an existing data segment of an existing stripe comprising N data segments and one or more corresponding parity data segments, the N data segments stored on storage devices of a set of storage devices assigned to the stripe, each of the parity data segments stored on one or more parity-mirror storage devices assigned to the stripe;

copying the updated data segment to a storage device where a corresponding existing data segment is stored and copying the updated data segment to the one or more parity-minor storage devices corresponding to the existing stripe; and

calculating one or more updated parity data segments for the one or more parity-mirror storage devices of the existing stripe and storing the updated parity data segments on the one or more parity-mirror storage devices.