Power-of-2-Choices in Practice(engineering.mixpanel.com)
engineering.mixpanel.com
Power-of-2-Choices in Practice
https://engineering.mixpanel.com/power-of-2-choices-in-practice-b6097020dfad
13 comments
"It introduces two extra round trips" is an implementation flaw/detail, not an aspect of this strategy. There is no reason that servers cannot periodically advertise their load measures to clients, or staple current load reports to query responses, which the client can cache and use for a period of time.
That is still an extra repsonse time though, you get nothing for free.
In the two cases mentioned, there isn't any extra _response_ time.
> 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.
> 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.
Author here. Great points, I agree 2 extra round trips are not strictly necessary.
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.
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.
Even in the proxy case (which is my day job), it's often worth the price of the up-front load polling to have sufficiently recent information to take action on. The most obvious cases are those where you have some (or all) requests being expensive, as opposed to thousands of exclusively tiny requests.
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).
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).
The name "power of two" seems to misrepresent the algorithm to me. Shouldn't it be called "least of random 2"?
What's the history behind the name?
What's the history behind the name?
It comes from the paper "The Power of Two Random Choices: A Survey of Techniques and Results" - http://www.eecs.harvard.edu/~michaelm/postscripts/handbook20...
I'm the author of this post, happy to answer any questions!
Great article, always love to see the law of large numbers fail! You mention that the solution "requires all clients to cooperate" - wouldn't it be in the client's best interest to cooperate (maximizes the probability the request is served, as well as minimizes latency)? I suppose a malicious client could deliberately route traffic to a fully-utilized node, but that seems outside the scope of this problem space
Good question! Yes, it's in the interest of clients to cooperate.
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.
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.
Wonderful use case and love how simple of a heuristic it is to implement.
Diminishing returns beyond choice of 2 is also quite interesting: http://www.cs.tau.ac.il/~azar/box.pdf
Diminishing returns beyond choice of 2 is also quite interesting: http://www.cs.tau.ac.il/~azar/box.pdf