# US 11,310,309 B1 · Arc jump: per-key selection of an alternative server when implemented bounded loads

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,310,309 B1
- Document ID: US11310309B1
- Status: Granted
- Kind: B1
- Application number: 17/119,849
- Filed: 2020-12-11
- Granted: 2022-04-19
- Earliest claimed: 2020-12-11
- Assignees: Amazon Technologies, Inc.
- Applicants: Amazon Technologies, Inc.
- Inventors: Benjamin Ray Coleman; Anshumali Shrivastava; Aravind Srinivasan
- Web page: https://patentgrep.com/patent/US11310309B1

## CPC

- H04L 67/1008: based on parameters of servers, e.g. available memory or workload (monitoring of computer activity G06F11/30)
- H04L 9/0643: {Hash functions, e.g. MD5, SHA, HMAC or f9 MAC}
- H04L 67/1023: based on a hash applied to IP addresses or costs
- H04L 67/1029: using data related to the state of servers by a load balancer
- H04L 67/1034: Reaction to server failures by a load balancer
- H04L 67/1065: {Discovery involving distributed pre-established resource-based relationships among peers, e.g. based on distributed hash tables [DHT] (pre-configuration of logical or physical connections H04L67/1053)}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Systems and methods are described for implementing an “arc jump” technique in conjunction with bounded loads in consistent hashing. In general, bounded loads refers to limiting the ability of a single device within a distributed system to store data objects, such that when a request to store a new data object would otherwise be directed to that device, it is instead redirected to an alternative device. Redirecting all requests to a single alternative device can lead to cascading failures, as the alternative device must maintain its own load and that which has been redirected to it. Embodiments of the present disclosure address this by determining an alternative device on a per-object basis, such as by again hashing the object with an additional seed value. This distributes request from an overloaded device among all other devices of the distributed system, avoiding cascading failures.

## Claims

### Claim 1

A load balancer for a distributed system providing a network-accessible service, the distributed system comprising a plurality of computing devices providing the network-accessible service, wherein the load balancer comprises:
a data store storing information arranging the plurality of computing devices into a consistent hash ring, wherein each computing devices of the plurality of computing devices is mapped to a location on the consistent hash ring and assigned to store data that is mapped to an arc of the consistent hash ring corresponding to the location; and
a processor in communication with the data store and configured to:
obtain a request to store information within the distributed system;
select a first computing device, of the plurality of computing devices, to store the information, wherein the first computing device is selected by:
passing an initial key of the information through a hash function to result in a hash value that corresponds to a first location on the consistent hash ring; and
identifying the first computing device as assigned to the arc of the consistent hash ring that contains the first location;
determine that the first computing device does not have capacity to store the information;
select an alternative computing device, of the plurality of computing devices, to store the information, wherein the alternative computing device is selected by:
passing an alternative key of the information, representing a combination of the initial key and an additional seed value, through the hash function to result in a second hash value that corresponds to a second location on the consistent hash ring; and
identifying the alternative computing device as assigned to a second arc of the consistent hash ring that contains the second location; and
storing the information at the alternative computing device.

### Claim 2 (depends on 1)

The load balancer of claim 1, wherein to determine that the first computing device does not have capacity to store the information, the processor is configured to:
transmit to the first computing device a request to store the information at the first computing device; and
receive a response declining the request to store the information at the first computing device.

### Claim 3 (depends on 1)

The load balancer of claim 1, wherein to determine that the first computing device does not have capacity to store the information, the processor is configured to assess load information, for the first computing device, stored at the load balancer.

### Claim 4 (depends on 1)

The load balancer of claim 1, wherein the additional seed value is a counter indicating a number of attempted locations on the consistent hash ring.

### Claim 5 (depends on 1)

The load balancer of claim 1, wherein the processor is further configured to:
obtain a request to read the information;
identify the first computing device as potentially storing the information at least partly by:
passing the initial key of the information through the hash function to result in the hash value that corresponds to the first location on the consistent hash ring; and
identifying the first computing device as assigned to the arc of the consistent hash ring that contains the first location;
transmit the request to read the information to the first computing device;
obtain a response from the first computing device indicating that the information is not stored at the first computing device;
identify the alternative computing device as potentially storing the information at least partly by:
passing the alternative key of the information and the additional seed value through the hash function to result in the second hash value that corresponds to the second location on the consistent hash ring; and
identifying the alternative computing device as assigned to the second arc of the consistent hash ring that contains the second location;
transmitting the request to read the information to the alternative computing device; and
obtaining the information from the alternative computing device.

### Claim 6

A computer-implemented method comprising:
arranging a plurality of computing devices, which collectively operate as a distributed system, into a consistent hash ring, wherein each computing devices of the plurality of computing devices is mapped to a location on the consistent hash ring and assigned to store data that is mapped to an arc of the consistent hash ring corresponding to the location;
obtaining a request to store information within the distributed system;
mapping the information to a first location on the consistent hash ring based at least partly on a first hash value of the information, the first hash value calculated by passing an initial key of the information through a hash function to result in the first hash value;
determining that a first computing device, of the plurality of computing devices, that is assigned to store data mapped to the first location, is overloaded;
mapping the information to an alternative location on the consistent hash ring based at least in part on an alternative hash value of the information, the alternative hash value calculated by passing an alternative key of the information, representing a combination of the initial key and an additional seed value, through the hash function to result in the alternative hash value; and
storing the information on an alternative computing device, of the plurality of computing devices, that is assigned to store data mapped to the alternative location.

### Claim 7 (depends on 6)

The computer-implemented method of claim 6, wherein the additional seed value indicates an alternative placement of the information on the consistent hash ring.

### Claim 8 (depends on 6)

The computer-implemented method of claim 6 wherein mapping the information to the first location on the consistent hash ring based at least partly on the first hash value of the information comprises:
identifying a plurality of potential locations for the information on the consistent hash ring at least partly by calculating multiple hash values for the information, each of the multiple hash values corresponding to a potential location of the plurality of potential locations for the information; and
comparing the plurality of potential locations for the information to identify the first location as a preferred location for the information.

### Claim 9 (depends on 6)

The computer-implemented method of claim 6 further comprising:
obtaining a request to read the information;
re-mapping the information to the first location on the consistent hash ring based at least partly on the first hash value of the information;
determining that the first computing device does not store the information;
re-mapping the information to the alternative location on the consistent hash ring based at least in part on the alternative hash value of the information; and
reading the information from the alternative computing device that is assigned to store data mapped to the alternative location.

### Claim 10 (depends on 6)

The computer-implemented method of claim 6, wherein the consistent hash ring is represented as a unit circle, and wherein locations on the unit circle are numbered according to a range of a hash function used to generate the first and alternative hash values.

### Claim 11 (depends on 6)

The computer-implemented method of claim 6, wherein determining that the first computing device is overloaded comprises attempting to store the information on the first computing device and failing to store the information on the first computing device.

### Claim 12

One or more non-transitory computer-readable media comprising computer executable instructions for load balancing requests among a plurality of computing devices that collectively operate as a distributed system, wherein the instructions, when executed by a load balancer, cause the load balancer to:
arrange a plurality of computing devices into a ring, wherein each computing devices of the plurality of computing devices is mapped to a location on the ring and assigned to store data that is mapped to an arc of the ring corresponding to the location;
obtain a request to store information within the distributed system;
map the information to a first location on the ring based at least partly on a first hash value of the information, the first hash value calculated by passing an initial key of the information through a hash function to result in the first hash value;
determine that a first computing device, of the plurality of computing devices, that is assigned to store data mapped to the first location, is overloaded;
map the information to an alternative location on the ring based at least in part on a alternative hash value of the information that differs stochastically from the first hash value, the alternative hash value calculated by passing an alternative key of the information, representing a combination of the initial key and an additional seed value, through the hash function to result in the alternative hash value; and
store the information on an alternative computing device, of the plurality of computing devices, that is assigned to store data mapped to the alternative location.

### Claim 13 (depends on 12)

The one or more non-transitory computer-readable media of claim 12, wherein the additional seed value indicates an alternative placement of the information on the ring.

### Claim 14 (depends on 12)

The one or more non-transitory computer-readable media of claim 12, wherein mapping the information to the first location on the ring based at least partly on the first hash value of the information comprises:
identifying a plurality of potential locations for the information on the ring at least partly by calculating multiple hash values for the information, each of the multiple hash values corresponding to a potential location of the plurality of potential locations for the information; and
comparing the plurality of potential locations for the information to identify the first location as a preferred location for the information.

### Claim 15 (depends on 12)

The one or more non-transitory computer-readable media of claim 12, wherein the instructions further cause the load balancer to:
obtain a request to read the information;
re-map the information to the first location on the ring based at least partly on the first hash value of the information;
determine that the first computing device does not store the information;
re-mapping the information to the alternative location on the ring based at least in part on the alternative hash value of the information; and
read the information from the alternative computing device that is assigned to store data mapped to the alternative location.

### Claim 16 (depends on 12)

The one or more non-transitory computer-readable media of claim 12, wherein to determine that the first computing device is overloaded, the instructions cause the load balancer to determine that a load metric of the first computing device exceeds a threshold value.

### Claim 17 (depends on 12)

The one or more non-transitory computer-readable media of claim 12, wherein to determine that the first computing device is overloaded, the instructions cause the load balancer to attempt to store the information on the first computing device and fail to store the information on the first computing device.