Storing Replication Requests for Objects In A Distributed Storage System

• US 20110196834A1
• Filed: 02/09/2011
• Published: 08/11/2011
• Est. Priority Date: 02/09/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kesselman, Alexander
• Granted Patent: US 8,271,455 B2
• Time in Patent Office: Days
• US Class Current: 707/634
• 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.

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 plurality of replication requests is received from a location assignment daemon 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.

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

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

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

11. The system of claim 10, 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.

12. The system of claim 11, 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.

13. The system of claim 11, 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.

14. The system of claim 11, 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.

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

16. The system of claim 10, wherein the plurality of replication requests is received from a location assignment daemon 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.

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

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

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

20. The computer readable storage medium of claim 19, 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.

21. The computer readable storage medium of claim 20, 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.

22. The computer readable storage medium of claim 20, 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.

23. The computer readable storage medium of claim 20, 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.

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

25. The computer readable storage medium of claim 19, wherein the plurality of replication requests is received from a location assignment daemon 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.

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

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