Storage of data in a distributed storage system

• US 8,868,508 B2
• Filed: 02/08/2011
• Issued: 10/21/2014
• Est. Priority Date: 02/09/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Drobychev, Alexandre, Kesselman, Alexander, Vickrey, Rebekah C., Dachille, Frank C., Datuashvili, George
• Primary Examiner(s): Ehichioya, Fred I
• Assistant Examiner(s): MENG, JAU SHYA
• Application Number:
  US13/023,503
• Publication Number:
  US 20110196833A1
• Time in Patent Office: 1,351 Days
• Field of Search: None
• US Class Current: 707/652
• CPC Class Codes: G06F 16/122 using management policies backup systems G06F11/1446; file migration policies for HSM systems G06F16/185
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/248 Presentation of query results
• 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
• CPC Class Codes: G06F 3/065 Replication mechanisms

Abstract

A distributed storage system has multiple instances. There is a plurality of local instances, and at least some of the local instances are at physically distinct geographic locations. Each local instance is configured to store data for a non-empty set of blobs in a plurality of data stores having a plurality of distinct data store types. In addition, each local instance stores metadata for the respective set of blobs in a metadata store distinct from the data stores. There is also a plurality of global instances. Each global instance is configured to store data for zero or more blobs in zero or more data stores and store metadata for all blobs stored at any local or global instance. The system selects one global instance to run a replication module that replicates blobs between instances according to blob policies.

Claims

1. A distributed storage system for storing blobs, comprising:

a plurality of instances, wherein each respective instance includes a plurality of server computers having memory and one or more processors storing one or more programs for execution by the one or more processors, and wherein at least a subset of the instances are at physically distinct geographic locations;

wherein a respective instance stores data for a plurality of blobs; and

wherein each respective blob has corresponding metadata that includes information that identifies a set of one or more instances where the respective blob is stored and includes a blob placement policy that specifies the desired number of copies of the respective blob as well as the desired locations for copies of the respective blob; and

a location assignment module configured to;

compare the desired number of copies of each respective blob and the desired locations for copies of the respective blob, as specified in the respective blob placement policy for the respective blob, to a current number of copies of the respective blob and current locations of copies of the respective blob; and

issue commands to delete a copy of the respective blob or to replicate the respective blob to another instance in response to determining that the current number of copies of the respective blob is inconsistent with the desired number of copies of the respective blob or the current locations of the respective blob are inconsistent with the desired locations for copies of the respective blob, as specified in the respective blob placement policy for the respective blob.

2. The distributed storage system of claim 1, wherein one or more blob placement policies further specify data store type requirements of blob replicas.

3. The distributed storage system of claim 1, wherein a respective instance further comprises a first replication module that dynamically replicates blobs from one instance to another instance based on user requests to access blobs that are not stored at an instance near the user.

4. The distributed storage system of claim 2, wherein the data store types include inline data stores, BigTable data stores, file system data stores, and tape data stores.

5. A method, comprising:

at a server having one or more processors and memory storing programs configured for execution by the one or more processors to manage storage of blobs in a distributed storage system, wherein the distributed storage system includes a plurality of instances, at least a subset of the instances are at physically distinct geographic locations, each respective instance stores data for a plurality of blobs, and each respective blob has corresponding metadata that includes information that identifies a set of one or more instances where the respective blob is stored and includes a blob placement policy that specifies the desired number of copies of the respective blob as well as the desired locations for copies of the respective blob;

comparing the desired number of copies of each respective blob and the desired locations for copies of the respective blob, as specified in the respective blob placement policy for the respective blob, to a current number of copies of the respective blob and current locations of copies of the respective blob; and

issue commands to delete a copy of the respective blob or to replicate the respective blob to another instance in response to determining that the current number of copies of the respective blob is inconsistent with the desired number of copies of the respective blob or the current locations of the respective blob are inconsistent with the desired locations for copies of the respective blob, as specified in the respective blob placement policy for the respective blob.

6. The method of claim 5, wherein one or more blob placement policies further specify data store type requirements of blob replicas.

7. The distributed storage system of claim 6, wherein the data store types include inline data stores, BigTable data stores, file system data stores, and tape data stores.

8. The distributed storage system of claim 5, further comprising dynamically replicating a first blob from one instance to another instance based on a user request to access the first blob, wherein the first blob is not stored at an instance near the user.

9. A non-transitory computer readable storage medium storing one or more programs configured for execution by a server having one or more processors and memory, the one or more programs comprising instructions for:

managing storage of blobs in a distributed storage system, wherein the distributed storage system includes a plurality of instances, at least a subset of the instances are at physically distinct geographic locations, each respective instance stores data for a plurality of blobs, and each respective blob has corresponding metadata that includes information that identifies a set of one or more instances where the respective blob is stored and includes a blob placement policy that specifies the desired number of copies of the respective blob as well as the desired locations for copies of the respective blob; and

wherein managing storage of the blobs includes;

comparing the desired number of copies of each respective blob and the desired locations for copies of the respective blob, as specified in the respective blob placement policy for the respective blob, to a current number of copies of the respective blob and current locations of copies of the respective blob; and

issuing commands to delete a copy of the respective blob or to replicate the respective blob to another instance in response to determining that the current number of copies of the respective blob is inconsistent with the desired number of copies of the respective blob or the current locations of the respective blob are inconsistent with the desired locations for copies of the respective blob, as specified in the respective blob placement policy for the respective blob.

10. The computer readable storage medium of claim 9, wherein one or more blob placement policies further specify data store type requirements of blob replicas.

11. The computer readable storage medium of claim 10, wherein the data store types include inline data stores, BigTable data stores, file system data stores, and tape data stores.

12. The computer readable storage medium of claim 9, wherein the one or more programs further comprise instructions for dynamically replicating a first blob from one instance to another instance based on a user request to access the first blob, wherein the first blob is not stored at an instance near the user.