Reading "The Power of Two Choices," by Michael David Mitzenmacher

Use two choices. It's easy to get hugely better performance by moving from one choice to two choices. It's very hard to do better.

The full title is The Power of Two Choices in Randomized Load Balancing, by Michael David Mitzenmacher.

I love the simple theory of this: use two choices.

Two choices is exponentially better than one choice, and having three or more choices don't offer much more improvement.

  • Need to hash? Hash it twice, then choose the bucket with fewer items.
  • Need to load balance? Choose two servers at random, then pick the one with less traffic.
  • Need to cache? TWO CHOICES.

The math of this thesis is beyond me, but that's true of most compsci theses now. (Can anyone retain their math knowledge if they're not actively teaching or publishing?)

I love papers with simple and powerful takeaways.

Comments

(Commenting is closed. Please tweet me at @landedstar instead.)

┼╝aden.

PHP Startup: memcached.sess_lock_wait and memcached.sess_lock_max_wait are deprecated. Please update your configuration to use memcached.sess_lock_wait_min, memcached.sess_lock_wait_max and memcached.sess_lock_retries
The error has been logged in /anchor/errors.log
Uncaught Exception

Uncaught Exception

PHP Startup: memcached.sess_lock_wait and memcached.sess_lock_max_wait are deprecated. Please update your configuration to use memcached.sess_lock_wait_min, memcached.sess_lock_wait_max and memcached.sess_lock_retries

Origin

on line 0

Trace

#0 [internal function]: System\Error::shutdown()
#1 {main}