IT评测·应用市场-qidao123.com技术社区

标题: Graph4Stream：基于图的流计算加速 [打印本页]
作者: 丝    时间: 2025-4-2 12:52
标题: Graph4Stream：基于图的流计算加速

作者：汪煜
之前在「姊妹篇」《Stream4Graph：动态图上的增量计算》中，向各人先容了在图计算技能中引入增量计算能力「图+流」，GeaFlow流图计算相比Spark GraphX取得了显著的性能提升。那么在流计算技能中引入图计算能力「流+图」，GeaFlow流图计算相比Flink关联计算性能如何呢？
当今期间，数据正以前所未有的速度和规模产生，对海量数据进行实时处理惩罚在异常检测、搜索推荐、金融交易等各个范畴都有着广泛的应用。流计算作为最主要的实时数据处理惩罚技能也变得越来越重要。
与批处理惩罚需要等候数据全部到齐才进行计算不同，流计算将持续生成的数据流划分成微批，对每个微批的数据进行增量计算。如许的计算特性使得流计算具有高吞吐、低延迟的特性。常见的流计算引擎包括Flink、Spark Streaming等，他们都采用表的方式处理惩罚流中的数据。随着流计算应用的深入，越来越多的计算场景涉及到大数据之间关联关系的计算，此时基于表的流计算引擎性能会大幅下降。
蚂蚁图计算团队开源的流图计算引擎GeaFlow，将图计算与流计算相联合，提供了高效的流图处理惩罚框架，大幅提升了计算性能。下面为各人先容传统流计算引擎在关联关系计算的范围性，GeaFlow流图计算高效的原理以及他们的性能对比。
1. 流计算引擎：Flink

Flink是经典的基于表的流处理惩罚引擎，他将输入的数据流切分成微批，每次计算当前批次的数据。在计算过程中，Flink将计算任务翻译成由map、filter、join等基础算子组成的有向图，每个算子都有他的上游输入和下游输出。增量数据颠末所有算子的计算后输出当前批次的结果。

我们以k-Hop算法为例，描述Flink的计算过程。k-Hop是指K跳关系，比方在社交网络中k-Hop指的是可以通过K个中间人相互熟悉的关系链，在交易分析中指资金的K次连续转移的路径。假定以2跳关系为例，输入的数据格式 src dst代表了两两关系。Flink的计算SQL如下文所示
  1. -- create source table
  2. CREATE TABLE edge (
  3.     src int,
  4.     dst int
  5. ) WITH (
  6. );
  8. CREATE VIEW `v_view` (`vid`) AS
  9. SELECT distinct * from
  10. (
  11. SELECT `src` FROM `edge`
  12. UNION ALL
  13. SELECT `dst` FROM `edge`
  14. );
  16. CREATE VIEW `e_view` (`src`, `dst`) AS
  17. SELECT `src`, `dst` FROM `edge`;               
  19. CREATE VIEW `join1_edge`(`id1`, `dst`) AS SELECT `v`.`vid`, `e`.`dst`
  20. FROM `v_view` AS `v` INNER JOIN `e_view` AS `e`
  21. ON `v`.`vid` = `e`.`src`;
  23. CREATE VIEW `join1`(`id1`, `id2`) AS SELECT `e`.`id1`, `v`.`vid`
  24. FROM `join1_edge` AS `e` INNER JOIN `v_view` AS `v`
  25. ON `e`.`dst` = `v`.`vid`;                                
  27. CREATE VIEW `join2_edge`(`id1`, `id2`, `dst`) AS SELECT `v`.`id1`, `v`.`id2`, `e`.`dst`
  28. FROM `join1` AS `v` INNER JOIN `e_view` AS `e`
  29. ON `v`.`id2` = `e`.`src`;
  31. CREATE VIEW `join2`(`id1`, `id2`, `id3`) AS SELECT `e`.`id1`, `e`.`id2`, `v`.`vid`
  32. FROM `join2_edge` AS `e` INNER JOIN `v_view` AS `v`
  33. ON `e`.`dst` = `v`.`vid`;
复制代码
它的实行计划如下图所示，他由Aggregate、Calc、Join等算子组成，数据流经每个算子最终得到增量结果。核心算子join实现了关联关系的查找，我们来详细分析Join算子的实现方式。

如下图所示，Join算子有两个输入流LeftInput和RightInput，分别代表了join的左表和右表，Join算子在接收到上游的数据后实行计算。以左输入流为例，输入的数据首先被加入到LeftStateView中保存起来，然后去RightStateView中查询是否有数据符合join条件，这个查询过程需要遍历RightStateView，最后将join结果输入到下一个算子中。
join计算主要的性能瓶颈就在遍历RightStateView。LeftStateView和RightStateView实际上存储join的左表和右表。随着数据不停输入，StateView中的数据量持续膨胀，最终导致遍历的耗时急剧上升，严重影响系统性能。

2. 流图计算引擎：GeaFlow

2.1 图计算&流图

图计算是一种基于图数据格式的计算范式，其中图G(V,E)由点集合V和边集合E构成，边代表了数据之间的关联关系。以公开数据集web-Google为例，其中每一行数据由两个数字组成，代表了两个页面之间的跳转关系。如下图所示，左侧是原始数据，常规的数据建模方式是建立一张包含两列数据的表，而图的建模方式是将网页作为点，将页面的跳转关系作为边，构成一张跳转网络图。在表的建模方式中，关联关系的计算是通过表的join实现的，join需要遍历左表或者右表。而在图计算中，关联关系被直接存储在边中，省去了遍历的过程。

流图是图在流场景中的应用，他依据数据流对图的更新将图分成历史图和增量图两个部分。比方在上图中，假设第一行和第二行数据已经输入并完成相应计算，当前处理惩罚第三行数据。此时历史图就是由前两行数据建模得到，而增量图是由第三行数据组成的图，两者合并起来就得到完整的图。在流图上应用增量图算法，可以高效完成计算任务，实现实时计算。
2.2 GeaFlow架构

GeaFlow引擎的计算流程分为流数据输入、分布式增量图计算、增量结果输出几个部分。和传统的流计算引擎一样，输入的实时数据按照窗口被切分成微批。对于当前批次的数据，先按照建模策略解析成点边构成增量图。增量图和之前数据构成的历史图一道组成完整的流图。计算框架在流图上应用增量图算法得到增量结果输出，最后把增量图添加到历史图中。

GeaFlow计算框架是以点为中心的迭代计算模型。他以增量图中的点作为第一轮迭代的起点。在每一轮迭代中，每个点都独立维护自身的状态，根据与每个点关联的历史图和增量图完成当前迭代轮次的计算，最后将计算结果通过消息传递给邻人点，开启下一轮迭代。
以前文中提到的k-Hop为例，增量算法如下：在第一轮迭代中，我们找到增量图中的所有边，将这些边作为初始的入向路径和出向路径，分别发送到他们的起点和终点。在后续的迭代中不停扩展入向路径和出向路径。当达到求取跳数时，将出向路径和入向路径发送给起点，在起点组合成最终结果。详细代码实现在开源仓库的IncKHopAlgorithm.java文件中。
下图是两跳场景的描述。在第一轮迭代，增量边B->C分别构建入向路径和出向路径，将他们分别发送给点B和点C。在第二轮迭代，B收到入向路径，并加上当前点的入边形成2跳入向路径，发送给点B。同样点C也收到出向路径，加上当前的出边形成2跳出向路径，发送给点B。最后一轮迭代在B点将收到的出向和入向路径整合成新增的路径。可以看到，和Flink中需要查找所有的历史关系不同，GeaFlow采用基于流图的增量图算法，计算量和图中的增量路径成正比。

上述图算法已经集成到GeaFlow的IncKHop算子中，用户可以直接通过DSL调用。
  1. set geaflow.dsl.max.traversal=4;
  2. set geaflow.dsl.table.parallelism=4;
  4. CREATE GRAPH modern (
  5.   Vertex node (
  6.     id int ID
  7.   ),
  8.   Edge relation (
  9.     srcId int SOURCE ID,
  10.     targetId int DESTINATION ID
  11.   )
  12. ) WITH (
  13.   storeType='rocksdb',
  14.   shardCount = 4
  15. );
  17. CREATE TABLE web_google_20 (
  18.   src varchar,
  19.   dst varchar
  20. ) WITH (
  21.   type='file',
  22.   geaflow.dsl.table.parallelism='4',
  23.   geaflow.dsl.column.separator='\t',
  24.   `geaflow.dsl.source.file.parallel.mod`='true',
  25.   geaflow.dsl.file.path = 'resource:///data/web-google-20',
  26.   geaflow.dsl.window.size = 8
  27. );
  29. INSERT INTO modern.node
  30. SELECT cast(src as int)
  31. FROM web_google_20
  32. ;
  34. INSERT INTO modern.node
  35. SELECT cast(dst as int)
  36. FROM web_google_20
  37. ;
  39. INSERT INTO modern.relation
  40. SELECT cast(src as int), cast(dst as int)
  41. FROM web_google_20;
  42. ;
  44. CREATE TABLE tbl_result (
  45.   ret varchar
  46. ) WITH (
  47.   type='file',
  48.   geaflow.dsl.file.path='${target}'
  49. );
  51. USE GRAPH modern;
  53. INSERT INTO tbl_result
  54. CALL inc_khop(2) YIELD (ret)
  55. RETURN ret
  56. ;
复制代码
3. GeaFlow 性能测试

为了验证GeaFlow的流图计算性能，我们以k-Hop算法为例设计了和Flink的对比实行。我们将指定数据作为输入源输入到计算引擎中，实行k-Hop算法，并统计所有数据完成计算的时间来比力系统的性能。我们采用公开数据集web-Google.txt作为输入，实行环境为16台8核16G的服务器，分别比力了一跳、两跳、三跳、四跳关系计算的场景。
实行结果如图所示，横坐标是分别是一跳关系、两跳关系、三跳关系、四跳关系，纵坐标是处理惩罚完所有数据的耗时，采用对数指标。可以看到在一跳、两跳场景中，Flink的性能要好于GeaFlow，这是由于在一跳、两跳场景中参与join计算的数据量比力小，join需要遍历的左表和右表都很小，遍历本身耗时短，而且Flink的计算框架可以缓存join的历史计算结果。但是到了三跳、四跳场景时间，由于计算复杂度的上升，join算子需要遍历的表迅速膨胀，带来计算性能的急剧下降，甚至四跳场景超过一天也无法完成计算。而GeaFlow采用基于流图增量图算法，计算耗时只和增量路径相关，和历史的关联关系计算结果无关，所以性能明显优于Flink。

4. 总结和展望

传统的Flink等流计算引擎在计算关联关系时需要用到join算子，join算子需要遍历全量的历史数据，这使得他们在大数据关联计算场景中性能不佳。GeaFlow引擎通过支持流图计算框架，将图计算引入到流计算中，采用增量图计算的方法大大提升了实时数据的处理惩罚系性能。
目前GeaFlow项目代码已经开源，我们希望基于GeaFlow构建面向图数据的统一湖仓处理惩罚引擎，以解决多样化的大数据关联性分析诉求。同时我们也在积极筹备加入Apache基金会，丰富大数据开源生态，因此非常接待对图技能有浓厚爱好同学加入社区共建。
社区中有诸多有趣的工作尚待完成，你可以从如下简朴的「Good First Issue」开始，等候你加入偕行。
参考链接

                        本文版权归作者和博客园共有，接待转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文链接，否则作者保留追究法律责任的权利。               
                                    若本文对你有所帮助，您的                                    关注                                和                                    推荐                                是我分享知识的动力!                    
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/) Powered by Discuz! X3.4