数据分配

在学习新技术的时候，我习惯先了解该项技术出现的背景，简单来说就是为了解决什么问题而出现的？今天所研究的数据分片出现的背景就是单机无法存储与处理大规模的数据量，只能依靠大规模集群来对这些数据进行存储和处理。

那么，现在要思考的问题就是如何分片并且分配到各个机器中，分片后如何找到某条记录的存储位置——数据路由。延伸还要思考高可用的问题，因为单个分片挂了数据就丢失了，因此需要复制一些副本，但是引入副本就会涉及并发对数据更新时如何保证数据一致性的问题。

此时，脑子可能陷入了一团糟，要思考的问题这么多，怎么才能考虑得全面？传说计算机中的任何问题都可以通过分层或者分治的方法来解决，那么我们分而治之，先不管副本和一致性的问题，先研究一下分片的问题。

抽象模型

从上面的分析，我们需要解决两个问题：

数据如何分片

分片存储到哪里

因此，我们可以抽象出以下模型：

从上面的模型可以看出，Key-partition映射解决的是如何分片的问题，partition-machine映射解决的是分片存储到哪里的问题。这两级映射都是多对一关系，多条记录映射到一个分片，多个分片保存到一台机器。

之所以称之为抽象模型，因为下面所要讨论的三种分片策略都可以映射到这个模型上来。

哈希分片策略

范围分片策略

容量分片策略

哈希分片

哈希分片主要通过哈希函数来建立key-partition 映射关系，所以只支持“点查询”，即根据某个记录的主键（key）获得记录内容，而无法支持“范围查询”，即指定记录的主键范围一次读取多条满足条件的记录。大多数KV存储系统都支持这种方式，比如Dynamo,Cassandra等。

哈希分片一般有以下几种方式：

哈希取模

虚拟桶

一致性哈希

哈希取模

假设有K台物理机器，通过一下哈希函数即可实现数据分片：

K 为物理机器总数，编号为0到K-1，H(key)的数值即为存储该数据的物理机器编号。注意:这种方式对应抽象模型的一二级映射都使用了同一个函数，即分片和机器一一对应了。

哈希取模的优点是实现起来简单，只要哈希函数的散列特性较好,哈希方式可以较为均匀的将数据分布到集群中去。缺点缺乏灵活性，比如要新增一台机器，那么哈希函数就变成了：

这样之前已经分配的数据与存储的物理机器之间的映射完全被打乱了，所有数据必须重新再次分配，这显然是不科学的。如果你有了解java 中HashMap这个数据结构，你会发现它的扩容机制是成倍增加的，因为这样做大概只需移动一半的数据即可。所以在实际的使用中，一般建议是成倍增加机器。

虚拟桶

哈希取模的方式缺点很明显，扩容的时候效率很低，成倍扩增还需要移动一半的机器。归根到底是因为key-partition 映射和partition-machine映射都使用了同样的哈希函数，分片和机器一一对应耦合性太强，我们只需要增加一个中间层来解耦合即可解决这个问题。再次验证文章开头的这句话——计算机中的任何问题都可以通过分层或者分治的方法来解决。这个中间层就是虚拟桶。

key 到虚拟桶的映射还是使用哈希取模的方式，而虚拟桶到机器的映射是采用表格配置的方式。这其实就是上面的抽象模型，虚拟桶就是一个数据分片。

那么，虚拟桶是怎么解决哈希取模中的问题？

试下一下，因为虚拟桶是虚拟的，我们可以假设虚拟桶的个数比机器数大。比如16个虚拟桶，4台机器，这样可以配置四个虚拟桶对应一台机器。当我们需要增加机器扩容时，只需要修改虚拟桶到机器的映射配置即可。

比如虚拟桶0,1,2,3映射到机器1，虚拟桶4,5,6,7映射到机器2，依次类推。假如我们需要增加一台机器，我们可以选择配置虚拟桶0映射到这台机器，虚拟桶1,2,3还是映射在原来的机器，这样我们只需要移动虚拟桶0的数据即可。

一致性哈希

一致性哈希的基本方式是使用一个哈希函数计算数据的哈希值，令该哈希函数的输出值域为一个封闭的环。然后将机器节点随机分布(也可以根据IP和端口哈希)到这个环上，每个节点负责处理从自己开始顺时针至下一个节点的全部哈希值域上的数据。

假设哈希函数的输出值范围在0～31之间，有5台机器，如下图所示：

环上的大圆表示机器节点，比如N14 节点负责存储主键经过哈希后落在6～14范围内的键值数据，而N5 节点则存储30～31以及0～5范围内的键值数据。

上面谈到哈希取模的方式在集群扩容时非常复杂，往往需要倍增节点个数。与此相比，一致性哈希的优点在于可以任意动态添加、删除节点，每次添加、删除一个节点仅影响一致性哈希环上相邻的节点。

一致性哈希算法有很明显的缺点，随机(或根据IP和端口哈希)分布节点的方式使得很难均匀的分布哈希值域，尤其在动态增加节点后，即使原先的分布均匀也很难保证继续均匀。由此带来的另一个较为严重的缺点是，当一个节点异常时，该节点的压力全部转移到相邻的一个节点，当加入一个新节点时只能为一个相邻节点分摊压力。

解决这个问题还是加入一个中间层，中间层大法好啊。跟虚拟桶类似，引入多个虚拟节点，分散到环上的各个位置，然后多个虚拟节点对应一个真实的物理节点。

路由问题

一致性哈希应用于P2P网络时，无中心管理节点，任何一个节点都可以处理查找请求，那么如何根据数据记录的主键以及哈希函数H来定位到记录的内容？

一种简单的方式就是：当一个节点接收到查询请求是，先看看数据是不是在自身节点，如果没有，就转发到后继节点，直接查询到结果为止。这显然是效率低下的。

另一种方式是每个节点都保存一个路由表，路由表的内容是该节点到其他节点的距离映射。先看是不是在后继节点中，不是就查询路由表计算出在哪个节点。

哈希分片缺点

三种哈希分片还有一个共同的缺点，就是在具体的业务中，某个哈希值的数据特别多，那么无论用哪种方式，这个哈希值的数据都会落在同一台机器上，出现数据倾斜问题。例如，某系统中以用户 id 做哈希分数据，当某个用户 id 的数据量异常庞大时，该用户的数据始终由某一台服务器处理，假如该用户的数据量超过了单台服务器处理能力的上限，则该用户的数据不能被处理。更为严重的是，无论如何扩展集群规模，该用户的数据始终只能由某一台服务器处理，都无法解决这个问题。

这种情况可能需要结合多种分片方式解决，比如哈希分片结合后面的按数据量分片。

范围分片

范围分片首先将所有记录的主键进行排序，然后在排好序的主键空间里将记录划分成数据分片，每个数据分片存储有序的主键空间片段内的所有记录。在实现具体存储系统时，往往保持一个数据分片的映射表，记录表每一项记载数据分片的最小主键及其对应的物理机器地址。

工程中，为了数据迁移等负载均衡操作的方便，往往利用动态划分区间的技术，使得每个区间中服务的数据量尽量的一样多。当某个区间的数据量较大时，通过将区间“分裂”的方式拆分为两个区间，使得每个数据区间中的数据量都尽量维持在一个较为固定的阈值之下。

使用范围分片的优点是可以灵活拆分，迁移也很方便，同时避免了数据倾斜问题。缺点是要维护较为复杂的元数据。

按数据量分片

另一类常用的数据分布方式则是按照数据量分布数据。与哈希方式和按数据范围方式不同，数据量分布数据与具体的数据特征无关，而是将数据视为一个顺序增长的文件，并将这个文件按照某一较为固定的大小划分为若干数据块(chunk)，不同的数据块分布到不同的服务器上。与按数据范围分布数据的方式类似的是，按数据量分布数据也需要记录数据块的具体分布情况，并将该分布信息作为元数据使用元数据服务器管理。

按数据量分片的优点和缺点跟范围分片差不多。

应用