Fault tolerant distributed storage method and controller using (N,K) algorithms

• US 7,418,620 B1
• Filed: 12/06/2004
• Issued: 08/26/2008
• Est. Priority Date: 02/16/2001
• Status: Expired due to Term

• Current Assignee: Virtuozzo International GmbH
• Original Assignee: Swsoft Holdings, Ltd.
• Inventors: Protassov, Stanislav S., Beloussov, Serguei M., Tormasov, Alexander G.
• Primary Examiner(s): DUNCAN, MARC M
• Application Number:
  US11/004,078
• Time in Patent Office: 1,359 Days
• Field of Search: 714/6, 714/770
• US Class Current: 714/6.24
• 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

Data sets and blocks are stored in a set of independent, functionally equivalent chunks. These chunks are placed on different elements of a distributed network to achieve pre-defined 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 block. Maximal and minimal number of chunks available are variable method parameters. The minimal amount of data chunks K needed to restore a data block is defined. The size of each chunk is approximately 1/K of the original block size. The maximal amounts of chunks 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 chunks available. Significant increase in data transfer rate is possible because all block chunks could be transferred in parallel and independently.

Claims

1. A method for data storage in a distributed data storage system with redundancy, the method comprising:

dividing a data set into a plurality of data blocks using an (N,K) algorithm;

defining a minimal number K out of N data chunks needed to restore one data block;

disassembling each of the data blocks into at least L different data chunks, wherein K≦

L≦

N; and

distributing the at least L data chunks to storage elements of the distributed storage system.

2. The method of claim 1, further comprising defining a size of data block and adding filler to any data block that is less than the defined size.

3. The method of claim 1, further comprising defining a size of data block and adding filler to the data set so that the data set is represented by an integral number of data blocks.

5. The method of claim 1, wherein a size of each data chunk is defined based on a size of Message Transfer Units in a TCP transmission protocol.

6. The method of claim 1, wherein L≧

M+K, M being a number of simultaneously failed storage elements.

7. The method of claim 6, wherein the data chunks corresponding to one data block are distributed to at least M+K different storage elements.

8. The method of claim 1, wherein all the data chunks are written to the storage elements placed on a single storage medium.

9. The method of claim 8, wherein the single storage medium is one of a hard disk drive or a CD or a DVD or a magneto-optical disk or magnetic tape or magnetic stripe.

10. The method of claim 8, wherein the storage elements are allocated throughout the storage medium so as maximize distribution of data related to different chunks of a single data block.

11. The method of claim 10, wherein the storage elements are allocated separately by distance.

12. The method of claim 11, further comprising:

defining geometrical areas of the data storage medium for placing storage elements corresponding to different chunks of one block; and

writing the chunks to storage elements located within the geometrical areas.

13. The method of claim 12, wherein the geometrical areas are any of:

a set of parts of sectors, a set of circular areas of a disk, a set of sections of tape, and a set of sections of a magnetic stripe.

4. A method for data storage in a distributed data storage system with redundancy, the method comprising:

dividing a data set into a plurality of data blocks;

defining a minimal number K out of N data chunks needed to restore one data block;

disassembling each of the data blocks into at least L different data chunks wherein K<

L<

N; and

distributing the at least L data chunks to storage elements of the distributed storage system,

wherein each data chunk includes a unique identifier.

14. A method for retrieving data in a distributed data storage system comprising:

receiving, from a distributed storage system, any K data chunks out of L data chunks for each data block, wherein K≦

L, and wherein the data was divided into N data chunks generated using an (N,K) algorithm, each chunk including a unique identifier;

composing the received data chunks into corresponding data blocks; and

assembling the data blocks into a data set.

15. The method of claim 14, further comprising removing added data from the data set, the added data resulting from chunk generation.

16. The method of claim 14, wherein data chunks corresponding to the same data block were distributed to a plurality of storage elements of the distributed storage system.

17. The method of claim 16, wherein the plurality of storage elements belongs to a single storage medium.

18. The method of claim 17, further comprising using any of an optical disk, magneto-optical disk, a single sided hard disk drive, a double-sided hard disk drive, a multi-surfaced hard disk drive, a credit card, and an airline ticket with a magnetic strip as the data storage medium.

19. The method of claim 16, wherein the storage elements are physical storage blocks.

20. The method of claim 16, further comprising using a magnetic storage device as the data storage medium.

21. The method of claim 20, further comprising using a magnetic stripe of a magnetic stripe card as the magnetic storage device.

22. The method of claim 20, further comprising using a disk surface of HDD as the magnetic storage device.

23. A system for managing distributed storage comprising:

decomposition logic that disassembles each data block into L different data chunks, such that K data chunks out of N data chunks are sufficient to restore the original data blocks, wherein L≦

N and K<

N−

2;

an interface for distributing data to storage elements;

composition logic for assembling K data chunks received for each data block into corresponding data blocks; and

control logic to control operations of the decomposition logic and the composition logic.

24. The system of claim 23, further comprising:

a data set disassembler that divides the data set into data blocks; and

a data set assembler that combines the data blocks into the data set,

wherein the control logic controls operations of the data set disassembler and the data set assembler.

25. The system of claim 23, wherein the interface is a SCSI interface.

26. The system of claim 23, wherein the interface is coupled to a computer network.

27. The system of claim 23, wherein the storage elements include network drives.

28. The system of claim 23, wherein the storage elements include servers.

29. The system of claim 23, wherein the storage elements include a Storage Area Network.

30. The system of claim 23, wherein any of N, L, and K vary for different data blocks.

31. The system of claim 23, wherein the number L depends on any of a desired fault tolerance level, a network bandwidth, available system resources and workload.

32. The system of claim 23, wherein a size of each data chunk is defined based on a size of Message Transfer Units.