分布式图存储系统关键技术设计与实现

发布时间：2022-01-05 23:13

　　近年来,超大规模复杂图和社交图的处理成为业界关注的热点问题。与传统数据处理相比,除规模超大外,数据往往表现为逻辑上的图结构,数据的处理表现为点和边不断迭代。传统关系型数据库在存储和处理两方面对大规模图数据的支持有限,本文主要讨论在构建分布式图数据库中存储方面的关键问题。在分布式图存储系统中,图的存储策略和划分算法对整个系统起着很重要的作用。优秀的划分算法能最大限度保留图自身结构,减少切割边规模,保证子分区内部的邻近性,这能从根本上减少处理数据时带来的网络开销。存储策略则负责为划分后的图构建存储模型,高效组织数据索引,为查询和写入提供支撑。本文着重关注三个方面,一是提高划分算法并行执行效率并保证一定划分效果;二是设计针对图数据特点的数据模型;三是针对图数据设计和实现一套可靠的分布式存储解决方案。本文所做的工作主要如下:1)首先介绍图数据库的产生和发展,然后分析当前图数据库对底层图存储系统的需求,并介绍图划分算法的分类和研究现状。最后深入研究实现分布式图存储系统所需要的相关技术。2)本文研究了当前图数据领域主流划分算法,分析各自的优缺点。对HDRF划分算法在并行执行场景下的划分效率进行优化... 

【文章来源】：电子科技大学四川省 211工程院校 985工程院校 教育部直属院校

【文章页数】：84 页

【学位级别】：硕士

【部分图文】：

算法执行时间开销对比图

电子科技大学硕士学位论文60第五章测试本章测试的对象主要分为两个部分：划分算法和图存储系统。每个部分分别以功能测试和性能测试两个方面来展示。其中功能测试包括划分算法的导入和划分后分区的负载均衡以及图存储系统的数据写入和查询功能。性能测试包括划分算法的执行时间和划分效果以及图存储系统的吞吐能力。5.1P-HDRF划分算法测试5.1.1测试环境表5-1划分算法测试配置表CPUIntel(R)Xeon(R)CPUE5-2603@1.80GHz内存62GB网卡1000Mb/s硬盘256G操作系统Linuxubuntu4.4.0-161-generic(x86_64)开发工具Vim5.1.2图划分算法功能测试P-HDRF功能测试主要是为了测试其是否能保证分区的负载均衡。负载均衡的测试数据是社交平台的开源数据。划分算法从本地磁盘读入数据，并将其划分为为4个子分区。我们分别以两个数量级的数据做了测试，测试结果如图5-1和图5-2所示。图5-1数据集一测试结果图

第五章测试61由图5-1可知，该测试文件约有八十二万八千条边、七万七千个顶点。划分之后，所有子分区的最大负载和最小负载如图5-1中红线框所示,分区的负载能够达到很好的均衡状态。图5-2数据集二测试结果图图5-2所示的测试文件总共有一千万条边、五百一十五万个顶点。划分之后每个分区的负载依然能够保证负载均衡。图5-2第一处红线框的数据依次为划分后总顶点数和划分前的总顶点数。第二处红线框的数据表明分区负载的最大顶点和边数量以及负载最少的顶点和边数量。结合这三个指标可以得出，改进后的算法能够满足划分后分区负载均衡的目标，并且通过这几个指标和重复度因子也可以看出算法的划分效果也符合预期。5.1.3图划分算法性能测试5.1.3.1窗口值的测试本文提出的P-HDRF版本是针对HDRF划分算法在并行处理场景中的优化。在优化算法中我们引入了窗口，在实际测试中，窗口值的变化会引起算法执行效率的变化。图5-3测试在不同线程数下调节窗口值的大小，然后测试划分算法执行的时间开销。由图可知，在将线程数设置为1的情况下，增大窗口值后算法的执行时间会明显减少，尤其在增大窗口值的初期，执行时间减少得最明显。当把窗口值设定为比16更大时，执行时间并没有明显的变化。测试实验增加了对比数据，引入了不同线程数，来佐证之前的实验结果。可以看到，对于不同的线程数目，当调节窗口

【参考文献】：
期刊论文
[1]NoSQL数据库综述[J]. 吾木提·那合曼.  电子世界. 2015(17)
[2]大规模图数据划分算法综述[J]. 许金凤,董一鸿,王诗懿,何贤芒,陈华辉.  电信科学. 2014(07)
[3]数据库技术发展综述[J]. 向海华.  现代情报. 2003(12)

硕士论文
[1]基于分布式图计算的大规模网络分析系统的研究[D]. 赵炳.北京邮电大学 2018
[2]图分布式计算的通信优化研究[D]. 常东阳.辽宁大学 2017



本文编号：3571222