Location assignment daemon (LAD) for a distributed storage system

• US 9,317,524 B2
• Filed: 11/11/2014
• Issued: 04/19/2016
• Est. Priority Date: 02/09/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Zunger, Yonatan, Drobychev, Alexandre, Kesselman, Alexander, Vickrey, Rebekah C., Dachille, Frank C., Datuashvili, George
• Primary Examiner(s): Mamillapalli, Pavan
• Application Number:
  US14/538,716
• Publication Number:
  US 20150142743A1
• Time in Patent Office: 525 Days
• Field of Search: 707/634, 707/626
• US Class Current: 1/1
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 11/3457 Performance evaluation by simulation
• CPC Class Codes: G06F 13/10 Program control for peripheral devices G06F13/14 - G06F13/42 take precedence
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems
• CPC Class Codes: G06G 7/62 for electric systems or apparatus G06G7/78 takes precedence
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

A system and method for generating replication requests for objects in a distributed storage system is provided. For a respective object in a distributed storage system the following is performed. Replication policies for the object that have not been satisfied are determined. Replication requests are ranked for the object whose replication policies have not been satisfied based on a number of replicas of the object that need to be created in order to satisfy the replication policies for the object. Replication requests are generated for the object based at least in part on the replication policies for the object that have not been satisfied and on a current state of the distributed storage system. At least a subset of the replication requests for the objects in the distributed storage system are distributed to respective instances of the distributed storage system corresponding to the replication requests for execution.

Claims

1. A computer-implemented method for generating 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;

storing a plurality of objects in the distributed storage system, wherein each object has an associated replication policy that specifies a desired number of replicas of the respective object and specifies desired storage device types on which the replicas of the respective object are to be stored;

identifying a plurality of objects in the distributed storage system whose associated replication policies have not been satisfied;

ranking replication requests for the objects whose replication policies have not been satisfied based on respective numbers of replicas of the respective objects object that need to be created in order to satisfy the replication policies for the objects; and

generating replication requests for the identified plurality of objects based on the associated replication policies for the objects that have not been satisfied and on a current state of the distributed storage system, wherein each respective replication request for a respective object instructs a respective instance of the distributed storage system to replicate the respective object so as to better satisfy the respective replication policy associated with the respective object; and

distributing at least a subset of the replication requests for the objects in the distributed storage system to respective instances of the distributed storage system corresponding to the replication requests, for execution at the respective instances.

2. The method of claim 1, wherein prior to the distributing the method further comprises:

partitioning the replication requests into groups of respective replication requests corresponding to respective instances of the distributed storage system at which respective predetermined actions of the respective replication requests are to be performed;

calculating priorities of the replication requests; and

for a respective group of replication requests, sorting the replication requests in the group of replication requests by priority to produce a sorted group of replication requests.

3. The method of claim 2, wherein calculating a priority of a respective replication request includes calculating the priority of the respective replication request as a difference between a metric corresponding to a benefit of performing the respective replication request and a metric corresponding to a cost of performing the respective replication request.

4. The method of claim 1, wherein prior to the distributing the method further comprises determining which replication requests can be completed within a predetermined time interval.

5. The method of claim 4, further comprising discarding replication requests that cannot be completed within the predetermined time interval.

6. The method of claim 1, wherein the current state of the distributed storage system includes:

a current network state;

current user quotas for storage space in the distributed storage system;

storage space in the distributed storage system that is currently used by users;

current storage space available at instances of the distributed storage system;

current statuses of replication queues at instances of the distributed storage system;

current planned maintenance operations zones; and

a list of current replicas of objects in the distributed storage system.

7. The method of claim 1, wherein each replication policy for an object includes criteria selected from the group consisting of:

a desired minimum number of replicas of the object in the distributed storage system;

a desired maximum number of replicas of the object in the distributed storage system;

storage device types on which replicas of the object are to be stored;

instances at which replicas of the object may be stored;

instances at which replicas of the object may not be stored; and

a range of ages for the object during which the replication policy for the object applies.

8. The method of claim 1, wherein generating the replication requests is further based in part on costs and benefits for performing the replication requests.

9. The method of claim 1, wherein replication requests are distributed to a replication queue in a respective instance of the distributed storage system.

10. A system for generating 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 for;

storing a plurality of objects in the distributed storage system, wherein each object has an associated replication policy that specifies a desired number of replicas of the respective object and specifies desired storage device types on which the replicas of the respective object are to be stored;

identifying a plurality of objects in the distributed storage system whose associated replication policies have not been satisfied;

ranking replication requests for the objects whose replication policies have not been satisfied based on respective numbers of replicas of the respective objects that need to be created in order to satisfy the replication policies for the objects; and

generating replication requests for the identified plurality of objects based on the associated replication policies for the objects that have not been satisfied and on a current state of the distributed storage system, wherein each respective replication request for a respective object instructs a respective instance of the distributed storage system to replicate the respective object so as to better satisfy the respective replication policy associated with the respective object; and

distributing at least a subset of the replication requests for the objects in the distributed storage system to respective instances of the distributed storage system corresponding to the replication requests, for execution at the respective instances.

11. The system of claim 10, wherein the one or more programs further comprise instructions that execute prior to the distributing, thereby:

partitioning the replication requests into groups of respective replication requests corresponding to respective instances of the distributed storage system at which respective predetermined actions of the respective replication requests are to be performed;

calculating priorities of the replication requests; and

for a respective group of replication requests, sorting the replication requests in the group of replication requests by priority to produce a sorted group of replication requests.

12. The system of claim 11, wherein the instructions for calculating a priority of a respective replication request include instructions for calculating the priority of the respective replication request as a difference between a metric corresponding to a benefit of performing the respective replication request and a metric corresponding to a cost of performing the respective replication request.

13. The system of claim 11, wherein the one or more programs further comprise instructions that execute prior to the distributing, thereby determining which replication requests can be completed within a predetermined time interval.

14. The system of claim 13, wherein the one or more program further comprise instructions for discarding replication requests that cannot be completed within the predetermined time interval.

15. The system of claim 10, wherein the current state of the distributed storage system includes:

a current network state;

current user quotas for storage space in the distributed storage system;

storage space in the distributed storage system that is currently used by users;

current storage space available at instances of the distributed storage system;

current statuses of replication queues at instances of the distributed storage system;

current planned maintenance operations zones; and

a list of current replicas of objects in the distributed storage system.

16. The system of claim 10, wherein each replication policy for an object includes criteria selected from the group consisting of:

a desired minimum number of replicas of the object in the distributed storage system;

a desired maximum number of replicas of the object in the distributed storage system;

storage device types on which replicas of the object are to be stored;

instances at which replicas of the object may be stored;

instances at which replicas of the object may not be stored; and

a range of ages for the object during which the replication policy for the object applies.

17. The system of claim 10, wherein the instructions for generating the replication requests further comprise instructions for generating the replication requests in part on costs and benefits for performing the replication requests.

18. The system of claim 10, wherein the instructions for distributing the replication requests further include instructions for distributing the replication requests to a replication queue in a respective 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 for:

storing a plurality of objects in the distributed storage system, wherein each object has an associated replication policy that specifies a desired number of replicas of the respective object and specifies desired storage device types on which the replicas of the respective object are to be stored;

identifying a plurality of objects in the distributed storage system whose associated replication policies have not been satisfied;

ranking replication requests for the objects whose replication policies have not been satisfied based on respective numbers of replicas of the respective objects that need to be created in order to satisfy the replication policies for the objects; and

generating replication requests for the identified plurality of objects based on the associated replication policies for the objects that have not been satisfied and on a current state of the distributed storage system, wherein each respective replication request for a respective object instructs a respective instance of the distributed storage system to replicate the respective object so as to better satisfy the respective replication policy associated with the respective object; and

distributing at least a subset of the replication requests for the objects in the distributed storage system to respective instances of the distributed storage system corresponding to the replication requests, for execution at the respective instances.

20. The non-transitory computer readable storage medium of claim 19, wherein the one or more programs further comprise instructions that execute prior to the distributing, thereby determining which replication requests can be completed within a predetermined time interval and discarding replication requests that cannot be completed within the predetermined time interval.