大图分布式存储关键技术浅析

辛刚

（中国航空工业集团公司西安航空计算技术研究所，陕西 西安 710065）

1 研究背景及挑战

作为一种重要的数据结构，图具有极强的表示能力，能够描述事物之间的复杂关系，被广泛应用于工程和社会生活的各个领域。比如，公路运输中最优路线的确定，公共卫生学上流行病爆发路径的预测[1,2]。长期以来，有关图的研究一直较为活跃，覆盖图的存储、查询和挖掘等各个方面[3-5]。尤其近年来，伴随互联网信息类型和服务模式的不断丰富和创新，一张张反映事物间复杂关系的大图正在悄然形成。比如，反映用户间互动关系的社交网络图，反映概念实体间依赖关系的知识图谱等。这些大规模、高度结构化的图数据在很大程度上反映真实世界中的关系，蕴藏着重要的商业和学术价值。对这些图数据的分析和挖掘，有望帮助人们找到认识、分析和解决各类问题的新途径。

然而，当前图数据处理技术正面临严峻挑战。首先，图数据规模急剧增长。在社交网络领域，Twitter、Facebook和新浪微博各自的用户数量已达数亿甚至数十亿规模；在语义网领域，Linked Data已包含310亿个RDF（Resource Description Framework）三元组以及超过5亿个RDF链接；在生物信息学领域，人类基因组De Brujin图最坏情况下具有420个顶点[6]。大规模图数据的分析和计算已难以依靠单台高性能的计算机来完成。其次，图数据呈现出显著的动态演化特性，随着时间的推移，新的顶点和边不断产生，原有的顶点和边也可能逐渐消亡。比如，在社交网络中，新用户不断注册，原有用户可能退出，用户间互动频率也在不断发生变化。传统基于静态图的处理技术已无法满足动态演化图的新需求。现实中的大图往往都是动态演化的，后文不加以区分地使用“大图”和“大规模动态演化图”两个术语。

图处理相关的各类技术中，又以存储最为基础。图的存储方式直接决定图数据的访问效率以及图查询与挖掘的效率[6]。研究大规模动态演化图的分布式存储技术具有重要的现实意义。一方面，分布式存储架构支持容量灵活扩充，能够满足图数据规模不断增长的存储容量需求；另一方面，分布式存储降低了单台计算机的存储容量压力，有望实现基于内存的图计算。当前计算机的内存容量普遍处于GB级别，当依靠单台计算机处理数百GB乃至TB级别的图数据时，需要进行频繁的磁盘交互，访问性能低下。而在分布式存储架构下，图数据被分割存储至多台计算机，每台计算机在进行图计算时，可以将数据大部分甚至全部读入内存，极大提高了访问性能。

分布式存储研究由来已久，但大多针对文件数据[7,8]，相关技术无法直接用于大图数据。首先，文件数据被视作互不相干的独立存储任务，但图数据内部深度耦合，加大了分割难度。若在分布式存储时将存在链接关系的大量顶点分开存放，则在数据访问阶段会产生频繁的网络通信，严重影响图数据的访问性能，并降低图计算和图处理的效率。其次，文件数据一般只会访问最新状态，但图数据要求能够重现任意时刻的历史状态，以支持各类历史分析和查询应用。比如，分析在线社交服务中的用户互动，比较不同时刻最具影响力人群的变化；再比如，分析网页超链接图的动态结构，获得不同时刻网页排名的变化[9]。若无特殊说明，后文将基于图当前时刻的查询称为在线分析，而将基于图某个历史时刻的查询称为历史分析。

基于此，大规模动态演化图的分布式存储技术需要解决如下两个难点问题：图的分割问题和图演化历史的重现问题。

2 国内外研究现状

围绕图的分布式存储技术，研究人员开展了大量工作[10-12]。分述如下：

2.1 图分割

图分割一般要求各子图规模尽可能均衡，并且子图间交叉边数量尽可能少（若一条边所关联的两个顶点被分割至两个不同的子图，则称该边为交叉边）。图分割效果一般也通过上述两个指标进行评价。

图分割问题已经被证明是NP完全问题[13]，图论研究领域提出了大量解决该问题的算法，比如，针对无权图的二分问题，Brunetta等人提出了基于线性规划松弛和分离技术序列割的分支切割算法[14]；针对点和边具有权值以及分割数目为任意值情况下的分割问题，Ferreira等人提出加权图的k-路分割切割算法[15]。这些算法能够获得较为精确的分割结果，但时间复杂度较高，所能处理图的规模一般较小。

适用于大图分割的算法大多属于启发式算法，比如，Kernighan和Lin提出的启发式交换点对的KL算法[16]，以及对KL算法改进的FM算法[17]。基于启发式交换算法所能处理的图的顶点数量一般在104以内。为了处理更大规模的图，基于多层次框架的算法被提出，比如Kumar等人提出的METIS算法[18]，其基本思想是通过粗糙化技术将大图缩减到可接受的小图，而后在小图上执行分割，最后再利用反粗糙化技术将小图上的分割还原成原图上的分割。基于多层次框架的算法能够处理百万规模左右的图。

近年来，又出现了可处理数十亿顶点规模图分割问题的MLP算法[19]，该算法主要通过标签传播确定图分割结果，在标签传播中，距离相近的顶点会被标记为相同的标签。针对自然图中顶点度分布极不均衡的问题，上海交通大学陈榕等人提出PowerLyra算法[20]，该算法尽可能减少低度数顶点的副本数量，而只为少数高度数顶点存储较多副本，以少量冗余数据显著减少了交叉边数量。

然而，上述算法只能针对静态图进行处理，难以处理动态图。Vaquero等人提出随着大图结构的不断变化，迭代式地进行顶点迁移，以保持交叉边数量保持在合理的范围[21]。辽宁大学陈宝燕教授团队针对大规模动态演化图的分割问题做了大量工作，提出增量式算法对变化后的大图进行分割[22]。但是，二者都属于延迟更新策略，而非实时在线分割。

目前使用的在线分割算法通常采用随机策略或贪心策略，随机策略以哈希方式确定新顶点所在的顶点子集合，机制简单，但可能导致大量交叉边。贪心策略则选择各顶点子集合中含有最多新顶点邻居的子集合。事实上，新顶点加入时往往只会关联少量顶点，但在随后的演化过程中又可能产生许多新边。仅考虑“眼前利益”的贪心策略仍会造成大量交叉边，分割效果较差。

2.2 图历史查询

快照和日志是记录数据演变过程的两种方法。每一次更新操作都为所有数据存储一个新快照的方法会占用较多的存储空间，对不断动态演化的大图数据并不适用。单纯记录日志的方法可以节约存储空间，但要访问某时刻的图数据时，需要花费时间进行生成。因此，实用的方法大多属于“快照+日志”的混合式方法，仅在某些时刻建立快照，而将两个相邻快照间的更新操作写入日志。当需要访问某个不存在的快照时，借助其相近时刻的已有快照和两时刻间的日志数据临时进行生成。

对“快照+日志”的混合式方法而言，快照和日志数据的排布方式非常关键，直接影响已有快照的访问效率以及生成新快照的效率。日志数据的每条记录关联快照数据的某个部分，若在数据排布时未能考虑这种关联性，则会影响新快照生成的性能。此外，新的快照生成之后，后续分析亦可能需要对其进行分割。若忽略各快照间的联系，将每一个快照视作独立的静态图，则可以通过现有静态图分割算法对其分割。但是，这种方式时间开销很大，影响历史分析的性能。

针对快照和日志数据的排布问题，中国科学技术大学陈恩红和沈向洋教授团队做了大量工作，提出了一种副本相异数据排布方案，即一些副本采用时间维度优先策略，而另一些副本采用空间维度优先策略[23]。无论时间维度优先还是空间维度优先，都针对的是数据在单个磁盘上的排布方式。该方案没有讨论快照和日志数据在分布式存储系统不同计算机间如何排布的问题。

针对新生成快照的分割问题，辽宁大学陈宝燕教授团队提出一种增量式算法[22]。但该算法本质上属于集中式算法，难以借助分布式计算实现并行化工作。

2.3 其它方面

除图分割和图历史重现两个问题之外，容错问题也是大规模动态演化图分布式存储系统必须解决的基本问题。目前主要沿用传统分布式文件存储系统中的容错方法，即将图存储系统中的各类数据（含最新大图数据、快照数据和日志数据）统统看作普通数据进行多副本存储[24]。快照和日志数据自身所具有的容错性没有被有效用于容错算法的优化。

3 存在的问题与未来研究方向

尽管研究人员已经围绕大图的分布式存储技术开展了大量研究工作，当前大图分布式存储系统仍然无法有效满足各类大图应用的实际需求，主要表现如下：

(1)大图在线分析结果的实时性较差。在线分析需要访问图数据最新时刻的状态，然而，由于图数据更新操作需要重新计算图分割，现有技术大多采用延迟更新策略，即仅将更新操作记录下来，积累一段时间后集中进行更新。延迟更新策略影响在线分析结果的实时性。在很多商业领域中，数据分析结果的实时性往往对人们作出正确决策具有至关重要的作用。

(2)大图历史分析的性能较低。历史分析需要访问某一时刻或某些时刻的图数据。考虑到存储效率问题，不可能为任意时刻的图存储快照。现有方法大多以“快照+日志”的方式记录图的演变历史[24]，即仅在某些时刻建立快照，并将两个相邻快照间的更新操作写入日志。当历史分析涉及访问某个不存在的快照时，借助相近时刻的快照和两时刻间的日志数据临时生成该快照。受限于快照和日志数据的排布方式，现有方法生成新快照的时间较长，严重影响了历史分析的性能。

(3)容错成本存在极大浪费。分布式存储系统必须具备容忍各类故障的能力，需要在故障发生时，仍然保证数据的可用性。副本是分布式存储系统最常用的容错技术，比如，分布式文件存储系统GFS[25]通常采用三副本容错。若将这种容错技术直接应用于大规模动态演化图的分布式存储系统，则会造成存储资源和成本的极大浪费。如前文所述，大图分布式存储系统除了存储大图最新时刻的状态之外，还会存储多个快照数据以及用以记录大图更新操作的日志数据。事实上，不同于分布式文件存储系统中的普通文件数据，快照和日志数据自身就具有一定的容错性。比如，快照B可以借助快照A和记录了两快照A、B间更新操作的日志数据来产生，只要快照A和相关日志数据可用，快照B的丢失不会降低数据的可用性。充分利用数据自身的容错性，有望获得更优化的容错方法，在保证数据可用性的前提下，降低存储系统的成本。

由上述分析可知，大图分布式存储技术未能有效解决如下问题：大规模动态演化图的在线分割问题、大图快照的快速生成问题以及图存储的容错优化问题。未来可以围绕上述问题开展进一步的研究工作。

参考文献:

[1]祝园园，秦璐，于旭．图匹配问题的应用和研究[J]．中国计算机学会通讯，2012，8(11)：21-27．

[2]于戈，谷峪，鲍玉斌，王志刚．云计算环境下的大规模图数据处理技术[J]．计算机学报，2011，34(10)：1753-1767.

[3]施佺，肖仰华，鲁轶奇，陈垚亮，王恒山．基于K2树的大图存储优化研究[J]．计算机应用研究，2011，28(7)：2488-2491．

[4]X.Yan，P.S.Yu，and J．Han，Substructure sim ilarity search in graph databases，in SIGMOD Coriference，2005．

[5]U．Kang，D．H．Chau，and C．Faloutsos，M ining large graphs：Algorithms，inference，and discoveries，in ICDE，2011．

[6]冯国栋，肖仰华．大图的分布式存储[J]．中国计算机学会通讯，2012，8(11)：12-16．

[7]M acCorm ick J，Murphy N，Ramasubramanian V，etal.Kinesis：A new approach to replica placement in distributed storage systems[J]． ACM Transactions On Storage(TOS)，2009，4(4)：11．

[8]Thereska E，Donnelly A，Narayanan D．Sierra：practical power-proportionality for data center storage[C]．Proceedings of the 6th ACM conference on Computer systems，2011：169-182．

[9]Yang L，Q i L，Zhao Y P，et al．Link analysis using time series of web graphs[C]．Proceedings of the 16th ACM conference on Information and Know ledge Management，2007：1011-1014．

[10]Low Y，Bickson D，Gonzalez J，et al．Distributed GraphLab：a framework for machine learning and datamining in the cloud[J]．Proceedingsof the VLDB Endowment，2012，5(8)：716-727．

[11]Malew icz G，Austern M H，Bik A JC，etal．Pregel：a system for large-scale graph processing[C]．Proceedingsof the ACM International Conference on Management of Data(SIGMOD)，2010：135-146．

[12]C.Mayer，M.A.Tariq，C.Li，etal.GrapH：heterogeneity-aware graph computation w ith adaptive partitioning.Proceedingsof IEEE InternationalConference of Distributed Computing Systems(ICDCS)，2016：118-128．

[13]Garey M R，Johnson D S，Stockmeyer L．Some simplified NP-complete graph problems[J]．Theoretical Computer Science，1976，1(3)：237-267．

[14]Brunetta L，ConfortiM，R inaldiG．A branch-andcut algorithm for the equicut problem[J]．Mathematical Programming，1997，78(2)：243-263．

[15]Ferreira C E，Maritin A，de Souza C C，et al．The node capacitated graph partitioning problem：A computational study[J]．MathematicalProgramm ing，1998，81(2)：229-256．

[16]Kernighan BW，Lin S．An efficient heuristic procedure for partitioning graphs[J]． Bell system technical journal，1970，49(2)：291-307．

[17]Fiduccia C M，MattheysesR M．A linear-time heuristic for improving network partitions[C]．Proceedings of the 19th IEEEConference on Design Automation，1982：175-181．

[18]Karypis G，Kumar V．Multilevelk-way partitioning scheme for irregular graphs[J]．Journalof Paralleland Distributed computing，1998，48(1)：96-129．

[19]W ang L，Xiao Y，Shao B，et al．How to partition a billion-node graph[C]．Proceedingsof the 30th IEEE InternationalConference on Data Engineering(ICDE)，2014：568-579.

[20]Chen R，Shi J，Chen Y，et al.Powerlyra：Differentiated graph computation and partitioning on skewed graphs[C]．Proceedings of the 10th European Conference on Computer Systems．ACM，2015：1．

[21]Vaquero L，Cuadrado F，Logothetis D，et al．Adaptive partitioning for large-scale dynam ic graphs[C]．Proceedings of the 34th IEEE International Conference on Distributed Computing Systems(ICDCS)，2014：144-153．

[22]单晓欢．大规模演化图的分割技术研究[D]．沈阳：辽宁大学，2014．

[23]苗又山．大规模动态演化图的存储与分析系统研究[D]．中国博士学位论文，中国科学技术大学，2015．

[24]M iao Y，Han W，Li K，et al．ImmortalGraph：a system for storage and analysis of temporal graphs[J]．ACM Transactionson Storage(TOS)，2015，11(3)：14．

[25]Ghemawat S，Gobioff H，Leung S-T．The Google file system[C]．In：Proc．of the 19th Symposium on Operating SystemsPrinciples．2003：29-43．