Load balancing & Subsetting

This write-up explores the problems of load balancing and sunsetting. It also discusses various approaches one can take for both these problems and how they mirror each other. Ideas and pictures were taken from the paper: Reinventing Backend Subsetting at Google.

Load Balancing

Load balancing is a fundamental technique in distributed systems that efficiently distributes incoming network traffic across multiple servers or resources. Its primary goal is to optimize resource utilization, maximize throughput etc by preventing any single server from becoming a bottleneck or a single point of failure. Given these many goals and the degrees of freedom amongst many replicas, we have quite a few approaches at trying to achieve a good distribution. Let’s look at them in (roughly) increasing order of complexity. Simpler load balancing approaches often rely on straightforward algorithms that distribute requests which are fairly straightforward to implement but can lead to uneven distribution or skew in various scenarios. By increasing the complexity and potentially adding some overhead, we can achieve a good trade-off of the target feature set.

Take 1 — Round Robin

Round Robin is the most basic method, where requests are sequentially distributed to each server in a continuous rotation. If there are n servers, the first request goes to server 1, the second to server 2, and so on, cycling back to 1 at request (n+1). This is simple, but it doesn’t account for server health or capacity, meaning a slow or overloaded server will still receive requests. It can be enhanced using weighted round robin where a weight is assigned to each server based on its capacity and servers with higher weights receive a larger share of the incoming requests. This helps in distributing load more effectively across heterogeneous servers but often requires manual configuration, can’t adapt quickly to changes etc.

Take 2 — Dynamic decisions

A slightly different approach is to optimise some indicative metric of load. For example, Least Connections based load balancing directs new requests to the server with the fewest active connections. It aims to prevent servers from becoming overloaded and maintain a more consistent load across the server pool. This method works well when connections are persistent and vary in duration, but this is more complex and makes potentially bad assumptions like equal capacity for server tasks. On the other spectrum, you can make this decision metric hash-based where the source and destination IP addresses of the client are used to generate a hash value, which then consistently maps the request to a specific server. This works well for maintaining session affinity or caching too. But, the main drawback here is that if a server got added or removed, then the entire mapping changes. Put another way, this rehashing results in a lot of churn in connections.

Take 3 — Consistent hashing

Consistent hashing addresses this problem by minimizing the number of keys that need to be remapped when the number of servers (nodes) changes. It works on the principle of a hash ring where hash space is arranged in a circle and server nodes and request keys are both hashed using the same hash function and mapped. That server that responsible for a key will be the first taken clockwise hash. This is essentially the traditional hashing approach with a longer lookup. The advantage we get is minimal remapping. How? — when a server is added or removed, only a few data keys needs to be remapping to maintain the clockwise invariant which is a massive reduction. This can still result in some skew and to reduce it especially in cases of small number of physical servers, each one can be assigned multiple nodes (virtual nodes ) in the ring and reduces impact even more. It can be proved that the solution is optimal, which means that least number of keys need to be remapped to maintain load-balance on an average. Consistent hashing is widely used in distributed caching, distributed hash tables (DHTs), and content delivery networks (CDNs) to ensure scalability and fault tolerance.

Consistent hashing

Subsetting

Subsetting is a related idea to load balancing where the goal is to divide a large dataset into smaller, more manageable subsets for analysis or processing. While load balancing focuses on distributing traffic, subsetting focuses on organizing resources. In Google’s ACM paper on subsetting, the chosen application is assigning frontend tasks to backend tasks. The method of subsetting is the task at hand and the choice depends on the specific application. But, it broadly follows the same increasingly complex approaches in load balancing.

Take 1 — Random subsetting

The simple starting algorithm is to choose random subsets for each Each frontend task shuffles the list of backend tasks and selects the first k tasks. This is straightforward to implement but doesn’t work well in practice. It interacts poorly with many load-balancing policies primarily as it leads to a non-uniform distribution of connections across backend tasks.

Take 2 — Round Robin

We can do round robin subsetting which is actually excellent if just the subsetting is concerned, but it has other practical issues. For example, if you deploy a canary to a backend, it might crash and affect tasks in some frontend tasks disproportionately. Also, if a frontend task fails or is restarted, and then comes back up, it will deterministically be assigned a different subset of backends than it might have had before, leading to connection churn on the backend side.

Take 3 — Determinstic subsetting

Subset diversity missing in round robin subsetting can be increased by introducing randomness. In practice, this leads to a solution where you shuffle all the backend tasks, assign them to the first few front ends, and then repeat this. This idea along with some round robin management of the left over tasks after a cycle seemed like a good model at least in Google. But, this faced issues when Autopilot made horizontal resizing of the backend tasks more frequent which means there is a lot of backend connection churn now with this approach.

Take 4 — Ringsteady Subsetting

The goal is to keep the good things about deterministic subsetting but drastically reduce connection churn. The problem was the connection balance is determined by how evenly spaced the backend tasks are around the circle and they were essentially. The approach Google came up with was to improve on backend tasks getting randomly chosen positions by using a sequence of positions that favors an even distribution: a low-discrepancy sequence. The sequence Google chose is the binary van der Corput sequence,h which begins (with the addition of 0 as the zeroth element) as 0, ½, ¼, ¾, ⅛, ⅝, ⅜, ⅞.

Note that this approach works only because the backend tasks are consecutively numbered, so the nth element in the low-discrepancy sequence can be associated with the nth backend task. This means if a backend gets added or removed, the connection churn of the subset is drastically reduced. The figure shows utilisation against #frontend/#backend ratio.

Final take — Rocksteadier Subsetting

The last one still had a small pitfall as seen in (c). When Frontend tasks outnumber backend tasks, utilization does not converge toward the ideal. The low-discrepancy sequence results in the positions for frontend and backend tasks not exactly evenly spaced which is bad for scenarios with leftover tasks. You can fight it by eliminating leftovers, and you can do that by scaling frontend or backend tasks. Frontend scaling is not a good idea though since frontend scaling makes the positions of frontend tasks dependent on the frontend size, which introduces a lot of frontend churn. Rocksteadier Subsetting is essentially Ringsteady Subsetting + backend scaling. This seems to be the final frontier, for now.

Summary