Hey folks!
This post will deep dive into a new load-balancing algorithm at Netflix. If you are into backend engineering and system design, keep reading!
Netflix's Load Balancer - Zuul
Netflix runs on AWS. It has millions of active users, and every user connects with their backend services through a load balancer called Zuul.
Here's what that looks like:
1. Netflix Zuul balancers incoming traffic between backend servers.
To minimize latency, client devices create connections with Zuul. Setting up and tearing down TCP connections is expensive.
Ideally, we would want to create a single long-lived connection with each backend service and use it for multiple requests.
Considering this, Netflix has the following load-balancing goals:
- Distribute connections evenly across servers, to best utilize hardware capabilities.
- Dynamically allocate and deallocate servers, to react to changes.
- Minimize connection churn, which is the maximum movement of users from one server to another, when adding or removing servers. This stops a server from being flooded with new requests.
Satisfying all three requirements is a challenge. Let's go over some solutions step by step.
1. Routing with Maps
The idea is simple: on receiving a request from a user, send the request to a user-dedicated server.
A user with id = 1 is assigned to S1. A user with id = 2 goes to S2, and so on.
This algorithm needs one server per user. That's too expensive!
Instead, let's assign multiple users to a single server.
The first million users go to S1, the second million go to S2, and so on. When a user registers, they are allotted a server for life.
And what happens if a user leaves the platform? We could adjust all user IDs to shift by one, but that causes connection churn. Instead, we let that connection stay idle forever.
Now comes the important question: is traffic distributed evenly across servers? Nahi!
Different users are active at different times based on time zones. At 8 PM PST, a server with primarily American users will be flooded, while servers with Indian users will be underutilized.
Server 1 is flooded during peak watch time in the Americas, while S2's users are sleeping!
We need a better distribution algorithm.
2. No maps, just hashing
Instead of statically mapping users to servers, let's dynamically allocate users using hashing.
The idea is simple:
- Hash requests based on user_id. This gives us a number = U1.
- Also hash all server ids to get numbers {SH1, SH2, SH3, SH4, …}
- Find the server hash closest to H1, and assign the request to it!
This is what it looks like figuratively:
The request is allotted to the server having the closest hash value = S4.
Why does this work? Hashes are random and uniform. We expect them to be evenly distributed.
That means an incoming request has an equal likelihood of being picked up by any of our servers, satisfying our first requirement.
Hashing also satisfies our second requirement, with easy addition and deletion of servers (just add or remove the server hashes from the list).
The third requirement is a challenge. What happens if a server crashes? All connections served by it will move to the next server in the list, potentially flooding it.
3. On server crash, an avalanche of requests hits the next server.
When S4 crashes, all of its requests move to a single server S1, straining it.
3. Virtual Servers
When you have problems, find imaginary solutions.
Instead of having a single hash for a server, we generate multiple hash IDs per server. This is done by assigning multiple virtual ids to a single server, or using multiple hash functions.
The result looks something like this:
4. Churn reduces with different neighbors for each server.
The request is allotted to the server having the closest hash value = S2.
What's the benefit? If a server crashes, all of its requests will be redirected to the next servers in the list. It's extremely unlikely for two servers to be consecutive to each other for all positions in the list.
So, we expect lesser connection churn on addition or removal of servers. That satisfies our third requirement.
This algorithm is known as consistent hashing.
4. Netflix Subsetting
The problem with the above algorithm is variance. Hashes should be uniform, but it is common to see skew in real-world distributions.
This prompted the Netflix team to try a new algorithm: Backend Subsetting.
The main idea is this: split the list into chunks and enforce uniform distribution. Here is the flow:
- We divide our servers into sets.
- On receiving a request, we randomly assign it to a set.
- Inside this set, servers are chosen sequentially (round-robin).
- During the addition or removal of a server, we go set by set. The math behind this is the Van der Corput sequence, which looks like this:
That's it! This algorithm has a reasonably uniform load, smooth allocation and deallocation, and very little connection churn.
Netflix used this algorithm to reduce their connections by a factor of 10. That's over 13 million connections saved!
6. The server set sizes are roughly equal. Awesome!
The interesting thing is that Google and Uber Load Balancers have used the same algorithm to clock massive gains. All reported advancements are recent, from 2022-2023.
Wow, load balancing still has some secrets!
That's it for this blog on deep backend engineering. I will see you in the next article, soon!
References
Cheers! To learn more System Design, enjoy our in-depth course at InterviewReady.
Cheers 😀
#systemdesign #netflix #loadbalancing