System and method for storing metadata for a file in a distributed storage system

• US 9,330,107 B1
• Filed: 02/06/2013
• Issued: 05/03/2016
• Est. Priority Date: 02/08/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kesselman, Alexander, Broyde, Dmitry, O'Reilly, Michael, Lees, Angus
• Primary Examiner(s): Wilson, Kimberly
• Assistant Examiner(s): Santos, Pedro J
• Application Number:
  US13/761,115
• Time in Patent Office: 1,182 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/182 Distributed file systems

Abstract

A system, computer-readable storage medium storing at least one program, and a computer-implemented method for storing metadata for a file in a distributed storage system is presented. Metadata for a file is generated. A subset of metadata clusters in a distributed storage system is identified to form a quorum of metadata clusters. Requests to store the metadata for the file on the metadata clusters in the distributed storage system are issued, where the requests include high priority requests to store the metadata for the file on at least one of the metadata clusters in the quorum of metadata clusters and normal priority requests to store the metadata in the remaining metadata clusters, the metadata being stored on the at least one of the metadata clusters in the quorum of metadata clusters before being stored on the remaining metadata clusters.

Claims

1. A computer-implemented method for storing metadata for a file in a distributed storage system, performed on a server having at least one processor and memory storing at least one program for execution by the at least one processor to perform the method, comprising:

after the file has been uploaded to at least one storage cluster in the distributed storage system;

generating metadata for the uploaded file, the metadata for the uploaded file including information identifying at least one location of the uploaded file in the at least one storage cluster in the distributed storage system;

identifying a subset of metadata clusters in the distributed storage system to form a quorum of metadata clusters, wherein the subset of metadata clusters forming the quorum includes one or more metadata clusters selected from one or more geographical regions associated with the metadata clusters in the distributed storage system; and

issuing requests to store the metadata for the uploaded file on the metadata clusters in the distributed storage system, the requests including high priority requests and normal priority requests, wherein the high priority requests are requests to store the metadata for the uploaded file on at least one of the metadata clusters in the quorum of metadata clusters, and the normal priority requests are requests to store the metadata in the remaining metadata clusters,

the metadata being stored on the at least one of the metadata clusters in the quorum of metadata clusters before being stored on the remaining metadata clusters in accordance with the high priority requests, such that in response to a request to obtain the uploaded file, the location of the uploaded file in the at least one storage cluster in the distributed storage system can be identified from the metadata stored on the at least one of the metadata clusters in the quorum of metadata clusters.

2. The computer-implemented method of claim 1, wherein prior to generating the metadata for the file, the method includes:

receiving a file from a client computer system; and

storing the file in the at least one storage cluster in the distributed storage system.

3. The computer-implemented method of claim 1, further comprising:

receiving a first request to obtain the file from the distributed storage system;

obtaining the metadata for the file from the at least one of the metadata clusters in the quorum of metadata clusters;

identifying the at least one location of the file in the at least one storage clusters based on the metadata for the file; and

obtaining the file from the at least one location of the file in the at least one storage clusters.

4. The computer-implemented method of claim 1, wherein identifying the subset of metadata clusters in the distributed storage system to form the quorum of metadata clusters includes:

grouping the metadata clusters into failure domains, a respective failure domain including metadata clusters that are likely to be concurrently unavailable;

identifying a set of the failure domains based on a first function of a hash value of an object identifier for the file, wherein the set of failure domains includes metadata clusters that are available; and

identifying metadata clusters to be included in the subset of the metadata clusters from the set of the failure domains based on a second function of the hash value of the object identifier for the file.

5. The computer-implemented method of claim 4, wherein identifying the set of the failure domains based on the first function of the hash of the object identifier for the file includes:

calculating a first index value as the hash value of the object identifier for the file modulo a number of failure domains in the distributed storage system; and

identifying the set of failure domains as the s consecutive failure domains that include available metadata clusters starting with the failure domain associated with the first index value, wherein s is a desired number of metadata clusters in the quorum of metadata clusters, and wherein each failure domain is associated with a respective index value.

6. The computer-implemented method of claim 4, wherein identifying metadata clusters to be included in the subset of the metadata clusters from the set of the failure domains based on the second function of the hash value of the object identifier for the file includes:

for each failure domain in the set of failure domains,

calculating a second index value as the hash value of the object identifier for the file modulo a number of metadata clusters in the failure domain; and

identifying an available metadata cluster in the failure domain that is associated with the second index value, wherein the available metadata cluster is included in the subset of the metadata clusters.

7. The computer-implemented method of claim 1, wherein identifying the subset of metadata clusters in the distributed storage system to form the quorum of metadata clusters includes:

grouping the metadata clusters into the one or more geographical regions; and

for each geographic region of the one or more geographical regions, identifying a set of metadata clusters in the geographic region to be included in the subset of the metadata clusters based on a third function of the hash value of the object identifier for the file.

8. The computer-implemented method of claim 7, wherein identifying a respective set of metadata clusters in a respective geographic region to be included in the subset of the metadata clusters based on the third function of the hash value of the object identifier for the file includes:

calculating a third index value as the hash value of the object identifier for the file modulo a number of metadata clusters in the respective geographic region; and

identifying the respective set of metadata clusters the respective geographic region as the s consecutive available metadata clusters in the respective geographic region starting with the metadata cluster associated with the third index value, wherein s is a desired number of metadata clusters in the quorum of metadata clusters for the respective geographic region, and wherein each metadata cluster in the respective geographic region is associated with a respective index value.

9. The computer-implemented method of claim 1, wherein identifying the subset of metadata clusters in the distributed storage system to form the quorum of metadata clusters includes:

grouping the metadata clusters into geographical regions;

for each geographic region,

identifying primary metadata clusters and backup metadata clusters, wherein the primary metadata clusters include metadata clusters from different failure domains, wherein the backup metadata clusters include metadata clusters from different failure domains, and wherein a respective failure domain includes metadata clusters that are likely to be concurrently unavailable;

identifying x available metadata clusters in the primary metadata clusters, where x is less than or equal to a desired number, y, of metadata servers in the quorum of metadata servers for the geographic region; and

identifying y−

x available metadata clusters in the backup metadata clusters; and

identifying the subset of metadata clusters as a union of the identified available metadata clusters.

10. The computer-implemented method of claim 1, wherein storing the file in the at least one storage cluster includes:

partitioning the file into a plurality of chunks; and

storing the plurality of chunks in the at least one storage cluster in a distributed storage system.

11. The computer-implemented method of claim 1, wherein the file is stored asynchronously on the at least one storage cluster.

12. A system to store metadata for a file in a distributed storage system, comprising:

at least one processor;

memory; and

at least one program stored in the memory and executable by the at least one processor, the at least one program comprising instructions to;

after the file has been uploaded to at least one storage cluster in the distributed storage system;

generate metadata for the uploaded file, the metadata for the uploaded file including information identifying at least one location of the uploaded file in the at least one storage cluster in the distributed storage system;

identify a subset of metadata clusters in the distributed storage system to form a quorum of metadata clusters, wherein the subset of metadata clusters forming the quorum includes one or more metadata clusters selected from one or more geographical regions associated with the metadata clusters in the distributed storage system; and

issue requests to store the metadata for the uploaded file on the metadata clusters in the distributed storage system, the requests including high priority requests and normal priority requests, wherein the high priority requests are requests to store the metadata for the uploaded file on at least one of the metadata clusters in the quorum of metadata clusters, and the normal priority requests are requests to store the metadata in the remaining metadata clusters,

the metadata being stored on the at least one of the metadata clusters in the quorum of metadata clusters before being stored on the remaining metadata clusters in accordance with the high priority requests, such that in response to a request to obtain the uploaded file, the location of the uploaded file in the at least one storage cluster in the distributed storage system can be identified from the metadata stored on the at least one of the metadata clusters in the quorum of metadata clusters.

13. The system of claim 12, wherein prior to generating the metadata for the file, the at least one program includes instructions to:

receive a file from a client computer system; and

store the file in the at least one storage cluster in the distributed storage system.

14. The system of claim 12, further comprising instructions to:

receive a first request to obtain the file from the distributed storage system;

obtain the metadata for the file from the at least one of the metadata clusters in the quorum of metadata clusters;

identify the at least one location of the file in the at least one storage clusters based on the metadata for the file; and

obtain the file from the at least one location of the file in the at least one storage clusters.

15. The system of claim 12, wherein the instructions to identify the subset of metadata clusters in the distributed storage system to form the quorum of metadata clusters include instructions to:

group the metadata clusters into failure domains, a respective failure domain including metadata clusters that are likely to be concurrently unavailable;

identify a set of the failure domains based on a first function of a hash value of an object identifier for the file, wherein the set of failure domains includes metadata clusters that are available; and

identify metadata clusters to be included in the subset of the metadata clusters from the set of the failure domains based on a second function of the hash value of the object identifier for the file.

16. The system of claim 15, wherein the instructions to identify the set of the failure domains based on the first function of the hash of the object identifier for the file include instructions to:

calculate a first index value as the hash value of the object identifier for the file modulo a number of failure domains in the distributed storage system; and

identify the set of failure domains as the s consecutive failure domains that include available metadata clusters starting with the failure domain associated with the first index value, wherein s is a desired number of metadata clusters in the quorum of metadata clusters, and wherein each failure domain is associated with a respective index value.

17. The system of claim 15, wherein the instructions to identify metadata clusters to be included in the subset of the metadata clusters from the set of the failure domains based on the second function of the hash value of the object identifier for the file include instructions to:

for each failure domain in the set of failure domains,

calculate a second index value as the hash value of the object identifier for the file modulo a number of metadata clusters in the failure domain; and

identify an available metadata cluster in the failure domain that is associated with the second index value, wherein the available metadata cluster is included in the subset of the metadata clusters.

18. The system of claim 12, wherein the instructions to identify the subset of metadata clusters in the distributed storage system to form the quorum of metadata clusters include instructions to:

group the metadata clusters into the one or more geographical regions; and

for each geographic region of the one or more geographical regions, identify a set of metadata clusters in the geographic region to be included in the subset of the metadata clusters based on a third function of the hash value of the object identifier for the file.

19. The system of claim 18, wherein the instructions to identify a respective set of metadata clusters in a respective geographic region to be included in the subset of the metadata clusters based on the third function of the hash value of the object identifier for the file include instructions to:

calculate a third index value as the hash value of the object identifier for the file modulo a number of metadata clusters in the respective geographic region; and

identify the respective set of metadata clusters the respective geographic region as the s consecutive available metadata clusters in the respective geographic region starting with the metadata cluster associated with the third index value, wherein s is a desired number of metadata clusters in the quorum of metadata clusters for the respective geographic region, and wherein each metadata cluster in the respective geographic region is associated with a respective index value.

20. The system of claim 12, wherein the instructions to identify the subset of metadata clusters in the distributed storage system to form the quorum of metadata clusters include instructions to:

group the metadata clusters into geographical regions;

for each geographic region,

identify primary metadata clusters and backup metadata clusters, wherein the primary metadata clusters include metadata clusters from different failure domains, wherein the backup metadata clusters include metadata clusters from different failure domains, and wherein a respective failure domain includes metadata clusters that are likely to be concurrently unavailable;

identify x available metadata clusters in the primary metadata clusters, where x is less than or equal to a desired number, y, of metadata servers in the quorum of metadata servers for the geographic region; and

identify y−

x available metadata clusters in the backup metadata clusters; and

identify the subset of metadata clusters as a union of the identified available metadata clusters.

21. The system of claim 12, wherein the instructions to store the file in the at least one storage cluster include instructions to:

partition the file into a plurality of chunks; and

store the plurality of chunks in the at least one storage cluster in a distributed storage system.

22. The system of claim 12, wherein the file is stored asynchronously on the at least one storage cluster.

23. A non-transitory computer readable storage medium storing at least one program configured for execution by at least one processor of a computer system, the at least one program comprising instructions to:

after the file has been uploaded to at least one storage cluster in the distributed storage system;

generate metadata for the uploaded file, the metadata for the uploaded file including information identifying at least one location of the uploaded file in the at least one storage cluster in the distributed storage system;

identify a subset of metadata clusters in the distributed storage system to form a quorum of metadata clusters, wherein the subset of metadata clusters forming the quorum includes one or more metadata clusters selected from one or more geographical regions associated with the metadata clusters in the distributed storage system; and

issue requests to store the metadata for the uploaded file on the metadata clusters in the distributed storage system, the requests including high priority requests and normal priority requests, wherein the high priority requests are requests to store the metadata for the uploaded file on at least one of the metadata clusters in the quorum of metadata clusters, and the normal priority requests are requests to store the metadata in the remaining metadata clusters,

the metadata being stored on the at least one of the metadata clusters in the quorum of metadata clusters before being stored on the remaining metadata clusters in accordance with the high priority requests, such that in response to a request to obtain the uploaded file, the location of the uploaded file in the at least one storage cluster in the distributed storage system can be identified from the metadata stored on the at least one of the metadata clusters in the quorum of metadata clusters.