5.1.4　负载均衡

Dynamo的负载均衡取决于如何给每台机器分配虚拟节点号，即token。由于集群环境的异构性，每台物理机器包含多个虚拟节点。一般有如下两种分配节点号的方法。

●随机分配。每台物理节点加入时根据其配置情况随机分配S个Token。这种方法的负载平衡效果还是不错的，因为自然界的数据大致是比较随机的，虽然可能出现某段范围的数据特别多的情况（如baidu、sina等域名下的网页特别多），但是只要切分足够细，即S足够大，负载还是比较均衡的。这个方法的问题是可控性较差，新节点加入/离开系统时，集群中的原有节点都需要扫描所有的数据从而找出属于新节点的数据，Merkle树也需要全部更新；另外，增量归档/备份变得几乎不可能。

●数据范围等分+随机分配。为了解决上种方法的问题，首先将数据的哈希空间等分为Q=N×S份（N=机器个数，S=每台机器的虚拟节点数），然后每台机器随机选择S个分割点作为Token。和上种方法一样，这种方法的负载也比较均衡，并且每台机器都可以对属于每个范围的数据维护一颗逻辑上的Merkle树，新节点加入/离开时只需扫描部分数据进行同步，并更新这部分数据对应的逻辑Merkle树，增量归档也变得简单。

另外，Dynamo对单机的前后台任务资源分配也做了一些工作。Dynamo中同步操作、写操作重试等后台任务较多。为了不影响正常的读写服务，需要对后台任务能够使用的资源做出限制。Dynamo中维护一个资源授权系统。该系统将整个机器的资源切分成多个片，监控60秒内的磁盘读写响应时间，事务超时时间及锁冲突情况，根据监控信息算出机器负载从而动态调整分配给后台任务的资源片个数。