当前NoSQL的分布式存储系统的资料(包括Paper以及各大Blog上的内容),大部分都是关于分布式Key-Value存储下的读写操作、数据一致性、节点失效与修复等问题上,很少有系统的提及有关Load Balance的处理。不过既NoSQL指导型原则是CAP原理,而系统在实现时无论偏重AP还是CP,P都是必选的,因此对于分布式的各个节点的负载均衡也应该是要面对的问题,不过很遗憾,在BigTable, Dynamo以及Cassandra的Paper中对于Load Balance基本都没有提及,都只是很简单的进行了说明。特地花了几天去找了一些资料,总结记录于此。

1. Dynamo

Dynamo的论文上对于Load Balance的提及基本就是一个关键词”uniform hashing”,”A uniform key distribution can help us achieve uniform load distribution assuming the access distribution of keys is not highly skew“。即通过均匀的hash函数,保证将所有的key以及node都可以均匀的分布到同一哈希地址空间上,从而实现负载的均衡,此类常用的函数包括MD5 hash函数和SHA-1 hash函数。

除了利用哈希函数使得整个存储的item被均匀的分配到整个地址空间上,此外Dynamo的Virtual Node机制也对负载均衡进行一定的帮助,根据机器的性能指标不同划分不同的VNode即可。

此外,当新的VNode启动以及离开时,需要将某个VNode的数据迁移至邻居节点,而此种迁移有时会带来比较大的计算量(Merkle Tree等),因此Dynamo又采用了一个将整个地址空间划分成段的策略(如下图所示),然后每个VNode只能在一个段边界位置进行添加,即每一个VNode管理段长的整数倍的地址空间,此种方式对于节点的启动以及恢复,数据的归档等都有好处。

由于Dynamo虽然是NoSQL数据库的雏形以及类white paper,但由于工业界基于此模型构建实际针对业务数据库并是特别认可,因此资料也较少。

2.  Cassandra

Cassandra首先包含了两种Partitioner,这两种Partitioner对负载均衡的影响完全不同。

RandomPartitioner: RandomPartitioner采用均匀的hash函数,将负载均匀的划分到Key space空间上。RandomPartitioner gives you pretty good load balancing with no further work required。不过由于hash函数会将连续的Key映射到不同的环上地址,缺点就是无法进行range query.
OrderPreservingPartitioner:OrderPreservingPartitioner会使得连续的key映射到环上的地址空间后也是连续的,因此支持range query. OrderPreservingPartitioner let u perform range queries on the keys, but requires choosing node tokens carefully and active load balancing.

也就是说RandomPartitioner几乎是不需要进行Load Balancing的,但对于后者,就需要在Load Balancing上下一点功夫。

阅读全文…

, , , ,