Incremental erasure coding for storage systems

Patent metadata

Field	Value
Publication number	US-10248326-B2
Application number	US-201715398819-A
Country	US
Kind code	B2
Filing date	Jan 5, 2017
Priority date	Jun 29, 2016
Publication date	Apr 2, 2019
Grant date	Apr 2, 2019

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.

First claim

What is claimed is:

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.

Assignees

• Emc Ip Holding Co Llc

Inventors

• Danilov Mikhail
• Buinov Konstantin
• Fomin Andrey
• Kurilov Andrey
• Trusov Maxim

Classifications

• G06F3/067

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• G06F3/061 Primary

  Improving I/O performance · CPC title

• G06F3/0685

  Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays · CPC title

• G06F3/0659

  Command handling arrangements, e.g. command buffers, queues, command scheduling · CPC title