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

• US 8,412,979 B2
• Filed: 07/13/2011
• Issued: 04/02/2013
• Est. Priority Date: 12/06/2006
• Status: Expired due to Fees

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Fusion-IO Incorporated (Western Digital Corporation)
• Inventors: Flynn, David, Atkisson, David, Thatcher, Jonathan, Zappe, Michael
• Primary Examiner(s): Lottich, Joshua P
• Application Number:
  US13/182,315
• Publication Number:
  US 20120179869A1
• Time in Patent Office: 629 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-mirror storage device.

Claims

1. A method for reliable, high performance storage of data, the method 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 a parity-mirror storage device within the set of storage devices, the parity-mirror storage device being in addition to the N storage devices; and

recovering a data segment stored on an unavailable storage device of the N storage devices in response to a request to read the data segment, the data segment recovered from a corresponding data segment stored on the parity-mirror storage device prior to a parity progression module generating one or more parity data segments for the stripe and storing the one or more parity data segments on the parity-mirror storage device.

2. The method of claim 1, further comprising calculating the one or more parity data segments for the stripe and storing the one or more parity data segments on the parity-mirror storage device in response to a storage consolidation operation.

3. The method of claim 2, wherein the storage consolidation operation comprises one of a garbage collection operation, a defragmentation operation, an error recovery operation, and a data recovery operation.

4. The method of claim 1, further comprising calculating the one or more parity data segments for the stripe and storing the one or more parity data segments on the parity-mirror storage device in response to a storage space requirement on the parity-mirror storage device.

5. The method of claim 1, further comprising delaying generating the one or more parity data segments until available storage space drops below a minimum threshold.

6. The method of claim 1, further comprising calculating the one or more parity data segments for the stripe from the N data segments stored on the parity-mirror storage device.

7. The method of claim 1, further comprising:

receiving an updated data segment, the updated data segment corresponding to an existing data segment of the N data segments;

replacing the existing data segment stored on a 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 prior to the parity progression module generating one or more parity data segments for the stripe and storing the one or more parity data segments on the parity-mirror storage device.

8. The method of claim 1, further comprising storing the recovered data segment onto a replacement storage device in a 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 a matching data segment stored on the parity-mirror storage device.

9. The method of claim 1, further comprising creating one or more storage device sets in addition to the storage device set, wherein each of the one or more additional storage device sets write the N data segments to N storage devices of each of the one or more additional storage sets and store a set of the N data segments on a parity-mirror storage device.

10. A method for reliable, high performance storage of data, the method 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 a parity-mirror storage device within the set of storage devices, the parity-mirror storage device being in addition to the N storage devices; and

recovering a data segment for an unavailable storage device of the N storage devices using one or more parity data segments stored on the parity-mirror storage device by a parity progression module.

11. The method of claim 10, further comprising calculating the one or more parity data segments for the stripe and storing the one or more parity data segments on the parity-mirror storage device in response to a storage consolidation operation.

12. The method of claim 10, further comprising calculating the one or more parity data segments for the stripe and storing the one or more parity data segments on the parity-mirror storage device in response to a storage space requirement on the parity-mirror storage device.

13. The method of claim 10, further comprising calculating the one or more parity data segments for the stripe from the N data segments of the stripe stored on the parity-mirror storage device.

14. The method of claim 10, further comprising delaying generating the one or more parity data segments until available storage space drops below a minimum threshold.

15. The method of claim 10, further comprising:

receiving an updated data segment corresponding to an existing data segment of the N data segments;

copying the updated data segment to a storage device storing a corresponding existing data segment and copying the updated data segment to the parity-mirror storage device; and

calculating one or more updated parity data segments for the parity-mirror storage device and storing the one or more updated parity data segments on the parity-mirror storage device.

16. The method of claim 10, further comprising storing a recovered data segment onto a replacement storage device in a rebuild operation to restore data segments onto the replacement storage device, the recovered data segment recovered for the rebuild operation from available data segments of the N data segments.

17. The method of claim 10, further comprising rebuilding a recovered parity data segment matching an unavailable parity data segment stored on an unavailable parity-mirror storage device, the recovered parity data segment rebuilt using one of a second set of storage devices storing a mirror copy of the stripe and available data segments stored on one or more of the set of storage devices and the second set of storage devices.

18. The method of claim 10, further comprising creating one or more storage device sets in addition to the storage device set, wherein each of the one or more additional storage sets, store a set of the N data segments on the parity-mirror storage device, calculate the one or more parity data segments and store the one or more parity data segments on the parity-mirror storage device, calculate one or more parity data segments and store the one or more parity data segments one the parity-mirror storage device.

19. A system comprising:

a set of storage devices comprising N storage devices and a parity-mirror storage device in addition to the N storage devices;

a processor;

a memory comprising modules for execution by the processor, the memory comprising;

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

a parity-mirror module configured to write the N data segments of the stripe to the parity-mirror storage device within the set of storage devices; and

a pre-consolidation restoration module configured to recover a data segment stored on an unavailable storage device of the N storage devices in response to a request to read the data segment, the data segment recovered from a corresponding data segment stored on the parity-mirror storage device prior to a parity progression module generating one or more parity data segments for the stripe and storing the one or more parity data segments on the parity-mirror storage device.

20. The system of claim 19, further comprising a server housing the set of storage devices, the processor, and the memory.