Google论文Consistent Hashing with Bounded Loads的背景知识。
最近看到Google一篇论文Consistent Hashing with Bounded Loads，提出一种新的算法，使得在动态负载均衡的场景中，增删节点的时候流量切换更加平缓。
可以通过参考wiki百科Balls into bins，了解其背后的原理。
在计算机科学中，常常会有资源分配的问题，其中一个典型的例子是分布式服务的负载均衡：可以简单地理解为有n个桶(服务器)，需要装下m个球(客户端)。为了能让客户端尽可能随机分布在各个服务器，以保证服务器资源的平衡，比较常见的做法是通过计算给每个客户端生成一个一致性hash值，映射到服务器。实际上对大多数服务而言，m是一个无穷的值，因为客户端的请求总是源源不断地涌来。但当服务器稳定运行时，单位时间服务器需要处理的请求可以认为是近似固定的。
首先提出一种最均衡的方式，那就是每个球在投放之前，先判断每个桶当前的装球量，然后选取负载最低的桶，但实际应用中因为查询已占用资源的也有明显的开销，所以通常并不会这样做。
考虑一种特殊情况：m=n，比较容易理解，如果在这种情况下能够达到负载均衡，那么在m>n的情况下，理论上也总是能够分配均衡。
进一步，当m=n的时候，如果随机把n个球放进n个桶里，那么一定会有一个或多个桶分配的球比其他的桶多，导致分布并不像想象中那么均匀，因为每个球都有1/n的概率被丢到这个桶里。
一种优化的方案是，每个球先随机选取2个桶，然后判断这两个桶当前的装球量，最后选择负载的桶来投放。按照计算结果，已经能极大程度地满足负载均衡和快速选取资源的需要。