Pruning of Blob Replicas

• US 20110196831A1
• Filed: 02/07/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: Kessleman, Alexandre, Datuashvili, George, Zunger, Yonatan, Drobychev, Alexandre, Vickrey, Rebekah C., Dachille, Frank C.
• Granted Patent: US 8,744,997 B2
• Time in Patent Office: Days
• US Class Current: 707/634
• 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 generating and distributing replica removal requests for objects in a distributed storage system is provided. Replica removal requests for objects in a distributed storage system are generated based at least in part on replication policies for the objects. A respective replica removal request instructs a respective instance of the distributed storage system to remove a respective replica of the respective object so as to at least partially satisfy replication policies for the respective object. Then the replica removal requests for the objects in the distributed storage system are distributed to respective instances of the distributed storage system corresponding to the replica removal requests for execution.

Claims

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

generating replica removal requests for objects in a distributed storage system based at least in part on replication policies for the objects, wherein a respective replica removal request instructs a respective instance of the distributed storage system to remove a respective replica of the respective object so as to at least partially satisfy replication policies for the respective object; and

distributing the replica removal requests for the objects in the distributed storage system to respective instances of the distributed storage system corresponding to the replica removal requests for execution.

2. A computer-implemented method for generating and distributing replica removal 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;

for a respective object in a distributed storage system,

identifying one or more replicas of the object to be removed from the distributed storage system based at least in part on replication policies for the object;

generating replica removal requests for the one or more replicas of the object, wherein a respective replica removal request instructs a respective instance of the distributed storage system to remove a respective replica of the respective object so as to at least partially satisfy replication policies for the respective object; and

distributing the replica removal requests for the object in the distributed storage system to respective instances of the distributed storage system corresponding to the replica removal requests for execution.

3. The method of claim 2, wherein generating the replica removal requests for the one or more replicas of the object includes:

identifying replication policies for the object that have been violated;

selecting the one or more replicas of the object to be removed from instances of the distributed storage system based at least in part on last access times of replicas of the respective object and the current storage space available at the instances of the distributed storage system including the replicas of the respective object; and

generating the replica removal requests for the one or more selected replica of the respective object.

4. The method of claim 2, wherein generating the replica removal requests for the one or more replicas of the object includes:

determining that an instance of the distributed storage system including the replica of the object is being deactivated;

determining whether the deactivation of the instance of the distributed storage system causes a number of replicas of the object to be below a minimum number of replicas of the object as specified by the replication policies for the object;

if the deactivation of the instance of the distributed storage system causes the number of replicas of the object to be below the minimum number of replicas of the object,

generating a replication request to replicate the object based at least in part on replication policies for the object and a current state of the distributed storage system;

distributing the replication request to a respective instance of the distributed storage system for execution; and

generating the replica removal request for the object only after the replication request to replicate the object has been completed.

5. The method of claim 4, 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 are 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.

6. The method of claim 2, wherein a replication policy for an object includes criteria selected from the group consisting of:

a minimum number of replicas of the object that must be present in the distributed storage system;

a maximum number of the replicas of the object that are allowed to be present in the distributed storage system;

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

locations at which the replicas of the object may be stored;

locations at which the 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.

7. The method of claim 2, wherein replica removal requests are generated for an object whose replicas violate replication policies for the object.

8. The method of claim 2, wherein replica removal requests are generated for an object for which dynamic replication requests caused the number of replicas of the object to exceed the number of replicas of the object specified in the replication policies for the object, wherein a dynamic replication request generates a replica of the object based at least in part on a current level of demand for the object.

9. A system for generating and distributing replica removal 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;

generate replica removal requests for objects in a distributed storage system based at least in part on replication policies for the objects, wherein a respective replica removal request instructs a respective instance of the distributed storage system to remove a respective replica of the respective object so as to at least partially satisfy replication policies for the respective object; and

distribute the replica removal requests for the objects in the distributed storage system to respective instances of the distributed storage system corresponding to the replica removal requests for execution.

10. A system for generating and distributing replica removal 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;

identify one or more replicas of the object to be removed from the distributed storage system based at least in part on replication policies for the object;

generate replica removal requests for the one or more replicas of the object, wherein a respective replica removal request instructs a respective instance of the distributed storage system to remove a respective replica of the respective object so as to at least partially satisfy replication policies for the respective object; and

distribute the replica removal requests for the object in the distributed storage system to respective instances of the distributed storage system corresponding to the replica removal requests for execution.

11. The system of claim 10, wherein generating the replica removal requests for the one or more replicas of the object includes:

identifying replication policies for the object that have been violated;

selecting the one or more replicas of the object to be removed from instances of the distributed storage system based at least in part on last access times of replicas of the respective object and the current storage space available at the instances of the distributed storage system including the replicas of the respective object; and

generating the replica removal requests for the one or more selected replica of the respective object.

12. The system of claim 10, wherein generating the replica removal requests for the one or more replicas of the object includes:

determining that an instance of the distributed storage system including the replica of the object is being deactivated;

determining whether the deactivation of the instance of the distributed storage system causes a number of replicas of the object to be below a minimum number of replicas of the object as specified by the replication policies for the object;

if the deactivation of the instance of the distributed storage system causes the number of replicas of the object to be below the minimum number of replicas of the object,

generating a replication request to replicate the object based at least in part on replication policies for the object and a current state of the distributed storage system;

distributing the replication request to a respective instance of the distributed storage system for execution; and

generating the replica removal request for the object only after the replication request to replicate the object has been completed.

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

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

a minimum number of replicas of the object that must be present in the distributed storage system;

a maximum number of the replicas of the object that are allowed to be present in the distributed storage system;

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

locations at which the replicas of the object may be stored;

locations at which the 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.

15. The system of claim 10, wherein replica removal requests are generated for an object whose replicas violate replication policies for the object.

16. The system of claim 10, wherein replica removal requests are generated for an object for which dynamic replication requests caused the number of replicas of the object to exceed the number of replicas of the object specified in the replication policies for the object, wherein a dynamic replication request generates a replica of the object based at least in part on a current level of demand for the object.

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:

generate replica removal requests for objects in a distributed storage system based at least in part on replication policies for the objects, wherein a respective replica removal request instructs a respective instance of the distributed storage system to remove a respective replica of the respective object so as to at least partially satisfy replication policies for the respective object; and

distribute the replica removal requests for the objects in the distributed storage system to respective instances of the distributed storage system corresponding to the replica removal requests for execution.

18. 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:

identify one or more replicas of the object to be removed from the distributed storage system based at least in part on replication policies for the object;

generate replica removal requests for the one or more replicas of the object, wherein a respective replica removal request instructs a respective instance of the distributed storage system to remove a respective replica of the respective object so as to at least partially satisfy replication policies for the respective object; and

distribute the replica removal requests for the object in the distributed storage system to respective instances of the distributed storage system corresponding to the replica removal requests for execution.

19. The computer readable storage medium of claim 18, wherein generating the replica removal requests for the one or more replicas of the object includes:

identifying replication policies for the object that have been violated;

selecting the one or more replicas of the object to be removed from instances of the distributed storage system based at least in part on last access times of replicas of the respective object and the current storage space available at the instances of the distributed storage system including the replicas of the respective object; and

generating the replica removal requests for the one or more selected replica of the respective object.

20. The computer readable storage medium of claim 18, wherein generating the replica removal requests for the one or more replicas of the object includes:

determining that an instance of the distributed storage system including the replica of the object is being deactivated;

determining whether the deactivation of the instance of the distributed storage system causes a number of replicas of the object to be below a minimum number of replicas of the object as specified by the replication policies for the object;

if the deactivation of the instance of the distributed storage system causes the number of replicas of the object to be below the minimum number of replicas of the object,

generating a replication request to replicate the object based at least in part on replication policies for the object and a current state of the distributed storage system;

distributing the replication request to a respective instance of the distributed storage system for execution; and

generating the replica removal request for the object only after the replication request to replicate the object has been completed.

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

22. The computer readable storage medium of claim 18, wherein a replication policy for an object includes criteria selected from the group consisting of:

a minimum number of replicas of the object that must be present in the distributed storage system;

a maximum number of the replicas of the object that are allowed to be present in the distributed storage system;

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

locations at which the replicas of the object may be stored;

locations at which the 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.

23. The computer readable storage medium of claim 18, wherein replica removal requests are generated for an object whose replicas violate replication policies for the object.

24. The computer readable storage medium of claim 18, wherein replica removal requests are generated for an object for which dynamic replication requests caused the number of replicas of the object to exceed the number of replicas of the object specified in the replication policies for the object, wherein a dynamic replication request generates a replica of the object based at least in part on a current level of demand for the object.