高军 - 可扩展的大图数据管理框架和查询处理

仲晔晔

2018/05/13 发布于 技术 分类

Hadoop技术经过最近10年发展,已经开始深入各行业和各类应用。但从市场的反馈来看,Hadoop还没有被大面积普遍采用,主要制约因素来自两个方面:1. SQL on Hadoop的技术进展制约了企业原有应用的迁移以及新应用的开发;2. 企业在建设大数据平台或者Data Lake时,往往有多租户资源管控和弹性计算的需求,这些需求现有的YARN或者虚拟化技术没有满足。 本次演讲将介绍星环科技在这两方面的最新突破,首先介绍星环科技在对SQL2003和PL/SQL支持上的多种优化技术,可帮助企业快速完成应用迁移和部署;其次介绍星环科技的最新产品,结合Hadoop和Docker技术,如何实现细粒度的资源管理和调度。

文字内容
1. 可扩展的大图数据管理框架 和查询处理 高军 信息科学技术学院 1 1
2. 提纲 ♠ 背景和意义 ♠ 单机大图数据管理框架 ♠ 分布式大图数据管理框架 2 2
3. 背景-图数据出现在不同的应用领域 社交网络 Web数据 生物数据 >1 billion vertices ~1 trillion edges >50 billion vertices >100 billion vertices >1 trillion edges >100 trillion edges ♠ 大数据中不仅仅有数据项的信息,也有数 据项之间的关联信息 ♠ 我们称这些规模庞大、结构复杂的数据为 大图(Big Graph)数据 3 3
4. 大图数据分析的应用示例 ♠ 图数据分析有助于判 定敏感人物或者社区 ♣ 美国911事件后构造 的关系网络 ♣ 2011年在伦敦骚乱 和挪威枪击事件中, Twitter, Facebook 等社交网络起到的传 递鼓动信息和散播谣 言等作用 绿色、红色、蓝色 节点是911劫机分子 灰色节点是推测 出的嫌疑人员 4 4
5. 大图数据管理在不同领域中应用 Financial Network ♠ 特定节点的发现 ♣ 发现社交网络中有影响力节点,用于 广告发送 ♣ 社交网络中发现潜在的犯罪嫌疑人 ♠ 特定路径的发现 ♣ 交通领域中的最短路 ♣ 社交网络中异常路径的发现 ♠ 特定子图的发现 ♣ 生物领域中基因数据的频繁模式 ♣ 社交网络的特定兴趣社区 ♣ 财经网络中可疑交易集合 ♣ ….. 5 5
6. 大图数据查询分析面临挑战 ♠ 数据复杂性 ♣ 数据量大 ♣ 结构+内容 1970s~ 101 nodes 1990s~ 104 nodes ♣ 数据之间的结构关联复杂 ♠ 查询复杂性 ♣ 查询表达方式灵活 2000~ 108 + nodes 2010~ 1010 + nodes ♣ 查询搜索空间大 ♣ 图数据模型灵活 存不下:大图数据无法存储在单机内存 算不出:大图数据操作6 代价过高 6
7. 大图数据管理1:针对特定图查询编写方法 ♠ 优点 ♣ 面向大图数据处理的专有算法,处理效率高 ♠ 缺点 ♣ 系统实现代价高 ♦ 大图数据分块、存储、索引、数据缓存策略、网络 传输、副本、故障恢复....... ♣ 系统稳定性差 ♣ 市场接受度差 7 7
8. 大图数据管理2:图数据管理系统 ♠ 实现以图模型为底层存储模型的数据管理系统 ♠ 支持图数据的存储,索引等 ♠ 提供图数据的基本操作,如遍历、最短路等 ♠ 简化用户应用程序开发代价 ♠ 但是 ♣ 图数据的操作过于灵活、复杂,有限的几种操作很 难满足应用的需求 8 8
9. 大图数据管理3:图数据管理框架 ♠ 支持图数据的透明存储、任务调度等公有操作 ♠ 提供合适的底层接口,允许用户表达各类查询 ♣ 接口尽可能简单 ♣ 通过接口实现尽可能多的查询操作 ♦ PageRank、最短路、社区发现、异常点发现、可 达性发现 抽象:不同类型的图操作都是??? 系统优化公共部分 用户编写不同图操作特有的代码,提高通用性 9 9
10. 以点为中心计算模型的图数据管理框架 ♠ 不同类型的图操作都是一系列迭代组成,在每次迭代中在每次 迭代中,每个节点接受消息、按照用户输入的脚本处理消息、 输出消息. Iteration 0 Iteration 1 Placement Of Vertices Computation Communication Computation Communication Barrier Barrier ♠ 主流的框架大多遵从以点为中心的计算模式 Google Microsoft Apache/Facebook CMU Barrier CMU 10 10
11. 大数据处理的通常思路 更多CPU 更大内存 更多存储 单机大图数据管理 更多的 计算节点 分布并行 计算 分布式大图数据管理 11 11
12. 提纲 ♠ 背景和意义 ♠ 单机大图数据管理框架 ♠ 分布式大图数据管理框架 12 12
13. 单机大图数据管理框架 ♠ 单机程序开发效率相对高 ♠ 单机程序不需要考虑网络传输代价,相对效率高 ♠ 单机安装、管理、部署代价低 ♠ 单机运行程序能耗低 13 13
14. 典型框架介绍:GraphChi ♠ Graphchi是CMU开发的 单机图数据管理框架, 发表于OSDI 2012 ♠ 支持超过内存的图数据 有效处理 ♠ 图的操作中涉及到大量 的数据随机访问操作, GraphChi利用顺序读写 代替随机读写降低外存 影响 ♠ 单机上获得和分布式集 群可比较的效率 14 14
15. 典型框架介绍:Mac Mini上Graphchi的测试结果 PageRank WebGraph Belief Propagation (U Kang et al.) Twitter-2010 (1.5B edges) GraphChi (Mac Mini) Spark (50 machines) 0 2 4 6 8 10 12 14 Minutes Matrix Factorization (Alt. Least Sqr.) Netflix (99B edges) GraphChi (Mac Mini) GraphLab v1 (8 cores) 0 2 4 6 8 10 12 Minutes Yahoo-web (6.7B edges) 0 5 10 15 Minutes Triangle Counting GraphChi (Mac Mini) Pegasus / Hadoop (100 machines) 20 25 30 twitter-2010 (1.5B edges) GraphChi (Mac Mini) Hadoop (1636 machines) 0 100 200 300 400 500 Minutes 15 15
16. 基于关系数据库管理图数据 ♠ 关系数据库是一种成熟的系统软件,能够高效的 管理超过内存的结构化表格数据 ♠ 将图数据以表格的形式存储起来,利用关系数据 库的存储能力和查询能力来管理图数据 ♠ 扩展关系数据库支持图数据,也是关系数据库发 展的重要技术思路 s 6 12 d1 c b TNodes nid fid 8 7 3 e 2 3 s 7b s d f 5 84 g ...... s 4 h1 ... j9 2i t16 TEdges tid cost d 6 c 1 b 2 ... ... 16
17. 基于关系数据库的图查询方法 ♠ 性能挑战: ♣ 关系数据库的操作一次一个集合 ,图操作一次一个记录,这种差 异使得直接使用关系数据库查询 图数据效率低 ♠ 贡献: ♣ 提出关系数据库管理图数据FEM (Frontier-Expand-Merge)框 架 ♣ 设计利用SQL语言的新标准,包 括Window function和merge语 句提高FEM框架的效率 17 Gao, et al VLDB 2012 17
18. 基于权重分表的图查询方法 Gao, et al. TKDE 2014 ♠ 关系数据库环境中,图的遍历通过边表的连接操作完成 ♠ 随着图规模的增长,边表规模变得很大,连接操作代价高 ♠ 将表按照权重进行划分,同时调整搜索算法 1s 9c b 12 d 12 g 4 h A1(fwd=1) E TE1 1-st expansion A2 (fwd=2) E TE1 A2 (fwd=1) E TE2 2-nd expansion ...... 3-rd expansion (a) Example of Restrictive BFS (b) Illustration of Extended E-operator 18 18
19. 和著名开源系统对比 ♠ Neo4j号称是世界领先的图数据库系统,支持图的最短路发现等 基本操作 基于分表之后的关系数据库操作的方法再处理有权图最短路 方面超过Neo4j几个数量级 19 19
20. 提纲 ♠ 研究背景和意义 ♠ 单机大图数据管理框架 ♠ 分布式大图数据管理框架 20 20
21. MapReduce分布式框架 ♠ MapReduce是Google提出的分布式计算框架,极 大简化最终用户分布式编程的代价 ♠ Hadoop是MapReduce的开源实现。 ♠ Hadoop系统扩展性极强,集群支持的计算节点数 超过4000个 ♠ Hadoop系统广泛用于非结构化数据处理,如文本 处理、日志处理、数据分析等,被称为大数据处 理事实标准。 21 21
22. 基于MapReduce图操作 Join & compute rank Ri M L-split0 r M L-split1 r M Aggregate M r M r fixpoint evaluation M r M r i=i+1 Converged? Client done 22 22
23. 基于MapReduce的图数据管理面临的问题  用户需要较强的编程能力  调试MapReduce框架程序困 难  用户可能编写执行效率不高 的程序  Mapduce框架对循环的支持较 弱 23 Example of MapReduce Program 23
24. 基于MapReduce的描述性图查询方法 Gao, et. ICDE 2014 Results  用户利用高层语言描述图查询数据 GLog Query 流程 Parser MapReduce Code Generation MapReduce Code Optimization  自动将这个语言翻译到 MapReduce的任务  实现MapReduce任务的优化 Common Utility Codes Code Merge and Compile MapReduce Programs Hadoop MapReduce Framework RG table ... ... RG table RG table 24 24
25. 以点为中心的大图数据框架 ♠ 为了克服MapReduce框架管理大图数据的问题 ♣ 大图数据节点间消息传递、状态修改全部通过文件系统来 实现,导致大量的磁盘读写代价 ♠ Google提出了基于BSP模型和以点为中心计算模式的 Pregel系统,希望 ♣ 高可扩展性 ♣ 支持容错 ♣ 支持多种图操作 ♠ Apache社区中出现了两个类似的子项目,Hama和Giraph 25 25
26. BSP模型和以点为中心计算 ♠ 计算任务由超步组成 ♠ 在每个超步中,执行 ♣ 用户给定的节点之上的操作 序列 ♣ 在节点的操作序列中,输入 参数包括其他节点发送的消 息,输出结果包括向其他节 点发出的消息 ♣ 节点可以投票终止超步,系 统汇总决定循环是否终止 26 26
27. 以点为中心计算-用户编写代码示例 Class MaxFindVertex : public Vertex { public: virtual void Compute(MessageIterator* msgs) { int currMax = GetValue(); for ( ; !msgs->Done(); msgs->Next()) { if (msgs->Value() > currMax) currMax = msgs->Value(); 处理输入消息 } if (currMax > GetValue()) *MutableValue() = currMax; SendMessageToAllNeighbors(currMax); else VoteToHalt(); 输出消息 } }; 27 27
28. Google报告Pregel运行时间 ♠ 在300台多核PC服务器组成的机群上,运行随机图的最短路查询 ,随机图的平均度数为127,那么在最大图上大约是1270亿条边 的规模。在系统运行中,启动了800个worker。 28 28
29. Facebook报告Giraph运行时间 ♠ Giraph在Faceook上的应用情况。在Facebook产品化已经1年半,每周超 过100个任务与运行 ,支持内部的30个应用,单个应用处理超过7千亿 条边。经过优化后,200台机器运行1万亿边的pagerank方法,每轮小于 4分钟。 29 29
30. 研究组的实验环境 ♠ Hadoop集群 ♣ 28个节点,每个节点2颗2.60GHz AMD Opteron 4180 处理器,48G内存,10T硬盘 ♣ 我们安装了SUSE Linux Enterprise Server 11和 Java 1.7 64-bit ♣ 计算节点通过1G的网络连接 ♠ 图数据规模 30 30
31. Giraph集群压力测试结果 Query Time(s) 250 Random Graph 200 150 minQueryTime maxQueryTime 100 50 1B_5B 1B_10B 1B_15B GraphSize 1B_20B 700 600 500 400 300 200 100 0 PowerLaw Graph minQueryTime maxQueryTime 0.4B-10B 0.6B-15B GraphSize 0.8B-20B # Nodes # Edges minQueryTime maxQueryTime 1B 5B 32 61 1B 10B 57 92 1B 15B 73 133 1B 20B 105 223 # nodes 0.4B 0.6B 0.8B # edges minQueryTime maxQueryTime 10B 38 340 15B 52 420 20B 71 650 31 31 minQueryTime
32. 基于类Pregel框架的动态图上模式的检测 ♠ 图模式查询本身是NP-C问题,大图 、动态图带来更多的挑战。 supplier Gao, et al. ICDE 2014 seller user ♠ 基本框架 ♣ 图数据分布存储于不同的计算节 点中 ♣ 模式查询的执行基于数据节点之 间的消息驱动 ♣ 查询执行类似于自动机的运行 Member in gang 1 0a b2 4 c Member in gang 2 e1 d3 a5 d6 c7 c8 a9 d 10 ♠ 利用分布式计算框架支持超过10亿 边的动态大图模式匹配 ♠ 对比现有方法,我们的方法在消息 量和相应时间方面优势明显 32 32
33. 基于消息流式处理的分布式计算框架 ♠ 类Pregel框架将图数据保 存在内存中 ♠ 图数据自身和计算临时结 果规模庞大 ♠ 一旦超出内存,现有框架 奔溃或者性能严重下降 ♠ 提出利用流式处理机制减 少内存消耗的方法,在 Giraph框架中实现,提高 系统的可扩展性 33 Zhou, et al. VLDB2015 33
34. 总结 ♠ 图数据广泛出现在不同的应用领域. ♠ 图数据的处理需要考虑结构信息,处理复杂性高 ♠ 利用图数据管理框架,能够简化用户编写图数据 处理方法的代价,同时提高图数据查询的灵活度 ♠ 目前出现多种单机和分布式的图数据管理框架, 大多遵循以点为中心的计算模式 34 34
35. 研究组进展 CIKM 2010 TKDE 2012 SIGMOD 2011 VLDBJ 2013 VLDB 2012 TKDE 2014 ICDE 2014 35 ICDE 2014 VLDB 2015 35
36. 敬请指正! gaojun@pku.edu.cn 36 36