Gremlin 算子并行化实现论文
0 论文的结构：「是什么，为什么，怎么做」
目标：高性能，易用的分布式OLAP图分析系统
0 摘要
这篇论文讲述的系统主要是一个支持 Gremlin 查询的分布式 OLAP 图分析系统，此系统已经在Ali 生产环境中应用
1. 介绍
主要讲解了解决大图交互式查询的性能问题，提出了核心技术：
1. DataFlow graph、
2. bounded-memory executionand
3. early-stop optimization
这几个核心概念解决性能以及内存使用问题
2.系统架构
架构图
本文主要实现了分布式算子执行，为了用户方便使用，集成了Gremlin Server
3. 编程模型 GAIA
重点介绍数据模型 + 核心概念
DataModel: Property Graph
Processing: Traversal 集成各种算子，只不过此处的算子在工程实现上模仿了分布式实现
第四五章是论文重点，讲解核心概念以及详细设计
4. Gremlin编译汇编 【Compilation of Gremlin】
核心实现概念 Data DataFlow Graph
有个横向对比针对Q2
Q2: g.V(2).out().out().count()
gremlin-core 实现的执行算子
GraphScope GAIA 实现的执行计划
结合图模型 + 执行计划 讲解了 Dataflow graph and execution for query Q2.【附图】
Data Flow执行中核心概念 Enter, Exit, and GoTo
通过几个Query Case 没有理解分布式执行的理念： 需要进一步结合代码 debug 下看看
第五章讲解具体工程实现思路？
5. 分布式执行【Distributed Execution】
DOP 的具体实现
核心点：算子并行化后，是否能够存储层裁剪？如果不能，可能还不如串行执行效率高
Bounded-Memory Execution： 通过混合策略（BFS、DFS）以及调度策略控制内存使用，防止OOM
Early-Stop Optimization：并行化执行 也就是和串行中一样尽量做到「恰到好处的Stop」 因为底层存储进行RPC通信是代价最大的
这个策略的性能表现在第六章中有测试结果
例子：
Q5: g.V(2).repeat(out().simplePath())
.times(4).path()
.limit(k)
6.测试与评估 《Evaluation》
6.1 测试用例
数据集
测试Query 14个 从哪里能拿到？
配置
6.2 可扩展性：测试结果
6.3 核心技术设计：测试结果
- 内存大小与Latency 之间的关系
- Traversal Strategy:BFS、DFS 内存/latency 之间的关系 结论：DFS 效果很好
- EarlyStop 性能表现：enables 12× improved performance and 1GB memory saving when the limit number is 10. 当limit(10) 有12倍的性能提升
- Compare with big engines.：采用提出的新技术，性能以及内存方面有卓越的表现：内存限制，混合调度，Early-Stop(Limit)
6.4 和其他图数据库比较查询性能
- 小数据规模G1 数据集中，整个表现比不上单独的数据库 GAIA has an average relative per-formance of just around 1.8 using single thread, and of 0.73 using 16 threads, among all LDBC queries.
- 大数据规模G100 数据集中，与JnasGraph 对比，性能整体上比数据优秀，不过也是10^3 ms 级别，JN很多查询OT
7. 相关工作
核心点不是替换 GraphDB 场景，主要是面向用户的Graph Processing Systems ，降低用户使用门槛儿，并且降低Latency
目前支持了Gremlin + Cypher 以及基于Langchain 可以提供Gremlin编写服务【21年到现在发展的样子】
8. 结论
这个系统在内部提供了大图分析的能力