Elijah's Notes

Load Balancing

4 min read

Purpose

This note lists what a load balancing scheme has to achieve, then covers the strategies I’ve studied for getting there and the queueing math that explains why utilization drives tail latency.

What we want

  1. Clients all follow the same assignment
  2. Load is evenly distributed
  3. Adding or removing a server only moves a few keys
  4. Tail latency is minimized
  5. Redistributing keys should not overload a single server
  6. Load stays even despite differences in key popularity

Scaling Paxos with sharding

This design combines Paxos consensus with sharding.

Use Paxos to define the order of a state machine running on a set of servers. For a key-value store, split the key space into shards, assigning a set of keys to each shard. A dedicated Paxos group called the shard master owns the assignment of keys to shards. Each shard is then its own Paxos group running the state machine for its subset of keys.

flowchart TD
    Client[Client] -->|where does key k live?| SM[Shard master<br/>Paxos group]
    Client -->|request for key k| S2

    subgraph Shards
        S1[Shard 1<br/>Paxos group<br/>keys a–h]
        S2[Shard 2<br/>Paxos group<br/>keys i–p]
        S3[Shard 3<br/>Paxos group<br/>keys q–z]
    end

    SM -.assigns key ranges.-> S1
    SM -.-> S2
    SM -.-> S3

This spreads request load across multiple servers and distributes the data along with it.

Edge caching

Content local to a user should be cached on the user’s machine. For content that is popular and not user specific, like logo.png, cache it on one designated server and redirect all requests for that content there. Requests spread across servers by content, and each piece of content occupies cache memory on only one server instead of every server.

Queueing

Assume completely random (Poisson) arrivals and exponentially distributed service times, the M/M/1 queueing model. The mean response time is

where is response time, is service time, and is server utilization. In an M/M/1 queue the response time is exponentially distributed, so its standard deviation equals its mean, . As utilization approaches 1, both the mean and the spread of response times blow up, which is exactly where tail latency comes from.

The system can be modeled as a Markov chain with states , where state means requests are in the system. The transition rate from state to is the arrival rate , and from to is the service rate . The formulas above fall out of solving this chain’s steady state.

In practice load is bursty rather than Poisson, so services get overprovisioned to absorb spikes. The variance result explains why that overprovisioning is worth paying for. Run a server near full utilization and its tail latency becomes enormous.

Utilization drives tail latency

As , both the mean response time and its standard deviation blow up as . High utilization looks efficient on a dashboard, but it is exactly where tail latency comes from, which is why services deliberately overprovision.

Key popularity

The Zipf distribution says the th most popular item has frequency proportional to for some . It roughly fits a lot of observed workloads, including web page hits, file access frequency, file sizes, word frequency, and friend counts on social networks. The consequence for load balancing is that hashing keys uniformly across servers still leaves whichever server holds the hottest keys overloaded.

The power of two choices copes with popular keys: hash each key to two (or in general ) candidate servers, and forward each request to whichever candidate is under less load. Mitzenmacher’s analysis shows that moving from one choice to two gives an exponential improvement in the maximum load, while more than two choices adds little.

Two choices is the sweet spot

Going from one random choice to two gives an exponential improvement in maximum load; going from two to three or more gives only a constant-factor gain. Almost all of the benefit comes from having any choice at all.

Graph View