Granted Patent B2

US 9,619,322 · App. 14/540,610 · Granted Apr 11, 2017

Abstract

Claims (71)

1. A computer-implemented method, comprising:

obtaining a set of source extents to be erasure-coded;

selecting a set of destination machines for storing a set of destination extents;

storing the set of destination extents on the set of destination machines, 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;

retrieving data from the set of source extents;

performing an erasure-coding operation on the retrieved data to produce erasure-coded data;

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 , further comprising:

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

where the integrity check succeeds, modifying one or more indices 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 the method further comprises 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 the obtaining the set of extents to be erasure-coded is based, at least in part, on selecting extents that are full, closed, replicated and synced.

5. The computer-implemented method of claim 1 , further comprising prior to the obtaining the set of source extents, ensuring that each source extent in the set of source extents is stored on a different machine based, at least in part, on 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 the 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; and

wherein the method further comprises after the erasure-coding operation is complete, deleting redundant copies of source extents in the set of source extents.

7. The computer-implemented method of claim 1 ,

wherein the initializing the set of destination extents on the set of destination machines is based, at least in part, on initializing a set of scratch extents that are accessible through private identifiers on the set of destination machines; and

wherein the method further comprises enabling the set of destination extents to be accessed in place of the source extents further based, at least in part, on associating the set of scratch extents with public identifiers that are accessible through indices.

8. The computer-implemented method of claim 1 , further comprising 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 , further comprising using a volume manager to perform the erasure-coding operation, wherein the volume manager is a separate process.

10. A non-transitory computer-readable storage medium storing instructions that when executed by a computer system cause the computer system to perform operations comprising:

obtaining a set of source extents to be erasure-coded;

selecting a set of destination machines for storing a set of destination extents;

storing the set of destination extents on the set of destination machines, 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;

retrieving data from the set of source extents;

performing an erasure-coding operation on the retrieved data to produce erasure-coded data;

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 the committing the results of the erasure-coding operation is based, at least in part, on:

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

where the integrity check succeeds, modifying one or more indices 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 the operations further comprise 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 the obtaining the set of extents to be erasure-coded is based, at least in part, on selecting extents that are full, closed, replicated and synced.

14. The non-transitory computer-readable storage medium of claim 10 , wherein the operations further comprise prior to the obtaining the set of source extents, ensuring that each source extent in the set of source extents is stored on a different machine based, at least in part, on 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 the 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; and

wherein the operations further comprise after the erasure-coding operation is complete, deleting redundant copies of source extents in the set of source extents.

16. The non-transitory computer-readable storage medium of claim 10 , wherein the initializing the set of destination extents on the set of destination machines is based, at least in part, on initializing a set of scratch extents that are accessible through private identifiers on the set of destination machines; and

wherein the operations further comprise enabling the set of destination extents to be accessed in place of the source extents based, at least in part, on associating the set of scratch extents with public identifiers that are accessible through indices.

17. A data storage system, comprising:

one or more processors;

instructions for execution by the one or more processors and configured to perform, when executed by the one or more processors, the operations of:

obtaining a set of source extents to be erasure-coded;

selecting a set of destination machines for storing a set of destination extents;

storing the set of destination extents on the set of destination machines, 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;

retrieving data from the set of source extents;

performing an erasure-coding operation on the retrieved data to produce erasure-coded data;

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.

18. The data storage system of claim 17 , wherein the committing the results of the erasure-coding operation is based, at least in part, on:

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

where 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.

19. The data storage system of claim 17 ,

wherein the set of source extents comprises six extents; and

wherein the operations further comprise 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.

20. The data storage system of claim 17 , wherein the obtaining the set of extents to be erasure-coded is based, at least in part, on selecting extents that are full, closed, replicated and synced.

21. The data storage system of claim 17 , wherein the operations further comprise prior to the obtaining the set of source extents, ensuring that each source extent in the set of source extents is stored on a different machine based, at least in part, on moving one or more of the source extents in the set of source extents to different machines.

22. The data storage system of claim 17 ,

wherein prior to the obtaining the set of source extents, replicating each source extent in the set of source extents so that redundant copies of each source extent exist on different machines in the data storage system; and

wherein after the erasure-coding operation is complete, deleting redundant copies of source extents in the set of source extents.

23. The data storage system of claim 17 ,

wherein the initializing the set of destination extents on the set of destination machines is based, at least in part, on initializing a set of scratch extents that are accessible through private identifiers on the set of destination machines; and

wherein the enabling the set of destination extents to be accessed in place of the source extents is based, at least in part, on associating the set of scratch extents with public identifiers that are accessible through indices in the data storage system.

Assignments (6)