System and method for managing load in a distributed storage system

• US 10,009,250 B2
• Filed: 05/27/2016
• Issued: 06/26/2018
• Est. Priority Date: 02/09/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Drobychev, Alexandre, Kesselman, Alexander, Datuashvili, George
• Primary Examiner(s): Meky, Moustafa M
• Assistant Examiner(s): Waugh, Thorne E
• Application Number:
  US15/167,944
• Publication Number:
  US 20160277275A1
• Time in Patent Office: 760 Days
• Field of Search: 709203-248
• 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: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• 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]
• CPC Class Codes: H04L 67/60 Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources admission control or resource allocation H04L47/70

Abstract

The various embodiments described herein include methods, systems, and devices for managing load in a distributed storage system. In one aspect, a method is performed at a first instance server in the distributed storage system, the first instance server having memory and at least one processor coupled to the memory. The method includes: (i) issuing a first plurality of requests to a second instance server; (ii) obtaining one or more messages from the second instance server in response to the first plurality of requests, the messages indicating a utilization rate of the second instance server; (iii) determining a transaction rate limit for the second instance server based on the utilization rate of the second instance server; and (iv) issuing a second plurality of requests to the second instance server, where the second plurality of requests are issued at a rate no greater than the transaction rate limit.

Claims

1. A computer-implemented method for managing load in a distributed storage system, comprising:

at a first instance server in the distributed storage system, the first instance server having memory and at least one processor coupled to the memory;

issuing a first plurality of transactional requests to a second instance server, the first plurality of transactional requests for creating, modifying, or deleting objects within the distributed storage system;

obtaining one or more messages from the second instance server in response to the first plurality of transactional requests, the one or more messages indicating a utilization rate of the second instance server;

determining a transaction rate limit for the second instance server based on the utilization rate of the second instance server; and

issuing a second plurality of transactional requests to the second instance server, wherein the second plurality of transactional requests are issued at a rate no greater than the transaction rate limit.

2. The method of claim 1, wherein determining the transaction rate limit for the second instance server comprises:

determining at least one percentage of the messages received over at least one predetermined time interval that include a pushback signal; and

determining the transaction rate limit based on the at least one percentage.

3. The method of claim 2, wherein the at least one percentage includes a first percentage of the messages received over a first predetermined time interval that include the pushback signal and a second percentage of the messages over a second predetermined time interval that include the pushback signal, wherein determining the transaction rate limit based on the at least one percentage includes:

determining that the first percentage is below a first predetermined threshold and that the second percentage is below a second predetermined threshold; and

responsive to the determining, increasing the transaction rate limit.

4. The method of claim 2, wherein the transaction rate limit is increased in accordance with a determination that a predetermined amount of time has elapsed since a prior increase to the transaction rate limit.

5. The method of claim 2, wherein at least one percentage includes a first percentage of the messages received over a first predetermined time interval that include the pushback signal and a second percentage of the messages over a second predetermined time interval that include the pushback signal, wherein adjusting the transaction rate limit based on the at least one percentage includes:

determining that the first percentage is above a first predetermined threshold or that the second percentage is above a second predetermined threshold; and

responsive to the determining, decreasing the transaction rate limit.

6. The method of claim 1, wherein at least one request of the plurality of transactional requests is issued in accordance with an object replication policy.

7. The method of claim 6, wherein the object replication policy corresponds to an object to be stored by the at least one request and the object replication policy specifies at least one of:

the number of object replications to be stored;

the type of data stores to be used for storage of the object replications; and

locations within the distributed storage system where the object replications are to be stored.

8. The method of claim 6, wherein the object replication policy is stored in a global configuration file for the distributed storage system.

9. The method of claim 1, wherein the first instance server includes a number of processes that are issuing transactional requests to the second instance server, and the method includes, prior to issuing the plurality of transactional requests to the second instance server:

identifying a maximum transaction rate of the second instance server; and

for each process on the first instance server that is issuing transactional requests to the second instance server, setting the transaction rate limit to be the maximum transaction rate of the second instance server divided by the number of processes of the first instance server that are issuing transactional requests to the second instance server.

10. The method of claim 1, further comprising:

determining an average rate at which requests are being issued by the first instance server to the second instance server over a first predetermined time interval; and

in accordance with a determination that the average rate at which transactions are being issued by the first instance server for the second instance server is below a predetermined average rate, decreasing the transaction rate limit.

11. The method of claim 1, wherein the second plurality of transactional requests are issued by a plurality of processes operating at the first instance server;

the method includes, prior to issuing the second plurality of transactional requests to the second instance server, assigning a respective process transaction rate limit to each process in the plurality of processes such that the sum of the process transaction rate limits is equal to or less than the determined transaction rate for the second server; and

wherein the second plurality of transactional requests are issued in accordance with the process transaction rate limits.

12. A distributed storage system, comprising:

a plurality of instance servers communicatively coupled to one another, each instance server of the plurality of instance servers including one or more respective processors coupled to memory, the plurality of instance servers including a first instance server and a second instance server;

the first instance server configured to;

issue a first plurality of transactional requests to a second instance server, the first plurality of transactional requests for creating, modifying, or deleting objects within the distributed storage system;

obtain one or more messages from the second instance server in response to the first plurality of transactional requests, the one or more messages indicating a utilization rate of the second instance server;

determine a transaction rate limit for the second instance server based on the utilization rate of the second instance server; and

issue a second plurality of transactional requests to the second instance server, wherein the second plurality of transactional requests are issued at a rate no greater than the transaction rate limit.

13. The distributed storage system of claim 12, wherein determining the transaction rate limit for the second instance server comprises:

determining at least one percentage of the messages received over at least one predetermined time interval that include a pushback signal; and

determining the transaction rate limit based on the at least one percentage.

14. The distributed storage system of claim 13, wherein the at least one percentage includes a first percentage of the messages received over a first predetermined time interval that include the pushback signal and a second percentage of the messages over a second predetermined time interval that include the pushback signal, wherein determining the transaction rate limit based on the at least one percentage includes:

determining that the first percentage is below a first predetermined threshold and that the second percentage is below a second predetermined threshold; and

responsive to the determining, increasing the transaction rate limit.

15. The distributed storage system of claim 14, wherein at least one percentage includes a first percentage of the messages received over a first predetermined time interval that include the pushback signal and a second percentage of the messages over a second predetermined time interval that include the pushback signal, wherein adjusting the transaction rate limit based on the at least one percentage includes:

determining that the first percentage is above a first predetermined threshold or that the second percentage is above a second predetermined threshold; and

responsive to the determining, decreasing the transaction rate limit.

16. The distributed storage system of claim 12, wherein at least one request of the plurality of transactional requests is issued in accordance with an object replication policy.

17. The distributed storage system of claim 12, wherein the first instance server is further configured to:

determine an average rate at which transactional requests are being issued by the first instance server to the second instance server over a first predetermined time interval; and

in accordance with a determination that the average rate at which transactions are being issued by the first instance server for the second instance server is below a predetermined average rate, decrease the transaction rate limit.

18. The distributed storage system of claim 12, wherein the first instance server includes a number of processes that are issuing transactional requests to the second instance server, and the first instance server is further configured to:

prior to issuing the plurality of transactional requests to the second instance server;

identify a maximum transaction rate of the second instance server; and

for each process on the first instance server that is issuing transactional requests to the second instance server, set the transaction rate limit to be the maximum transaction rate of the second instance server divided by the number of processes of the first instance server that are issuing requests to the second instance server.

19. A non-transitory computer-readable storage medium storing at least one program configured for execution by at least one processor of a first instance server within a distributed storage system, the at least one program comprising instructions to cause the first instance server to:

issue a first plurality of transactional requests to a second instance server, the first plurality of transactional requests for creating, modifying, or deleting objects within the distributed storage system;

obtain one or more messages from the second instance server in response to the first plurality of transactional requests, the one or more messages indicating a utilization rate of the second instance server;

determine a transaction rate limit for the second instance server based on the utilization rate of the second instance server; and

issue a second plurality of transactional requests to the second instance server, wherein the second plurality of transactional requests are issued at a rate no greater than the transaction rate limit.

20. The non-transitory computer-readable storage medium of claim 19, wherein determining the transaction rate limit for the second instance server comprises:

determining at least one percentage of the messages received over at least one predetermined time interval that include a pushback signal; and

determining the transaction rate limit based on the at least one percentage.

21. The non-transitory computer-readable storage medium of claim 20, wherein the transaction rate limit is increased in accordance with a determination that a predetermined amount of time has elapsed since a prior increase to the transaction rate limit.

22. The non-transitory computer-readable storage medium of claim 19, wherein the at least one percentage includes a first percentage of the messages received over a first predetermined time interval that include the pushback signal and a second percentage of the messages over a second predetermined time interval that include the pushback signal, wherein determining the transaction rate limit based on the at least one percentage includes:

determining that the first percentage is below a first predetermined threshold and that the second percentage is below a second predetermined threshold; and

responsive to the determining, increasing the transaction rate limit.

23. The non-transitory computer-readable storage medium of claim 19, wherein at least one percentage includes a first percentage of the messages received over a first predetermined time interval that include the pushback signal and a second percentage of the messages over a second predetermined time interval that include the pushback signal, wherein adjusting the transaction rate limit based on the at least one percentage includes:

determining that the first percentage is above a first predetermined threshold or that the second percentage is above a second predetermined threshold; and

responsive to the determining, decreasing the transaction rate limit.

24. The non-transitory computer-readable storage medium of claim 19, wherein at least one request of the plurality of transactional requests is issued in accordance with an object replication policy.

25. The non-transitory computer-readable storage medium of claim 19, wherein the first instance server includes a number of processes that are issuing transactional requests to the second instance server, and the at least one program further comprises instructions to cause the first instance server to:

prior to issuing the plurality of transactional requests to the second instance server;

identify a maximum transaction rate of the second instance server; and

for each process on the first instance server that is issuing transactional requests to the second instance server, set the transaction rate limit to be the maximum transaction rate of the second instance server divided by the number of processes of the first instance server that are issuing transactional requests to the second instance server.

26. The non-transitory computer-readable storage medium of claim 19, wherein the at least one program further comprises instructions to cause the first instance server to:

determine an average rate at which transactional requests are being issued by the first instance server to the second instance server over a first predetermined time interval; and

in accordance with a determination that the average rate at which transactions are being issued by the first instance server for the second instance server is below a predetermined average rate, decrease the transaction rate limit.