分布式流式图划分系统的设计与实现

论文摘要

随着大规模图计算和图存储的发展,单机的计算和存储能力已经难以胜任,将图数据划分成多个子图并分发到集群中进行分布式处理成为一个常见方案。如何进行图划分是一个有挑战的问题,一方面一个良好的划分结果需要子图间连通性和增大子图间平衡性两个可能冲突的目标问找到平衡点。另一方面,图划分系统还应该拥有较强的伸缩性、可靠性、可用性和性能。图划分任务可以被形式化为（k,v）平衡图划分问题,即将图G =（V,E）分为k个最大不超过vn/k的分量。目前常见的图划分算法可根据在线或离线、边划分或点划分分为四类。其中在线边划分算法由于具有较好的实时性,并且在幂率图上有着较好的性能,因此是目前较为流行的研究方向。为这些算法提供高效可靠的工程化实现是有意义的课题。本文的研究目的是设计并实现一个能够可靠使用的分布式流式图划分系统,该系统在实现上根据功能分为两个流式图划分和图存储两个子系统。流式图划分系统的设计基于Sajjad在2016年提出的HoVerCut在线边划分算法[1]。HoVerCut通过子分类器支持横向和纵向扩展,每个子分类器通过全局的共享状态进行同步。但该算法在分布式架构上会存在较高的通信延迟,本文对HoVerCut算法中存在的通信性能问题进行了讨论,并围绕减少冗余通信规模和优化IO模型提出了三点优化措施。出于提高可扩展性,共享状态可以使用多种数据库作为后端存储,这些数据库的容错与故障恢复性能不一,而共享状态又是子分类器与全局同步的唯一途径,所以共享状态可能产生单点问题。本文基于Raft共识算法设计并实现了图存储子系统,从而提高共享状态的可靠性和可用性。此外,本文还基于Redis、本地内存等提供了轻量级的实现方案。本文将对输入流的去重功能整合到共享状态模块中,从而避免了额外实现去重机制带来的时空开销。为了进一步加快去重效率,本文还布隆分类器进行预筛。本文对图存储子系统中的部分数据建立了缓存,以提高读性能。该缓存使用旁路缓存策略进行维护,并通过下层的Raft层提供故障恢复功能。本文在以上设计基础上使用C++实现了图划分系统,并使用GoogleTest等测试框架对系统的有效性和高效性进行了测试。经实验验证,采用优化的Ho VerCut算法,系统在不损失划分结果质量的情况下的划分速度得到提升。随着数据集规模的增大,优化算法相比普通算法减少运行时间的比例在逐渐增加,并且优化算法中每个窗口的处理时间是较为接近的。在图存储子系统支持下,系统的可靠性和可用性也得到了提高。本文的主要贡献可以概括如下。·针对HoVerCut算法存在的通信性能问题进行讨论,并通过减少通信冗余和改进IO模型等方式对原算法进行优化,从而提升了算法的性能。·指出Ho VerCut算法中共享状态可能存在的单点问题,基于Raft共识算法实现了一个图存储子系统,能够提高共享状态的可用性和可靠性。对经常访问到的部分数据使用缓存进行维护,从而减少对共享状态的读请求,以进一步提高读效率。·提出基于共享状态模块的边去重机制,并引入布隆过滤器对输入的边进行预先去重以进一步提高效率。

论文目录

• 摘要
• Abstract
• 第一章 绪论
•   1.1 选题背景与意义
•   1.2 本文的研究思路和解决方案
•   1.3 本文的主要工作
•   1.4 本文结构
• 第二章 相关技术概述
•   2.1 国内外研究现状和分析
•     2.1.1 图划分算法
•     2.1.2 分布式图计算系统
•     2.1.3 分布式图数据库
•   2.2 本文使用的技术简介
•     2.2.1 Redis
•     2.2.2 Protobuf
•     2.2.3 gRPC
•     2.2.4 状态机复制和Raft分布式共识算法
•     2.2.5 GoogleTest
•   2.3 本章小结
• 第三章 图划分系统的需求分析和总体设计
•   3.1 需求分析
•   3.2 总体设计
•     3.2.1 流式图划分子系统
•     3.2.2 图存储子系统
•   3.3 本章小结
• 第四章 流式图划分子系统的详细设计与实现
•   4.1 改进的HoVerCut算法
•   4.2 子分类器模块的详细设计和实现
•   4.3 共享状态模块的详细设计
•   4.4 共享状态模块的实现
•     4.4.1 基于本地内存的共享状态存储
•     4.4.2 基于Redis的共享状态存储
•   4.5 在线评分模块的详细设计与实现
•   4.6 去重机制的详细设计与实现
•   4.7 系统测试和评估
•     4.7.1 测试环境搭建
•     4.7.2 系统性能评价指标
•     4.7.3 结果与分析
•   4.8 本章小结
• 第五章 图存储子系统的详细设计与实现
•   5.1 PartitionStateNuft的详细设计和实现
•   5.2 客户端接口模块的详细设计与实现
•   5.3 Raft算法模块的详细设计与实现
•   5.4 RPC模块的详细设计与实现
•   5.5 系统测试和评估
•     5.5.1 测试环境搭建
•     5.5.2 单元测试
•     5.5.3 性能测试与结果分析
•   5.6 本章小结
• 第六章 总结与展望
•   6.1 本文工作总结
•   6.2 展望
• 参考文献
• 致谢

文章来源

类型: 硕士论文

作者: 骆融臻

导师: 杨育彬

关键词: 分布式系统,流式图划分,图数据库

来源: 南京大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机软件及计算机应用

单位: 南京大学

分类号: TP311.52;O157.5

总页数: 76

文件大小: 4529K

下载量: 69