【CCF优秀博士学位论文奖-2019】大规模图数据处理系统的设计与实现，清华大学朱晓伟

论文摘要：图数据的处理在各个领域都有⼴泛的应⽤。随着图数据规模的扩⼤和对处理能⼒要求的提升，众多专门⾯向图数据的处理系统应运⽽⽣。本⽂先从传统的离线处理⾓度切⼊，研究了如何基于向上和向外两种扩展⽅式进⾏⼤规模图数据的分析，主要⼯作包括：

• ⾯向单机外存的图数据处理系统 GridGraph，通过⼆维划分和流式处理的⽅式，尽可能地使⽤顺序 I/O 访问外存上的数据并尽可能地将需要随机访问的数据驻留在内存中。通过⼀种创新的双滑动窗⼜的处理模型，结合选择性调度来减少不必要的数据访问，GridGraph 有效地降低了系统在进⾏图计算时的 I/O 量，可以获得与之前的最佳系统 GraphChi 和 X-Stream 相⽐⼗分显著的性能提升。
• ⾯向分布式内存的图数据处理系统Gemini，通过降低系统设计上分布式带来的开销并尽可能地优化本地计算部分的实现，使得系统能够在获得扩展性的 同时不失⾼效性。基于⾼速⽹络的现状及逐渐普及的发展趋势，Gemini 提出了以计算为中⼼的设计原则，⼀改过去分布式图数据处理系统过度重视通信 代价的理念，可以获得与现有系统相⽐多达数⼗倍的性能提升。离线处理的模式需要⼤量的数据准备时间，其开销甚⾄⾼于实际处理的时间。 因此，本⽂设计并实现了 LiveGraph，⼀个同时兼具数据管理和分析计算功能的在线图处理系统：
• LiveGraph 创新性地使⽤了⼀种分布式⽇志结构来存储图的拓扑信息，通过给每个顶点的邻接边表预留⼀定空间来⽀持⾼速的数据更新，同时保留了良 好的数据局部性。LiveGraph 不仅在事务处理⽅⾯具有相⽐各类数据库解决⽅案更卓越的性能，其能够直接在最新版本的图数据上进⾏分析计算的特点 更是⼤⼤降低了数据准备的开销，使在线的图数据处理成为了可能。

关键词：⼤数据；图数据处理；离线处理；在线处理；混合事务/分析处理

作者介绍：朱晓伟，他目前是清华大学计算机科学与技术系的博士研究生，他的博士生导师是陈文光。他的研究方向是于并行/分布式计算和大数据分析。