Method and system for storing a file on a plurality of servers

Patent metadata

Field	Value
Publication number	US-10055427-B2
Application number	US-201314419700-A
Country	US
Kind code	B2
Filing date	Oct 18, 2013
Priority date	Oct 19, 2012
Publication date	Aug 21, 2018
Grant date	Aug 21, 2018

Abstract

Methods and systems for storing a file on a plurality of servers are provided. The number of servers is n and the maximum number of servers which may fail is t. A predefined number b of byzantine failures and a number t−b of crashes of the servers is contemplated, where n equals 2t+b+1. The file is divided into a plurality of chunks, where the number of chunks is equal to or greater than the number of servers. The chunks of the file are sent to the n servers, where at least one chunk is sent to each server. The number of replies r from the n servers indicating successful storage of the respective chunks are determined. The number of replies r matching a terminating condition is checked. A new file based is generated. The process is repeated for the new file.

First claim

The invention claimed is:

1. A method for storing a first file (Δ 1 ) on a plurality of servers (S 1 , S 2 , . . . , S n ), wherein the number of servers (S 1 , S 2 , . . . , S n ) is n and the maximum number of servers (S 1 , S 2 , . . . , S n ) which may fail is t, including a predefined number b of byzantine failures and a number t−b of crashes of the servers (S 1 , S 2 , . . . , S n ), and wherein n equals 2t+b+1,
the method comprising:
a) Dividing the first file (Δ 1 ) into a plurality of chunks (C 1 , C 2 , . . . , C n ), wherein the number of chunks (δ 1 ) is equal to or greater than the number of servers n,
b) Sending n chunks of the first file (Δ 1 ) to the n servers (S 1 , S 2 , . . . , S n ), wherein one chunk is sent to each server (S 1 , S 2 , . . . , S n ),
c) Determining a number of replies r from the n servers (S 1 , S 2 , . . . , S n ) indicating successful storage of the respective chunks,
d) Checking if the number of replies r matches a terminating condition (TC),
e) Generating, when the number of replies r does not match the terminating condition, a new file (Δ 2 ) based on one or more chunks of the first file (Δ 1 ), a reconstruction threshold (m 1 ) of the first file (Δ 1 ) and the number of replies r, and
f) Performing steps a)-e) with the new file (Δ 2 ), until the terminating condition in step d) is fulfilled,

wherein the terminating condition (TC) is based on the difference between the reconstruction thresholds of the new file (Δ 1 , Δ 2 , . . . , Δ k ) of step e) and the first file of step a) and the maximum number of servers t which may fail.

2. The method according to claim 1 , wherein in step a) when the number of generated chunks (C 1 , C 2 , . . . , C n ) is greater than the number of servers n, generating additional chunks, wherein the number of additional chunks is dependent on the number of servers (t) which may fail and a reconstruction threshold (m 1 , m 2 , . . . ) for the file (Δ 1 ).

3. The method according to claim 1 , wherein for the reconstruction threshold (m) is based on an estimated number of responsive servers (S 1 , S 2 , . . . , S n ).

4. The method according to claim 3 , wherein the estimated number is greater than a sum of byzantine servers b and servers t−b that may fail.

5. The method according to claim 2 , wherein the total number of chunks in step a) is
2 t+th,
wherein t is the maximum number of servers that may fail and th is the reconstruction threshold for the file.

6. The method according to claim 1 , wherein the one or more chunks for generation of the new file (Δ 2 ) are solely-based on one or more of a prior non-sent remaining chunks.

7. The method according to claim 1 , wherein the one or more chunks for generation of the new file (Δ 2 ) are only generated when the termination condition (TC) is not matched.

8. The method according to claim 1 , wherein the generation of the new file (Δ 2 ) is performed by concatenating one or more chunks for generation of the new file.

9. The method according to claim 1 , wherein a timeout threshold is used when determining the number of replies according to step c), wherein the timeout threshold starts after a predetermined number of received replies, and the predetermined number of replies is the number of replies needed for reconstruction of the file.

10. The method according to claim 9 , wherein the timeout threshold is dynamically adapted in each round of steps a)-e), wherein the adaption is based on at least one of connection conditions between a writer of the file and the servers (S 1 , S 2 , . . . , S n ) and server conditions.

11. The method according to claim 10 , wherein adaption information is encoded in the replies from the servers (S 1 , S 2 , . . . , S n ).

12. The method according to claim 1 , wherein the termination condition (TC) is fulfilled when one of the reconstruction threshold (m 2 , m 3 ) for a file (F, Δ 1 ) of an actual round with regard to rounds of steps a)-e) is greater than or equal to the reconstruction threshold (m 1 , m 2 , . . . ) of the prior round and the number of rounds has exceeded the number of servers (t) that might be fail.

13. The method according to claim 1 , wherein the new file (Δ 2 ) is generated based on the one or more chunks (C 1 ) of a prior non-sent remaining chunks.

14. A system for storing a first file (Δ 1 ) on a plurality of servers (S 1 , S 2 , . . . , S n ), wherein the number of servers (S 1 , S 2 , . . . , S n ) is n and the maximum number of servers (S 1 , S 2 , . . . , S n ) which may fail is t, preferably including a predefined number b of byzantine failures and a number t−b of crashes of the servers (S 1 , S 2 , . . . , S n ), and wherein n equals 2t+b+1, the system comprising one or more processors which, alone or in combination, are configured to provide for execution of the following steps:
dividing the first file (Δ 1 ) into a plurality of chunks (C 1 , C 2 , . . . , C n ), wherein the number of chunks (δ 1 ) is equal to or greater than the number of servers n,
sending n chunks of the first file (Δ 1 ) to the n servers (S 1 , S 2 , . . . , S n ), wherein one chunk (C 1 , C 2 ) is sent to each server (S 1 , S 2 , . . . , S n ),
determining a number of replies r from the n servers (S 1 , S 2 , . . . , S n ) indicating successful storage of the respective chunks (C 1 , C 2 ),
checking whether the number of replies r matches a terminating condition (TC),
generating a new file (Δ 2 , Δ 3 ) based on one or more chunks (C 1 , C 2 ) of the first file (Δ 1 ), a reconstruction threshold (m 1 , m 2 , . . . ) of the first file and the number of replies r, and
operating recursively the dividing, the sending, the determining, the checking and the generating steps with a new file (Δ 2 ), until the terminating condition is fulfilled,
wherein the terminating condition (TC) is based on the difference between the reconstruction thresholds of the new file (Δ 2 , . . . , Δ k ) and the first file and the maximum number of servers t which may fail.

Assignees

• Nec Europe Ltd
• Nec Corp

Inventors

• Dobre Dan
• Karame Ghassan

Classifications

• G06F16/183 Primary

  Provision of network file services by network file servers, e.g. by using NFS, CIFS (network file access protocols H04L67/1097) · CPC title

• G06F11/1096 Primary

  Parity calculation or recalculation after configuration or reconfiguration of the system · CPC title

• G06F17/30203 Primary

  Physics · mapped topic