Executing Replication Requests for Objects In A Distributed Storage System

• US 20110196836A1
• 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,335,769 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 executing replication requests for objects in a distributed database is provided. A plurality of replication requests for objects in a distributed storage system is received. The replication requests are partitioned into one or more replication queues. A respective replication queue includes replication requests that have a respective replication key. The respective replication key includes information related to at least a respective source storage device at which a respective object is located and a respective destination storage device to which the respective object is to be replicated. For each respective replication queue, the replication requests in the replication queue are sorted based on priorities of the replication requests. Commands to execute a highest priority request are issued in each respective replication queue. When a respective replication request is completed, the respective replication request is deleted from the replication queue.

Claims

1. A computer-implemented method for executing 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 to perform the method, comprising;

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

partitioning the plurality of replication requests into one or more replication queues, wherein a respective replication queue includes replication requests that have a respective replication key, wherein the respective replication key includes information related to at least a respective source storage device at which a respective object is located and a respective destination storage device to which the respective object is to be replicated;

for each respective replication queue, sorting the replication requests in the replication queue based on priorities of the replication requests;

issuing commands to execute a highest priority request in each respective replication queue; and

when a respective replication request is completed, deleting the respective replication request from the replication queue.

2. The method of claim 1, further comprising issuing, to a blobmaster, commands to update metadata for a respective object corresponding to the respective replication request, wherein the blobmaster is configured to maintain metadata for objects in the distributed storage system.

3. The method of claim 1, further comprising for each respective replication queue, repeating the issuing and deleting until the replication queue is empty.

4. The method of claim 1, further comprising for each respective replication queue, repeating the issuing and deleting until a plurality of new replication requests is received from the location assignment daemon.

5. The method of claim 1, wherein the respective replication request includes:

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.

6. The method of claim 1, wherein each respective replication queue is handled by a respective task server that is separate and distinct from the computer system.

7. The method of claim 1, wherein a respective object is a binary large object (blob).

8. The method of claim 1, wherein the commands are issued to a bitpusher module configured to copy chunks of objects from source storage devices to destination storage devices.

9. The method of claim 8, wherein the bitpusher module is located on a second computer system that is separate and distinct from the computer system.

10. The method of claim 1, wherein the plurality of replication requests is received from a location assignment daemon configured to generate replication requests based at least in part on a current state of the distributed storage system and replication policies for objects in the distributed storage system.

11. The method of claim 10, wherein the location assignment daemon is located on a third computer system that is separate and distinct from the computer system.

12. The method of claim 1, wherein the replication key also includes a respective user identifier and a respective quality of service metric.

13. The method of claim 1, wherein the distributed storage system includes a plurality of instances of the distributed storage system.

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

15. A system for executing 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 in a distributed storage system;

partition the plurality of replication requests into one or more replication queues, wherein a respective replication queue includes replication requests that have a respective replication key, wherein the respective replication key includes information related to at least a respective source storage device at which a respective object is located and a respective destination storage device to which the respective object is to be replicated;

for each respective replication queue, sort the replication requests in the replication queue based on priorities of the replication requests;

issue commands to execute a highest priority request in each respective replication queue; and

when a respective replication request is completed, delete the respective replication request from the replication queue.

16. The system of claim 15, further comprising instructions to issue, to a blobmaster, commands to update metadata for a respective object corresponding to the respective replication request, wherein the blobmaster is configured to maintain metadata for objects in the distributed storage system.

17. The system of claim 15, further comprising instructions to for each respective replication queue, repeat the issuing and deleting until a plurality of new replication requests is received from the location assignment daemon.

18. The system of claim 15, wherein the respective replication request includes:

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 system of claim 15, wherein the plurality of replication requests is received from a location assignment daemon configured to generate replication requests based at least in part on a current state of the distributed storage system and replication policies for objects in the distributed storage system.

20. The system of claim 15, wherein the replication key also includes a respective user identifier and a respective quality of service metric.

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

22. 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 in a distributed storage system;

partition the plurality of replication requests into one or more replication queues, wherein a respective replication queue includes replication requests that have a respective replication key, wherein the respective replication key includes information related to at least a respective source storage device at which a respective object is located and a respective destination storage device to which the respective object is to be replicated;

for each respective replication queue, sort the replication requests in the replication queue based on priorities of the replication requests;

issue commands to execute a highest priority request in each respective replication queue; and

when a respective replication request is completed, delete the respective replication request from the replication queue.

23. The computer readable storage medium of claim 22, further comprising instructions to issue, to a blobmaster, commands to update metadata for a respective object corresponding to the respective replication request, wherein the blobmaster is configured to maintain metadata for objects in the distributed storage system.

24. The computer readable storage medium of claim 22, further comprising instructions to for each respective replication queue, repeat the issuing and deleting until a plurality of new replication requests is received from the location assignment daemon.

25. The computer readable storage medium of claim 22, wherein the respective replication request includes:

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.

26. The computer readable storage medium of claim 22, wherein the plurality of replication requests is received from a location assignment daemon configured to generate replication requests based at least in part on a current state of the distributed storage system and replication policies for objects in the distributed storage system.

27. The computer readable storage medium of claim 22, wherein the replication key also includes a respective user identifier and a respective quality of service metric.

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