Array-based distributed storage system with parity

• US 20090216832A1
• Filed: 02/26/2008
• Published: 08/27/2009
• Est. Priority Date: 02/26/2008
• Status: Active Grant

• Current Assignee: Avid Technology Incorporated
• Original Assignee: Avid Technology Incorporated
• Inventors: Quinn, Steven C., Rabinowitz, Stanley
• Granted Patent: US 8,510,370 B2
• Time in Patent Office: Days
• US Class Current: 709/203
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity

Abstract

In one general aspect, a data access method is disclosed that includes directing data block write requests from different clients to different data storage servers based on a map. Data blocks referenced in the data block write requests are stored in the data storage servers. Data from the data write requests are also relayed to a parity server, and parity information is derived and stored for the blocks. This method can reduce the need for inter-server communication, and can be scaled across an arbitrary number of servers. It can also employ parity load distribution to improve the performance of file transfers.

Claims

1. A data access method, comprising:

directing a series of different data block write requests from one of a series of different clients to a plurality of different data storage servers based on a map,

storing data blocks referenced in the data block write requests in the data storage servers,

relaying the data from the data write requests to a parity server, and

deriving and storing parity information for the series of blocks.

2. The method of claim 1 further including independently generating the map by each of the clients.

3. The method of claim 2 wherein the step of independently generating the map by each of the clients uses a same predetermined permutation seed.

4. The method of claim 2 wherein the step of independently generating the map by each of the clients generates a repetitive map.

5. The method of claim 4 wherein the step of independently generating the map by each of the clients generates a map that is at least as long as the least common multiple of a number of data storage servers and a number of blocks for a super block for which parity is computed.

6. The method of claim 1 wherein the data storage servers and the parity server are members of a group of storage servers and wherein the map defines which of the group members are data storage servers and which of the group members is a parity server for particular write requests.

7. The method of claim 6 wherein the map changes which members of the group are used as a parity server to distribute load resulting from the step of deriving.

8. The method of claim 1 wherein the steps of directing, storing, relaying and deriving operate on a block size of a power of two Kilobytes.

9. The method of claim 1 further including the step of maintaining file system information that associates the blocks with files in a file system.

10. The method of claim 1 wherein the step of deriving parity information operates according to a row-diagonal parity coding scheme.

11. The method of claim 1 wherein the steps of relaying and deriving operate according to a single parity element.

12. The method of claim 1 wherein the steps of relaying and deriving operate according to row and diagonal parity elements.

13. The method of claim 12 wherein both row and diagonal parity are calculated on one of the parity servers and the non-native parity is forwarded to the other parity server.

14. An array-based distributed storage system, comprising:

a plurality of clients that each include map generation logic and a communication interface, and

a plurality of storage servers that each include

a communication interface responsive to the clients,

data storage logic responsive to the communication interface,

parity logic responsive to the communication interface,

selection logic operative to determine whether to enable the data storage logic or the parity logic for a particular data block based on results of the map generation logic for that block, and

relaying logic operative to relay a copy of a block to another of the servers in response to a determination by the selection logic that the data storage logic should be enabled for that block.

15. The system of claim 14 wherein the storage servers each further include a local copy of the same map generation logic as do the clients and wherein the selection logic for each of the servers is responsive to its local map generation logic to determine whether to enable the data storage logic or the parity logic for a particular data block.

16. The system of claim 14 wherein the map generation logic is operative to generate a map that distributes parity loading across the servers.

17. The system of claim 14 wherein the parity logic operates according to a row-diagonal parity scheme.

18. The system of claim 15 wherein the parity logic includes native parity logic operative to derive and store a native parity block and non-native parity logic operative to derive and forward a non-native parity block to another one of the servers.

19. An array-based distributed storage system, comprising:

means for directing a series of different data block write requests from one of a series of different clients to a plurality of different data storage servers based on a map,

means for storing data blocks referenced in the data block write requests in the data storage servers,

means for relaying the data from the data write requests to a parity server, and

means for deriving and storing parity information for the series of blocks.