分布式系统－－数据分布方式

分布式系统如何拆解输入数据，将数据分发到不同的机器中。下面将介绍几种不同的数据分布方式。
一：哈希方式
哈希方式是最常见的数据分布方式,其方法是按照数据的某一特征计算哈希值,并将哈希值与机器中的机器建立映射关系,从而将不同哈希值的数据分布到不同的机器上。所谓数据特征可以是key-value 系统中的 key,也可以是其他与应用业务逻辑相关的值。

只要哈希散列性比较好，数据就能均匀到分发到不同机器中。同时,需要管理的元信息很少,只需要知道哈希函数和模（一般是机器总数）。
但是有个明显的缺点,扩展性很差。如果我想把集群规模扩大,可能所有的数据需要被重新迁移。工程中,扩展哈希分布数据的系统时,往往使得集群规模成倍扩 展,按照数据重新计算哈希,这样原本一台机器上的数据只需迁移一半到另一台对应的机器上即可 完成扩展。针对哈希方式扩展性差的问题,一种思路是不再简单的将哈希值与机器做除法取模映射,而是将对应关系作为元数据由专门的元数据服务器管理。访问数据时,首先计算哈希值并查询元数据服务器,获得该哈希值对应的机器。同时,哈希值取模个数往往大于机器个数,这样同一台机器上需要负责多个哈希取模的余数。不过，需要管理的元数据就多了。
另外，如果作为哈希函数的key的某个值出现了严重不均，就容易出现“数据倾斜”。比如以用户ID作为特征值，偏偏用户ID＝1的数据特别多，这样就悲剧了。

二：按数据范围分布
按数据范围分布是另一个常见的数据分布式,将数据按特征值的值域范围划分为不同的区间,使得集群中每台(组)服务器处理不同区间的数据。


对于上面哈希方式某个用户数据特别多我们就可以通过采用数据范围分布解决,动态划分范围空间,实现负载均衡（类似B树）。
按数据范围分布数据需要记录所有的数据分布情况。一般的,往往需要使用专门的服务器在内存中维护数据分布信息, 称这种数据的分布信息为一种元数据。
实际工程中,一般也不按照某一维度划分数据范围,而是使用全部数据划分范围,从而避免数据倾斜的问题。
使用范围分布数据的方式的最大优点就是可以灵活的根据数据量的具体情况拆分原有数据区间, 拆分后的数据区间可以迁移到其他机器,一旦需要集群完成负载均衡时,与哈希方式相比非常灵活。 另外,当集群需要扩容时,可以随意添加机器,而不限为倍增的方式,只需将原机器上的部分数据 分区迁移到新加入的机器上就可以完成集群扩容。而缺点就是元数据可能会成为瓶颈。

三：按数据量分布
数据量分布数据与具体的数据特征无关,而是将数据视为一个顺序增长的文件,并将这个文件按某 一较为固定的大小划分为若干数据块(chunk),不同的数据块分布到不同的服务器上。与按数据范 围分布数据的方式类似的是,按数据量分布数据也需要记录数据块的具体分布情况,并将该分布信 息作为元数据使用元数据服务器管理。
按数据量分布数据的方式一般没有数据倾斜的问题,数据总是被均匀切分并分布到集群中。当集群需要重新负载均衡时,只需通过迁移数据块即可完成。集群扩容 也没有太大的限制,只需将部分数据库迁移到新加入的机器上即可以完成扩容。按数据量划分数据的缺点是需要管理较为复杂的元数据。

四：一致性哈希
一致性哈希的基本方式是使用一个哈希函数计算数据或数据特征的哈希值,令该哈希函数的输出值域为一个封闭的环,即哈希函数输出的最大值是最小值的前序。将节点随机分布到这个环上,每节点负责处理从自己开始顺时针至下一个节点的全部哈希值域上的数据。


节点 A 负责的值域范围为[1,4),节点 B 负责的范围为[4, 9), 节点 C 负责的范围为[9, 10)和[0,1)。
一致性哈希的优点在于可以任意动态添加、删除节点,每次添加、删除一个节点仅影响一致性哈希环上相邻的节点。
但也有很明显的缺点,随机分布节点的方式使得很难均匀的分布哈希值域,尤其在动态增加节点后,即使原先的分布均匀也很难保证继续均匀,由此带来的另一个较为严重的缺点是,当一个节点异常时,该节点的压力全部转移到相邻的一个节点,当加入一个新节点时只能为一个相邻节点分摊力。
为此，一种改进是引入“虚节点”的概念。系统初始时就创建许多虚节点, 虚节点的个数一般远大于未来集群中机器的个数,将虚节点均匀分布到一致性哈希值域环上,其功能与基本一致性哈希算法中的节点相同。为每个节点分配若干虚节点。操作数据时,首先通过数据的哈希值在环上找到对应的虚节点,进而查找元数据找到对应的真实节点。这样,一旦某个节点不可用,该节点将使得多个虚节点不可用,从而使得多个相邻的真实节点负载失效节点的压里。同理,一旦加入一个新节点,可以分配多个虚节点,从而使得新节点可以负载多个原有节点的压力,从全局看,较容易实现扩容时的负载均衡。

一般,我们可以把哈希分布数据方式与按数据量分布数据方式组合使用。按用户 id 的哈希值分数据,当某个用户 id 的数据量特别大时, 该用户的数据始终落在某一台机器上。此时,引入按数据量分布数据的方式,统计用户的数据量, 并按某一阈值将用户的数据切为多个均匀的数据段,将这些数据段分布到集群中去。由于大部分用 户的数据量不会超过阈值,所以元数据中仅仅保存超过阈值的用户的数据段分布信息,从而可以控 制元数据的规模。

参考：分布式系统原理介绍.pdf