清华大学教授陈文光 - Gemini：基于图计算的高性能大数据分析系统

2020-02-27 444浏览

  • 1.基于图计算的高性能大数据分析系统 Gemini 清华大学 陈文光
  • 2.大数据对分析平台的挑战  大数据是指无法在一定时间内用常规软件工具对其 内容进行抓取、管理和处理的数据集合（维基百科 定义）  大数据 = “海量数据”+“复杂类型的数据”  大数据的特性（ Volume，Variety，Velocity） – 数据量大：PB、TB、EB、ZB级别的数据量 – 种类多：包括文档、视频、图片、音频、数据库、层次状 数据等 – 速度快：数据生产速度很快；要求对数据处理和I/O 速度很快 2
  • 3.主流大数据平台 - Hadoop
  • 4.基于内存的大数据分析平台 -Spark
  • 5.Spark的局限性-数据模型层面 大数据应用: Spark：只读数据对象 部分数据更每新 次细粒度的数据更新时，间片由段 于spark基于粗 图遍历（BFS） 粒数度据 RDD只读的数据对象模型，需要RDD变 换，即有大量数据的复制，导致处理效率 不高。 . . . RDD 5
  • 6.Spark的局限性-实现层面 • Spark基于Scala语言，运行在JVM上 • 内存表示冗余，占用内存大 • 内存分配与回收开销大
  • 7.GraphLab在某些任务上 比Spark快10倍 Gonzalez, Joseph E., et al. "Graphx:Graph processing in a distributed dataflow framework." Proceedings of OSDI. 2014.
  • 8.图计算 – 折衷的大数据分析平 台 MPI，OpenMP • 可读写的数据 • 容错困难 • 不支持自动负 载平衡 GraphLab,Gemini • 可读写的数据 • 容错性能较好 • 一定程度的自动 负载平衡 MapReduce，Spark • 只读数据集 • 容错方便，扩展 性好 • 自动负载平衡 性能 扩展性
  • 9.图数据的重要意义 • 图能够表达丰富的数据和关系 – 网络连接 – 网页链接 – 社交关系 – 蛋白质交互 – 人与人，人与公司，人与产品
  • 10.图的计算与分析 • PageRank • 最短路径 • 连通分支 • 极大独立集 • 最小代价生成树 • Bayesian Belief Propagation •…
  • 11.代表性图计算系统 GraphLab UAI’10 Pregel SIGMOD’10 PowerGraph OSDI’12 Distributed GraphLab VLDB’12 Galois SOSP’13 Ligra PPoPP’13 2010 2011 2012 2013 Polymer PPoPP’15 PowerLyra EuroSys’15 Gemini OSDI’16 2014 2015 2016
  • 12.
  • 13.PowerGraph/PowerLyra的问题 • 计算性能低，处理小图时8台机器性能还不 如单机系统 twitter-2010数据集上，20 轮PageRank迭代(41.7M 结点, 1.47B 边)
  • 14.性能数据对比 瓶颈在计算！ 结点数 系统 运行时间 (s) 指令数 内存访问数 通信量(GB) IPC L3 缺失率 CPU 利用率 1 Galois 8 PowerLyra 19.3 26.9 482G 6.06T 分布式计算开销 23.4G 87.2G - 38.1 0.414 0.655 49.7%计算不够优化54.9% 96.8% 68.4% twitter-2010数据集上， 20 轮PageRank迭代 (41.7M 结点, 1.47B 边) 网络带宽远远没有饱和 执行了更(1多00指Gb令ps和) 更 (38.1*8/2多/2访6.存9/8=0.708Gbps) 局部性差 CPU利用率低 14
  • 15.分布式图计算系统Gemini • 在高效性的基础上支持扩展性 – 避免没有必要的“分布式”副作用 – 优化图的划分与计算 • 设计理念的变化 – 以计算性能为中心的分布式系统 • 分布式系统有快速的通信网络 • 计算可以与通信重叠 – 效率优化 • 自适应push-pull转换 • 层次化的分块划分 – 扩展性优化 • 局部性感知的分块 • 基于分块的任务窃取
  • 16.稠密-稀疏双模式的计算模型 • 图计算中的活跃结点数在不同迭代步骤时 不同 – 活跃结点多，适合稠密模式 – 活跃结点少，适合稀疏模式 sparseSignal sparseSlot aa b c communication computation x denseSignal denseSlot zz y master mirror
  • 17.双模式: 以BFS 为例 (1) Dual mode updates proposed in shared-memory systems (Ligra[PPoPP ’13]) Active edge set / E < threshold  Sparse mode  Push operations Active edge set 13 Active vertex set 0 Selectivescheduling:only access out-edges from active vertices 24 57 68 1st iteration 9 Locks/atomic operations required for correctness of concurrent updates 17
  • 18.双模式: 以BFS 为例 (2) Active edge set Active edge set / E > threshold  Dense mode  Pull operations 13 24 Limited selective scheduling 09 57 68 2nd iteration Vertices pulling along in-edges Contention-free updating 18
  • 19.分布式双模式计算 Node0 1 3 24 09 57 Node1 6 8 19
  • 20.分布到两个节点 13 Node0 Master 24 0 9 Mirror 57 6 13 24 09 57 Inter-node message passing 68 24 0 57 Node1 68 9 20
  • 21.Gemini的分布式push 13 Node0 24 09 57 24 60 9 57 Node1 68 Masters message mirrors, who update their local neighbors 21
  • 22.Gemini的分布式Pull 13 Node0 24 09 57 24 60 9 57 Node1 68 Mirrors pull updates from neighbors, then message masters 22
  • 23.基于chunk的图划分方法 • 传统图划分方法 – 代价高：metis – 划分效果差：hash • 基于chunk的划分 – 利用数据集中的局部性
  • 24.为什么做chunk划分? • chunk划分保留了局部性! – 很多实际图中都存在局部性 • E.g., WebGraph[WWW ’04], BLP[WSDM ’13] • 图结点按“语义”排序 Facebook Country Adjacency Matrix1 UK Web (2005) Adjacency Matrix – 结点没有排序时存在可接受的预处理方法 • E.g., BFS[Algorithms 09], LLP[WWW ’11] 1 The Anatomy of the Facebook Social Graph 24
  • 25.Chunk的其它好处 • 不需要转换vertex IDs (global  local) – 大大缩小了partition信息的维护开销 • O(p) chunk 边界 – 结点数据更容易管理 • 在共享内存中分配连续的数据 Touched • 可以在多个层次递归地使用 25
  • 26.局部性感知的Chunking • 如何分块? 0 LLC Balancing by edges? V Chunk size affects random access efficiency! • Gemini 同时考虑了结点和边 – 边数: 处理的工作量 – 结点数局部性 – 混合度量: ⍺· Vi + Ei • ⍺ 现在设为 8(p-1) 26
  • 27.多层次分块划分和任务窃取 Per-node partition cluster node socket Per-socket partition w. NUMA-aware placement Data partitioning till socket-level Per-core work chunk Locality-aware core Mini-chunk for work stealing Work partitioning within socket Fine grain (64-vertex) 27
  • 28.性能评估 • 平台: 8-结点集群 – Intel Xeon E5-2670 v3 (12-core CPU), 30MB L3 cache – 2 sockets sharing 128 GB RAM (DDR4 2133MHz) –Network:Mellanox Infiniband EDR 100Gbps • 测试程序 • 输入图 – PageRank (PR) (20 iterations) Graph – Connected Components (CC) – Single-Source Shortest Paths (SSSP) – Breadth-First Search (BFS) – Betweenness Centrality (BC) enwiki-2013 twitter-2010 uk-2007-05 weibo-2013 clueweb-12 V 4,206,785 41,652,330 105,896,555 72,393,453 978,048,098 E 101,355,853 1,468,365,182 3,738,733,648 6,431,150,494 42,574,107,469 28
  • 29.单结点效率 Application PR CC SSSP BFS BC Ligra Galois 21.2 19.3 6.51 3.59* 2.81 3.33 0.347 0.528 2.45 3.94* Runtime in seconds (twitter-2010) Gemini 12.7 4.93 3.29 0.468 1.88 System Ligra Gemini Remote access ratio 50.1% 9.10% L3 cache miss rate 52.6% 40.1% Average access latency 183ns 125ns Memory reference profiling results More iterations More instructions NUMA-aware memory accesses “*” uses different algorithms. 29
  • 30.基于chunk的分块方法和基于 Hash的划分方法 30
  • 31.Runtime(s) Iteration # 0.6 0.45 0.3 0.15 0 0 分布式push/pull效果 1 0.75 0.5 0.25 0 0 PageRank Sparse Dense 20 Runtime of each iteration using sparse / dense mode (uk-2007-05) Connected Components Sparse Dense Single-Source Shortest Paths 0.2 0.15 0.1 0.05 0 76 0 Sparse Dense “mis-predictions”: 2 out of 76 for CC and 5 out of 172 for SSSP 172 31
  • 32.结点内负载平衡 Speedups of different intra-node load balancing strategies over static scheduling (PR) 2.5 2 1.5 1 0.5 0 twitter-2010 uk-2007-05 static scheduling balanced partition stealing stealing w/ balanced partition 32
  • 33.分布式系统Gemeni – 性能 • 测试环境 • 8台双路Xeon E52670V3 4 (hypert.) vCPU cores • 128 GB memory • Infiniband EDR(100Gbps) • 与PowerLyra相比， 加速比约为18.7X • 与GraphX相比， 加速比约为80300X
  • 34.内存占用情况 • Gemini的内存占用约为PowerGraph的六分之一 • 意味着可以用更少的机器获得更快的分析速度，降 低用户大数据分析的成本
  • 35.性能优先的大数据系统 数据模型：区分只读数据和可读写数据 数据结构：基于混洗的数据结构 编程抽象：基于点和边的集合，编译与运行时优化 执行平台：单机内存  Out of core  分布式  GPU/APU/FPGA 编程系统 数据模型 MPI 可读写数据集 MapReduce 只读数据集 Spark GraphLab Gemini 只读数据集 可读写数据集 部分只读，部分可读写 容错能 力 弱 强 性能 自动负载平衡 高无 很低 有 强 弱 较强 低 较高 高 有 有 有
  • 36.感谢聆听！