前言
现实生活中的图数据常表现出动态的形式，图上的节点和边在不断的更新，例如社交网络，金融网络，网络图等。因此，近年来图数据领域中的大量研究工作都与动态图(dynamic graph)相关。本文介绍的工作为:? Teseo and the Analysis of Structural Dynamic Graphs。作者是来自于CWI的Dean De Leo和Peter Boncz。该文发表在VLDB2021上。
·· 背景介绍 ··
图分析常常涉及在结构图(structural graphs)上昂贵的计算代价和较长的运行时间。结构图是一种同质图，简单而言只包含点和边，并可能会携带权重。过去已经有相当多的工作和系统聚焦于在静态结构图上高效的运行复杂的图算法。然而，这些工作常常局限于静态的数据源，当数据发生变动时，需要重新运行相关的分析过程或者算法，有一定的局限性。为了更好的适应动态的图数据，动态图模型应运而生。已经有一部分研究关注于如何在事务型的源数据上建立ETL的过程以用于运行图算法。另一方面，图数据库也可以提供一定的动态图上的分析能力例如neo4j或提供图分析能力的关系型数据库。这些方法都存在一些性能问题，而且限制颇多。
本文提出了一种动态图的分析库，名为Teseo，实现了与已有工作相似的逻辑视图，并提供了事务处理和快照隔离等级。相对于现有的工作，Teseo较为特别的地方在于使用B+树为原型设计树型索引，并使用了较大的叶子节点以降低随机访存次数以提供更好的局部性。另外叶子节点中使用了稀疏数组(也称PMA)这一结构来提高顺序以提高图分析的效率和更新的效率，保证动态图上高效的运行图算法。反观当前的工作，通常可以归结为一个基础系统模型。如图1所示，对于绝大多数动态图系统，通常由哈希表来提供随机的点查，然后用邻接列表来提供图上的访问。这样做有几点缺陷:1)现有工作通常忽视哈希表的并发 2)点表是顺序表，通常不能删除节 3)边表无序对边的查询不太友好。
图1 动态图系统的基础系统模型
··?基础知识?··
1.? 稀疏数组
稀疏数组是一种动态的数据结构，其中的数据按照键值排序。稀疏数组常被划分为多个块，每个块之间都有空隙供更新数据插入。稀疏数组的大小和每个块的大小为参数，被称之为CA和CS。当块满或者小于一半时将会进行重平衡(rebalance)操作，部分数据将会被重排。图2展示了一次稀疏数组的重平衡过程
图2.稀疏数组的重排示例
2.? 混合锁存器
锁存器能够有效的保护并发条件下的数据，保证线程安全。较为经典的例子是Unix/Linux的标准库Pthread。经典的锁存器会将试图获得锁存器但是失败的线程睡眠并等待，直到锁存器被另一线程释放。混合锁存器引入了乐观锁的模式，即使用有效性检测的方法，即在操作前后重复读被更新的数据以检测在操作过程中数据是否发生了改变。混合锁存器的优势在于可以减少对内部数据状态的改变提高性能。
3.??MVCC
多版本并发控制协议(MVCC)是一种对数据进行多版本化以解决并发过程中读写冲突的技术。实现方式常为每个版本都包含一个时间戳以刻画其生命周期。读线程按照时间戳读取属于其自身的版本，而写线程通过获得锁存器来解决写写冲突。写线程在事务提交之前创建仅自身可见的新数据版本，提交后该数据版本将全局可见。对于持续增长的数据版本，需要使用垃圾回收的方式进行版本清理。
·· 实现原理 ··
1.? 图分析与访问模式
图上的经典算法通常表现为两种访问模式:1)点与边顺序访问 2)点随机访问。图3展示了常见图算法的框架吗，行2可能会表现为点的随机访问，而行3常表现为边的顺序访问。例如PageRank，BFS，CDLP(社区发现)算法常常属于顺序访问的模式。单源最短路(SSSP),弱连通分量(WCC)属于随机访问模式。本地三角形计数(LCC)两者兼有。如何平衡这两种访问模式以提供更为高效的图算法和图分析需要合理的系统设计。
图3.常见图算法的框架
2.? 存储设计
Teseo使用了树型索引作为主索引，受到B+启发，Teseo提出了一种被名为Fat Tree(胖树)的数据结构，以下简称为FT。如图4所示，FT的内部节点设计与ART树类似，是一种Trie树的变形以提高查询效率。叶子节点使用前文提及的稀疏数组组织数据。FT作为主索引能够更好的适应顺序访问模式。另外，为了更好的适应随机访问模式，Teseo同样使用了哈希表以提高随机点查的效率。
图4.FT的树结构
叶子节点可能会上溢和下溢，不仅要对叶子节点进行稀疏数组的重平衡操作，也需要与B+树一样进行相似的节点合并和分裂。这些通常被称作结构化操作(structural operations)，结构化操作由后台的服务线程以异步的方式进行。另外，为了更好的支持更新操作，叶子节点中的块常常被分为两种形式，写优化(WOS)和读优化(ROS)。WOS块的组织形式为与主索引类似的树型索引，两个指针提供查找和顺序扫描。ROS块的组织形式与稀疏数组相似。WOS块会被服务线程转换为ROS块。图5展示了叶子节点中的ROS块和WOS块。
图5.叶子节点中的两种块
对于权重而言，存储相对于点边的存储较为简单。Teseo假设权重是定长的，ROS的权重按顺序存放在一个单独的块中。而在WOS块中，权重和边存储在一起。
3.? 并发控制
Teseo将顺序扫描使用只读事务实现，这类事务会获得传统的读锁存器。而对于读写事务，由于Teseo的锁存器不可重入(non-reentran)。所以读写事务只能获取乐观模式的锁存器以防止死锁。主索引FT的每个内部节点中都由锁存器以保证事务线程安全，叶子节点同样由锁存器来保证线程安全。不同的是，对于服务线程和事务线程的并发中，需要考虑死锁的可能性，所以叶子节点还需要添加对服务现场的锁存器。二级索引使用的哈希表使用了无锁实现，同样可以保证线程安全。Teseo的MVCC实现与Hyper相似，使用原地更新，垃圾回收同样由服务线程负责.ROS块中的多版本存储为单独区域，用指针关联原始数据项。图6展示了具体的布局。对于WOS下每个数据项的版本记录直接组织成链表。
图6 ROS块的版本存储布局
·· 实验 ··
实验方面，Teseo使用了LDBC Benchmark，并挑选了三类图数据集: Graph500 (幂律分布)，Uniform(均匀分布)，Dota League(指数分布)。并对标了4个支持动态图上图分析的系统:Stinger, LLAMA, Graphone,LiveGraph。进行了三类实验:插入、更新、图分析。图7展示了实验使用的数据集及其规模。
图7 图数据集的信息
在所有的实验开始之前，对包含在Teseo在内的5个系统进行了扩展性测试，以此为标准，选取每个系统最好的并发度进行后续的实验。图8展示了这一实验结果。
图8 拓展性测实验结果
1.? 插入性能
插入实验中，所有系统从空图开始对图进行插入操作。图9展示了最终的测量结果。Stinger 在均匀图上表现较好，但是在幂律图和指数图上表现的较差。Graphone在实验中没有检查边是否存在，而且可拓展性较差。若按照其声称的加入检查边操作将会会导致性能大幅度下降。Teseo在所有的数据中的表现都较优。
图9 插入操作实验结果
2.? 更新性能
更新实验是在一张已建好的图上不断的插入和删除临时边，并且更新边涉及到的点满足图的度数分布。图10展现了更新操作的实验结果。类似的，Stinger在幂律图上表现的较差但是在均匀图上表现的最好。Teseo在两种图上表现都较优。图10右中展现了内存的使用情况，可以看到LLAM和LiveGraph的内存碎片随着时间大量增长。Graphone相对来说内存使用增长的较为平缓。而Stinger和Teseo一直保持在一个较为稳定的水平。在5个系统中，Stinger没有采用MVCC，所以内存使用不会有浮动。
图10更新操作实验结果
3.? 图分析性能
最后展示的是图分析能力的实验。本文将CSR作为基准线来进行对比。图11展现了部分的实验结果，其中衡量指标是CSR效率和对标系统效率的比值，即加速比。可以看到Teseo使用实际的点ID(相对于逻辑点ID)的运行效率相对于对标系统更优。由于结果较多，本文将不全部展示，有兴趣的读者可参考原文。
图11 图分析实验结果(单位:加速比)
