公开(公告)号：US11140220B1

公开(公告)日：2021-10-05

申请号：US17119835

申请日：2020-12-11

Applicant: Amazon Technologies, Inc.

Inventor： Benjamin Ray Coleman ,  Anshumali Shrivastava ,  Aravind Srinivasan

IPC: G06F15/173 ,  H04L29/08

Abstract: Systems and methods are described for load balancing requests in a distributed system using consistent hashing. Specifically, systems and methods are described for using “the power of k choices” when placing new servers on a consistent hash ring used to load balance requests. Rather than placing each new server at a fixed point determined by a hashing algorithm, a load balancer can identify multiple potential points on the hash ring for the new server. The load balancer can then compare these points to determine a preferred location, and place the server at the preferred location. Techniques described herein can substantially improve placement of servers, which in turn results in better load balancing.

公开(公告)号：US11863613B1

公开(公告)日：2024-01-02

申请号：US17209008

申请日：2021-03-22

Applicant: Amazon Technologies, Inc.

Inventor： Mihir Sathe ,  Aravind Srinivasan ,  Pranav Rao Perampalli Nekkar

IPC: H04L67/1008

CPC classification number: H04L67/1008

Abstract: Systems and methods are described for allocating requests to implement new workloads within a dynamic set of servers. Existing load balancing techniques can result in “focus firing” on new servers added to the set, since a load balancer may view a new server as underloaded. With sufficient intensity, focus firing can result in overshooting target load for the new server, and the new server in fact becoming overloaded. The present disclosure modifies selection of servers as potential targets for a workload by at least partly biasing against selection of young servers. The bias imposed can be scaled to avoid overloading new servers.

公开(公告)号：US11310309B1

公开(公告)日：2022-04-19

申请号：US17119849

申请日：2020-12-11

Applicant: Amazon Technologies, Inc.

Inventor： Benjamin Ray Coleman ,  Anshumali Shrivastava ,  Aravind Srinivasan

IPC: G06F15/173 ,  H04L67/1008 ,  H04L67/1023 ,  H04L9/06 ,  H04L67/1034 ,  H04L67/1029

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.