Distributed storage system data management and security

• US 10,608,784 B2
• Filed: 03/15/2017
• Issued: 03/31/2020
• Est. Priority Date: 03/15/2016
• Status: Active Grant

• Current Assignee: Cloud Storage Incorporated
• Original Assignee: Cline Hair Commercial Endeavors (CHCE), LLC
• Inventors: Yanovsky, David, Namoradze, Teimuraz, Miloslavskaya, Vera Dmitriyevna, Smirnov, Denys
• Primary Examiner(s): Knapp, Justin R
• Application Number:
  US15/460,119
• Publication Number:
  US 20170272100A1
• Time in Patent Office: 1,112 Days
• Field of Search: None
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/0848 Partitioned cache, e.g. separate instruction and operand caches
• CPC Class Codes: G06F 12/1408 by using cryptography for digital transmission H04L9/00
• CPC Class Codes: G06F 12/1466 Key-lock mechanism
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 21/00 Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 2212/1052 Security improvement
• CPC Class Codes: G06F 2212/282 Partitioned cache
• CPC Class Codes: G06F 2212/702 Conservative garbage collection
• CPC Class Codes: G06F 2221/2107 File encryption
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H03M 13/13 Linear codes
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/2921 wherein error correction coding involves a diagonal direction
• CPC Class Codes: H03M 13/616 Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations
• CPC Class Codes: H04L 1/0057 : Block codes H04L1/0061, H04L1/0064 take precedence
• CPC Class Codes: H04L 63/0428 : wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 67/1097 : for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 9/0863 : involving passwords or one-time passwords network architectures or network communication protocols for using one-time keys in a packet data network H04L63/067
• CPC Class Codes: H04L 9/0894 : Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage
• CPC Class Codes: H04L 9/3226 : using a predetermined code, e.g. password, passphrase or PIN network architectures or network communication protocols for supporting authentication of entities using passwords in a packet data network H04L63/083

Abstract

A system and method for distributing data over a plurality of remote storage nodes. Data are split into segments and each segment is encoded into a number of codeword chunks. None of the codeword chunks contains any of the segments. Each codeword chunk is packaged with at least one encoding parameter and identifier, and metadata are generated for at least one file and for related segments of the at least one file. The metadata contains information to reconstruct from the segments, and information for reconstructing from corresponding packages. Further, metadata are encoded into package(s), and correspond to a respective security level and a protection against storage node failure. A plurality of packages are assigned to remote storage nodes to optimize workload distribution. Each package is transmitted to at least one respective storage node as a function iteratively accessing and retrieving the packages of metadata and file data.

Claims

1. A method for erasure coding, comprising:

executing, by one or more processors configured to execute code stored in non-transitory processor readable media, encoding of data partitioned into K information chunks with an error correcting code C to produce N codeword chunks, wherein N is a composite natural number, K is a natural number lower than N and the error correcting code C is based on component codes;

h outer codes, wherein the i-th code generates b_in chunks as a function of k_i information chunks, where n is a natural number being a divisor of N, parameters h, b_i and k_i are natural numbers such that the code C has the highest possible minimum distance, and index i takes h different values; and

h inner codes, wherein the codes are nested and each code generates N/n chunks as a function of chunks produced by the outer codes;

distributing, by the one or more processors, the N codeword chunks over a set of storage nodes, wherein mapping of the N codeword chunks to the storage nodes is optimized to balance network load and to reduce predicted retrieval latency by computing;

i) availability coefficients for the storage nodes using statistical data, wherein each availability coefficient characterizes predicted average download speed for a respective storage node; and

ii) relevance coefficients for the codeword chunks;

reconstructing, by the one or more processors, the information chunks from the codeword chunks requested from the storage nodes;

repairing, by the one or more processors, failed storage nodes by reconstructing erased codeword chunks as a function of available codeword chunks belonging to the same set of the N codeword chunks; and

updating, by one or more processors, one or several information chunks, wherein the number of corresponding codeword chunks to be updated is minimized.

2. The method of claim 1, wherein encoding with the error-correcting code C of the K information chunks is implemented as multiplication of vectors having K elements of the different K information chunks by a K×

N generator matrix of the code C, wherein the generator matrix comprises a K×

K sparse matrix, such that its inverse matrix is also sparse.

3. The method of claim 2, wherein the K×

N generator matrix of the code C comprises a matrix obtained by column and row permutations from a K×

K block-diagonal matrix.

4. The method of claim 2, wherein the K×

N generator matrix of the code C comprises a K×

K block-diagonal matrix.

5. The method of claim 1, wherein any codeword of the code C comprises n groups of N/n elements, and further wherein any single erased codeword chunk within a group is repairable as a function of remaining N/n−

1 chunks from the same group.

6. The method of claim 1, further comprising reconstruction of erased codeword chunks by multi-stage decoding, wherein each decoding stage comprises decoding in one inner code and one outer code, and further where error correction capability of employed nested inner codes increases with the stage index, parameters of outer codes satisfy k_i/b_i≤

k_j/b_i for any stage i preceding to stage j, and stages are terminated upon recovering of all erasures within the codeword.

7. The method of claim 1, wherein the outer codes are maximum distance separable codes.

8. The method of claim 7, wherein the outer codes are Reed-Solomon codes.

9. The method of claim 1, wherein the inner codes are maximum distance separable codes.

10. The method of claim 1, wherein the inner codes are binary linear block codes with maximum possible minimum distances, and parameters b_i of the outer codes are the smallest possible natural numbers such that minimum distances of the inner codes strictly increase with the decoding stage index.

11. The method of claim 1, wherein updating of a single information chunk results in no more than N−

K+s updated codeword chunks, where s is a nature number equal to the smallest number of the codeword chunks required to reconstruct any information chunk and K is a natural number equal to the number of information chunks encoded into the N codeword chunks.

12. The method of claim 1, wherein retrieval of several chunks of the K information chunks, corresponding to the same s×

s submatrix of the K×

K block-diagonal matrix requires exactly s chunks of the N codeword chunks to be downloaded from the storage nodes.

13. A system for erasure coding, comprising:

one or more processors in communication with non-transitory processor readable media, wherein the non-transitory processor readable media store instructions that, when executed by the one or more processors, causes the one or more processors to;

execute encoding of data partitioned into K information chunks with an error-correcting code C to produce N codeword chunks, wherein N is a composite natural number, K is a natural number lower than N and the error correcting code C is based on component codes;

h outer codes, wherein the i-th code generates b_in chunks as a function of k_i information chunks, where n is a natural number being a divisor of N, parameters h, b_i and k_i are natural numbers such that the code C has the highest possible minimum distance, and index i takes h different values; and

h inner codes, wherein the codes are nested and each code generates N/n chunks as a function of chunks produced by the outer codes;

distribute the N codeword chunks over a set of storage nodes, wherein mapping of the N codeword chunks to the storage nodes is optimized to balance network load and to reduce predicted retrieval latency by computing;

i) availability coefficients for the storage nodes using statistical data, wherein each availability coefficient characterizes predicted average download speed for a respective storage node; and

ii) relevance coefficients for the codeword chunks;

reconstruct the information chunks from the codeword chunks requested from the storage nodes;

repair failed storage nodes by reconstructing erased codeword chunks as a function of available codeword chunks belonging to the same set of the N codeword chunks; and

update one or several information chunks, wherein the number of corresponding codeword chunks to be updated is minimized.

14. The system of claim 13, wherein encoding with the error-correcting code C of the K information chunks is implemented as multiplication of vectors having K elements of the different K information chunks by K×

N generator matrix of code C, wherein the generator matrix comprises a K×

K sparse matrix, such that its inverse matrix is also sparse.