Pruning of blob replicas

• US 9,298,736 B2
• Filed: 06/02/2014
• Issued: 03/29/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): Ruiz, Angelica
• Application Number:
  US14/293,966
• Publication Number:
  US 20140304240A1
• Time in Patent Office: 666 Days
• 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 method allocates object replicas in a distributed storage system. The method identifies a plurality of objects in the distributed storage system. Each object has an associated storage policy that specifies a target number of object replicas stored at distinct instances of the distributed storage system. The method identifies an object of the plurality of objects whose number of object replicas exceeds the target number of object replicas specified by the storage policy associated with the object. The method selects a first replica of the object for removal based on last access times for replicas of the object, and transmits a request to a first instance of the distributed storage system that stores the first replica. The request instructs the first instance to remove the first replica of the object.

Claims

1. A method for allocating object replicas 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;

identifying a plurality of objects in the distributed storage system, wherein each object has an associated storage policy that specifies a target number of object replicas stored at distinct instances of the distributed storage system, and wherein each storage policy includes criteria selected from the group consisting of;

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

a desired maximum number of the replicas of the object 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;

identifying an object of the plurality of objects whose number of object replicas exceeds the target number of object replicas specified by the storage policy associated with the object;

selecting a first replica of the object for removal based on last access times for replicas of the object; and

transmitting a request to a first instance of the distributed storage system that stores the first replica, the request instructing the first instance to remove the first replica of the object.

2. The method of claim 1, wherein selecting a first replica of the object for removal is further based on current storage space available at instances of the distributed storage system that store replicas of the object.

3. The method of claim 1, wherein selecting a first replica of the object for removal is further based on a current state of the distributed storage system.

4. The method of claim 3, wherein the current state of the distributed storage system includes a plurality of:

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 the object.

5. The method of claim 1, further comprising before transmitting the request to the first instance of the distributed storage system:

verifying that the replicas of the object that have not been selected for removal exist at corresponding instances.

6. The method of claim 1, further comprising before transmitting the request to the first instance of the distributed storage system:

verifying integrity of the replicas of the object that have not been selected for removal.

7. The method of claim 1, further comprising before transmitting the request to the first instance of the distributed storage system:

verifying that each instance of the distributed storage system that stores a respective replica of the object also stores metadata for the respective replica.

8. The method of claim 1, wherein the storage policy for the object specifies a first target number of replicas for the object having a first data store type, wherein a number of replicas of the object having the first data store type exceeds the first target number, and wherein the first replica is selected for removal based in part on having the first data store type.

9. The method of claim 8, wherein the first data store type is selected from the group consisting of Inline Stores, Big Table Stores, File System Stores, and Tape Stores.

10. A system for allocating object replicas 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;

identifying a plurality of objects in the distributed storage system, wherein each object has an associated storage policy that specifies a target number of object replicas stored at distinct instances of the distributed storage system, and wherein each storage policy 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 the replicas of the object 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;

identifying an object of the plurality of objects whose number of object replicas exceeds the target number of object replicas specified by the storage policy associated with the object;

selecting a first replica of the object for removal based on last access times for replicas of the object; and

transmitting a request to a first instance of the distributed storage system that stores the first replica, the request instructing the first instance to remove the first replica of the object.

11. The system of claim 10, wherein the instructions for selecting a first replica of the object for removal comprise instructions for selecting further based on current storage space available at instances of the distributed storage system that store replicas of the object.

12. The system of claim 10, wherein the instructions for selecting a first replica of the object for removal comprise instructions for selecting further based on a current state of the distributed storage system.

13. The system of claim 12, wherein the current state of the distributed storage system includes a plurality of:

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 the object.

14. The system of claim 10, further comprising verification instructions configured to execute before transmitting the request to the first instance of the distributed storage system, the verification instructions for:

verifying that the replicas of the object that have not been selected for removal exist at corresponding instances.

15. The system of claim 10, further comprising verification instructions configured to execute before transmitting the request to the first instance of the distributed storage system, the verification instructions for:

verifying integrity of the replicas of the object that have not been selected for removal.

16. The system of claim 10, further comprising verification instructions configured to execute before transmitting the request to the first instance of the distributed storage system, the verification instructions for:

verifying that each instance of the distributed storage system that stores a respective replica of the object also stores metadata for the respective replica.

17. The system of claim 10, wherein the storage policy for the object specifies a first target number of replicas for the object having a first data store type, wherein a number of replicas of the object having the first data store type exceeds the first target number, and wherein the instructions for selecting the first replica for removal comprise instructions for selecting the first replica based in part on the first replica having the first data store type.

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 for:

identifying a plurality of objects in the distributed storage system, wherein each object has an associated storage policy that specifies a target number of object replicas stored at distinct instances of the distributed storage system, and wherein each storage policy 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 the replicas of the object 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;

identifying an object of the plurality of objects whose number of object replicas exceeds the target number of object replicas specified by the storage policy associated with the object;

selecting a first replica of the object for removal based on last access times for replicas of the object; and

transmitting a request to a first instance of the distributed storage system that stores the first replica, the request instructing the first instance to remove the first replica of the object.