Back to results
US 9,755,985 B1Granted
Utilizing multiple algorithms in a distributed-service environment
AssigneeAmazon Technologies, Inc.
InventorsDavid A. Lutz, Stefano Stefani, Jakub Kulesza, Timothy Andrew Rath
Life of this patent
Estimating the term…
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.
Claims30
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.
9 more elements
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 determining that the first backlog of the first node of the group of nodes increased or decreased.
8 more elements
A method comprising:
- under control of one or more computer systems configured with specific executable instructions,
- receiving requests to perform work within a distributed service that performs the work using at least a first node and a second node of multiple nodes of the distributed service;
- determining that a first backlog of the first node and a second backlog of the second node are less than a threshold;
- based at least in part on the determining that the first backlog and the second backlog are less than the threshold, operating the distributed service in a first mode;
- setting a first rate at which the distributed service accepts the requests to perform the work using a first algorithm when the distributed service operates in the first mode;
- identifying that the first node enters a recovery mode based at least in part on the first backlog of the first node having a higher backlog of received requests than the threshold;
- based at least in part on the identifying:
- operating the distributed service in a second, different mode;
- determining, using a second, different algorithm, a second rate at which the second node is able to accept to the requests based, at least in part, on the second backlog, wherein the second backlog includes a highest backlog from among backlogs of nodes that are not in the recovery mode;
- and
- setting the first rate at which the distributed service accepts the requests to perform the work to include the second rate at which the second node is able to accept the requests.
8 more elements
One or more computing devices comprising:
- one or more processors;
- and
- one or more computer-readable media storing computer-executable instructions that, when executed, cause the one or more processors to perform acts comprising:
- processing sequential requests received at a distributed service, wherein individual requests of the sequential requests are replicated by at least a first computing device and a second computing device of the distributed service;
- operating the distributed service in a first mode to provide, from the first computing device to the second computing device, an indication of a first backlog of sequential requests yet to be processed at the first computing device, wherein the distributed service is configured to operate in the first mode in response to determining that the first backlog of sequential requests of the first computing device and a second backlog of sequential requests of the second computing device is less than a predetermined threshold;
- and
- based at least in part on the first computing device entering a recovery mode:
- operating the distributed service in a second, different mode to provide, from the first computing device to the second computing device, an indication of which request of the sequential requests the first computing device is currently processing;
- and
- setting a rate at which the distributed service receives the sequential requests during the second, different mode based at least in part on the second backlog of sequential requests that the second computing device has yet to process, wherein the second backlog of sequential requests includes a highest backlog from among backlogs of computing devices of the distributed service that are not in the recovery mode.
7 more elements
Dependencies are inferred from the claim text.