I came across the power of two choices theorem recently, it was referenced in a tech talk about schedulers. The central premise of the power of two choices is simple. Yet it is striking in its effectiveness in making decisions about routing requests. The following is my restatement of the premise: You have n options, and a score or rank associated with each of them. You also have an incoming queue of decisions to make about which option to pick. At each decision point, if you pick two options from the n at random, and then use the score to pick the best among those two, you will get exponentially better results (in terms of distributing load), than choosing a random option. Going from best of two, to best of 3 or 4 or more, only improves the results by a constant factor. Using power of two choices really starts to pay off when n is very large and examining all n options becomes prohibitively expensive. The paper applies this to load balancing, where they showed how effec
There is a great post from 1994 about black triangles in the context of building large and complex systems. You might think that 1994 sounds like the dark ages, but the principles outlined in that post do stand the test of time. Here is my favorite excerpt from that post: What she later came to realize (and explain to others) was that the black triangle was a pioneer. It wasn’t just that we’d managed to get a triangle onto the screen. That could be done in about a day. It was the journey the triangle had taken to get up on the screen. It had passed through our new modeling tools, through two different intermediate converter programs, had been loaded up as a complete database, and been rendered through a fairly complex scene hierarchy, fully textured and lit (though there were no lights, so the triangle came out looking black). The black triangle demonstrated that the foundation was finally complete the core of a fairly complex system was completed, and we were now ready to put it