Distributed storage system with efficient handling of file updates

• US 8,984,384 B1
• Filed: 06/30/2010
• Issued: 03/17/2015
• Est. Priority Date: 06/30/2010
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Juels, Ari, Bowers, Kevin D., Oprea, Alina
• Primary Examiner(s): NGUYEN, STEVE N
• Application Number:
  US12/827,097
• Time in Patent Office: 1,721 Days
• US Class Current: 714/800
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• 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]

Abstract

A client device or other processing device comprises a file encoding module, with the file encoding module being configured to separate a file into a plurality of sets of file blocks, to assign sets of the file blocks to respective ones of a plurality of servers, to define a plurality of parity groups each comprising a different subset of the plurality of servers, to assign, for each of the servers, each of its file blocks to at least one of the defined parity groups, and to compute one or more parity blocks for each of the parity groups. The file blocks are stored on their associated servers, and the parity blocks computed for each of the parity groups are stored on respective ones of the servers other than those within that parity group. Such an arrangement advantageously ensures that only a limited number of parity block recomputations are required in response to file block updates.

Claims

1. A method comprising:

separating a file into a plurality of sets of file blocks;

assigning sets of the file blocks to respective ones of a plurality of servers;

defining a plurality of parity groups each comprising a different subset of the plurality of servers;

for each of the servers, assigning each of its file blocks to at least one of the defined parity groups;

computing one or more parity blocks for each of the parity groups;

storing the file blocks on their associated servers;

storing the parity blocks such that said one or more parity blocks computed for each of the parity groups are stored on respective ones of the plurality of servers other than the servers within that parity group; and

in each of a plurality of epochs, performing a challenge phase, a remediation phase, a file update phase, and a proactivization phase;

wherein the challenge phase comprises issuing challenges to respective ones of the servers and processing responses to the challenges to determine corruption of the file blocks, the remediation phase comprises restoring file blocks determined to be corrupted during the challenge phase, the file update phase comprises making one or more updates to the file, and the proactivization phase comprises recomputing a fraction of parity blocks for the updated file, the fraction being based on a number of servers assumed to be corruptible by an adversary per epoch;

wherein the file blocks and one or more parity blocks associated with each parity group are stored in respective independently and randomly selected positions on respective ones of the plurality of servers; and

wherein the plurality of parity groups are defined such that respective structures of the parity groups are not predictable without access to a secret used in assigning the file blocks to the parity groups.

2. The method of claim 1 further comprising the steps of:

modifying contents of at least one of the file blocks; and

responsive to the modifying, substantially simultaneously updating the parity blocks previously computed for each parity group corresponding to said one or more modified file blocks.

3. The method of claim 1 wherein the parity groups are each defined as a sequence of k specified servers of the plurality of servers such that there are n different parity groups PG₁={S₁, . . . , S_k}, . . . , PG_n={S_n, S₁, . . . , S_k-1} where n denotes the number of servers in the plurality of servers and k<

n.

4. The method of claim 3 wherein the file comprises m=lk file blocks evenly separated into n sets of file blocks, wherein m is an input message, and l is a number of groups of message blocks.

5. The method of claim 3 wherein n-k parity blocks are computed for each of the parity groups.

6. The method of claim 3 wherein said one or more parity blocks are computed for each of the parity groups using a systematic (k, n) Reed-Solomon code.

7. The method of claim 1 further comprising the step of randomly permuting the parity blocks to be stored on each of the servers.

8. The method of claim 1 further comprising the step of repeating at least one additional round of said assigning, for each of the plurality of servers, each of its file blocks to at least one of the defined parity groups and said computing one or more parity blocks for each of the parity groups.

9. The method of claim 1 wherein the file blocks and one or more parity blocks associated with each parity group are stored on respective ones of the plurality of servers with one such block being stored on each server.

10. The method of claim 9 wherein each of the servers stores the same number of file blocks and parity blocks.

11. The method of claim 1 wherein an update to a given one of the file blocks requires a predetermined constant number of parity block recomputations, the predetermined constant number of parity block recomputations being less than a number of parity block computations required for the computing the one or more parity blocks for each of the parity groups.

12. A computer program product comprising a non-transitory processor-readable storage medium having encoded therein executable code of one or more software programs, wherein the one or more software programs when executed by a processor implement the steps of the method of claim 1.

13. The method of claim 1 wherein, for a given parity group, a first one of the file blocks or one or more parity blocks is stored in a first position on a first one of the servers and a second one of the file blocks or one or more parity blocks is stored in a second position on a second one of the servers, the first position being different than the second position.

14. An apparatus comprising:

a processing device including a processor, a memory coupled to the processor, and a network interface configured to support communication between the processing device and a plurality of servers;

wherein the processing device further comprises a file encoding module, the file encoding module being configured to separate a file into a plurality of sets of file blocks, to assign sets of the file blocks to respective ones of a plurality of servers, to define a plurality of parity groups each comprising a different subset of the plurality of servers, to assign, for each of the servers, each of its file blocks to at least one of the defined parity groups, to compute one or more parity blocks for each of the parity groups, to store the file blocks on their associated servers, to store the parity blocks such that said one or more parity blocks computed for each of the parity groups are stored on respective ones of the plurality of servers other than the servers within that parity group, and, in each of a plurality of epochs, to perform a challenge phase, a remediation phase, a file update phase, and a proactivization phase;

wherein the challenge phase comprises issuing challenges to respective ones of the servers and processing responses to the challenges to determine corruption of the file blocks, the remediation phase comprises restoring file blocks determined to be corrupted during the challenge phase, the file update phase comprises making one or more updates to the file, and the proactivization phase comprises recomputing a fraction of parity blocks for the updated file, the fraction being based on a number of servers assumed to be corruptible by an adversary per epoch;

wherein the file encoding module is configured to store the file blocks and the one or more parity blocks associated with each parity group in respective independently and randomly selected positions on respective ones of the plurality of servers; and

wherein the plurality of parity groups are defined such that respective structures of the parity groups are not predictable without access to a secret used in assigning the file blocks to the parity groups.

15. The apparatus of claim 14 wherein the file encoding module is further configured to modify contents of at least one of the file blocks, and responsive to the modifying, to substantially simultaneously update the parity blocks previously computed for each parity group corresponding to said one or more modified file blocks.

16. The processing device of claim 14 wherein said processing device comprises a client device.

17. The processing device of claim 14 wherein said processing device further comprises a file decoding module configured to reconstruct the file from blocks retrieved from the plurality of servers.

18. The processing device of claim 14 wherein said processing device further comprises a challenge-response module configured to issue challenges to respective ones of the servers, and to process responses to the challenges to determine if the number of stored file blocks containing faults exceeds a specified threshold.

19. The processing device of claim 14 wherein an update to a given one of the file blocks requires a predetermined constant number of parity block recomputations, the predetermined constant number of parity block recomputations being less than a number of parity block computations required to compute the one or more parity blocks for each of the parity groups.

20. A distributed storage system comprising:

a plurality of servers; and

at least one processing device configured to communicate with the plurality of servers;

wherein the processing device comprises a file encoding module configured to separate a file into a plurality of sets of file blocks, to assign sets of the file blocks to respective ones of a plurality of servers, to define a plurality of parity groups each comprising a different subset of the plurality of servers, to assign, for each of the servers, each of its file blocks to at least one of the defined parity groups, to compute one or more parity blocks for each of the parity groups, to store the file blocks on their associated servers, to store the parity blocks such that said one or more parity blocks computed for each of the parity groups are stored on respective ones of the plurality of servers other than the servers within that parity group, and, in each of a plurality of epochs, to perform a challenge phase, a remediation phase, a file update phase, and a proactivization phase;

wherein the challenge phase comprises issuing challenges to respective ones of the servers and processing responses to the challenges to determine corruption of the file blocks, the remediation phase comprises restoring file blocks determined to be corrupted during the challenge phase, the file update phase comprises making one or more updates to the file, and the proactivization phase comprises recomputing a fraction of parity blocks for the updated file, the fraction being based on a number of servers assumed to be corruptible by an adversary per epoch;

wherein the file encoding module is configured to store the file blocks and the one or more parity blocks associated with each parity group in respective independently and randomly selected positions on respective ones of the plurality of servers; and

wherein the plurality of parity groups are defined such that respective structures of the parity groups are not predictable without access to a secret used in assigning the file blocks to the parity groups.

21. The system of claim 20 wherein the processing device comprises a client device.

22. The system of claim 20 wherein the plurality of servers are part of a cloud storage system.

23. The system of claim 20 wherein an update to a given one of the file blocks requires a predetermined constant number of parity block recomputations, the predetermined constant number of parity block recomputations being less than a number of parity block computations required to compute the one or more parity blocks for each of the parity groups.