介绍数据划分方法：轮流放置（Round-Robin）、一致性哈希(Consistent Hashing)和区间划分（Range-based Partitioning）。
一. 轮流放置
轮流放置是最简单的划分方法：即每条元组都会被依次放置在下一个节点上，以此进行循环。一般在实际应用中为了处理的方便，通常按照主键的值来决定次序从而进行划分。即给定一个表T，表T的划分键 (Partitioning Key) 是k，需要划分的节点数目N，那么元组t ∈ T将会被放置在节点n上面，其中n = t.k mod N。由于划分只与划分键有关，因此我们可以把对元组的划分简化为对数字的划分，对于不是数字的键值可以通过其它方式比如哈希转化为数字形式。下面给出一个例子来表示这种划分方式，把9个元组分布到3个节点上的情况。
轮流放置
简单的直接用划分键上的值来计算放置节点的算法可能会造成数据的不均匀。因此，轮流放置有很多改进版，比如说哈希方式（Hashing），即n = hash(t.k) mod N。先将划分键的值进行hash操作，变成一个与输入分布无关、输出均匀的值，然后再进行取模操作。
Pros(优点): 轮流放置算法的实现非常简单，而且几乎不需要元数据就可以进行查询的路由。
Cons(缺点)： 轮流放置当系统中添加或者删除节点时，数据的迁移量非常巨大。
二. 一致性哈希
考虑通常的 hash 算法都是将 value 映射到一个 32 维的 key 值，也即是 0~2^32-1 次方的数值空间；我们可以将这个空间想象成一个首（ 0 ）尾（ 2^32-1 ）相接的圆环，如下面图 1 所示的那样
一致性哈希
把存储对象和存储服务器分别哈希到环上：
一致性哈希
一致性哈希
存储对象按一致的方向落在离它最近的存储服务器上。
Pros:
- 均匀：由于采用的哈希函数通常是与输入无关的均匀函数，因此当键值和节点都非常的多的时候，一致性哈希可以达到很好的分布式均匀性。
- 迁移时数量小：并且由于特殊的放置规则，一致性哈希在节点数据发生变动时可以将影响控制在局部区间内，从而保证非常少的数据迁移（接近理论上的最小值）。当增加一个节点时，只有这个节点所在的区间内的数据需要被重新划分，如下图中，只需要将range 2上面的数据会从node 1中迁移到node 3上面。当删除一个节点时，只需要将这个节点上面的数据迁移到下一个节点上面，比如删除node 3，只把range 2上面的数据迁移到node 1上面就可以并，而其它的数据是不需要迁移变动的。
一致性哈希
三. 区间划分
区间划分是现在很热门的NoSQL数据库MongoDB的sharding方案中所使用的算法。系统会首先把所有的数据划分为多个区间，然后再将这些区间分配到系统的各个节点上面。最简单的区间划分是一个节点只持有一个区间：在有n个节点的情况下，将划分键的取值区间均匀划分（这里的均匀是指划分后的每个partition的数据量尽量一样大，而并非值域区间一样大）为n份，然后每个节点持有一块。例如，按照用户名首字母进行划分，可能有以下的划分方案：
区间划分
如果发生数据分布不均匀的情况，可以通过调整区间分布达到均匀情况，数据迁移同样会很小。
区间划分
但是另外一些情况下，可能会导致连锁迁移。
情况一：数据分布不均，调整导致的连锁迁移
区间划分
情况二：增加或删除节点导致的连锁迁移：
区间划分
为了解决这个问题，MongoDB采用的是每个节点持有多个区间的方案（Multiple range shards）。当需要进行迁移的时候，将持有过多数据的节点上的区间分裂，使得分裂出来的区间刚好满足迁移需要，然后再进行迁移。举例来说 (下图)，如果shard 1中存有[a, f]区间的数据，数据量为500G，此时需要从shard 1上面迁移100G到shard 4，以保证数据的均匀分布。经统计，shard 1中的[a, d]段的数据为400G，[d, f]段数据为100G，因此将shard 1中的[d, f]段的数据直接迁移到shard 4上面。同理，需要从shard 2中迁移100G的数据到shard 3中。这种迁移方式的数据迁移量是理论上的最小值。（简单理解就是节点持有多个不连续区间。）
区间划分
Cons: 每个节点多个区间的做法的缺点是使得对元数据的处理变得复杂，我们需要记录每个节点上面存储的所有区间。但是一般来说，每个节点上面的区间数目不是很大，因此元数据的数目不会很大。这种同时保证了数据的最小迁移，并且实现也比较简单的方案是一个很理想的做法，虽然它的无数据管理和同步上面会有一些问题。
另外，区间划分非常适合处理有区间查询的查询语句，但是也带来很大的一个trade-off。如果一个查询需要访问到多条元组，那么对区间的边界的选取就变得非常棘手，如果选择不当的话，很容易造成一个查询需要在多个节点上面进行运行的情况，这种跨节点的操作会对系统的性能进行很大的影响。
网友评论