Encoding and storage node repairing method for minimum storage regenerating codes for distributed storage systems

Abstract

The present disclosure is based on erasure coding, information dispersal, secret sharing and ramp schemes to assure reliability and security. More precisely, the present disclosure combines ramp threshold secret sharing and systematic erasure coding.

1 . A method for distributing data of a plurality of files over a plurality of respective remote storage nodes, the method comprising:
 a. splitting into segments, by at least one processor configured to execute code stored in non-transitory processor readable media, the data of the plurality of files;   b. preprocessing each segment and then splitting it into v of input chunks: t highly sensitive chunks and v−t frequently demanded chunks, where highly sensitive chunks contain data which ought to be stored securely and highly demanded chunks contain data which ought to be stored in highly-available manner;   c. encoding, by the at least one processor, v input chunks (produced from the same segment) together with k−v supplementary input chunks into n of output chunks, where any of n output chunks do not contain copy of any fragment of highly sensitive chunks, while v−t output chunks are given by copies of v−t frequently demanded input chunks (these output chunks are further referred as frequently demanded output chunks), n≥k;   d. assigning, by the at least one processor, output chunks to remote storage nodes, wherein n output chunks produced from the same segment are assigned to n different storage nodes   e. transmitting, by the at least one processor, each of the output chunks to at least one respective storage node; and   f. retrieving, by the at least one processor, at least a part of at least one of the plurality of files by downloading parts of output chunks from storage nodes, where amount of data transferred from each storage node is optimized to minimize average latency for data reconstruction.   
     
     
         2 . The method of  claim 1 , wherein the step of data splitting provides data within a respective segment that comprises a part of one individual file or several different files. 
     
     
         3 . The method of  claim 1 , wherein the step of segment preprocessing comprises one or several of the following transformations: deduplication, compression, encryption and fragmentation. 
     
     
         4 . The method of  claim 3 , wherein the step of segment preprocessing includes encryption, wherein one or several parts of a segment are encrypted in individual manner or a segment is encrypted entirely. 
     
     
         5 . The method of  claim 3 , wherein the step of segment preprocessing includes fragmentation consisting of data partitioning and encoding, wherein fragmentation encoding is a function of one or several of the following: random (pseudo-random) values, values derived from original data (e.g. derived using deterministic cryptographic hash) and predetermined values. 
     
     
         6 . The method of  claim 1 , wherein the step of encoding employs supplementary inputs given by random data, values derived from original data (e.g. derived using deterministic hash) or predetermined values. 
     
     
         7 . The method of  claim 1 , wherein the step of encoding comprises applying erasure coding to k input chunks to produce n output chunks, where erasure coding is performed using a linear block error correction code in such a way that t highly sensitive input chunks may be reconstructed only as a function of at least k output chunks (any k output chunks are suitable), while (v−t) frequently demanded input chunks may be reconstructed as a copy of a related output chunks, as well as a function of any other k input chunks. 
     
     
         8 . The method of  claim 7 , wherein method for erasure coding utilizes a maximum distance separable (MDS) error-correction code and encoding is performed using k×n generator matrix G comprising (k−p) columns of k×k identity matrix, where 0≤t≤p≤k and v−t≤k−p, while other columns form k×(n+p−k) matrix such that any its square submatrix is nonsingular. 
     
     
         9 . The method of  claim 15 , wherein a k×n MDS code generator matrix G is obtained as follows
 a. Selecting an arbitrary MDS code of length (n+p) and dimension k; 
 b. Constructing a k×(n+p) generator matrix in systematic form (i.e. generator matrix, which includes k×k identity matrix as its submatrix); 
 c. Excluding p columns of k×k identity matrix from k×(n+p) generator matrix in systematic form to obtain k×n matrix G. 
 
     
     
         10 . The method of  claim 15 , wherein t=v, that is output chunks do not contain any copy of a fragment of input chunks produced from a segment and any fragment of a these input chunks may be reconstructed only as a function of at least k output chunks. 
     
     
         11 . The method of  claim 15 , wherein employed MDS error-correction code is a Reed-Solomon code. 
     
     
         12 . The method of  claim 15 , wherein for encoding with Reed-Solomon code employed generator matrix is based on Vandermonde matrix. 
     
     
         13 . The method of  claim 15 , wherein for encoding with Reed-Solomon code employed generator matrix is based on Cauchy matrix concatenated with identity matrix. 
     
     
         14 . The method of  claim 1 , wherein the step of assigning of output chunks to storage nodes comprises selection of trusted storage nodes (e.g. in private storage) and mapping frequently demanded output chunks to these trusted storage nodes. 
     
     
         15 . The method of  claim 1 , wherein the step of assigning of output chunks to storage nodes comprises selection of highly available storage nodes, mapping frequently demanded output chunks to these storage nodes and encrypting frequently demanded output chunks in individual manner prior to transmission, where highly available storage nodes demonstrate high average data transferring speed and low latency. 
     
     
         16 . The method of  claim 1 , wherein the step of data (at least a part of at least one of the plurality of files) retrieving comprises
 a. identifying range of indices within each information chunk corresponding to requested data;   b. downloading, by the at least one processor, such parts of output chunks from storage nodes that
 i. total size these parts is equal to the size of the widest range multiplied by k and 
 ii. the number of parts with the same range of indices within output chunks is equal to k; 
   c. reconstructing, by the at least one processor, requested data by performing the following steps:   for each set S of k source storage nodes
 i. combing parts with the same range of indices into a vector cs, and 
 ii. multiplying vector cs by inverse matrix to matrix G (S) , where G (S)  is a matrix consisting of k columns of selectively mixing matrix G with indices from the set S. 
   
     
     
         17 . The method of  claim 1 , wherein requested data is contained only in frequently demanded input chunks. In this case, requested data may be retrieved by downloading only corresponding frequently demanded output chunks. Thus, traffic reduction is achieved compared to general case of data retrieval (described in  claim 16 ). 
     
     
         18 . A method for distributing data of a plurality of files over a plurality of respective remote storage nodes, the method comprising:
 a. splitting data into segments, by at least one processor configured to execute code stored in non-transitory processor readable media, the data of the plurality of files;   b. optionally applying deduplication, compression and/or encryption to each segment;   c. splitting each segment into k information multi-chunks and optionally applying data mixing to these information chunks to produce k systematic multi-chunks;   d. encoding, by the at least one processor, k systematic multi-chunks (produced from the same segment) into r parity multi-chunks, wherein employed erasure coding scheme maximizes storage efficiency, enables reconstruction of the k systematic multi-chunks from any k output multi-chunks and enables recovering of a single output multi-chunk with minimized network traffic, where the set of k+r output multi-chunks comprises k systematic multi-chunks and r parity multi-chunks;   e. assigning, by the at least one processor, k+r output multi-chunks to remote storage nodes, wherein k+r output multi-chunks produced from the same segment are assigned to k+r different storage nodes;   f. transmitting, by the at least one processor, each of the output multi-chunks to at least one respective storage node;   g. storage node repairing, by the at least one processor, wherein at least one output multi-chunk is recovered as a function of parts of other output multi-chunks produced from the same segment, wherein network traffic is minimized; and   h. retrieving, by the at least one processor, at least a part of at least one of the plurality of files as a function of parts of output multi-chunks.   
     
     
         19 . A system for distributing data of a plurality of files over a plurality of respective remote storage nodes, the system comprising:
 at least one processor configured by executing instructions from non-transitory processor readable media, the at least processor configured for:
 a. splitting data into segments, by at least one processor configured to execute code stored in non-transitory processor readable media, the data of the plurality of files; 
 b. optionally applying deduplication, compression and/or encryption to each segment; 
 c. splitting each segment into k information multi-chunks and optionally applying data mixing to these information chunks to produce k systematic multi-chunks; 
 d. encoding k systematic multi-chunks (produced from the same segment) into r parity multi-chunks, wherein employed erasure coding scheme maximizes storage efficiency, enables reconstruction of the k systematic multi-chunks from any k output multi-chunks and enables recovering of a single output multi-chunk with minimized network traffic, where the set of k+r output multi-chunks comprises k systematic multi-chunks and r parity multi-chunks; 
 e. assigning k+r output multi-chunks to remote storage nodes, wherein k+r output multi-chunks produced from the same segment are assigned to k+r different storage nodes; 
 f. transmitting each of the output multi-chunks to at least one respective storage node; 
 g. storage node repairing wherein at least one output multi-chunk is recovered as a function of parts of other output multi-chunks produced from the same segment, wherein network traffic is minimized; and 
 h. retrieving at least a part of at least one of the plurality of files as a function of parts of output multi-chunks.