Using scratch extents to facilitate copying operations in an append-only storage system

• US 10,248,356 B2
• Filed: 10/21/2014
• Issued: 04/02/2019
• Est. Priority Date: 10/21/2014
• Status: Active Grant

• Current Assignee: Dropbox, Inc.
• Original Assignee: Dropbox, Inc.
• Inventors: Cowling, James, Turner, James
• Primary Examiner(s): Lo, Ann J
• Assistant Examiner(s): Khan, Masud K
• Application Number:
  US14/519,907
• Publication Number:
  US 20160110109A1
• Time in Patent Office: 1,624 Days
• Field of Search: 711161
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 2212/254 Distributed memory
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0623 in relation to content
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

An append-only data storage system is described that stores sets of data blocks in extents that are located in storage devices. During operation of the system, upon receiving a request to copy an extent from a source storage device to a destination storage device, the system creates a scratch extent on the destination storage device, and associates the scratch extent with a private identifier, whereby the scratch extent can only be accessed through the private identifier. The system uses the private identifier to perform a copying operation that copies the extent from the source storage device to the scratch extent on the destination storage device. After the copying operation is complete and the scratch extent is closed, the system associates the scratch extent with a public identifier, whereby the copy of the extent on the destination storage device becomes publically accessible to other entities in the data storage system.

Claims

1. A computer-implemented method, comprising:

at one or more devices comprising one or more processors and memory storing instructions executed by the one or more processors to perform the method, performing the following operations;

receiving a request to copy an extent from a source storage device to a destination storage device;

creating a scratch extent on the destination storage device;

associating the scratch extent with a private identifier;

performing a copying operation that copies the extent from the source storage device to the scratch extent on the destination storage device;

wherein the scratch extent is associated with the private identifier while the copying operation is being performed;

after the copying operation is complete and the scratch extent is closed, associating the scratch extent with a public identifier;

wherein associating the scratch extent with the private identifier comprises using the private identifier to create a first entry in a lookup structure stored at the destination storage device, the first entry for accessing the scratch extent using the private identifier, the first entry retrievable from the lookup structure using the private identifier; and

wherein associating the scratch extent with the public identifier comprises using the public identifier to create a second entry in the lookup structure, the second entry for accessing the scratch extent using the public identifier, the second entry retrievable from the lookup structure using the public identifier.

2. The computer-implemented method of claim 1,

wherein the private identifier comprises a one-hundred and twenty-two bit randomly selected portion.

3. The computer-implemented method of claim 1,

wherein accesses to extents on the destination storage device involve performing lookups based on associated identifiers in the lookup structure in the destination storage device;

and

wherein the lookup structure includes an entry for each identifier that includes functionality to access an associated extent.

4. The computer-implemented method of claim 3, wherein the lookup structure comprises a hash map that associates a hash of an identifier with an associated extent object that can be used to access an associated extent on the destination storage device.

5. The computer-implemented method of claim 1, wherein performing the copying operation involves verifying a checksum for the scratch extent to ensure that the extent is correctly copied to the scratch extent.

6. The computer-implemented method of claim 1, wherein the copying operation is associated with moving the extent from the source storage device to the destination storage device.

7. The computer-implemented method of claim 1, wherein the copying operation is associated with replicating the extent from the source storage device to the destination storage device.

8. The computer-implemented method of claim 1,

wherein the extent on the source storage device comprises a set of un-encoded extents on a set of source storage devices;

wherein the copy of the extent on the destination storage device comprises a corresponding set of erasure-coded extents on a set of destination storage devices; and

wherein performing the copying operation involves performing an erasure-coding operation that encodes the set of un-encoded extents from the set of source storage devices to the corresponding set of erasure-coded extents on the set of destination storage devices.

9. The computer-implemented method of claim 8,

wherein the request is sent by a master and is received by a volume manager, wherein the master and the volume manager comprise processes at the one or more devices;

wherein the volume manager asks the set of destination storage devices to create scratch extents and also performs the erasure-coding operation;

wherein after the erasure-coding operation is complete, the scratch extents are closed, and associated checksums are verified, the volume manager sends private identifiers for the scratch extents to the master; and

wherein after receiving the private identifier, the master tells the set of destination storage devices to associate the scratch extents with associated public identifiers.

10. One or more non-transitory computer-readable media storing instructions that when executed by a computer system cause the computer system to perform operations comprising:

receiving a request to copy an extent from a source storage device to a destination storage device;

creating a scratch extent on the destination storage device;

associating the scratch extent with a private identifier;

performing a copying operation that copies the extent from the source storage device to the scratch extent on the destination storage device;

wherein the scratch extent is associated with the private identifier while the copying operation is being performed;

after the copying operation is complete and the scratch extent is closed, associating the scratch extent with a public identifier;

wherein associating the scratch extent with the private identifier comprises using the private identifier to create a first entry in a lookup structure stored at the destination storage device, the first entry for accessing the scratch extent using the private identifier, the first entry retrievable from the lookup structure using the private identifier; and

wherein associating the scratch extent with the public identifier comprises using the public identifier to create a second entry in the lookup structure, the second entry for accessing the scratch extent using the public identifier, the second entry retrievable from the lookup structure using the public identifier.

11. The one or more non-transitory computer-readable media of claim 10,

wherein the private identifier comprises a one-hundred and twenty-two bit randomly selected portion.

12. The one or more non-transitory computer-readable media of claim 10,

wherein accesses to extents on the destination storage device involve performing lookups based on associated identifiers in the lookup structure in the destination storage device;

and

wherein the lookup structure includes an entry for each identifier that includes functionality to access an associated extent.

13. The one or more non-transitory computer-readable media of claim 12, wherein the lookup structure comprises a hash map that associates a hash of an identifier with an associated extent object that can be used to access an associated extent on the destination storage device.

14. The one or more non-transitory computer-readable media of claim 10, wherein performing the copying operation involves verifying a checksum for the scratch extent to ensure that the extent is correctly copied to the scratch extent.

15. The one or more non-transitory computer-readable media of claim 10, wherein the copying operation is associated with moving the extent from the source storage device to the destination storage device.

16. The one or more non-transitory computer-readable media of claim 10, wherein the copying operation is associated with replicating the extent from the source storage device to the destination storage device.

17. The one or more non-transitory computer-readable media of claim 10,

wherein the extent on the source storage device comprises a set of un-encoded extents on a set of source storage devices;

wherein the copy of the extent on the destination storage device comprises a corresponding set of erasure-coded extents on a set of destination storage devices; and

wherein performing the copying operation involves performing an erasure-coding operation that encodes the set of un-encoded extents from the set of source storage devices to the corresponding set of erasure-coded extents on the set of destination storage devices.

18. The one or more non-transitory computer-readable media of claim 17,

wherein the request is sent by a master and is received by a volume manager, wherein the master and the volume manager comprise processes at the one or more devices;

wherein the volume manager asks the set of destination storage devices to create scratch extents and also performs the erasure-coding operation;

wherein after the erasure-coding operation is complete, the scratch extents are closed, and associated checksums are verified, the volume manager sends private identifiers for the scratch extents to the master; and

wherein after receiving the private identifier, the master tells the set of destination storage devices to associate the scratch extents with associated public identifiers.

19. A data storage system, comprising:

one or more storage devices containing extents, wherein each extent stores a set of data blocks;

wherein upon receiving a request to copy an extent from a source storage device to a destination storage device, the data storage system is configured to;

create a scratch extent on the destination storage device,

associate the scratch extent with a private identifier,

perform a copying operation that copies the extent from the source storage device to the scratch extent on the destination storage device,

wherein the scratch extent is associated with the private identifier while the copying operation is being performed,

after the copying operation is complete and the scratch extent is closed, associate the scratch extent with a public identifier,

wherein the data storage system is configured to associate the scratch extent with the private identifier using the private identifier to create a first entry in a lookup structure stored at the destination storage device, the first entry for accessing the scratch extent using the private identifier, the first entry retrievable from the lookup structure using the private identifier, and

wherein the data storage system is configured to associate the scratch extent with the public identifier using the public identifier to create a second entry in the lookup structure, the second entry for accessing the scratch extent using the public identifier, the second entry retrievable from the lookup structure using the public identifier.

20. The data storage system of claim 19,

wherein the private identifier comprises a one-hundred and twenty-two bit randomly selected portion.

21. The data storage system of claim 19,

wherein accesses to extents on the destination storage device involve performing lookups based on associated identifiers in the lookup structure in the destination storage device;

and

wherein the lookup structure includes an entry for each identifier that includes functionality to access an associated extent.

22. The data storage system of claim 21, wherein the lookup structure comprises a hash map that associates a hash of an identifier with an associated extent object that can be used to access an associated extent on the destination storage device.

23. The data storage system of claim 19, wherein while performing the copying operation, the data storage system is configured to verify a checksum for the scratch extent to ensure that the extent is correctly copied to the scratch extent.

24. The data storage system of claim 19, wherein the copying operation is associated with moving the extent from the source storage device to the destination storage device.

25. The data storage system of claim 19, wherein the copying operation is associated with replicating the extent from the source storage device to the destination storage device.

26. The data storage system of claim 19,

wherein the extent on the source storage device comprises a set of un-encoded extents on a set of source storage devices;

wherein the copy of the extent on the destination storage device comprises a corresponding set of erasure-coded extents on a set of destination storage devices; and

wherein while performing the copying operation, the data storage system is configured to perform an erasure-coding operation that encodes the set of un-encoded extents from the set of source storage devices to the corresponding set of erasure-coded extents on the set of destination storage devices.

27. The data storage system of claim 26,

wherein the request is sent by a master and is received by a volume manager, wherein the master and the volume manager comprise processes at the one or more devices;

wherein the volume manager asks the set of destination storage devices to create scratch extents and also performs the erasure-coding operation;

wherein after the erasure-coding operation is complete, the scratch extents are closed, and associated checksums are verified, the volume manager sends private identifiers for the scratch extents to the master; and

wherein after receiving the private identifier, the master tells the set of destination storage devices to associate the scratch extents with associated public identifiers.