Erasure-coding extents in an append-only storage system

Patent metadata

Field	Value
Publication number	US-2016139980-A1
Application number	US-201414540610-A
Country	US
Kind code	A1
Filing date	Nov 13, 2014
Priority date	Nov 13, 2014
Publication date	May 19, 2016
Grant date	—

Abstract

A data storage system stores sets of data blocks in extents located on storage devices. During operation, the system performs an erasure-coding operation by obtaining a set of source extents, wherein each source extent is stored on a different machine in the data storage system. The system also selects a set of destination machines for storing destination extents, wherein each destination extent is stored on a different destination machine. Next, the system performs the erasure-coding operation by retrieving data from the set of source extents, performing the erasure-coding operation on the retrieved data to produce erasure-coded data, and then writing the erasure-coded data to the set of destination extents on the set of destination machines. Finally, after the erasure-coding operation is complete, the system commits results of the erasure-coding operation to enable the set of destination extents to be accessed in place of the set of source extents.

First claim

What is claimed is:

1 . A computer-implemented method, comprising:
operating a data storage system that stores sets of data blocks in extents that are located in storage devices, wherein operating the data storage system involves performing an erasure-coding operation by: obtaining a set of source extents to be erasure-coded; selecting a set of destination machines for storing a set of destination extents to during the erasure-coding operation, wherein each destination extent in the set of destination extents is stored on a different machine in the set of destination machines; initializing the set of destination extents on the set of destination machines; performing the erasure-coding operation by,
retrieving data from the set of source extents,
performing an erasure-coding operation on the retrieved data to produce erasure-coded data, and
writing the erasure-coded data to the set of destination extents on the set of destination machines; and
after the erasure-coding operation is complete, committing results of the erasure-coding operation to enable the set of destination extents to be accessed in place of the set of source extents.

2 . The computer-implemented method of claim 1 , wherein committing the results of the erasure-coding operation involves:
performing an integrity check to ensure that each extent in the set of destination extents is properly generated on a machine in the set of destination machines; and if the integrity check succeeds, modifying one or more indices in the data storage system to refer to the destination extents instead of the source extents.

3 . The computer-implemented method of claim 1 ,
wherein the set of source extents comprises six extents; and wherein performing the erasure-coding operation involves computing an RS(6,3) Reed-Solomon code that takes the set of six source extents and generates three additional parity extents to produce an erasure-coded volume comprising nine extents.

4 . The computer-implemented method of claim 1 , wherein obtaining the set of extents to be erasure-coded includes selecting extents that are full, closed, replicated and synced.

5 . The computer-implemented method of claim 1 , wherein prior to obtaining the set of source extents, the method further comprises ensuring that each source extent in the set of source extents is stored on a different machine by moving one or more of the source extents in the set of source extents to different machines.

6 . The computer-implemented method of claim 1 ,
wherein prior to obtaining the set of source extents, each source extent in the set of source extents is replicated so that redundant copies of the extent exist on different machines in the data storage system; and wherein after the erasure-coding operation is complete, the method further comprises deleting redundant copies of source extents in the set of source extents.

7 . The computer-implemented method of claim 1 ,
wherein initializing the set of destination extents on the set of destination machines involves initializing a set of scratch extents that are accessible through private identifiers on the set of destination machines; and wherein enabling the set of destination extents to be accessed in place of the source extents further involves associating the set of scratch extents with public identifiers that are accessible through indices in the data storage system.

8 . The computer-implemented method of claim 1 , wherein performing the erasure-coding operation additionally involves performing a compaction operation on data retrieved from the source extents so that corresponding data written to the destination extents is compacted.

9 . The computer-implemented method of claim 1 , wherein performing the erasure-coding operation involves using a volume manager to perform the erasure-coding operation, wherein the volume manager is a separate process in the data storage system.

10 . A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method, the method comprising:
operating a data storage system that stores sets of data blocks in extents that are located in storage devices, wherein operating the data storage system involves performing an erasure-coding operation by: obtaining a set of source extents to be erasure-coded; selecting a set of destination machines for storing a set of destination extents to during the erasure-coding operation, wherein each destination extent in the set of destination extents is stored on a different machine in the set of destination machines; initializing the set of destination extents on the set of destination machines; performing the erasure-coding operation by,
retrieving data from the set of source extents,
performing an erasure-coding operation on the retrieved data to produce erasure-coded data, and
writing the erasure-coded data to the set of destination extents on the set of destination machines; and
after the erasure-coding operation is complete, committing results of the erasure-coding operation to enable the set of destination extents to be accessed in place of the set of source extents.

11 . The non-transitory computer-readable storage medium of claim 10 , wherein committing the results of the erasure-coding operation involves:
performing an integrity check to ensure that each extent in the set of destination extents is properly generated on a machine in the set of destination machines; and if the integrity check succeeds, modifying one or more indices in the data storage system to refer to the destination extents instead of the source extents.

12 . The non-transitory computer-readable storage medium of claim 10 ,
wherein the set of source extents comprises six extents; and wherein performing the erasure-coding operation involves computing an RS(6,3) Reed-Solomon code that takes the set of six source extents and generates three additional parity extents to produce an erasure-coded volume comprising nine extents.

13 . The non-transitory computer-readable storage medium of claim 10 , wherein obtaining the set of extents to be erasure-coded includes selecting extents that are full, closed, replicated and synced.

14 . The non-transitory computer-readable storage medium of claim 10 , wherein prior to obtaining the set of source extents, the method further comprises ensuring that each source extent in the set of source extents is stored on a different machine by moving one or more of the source extents in the set of source extents to different machines.

15 . The non-transitory computer-readable storage medium of claim 10 ,
wherein prior to obtaining the set of source extents, each source extent in the set of source extents is replicated so that redundant copies of the extent exist on different machines in the data storage system; and wherein after the erasure-coding operation is complete, the method further comprises deleting redundant copies of source extents in the set of source extents.

16 . The non-transitory computer-readable storage medium of claim 10 ,
wherein initializing the set of destination extents on the set of destination machines involves initializing a set of scratch extents that are accessible through private identifiers on the set of destination machines; and wherein enabling the set of destination extents to be accessed in place of the source extents further involves associating the set of scratch extents with public identifiers that are accessible through indices in the data storage system.

17 . A data stora

Assignees

• Dropbox Inc

Inventors

• Cowling James
• Modzelewski Kevin P
• Mallipeddi Venkata Harish

Classifications

• G06F11/1048 Primary

  using arrangements adapted for a specific error detection or correction feature · CPC title

• H03M13/1515

  Reed-Solomon codes · CPC title

• G06F11/1004 Primary

  to protect a block of data words, e.g. CRC or checksum (G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00) · CPC title

• H03M13/611

  Specific encoding aspects, e.g. encoding by means of decoding · CPC title

• H03M13/05

  using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits {(H03M13/2906 takes precedence)} · CPC title