Part 5 of 9 · 3 min read
Choosing a server
Round robin, least connections, hashing and two random choices, with the weakness of each.
Think of a supermarket with five tills. A guard can send people to the tills in order, send each one to the till with the shortest queue, or send each person to the till that matches their trolley number. Each rule works well in some shops and badly in others.
The rule is called the balancing algorithm.
Round robin. Server 1, then 2, then 3, then 1 again. It is simple and needs no data. It treats all servers and all requests as equal, which is false when one request is 100 times heavier than another. A weighted form gives bigger servers a bigger share: a server with weight 2 gets twice as many turns as one with weight 1.
Least connections. The request goes to the server with the fewest requests in progress. It copes with uneven request cost. It needs the LB to count what is in progress.
Hashing. A hash of something stable picks the server: the client address, a user identifier or a cookie. The same key reaches the same server every time. This helps when a server keeps something warm for that key. Its weakness shows when the pool changes.
A worked example of that weakness. The simple method is "hash modulo N": take the hash, divide by the number of servers, and use the remainder. With 4 servers, key 7 goes to server 7 mod 4 = 3. Now a fifth server joins.
- Look at keys 0 to 19.
- A key stays on its server only if
key mod 4equalskey mod 5. - This holds for keys 0, 1, 2 and 3 only. That is 4 keys of 20.
- So 16 of 20 keys, 80 percent, move to a new server.
For a cache (Level 3), this means that nearly all stored copies are suddenly in the wrong place. The fix named in the book is consistent hashing, in which servers and keys are placed on a circle and each key goes to the next server around. Adding one server to 4 moves only about 1 in 5 keys, 20 percent. Level 4 explains it fully.
Two random choices. The book describes a trap with load metrics. A balancer checks each server's load now and then, not on every request. A server that just joined reports a load of zero. The balancer sends it everything until the next check. The server is then marked busy, and the balancer stops sending anything. The load swings back and forth. This is called herding. Pure random choice avoids it and works better than the stale numbers. The best fix in the book mixes the two ideas. Pick two servers at random, and send the request to the less loaded of the pair. Stale data is used, but the randomness spreads the herd.
| Rule | Strength | Weakness |
|---|---|---|
| Round robin | Simple | Ignores uneven requests |
| Weighted round robin | Handles different server sizes | Weights are set by hand |
| Least connections | Handles uneven requests | Needs live counts |
| Hash of a key | Same key, same server | Moves keys when the pool changes |
| Two random choices | No herding, good spread | Slightly more logic |
Hotspot
A hotspot is one server (or one part of a system) that gets far more work than the others.
Example: if one big customer sends half of all requests, and requests are routed by customer, one server carries half the load.
Common mistake
Keeping a user on one server with a cookie "so that it works". The book notes that such sticky sessions can create hotspots, since some users cost much more than others. Page 5 shows a better way.
Check yourself:
- Why does adding a fifth server to a pool of 4 move 80 percent of keys under modulo hashing?
- What is herding, and which rule avoids it?