作者：汪煜
之前在「姊妹篇」《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如下文所示- -- create source table
- CREATE TABLE edge (
- src int,
- dst int
- ) WITH (
- );
- CREATE VIEW `v_view` (`vid`) AS
- SELECT distinct * from
- (
- SELECT `src` FROM `edge`
- UNION ALL
- SELECT `dst` FROM `edge`
- );
- CREATE VIEW `e_view` (`src`, `dst`) AS
- SELECT `src`, `dst` FROM `edge`;
- CREATE VIEW `join1_edge`(`id1`, `dst`) AS SELECT `v`.`vid`, `e`.`dst`
- FROM `v_view` AS `v` INNER JOIN `e_view` AS `e`
- ON `v`.`vid` = `e`.`src`;
- CREATE VIEW `join1`(`id1`, `id2`) AS SELECT `e`.`id1`, `v`.`vid`
- FROM `join1_edge` AS `e` INNER JOIN `v_view` AS `v`
- ON `e`.`dst` = `v`.`vid`;
- CREATE VIEW `join2_edge`(`id1`, `id2`, `dst`) AS SELECT `v`.`id1`, `v`.`id2`, `e`.`dst`
- FROM `join1` AS `v` INNER JOIN `e_view` AS `e`
- ON `v`.`id2` = `e`.`src`;
- CREATE VIEW `join2`(`id1`, `id2`, `id3`) AS SELECT `e`.`id1`, `e`.`id2`, `v`.`vid`
- FROM `join2_edge` AS `e` INNER JOIN `v_view` AS `v`
- ON `e`.`dst` = `v`.`vid`;
如下图所示，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调用。- set geaflow.dsl.max.traversal=4;
- set geaflow.dsl.table.parallelism=4;
- CREATE GRAPH modern (
- Vertex node (
- id int ID
- ),
- Edge relation (
- srcId int SOURCE ID,
- targetId int DESTINATION ID
- )
- ) WITH (
- storeType='rocksdb',
- shardCount = 4
- );
- CREATE TABLE web_google_20 (
- src varchar,
- dst varchar
- ) WITH (
- type='file',
- geaflow.dsl.table.parallelism='4',
- geaflow.dsl.column.separator='\t',
- `geaflow.dsl.source.file.parallel.mod`='true',
- geaflow.dsl.file.path = 'resource:///data/web-google-20',
- geaflow.dsl.window.size = 8
- );
- INSERT INTO modern.node
- SELECT cast(src as int)
- FROM web_google_20
- ;
- INSERT INTO modern.node
- SELECT cast(dst as int)
- FROM web_google_20
- ;
- INSERT INTO modern.relation
- SELECT cast(src as int), cast(dst as int)
- FROM web_google_20;
- ;
- CREATE TABLE tbl_result (
- ret varchar
- ) WITH (
- type='file',
- geaflow.dsl.file.path='${target}'
- );
- USE GRAPH modern;
- INSERT INTO tbl_result
- CALL inc_khop(2) YIELD (ret)
- RETURN ret
- ;
为了验证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企服之家，中国第一个企服评测及商务社交产业平台。 |
