所谓分布式系统，就是利用多个独立的计算机来解决单个节点（计算机）无法处理的存储、计算问题，这是非常典型的分而治之的思想。每个节点只负责原问题（即整个系统需要完成的任务）的一个子集，那么原问题如何拆分到多个节点？在分布式存储系统中，任务的拆分即数据分片。
何为数据分片（segment，fragment， shard， partition），就是按照一定的规则，将数据集划分成相互独立、正交的数据子集，然后将数据子集分布到不同的节点上。注意，这里提到，数据分片需要按照一定的规则，不同的分布式应用有不同的规则，但都遵循同样的原则：按照最主要、最频繁使用的访问方式来分片。
本文主要介绍分布式系统中的分片相关问题，包括三种分布方式：hash、一致性hash、range based，以及各自的优缺点。
三种数据分片方式
首先介绍三种分片方式：hash方式，一致性hash（consistent hash），按照数据范围（range based）。对于任何方式，都需要思考以下几个问题：
具体如何划分原始数据集？
当原问题的规模变大的时候，能否通过增加节点来动态适应？
当某个节点故障的时候，能否将该节点上的任务均衡的分摊到其他节点？
对于可修改的数据（比如数据库数据），如果某节点数据量变大，能否以及如何将部分数据迁移到其他负载较小的节点，及达到动态均衡的效果？
元数据的管理（即数据与物理节点的对应关系）规模？元数据更新的频率以及复杂度？
为了后面分析不同的数据分片方式，假设有三个物理节点，编号为N0， N1， N2；有以下几条记录：
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），便于快速访问。绝大多数编程语言都有对hash表的支持，如python中的dict， C++中的map，Java中的Hashtable， Lua中的table等等。在哈希表中，最为简单的散列函数是 mod N（N为表的大小）。即首先将关键值计算出hash值（这里是一个整型），通过对N取余，余数即在表中的位置。
数据分片的hash方式也是这个思想，即按照数据的某一特征（key）来计算哈希值，并将哈希值与系统中的节点建立映射关系,从而将哈希值不同的数据分布到不同的节点上。
我们选择id作为数据分片的key，那么各个节点负责的数据如下：
由此可以看到，按照hash方式做数据分片，映射关系非常简单；需要管理的元数据也非常之少，只需要记录节点的数目以及hash方式就行了。
但hash方式的缺点也非常明显：当加入或者删除一个节点的时候，大量的数据需要移动。比如在这里增加一个节点N3，因此hash方式变为了mod 4，数据的迁移如下：
在这种方式下，是不满足单调性（Monotonicity）的：如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。
在工程中，为了减少迁移的数据量，节点的数目可以成倍增长，这样概率上来讲至多有50%的数据迁移。
hash方式还有一个缺点，即很难解决数据不均衡的问题。有两种情况：原始数据的特征值分布不均匀，导致大量的数据集中到一个物理节点上；第二，对于可修改的记录数据，单条记录的数据变大。在这两种情况下，都会导致节点之间的负载不均衡，而且在hash方式下很难解决。
一致性hash
一致性hash是将数据按照特征值映射到一个首尾相接的hash环上，同时也将节点（按照IP地址或者机器名hash）映射到这个环上。对于数据，从数据在环上的位置开始，顺时针找到的第一个节点即为数据的存储节点。这里仍然以上述的数据为例，假设id的范围为［0， 1000］，N0， N1， N2在环上的位置分别是100， 400， 800，那么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]。那么数据分布如下：
注意，区间的大小不是固定的，每个数据区间的数据量与区间的大小也是没有关系的。比如说，一部分数据非常集中，那么区间大小应该是比较小的，即以数据量的大小为片段标准。在实际工程中，一个节点往往负责多个区间，每个区间成为一个块（chunk、block），每个块有一个阈值，当达到这个阈值之后就会分裂成两个块。这样做的目的在于当有节点加入的时候，可以快速达到均衡的目的。
不知道读者有没有发现，如果一个节点负责的数据只有一个区间，range based与没有虚拟节点概念的一致性hash很类似；如果一个节点负责多个区间，range based与有虚拟节点概念的一致性hash很类似。
range based的元数据管理相对复杂一些，需要记录每个节点的数据区间范围，特别单个节点对于多个区间的情况。而且，在数据可修改的情况下，如果块进行分裂，那么元数据中的区间信息也需要同步修改。
range based这种数据分片方式应用非常广泛，比如MongoDB, PostgreSQL， HDFS
小结：
在这里对三种分片方式（应该是四种，有没有virtual node的一致性hash算两种）进行简单总结，主要是针对提出的几个问题：
映射难度元数据节点增删数据动态均衡
hash方式简单非常简单，几乎不用修改需要迁移的数据比较多不支持
consistent hash
without virtual node简单比较简单，取决于节点规模，几乎不用修改增删节点的时候只影响hash环上相邻节点，但不能使所有节点都参与数据迁移过程不支持
consistent hash
with virtual node中等稍微复杂一些，主要取决于虚拟节点规模，很少修改需要迁移的数据比较少，且所有节点都能贡献部分数据若支持（修改虚拟节点与物理节点映射关系）
range based较为复杂取决于每个块的大小，一般来说规模较大；且修改频率较高需要迁移的数据比较少，且所有节点都能贡献部分数据支持，且比较容易
上面的数据动态均衡，值得是上述问题的第4点，即如果某节点数据量变大，能否以及如何将部分数据迁移到其他负载较小的节点。
BB财经原创，作者：区块链百科，转载请注明出处：http://www.bbcaijing.cn/baike/13133.html
