Apparatus, system, and method for a front-end, distributed raid

• US 8,019,940 B2
• Filed: 12/06/2007
• Issued: 09/13/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, Thatcher, Jonathan, Zappe, Michael, Strasser, John
• Primary Examiner(s): Dudek, Jr.; Edward J
• Application Number:
  US11/952,116
• Publication Number:
  US 20080256183A1
• Time in Patent Office: 1,377 Days
• Field of Search: 711/114, 711/E12.001, 710/8, 710/22
• 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 front-end, distributed redundant array of independent drives (“RAID”). A storage request receiver module receives a storage request to store object or file data in a set of autonomous storage devices forming a RAID group. The storage devices independently receive storage requests from a client over a network, and one or more of the storage devices are designated as parity-mirror storage devices for a stripe. The striping association module calculates a stripe pattern for the data. Each stripe includes N data segments, each associated with N storage devices. The parity-mirror association module associates a set of the N data segments with one or more parity-mirror storage devices. The storage request transmitter module transmits storage requests to each storage device. Each storage request is sufficient to store onto the storage device the associated data segments. The storage requests are substantially free of data.

Claims

1. An apparatus for high performance, distributed storage, the apparatus comprising:

a front-end controller executed on a processor, the front-end controller comprising;

a storage request receiver module that receives a storage request to store data in a storage device set, comprising a plurality of autonomous storage devices configured to independently receive and service storage requests from a client;

a striping association 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 associates each of the N data segments with one of N storage devices in the storage device set; and

a storage request transmitter module that transmits one or more storage requests to each of the N storage devices associated with a data segment, each storage request to configure a storage device to access data segments of the set of N data segments directly, independent of the front-end controller.

2. The apparatus of claim 1, further comprising a parity-mirror association module that associates the set of the N data segments with one or more parity-mirror storage devices in the storage device set, wherein the one or more parity-mirror storage devices are in addition to the N storage devices.

3. The apparatus of claim 2, further comprising a front-end parity generation module that calculates, independent of a client, a parity data segment for the stripe and stores the parity data segment on a parity-mirror storage device, the parity data segment calculated from the set of N data segments on the parity-mirror storage device.

4. The apparatus of claim 3, wherein the front-end parity generation module calculates the parity data segment within one of the storage devices of the storage device set and a third party redundant array of independent drives (“

RAID”

) management device.

5. The apparatus of claim 3, wherein the front-end parity generation module operates within a parity-mirror storage device.

6. The apparatus of claim 3, wherein the front-end parity generation module further calculates the parity data segment and transmits the calculated parity data segment to one or more additional parity-mirror storage devices in a second set of storage devices forming a mirror.

7. The apparatus of claim 3, 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 of the storage device set using one of

data segments on available storage devices of the storage device set;

a combination of a parity data segment from one or more of the parity-mirror storage devices and the available data segments on available storage devices of the storage device set;

a matching data segment that matches the unavailable data segment, wherein the matching data segment is read from a parity-mirror storage device; and

a matching data segment that matches the unavailable data segment, wherein the matching data segment is read from a mirror storage device containing a copy of the data segment, the mirror storage device comprising one of a mirrored device set of one or more storage devices storing a copy of the N data segments.

8. The apparatus of claim 7, wherein the data rebuild module operates and stores a recovered data segment while residing on one of a client, a third party redundant array of independent drives (“

RAID”

) management device, one or more storage devices of the storage device set, and a mirrored device set.

9. The apparatus of claim 3, further comprising a parity rebuild module that rebuilds a recovered parity data segment on a replacement storage device in a rebuild operation, the recovered parity data segment matching an unavailable parity data segment by one of

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

copying the parity data segment from a parity-mirror storage device in the storage device set; and

generating the parity data segment using one or more of the N data segments and parity data segments stored on the available storage devices of the storage device set and a mirror storage device containing a copy of the data segment, the mirror storage device comprising one of a mirrored device set of one or more storage devices storing a copy of the N data segments.

10. The apparatus of claim 9, wherein the parity rebuild module operates and rebuilds the recovered parity data segment while residing on one of the client, a third party redundant array of independent drives (“

RAID”

) management device, one or more storage devices of the storage device set, and a mirrored device set.

11. The apparatus of claim 3, wherein an autonomous storage device in the storage device set independently receiving storage requests comprises the storage device receiving storage requests to store data in a region within the storage device that comprises one or more of:

data segments that are assigned by the striping association module;

data segments that are assigned by the parity-mirror association module; and

parity data segments calculated by the front-end parity generation module, wherein data stored by executing at least one of the independent storage requests is not stored in a redundant array of independent drives (“

RAID”

) configuration.

12. The apparatus of claim 2, wherein the parity-mirror association module associates each data segment of a set of N data segments with a parity-mirror storage device, the parity-mirror devices comprising a mirror of the N data segments on the N storage devices.

13. The apparatus of claim 2, wherein

the striping association module calculates a stripe pattern and associates each data segment of each stripe with one or more of the storage devices of the storage device set while operating from within at least one of the client, one or more storage devices of the storage device set, and a third party redundant array of independent drives (“

RAID”

) management device; and

the parity-mirror association module associates a set of N data segments with one or more parity-mirror storage devices and the storage request transmitter module transmits the storage requests while operating from within at least one of the client, one or more storage devices of the storage device set, and a third party RAID management device.

14. The apparatus of claim 1, further comprising a data segment recovery module that operates and recovers a data segment while residing on one of the client, a third party redundant array of independent drives (“

RAID”

) management device, and one or more storage devices of the storage device set, and 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.

15. The apparatus of claim 1, wherein the one or more storage requests transmitted by the storage request transmitter module identify the storage devices that comprise the storage device set of the stripe.

16. The apparatus of claim 1, wherein each storage device manages data transfers, between the storage device and the client, of the one or more data segments and parity data segments associated with the storage device using one of direct memory access (“

DMA”

) and remote direct memory access (“

RDMA”

).

17. The apparatus of claim 1, wherein one or more data segments are broadcast or multicast to two or more of the storage devices within the storage device set and each storage device receiving the broadcast or multicast stores the one or more data segments associated with the storage device without storing data segments not associated with the storage device.

18. The apparatus of claim 1, further comprising a parity alternation module that alternates, for each stripe, which storage devices in the storage device set are designated as the one or more parity-mirror storage devices for the stripe.

19. The apparatus of claim 1, further comprising a peer-to-peer communication module that transmits and receives storage requests within the storage devices of the storage device set with peer devices within the storage device set and outside the storage device set.

20. The apparatus of claim 1, wherein one or more of the autonomous storage devices of the storage device set are allocated within a first redundant array of independent drives (“

RAID”

) group comprising a first set of storage devices for a first storage request and are allocated within a second RAID group comprising a second, different set of storage devices for a second storage request.

21. The apparatus of claim 1, wherein the storage request comprises an object request to store an object.

22. The apparatus of claim 1, wherein the processor is a field-programmable gate array.

23. An apparatus for high performance, distributed storage, the apparatus comprising:

a front-end controller, comprising;

a storage request receiver module that receives a storage request to store data in a storage device set comprising a plurality of autonomous storage devices, wherein each storage device in the storage device set is configured to communicate with storage clients and to receive storage requests from the storage clients independent of the front-end controller;

a striping association module that calculates a stripe pattern for data of the storage request, the stripe pattern comprising one or more stripes, each stripe comprising a set of N data segments, and associates each of the N data segments with one of N storage devices in the storage device set; and

a storage request transmitter module that transmits one or more storage requests to each storage device assigned a data segment, each storage request to configure a storage device to access data of a data segment associated with the storage device.

24. A computer program product comprising a non-transitory computer readable storage medium having computer usable program code executable to perform operations for high performance, distributed redundant array of independent drives (“

RAID”

), the operations of the computer program product comprising;

receiving at a front-end controller a storage request to store data in a storage device set comprising autonomous storage devices forming a RAID group, the storage devices communicatively coupled to storage clients independent of the front-end controller, and configured to independently receive storage requests from the storage clients;

calculating a stripe pattern for data of the storage request, the stripe pattern comprising one or more stripes, each stripe comprising a set of N data segments;

associating each of the N data segments with a storage device in the storage device set; and

transmitting one or more storage requests to each storage device in the storage device set, each storage request to configure a storage device to access data segments associated with the storage device.

25. The computer program product of claim 24, further comprising calculating, independent of a client, a parity data segment from the set of N data segments on a parity-mirror storage device;

and storing the parity data segment on a parity-mirror storage device.

26. A method for providing front-end distributed storage services, the method comprising:

receiving a storage request at a front-end controller, the storage request comprising a request to store data on a storage device set comprising a plurality of autonomous storage devices;

associating each of N data segments of the data with a respective storage device in the storage device set; and

transmitting storage requests to storage devices in the storage device set assigned data segments, the storage requests to configure a storage device to access data pertaining to a data segment assigned to the storage device,

wherein transmitting comprises one of broadcasting and multicasting a storage request to two or more of the storage devices in the storage device set, the two or more storage devices performing portions of the storage request pertaining to data segments associated with the storage device and ignoring portions of the storage request pertaining to data segments not associated with the storage device.

27. A method for providing front-end distributed storage services, the method comprising:

receiving a storage request at a front-end controller, the storage request comprising a request to store data on a storage device set comprising a plurality of autonomous storage devices;

associating each of N data segments in a stripe pattern of the data with a respective storage device in the storage device set; and

transmitting storage requests to storage devices associated with data segments of the stripe pattern, the storage requests to configure a storage device to store data of the segment,

wherein transmitting comprises one of broadcasting and multicasting a storage request comprising the data to two or more of the storage devices in the storage device set, and wherein each storage device receiving the storage request stores data of the storage request pertaining to data segments associated with the storage device without storing data pertaining to data segments not associated with the storage device.

28. A method for high performance, distributed storage, the method comprising:

receiving a storage request at a front-end controller device;

associating each of a plurality of N data segments of the storage request with respective autonomous storage devices in a storage device set;

transmitting a plurality of storage requests, each to configure an autonomous storage device in the storage device set to perform a storage operation pertaining to the storage request; and

storage devices in the storage device set accessing data pertaining to the storage request autonomously, independent of the front-end controller.

29. The method of claim 28, wherein one of the storage devices in the storage device set comprises the front-end controller device.

30. The method of claim 28, wherein one of the autonomous storage devices in the storage device set implements the front-end controller, the method further comprising:

replacing the front-end controller with a second front-end controller implemented on a second one of the autonomous storages in the storage device set.

31. The method of claim 28, wherein the storage device set comprises a redundant array of independent disks (“

RAID”

) group, the method further comprising;

each of the autonomous storage devices in the storage device set maintaining indicators of the autonomous storage devices in the RAID group; and

reconstructing the RAID group using the indicators.

32. The method of claim 28, further comprising:

determining at the front-end controller, a first redundant array of independent disks (“

RAID”

) group comprising a first set of storage devices for a first storage request; and

determining a second, different RAID group comprising a second, different set of autonomous storage devices for a second storage request.

33. The method of claim 32, wherein one of the autonomous storage devices stores data pertaining to a storage request of the client in a storage region comprising data of the first RAID group.

34. The method of claim 32, wherein one of the transmitted storage requests is to configure an autonomous storage device in the first RAID group to access data using one of a broadcast, a multicast, an anycast, and a unicast.

35. The method of claim 28, further comprising one of the autonomous storage devices in the storage device set receiving and servicing storage requests of a client while receiving and servicing storage requests from the front-end controller pertaining to first redundant array of independent disks (“

RAID”

) group.

36. The method of claim 28, wherein a transmitted storage request is to configure an autonomous storage device in the storage device set to identify network traffic comprising data of a data segment associated with the storage device.

37. A method for high performance, distributed storage, the method comprising:

receiving a plurality of client storage requests at a front-end controller of a storage device set comprising a plurality of autonomous storage devices;

P1 determining a different redundant array of independent disks (“

RAID”

) group for each of the client storage requests, each RAID group comprising a plurality of autonomous storage devices in the storage device set;

calculating a stripe pattern for a first one of the client storage requests, the stripe pattern associating each of N data segments of the first client storage request with an autonomous storage device in the RAID group determined for the first client storage request; and

transmitting a plurality of storage requests to the autonomous storage devices in the RAID group of the first client storage request, each to configure an autonomous storage device to perform a storage operation according to the stripe pattern, independent of the front-end controller.

38. The method of claim 37, further comprising:

assigning a different autonomous storage device in the storage device set to calculate parity data for each of a plurality of stripes in the stripe pattern.

39. The method of claim 37, further comprising:

calculating a first stripe pattern for a first one of the client storage requests; and

calculating a second, different stripe pattern for a second one of the client storage requests.

40. The method of claim 37, further comprising:

configuring each of the autonomous storage devices in a RAID group to maintain indicators of the autonomous storage devices in the RAID group; and

reconstructing the RAID group using the indicators.

41. The method of claim 37, wherein one of the transmitted storage requests configures an autonomous storage device to perform one of:

a direct memory access (“

DMA”

) operation directly with a client and without an intervening DMA controller, a remote memory access (“

RDMA”

) operation directly with the client and without an intervening DMA and/or RDMA controller, and a network data transfer with the client independent of the front-end controller.

42. A product comprising a non-transitory machine readable storage medium comprising executable code to perform operations for providing high performance, distributed storage, the operations comprising:

receiving a plurality of storage requests from respective clients at a front-end controller of a storage set comprising a plurality of autonomous storage devices, each storage device configured to communicate with the clients directly, independent of the front-end controller;

determining a different redundant array of independent disks (“

RAID”

) group for each of the client storage requests, each RAID group comprising a plurality of autonomous storage devices in the storage device set;

calculating a first stripe pattern for a first one of the client storage requests, the first stripe pattern associating data of the first client storage request with autonomous storage devices in a first RAID group determined for the first client storage request;

calculating a second, different stripe pattern for a second one of the client storage requests, the second stripe pattern associating data of the second storage request with autonomous storage devices in a second RAID group determined for the second client storage request; and

transmitting a plurality of storage requests to the autonomous storage devices in the first RAID group, each to configure an autonomous storage device to perform a storage operation independent of the front-end controller.