Converting a data chunk into a ring algebraic structure for fast erasure coding

• US 10,191,809 B2
• Filed: 08/17/2016
• Issued: 01/29/2019
• Est. Priority Date: 08/17/2016
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Han, Zhenxing
• Primary Examiner(s): Alphonse, Fritz
• Application Number:
  US15/239,630
• Publication Number:
  US 20180052737A1
• Time in Patent Office: 895 Days
• Field of Search: 714774, 714776
• 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/1096 Parity calculation or recalculation after configuration or reconfiguration of the system
• CPC Class Codes: G06F 11/1446 Point-in-time backing up or restoration of persistent data
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 9/30029 Logical and Boolean instructions, e.g. XOR, NOT
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes

Abstract

One embodiment provides a method comprising arranging a first data chunk into a ring structure, tagging the first data chunk by appending extra data to the first data chunk, and performing erasure coding on the first data chunk utilizing only exclusive or (XOR) operations.

Claims

1. A method comprising:

at a storage manager of a storage system;

arranging a first data chunk into a ring structure;

tagging the first data chunk by appending extra data to the ring structure;

performing erasure coding on the first data chunk utilizing only exclusive or (XOR) operations and the ring structure, wherein erasure coded encoded data resulting from the erasure coding is written to a persistent storage device; and

maintaining an index pointer that references a portion of the ring structure;

wherein the ring structure allows for multiplication of data included in the first data chunk to be implemented by rotation of the data utilizing the index pointer, thereby increasing efficiency of the storage system as the multiplication is simplified to an adjustment of the index pointer.

2. The method of claim 1, wherein:

the ring structure is a ring algebraic structure comprising binary polynomials;

the highest degree of any term in the ring algebraic structure is p−

2, wherein p is a prime number;

the ring algebraic structure supports addition of polynomials, and the addition of polynomials is implemented via an XOR operation; and

the ring algebraic structure supports multiplication of polynomials, and a product resulting from the multiplication of polynomials is taken modulo over a polynomial expression.

3. The method of claim 2, wherein:

a logical data arrangement for the first data chunk comprises a first matrix of bits;

each column of the first matrix corresponds to a polynomial; and

each row of the first matrix represents a single instruction, multiple data (SIMD) vector that corresponds to terms of the same degree in the polynomials.

4. The method of claim 3, wherein the tagging comprises appending an additional row of bits representing an additional SIMD vector to the first matrix.

5. The method of claim 4, wherein the index pointer references a row of the first matrix, and the row corresponds to terms of a specific degree.

6. The method of claim 5, further comprising:

at the storage manager of the storage system;

multiplying data included in the data chunk by adjusting the index pointer to reference another row of the first matrix, wherein the total number of rows the index pointer is offset by is indicative of an amount by which the data is multiplied by.

7. The method of claim 4, wherein the performing erasure coding comprises performing an addition of the first data chunk and a second data chunk.

8. The method of claim 7, wherein:

a logical data arrangement for the second data chunk comprises a second matrix of bits; and

the performing an addition comprises;

aligning each row of the first matrix with a row of the second matrix that corresponds to terms of the same degree; and

for each pair of aligned rows, performing an XOR operation of the aligned rows.

9. The method of claim 8, further comprising:

at the storage manager of the storage system;

writing a third data chunk to a persistent storage device, wherein the third data chunk comprises erasure coded encoded data resulting from the addition of the first data chunk and the second data chunk.

10. The method of claim 9, wherein:

a logical data arrangement for the third data chunk comprises a third matrix of bits; and

a row of the third matrix that corresponds to terms having a degree greater than p−

2 is zeroed out and discarded.

11. A storage system comprising:

at least one processor; and

a non-transitory processor-readable memory device storing instructions that when executed by the at least one processor causes the at least one processor to perform operations including;

at a storage manager of the storage system;

arranging a first data chunk into a ring structure;

tagging the first data chunk by appending extra data to the ring structure;

performing erasure coding on the first data chunk utilizing only exclusive or (XOR) operations and the ring structure, wherein erasure coded encoded data resulting from the erasure coding is written to a persistent storage device; and

maintaining an index pointer that references a portion of the ring structure;

wherein the ring structure allows for multiplication of data included in the first data chunk to be implemented by rotation of the data utilizing the index pointer, thereby increasing efficiency of the storage system as the multiplication is simplified to an adjustment of the index pointer.

12. The storage system of claim 11, wherein:

the ring structure is a ring algebraic structure comprising binary polynomials;

the highest degree of any term in the ring algebraic structure is p−

2, wherein p is a prime number;

the ring algebraic structure supports addition of polynomials, and the addition of polynomials is implemented via an XOR operation; and

the ring algebraic structure supports multiplication of polynomials, and a product resulting from the multiplication of polynomials is taken modulo over a polynomial expression.

13. The storage system of claim 12, wherein:

a logical data arrangement for the first data chunk comprises a first matrix of bits;

each column of the first matrix corresponds to a polynomial; and

each row of the first matrix represents a single instruction, multiple data (SIMD) vector that corresponds to terms of the same degree in the polynomials.

14. The storage system of claim 13, wherein the tagging comprises appending an additional row of bits representing an additional SIMD vector to the first matrix.

15. The storage system of claim 14, wherein the index pointer references a row of the first matrix, and the row corresponds to terms of a specific degree.

16. The storage system of claim 15, wherein the operations further comprise:

at the storage manager of the storage system;

multiplying data included in the data chunk by adjusting the index pointer to reference another row of the first matrix, wherein the total number of rows the index pointer is offset by is indicative of an amount by which the data is multiplied by.

17. The storage system of claim 14, wherein the performing erasure coding comprises performing an addition of the first data chunk and a second data chunk.

18. The storage system of claim 17, wherein:

a logical data arrangement for the second data chunk comprises a second matrix of bits; and

the performing an addition comprises;

aligning each row of the first matrix with a row of the second matrix that corresponds to terms of the same degree; and

for each pair of aligned rows, performing an XOR operation of the aligned rows.

19. The storage system of claim 18, wherein the operations further comprise:

at the storage manager of the storage system;

writing a third data chunk to a persistent storage device, wherein the third data chunk comprises erasure coded encoded data resulting from the addition of the first data chunk and the second data chunk.

20. A computer program product comprising a computer-readable hardware storage medium having program code embodied therewith, the program code being executable by a computer to implement a method comprising:

at a storage manager of a storage system;

arranging a first data chunk into a ring structure;

tagging the first data chunk by appending extra data to the first data chunk ring structure; and

performing erasure coding on the first data chunk utilizing only exclusive or (XOR) operations and the ring structure, wherein erasure coded encoded data resulting from the erasure coding is written to a persistent storage device; and

maintaining an index pointer that references a portion of the ring structure;

wherein the ring structure allows for multiplication of data included in the first data chunk to be implemented by rotation of the data utilizing the index pointer, thereby increasing efficiency of the storage system as the multiplication is simplified to an adjustment of the index pointer.