Distributed storage system with replica location selection

• US 10,346,425 B2
• Filed: 07/01/2016
• Issued: 07/09/2019
• Est. Priority Date: 07/02/2015
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Shraer, Alexander, Merchant, Arif Abdulhusein, Sharov, Artyom, Cooper, Brian F.
• Primary Examiner(s): Chea, Philip J
• Assistant Examiner(s): Ma, Wing
• Application Number:
  US15/200,743
• Publication Number:
  US 20170006105A1
• Time in Patent Office: 1,103 Days
• Field of Search: 709205
• CPC Class Codes: G06F 16/25 Integrating or interfacing systems involving database management systems
• 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 16/955 using information identifiers, e.g. uniform resource locators [URL]
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/1025 Dynamic adaptation of the criteria on which the server selection is based
• 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]
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal

Abstract

Replicas are selected in a large distributed network, and the roles for these replicas are identified. In one example, an indication that a number N of clusters are to be assigned a replica role and a second number M of the replica-role assigned clusters are to be assigned to a voting role. N computing clusters are selected using workload data, and M of the clusters are assigned to a voting role.

Claims

1. A system comprising:

a plurality of computing clusters each comprising computer memory and a computer processor;

a distributed database running on at least a subset of the plurality of the computing clusters and that interacts with a client application running on a client computer, the distributed database configured to;

store data of the distributed database in shards distributed among computing clusters of the distributed database; and

use each computing cluster of the computing clusters of the distributed database according to a respective role assigned to the computing cluster that identifies functions of the computing cluster; and

an activity monitor service configured to;

monitor interactions between the client application and the distributed database;

generate, from the monitoring of the interactions between the client application and the distributed database, historical workload data describing historical interactions that have occurred between the client application and the distributed database; and

a task assigning service configured to;

receive an indication that a first number (N) of the computing clusters are to be assigned to a replica role of the distributed database;

receive an indication that a second number (M) of the replica-role assigned computing clusters are to be assigned as a subset of the first number (N) of the computer clusters to a voting role of the distributed database;

select, using the historical workload data describing interactions that have occurred between the client application and the distributed database, N computing clusters to be included in the distributed database;

assign the N selected computing clusters to a replica role within the distributed database; and

assign M of the selected subset of computing clusters to a voting role within the distributed database.

2. The system of claim 1, wherein the task assigning service is configured to repeat the selecting of, using the historical workload data, N computing clusters to be included in the distributed database;

the assigning of N of the selected computing clusters to a replica role within the distributed database; and

the assigning of M of the selected computing clusters to a voting role within the distributed database.

3. The system of claim 2, wherein the repeating is on a schedule that is based on cyclical changes in usages of the computing clusters.

4. The system of claim 1, wherein to receive an indication that the N of the computing clusters are to be assigned to a replica role of the distributed database, the task assigning service is configured to determine a count of voters required for a quorum of voters.

5. The system of claim 1, wherein to assign N of the selected computing clusters to a replica role within the distributed database, the task assigning service is configured to select N computing clusters based on a location of a computing cluster assigned to a leader role in the distributed database.

6. A method comprising:

monitoring interactions between a client application and a distributed database;

generating from the monitoring of the interactions between the client application and the distributed database, historical workload data describing historical interactions that have occurred between the client application and the distributed database;

receive an indication that a first number (N) of the computing clusters are to be assigned to a replica role of the distributed database;

receive an indication that a second number (M) of the replica-role assigned computing clusters are to be assigned as a subset of the first number (N) of the computer clusters to a voting role of the distributed database;

select, using the historical workload data describing interactions that have occurred between the client application and the distributed database, N computing clusters to be included in the distributed database;

assign the N selected computing clusters to a replica role within the distributed database; and

assign M of the selected subset of computing clusters to a voting role within the distributed database.

7. The method of claim 6, the method further comprising repeating the selecting of, using the historical workload data, N computing clusters to be included in the distributed database;

the assigning of N of the selected computing clusters to a replica role within the distributed database; and

the assigning of M of the selected computing clusters to a voting role within the distributed database.

8. The method of claim 7, wherein the repeating is on a schedule that is based on cyclical changes in usages of the computing clusters.

9. The method of claim 6, wherein receiving an indication that a second number (N) of the computing clusters are to be assigned to a replica role of the distributed database comprises determining a count of voters required for a quorum of voters.

10. The method of claim 6, wherein assigning N of the selected computing clusters to a replica role within the distributed database comprises selecting N computing clusters based on a location of a computing cluster assigned to a leader role in the distributed database.

11. A system comprising:

a plurality of computing clusters each comprising computer memory and a computer processor;

a distributed database running on at least a subset of the plurality of the computing clusters and that interacts with a client application running on a client computer, the distributed database configured to;

store data of the distributed database in shards distributed among computing clusters of the distributed database; and

use each computing cluster of the computing clusters of the distributed database according to a respective role assigned to the computing cluster that identifies functions of the computing cluster; and

an activity monitor service configured to;

monitor interactions between the client application and the distributed database;

generate, from the monitoring of the interactions between the client application and the distributed database, workload data describing the interactions between the client application and the distributed database; and

a task assigning service configured to;

receive an indication that a number (M) of the computing clusters are to be assigned to a voting role of the distributed database;

for each particular computer cluster of at least some of the computer clusters;

consider the particular computing cluster as a candidate leader;

identify, using the workload data, (M+1)/2 computer clusters having (M+1)/2 lowest latencies with the particular computing cluster as voters corresponding to the candidate leader;

identify M−

(M+1)/2 unidentified computing clusters as voters corresponding to the candidate leader;

identify a number (N) of unidentified computing clusters as replicas corresponding to the candidate leader;

select the candidate leader computing cluster, corresponding voters, and corresponding replicas having a best score on a metric;

assigning, to the selected candidate computer cluster, a leader role within the distributed database;

assigning, to the selected M computer clusters, the voting role within the distributed database; and

assigning, to the selected N computer clusters, the replica role within the distributed database.

12. The system of claim 11, wherein the task assigning service is configured to repeat the considering of the particular computing cluster as a candidate leader, the identifying, using the workload data, (M+1)/2 computer clusters having (M+1)/2 lowest latencies with the particular computing cluster as voters corresponding to the candidate leader, the identifying M−

(M+1)/2 unidentified computing clusters as voters corresponding to the candidate leader, the identifying a number (N) of unidentified computing clusters as replicas corresponding to the candidate leader, the selecting the candidate leader computing cluster, corresponding voters, and corresponding replicas having a best score on a metric, the assigning, to the selected candidate computer cluster, the leader role within the distributed database, the assigning, to the selected M computer clusters, the voting role within the distributed database, and the assigning, to the selected N computer clusters, the replica role within the distributed database.

13. The system of claim 12, wherein the repeating is on a schedule that is based on cyclical changes in usage of the computing clusters.

14. The system of claim 11, wherein to identify a number (N) of unidentified computing clusters as replicas corresponding to the candidate leader, the task assigning service is configured to determine a count of voters required for a quorum of voters.

15. The system of claim 11 wherein to identify a number (N) of unidentified computing clusters as replicas corresponding to the candidate leader, the task assigning service is configured to select N computing clusters based on a location of a client computer.

16. A method comprising:

monitoring interactions between a client application and a distributed database;

generating from the monitoring of the interactions between the client application and the distributed database, workload data describing the interactions between the client application and the distributed database;

receiving an indication that a number (M) of the computing clusters are to be assigned to a voting role of the distributed database;

for each particular computer cluster of at least some of the computer clusters;

considering the particular computing cluster as a candidate leader;

identifying, using the workload data, (M+1)/2 computer clusters having (M+1)/2 lowest latencies with the particular computing cluster as voters corresponding to the candidate leader;

identifying M−

(M+1)/2 unidentified computing clusters as voters corresponding to the candidate leader;

identifying a number (N) of unidentified computing clusters as replicas corresponding to the candidate leader;

selecting the candidate leader computing cluster, corresponding voters, and corresponding replicas having a best score on a metric;

assigning, to the selected candidate computer cluster, a leader role within the distributed database;

assigning, to the selected M computer clusters, the voting role within the distributed database; and

assigning, to the selected N computer clusters, the replica role within the distributed database.

17. The method of claim 16, the method further comprising repeating the considering of the particular computing cluster as a candidate leader, the identifying, using the workload data, (M+1)/2 computer clusters having (M+1)/2 lowest latencies with the particular computing cluster as voters corresponding to the candidate leader, the identifying M−

(M+1)/2 unidentified computing clusters as voters corresponding to the candidate leader, the identifying a number (N) of unidentified computing clusters as replicas corresponding to the candidate leader, the selecting the candidate leader computing cluster, corresponding voters, and corresponding replicas having a best score on a metric, the assigning, to the selected candidate computer cluster, the leader role within the distributed database, the assigning, to the selected M computer clusters, the voting role within the distributed database, and the assigning, to the selected N computer clusters, the replica role within the distributed database.

18. The method of claim 17, wherein the repeating is on a schedule that is based on cyclical changes in usage of the computing clusters.

19. The method of claim 16, the method further comprising determining a count of voters required for a quorum of voters.

20. The method of claim 16, the method further comprising selecting N computing clusters based on a location of a client computer.