随笔档案

负载平衡策略

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

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

2. 数据范围等分+随机分配。为了解决方法1的问题，首先将数据的Hash空间等分为Q = N * S份 (N=机器个数，S=每台机器的虚拟节点数），然后每台机器随机选择S个分割点作为Token。和方法1一样，这种方法的负载也比较均衡，且每台机器都可以对属于每个范围的数据维护一个逻辑上的Merkle Tree，新节点加入/离开时只需扫描部分数据进行同步，并更新这部分数据对应的逻辑Merkle Tree，增量归档也变得简单。该方法的一个问题是对机器规模需要做出比较合适的预估，随着业务量的增长，可能需要重新对数据进行划分。

不管采用哪种方法，Dynamo的负载平衡效果还是值得担心的。

客户端缓存及前后台任务资源分配

客户端缓存机器信息可以减少一次在DHT中定位目标机器的网络交互。由于客户端数量不可控，这里缓存采用客户端pull的方式更新，Dynamo中每隔10s或者读/写操作发现缓存信息不一致时客户端更新一次缓存信息。

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

Dynamo的优点

1. 设计简单，组合利用P2P的各种成熟技术，模块划分好，代码复用程度高。

2. 分布式逻辑与单机存储引擎逻辑基本隔离。很多公司有自己的单机存储引擎，可以借鉴Dynamo的思想加入分布式功能。

3. NWR策略可以根据应用自由调整，这个思想已经被Google借鉴到其下一代存储基础设施中。

4. 设计上天然没有单点，且基本没有对系统时钟一致性的依赖。而在Google的单Master设计中，Master是单点，需要引入复杂的分布式锁机制来解决，且Lease机制需要对机器间时钟同步做出假设。

Dynamo的缺陷

1. 负载平衡相比单Master设计较不可控；负载平衡策略一般需要预估机器规模，不能无缝地适应业务动态增长。

2. 系统的扩展性较差。由于增加机器需要给机器分配DHT算法所需的编号，操作复杂度较高，且每台机器存储了整个集群的机器信息及数据文件的Merkle Tree信息，机器最大规模只能到几千台。

3. 数据一致性问题。多个客户端的写操作有顺序问题，而在GFS中可以通过只允许Append操作得到一个比较好的一致性模型。

4. 数据存储不是有序，无法执行Mapreduce；Mapreduce是目前允许机器故障，具有强扩展性的最好的并行计算模型，且有开源的Hadoop可以直接使用，Dynamo由于数据存储依赖Hash无法直接执行Mapreduce任务。