Power-of-2-Choices in Practice
engineering.mixpanel.com
engineering.mixpanel.com
> servers cannot periodically advertise their load measures to clients
This is an asynchronous mechanism - you can use polling, push, or queue, or whatever. Individual responses don't pay the cost.
> staple current load reports to query responses, which the client can cache and use for a period of time
This is just a few extra bytes in the response, which likely has negligible cost. One can fairly reasonably say that responses don't pay any cost.
Obviously there are other costs - it just depends on what you're trading off between on whether it is the right decision.
The advantage of P2C is the simplicity that comes from its stateless/just-in-time nature. If you cache load, either by servers broadcasting or including a load indicator in the response, you have to consider cache invalidation and TTLs. The longer the TTL, the higher the odds of a thundering herd (all clients think one server is under loaded and proceed to overload it). If you're undertaking this complexity, it may be better to go with a proxy, which can have other benefits too (connection pooling, no client cooperation required). Like all such decisions, it depends on the situation.
This does depend on having a local load balancing layer (not, say, making a choice between two servers that are each 50+ms away from the load balancer), and also having a high-performance RPC stack (C++ on both sides, and Thrift, in my case).
Fundamentally, P2C thickens the interface between client and server by leaking the implementation and responsibility of balancing server load onto the client. Again, this works really well if there is a small, static set of clients as we have internally, but not that well if the clients are out in the wild (eg: on mobile devices). It's totally in the client's interest to upgrade, but that's always work and you just can't rely on that. :)
So imo this is a serious tradeoff that must be made before employing P2C. A good hybrid approach (briefly mentioned in the post) is to introduce a proxy that uses P2C. This is fully in your control and is cheaper than having the proxy maintain a full histogram of load on all downstreams.
Diminishing returns beyond choice of 2 is also quite interesting: http://www.cs.tau.ac.il/~azar/box.pdf
"of or concerning priests"
What's the history behind the name?