面向信息网模型的动态数据划分算法

袁嘉立，刘梦赤

(华南师范大学计算机学院，广东 广州 510631)

0 引 言

随着互联网技术的发展，数据正以爆炸式的速度飞速增长。在大数据时代[1]，传统的集中式存储方式由于系统的可用性和可扩展性较低的缺陷无法满足日益增长的数据存储需求。过去10多年，产生了一批构建在集群上的分布式并行数据库[2-4]，它们通过将数据分布在不同节点以及使用副本和日志等方式，提供了良好的水平扩展性和更高的可用性。与此同时，为处理大量半结构化、非结构化数据，NoSQL(Not Only SQL)数据库迅猛发展，涌现了大批如MongoDB、HBase、Neo4J[5]这样的NoSQL数据库。本文在信息网模型[6-8]的基础上，研究并实现分布式信息网数据库管理系统，并针对分布式环境下的复杂查询设计数据动态划分算法。

对于分布式系统来说，数据是否被合理地划分会直接影响查询的性能。对于数据划分方案的选取，需要考虑到分布式系统的负载均衡[9]、可扩展性等性能需求，以及划分所带来的时间和空间开销。传统的数据划分算法主要从负载均衡的角度出发，其中具有代表性的是多级划分算法[10-11]，该算法对于相互独立的数据具有良好的分布式性能，然而对于关联性较高的数据，则会产生较大的通信开销。一致性哈希算法将系统中的物理节点和需要被存储的数据映射到哈希环上的合适位置，根据其相对位置来选取数据的存储节点[12]。研究者在一致性哈希方法的基础上引入虚节点[13]，即每个物理节点根据其处理性能从逻辑上切分为多个虚拟节点，来保证各个处理节点间的负载均衡。但是，上述划分方案由于其划分的随机性，如果数据之间相互关联，在分布式环境中可能造成一个查询任务需要在多个存储节点上完成，同样影响查询效率。

在信息网模型中，每个现实世界中的实体对应于信息网模型数据库中的一个对象，对象之间通过关系进行联系。如果查询需要某个对象相关联的对象信息，则需要根据关系的指向去访问关联对象的信息。当相互关联的2个对象存储在不同节点上时，需要进行跨节点通信，造成昂贵的通信开销。因此，如何进行数据划分使负载均衡的同时最小化通信开销成为一个研究难点。

针对数据划分中的通信开销问题，很多图分割算法在维护数据单元之间的关联关系，减少查询任务跨节点带来的通信开销方向提出了解决方案，如K-balanced图分割算法[14]。K-balanced图分割算法在均衡数据分布的同时，最大程度减少了节点间的通信开销。文献[15]证明了K-balanced图分割算法是一个NP难问题。研究者们提出了很多近似算法以及多层次启发式算法，例如最小切边算法[16-18]从最小化切边数出发减少通信开销。但是随着数据量不断增大，算法本身实现过于复杂，使得算法本身开销抵消了减少的通信开销，在实际开发中不具备实用性。此外，研究者们发现流式图数据分区方法能够在有限的资源下扩展到非常大的图，进而提出了如Taper[19]、WARP[20]、Peng[21]等数据分区算法。然而，上述方法没有考虑到工作负载和图数据特征，导致节点负载的不平衡和节点间的通信开销增加，从而降低查询性能。文献[22]提出一种工作负载自适应流数据分区器WASP。其重新分配策略是动态的而非一次性的，并将主要的元数据信息保持在内存里以保证快速存储和访问。

为解决并行系统中请求本身差异带来的负载不均衡，文献[23]提出一种基于日志的动态数据调整算法。该算法通过历史信息预估下一周期的查询速度，并根据统计的负载差异进行数据动态调整，进而解决因请求差异导致的负载不均衡问题。

结合文献[22]和文献[23]中考虑实际环境动态变化的设计思想，本文提出一种基于信息网模型的关系特性和查询的动态数据调整算法。该算法利用信息网模型的强弱关系特征和历史关系调整信息，得到数据对象之间的初始对象关联值。再通过历史查询信息结合对象间的初始关联值，将相互间关联度较高的数据动态调整到一个处理节点上，进而减少因数据划分不合理导致的通信开销。算法引入对象关联值的概念，用于表示2个对象之间的关联度。在关系的动态调整中，若2个对象之间的关系为强关系，则这一对数据对象拥有更大的初始关联值，侧面反映信息网模型中强关系相比弱关系在对象之间有更大的关联度。当查询过程中产生跨节点跳对象操作，则动态修正2个对象之间的关联值，进一步减少通信开销。同时还引入关系对占比的概念，用于表示一个节点内有关系对象的对数占总对象对数的比值，侧面反映一个节点内不同对象之间的关联度。在数据动态调整的同时，不仅要考虑集群内节点之间数据量的负载均衡，还要考虑节点之间关系对占比的负载均衡，进而使得集群长期查询保持稳定。

1 信息网模型

信息网模型不同于关系模型[24]，是一种基于对象[25]、角色模型[26]的语义数据模型，可以表示现实世界复杂的语义关联。在信息网模型中，现实中的实体被抽象成类，实例则是类的实例化对象。该模型通过引入各种不同的关系类型以及关联层次，实现对于复杂语义的支持。一个关系一般连接着2个对象，以如下语句为例，其描述了“大学”类下的一个实例化对象“华南师范大学”。该对象具有“级别”等属性和“校领导”等关联关系。其中关系contain，它表示对象“华南师范大学”有“学院”这个包含关系，该关系的目标对象之一为对象“计算机学院”，即关系contain连接着“华南师范大学”和“计算机学院”2个对象。除了contain关系，信息网模型中还有普通关系normal(默认关系类型)、角色关系role等多种关联关系。

大学 华南师范大学[

@级别{“211工程院校”，其它}，

@类型:综合型院校，

@主页 https://www.scnu.edu.cn/，

normal校训 “艰苦奋斗、严谨治学、求实创新”，

role校领导 [@任期:4]→{

校长[@级别:正厅级]:王恩科[@上任时间:“2017-9”，@性别:男]，

contain学院:{计算机学院，心理学院，外国语言文化学院，马克思主义学院}];

在信息网模型中，对象中包含对应实体的属性信息以及与其它对象之间的关联信息。当从一个源对象出发想要查询目标对象的内容时，只需要从源对象出发沿着指定的路径跳入目标对象进而获取到最终的查询结果。例如查询“华南师范大学计算机学院的人员情况”，此时需要从“华南师范大学”这个对象出发，沿着“学院”//“计算机学院”这个关联路径跳入到目标对象中，查询其“人员情况”对应的内容，并最终返回查询结果。由此可知，在分布式环境中，如果一个查询涉及复杂的关联路径，对象往往分布在多个处理节点之中，处理节点之间频繁的跳对象操作会导致大量的通信开销。

在分布式环境中，减少不同节点之间通信开销的一个常见思路是使一个查询尽可能在一个处理节点上完成。本文从该思路出发，同时考虑信息网模型的关系特性，结合历史关系信息和查询信息，研究数据动态调整策略，使相互间关联度高的数据尽可能被划分到同一个处理节点上，进而实现一个查询在一个处理节点上执行，在一个调整周期内减少复杂查询的通信开销，并在多个调整周期内保证查询的稳定性。

2 系统架构

本章主要介绍分布式信息网数据库管理系统的整体架构，并结合此架构说明动态数据调整的实现机制。

如图1所示，集群中的节点分为3类：主节点、处理节点和配置节点。其中主节点主要进行任务计划和数据划分，处理节点负责任务的具体执行和数据的具体调整，配置节点则是负责元数据管理。

本文引入对象关联值Rij(Rij≥1)来表示对象i和对象j的关联程度。对象关联值越大，表示对象间的关联性越强，即查询时更容易从一个对象跳入另一个对象。数据的动态划分包含2个阶段:数据的初始划分和数据的动态调整。本文采用一致性哈希作为数据的初始划分策略，并在初次划分的同时将有关系的每对对象的关系类型和初始对象关联值更新到Id-Relation表中。系统在配置节点中动态地维护了Id-Node表与Id-Relation表。Id-Node表用于存储任意一个已经存在的数据对象所在的处理节点。如表1所示，Id-Relation表由一对文档对象、对象之间的关系类型以及对象关联值组成。在信息网模型中，对象间关系类型越强，其关联性往往越强，因此Rij根据对象关系表中对象i和对象j之间的关系类型来定义不同的初始值。若关系类型为弱关系类型normal，对象关联值为初始值1。若关系类型为强关系类型role或contain，对象关联值的初始值为2。

表1 Id-Relation表结构

例如对象O1和对象Oi之间的关系类型为弱关系，其初始对象关联值为1，当前关联值为1。对象O2和对象Oj之间的关系类型为强关系，其初始对象关联值为2，当前关联值为2。

数据的动态调整并行地分为关系动态调整和查询动态调整。当用户发出一个任务请求时，主节点通过Id-Node表获取请求对象所在的处理节点并将任务下发。若该任务请求涉及对象间的关系更新，处理节点则会在接受任务进行处理的同时，在配置节点的表1中根据关系的动态调整策略更新对象之间的关系。若是查询任务，处理节点则会在接受任务进行处理的同时，记录处理过程中产生的通信开销，并结合配置节点中的表1的关系类型，在配置节点的表1中动态更新数据对象之间的关联度，具体的策略在查询的动态调整中介绍。关系动态调整算法的具体描述如下。

算法1 关系动态调整算法。

输入:各个处理节点的关系调整统计信息。

输出:Id-Relation表。

过程:

1)根据修改的统计信息，筛选出关系信息发生变动的数据对象对。

2)依次处理关系信息发生变动的每对数据对象。

3)判断对象之间关系是否修改或新增为S(强关系role、contain)，是就将Id-Relation表中该对对象的对象关联值修改为2后，跳转到步骤2，否则跳转到步骤4。

4)判断对象之间关系是否修改或新增为W(弱关系normal)，是就将Id-Relation表中该对对象的关联值修改为1后，跳转到步骤2，否则跳转到步骤5。

5)判断对象之间关系是否删除，是就将Id-Relation表中该对对象删除后，跳转到步骤2，否则直接跳转到步骤2。

6)得到更新后的Id-Relation表。

3 动态数据调整算法

3.1 对象相关值的动态维护

数据的查询动态调整分为2个阶段：对象关联值的维护和节点之间对象的转移。在第1阶段中，根据查询进行动态调整。当查询过程中涉及跨节点跳对象操作，则对应的Rij进行增加操作。根据配置节点中Id-Node表，若关系类型为弱关系，则进行加1操作。为确保在相同查询频率下强关系类型的对象关联值高于弱关系类型的对象关联值，若关系类型为强关系，则进行加2操作。进入第2阶段，对象的动态调整算法根据第1阶段得到的Rij进行对象的动态调整。

在数据调整的过程中，会统计上一次对象动态调整到目前为止数据操作带来的通信开销Ototal，其中由于节点内通信开销相比于跨节点通信开销可以忽略不计，因此只统计跨节点通信开销Obe。当Ototal超过预设的阈值Omax时，启动对象动态调整。为了防止对象以及对象关系类型调整过于频繁，根据统计情况设置最小调整周期Tmin，即在最小调整周期内，即使Ototal已经超过了阈值，也不会马上进行调整，而是延迟一段时间进行。

3.2 数据的动态调整

当某个周期内Ototal超过预设的阈值Omax时，Id-Relation表停止更新，处理节点根据当前Id-Relation表和查询调整策略进行数据调整。在数据的动态调整过程中，优先处理Ototal较大的节点，因此，首先将各个节点按照Ototal降序排列，然后按照顺序依次处理。

为说明方便，此处引入一个新概念:查询贡献值。前文介绍了对象关联值Rij，用来量化对象i和对象j的关联程度。对象的动态调整是指将对象Oij从节点nodei移动到另一个节点nodej上。对象Oij的查询贡献度量化了由于对象Oij从节点nodei移动到另一个节点nodej后集群整体减少的通信开销，记为Cdec。Cdec计算公式如下：

(1)

其中dj是nodej上的任意对象，RdjOij表示nodej的任意对象dj与对象Oij的对象关联值。Cdec表示了对象Oij从源节点nodei移动到处理节点nodej为集群减少的通信开销量。

针对每个待处理的节点，筛选出产生跨节点通信的对象，并按照对应的查询贡献值降序排列，按照查询贡献值从高到底依次处理。如果查询贡献值大于0，则请求节点移动对集群整体的通信消耗是减少的。另外，考虑到节点间对象个数的负载均衡，各个处理节点上的对象个数应满足以下条件:

ni≤σ(N/p)

(2)

其中，ni表示处理节点i的对象个数；N表示总的对象个数；p表示集群中的节点总数；σ为节点间对象个数的调整因子，侧面反映对节点间对象个数负载不均衡的容忍程度，其值越大，表示容忍程度越高，并根据统计信息获取。

为说明方便，此处引入一个新的概念:关系对占比。除了考虑节点对象个数的负载均衡，针对信息网模型的关系特性，还需要考虑节点间强弱关系占比的负载均衡。例如节点i有ni个对象，则该节点互有关系的对象对最多为(ni-1)!个。由配置节点的Id-Node表可以获取节点i的对象个数，由配置节点的Id-Relation表可以获取节点i当前互有关系的对象对个数，即关系对的个数，因此可以得到节点i的初始关系对占比。另外，由于信息网模型的强弱关系特性，还需考虑强关系相比于弱关系对于对象之间更高的关联度。在满足式(2)的前提下，各个处理节点上的关系占比应满足以下条件：

(3)

对象的动态调整过程中，会先对不同对象产生的通信开销制定对象的调整计划，计划制定完成后，为保证节点对象个数间的负载均衡，必须对式(2)进行验证，在满足的前提下还需保证节点强弱关系占比的负载均衡，再对式(3)进行验证，验证通过则执行调整计划，否则修正调整计划。对于所有需要处理的分片重复上述过程，直至所有的分片都处理结束，至此一次数据的动态调整过程结束。分布式信息网数据库管理系统重新执行用户请求，对象之间的Rij值重新从Id-Relation表中获取，并继续按照查询进行动态维护，循环上述过程。

对象的动态调整策略在减少通信开销的基础上，尽可能地使得划分结果具有较好的负载均衡性。动态调整算法的具体描述如下。

算法2 动态调整算法。

输入:各个处理节点上的查询统计信息。

输出:对象动态调整计划过程。

过程:

1)根据通信开销对各个处理节点进行降序排列。

2)依次处理排序后的每个处理节点。

3)根据查询的记录信息，筛选出产生跨节点通信开销的请求对象，并按查询贡献值进行降序排列(优先处理查询贡献值较大的对象)。

4)依次处理排序后的每个请求对象。

5)判断该请求查询贡献值是否大于0(整体通信开销减少)，是就将该对象加入转移列表中，转到步骤4，否则转到步骤6。

6)判断是否满足节点间对象个数的负载均衡条件，即条件式(2)，是就转到步骤2，否则转到步骤7。

7)判断是否满足节点间强弱关系占比的负载均衡条件，即条件式(3)，是就跳转到步骤2，否则跳转到步骤4。

8)得到对象调整计划。

4 实验结果与分析

本文利用实验对比分析使用较广泛的一致性哈希算法，结合在线查询的动态工作负载特性的自适应流数据分区器WASP，以及综合考虑信息网模型关系特性及查询信息的动态调整算法，测试用例的短期通信开销以及长期的查询稳定性。

实验使用的分布式集群包括8个相同的处理节点、1个主节点以及1个配置节点，每个节点使用主频为3.60 GHz的Intel(R) Core(TM)9700的8核处理器，其内存大小为16 GB，硬盘大小为1 TB，节点间通信使用1000 Mbit/s以太网。集群所有节点均使用Linux64-bit CentOS操作系统，本文系统的所有代码均用C++语言实现。实验基于WatDiv标准合成数据集，该数据集为RDF数据集[27]。WatDiv是一个标准的RDF合成数据集[28]，允许用户自定义自己的数据集并生成不同大小的数据集，本文将数据转换为信息网模型的数据格式(也就是WatDiv40M，将RDF数据集中的400万个顶点转为信息网模型中的400万个数据对象)。

表2给出了实验中要使用的测试用例。Q1～Q4语句和Q5～Q8语句涉及的对象个数逐渐增加，其中，Q1和Q5比较特殊，用于查询一个具体对象的内容，不涉及节点之间的通信。Q1和Q5的设计主要用于测试不同时刻网络环境差异等客观因素对查询速度等指标的影响，对其它查询起到一个参考作用。Q2～Q4和Q6～Q8涉及的节点间通信次数逐渐增加。Q2～Q4和Q6～Q8的设计旨在测试短期内动态调整算法对不同数据请求的优化能力。此外，Q5～Q8涉及的查询对象范围不同于Q1～Q4，且实验将Q1～Q4和Q5～Q8的查询请求放在2个不同的周期内，测试动态调整算法对系统长期查询稳定性的优化能力。

表2 测试用例

4.1 算法性能比较

表3给出了3个调整周期T1～T3内对8个查询请求Q1～Q8在一致性哈希算法、查询调整算法和动态调整算法下的查询时间与通信开销。对Q2～Q4和Q6～Q8简单分析可知，随着复杂查询带来的跨节点通信次数的增加，查询时间也在增长。当通信开销太大时，通信造成的时间开销成为了影响查询速度的首要因素，因此，通信次数的减少会间接加快查询速度。分析实验数据可知，动态调整算法可以使得通信次数减少35%～55%，同时查询时间减少35%左右，因此，该调整策略可以在周期内较大程度提高查询性能。此外，将T3内的错序查询与T1和T2内的查询对比可知，只根据频繁查询模式和图拓扑特征来管理节点重新分配的WASP动态调整算法，在一个调整周期内将有潜在关联的数据尽可能存放在同一个处理节点上，虽然在短期内查询性能有所提升，但没有考虑到信息网模型给数据之间带来的关联，随着时间的增加，在其它周期内重新进行相关对象的查询会有较大性能波动。实验结果表明，动态调整算法即使在不同周期内的同一个查询，其查询时间也在5%～10%的波动区间内，因此该策略保证了系统长期查询的稳定性。

表3 3种调整算法下的通信开销与查询时间对比

4.2 负载均衡测试

动态调整算法调整前后各个处理节点上的对象个数如图2所示。可以看出，动态调整算法调整过后集群中各个节点的对象个数与采用一致性哈希算法进行初次划分的结果较为接近，仍属于相对均衡的状态。实验结果表明，动态数据调整算法在根据对象之间关联性动态调整数据的同时，可使各个处理节点的数据量处于相对均衡的状态。

WASP调整算法与动态调整算法在调整后各个处理节点上的关系对占比如图3所示。由于WASP调整算法未考虑信息网模型的关系特征，各个节点的关系对占比差距很大。而动态调整算法中考虑了节点对象的强弱关系占比，在调整后保证集群整体数据量负载均衡的同时，也使各个节点上的关系对占比达到了相对均衡的状态。

5 结束语

本文基于信息网模型的关系特性，考虑对复杂查询效率可能产生影响的因素，设计了一种基于信息网模型查询的动态数据划分方案。该算法利用历史关系信息和信息网强弱关系特性得到数据对象之间的初始对象关联值，再结合历史查询信息调整对象关联值，进而将关联程度较高的数据对象动态调整到一个处理节点上，减少因跨节点导致的节点间通信开销。实验结果表明，与一致性哈希算法相比，该算法可减少单个周期内35%～55%的查询时间，多个周期的相同查询效率波动降至5%～10%，在加快周期内查询速度的同时，保证了系统长期查询的稳定性。同时集群中的各个处理节点之间拥有相比WASP算法更均衡的关系对占比，优化了分布式环境的整体性能。

考虑到实现的复杂程度，本文中最初的数据划分基于一致性哈希算法实现，并在划分过程中记录了每对数据对象之间的关系信息。一致性哈希算法使得数据均匀随机地被划分到各个处理节点上，导致相互关联的数据极大可能不在同一个处理节点上，因此，数据动态调整算法将会伴随大量的数据交换。此外，当前方案的负载均衡策略基于固定的处理节点数目。当集群中的数据总量过大或过小时，节点的数量需要手动修改，涉及多次初始数据划分及大量数据交换。因此，下一步将研究如何结合信息网模型的特点，设计初始数据划分算法，使得相互关联的数据在初始阶段就被划分到同一个处理节点上，并在后续的数据调整过程中能根据数据量动态调整集群中处理节点的数目，同时保证数据量和关系对占比的负载均衡，使分布式信息网数据库管理系统达到更好的处理性能。