Fault tolerant distributed storage method and controller using (N,K) algorithms
First Claim
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.
7 Assignments
0 Petitions
Accused Products
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.
-
Citations
32 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; anddistributing the at least L data chunks to storage elements of the distributed storage system. - View Dependent Claims (2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
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; anddistributing 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. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22)
-
-
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. - View Dependent Claims (24, 25, 26, 27, 28, 29, 30, 31, 32)
-
Specification