分布式系统数据分布

【摘 要】分布式系统面临的第一个问题就是数据分布,即将数据均匀地分布到多个存储节点.分布式系统区别于传统单机系统在于能够将数据分布到多个节点,并在多个节点之间实现负载均衡.数据分布的方式主要有两种,一种是哈希分布,如一致性哈希,代表系统为Amazon的Dynamo系统,另外一种方法是顺序分布,即每张表格上的数据按照主键整体有序.

【关 键 词】分布式系统,数据分布,哈希分布,顺序分布,负载均衡

1.数据分布

将数据分散到多台机器后,需要尽量保证多台机器之间的负载是比较均衡的.衡量机器负载涉及的因素很多,如机器Load值,CPU,内存,磁盘以及网络等资源使用情况,读写请求数及请求量,等等,分布式存储系统需要能够自动识别负载高的节点,当某台机器的负载较高时,将它怎么写作的部分数据迁移到其他机器,实现自动负载均衡.分布式存储系统的一个基本要求就是透明性,包括数据分布透明性,数据迁移透明性,数据复制透明性,故障处理透明性.

2.哈希分布

哈希取模的方法很常见,其方法是根据数据的某一种特征计算哈希值,并将哈希值与集群中的怎么写作器建立映射关系,从而将不同哈希值的数据分布到不同的怎么写作器上.所谓数据特征可以是key-value系统中的主键（key）,也可以是其他与业务逻辑相关的值.例如,将集群中的怎么写作器按0到N-1编号（N为怎么写作器的数量）,根据数据的主键（hash（key）%N）或者数据所属的用户id（hash（user_id）%N）计算哈希值,来决定将数据映射到哪一台怎么写作器.

如果哈希函数的散列特性很好,哈希方式可以将数据比较均匀地分布到集群中去.而且,哈希方式需要记录的元信息也非常简单,每个节点只需要知道哈希函数的计算方式以及模的怎么写作器的个数就可以计算出处理的数据应该属于哪台机器.

然而,找出一个散列特性很好的哈希函数是很难的.这是因为,如果按照主键散列,那么同一个用户id下的数据可能被分散到多台怎么写作器,这会使得一次操作同一个用户id下的多条记录变得困难,如果按照用户id散列,容易出现“数据倾斜”（dataskew）问题,即某些大用户的数据量很大,无论集群的规模有多大,这些用户始终由一台怎么写作器处理.

处理大用户问题一般有两种方式,一种方式是手动拆分,即线下标记系统中的大用户（例如运行一次MapReduce作业）,并根据这些大用户的数据量将其拆分到多台怎么写作器上.这就相当于在哈希分布的基础上针对这些大用户特殊处理,另一种方式是自动拆分,即数据分布算法能够动态调整,自动将大用户的数据拆分到多台怎么写作器上.

传统的哈希分布算法还有一个问题：当怎么写作器上线或者下线时,N值发生变化,数据映射完全被打乱,几乎所有的数据都需要重新分布,这将带来大量的数据迁移.一种思路是不再简单地将哈希值和怎么写作器个数做除法取模映射,而是将哈希值与怎么写作器的对应关系作为元数据,交给专门的元数据怎么写作器来管理.访问数据时,首先计算哈希值,再查询元数据怎么写作器,获得该哈希值对应的怎么写作器.这样,集群扩容时,可以将部分哈希值分配给新加入的机器并迁移对应的数据.

另一种思路就是采用一致性哈希（Dist-ributedHashTable,DHT）算法.算法思想如下：

给系统中每个节点分配一个随机token,这些token构成一个哈希环.执行数据存放操作时,先计算Key（主键）的哈希值,然后存放到顺时针方向第一个大于或者等于该哈希值的token所在的节点.一致性哈希的优点在于节点加入/删除时只会影响到在哈希环中相邻的节点,而对其他节点没影响.可以看出,一致性哈希算法在很大程度上避免了数据迁移.为了查找集群中的怎么写作器,需要维护每台机器在哈希环中位置信息,常见的做法如下.

（1）O（1）位置信息

每台怎么写作器记录它的前一个以及后一个节点的位置信息.这种做法的维护的节点位置信息的空间复杂度为O（1）,然而每一次查找都可能遍历整个哈希环中的所有怎么写作器,即时间复杂度为O（N）,其中,N为怎么写作器数量.

（2）O（logN）位置信息

检测设哈希空间为0～2n（即N等于2n）,以Chord系统为例,为了加速查找,它在每台怎么写作器维护了一个大小为n的路由表（fingertable）,FTP[i]等于succ（p+2i-1）,其中p为怎么写作器在哈希环中的编号,路由表中的第i个元素记录了编号为p+2i-1的后继节点.通过维护O（logN）的位置信息,查找的时间复杂度改进为O（logN）.

3.顺序分布

哈希散列破坏了数据的有序性,只支持随机读取操作,不能够支持顺序扫描.某些系统可以在应用层做折衷,比如互联网应用经常按照用户来进行数据拆分,并通过哈希方法进行数据分布,同一个用户的数据分布到相同的存储节点,允许对同一个用户的数据执行顺序扫描,由应用层解决跨多个用户的操作问题.另外,这种方式可能出现某些用户的数据量太大的问题,由于用户的数据限定在一个存储节点,无法发挥分布式存储系统的多机并行处理能力.

顺序分布在分布式表格系统中比较常见,一般的做法是将大表顺序划分为连续的范围,每个范围称为一个子表,总控怎么写作器负责将这些子表按照一定的策略分配到存储节点上.为了支持更大的集群规模,Bigtable这样的系统将索引分为两级：根表以及元数据表（Meta表）,由Meta表维护User表的位置信息,而Root表用来维护Meta表的位置信息.读User表时,需要通过Meta表查找相应的User子表所在的存储节点,而读取Meta表又需要通过Root表查找相应的Meta子表所在的存储节点.

顺序分布与B+树数据结构比较类似,每个子表相当于叶子节点,随着数据的插入和删除,某些子表可能变得很大,某些变得很小,数据分布不均匀.如果采用顺序分布,系统设计时需要考虑子表的分裂与合并,这将极大地增加系统复杂度.子表分裂指当一个子表太大超过一定阀值时需要分裂为两个子表,从而有机会通过系统的负载均衡机制分散到多个存储节点.子表合并一般由数据删除引起,当相邻的两个子表都很小时,可以合并为一个子表.一般来说,单个怎么写作节点能够怎么写作的子表数量是有限的,比如4000～10000个,子表合并的目的是为了防止系统中出现过多太小的子表,减少系统中的元数据.

4.负载均衡

分布式存储系统的每个集群中一般有一个总控节点,其他节点为工作节点,由总控节点根据全局负载信息进行整体调度.工作节点刚上线时,总控节点需要将数据迁移到该节点,另外,系统运行过程中也需要不断地执行迁移任务,将数据从负载较高的工作节点迁移到负载较低的工作节点.

5.结论

数据的分布对数据的管理提出了更高的要求.分布式数据库管理系统具有管理分布数据的功能,使用户不感到数据是分布的,即用户不必知道数据是否分片、是否有复本数据存放在哪个节点上以及事务在哪几个节点上执行并能保证前后数据的一致性.具有以上所有功能的分布式数据库系统就是分布透明的.

目前的数据库产品大都是基于关系模式的,只能提供部分分布式系统的功能,要真正实现分布式系统的所有功能还需进行多方面的探索.

作者简介：陈宇（1991―）,河南洛阳人,现就读于郑州大学信息工程学院计算机科学与技术专业.