gistfile1.txt

aphyr@waterhouse:~/timelike master$ lein test timelike.node-test

lein test timelike.node-test
Even connections LB
Total reqs: 10000
Latency distribution:
Min:     0.017489419380090965
Median:  141.4027252436847
95th %:  612.7774737814785
99th %:  937.1806417316121
Max:     2209.5865226144797

Round-robin LB
Total reqs: 10000
Latency distribution:
Min:     0.059074365428386955
Median:  324.036241525856
95th %:  1326.8732292504349
99th %:  2082.596619510439
Max:     4117.761247500504

Random LB
Total reqs: 10000
Latency distribution:
Min:     0.09270395696421474
Median:  486.3933621204492
95th %:  2076.5397925072252
99th %:  3083.4158554804326
Max:     5554.643863168227

Random -> 10 even LBs -> One pool
Total reqs: 10000
Latency distribution:
Min:     2.313230943246083
Median:  1701.463751485487
95th %:  2943.183875633857
99th %:  3497.1821173598187
Max:     4907.303065288917

Random -> 10 even LBs -> 10 disjoint pools
Total reqs: 10000
Latency distribution:
Min:     0.07358224340123343
Median:  153.84862403905777
95th %:  642.3243504490231
99th %:  965.8068718446074
Max:     1769.1909690601226

This is a simulation of some simple load-balancing algorithms over a single-threaded, queued server. There are 250 servers in this pool, and their response times are exponentially distributed with a mean of 200 milliseconds. Requests arrive at roughly 1 per millisecond, poisson-distributed, so the cluster is handling roughly 80% of maximum possible load in the infinite-time limit. The simulation is still pretty expensive so I haven't run it with a large number of requests yet!

This model doesn't take into account synchronization costs or network delays yet, and I haven't run the simulations long enough for reasonable accuracy, but I think the results are intuitively reasonable. A single even load balancer, which allocates new connections to those with the minimum number of open conns, is best. A round-robin load balancer does OK, but runs the risk of sending several long-running requests to the same server, which backs up latencies. Both of these models require live, synchronized distributed state, which the CAP theorem essentially prohibits.

A single random load balancer does horribly, as you'd expect. But there's another option: set up a bunch of independent min-conn load balancers, and allocate requests randomly between those. This is, if I understand correctly, essentially what Heroku's stack does. It's significantly better than random routing, since any given load balancer will try to avoid putting lots of conns onto a single server. OTOH, all 10 load balancers could double-down on the same node. This asymptotically approaches an even (and poorly available) LB with fewer mid-layer LBs, and a random (and highly available) LB with lots of mid-layer LBs.

There's another option, though, which is especially interesting if your network isn't evenly connected--which is typically the case. You partition your backends into disjoint (or at least minimally overlapping) groups, and assign a single shared-state even LB over each. Then you assign requests randomly between those LBs. This hybridized solution performs extremely well. Although it doesn't handle bursts as well as a globally even router, because groups can go underutilized when an LB can't dispatch to a lesser-used process. But it's significantly more efficient than a purely random mesh, or even several independent least-conn routers operating over the same backend.

This is a case where it can actually be more efficient to sacrifice throughput to achieve latency. I haven't written a failure-mode simulator yet, but I posit that if your independent router groups are allowed to fail entirely, in blocks, when a group's LB dies, your latency is still significantly better than global routing because you never run the risk of oversubscribing a node.