CSE Roadmap

Core tier · about 3 hours · 9 parts

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 4 equals key 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?