Utilizing multiple algorithms in a distributed-service environment

Patent metadata

Field	Value
Publication number	US-9755985-B1
Application number	US-89252710-A
Country	US
Kind code	B1
Filing date	Sep 28, 2010
Priority date	Sep 28, 2010
Publication date	Sep 5, 2017
Grant date	Sep 5, 2017

Abstract

Techniques for producing a gentle reduction in throughput in a distributed service when a node of the service encounters a very large backlog of requests and/or when a previously offline node of the service is brought back online. These techniques may utilize multiple different algorithms to determine an amount of work that the distributed service is able to accept at any given time, rather than a single algorithm.

First claim

What is claimed is:

1. One or more non-transitory computer-readable media storing computer-executable instructions that, when executed, cause one or more processors to perform acts comprising:
calculating, for a group of replicated nodes that includes at least a first replicated node and a second replicated node, a maximum number of requests per second that the group of replicated nodes is able to accept based at least in part on at least one of a first backlog of the first replicated node and a second backlog of the second replicated node, wherein the first replicated node and the second replicated node in the group of replicated nodes replicates processing of a plurality of requests that the group of replicated nodes accepts;
determining that the first backlog and the second backlog are both less than a threshold amount;
based at least in part on the determining that the first backlog and the second backlog are both less that the threshold amount, continuing to calculate the maximum number of requests per second that the group of replicated nodes is able to accept; and
at least partly in response to determining that the first backlog of the first replicated node is not less than the threshold amount:
determining that the first replicated node is in a recovery mode;
setting the maximum number of requests per second that the group of replicated nodes is able to accept while the first replicated node is in a recovery mode based at least in part on the second backlog of the second replicated node, the second backlog including a highest backlog from among backlogs of replicated nodes that are not in the recovery mode;
computing a size of the first backlog of the first replicated node at a first time;
re-computing the size of the first backlog of the first replicated node at a second, later time;
comparing the first backlog of the first replicated node at the first time with the first backlog of the first replicated node at the second, later time to determine that the first backlog of the first replicated node has increased or decreased; and
adjusting the maximum number of requests per second that the group of replicated nodes is able to accept based at least in part on determining that the first backlog of the first replicated node increased or decreased.

2. One or more non-transitory computer-readable media as recited in claim 1 , wherein:
the first replicated node and the second replicated node of the group of replicated nodes processes the plurality of requests sequentially according to a number associated with individual requests;
the computing of the size of the first backlog at the first time comprises determining a difference between a number associated with a most recent request received at the first time and a number associated with a request processed by the first replicated node at the first time;
the re-computing of the size of the first backlog at the second, later time comprises determining a difference between a number associated with a most recent request received at the second, later time and a number associated with a request processed by the first replicated node at the second, later time; and
the comparing comprises determining that the difference at the first time is greater or less than the difference at the second, later time.

3. One or more non-transitory computer-readable media as recited in claim 1 , further storing computer-executable instructions that, when executed, cause the one or more processors to perform an act comprising repeating the computing, the re-computing, and the adjusting until the first backlog is less than the threshold amount for a threshold amount of time.

4. One or more non-transitory computer-readable media as recited in claim 1 , further storing computer-executable instructions that, when executed, cause the one or more processors to perform acts comprising:
imposing a cap on the maximum number of requests per second that the group of replicated nodes is able to accept; and
based at least in part on imposing the cap:
relaxing the cap on the maximum number of requests per second that the group of replicated nodes is able to accept based at least in part on the first backlog of the first replicated node in the recovery mode decreasing; and
tightening the cap on the maximum number of requests per second that the group of replicated nodes is able to accept based at least in part on the first backlog of the first replicated node in the recovery mode increasing.

5. One or more non-transitory computer-readable media as recited in claim 1 , further storing computer-executable instructions that, when executed, cause the one or more processors to perform an act comprising:
calculating a maximum number of requests per second that the second replicated is able to accept based, at least in part, on the second backlog,
and wherein setting the maximum number of requests per second that the group of replicated nodes is able to accept comprises setting the maximum number of requests per second that the group of replicated nodes is able to accept to include the maximum number of requests per second that the second replicated is able to accept.

6. One or more non-transitory computer-readable media as recited in claim 1 , wherein:
the first backlog includes a higher backlog than the second backlog;
calculating the maximum number of requests per second that the group of replicated nodes is able to accept comprise calculating a maximum number of requests per second that the first replicated is able to accept based, at least in part, on the first backlog; and
further storing computer-executable instructions that, when executed, cause the one or more processors to perform an act comprising:
based at least in part on determining that the first backlog and the second backlog are both less that the threshold amount, setting the maximum number of requests per second that the group of nodes is able to accept to include the maximum number of requests per second that the first replicated node is able to accept.

7. One or more non-transitory computer-readable media storing computer-executable instructions that, when executed, cause one or more processors to perform acts comprising:
calculating, for a group of nodes that includes at least a first node and a second node, an amount of work that the group of nodes is able to accept based at least in part on a first backlog of a first node of the group of nodes and a second backlog of a second node of the group of nodes, wherein the first node and the second node in the group of nodes replicates processing of the work that the group of nodes accepts; and
based at least in part on the first backlog of the first node of the group of nodes being greater than a threshold amount:
determining that the first node is in a recovery mode;
calculating an amount of work that the second node is able to accept based at least in part on a second backlog of the second node, the second backlog including a highest backlog from among backlogs of nodes that are not in the recovery mode;
setting the amount of work that the group of nodes is able to accept to include the amount of work that the second node is able to accept;
computing a size of the first backlog of the first node of the group of nodes at a first time;
re-computing the size of the first backlog of the first node of the group of nodes at a second, later time;
comparing the first backlog of the first node of the group of nodes at the first time with the first backlog of the first node of the group of nodes at the second, later time to determine that the first backlog of the first node of the group of nodes has increased or decreased; and
adjusting the amount of work that the group of nodes is able to accept based at least in part on deter

Assignees

• Lutz David A
• Stefani Stefano
• Kulesza Jakub
• Rath Timothy Andrew
• Amazon Tech Inc

Inventors

• Lutz David A
• Stefani Stefano
• Kulesza Jakub
• Rath Timothy Andrew

Classifications

• H04L47/6255 Primary

  queue load conditions, e.g. longest queue first · CPC title