Incremental erasure coding for storage systems

• US 10,248,326 B2
• Filed: 01/05/2017
• Issued: 04/02/2019
• Est. Priority Date: 06/29/2016
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Danilov, Mikhail, Buinov, Konstantin, Fomin, Andrey, Kurilov, Andrey, Trusov, Maxim
• Primary Examiner(s): Padmanabhan, Mano
• Assistant Examiner(s): Edouard, Jean C
• Application Number:
  US15/398,819
• Publication Number:
  US 20180004414A1
• Time in Patent Office: 817 Days
• Field of Search: 711105
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays

Abstract

A method comprising: generating a storage chunk having a plurality of data fragments, the storage chunk stored in one or more storage devices; allocating space in a primary memory to store a plurality of coded fragments; receiving a plurality of I/O requests to write data; allocating space in the primary memory to store a next unfilled data fragment; processing a plurality of I/O requests to write data; and copying the coded fragments from the primary memory to the one or more storage devices. For each I/O request, writing the data to the next unfilled data fragment in the one or more storage devices, writing the data to the next unfilled data fragment in the primary memory, and if the data fragment in the primary memory is full, updating the coded fragments in the primary memory using the filled data fragment in the primary memory.

Claims

1. A method comprising:

generating a storage chunk having a plurality of data fragments, the storage chunk stored in one or more storage devices;

allocating space in a primary memory to store a plurality of coded fragments;

receiving a plurality of I/O requests to write data;

allocating space in the primary memory to store a next unfilled data fragment;

processing a plurality of I/O requests to write data, including for each I/O request;

writing the data to the next unfilled data fragment in the one or more storage devices;

writing the data to the next unfilled data fragment in the primary memory; and

if the data fragment in the primary memory is full, updating the coded fragments in the primary memory using the filled data fragment in the primary memory, removing the filled data fragment from the primary memory and allocating space in the primary memory to store a next unfilled data fragment; and

copying the coded fragments from the primary memory to the one or more storage devices.

2. The method of claim 1 wherein updating the coded fragments in primary memory using the full data fragment in primary memory comprises calculating C_i=C_i+X_i,j*D_full for each coding fragment C_i, where X is a matrix of coding coefficients and D_full is the full data fragment.

3. The method of claim 1 wherein the plurality of data fragments include k data fragments, the plurality of coded fragments include m coded fragments, the method further comprising in an event of a loss of m data fragments within the chunk, accessing a number of k unique data fragments or coded fragments and using information from the k unique data fragments or the coded fragments to decode the m data fragments within the chunk.

4. The method of claim 1 wherein the primary memory includes dynamic random-access memory (DRAM).

5. The method of claim 1 wherein the storage devices comprise disk drives.

6. A system comprising:

one or more processors;

a volatile memory; and

a non-volatile memory storing computer program code that when executed on the processor causes execution across the one or more processors of a process operable to perform the operations of;

generating a storage chunk having a plurality of data fragments, the storage chunk stored in one or more storage devices;

allocating space in a primary memory to store a plurality of coded fragments;

receiving a plurality of I/O requests to write data;

allocating space in the primary memory to store a next unfilled data fragment;

processing a plurality of I/O requests to write data, including for each I/O request;

writing the data to the next unfilled data fragment in the one or more storage devices;

writing the data to the next unfilled data fragment in the primary memory; and

if the data fragment in the primary memory is full, updating the coded fragments in the primary memory using the filled data fragment in the primary memory, removing the filled data fragment from the primary memory and allocating space in the primary memory to store a next unfilled data fragment; and

copying the coded fragments from the primary memory to the one or more storage devices.

7. The system of claim 6 wherein updating the coded fragments in primary memory using the full data fragment in primary memory comprises calculating C_i=C_i+X_i,j*D_full for each coding fragment C_i, where X is a matrix of coding coefficients and D_full is the full data fragment.

8. The system of claim 6 wherein the plurality of data fragments include k data fragments, the plurality of coded fragments include m coded fragments, the operations further comprising in an event of a loss of m data fragments within the chunk, accessing a number of k unique data fragments or coded fragments and using information from the k unique data fragments or the coded fragments to decode the m data fragments within the chunk.

9. The system of claim 6 wherein the primary memory includes dynamic random-access memory (DRAM).

10. The system of claim 6 wherein the storage devices comprise disk drives.

11. A computer program product tangibly embodied in a non-transitory computer-readable medium, the computer-readable medium storing program instructions that are executable to:

generate a storage chunk having a plurality of data fragments, the storage chunk stored in one or more storage devices;

allocate space in a primary memory to store a plurality of coded fragments;

receive a plurality of I/O requests to write data;

allocate space in the primary memory to store a next unfilled data fragment;

process a plurality of I/O requests to write data, including for each I/O request;

write the data to the next unfilled data fragment in the one or more storage devices;

write the data to the next unfilled data fragment in the primary memory; and

if the data fragment in the primary memory is full, update the coded fragments in the primary memory using the filled data fragment in the primary memory, removing the filled data fragment from the primary memory and allocating space in the primary memory to store a next unfilled data fragment; and

copy the coded fragments from the primary memory to the one or more storage devices.

12. The computer program product of claim 11 wherein updating the coded fragments in primary memory using the full data fragment in primary memory comprises calculating C_i=C_i+X_i,j*D_full for each coding fragment C_i, where X is a matrix of coding coefficients and D_full is the full data fragment.

13. The computer program product of claim 11 wherein the plurality of data fragments include k data fragments, the plurality of coded fragments include m coded fragments, the program instructions further configured to, in the event of a loss of m data fragments within the chunk, access a number of k unique data fragments or coded fragments and use information from the k unique data fragments or the coded fragments to decode the m data fragments within the chunk.

14. The computer program product of claim 11 wherein the primary memory includes dynamic random-access memory (DRAM).

15. The computer program product of claim 11 wherein the storage devices comprise disk drives.