5 ms·

Power-of-2-Choices in Practice

43 points by i0exception 6y ago

vijayjayaram 6y ago
I'm the author of this post, happy to answer any questions!
- illirik 6y ago
  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
  - vijayjayaram 6y ago
    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.
- dnw 6y ago
  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 http://www.cs.tau.ac.il/~azar/box.pdf
  - chrisweekly 6y ago
    hieratic? "of or concerning priests"
    - dnw 6y ago
      Thanks, I meant heuristic. Fixed that typo above.
jeffbee 6y ago
"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.
- bobthebuilders 6y ago
  That is still an extra repsonse time though, you get nothing for free.
  - nbm 6y ago
    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.
    - vijayjayaram 6y ago
      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.
      - nbm 6y ago
kristianp 6y ago
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?
- nbm 6y ago
  It comes from the paper "The Power of Two Random Choices: A Survey of Techniques and Results" - http://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf http://www.eecs.harvard.edu/~michaelm/postscripts/handbook20...

43 points by i0exception 6y ago

vijayjayaram 6y ago

I'm the author of this post, happy to answer any questions!

illirik 6y ago
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
- vijayjayaram 6y ago
  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.
dnw 6y ago
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 http://www.cs.tau.ac.il/~azar/box.pdf
- chrisweekly 6y ago
  hieratic? "of or concerning priests"
  - dnw 6y ago
    Thanks, I meant heuristic. Fixed that typo above.

jeffbee 6y ago

"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.

bobthebuilders 6y ago
That is still an extra repsonse time though, you get nothing for free.
- nbm 6y ago
  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.
  - vijayjayaram 6y ago
    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.
    - nbm 6y ago

kristianp 6y ago

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?

nbm 6y ago
It comes from the paper "The Power of Two Random Choices: A Survey of Techniques and Results" - http://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf http://www.eecs.harvard.edu/~michaelm/postscripts/handbook20...