Skewed orthogonal coding techniques

• US 8,615,698 B1
• Filed: 09/28/2011
• Issued: 12/24/2013
• Est. Priority Date: 09/28/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Cypher, Robert
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): KABIR, ENAMUL MD
• Application Number:
  US13/246,966
• Time in Patent Office: 818 Days
• Field of Search: None
• US Class Current: 714/758
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/2918 with error correction codes in three or more dimensions, e.g. 3-dimensional product code where the bits are arranged in a cube

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for skewed orthogonal coding techniques. In one aspect, a method includes receiving data chunks to be stored and generating intra-level code chunks and inter-level code chunks using the data chunks and partitions of numbers. Levels of codewords are stored. The partitions are selected so that, for at least a first set of chunks A, B, and A′ wherein A and B are in a same intra-level codeword and A and A′ are in a same inter-level codeword, there is no chunk B′ that is in both an intra-level codeword containing A′ and an inter-level codeword containing B.

Claims

1. A method performed by one or more computers, the method comprising:

receiving a plurality of data chunks to be stored using k partitions of x numbers, wherein k and x are each greater than one, and wherein each partition defines a plurality of groups of the x numbers;

generating a plurality of intra-level code chunks using the data chunks and a first error-correcting code, resulting in a plurality of intra-level codewords organized according to the groups of the partitions;

generating a plurality of inter-level code chunks using the data chunks and a second error-correcting code, resulting in x inter-level codewords organized according to the numbers of the partitions; and

storing each level of k levels of codewords, the k levels of codewords including the plurality of intra-level codewords and the plurality of inter-level codewords;

wherein the partitions are selected so that, for at least a first set of chunks A, B, and A′

wherein A and B are in a same intra-level codeword and A and A′

are in a same inter-level codeword, there is no chunk B′

that is in both an intra-level codeword containing A′ and

an inter-level codeword containing B.

2. The method of claim 1, wherein storing each level of k levels of codewords includes storing each level at a distinct group of storage nodes.

3. The method of claim 1, wherein generating the intra-level code chunks includes associating each data chunk with a group of the partitions, and wherein each intra-level codeword includes data chunks associated with a same group.

4. The method of claim 1, wherein generating the inter-level code chunks includes associating each data chunk with a number of the partitions, and wherein each inter-level codeword includes data chunks associated with a same number.

5. The method of claim 1, wherein the k partitions of x numbers are orthogonal so that, for any two numbers x1 and x2, x1 and x2 are in a same group in a first partition and not in a same group in any other partition.

6. The method of claim 1, wherein the k partitions of x numbers define the groups of numbers based on random or pseudo-random numbers.

7. The method of claim 1, wherein:

m of the levels include the inter-level code chunks, wherein m is greater than or equal to one; and

(k−

m) of the levels include the intra-level codewords, each intra-level codeword including d data chunks and n code chunks.

8. The method of claim 1, wherein storing each level of the k levels of codewords includes distributing the inter-level code chunks evenly across the k groups of storage nodes.

9. The method of claim 8, wherein distributing the inter-level code chunks evenly across the k groups of storage nodes includes allocating the inter-level code chunks to groups of storage nodes according to the numbers of one of the partitions.

10. The method of claim 1, wherein two orthogonal partitions are assigned to each level and each data chunk is included in two intra-level codewords organized according to the two partitions assigned to that level.

11. The method of claim 1, further comprising generating and storing local-remote code chunks for local-remote codewords that include the inter-level code chunks.

12. The method of claim 1, wherein the first and second error-correcting codes are linear Maximal Distance Separable (MDS) codes in systematic form.

13. A system of one or more computers configured to perform operations comprising:

receiving a plurality of data chunks to be stored using k partitions of x numbers, wherein k and x are each greater than one, and wherein each partition defines a plurality of groups of the x numbers;

generating a plurality of intra-level code chunks using the data chunks and a first error-correcting code, resulting in a plurality of intra-level codewords organized according to the groups of the partitions;

generating a plurality of inter-level code chunks using the data chunks and a second error-correcting code, resulting in x inter-level codewords organized according to the numbers of the partitions; and

storing each level of k levels of codewords, the k levels of codewords including the plurality of intra-level codewords and the plurality of inter-level codewords;

wherein the partitions are selected so that, for at least a first set of chunks A, B, and A′

wherein A and B are in a same intra-level codeword and A and A′

are in a same inter-level codeword, there is no chunk B′

that is in both an intra-level codeword containing A′ and

an inter-level codeword containing B.

14. The system of claim 13, wherein storing each level of k levels of codewords includes storing each level at a distinct group of storage nodes.

15. The system of claim 13, wherein generating the intra-level code chunks includes associating each data chunk with a group of the partitions, and wherein each intra-level codeword includes data chunks associated with a same group.

16. The system of claim 13, wherein generating the inter-level code chunks includes associating each data chunk with a number of the partitions, and wherein each inter-level codeword includes data chunks associated with a same number.

17. The system of claim 13, wherein the k partitions of x numbers are orthogonal so that, for any two numbers x1 and x2, x1 and x2 are in a same group in a first partition and not in a same group in any other partition.

18. The system of claim 13, wherein the k partitions of x numbers define the groups of numbers based on random or pseudo-random numbers.

19. The system of claim 13, wherein:

m of the levels include the inter-level code chunks, wherein m is greater than or equal to one; and

(k−

m) of the levels include the intra-level codewords, each intra-level codeword including d data chunks and n code chunks.

20. The system of claim 13, wherein storing each level of the k levels of codewords includes distributing the inter-level code chunks evenly across the k groups of storage nodes.

21. The system of claim 20, wherein distributing the inter-level code chunks evenly across the k groups of storage nodes includes allocating the inter-level code chunks to groups of storage nodes according to the numbers of one of the partitions.

22. The system of claim 13, wherein two orthogonal partitions are assigned to each level and each data chunk is included in two intra-level codewords organized according to the two partitions assigned to that level.

23. The system of claim 13, the operations further comprising generating and storing local-remote code chunks for local-remote codewords that include the inter-level code chunks.

24. The system of claim 13, wherein the first and second error-correcting codes are linear Maximal Distance Separable (MDS) codes in systematic form.

25. A non-transitory tangible computer storage medium encoded with a computer program, the program comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

receiving a plurality of data chunks to be stored using k partitions of x numbers, wherein k and x are each greater than one, and wherein each partition defines a plurality of groups of the x numbers;

generating a plurality of intra-level code chunks using the data chunks and a first error-correcting code, resulting in a plurality of intra-level codewords organized according to the groups of the partitions;

generating a plurality of inter-level code chunks using the data chunks and a second error-correcting code, resulting in x inter-level codewords organized according to the numbers of the partitions; and

storing each level of k levels of codewords, the k levels of codewords including the plurality of intra-level codewords and the plurality of inter-level codewords;

wherein the partitions are selected so that, for at least a first set of chunks A, B, and A′

wherein A and B are in a same intra-level codeword and A and A′

are in a same inter-level codeword, there is no chunk B′

that is in both an intra-level codeword containing A′ and

an inter-level codeword containing B.

26. The computer storage medium of claim 25, wherein storing each level of k levels of codewords includes storing each level at a distinct group of storage nodes.

27. The computer storage medium of claim 25, wherein generating the intra-level code chunks includes associating each data chunk with a group of the partitions, and wherein each intra-level codeword includes data chunks associated with a same group.

28. The computer storage medium of claim 25, wherein generating the inter-level code chunks includes associating each data chunk with a number of the partitions, and wherein each inter-level codeword includes data chunks associated with a same number.

29. The computer storage medium of claim 25, wherein the k partitions of x numbers are orthogonal so that, for any two numbers x1 and x2, x1 and x2 are in a same group in a first partition and not in a same group in any other partition.

30. The computer storage medium of claim 25, wherein the k partitions of x numbers define the groups of numbers based on random or pseudo-random numbers.

31. The computer storage medium of claim 25, wherein:

m of the levels include the inter-level code chunks, wherein m is greater than or equal to one; and

(k−

m) of the levels include the intra-level codewords, each intra-level codeword including d data chunks and n code chunks.

32. The computer storage medium of claim 25, wherein storing each level of the k levels of codewords includes distributing the inter-level code chunks evenly across the k groups of storage nodes.

33. The computer storage medium of claim 32, wherein distributing the inter-level code chunks evenly across the k groups of storage nodes includes allocating the inter-level code chunks to groups of storage nodes according to the numbers of one of the partitions.

34. The computer storage medium of claim 25, wherein two orthogonal partitions are assigned to each level and each data chunk is included in two intra-level codewords organized according to the two partitions assigned to that level.

35. The computer storage medium of claim 25, the operations further comprising generating and storing local-remote code chunks for local-remote codewords that include the inter-level code chunks.

36. The computer storage medium of claim 25, wherein the first and second error-correcting codes are linear Maximal Distance Separable (MDS) codes in systematic form.