Apparatus, system, and method for a shared, front-end, distributed RAID

• US 7,934,055 B2
• Filed: 12/06/2007
• Issued: 04/26/2011
• 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: Thatcher, Jonathan, Flynn, David, Zappe, Michael
• Primary Examiner(s): Kim; Matt
• Assistant Examiner(s): Fishburn; John P
• Application Number:
  US11/952,120
• Publication Number:
  US 20080256292A1
• Time in Patent Office: 1,237 Days
• Field of Search: None
• US Class Current: 711/114
• 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 a shared, front-end, distributed redundant array of independent drives (“RAID”). A multiple storage request receiver module receives at least two storage requests from at least two clients to store file or object data in one or more storage devices of a storage device set. The storage requests are concurrent and have at least a portion of the data in common. The storage device set includes autonomous storage devices forming a RAID group. Each storage device is capable of independently receiving storage requests from a client over a network. A striping module calculates a stripe pattern and writes N data segments per stripe to N storage devices. A parity-mirror module writes a set of N data segments to parity-mirror storage devices. A sequencer module ensures completion of a first storage request prior to executing a second storage request.

Claims

1. An apparatus for managing the reliable storage of shared data in a front-end, distributed RAID storage system by one or more clients, the apparatus comprising:

a multiple storage request receiver module that receives a first storage request and a second storage request from two clients for data in one or more storage devices of a storage device set, the first storage request arriving prior to the second storage request and processed concurrent with the second storage request, the first storage request comprising a request to store data, the first storage request and the second storage request referring to at least a portion of the data in common, the storage device set comprising autonomous storage devices forming a RAID group, each storage device independently receiving storage requests directly from a client;

a striping module that calculates a stripe pattern for data of the first storage request and writes N data segments of a stripe for the data of the first storage request to N storage devices within the storage device set, wherein each of the N data segments is written to a separate storage device in response to a subcommand to each of the separate storage devices, the subcommands derived from the first request; and

a sequencer module that ensures completion of the first storage request prior to executing the second storage request by determining completion of the subcommands derived from the first storage request prior to executing the second storage request.

2. The apparatus of claim 1, wherein the first storage request comprises updating one or more data segments of the data and the second storage request comprises one of updating one or more data segments of the data and reading one or more of the same one or more data segments of the data.

3. The apparatus of claim 1, wherein determining completion of the subcommands further comprises receiving an acknowledgement from each of the storage devices of the storage device set that received a subcommand derived from the first storage request.

4. The apparatus of claim 1, wherein the sequencer module selects the first storage request for execution prior to the second request by one of ordering the concurrent storage requests by arrival sequence, ordering the storage requests by timestamp, and by ordering the storage requests using selection criteria.

5. The apparatus of claim 1, wherein the apparatus comprises a master controller controlling servicing the first storage request and the second storage request.

6. The apparatus of claim 5, wherein the master controller operates within one of

a storage device in the storage device set;

a client; and

a third party RAID management device.

7. The apparatus of claim 5, wherein the master controller comprises one of a group of master controllers, each master controller able to service storage requests from two or more clients, the storage requests directed at the storage devices of the storage device set.

8. The apparatus of claim 7, further comprising a master validation module that confirms that a master controller servicing a received storage request is controlling execution of the storage request ahead of execution of one or more concurrent storage requests prior to execution of the received storage request, the one or more concurrent requests being received by other master controllers, the service request having at least a portion of the data in common with the one or more concurrent storage requests received by the other master controllers.

9. The apparatus of claim 7, further comprising a master determination module that sends a master determination request and receives a master determination response that is responsive to the master determination request, the master determination requests comprising a query to determine which master controller in the group of master controllers is assigned to execute a storage request, the master determination response enabling the master determination module to identify the master controller in the group of master controllers that is assigned to execute the storage request, wherein the master determination module determines the master controller identified as being assigned to execute the storage request from the master determination response prior to sending the storage request, the storage request comprising the portion of data common to the other storage requests.

10. The apparatus of claim 9, wherein the master determination module executes within a client.

11. The apparatus of claim 9, further comprising a master error module that returns an error indication in response to one of:

a multiple storage request receiver module that is controlled by a master controller receiving a storage request not controlled by the master controller; and

the master determination module determining that the master controller is no longer the determined master at the time of the completion of execution of the storage request.

12. The apparatus of claim 5, further comprising a master error module that returns an error indication in response to a multiple storage request receiver module that is controlled by a master controller receiving a storage request not controlled by the master controller.

13. The apparatus of claim 5, wherein the master controller controls storage requests to one or more secondary master controllers controlling storage requests for data stored on the storage devices of the storage device set.

14. The apparatus of claim 13, wherein the master controller acts as a secondary master controller for storage requests directed to data stored on the storage devices of the storage device set.

15. The apparatus of claim 5, wherein the master controller controls storage requests to one or more secondary master controllers, each secondary master controller controlling storage requests for data stored on storage devices of a storage device set unique to the secondary master controller.

16. The apparatus of claim 1, further comprising 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 storage device set, the parity-minor storage devices being in addition to the N storage devices.

17. The apparatus of claim 16, wherein at least one of receiving a request to store data, calculating a stripe pattern and writing N data segments to the N storage devices, and writing a set of N data segments to a parity-mirror storage device occur on one of

a storage device of the storage device set;

a client, and

a third party RAID management device.

18. The apparatus of claim 16, further comprising a parity generation module that calculates a parity data segment for the stripe and stores the parity data segment on a parity-minor storage device, the parity stripe calculated from the set of N data segments on the parity-minor storage device.

19. The apparatus of claim 16, 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-minor storage devices for the stripe.

20. The apparatus of claim 1, wherein the striping module calculates a stripe pattern for data of the second storage request and writes N data segments of a stripe for the data of the second storage request to N storage devices within the storage device set in response to the second storage request comprising a request to store data, wherein each of the N data segments is written to a separate storage device in response to a subcommand to each of the separate storage devices, the subcommands derived from the second request.

21. A system for managing the reliable storage of shared data in a front-end, distributed RAID storage system by one or more clients, the system comprising:

a storage device set of autonomous storage devices forming a RAID group, the storage devices independently receiving storage requests directly from a client;

a multiple storage request receiver module that receives a first storage request and a second storage request from two clients for data in the one or more storage devices of the storage device set, the first storage request arriving prior to the second storage request and processed concurrent with the second storage request, the first storage request comprising a request to store data, the first storage request and the second storage request referring to at least a portion of the data in common;

a striping module that calculates a stripe pattern for data of the first storage request and writes N data segments of a stripe for the data of the first storage request to N storage devices within the storage device set, wherein each of the N data segments is written to a separate storage device in response to a subcommand to each of the separate storage devices, the subcommands derived from the first request; and

a sequencer module that ensures completion of the first storage request prior to executing the second storage request by determining completion of the subcommands derived from the first storage request prior to executing the second storage request.

22. The system of claim 21, further comprising one or more servers comprising the storage devices of the storage device set.

23. The system of claim 22, further comprising the two clients within the one or more servers.

24. A method for managing the reliable storage of shared data in a front-end, distributed RAID storage system by one or more clients, the method comprising:

receiving a first storage request and a second storage request from two clients for data in one or more storage devices of a storage device set, the first storage request arriving prior to the second storage request and processed concurrent with the second storage request, the first storage request comprising a request to store data, the first storage request and the second storage request referring to at least a portion of the data in common, the storage device set comprising autonomous storage devices forming a RAID group, each storage device independently receiving storage requests directly from a client without an intervening storage controller;

calculating a stripe pattern for data of the first storage request and writing N data segments of a stripe for the data of the first storage request to N storage devices within the storage device set, wherein each of the N data segments is written to a separate storage device in response to a subcommand to each of the separate storage devices, the subcommands derived from the first request; and

ensuring completion of the first storage request prior to executing the second storage request by determining completion of the subcommands derived from the first storage request prior to executing the second storage request.

25. The method of claim 24, further comprising confirming that a master controller servicing a received storage request is controlling execution of the storage request ahead of execution of one or more concurrent storage requests prior to execution of the received storage request, the one or more concurrent requests being received by other master controllers, the service request having at least a portion of the data in common with the one or more concurrent storage requests received by the other master controllers.

26. The method of claim 24, further comprising sending a master determination request and receiving a master determination response that is responsive to the master determination request, the master determination requests comprising a query to determine which master controller in the group of master controllers is assigned to execute a storage request, the master determination response enabling the master determination module to identify the master controller in the group of master controllers that is assigned to execute the storage request, wherein the master determination module determines the master controller identified as being assigned to execute the storage request from the master determination response prior to sending the storage request, the storage request comprising the portion of data common to the other storage requests.

27. The method of claim 26, further comprising returning an error indication in response to one of:

receiving a storage request by a master controller not determined to be master controller for data referenced by the storage request; and

determining that the master controller for data referenced by the storage request is no longer the determined master at the time of the completion of execution of the storage request.

28. The method of claim 24, wherein determining completion of subcommands further comprises receiving an acknowledgement from each of the storage devices of the storage device set that received a subcommand derived from the first storage request.

29. The method of claim 24, further comprising calculating a stripe pattern for data of the second storage request and writing N data segments of a stripe for the data of the second storage request to N storage devices within the storage device set in response to the second storage request comprising a request to store data, wherein each of the N data segments is written to a separate storage device in response to a subcommand to each of the separate storage devices, the subcommands derived from the second request.