Storage of data in a distributed storage system

• US 9,747,322 B2
• Filed: 10/03/2014
• Issued: 08/29/2017
• 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): MENG, JAU SHYA
• Application Number:
  US14/506,530
• Publication Number:
  US 20150026128A1
• Time in Patent Office: 1,061 Days
• Field of Search: None
• 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. Some systems also include dynamic replication based on user needs.

Claims

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

a plurality of local instances, wherein each respective local 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 local instances are at physically distinct geographic locations; and

a plurality of global instances distinct from the local instances, wherein each respective global 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;

wherein each blob stored in the distributed storage system has corresponding metadata, and wherein the metadata includes information identifying a set of one or more local instances or global instances where the respective blob is stored;

wherein each respective local instance;

stores data for a respective set of blobs in a plurality of data stores having a plurality of distinct data store types, wherein the respective set of blobs is non-empty and is a subset of all blobs stored in the distributed storage system; and

stores the metadata for the respective set of blobs in a metadata store distinct from the data stores;

wherein each respective global instance stores the metadata for all blobs stored at all local instances; and

wherein one global instance has a location assignment daemon, and wherein for each blob the location assignment daemon;

determines locations of respective local instances currently storing replicas of the blob;

determines a number of target replica locations for the blob according to a respective placement policy assigned to the blob; and

upon determining the respective local instances currently storing replicas of the blob are fewer than the target number of replica locations, issuing a replication command to a first local instance to create a new replica of the blob at a second instance in accordance with the respective placement policy.

2. The distributed storage system of claim 1, wherein one or more blobs in a respective non-empty set of blobs at a local instance are replicas of blobs stored at a global instance.

3. The distributed storage system of claim 1, wherein blob placement policies specify a minimum number of blob replicas and/or location constraints of blob replicas and/or data store type requirements of blob replicas.

4. The distributed storage system of claim 1, wherein a respective local or global instance further comprises a first replication module, and wherein the first replication module dynamically replicates blobs from one local or global instance to another local or global instance based on user requests to access blobs not stored at a local or global instance near the user.

5. The distributed storage system of claim 1, wherein the data store types include BigTable data stores, file system data stores, and tape data stores.

6. A method, comprising:

at a server having one or more processors and memory storing programs configured for execution by the one or more processors;

managing storage of blobs in a distributed storage system;

wherein the distributed storage system includes a plurality of local instances, wherein each respective local instance includes a plurality of server computers, each 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 local instances are at physically distinct geographic locations;

wherein the distributed storage system includes a plurality of global instances distinct from the local instances, wherein each respective global 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;

wherein each blob stored in the distributed storage system has corresponding metadata, and wherein the metadata includes information identifying a set of one or more local instances or global instances where the respective blob is stored;

wherein each respective local instance;

stores data for a respective set of blobs in a plurality of data stores having a plurality of distinct data store types, wherein the respective set of blobs is non-empty and is a subset of all blobs stored in the distributed storage system; and

stores the metadata for the respective set of blobs in a metadata store distinct from the data stores;

wherein each respective global instance stores the metadata for all blobs stored at all local instances; and

wherein one global instance has a location assignment daemon, and wherein for each blob the location assignment daemon;

determines locations of respective local instances currently storing replicas of the blob;

determines a number of target replica locations for the blob according to a respective placement policy assigned to the blob; and

upon determining the respective local instances currently storing replicas of the blob are fewer than the target number of replica locations, issuing a replication command to a first local instance to create a new replica of the blob at a second instance in accordance with the respective placement policy.

7. The method of claim 6, wherein one or more blobs in a respective non-empty set of blobs at a local instance are replicas of blobs stored at a global instance.

8. The method of claim 6, wherein blob placement policies specify a minimum number of blob replicas and/or location constraints of blob replicas and/or data store type requirements of blob replicas.

9. The method of claim 6, wherein a respective local or global instance further comprises a first replication module, and wherein the first replication module dynamically replicates blobs from one local or global instance to another local or global instance based on user requests to access blobs not stored at a local or global instance near the user.

10. The method of claim 6, wherein the data store types include BigTable data stores, file system data stores, and tape data stores.

11. 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 to perform:

managing storage of blobs in a distributed storage system;

wherein the distributed storage system includes a plurality of local instances, wherein each respective local instance includes a plurality of server computers, each 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 local instances are at physically distinct geographic locations;

wherein the distributed storage system includes a plurality of global instances distinct from the local instances, wherein each respective global 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;

wherein each blob stored in the distributed storage system has corresponding metadata, and wherein the metadata includes information identifying a set of one or more local instances or global instances where the respective blob is stored;

wherein each respective local instance;

stores data for a respective set of blobs in a plurality of data stores having a plurality of distinct data store types, wherein the respective set of blobs is non-empty and is a subset of all blobs stored in the distributed storage system; and

stores the metadata for the respective set of blobs in a metadata store distinct from the data stores;

wherein each respective global instance stores the metadata for all blobs stored at all local instances; and

wherein one global instance has a location assignment daemon, and wherein for each blob the location assignment daemon;

determines locations of respective local instances currently storing replicas of the blob;

determines a number of target replica locations for the blob according to a respective placement policy assigned to the blob; and

upon determining the respective local instances currently storing replicas of the blob are fewer than the target number of replica locations, issuing a replication command to a first local instance to create a new replica of the blob at a second instance in accordance with the respective placement policy.

12. The computer readable storage medium of claim 11, wherein one or more blobs in a respective non-empty set of blobs at a local instance are replicas of blobs stored at a global instance.

13. The computer readable storage medium of claim 11, wherein blob placement policies specify a minimum number of blob replicas and/or location constraints of blob replicas and/or data store type requirements of blob replicas.

14. The computer readable storage medium of claim 11, wherein a respective local or global instance further comprises a first replication module, and wherein the first replication module dynamically replicates blobs from one local or global instance to another local or global instance based on user requests to access blobs not stored at a local or global instance near the user.

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