首先介绍三种分片方式：hash方式，一致性hash（consistent hash），按照数据范围（range based）。对于任何方式，都需要思考以下几个问题：

1. 具体如何划分原始数据集？
2. 当原问题的规模变大的时候，能否通过增加节点来动态适应？
3. 当某个节点故障的时候，能否将该节点上的任务均衡的分摊到其他节点？
4. 对于可修改的数据（比如数据库数据），如果某节点数据量变大，能否以及如何将部分数据迁移到其他负载较小的节点，及达到动态均衡的效果？
5. 元数据的管理（即数据与物理节点的对应关系）规模？元数据更新的频率以及复杂度？
   　　
   为了方便后面分析不同的数据分片方式，假设有三个物理节点，编号为N0， N1， N2，N3；并且，有以下几条记录：
   　　R0: {id: 95, name: 'aa', tag:'older'}
   　　R1: {id: 302, name: 'bb',}
   　　R2: {id: 759, name: 'aa',}
   　　R3: {id: 607, name: 'dd', age: 18}
   　　R4: {id: 904, name: 'ff',}
   　　R5: {id: 246, name: 'gg',}
   　　R6: {id: 148, name: 'ff',}
   　　R7: {id: 533, name: 'kk',}

Hash方式

哈希表（散列表）是最为常见的数据结构，根据记录（或者对象）的关键值将记录映射到表中的一个槽（slot），便于快速访问。哈希表中，最为简单的散列函数是 mod N（N为表的大小）。即首先将关键值计算出hash值（这里是一个整型），通过对N取余，余数即在表中的位置。

数据分片的hash方式也是这个思想，即按照数据的某一特征（key）来计算哈希值，并将哈希值与系统中的节点建立映射关系,从而将哈希值不同的数据分布到不同的节点上。
我们选择id作为数据分片的key，那么各个节点负责的数据如下：

Hash方式节点数据分布
由此可以看到，按照hash方式做数据分片，映射关系非常简单；需要管理的元数据也非常之少，只需要记录节点的数目以及hash方式就行了。

但hash方式的缺点也非常明显：当加入或者删除一个节点的时候，大量的数据需要移动。比如在这里增加一个节点N3，因此hash方式变为了mod 4，数据的迁移如下：

Hash方式节点增加数据分布改变

在这种方式下，是不满足单调性（Monotonicity）的：如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中，哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。

在工程中，为了减少迁移的数据量，节点的数目可以成倍增长，这样概率上来讲至多有50%的数据迁移。

hash方式还有一个缺点，即很难解决数据不均衡的问题。有两种情况：原始数据的特征值分布不均匀，导致大量的数据集中到一个物理节点上；第二，对于可修改的记录数据，单条记录的数据变大。在这两种情况下，都会导致节点之间的负载不均衡，而且在hash方式下很难解决。

一致性Hash

一致性哈希修正了CARP使用的简 单哈希算法带来的问题，使得分布式哈希（DHT）可以在P2P环境中真正得到应用。
一致性hash算法提出了在动态变化的Cache环境中，判定哈希算法好坏的四个定义：

1. 平衡性(Balance)：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。
2. 单调性(Monotonicity)：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。
3. 分散性(Spread)：在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。
4. 负载(Load)：负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同 的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。

一致性hash是将数据按照特征值映射到一个首尾相接的hash环上，同时也将节点（按照IP地址或者机器名hash）映射到这个环上。

对于数据，从数据在环上的位置开始，顺时针找到的第一个节点即为数据的存储节点。也就是说，每一个key的顺时针方向最近节点，就是key所归属的存储节点。

这里仍然以上述的数据为例，假设id的范围为［0， 1000］，N0， N1， N2在环上的位置分别是100， 400， 800，那么hash环示意图与数据的分布如下：

一致性Hash环
一致性Hash节点数据分布
可以看到相比于上述的hash方式，一致性hash方式需要维护的元数据额外包含了节点在环上的位置，但这个数据量也是非常小的。

一致性hash在增加或者删除节点的时候，受到影响的数据是比较有限的，比如这里增加一个节点N3，其在环上的位置为600，因此，原来N2负责的范围段（400， 800］现在由N3（400， 600] N2(600, 800]负责，因此只需要将记录R7(id:533) 从N2,迁移到N3。不难发现一致性hash方式在增删的时候只会影响到hash环上相邻的节点，不会发生大规模的数据迁移。

但是如果按照上述方式，一致性hash方式在增加节点的时候，只能分摊一个已存在节点的压力；同样，在其中一个节点挂掉的时候，该节点的压力也会被全部转移到下一个节点。我们希望的是“一方有难，八方支援”，因此需要在增删节点的时候，已存在的所有节点都能参与响应，达到新的均衡状态。

因此，在实际工程中，一般会引入虚拟节点（virtual node）的概念。即不是将物理节点映射在hash环上，而是将虚拟节点映射到hash环上。虚拟节点的数目远大于物理节点，因此一个物理节点需要负责多个虚拟节点的真实存储。操作数据的时候，先通过hash环找到对应的虚拟节点，再通过虚拟节点与物理节点的映射关系找到对应的物理节点。

引入虚拟节点后的一致性hash需要维护的元数据也会增加：第一，虚拟节点在hash环上的问题，且虚拟节点的数目又比较多；第二，虚拟节点与物理节点的映射关系。但带来的好处是明显的，当一个物理节点失效是，hash环上多个虚拟节点失效，对应的压力也就会发散到多个其余的虚拟节点，事实上也就是多个其余的物理节点。在增加物理节点的时候同样如此。

工程中，Dynamo、Cassandra都使用了一致性hash算法，且在比较高的版本中都使用了虚拟节点的概念。在这些系统中，需要考虑综合考虑数据分布方式和数据副本，当引入数据副本之后，一致性hash方式也需要做相应的调整， 可以参加cassandra的相关文档。

Range based

简单来说，就是按照关键值划分成不同的区间，每个物理节点负责一个或者多个区间。其实这种方式跟一致性hash有点像，可以理解为物理节点在hash环上的位置是动态变化的。
还是以上面的数据举例，三个节点的数据区间分别是N0(0, 200]， N1(200, 500]， N2(500, 1000]。那么数据分布如下：

Range based 节点数据分布

注意，区间的大小不是固定的，每个数据区间的数据量与区间的大小也是没有关系的。比如说，一部分数据非常集中，那么区间大小应该是比较小的，即以数据量的大小为片段标准。在实际工程中，一个节点往往负责多个区间，每个区间成为一个块（chunk、block），每个块有一个阈值，当达到这个阈值之后就会分裂成两个块。这样做的目的在于当有节点加入的时候，可以快速达到均衡的目的。

如果一个节点负责的数据只有一个区间，range based与没有虚拟节点概念的一致性hash很类似；如果一个节点负责多个区间，range based与有虚拟节点概念的一致性hash很类似。

range based的元数据管理相对复杂一些，需要记录每个节点的数据区间范围，特别单个节点对于多个区间的情况。而且，在数据可修改的情况下，如果块进行分裂，那么元数据中的区间信息也需要同步修改。

range based这种数据分片方式应用非常广泛，比如MongoDB, PostgreSQL， HDFS