一种基于累积版本块的动态图存储与快照访问方法及系统

本发明涉及一种基于累积版本块的动态图存储与快照访问方法及系统，属于图存储。

背景技术：

1、图是一种由顶点和边构成的数据表示形式，其中顶点用于表示实体，边用于表示实体之间的关联关系。图数据能够描述社交网络中的用户关系、金融系统中的交易关系、推荐系统中的用户与内容关系以及网络安全系统中的设备通信关系。在上述应用中，图数据通常会持续发生变化，例如新增用户关系、删除失效连接、修改交易关系或者更新边的属性值。与此同时，系统还需要在图数据持续更新的过程中执行广度优先搜索、单源最短路径、连通分量、社区发现和pagerank等图分析任务。

2、动态图在不同时间可以形成不同的图状态。边的插入、删除或属性修改会使图由前一状态转换为后一状态，各时间点对应的图状态可以表示为图快照。图分析任务可能在不同时间开始，并需要在运行期间持续访问任务开始时对应的图状态。因此，图存储系统除接收图更新外，还需要保存或者恢复不同时间对应的图快照。

3、如图1所示，同一顶点的出边可以在不同时间发生修改，并在不同时间戳下形成相应的图快照。对于持续运行的图分析任务，即使系统已经接收了新的边更新，较早开始的读取任务仍可能需要访问更新前的边状态。由此，动态图存储不仅涉及当前图状态的存储，还涉及历史边状态的组织和访问。

4、邻接表和压缩稀疏行是图数据存储中常见的两类数据结构。邻接表为每个顶点分别维护一个邻居列表，邻居列表保存由该顶点出发的边或者目标顶点标识符。读取一个顶点的邻域时，可以先根据顶点索引定位对应的邻居列表，再依次访问其中的边。由于不同顶点的邻居列表相互独立，邻接表便于按照顶点划分数据，也便于对单个顶点的边执行插入、删除和扩容操作。邻居列表可以采用数组、链表、跳表、树或者分块数组等数据结构实现，因而能够根据查询和更新需求选择相应的内部组织方式。

5、压缩稀疏行（compressed sparse row，csr）使用顶点偏移数组和连续边数组表示图数据。顶点偏移数组记录每个顶点的邻接数据在边数组中的起始位置和结束位置，同一顶点的邻居在边数组中连续存储。查询一个顶点的邻居时，可以通过偏移数组直接确定对应的数据范围。由于多个顶点的边集中保存在连续存储区域内，csr具有存储结构紧凑、邻接扫描过程连续和额外指针较少等特点，适合需要反复遍历邻接数据的图分析任务，也便于多个计算线程按照顶点或边的范围划分扫描任务。

6、如图2所示，邻接表将各顶点的邻居分别存储，并通过顶点索引定位邻居列表；csr则通过偏移数组划分连续边数组中属于各顶点的邻接范围。两类结构均能支持按顶点访问邻接数据，但其物理组织方式不同。邻接表允许各顶点的邻居列表相对独立地调整，适合存在局部更新的图数据；csr能够在较少的辅助信息下连续保存边，适合稳定图快照上的大规模邻接扫描。在持续更新场景中，基于邻接表的存储结构需要处理邻居列表扩容、数据分散以及索引维护，csr则需要处理插入或删除引起的数据移动、空闲空间预留或者批量重组。

7、为了在图更新持续发生时提供一致的图快照，现有动态图存储系统通常采用事务处理和多版本并发控制。事务处理用于将一组相关的边更新作为一个整体执行，避免读取任务观察到只完成部分更新的中间状态。多版本并发控制在边发生更新时保留旧的边状态，并为更新后的边创建新版本。各版本记录携带相应的时间信息，读取任务根据自身的快照时间选择可见版本，从而使更新事务和图分析任务能够并发运行。

8、同时支持图更新事务、一致性快照读取和图分析任务的存储系统，可以称为事务型图存储系统。此类系统通常包括顶点索引和边存储两个部分。顶点索引用于将外部顶点标识符映射为内部标识符，并定位相应顶点的邻接数据；边存储用于保存当前邻接数据及多版本并发控制产生的历史边版本。

9、如图3所示，根据当前邻接数据与历史版本数据是否存储在相同的物理容器中，现有事务型图存储方法可以分为耦合式边版本存储和解耦式边版本存储。

10、耦合式边版本存储将当前边状态和历史更新记录存储在共同的数据区域中。zhu等人提出livegraph系统（参见文献zhu x, feng g, serafini m, et al. livegraph: atransactional graph storage system with purely sequential adjacency listscans[j]. proceedings of the vldb endowment, 2020, 13(7): 1020-1034.），该系统以追加日志形式维护顶点的邻接数据，并通过时间戳判断记录是否对目标快照可见。zhou等人提出gtx系统（参见文献zhou l, rayhan y, xing l, aref w g. gtx: a write-optimized latch-free graph data system with transactional support[j].proceedings of the acm on management of data, 2025, 3(3): 1-27.），该系统采用增量记录和增量链组织图更新，并结合索引加快单条边定位。上述系统通过追加式记录接收新的边状态，能够降低更新写入时的数据移动，但当前版本和历史版本可能共同存在于增量记录区域内。

11、解耦式边版本存储将当前邻接数据和历史版本数据分别组织。de leo等人提出teseo系统（参见文献de leo d, boncz p. teseo and the analysis of structuraldynamic graphs[j]. proceedings of the vldb endowment, 2021, 14(6): 1053-1066.），使用带有空隙的稀疏数组和多层树结构保存动态图数据。fuchs等人提出sortledton数据结构（参见文献fuchs p, giceva j, margan d. sortledton: auniversal, transactional graph data structure[j]. proceedings of the vldbendowment, 2022, 15(6): 1173-1186.），为每个顶点维护由多个有序边块组成的邻接集合，并使用跳表连接相应数据块。hao等人提出rapidstore系统（参见文献hao c, su j,sun s, et al. rapidstore: an efficient dynamic graph storage system forconcurrent queries[j]. proceedings of the vldb endowment, 2025, 18(10): 3587-3600.），将图数据与版本数据分离，并采用面向子图的并发控制和版本管理方式。上述系统将当前边状态保存在面向邻接查询的结构中，将被新版本替换的旧状态转移至独立历史版本区域，使当前邻接结构和历史版本结构能够分别组织。

12、上述现有系统采用了不同的邻接数据结构和历史版本组织方式。csr侧重于连续存储和邻接扫描，邻接表侧重于按顶点独立组织数据；耦合式版本存储侧重于通过追加记录接收更新，解耦式版本存储则使当前邻接结构与历史版本结构能够分别组织。在事务型图存储中，系统需要同时处理边更新、当前邻接扫描和历史快照访问，因此还需要确定历史版本之间的连接方式、版本可见性的判断方式以及已提交更新向读取任务发布的时机。

13、现有技术存在的缺点：

14、1. 现有耦合式边版本存储方法将当前邻接数据与历史版本记录存放在相同的物理存储区域中。边发生插入、删除或修改时，系统通常将新的边状态以增量记录或日志记录形式追加到已有存储区域，而不立即移除已经失效的记录。该方式能够减少更新操作引起的数据移动，但随着更新持续进行，同一顶点的存储区域中会同时包含当前有效记录、历史记录以及对目标快照不可见的记录。图分析任务扫描顶点邻居列表时，需要读取并检查这些记录，再根据时间戳或事务状态筛选目标快照下可见的边，使实际读取的数据量大于结果数据量。历史记录与当前邻接数据交错排列，还会降低邻接扫描的连续性，使连续邻接数组或csr类结构的顺序扫描优势难以保持。

15、2. 现有解耦式边版本存储虽然将当前邻接数据与历史版本数据分开保存，但历史版本通常按照每条边分别组织为由新到旧的版本链。读取较早图快照时，系统先检查主邻接结构中的当前边记录；若当前记录晚于目标快照时间，则需要沿该边对应的版本链依次访问更早的历史记录，直到找到有效时间范围包含目标快照时间的版本。在持续更新的图中，一条边可能形成多个历史版本，多个图分析任务也可能分别保持不同快照时间。此时，读取任务需要针对邻居列表中的多条边分别执行版本链访问，并反复读取对目标快照不可见的较新版本。由于各条边的历史记录通常分散在不同内存位置，该过程会产生指针跳转、随机内存访问和重复的可见性判断。

16、3. 现有多版本图存储方法还存在版本发布和历史回收粒度较细的问题。若以单个事务或单条边更新作为版本创建、发布和回收单位，在小事务数量较多时，系统需要频繁生成时间戳、修改共享事务状态、整理历史记录并通知读取任务可见。若每次事务提交后立即整理当前邻接数据和历史版本数据，更新线程会承担较多排序、数据移动和同步操作；若延迟处理历史版本，则需要额外判断已提交更新何时能够被读取任务安全访问。长时间运行的图分析任务还会保留较早快照，使系统不能立即删除旧版本；多个分析任务分别保留不同快照时，系统需要判断哪些版本仍可能被读取。在以单条边版本链为基础的存储方法中，历史版本的发布和回收往往需要沿多个版本链分别处理，增加元数据访问和同步开销。

技术实现思路

1、本发明的目的在于提出一种基于累积版本块的动态图存储与快照访问方法及系统，以解决图数据持续接收事务更新且图分析任务并发访问不同快照时，当前邻接数据与历史版本数据混合、快照读取依赖逐边版本链以及历史版本逐事务发布导致协调开销较高的技术问题，达到保持当前邻接扫描连续性、支持一致快照访问并降低历史版本读取、发布及回收开销的效果。

2、为实现上述目的，本发明采用以下技术方案。

3、一种基于累积版本块的动态图存储与快照访问方法，包括以下步骤：

4、将接收的图更新事务分配至更新批次，根据所述图更新事务更新主邻接结构，并将产生的历史边版本写入临时版本块；

5、在所述更新批次满足发布条件时，将所述临时版本块中的历史边版本按照源顶点和版本时间组织为累积版本块；

6、将所述累积版本块设置为不可变状态，按照版本时间标识将所述累积版本块连接至对应源顶点的累积版本块链，并更新对应更新批次的已发布可见边界；

7、根据包括源顶点标识符和目标快照时间的快照读取请求，访问对应源顶点的主邻接结构，并依据所述目标快照时间从对应源顶点的累积版本块链中确定候选累积版本块；

8、从所述主邻接结构和所述候选累积版本块中确定所述目标快照时间下可见的边版本，得到所述源顶点在所述目标快照时间下的出边集合。

9、进一步地，根据所述图更新事务更新主邻接结构，并将产生的历史边版本写入临时版本块，包括：

10、根据所述图更新事务定位源顶点的主邻接结构及待更新边状态；

11、根据更新类型更新所述待更新边状态，并将被替换或删除的边状态确定为历史边版本；

12、将更新后的边状态写入所述主邻接结构，并将所述历史边版本写入所述临时版本块。

13、进一步地，根据更新类型更新所述待更新边状态，并将被替换或删除的边状态确定为历史边版本，包括：

14、当所述更新类型为边插入时，根据所述图更新事务生成新的边状态；

15、当所述更新类型为边修改时，根据所述图更新事务生成新的边状态以替换所述待更新边状态，并将所述待更新边状态确定为历史边版本；

16、当所述更新类型为边删除时，移除所述待更新边状态或将所述待更新边状态设置为删除状态，并将删除前的待更新边状态确定为历史边版本。

17、进一步地，根据所述图更新事务更新主邻接结构，并将产生的历史边版本写入临时版本块，包括：

18、将所述图更新事务产生的边更新记录追加至所述主邻接结构的写缓冲区；

19、在所述写缓冲区满足归并条件时，按照目标顶点标识符将所述写缓冲区中的边更新记录与所述主邻接结构的有序边数组进行归并，并根据被替换或删除的边状态生成历史边版本；

20、根据归并结果更新所述有序边数组，并将所述历史边版本写入所述临时版本块。

21、进一步地，将接收的图更新事务分配至更新批次，包括：

22、确定当前开放的更新批次，并将接收的图更新事务分配至所述当前开放的更新批次；

23、在所述当前开放的更新批次满足封闭条件时，将所述当前开放的更新批次设置为封闭状态，并创建下一开放的更新批次；

24、将所述当前开放的更新批次封闭后接收的图更新事务分配至所述下一开放的更新批次。

25、进一步地，在所述当前开放的更新批次满足封闭条件时，将所述当前开放的更新批次设置为封闭状态，并创建下一开放的更新批次，包括：

26、对所述当前开放的更新批次中的边更新进行抽样，并在抽样命中时更新共享抽样计数；

27、在所述共享抽样计数达到抽样配额时，取得更新批次封闭控制权，并确认所述当前开放的更新批次未发生切换；

28、将所述当前开放的更新批次设置为封闭状态，创建所述下一开放的更新批次，并重置所述共享抽样计数。

29、进一步地，在所述当前开放的更新批次满足封闭条件时，将所述当前开放的更新批次设置为封闭状态，并创建下一开放的更新批次，包括：

30、获取所述当前开放的更新批次的更新数量、事务数量、持续时间和临时版本块占用空间中的至少一项批次状态数据；

31、将所述批次状态数据与对应的封闭阈值进行比较，确定所述当前开放的更新批次是否满足封闭条件；

32、在满足所述封闭条件时，将所述当前开放的更新批次设置为封闭状态，并创建所述下一开放的更新批次。

33、进一步地，确定所述更新批次满足发布条件，包括：

34、在所述更新批次封闭后停止向所述更新批次分配新的图更新事务；

35、检测分配至所述更新批次的图更新事务是否均已提交或终止；

36、在分配至所述更新批次的图更新事务均已提交或终止时，确定所述更新批次满足发布条件。

37、进一步地，检测分配至所述更新批次的图更新事务是否均已提交或终止，包括：

38、获取各工作线程的活动槽中记录的更新批次标识、访问模式和活动状态；

39、根据所述更新批次标识、所述访问模式和所述活动状态，确定是否存在仍访问所述更新批次的图更新事务；

40、在不存在仍访问所述更新批次的图更新事务时，确定分配至所述更新批次的图更新事务均已提交或终止。

41、进一步地，将所述临时版本块中的历史边版本按照源顶点和版本时间组织为累积版本块，包括：

42、从所述临时版本块中获取属于所述更新批次的有效历史边版本，并按照源顶点和版本时间对所述有效历史边版本进行归组；

43、按照创建时间对各组有效历史边版本进行排序；

44、将排序后的各组有效历史边版本连续存储，得到对应的累积版本块。

45、进一步地，将排序后的各组有效历史边版本连续存储，得到对应的累积版本块，包括：

46、根据各组有效历史边版本对应的源顶点、版本时间和记录数量生成块头，并为各组有效历史边版本分配记录区域；

47、将各组有效历史边版本连续写入对应的记录区域，并将所述记录区域与对应的块头关联，得到所述累积版本块。

48、进一步地，将所述累积版本块设置为不可变状态，按照版本时间标识将所述累积版本块连接至对应源顶点的累积版本块链，并更新对应更新批次的已发布可见边界，包括：

49、按照更新批次的先后顺序确定待发布的累积版本块，并将所述待发布的累积版本块设置为不可变状态；

50、按照版本时间标识建立所述待发布的累积版本块与对应源顶点的累积版本块链中相邻累积版本块之间的时间顺序关联；

51、在所述待发布的累积版本块连接完成后，按照更新批次的先后顺序更新所述已发布可见边界。

52、进一步地，更新对应更新批次的已发布可见边界，包括：

53、在更新批次发布前，将所述更新批次产生的更新后边状态保存在所述主邻接结构的写缓冲区；

54、在所述更新批次发布时，将所述更新后边状态并入所述主邻接结构，并将所述更新批次对应的累积版本块连接至所述累积版本块链；

55、在所述更新后边状态和所述累积版本块完成发布后，更新所述更新批次的已发布可见边界。

56、进一步地，更新对应更新批次的已发布可见边界，包括：

57、在图更新事务提交时，为所述图更新事务分配批次内提交序号，并根据更新批次标识和所述批次内提交序号确定版本时间标识；

58、根据所述版本时间标识确定更新后边状态的创建时间和被替换或删除的边状态的失效时间，并将所述更新后边状态写入所述主邻接结构；

59、在所述更新批次发布时，将对应的累积版本块连接至所述累积版本块链，并根据所述版本时间标识更新所述已发布可见边界。

60、进一步地，依据所述目标快照时间从对应源顶点的累积版本块链中确定候选累积版本块，包括：

61、获取所述累积版本块链中各累积版本块的版本时间标识；

62、将各累积版本块的版本时间标识与所述目标快照时间进行比较，排除在所述目标快照时间之前已失效的累积版本块；

63、将未被排除的累积版本块确定为所述候选累积版本块。

64、进一步地，将各累积版本块的版本时间标识与所述目标快照时间进行比较，排除在所述目标快照时间之前已失效的累积版本块，包括：

65、将所述版本时间标识中的更新批次标识与所述目标快照时间中的更新批次标识进行比较；

66、在所述版本时间标识与所述目标快照时间对应相同更新批次时，将所述版本时间标识中的批次内提交序号与所述目标快照时间中的批次内提交序号进行比较；

67、根据更新批次标识和批次内提交序号的比较结果，确定对应的累积版本块是否在所述目标快照时间之前已失效。

68、进一步地，根据包括源顶点标识符和目标快照时间的快照读取请求，访问对应源顶点的主邻接结构，并依据所述目标快照时间从对应源顶点的累积版本块链中确定候选累积版本块，包括：

69、根据所述源顶点标识符取得对应源顶点的并发读取保护；

70、在所述并发读取保护下获取所述主邻接结构、所述累积版本块链的稳定入口和所述已发布可见边界；

71、在取得所述稳定入口和所述已发布可见边界后释放所述并发读取保护；

72、根据所述目标快照时间和所述已发布可见边界，从所述稳定入口指向的累积版本块链中确定所述候选累积版本块。

73、进一步地，从所述主邻接结构和所述候选累积版本块中确定所述目标快照时间下可见的边版本，得到所述源顶点在所述目标快照时间下的出边集合，包括：

74、根据所述目标快照时间从所述主邻接结构中确定可见的当前边状态；

75、按照创建时间扫描所述候选累积版本块中的历史边版本，并根据创建时间和失效时间确定可见的历史边版本；

76、按照逻辑边合并所述可见的当前边状态和所述可见的历史边版本，得到所述源顶点在所述目标快照时间下的出边集合。

77、进一步地，按照创建时间扫描所述候选累积版本块中的历史边版本，并根据创建时间和失效时间确定可见的历史边版本，包括：

78、按照创建时间顺序将所述候选累积版本块中的历史边版本的创建时间和失效时间与所述目标快照时间进行比较；

79、在扫描到创建时间不早于所述目标快照时间的历史边版本时，停止扫描当前候选累积版本块；

80、将停止扫描前满足创建时间早于所述目标快照时间且失效时间不早于所述目标快照时间的历史边版本确定为所述可见的历史边版本。

81、进一步地，从所述主邻接结构和所述候选累积版本块中确定所述目标快照时间下可见的边版本，得到所述源顶点在所述目标快照时间下的出边集合，包括：

82、按照目标顶点标识符的顺序扫描所述主邻接结构中的当前边状态；

83、在当前边状态不满足所述目标快照时间时，根据所述当前边状态的前驱版本引用从所述候选累积版本块中定位同一逻辑边的历史边版本；

84、根据所述目标快照时间从定位的历史边版本中确定可见的边版本，并按照目标顶点标识符的顺序生成所述源顶点在所述目标快照时间下的出边集合。

85、一种基于累积版本块的动态图存储与快照访问系统，包括：

86、更新事务处理模块，用于将接收的图更新事务分配至更新批次，根据所述图更新事务更新主邻接结构，并将产生的历史边版本写入临时版本块；

87、版本块构造模块，用于在所述更新批次满足发布条件时，将所述临时版本块中的历史边版本按照源顶点和版本时间组织为累积版本块；

88、后台发布模块，用于将所述累积版本块设置为不可变状态，按照版本时间标识将所述累积版本块连接至对应源顶点的累积版本块链，并更新对应更新批次的已发布可见边界；

89、快照读取模块，用于根据包括源顶点标识符和目标快照时间的快照读取请求，访问对应源顶点的主邻接结构，并依据所述目标快照时间从对应源顶点的累积版本块链中确定候选累积版本块；

90、出边集合生成模块，用于从所述主邻接结构和所述候选累积版本块中确定所述目标快照时间下可见的边版本，得到所述源顶点在所述目标快照时间下的出边集合。

91、本发明取得了如下有益效果。

92、1.本发明将当前边状态、尚未发布的历史边版本和已经发布的历史边版本分别存储于主邻接结构、临时版本块和累积版本块链中，并通过有序边数组连续保存整理后的当前边状态，通过写缓冲区接收近期边更新，使当前邻接扫描无需同时访问大量历史边版本和失效边状态，能够减少版本元数据及无效数据的读取，保持源顶点出边集合的连续存储和顺序访问。

93、2.本发明将同一源顶点下具有相同失效时间或相同更新批次标识的多个历史边版本集中存储于连续的累积版本块中，并按照创建时间排列块内历史边版本，同时通过前驱版本引用保留同一逻辑边不同版本之间的继承关系，改变了以逻辑边为单位分散组织历史版本的物理结构，能够减少版本指针跳转和分散内存访问，并兼顾连续快照扫描与指定逻辑边历史版本定位。

94、3.本发明在快照读取过程中先根据累积版本块的版本时间标识执行块级可见性判断，整体排除不可能包含目标快照时间下可见边版本的累积版本块，再按照创建时间顺序连续扫描候选累积版本块，并在后续历史边版本均不满足可见条件时停止扫描，能够减少逐边版本链访问、不可见版本逐条检查以及候选累积版本块内无效记录的访问。

95、4.本发明将多个图更新事务划分至更新批次，使更新批次依次经历开放状态、封闭状态、已提交状态和已发布状态，并将图更新事务产生的历史边版本先追加至临时版本块，再按照更新批次顺序批量构造和发布不可变的累积版本块；更新批次封闭能够通过抽样计数触发，图更新事务完成状态能够通过工作线程活动槽异步检测，从而减少每次边更新或事务提交时的历史版本整理以及对共享更新批次状态的频繁协调。

96、5.本发明采用由更新批次标识和批次内提交序号组成的双粒度时间戳，在保持按照更新批次构造和发布累积版本块的同时区分同一更新批次内不同图更新事务的提交次序，并通过顶点级并发控制保护主邻接结构、临时版本块和累积版本块链入口，使读取任务能够访问稳定入口指向的不可变累积版本块；在历史边版本不再被活动快照访问且不存在有效前驱版本引用时，以累积版本块为单位进行回收，能够保证快照可见性并降低历史数据回收过程中的元数据访问和结构修改开销。