Fault tolerant storage system and method

• US 20020116659A1
• Filed: 07/31/2001
• Published: 08/22/2002
• Est. Priority Date: 02/16/2001
• Status: Active Grant

• Current Assignee: Virtuozzo International GmbH
• Original Assignee: Swsoft Holdings, Ltd.
• Inventors: Tormasov, Alexander, Beloussov, Serguei, Protassov, Stanislav, Khassine, Mikhail
• Granted Patent: US 6,961,868 B2
• Time in Patent Office: Days
• US Class Current: 714/5
• CPC Class Codes: G06F 11/1662 the resynchronized component or unit being a persistent storage device re-synchronization of failed mirror storage G06F11/2082; rebuild or reconstruction of parity RAID storage G06F11/1008
• CPC Class Codes: G06F 16/182 Distributed file systems

Abstract

The disclosed invention stores files in a set of independent, functionally equal pieces. These pieces are placed on different servers of a distributed network to achieve a pre-determined level of fault tolerance. Terms of fault tolerance are defined in terms of amount of unavailable sites in the network allowing receipt and access to the data file. Maximal and minimal number of pieces available are variable method parameters. The minimal amount of data pieces k needed to restore a data file is defined. The size of each piece is approximately equal to 1/k of the original file size. The maximal amounts of pieces are defined during distribution operation and depend upon a requested fault tolerance level. Redundancy in data storage is minimized and varies dynamically by changing the total amount of pieces available. Significant increase in data transfer rate is possible because all file pieces could be transferred parallel and independently.

Claims

1. A method for data storage and retrieval from a network of servers, said method producing a distributed data storage system with a level of redundancy, said method comprising the steps of:

a. defining an amount of data pieces;

b. defining a minimal amount of data pieces k needed to restore a data file;

c. for a distributed arbitrarily-connected network of L servers, defining a number M of the servers that could be rendered inaccessible;

d. creating at least M+k data pieces for storage on at least M+k servers;

whereby the ability to restore the data file from M servers is retained and the optimal utilization of data storage means obtained.

2. The method as defined in claim 1 wherein said data pieces are numbered, interchangeable, and of equal size.

3. The method as defined in claim 1 wherein k≦

n.

4. The method as defined in claim 1 wherein M<

L.

5. The method as defined in claim 1 wherein the number of data pieces n depends on the fault tolerance level of and the number of servers in the network.

6. The method as defined in claim 1 wherein the amount of redundancy data stored for each file is incremented by steps of 1/k of the original file size and could be varied for each file.

7. A system for data storage and retrieval from a network of servers, said system providing data storage with a controllable level of redundancy, said system comprising for each file:

a predetermined amount of data pieces n;

a minimal amount of data pieces k needed to restore a data file;

a predetermined number M of servers in a network containing L servers, that could be rendered inaccessible;

at least M+k data pieces for storage on at least M+k servers;

wherein the ability to restore a data file from M servers is retained and the optimal utilization of data storage means is obtained.

8. The system as defined in claim 7 wherein said data pieces are numbered, interchangeable, and of equal size.

9. The system as defined in claim 7 wherein k≦

n.

10. The system as defined in claim 7 wherein M<

L.

11. The system as defined in claim 7 wherein the number of data pieces n depends upon the fault tolerance level and the number of servers in the network.

12. The system as defined in claim 7 wherein the amount of redundancy data stored for each file is incremented by steps of 1/k of the original file size and could be varied for each file.