APPARATUS, SYSTEM, AND METHOD FOR DATA STORAGE USING PROGRESSIVE RAID

• US 20080168304A1
• Filed: 12/06/2007
• Published: 07/10/2008
• 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
• Granted Patent: US 8,015,440 B2
• Time in Patent Office: Days
• US Class Current: 714/7
• 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-mirror storage device.

Claims

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

a storage request receiver module that receives a request to store data, the data comprising data of a file or of an object;

a striping module that calculates a stripe pattern for the data, the stripe pattern comprising one or more stripes, each stripe comprising a set of N data segments, and writes the N data segments of a stripe to N storage devices, wherein each of the N data segments is written to a separate storage device within a set of storage devices assigned to the stripe;

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

a parity progression module that calculates one or more parity data segments for the stripe in response to a storage consolidation operation, the one or more parity data segments calculated from the N data segments stored on the one or more parity-mirror storage devices, and stores a parity data segment on each of the one or more parity-mirror storage devices, the storage consolidation operation conducted to recover at least one of storage space and data on at least one of the one or more parity-mirror storage devices.

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 one or more parity-mirror storage devices for the stripe.

3. The apparatus of claim 1, wherein the storage consolidation operation is conducted autonomously from the storage operations of the storage receiver module, the striping module, and the parity-mirror module

4. 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 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 sets.

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

6. 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 the storage device of the stripe where the existing data segment is stored and to the one or more parity-mirror storage devices of the stripe;

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 one or more parity-mirror storage devices with the updated data segment in response to the parity progression module not having generated the one or more parity data segments on the one or more parity-mirror storage devices.

7. The apparatus of claim 1, wherein the set of first storage devices comprises a first storage device set and 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 mirror 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.

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

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

10. 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 a parity-mirror storage device prior to the parity progression module generating the one or more parity data segments on the one or more parity-mirror storage devices.

11. 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 one or more of the parity-mirror storage devices after the parity progression module generates the one or more parity data segments in response to a storage consolidation operation.

12. 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 a 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 one or more parity-mirror storage devices, 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 one or more parity-mirror storage devices or the mirror storage device.

13. 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 one of the one or more parity-mirror storage devices, 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-mirror storage device, the recovered parity data segment regenerated for the rebuild operation using one of

a parity data segment stored on a parity-mirror 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.

14. The apparatus of claim 1, wherein the N storage devices comprise N solid-state storage devices, each with a solid-state controller.

15. The apparatus of claim 1, wherein at least one of receiving an request to store data, calculating a stripe pattern and writing N data segments to the N storage devices, writing a set of N data segments to a parity-mirror 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.

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, the updated data segment corresponding to an existing data segment of an existing stripe, a stripe comprising data from a file or object divided into one or more stripes, each stripe comprising N data segments and one or more 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 generated from the N data segments of the stripe and stored on one or more parity-mirror storage devices assigned to the stripe, the set of storage devices comprising the one or more parity-mirror storage devices, the existing stripe comprising N existing data segments and one or more existing parity data segments;

an update copy module that copies the updated data segment to the storage device where the corresponding existing data segment is stored and to the one or more parity-mirror 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-mirror storage devices of the existing stripe in response to a storage consolidation operation, the storage consolidation operation conducted to recover at least one of storage space and data on one or more parity-mirror storage devices with the updated one or more parity data segments.

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 data-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 data-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 data-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 data-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 storage consolidation operation is conducted autonomously from the operations of the update receiver module and the update copy module.

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

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

a storage request receiver module that receives a request to store data, the data comprising data of a file or an object;

a striping module that calculates a stripe pattern for the data, the stripe pattern comprising one or more stripes, each stripe comprising a set of N data segments, and writes the 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 within the set of storage devices;

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

a parity progression module that calculates one or more parity data segments for the stripe in response to a storage consolidation operation, the one or more parity data segments calculated from the N data segments stored on the one or more parity-mirror storage devices, and stores a parity data segment on each of the one or more parity-mirror storage devices, the storage consolidation operation conducted autonomously from the storage operations of the storage receiver module, the striping module, and the parity mirror module, the storage consolidation operation conducted to recover at least one of storage space and data on the one or more parity-mirror storage devices.

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 24, further comprising one or more clients in the one or more servers, wherein the storage receiver module receives the request from at least one of the one or more clients.

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:

receiving a request to store data, the data comprising data of a file or of an object;

calculating a stripe pattern for the data, the stripe pattern comprising one or more stripes, each stripe comprising a set of N data segments, and writing the N data segments to N storage devices, wherein each of the N data segments is written to a separate storage device within a set of storage devices assigned to the stripe;

writing a set of N data segments of the stripe to one or more parity-mirror 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 in response to a storage consolidation operation, the parity data segment calculated from the N data segments stored on a parity-mirror storage device and storing the parity data segment on the parity-mirror storage device, the storage consolidation operation conducted autonomously from receiving a request to store N data segments, writing the N data segments to the N storage devices, or writing the N data segments to one or more parity-mirror storage devices, the storage consolidation operation conducted to recover at least one of storage space and data 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, the updated data segment corresponding to an existing data segment of an existing stripe, a stripe comprising data from a file or object divided into one or more stripes, each stripe comprising N data segments and one or more 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 generated from the N data segments of the stripe and stored on one or more parity-mirror storage devices assigned to the stripe, the set of storage devices comprising the one or more parity-mirror storage devices, the existing stripe comprising N existing data segments and one or more existing parity data segments;

copying the updated data segment to the storage device where the corresponding existing data segment is stored and to the one or more parity-mirror 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 in response to a storage consolidation operation, the storage consolidation operation conducted to recover at least one of storage space and data on one or more parity-mirror storage devices with the updated one or more parity data segments.