CONVERTING A DATA CHUNK INTO A RING ALGEBRAIC STRUCTURE FOR FAST ERASURE CODING

• US 20180052737A1
• Filed: 08/17/2016
• Published: 02/22/2018
• Est. Priority Date: 08/17/2016
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Han, Zhenxing
• Granted Patent: US 10,191,809 B2
• Time in Patent Office: Days
• 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:

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.

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 tagging comprises appending an additional row of bits representing an additional SIMD vector to the first matrix.

5. The method of claim 4, further comprising:

maintaining an index pointer referencing a row of the first matrix, wherein the row corresponds to terms of a specific degree.

6. The method of claim 5, further comprising:

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:

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 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;

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.

12. The 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 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 system of claim 13, wherein tagging comprises appending an additional row of bits representing an additional SIMD vector to the first matrix.

15. The system of claim 14, further comprising:

maintaining an index pointer referencing a row of the first matrix, wherein the row corresponds to terms of a specific degree.

16. The system of claim 15, further comprising:

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 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 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 system of claim 18, further comprising:

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:

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.