返回列表

优化方案总结

基于TuGraph Analytics的⾼性能图模式匹配算法设计 | 975

开始: 2023-09-24 结束: 2023-12-31 反欺诈与反洗钱
TuGraph Analytics · 高性能图模式匹配 · 优化方案
🏆 高性能图模式匹配 · 优化方案 📅 TuGraph Analytics ⚙️ 总耗时 ≤ 6.5s (M2) / 11s (E5-2680v4)

优化方案总结

基于TuGraph Analytics的高性能图模式匹配算法设计 · 赛题链接:https://www.datafountain.cn/competitions/975
👤 GitHub主页: pengzh1

最终性能

基于 ldbc finbench sf1 数据集,各环境耗时如下:

  • 环境1:MacBookPro M2 CPU 16G内存 → 总耗时 5.5S - 6.5S
  • 环境2:Linux机器 E5-2680v4 16核 32G内存 → 总耗时 9S - 11S

分阶段统计(每阶段耗时只统计距离上一阶段结束之后的时间):

阶段耗时
总耗时6055ms
1. 集群启动,PipelineTask任务开始执行830ms
2. 读文件完成, vertexSource和edgeSource就绪30ms
3. 构图完成,开启迭代计算2950ms
4. 第一轮计算完成950ms
5. 第二轮计算完成470ms
6. 第三轮计算完成135ms
7. 第四轮计算完成95ms
8. 第五轮计算完成,并开始执行Sink函数130ms
9. Sink执行完成,任务执行结束返回结果210ms
10. 进行节点排序,文件写入230ms
11. 写入完成,进程退出5ms

主要优化手段

前提:未使用任何图API之外的跨节点数据关联、点边数据关联、边合并等非标优化手段。

  1. 参数配置:工作线程数经实验使用8为最佳;GC策略不使用G1而使用ParallelGC,并调大新生代及Eden区空间,提升内存分配吞吐量。
  2. 预读取文件,预创建文件,多线程并发读取/写入:优化了阶段2/9的耗时,详见 readAllData() / writeFiles() 及其调用处。
  3. 使用文件“行号”代替原有Long ID:参考关系数据库自增ID设计,利用行号作为隐藏属性加速ID索引效率。不同类型节点加上不同初始值,通过“号段”区分类型。使用int类型即可表示数十亿个不重复节点(大数据集也可用,结果收集时做行号→原ID转换,或将原ID作为顶点label/属性带入计算)。此优化大幅提升了构图时间和计算迭代时间。
  4. 自定义高效Kryo序列化器:实现了顶点/边/消息结构体(PVertex/PEdge/MValue)的自定义序列化,极大提升了图序列化效率,在构图/计算阶段带来约20%的提升。
  5. 缜密设计的图扩散算法:基于一张图,在五轮迭代内完成全部节点四个case结果的计算。最终计算阶段耗时不到2秒,性能甚至超过直接遍历内存集合,验证了图计算的高效性。算法细节详见代码注释。
  6. 剩余细节优化:详见 CaseKiller 代码注释。

完整代码实现及详细注释请访问 GitHub仓库