Efficient High Availability Storage Systems

• US 20140189053A1
• Filed: 05/24/2013
• Published: 07/03/2014
• Est. Priority Date: 12/31/2012
• Status: Active Grant

• Current Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Inventors: Shi, Guangyu, Xu, Xiangyang, Li, Zhi
• Granted Patent: US 9,037,679 B2
• Time in Patent Office: Days
• US Class Current: 709/217
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 2211/1009 Cache, i.e. caches used in RAID system with parity
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 2211/105 On the fly coding, e.g. using XOR accumulators
• CPC Class Codes: G06F 2211/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/108 characterised by resources being split in blocks or fragments
• 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: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

A server configured to form part of a data protection group, wherein the server comprises a memory, a transceiver configured to receive a request to store a data file from another device, and a processor coupled to the memory and the transceiver and configured to acquire the request to store a data file, write the data file to a container in the memory, and encode the container contents when the container becomes full to generate a plurality of encoded blocks, wherein the transceiver is further configured to distribute the plurality of encoded blocks over peer servers in the data protection group.

Claims

1. A server configured to form part of a data protection group, wherein the server comprises:

a memory;

a transceiver configured to receive a request to store a data file from another device; and

a processor coupled to the memory and the transceiver and configured to;

acquire the request to store a data file,

write the data file to a container in the memory; and

encode the container contents when the container becomes full to generate a plurality of encoded blocks,

wherein the transceiver is further configured to;

distribute the plurality of encoded blocks over peer servers in the data protection group.

2. The server of claim 1, wherein the transceiver is further configured to send a message to at least one location node to indicate that the server is responsible for data in the container.

3. The server of claim 1, wherein the server further comprises a cache, wherein the container contents forms a data block, and wherein encoding the container contents comprises:

determine a size of a coding matrix;

determine a size of a submatrix of the data block such that the sum of the size of the coding matrix and the size of the submatrix is smaller than the size of the cache;

request that the submatrix of the data block and the coding matrix be written to the cache from the memory, wherein the cache is configured to store the submatrix of the data block and the coding matrix; and

compute a portion of an encoded block by selecting and computing the exclusive or (XOR) of at least two rows of the submatrix of the data block, wherein the at least two rows are selected according to elements of the first submatrix of the coding matrix.

4. The server of claim 3, wherein encoding the container contents further comprises for each of a plurality of submatrices of the data block that are equal to or less than the submatrix in size, encoding the selected submatrix to generate the remainder of the encoded blocks.

5. The server of claim 1, wherein the encoding is Cauchy Reed-Solomon coding.

6. An apparatus comprising:

a memory configured to store a data block and a coding matrix for encoding the data block;

a cache; and

a processor coupled to the cache and the memory, wherein the processor is configured to;

determine a size of the coding matrix;

determine a size of a submatrix of the data block such that the sum of the size of the coding matrix and the size of the submatrix is smaller than the size of the cache;

request that the submatrix of the data block and the coding matrix be written to the cache from the memory, wherein the cache is configured to store the submatrix of the data block and the coding matrix; and

compute a portion of an encoded block by selecting at least two rows of the submatrix of the data block and performing binary operations on the at least two rows, wherein the at least two rows are selected according to elements of the first submatrix of the coding matrix.

7. The apparatus of claim 6, further comprising a first register and a second register coupled to the processor, wherein computing a portion of the encoded block comprises:

retrieving a first row of the submatrix of the data block from the first register;

retrieving a second row of the submatrix of the data block from the second register, wherein the first row and the second row are selected according to elements of the submatrix of the coding matrix;

computing an exclusive or operation of the first row and the second row to produce a result; and

storing the result in the first register.

8. The apparatus of claim 7, wherein the processor is further configured to:

retrieve a third row of the submatrix of the data block according to an element of the submatrix of the coding matrix;

compute an XOR of the result and the third row to generate a second result; and

write the second result to the first register.

9. The apparatus of claim 6 further comprising at least four registers coupled to the processor, wherein the at least two rows of the submatrix of the data block comprise at least four rows and are stored in the registers, and wherein the processor is further configured to perform an XOR of all the at least four rows using single instruction multiple data (SIMD) operations.

10. The apparatus of claim 6, wherein the processor is further configured to:

for each of a plurality of submatrices of the data block that are equal to or less than the submatrix in size, encode the selected submatrix to generate the remainder of the encoded block.

11. The apparatus of claim 6, wherein the binary operations on the at least two rows comprises an XOR of the at least two rows.

12. A server configured to form part of a data protection group, wherein the server comprises:

a transceiver configured to request a failed server'"'"'s list of containers from at least one location node; and

a processor coupled to the transceiver and configured to;

select a portion of the list of containers for recovery, wherein the transceiver is further configured to transmit a plurality of requests to a plurality of servers in the data protection group, and wherein the requests are collectively for all the coded blocks corresponding to a container in the portion of the list.

13. The server of claim 12, wherein the transceiver is further configured to receive the coded blocks corresponding to the container, and wherein the processor is further configured to decode the coded blocks to generate the data corresponding to the container.

14. The server of claim 13, wherein the transceiver is configured to transmit the data corresponding to the container to a second server that replaced the failed server in the data protection group.

15. The server of claim 12, wherein the processor is configured to coordinate with a plurality of servers in the data protection group to recover all the containers in the list.

16. A method comprising:

generating a graph comprising a starting node and a plurality of nodes, where each of the plurality of nodes corresponds to a different row of a coding matrix used to encode data in a container, wherein an edge from the starting node to each node in the plurality of nodes is a number of ones of the corresponding row of the coding matrix;

adding edges between all pairs of nodes in the plurality of nodes to the graph, wherein an edge from a first node to a second node in each pair of nodes in the plurality of nodes is the number of differences between the corresponding two rows of the coding matrix;

determining the minimum spanning tree from the graph; and

adjusting the coding matrix based on the minimum spanning tree.

17. The method of claim 16, wherein adjusting the coding matrix comprises rearranging the row order of the coding matrix according to cost based on the minimum spanning tree to generate a new coding matrix.

18. The method of claim 17, further comprising:

encode a data block to generate encoded content using the new coding matrix.

19. The method of claim 18, wherein using the new coding matrix to encode a data block comprises:

determining a size of a coding matrix for encoding a data block;

determining a size of a submatrix of the data block such that the sum of the size of the coding matrix and the size of the submatrix is smaller than the size of the cache;

requesting that the submatrix of the data block and the coding matrix be written to the cache from the memory, wherein the cache is configured to store the submatrix of the data block and the coding matrix; and

compute a portion of an encoded block by selecting at least two rows of the submatrix of the data block and performing binary operations on the at least two rows, wherein the at least two rows are selected according to elements of the first submatrix of the coding matrix.

20. The method of claim 16, further comprising generating the coding matrix for Cauchy Reed-Solomon encoding.