Storing replication requests for objects in a distributed storage system

• US 8,271,455 B2
• Filed: 02/09/2011
• Issued: 09/18/2012
• Est. Priority Date: 02/09/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kesselman, Alexander
• Primary Examiner(s): Ehichioya, Fred I
• Assistant Examiner(s): Mobin, Hasanul
• Application Number:
  US13/024,186
• Publication Number:
  US 20110196834A1
• Time in Patent Office: 587 Days
• Field of Search: None
• US Class Current: 707/679
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor

Abstract

A system and method for storing replication requests for objects in a distributed storage system is provided. A plurality of replication requests for objects stored on storage devices in a distributed storage system is received. Respective row keys are generated for respective replication requests in the plurality of replication requests based on parameters of the respective replication requests. The respective row keys include respective globally-determined priorities for the respective replication requests that facilitate sorting of the respective replication requests by priority. The respective replication requests are stored in respective records of a distributed database using the respective row keys, wherein the respective records of the distributed database are distributed across a plurality of nodes of the distributed database.

Claims

1. A computer-implemented method for storing replication requests for objects in a distributed storage system, comprising:

at a computer system including one or more processors and memory storing one or more programs, for execution by the one or more processors;

receiving a plurality of replication requests for objects stored on storage devices in a distributed storage system;

generating respective row keys for respective replication requests in the plurality of replication requests based on parameters of the respective replication requests, wherein the respective row keys include respective globally-determined priorities for the respective replication requests that facilitate sorting of the respective replication requests by priority; and

storing the respective replication requests in respective records of a distributed database using the respective row keys, wherein the respective records of the distributed database are distributed across a plurality of nodes of the distributed database,

wherein the plurality of replication requests is received from a location assignment daemon that is configured to generate replication requests globally across instances of the distributed storage system based at least in part on a current state of the distributed storage system and replication policies for objects in the distributed storage system.

2. The method of claim 1, wherein the parameters for a respective replication request include:

a replication key corresponding to a respective object;

a list of chunks of the respective object;

a replication identifier corresponding to the respective replication request; and

a globally-determined profit value corresponding to the respective replication request, wherein the globally-determined profit value is based on a metric corresponding to a benefit of performing the respective replication request minus a metric corresponding to a cost of performing the respective replication request.

3. The method of claim 2, wherein a respective row key for the respective replication request is generated based on the replication key of the respective replication request, the profit value of the respective replication request, and the replication identifier of the respective replication request.

4. The method of claim 2, wherein a respective row key for the respective replication request is generated based on a hashed version of the replication key of the respective replication request, the profit value of the respective replication request, and the replication identifier of the respective replication request.

5. The method of claim 2, wherein the replication key includes:

a user identifier;

a quality of service metric;

an identifier for a source storage device in the distributed storage system; and

an identifier for a destination storage device in the distributed storage system.

6. The method of claim 2, wherein a globally-determined priority of the respective replication request is based on the globally-determined profit value for the respective replication request.

7. The method of claim 1, wherein the location assignment daemon is located on a second computer system that is separate and distinct from the computer system.

8. The method of claim 1, wherein a respective replication request is executable to add a replica of the respective object at an instance of the distributed storage system.

9. A system for storing replication requests for objects in a distributed storage system, comprising:

one or more processors;

memory; and

one or more programs stored in the memory, the one or more programs comprising instructions to;

receive a plurality of replication requests for objects stored on storage devices in a distributed storage system;

generate respective row keys for respective replication requests in the plurality of replication requests based on parameters of the respective replication requests, wherein the respective row keys include respective globally-determined priorities for the respective replication requests that facilitate sorting of the respective replication requests by priority; and

store the respective replication requests in respective records of a distributed database using the respective row keys, wherein the respective records of the distributed database are distributed across a plurality of nodes of the distributed database,

wherein the plurality of replication requests is received from a location assignment daemon that is configured to generate replication requests globally across instances of the distributed storage system based at least in part on a current state of the distributed storage system and replication policies for objects in the distributed storage system.

10. The system of claim 9, wherein the parameters for a respective replication request include:

a replication key corresponding to a respective object;

a list of chunks of the respective object;

a replication identifier corresponding to the respective replication request; and

a globally-determined profit value corresponding to the respective replication request, wherein the globally-determined profit value is based on a metric corresponding to a benefit of performing the respective replication request minus a metric corresponding to a cost of performing the respective replication request.

11. The system of claim 10, wherein a respective row key for the respective replication request is generated based on the replication key of the respective replication request, the profit value of the respective replication request, and the replication identifier of the respective replication request.

12. The system of claim 10, wherein a respective row key for the respective replication request is generated based on a hashed version of the replication key of the respective replication request, the profit value of the respective replication request, and the replication identifier of the respective replication request.

13. The system of claim 10, wherein the replication key includes:

a user identifier;

a quality of service metric;

an identifier for a source storage device in the distributed storage system; and

an identifier for a destination storage device in the distributed storage system.

14. The system of claim 10, wherein a globally-determined priority of the respective replication request is based on the globally-determined profit value for the respective replication request.

15. The system of claim 9, wherein the location assignment daemon is located on a second computer system that is separate and distinct from the computer system.

16. The system of claim 9, wherein a respective replication request is executable to add a replica of the respective object at an instance of the distributed storage system.

17. A non-transitory computer readable storage medium storing one or more programs configured for execution by a computer, the one or more programs comprising instructions to:

receive a plurality of replication requests for objects stored on storage devices in a distributed storage system;

generate respective row keys for respective replication requests in the plurality of replication requests based on parameters of the respective replication requests, wherein the respective row keys include respective globally-determined priorities for the respective replication requests that facilitate sorting of the respective replication requests by priority; and

store the respective replication requests in respective records of a distributed database using the respective row keys, wherein the respective records of the distributed database are distributed across a plurality of nodes of the distributed database,

wherein the plurality of replication requests is received from a location assignment daemon that is configured to generate replication requests globally across instances of the distributed storage system based at least in part on a current state of the distributed storage system and replication policies for objects in the distributed storage system.

18. The computer readable storage medium of claim 17, wherein the parameters for a respective replication request include:

a replication key corresponding to a respective object;

a list of chunks of the respective object;

a replication identifier corresponding to the respective replication request; and

a globally-determined profit value corresponding to the respective replication request, wherein the globally-determined profit value is based on a metric corresponding to a benefit of performing the respective replication request minus a metric corresponding to a cost of performing the respective replication request.

19. The computer readable storage medium of claim 18, wherein a respective row key for the respective replication request is generated based on the replication key of the respective replication request, the profit value of the respective replication request, and the replication identifier of the respective replication request.

20. The computer readable storage medium of claim 18, wherein a respective row key for the respective replication request is generated based on a hashed version of the replication key of the respective replication request, the profit value of the respective replication request, and the replication identifier of the respective replication request.

21. The computer readable storage medium of claim 18, wherein the replication key includes:

a user identifier;

a quality of service metric;

an identifier for a source storage device in the distributed storage system; and

an identifier for a destination storage device in the distributed storage system.

22. The computer readable storage medium of claim 18, wherein a globally-determined priority of the respective replication request is based on the globally-determined profit value for the respective replication request.

23. The computer readable storage medium of claim 17, wherein the location assignment daemon is located on a second computer system that is separate and distinct from the computer system.

24. The computer readable storage medium of claim 17, wherein a respective replication request is executable to add a replica of the respective object at an instance of the distributed storage system.