分布式图数据库中可达性索引的分层构建方法和系统

摘要

本申请涉及一种分布式图数据库中可达性索引的分层构建方法和系统，该方法基于图数据的分区特性，采用多种随机游走方式对跨分区和分区内的图数据分别构建可达性索引，形成双层可达性索引，并在构建双层可达性索引的过程中，随着图数据库中数据的持续更新，控制可达性索引也在线持续更新，其中针对跨分区这种较高成本的索引，和分区内这种较低成本的索引，采用不同的索引更新频率，控制跨分区的索引的变动频率低于分区内的索引的变动频率，以减少跨分区的网络通信开销，通过本申请，解决了相关技术中缺乏适用于分布式图数据库的可达性索引构建方法的问题。

权利要求

1.一种分布式图数据库中可达性索引的分层构建方法，其特征在于，所述方法包括：在分布式图数据库内部，基于图数据的分区特性，形成双层可达性索引：采用多种随机游走方式对跨分区内的图数据构建可达性索引时，以第一候选集中的节点作为索引的链表的元素，选择与所述节点相邻且未游走过的分区中的其他节点加入所述链表；

采用多种随机游走方式对分区内的图数据构建可达性索引时，以第二候选集中的节点作为索引的链表的元素，选择与所述节点相邻且与所述节点处于相同分区内的节点加入所述链表；

其中，在构建双层可达性索引的过程中，随着图数据库中数据的持续更新，控制跨分区的索引的变动频率低于分区内的索引的变动频率。

2.根据权利要求1所述的方法，其特征在于，所述随机游走的方式包括：在同一个分区内，赋予当前节点的每个邻居节点相同的概率，随机选择与所述节点相邻的节点加入所述链表；或者，根据当前节点的邻居与当前节点上一步的来源节点的距离，赋予每个邻居节点对应的概率，根据概率选择与所述节点相邻的节点加入所述链表。

3.根据权利要求2所述的方法，其特征在于，所述随机游走的方式还包括：确定当前节点是否有邻居节点落在所述第一候选集或所述第二候选集中，若是，则选择所述邻居节点加入所述链表。

4.根据权利要求1所述的方法，其特征在于，所述方法包括：

在所有分区均已被访问的情况下，或者，在由跨分区链表组成的集合占用的内存达到第一阈值的情况下，终止对跨分区可达性索引的更新；

在由分区内链表组成的集合占用的内存达到第二阈值的情况下，终止对本分区可达性索引的更新。

5.根据权利要求1所述的方法，其特征在于，所述方法还包括：

在构建双层可达性索引的过程中，针对第一候选集和第二候选集，不断换出未被使用的链表上的点；通过在同分区内或者跨分区进行多组随机游走，确定序列中出现频率最高的点或出入度较高的点并将其换入，以降低假阴率。

6.根据权利要求1所述的方法，其特征在于，所述方法包括：

在客户端对边发起删除操作的情况下，删除边的两端的节点在分区内所有链表中的对应节点及其邻边，并删除边的两端的节点在跨分区链表中处于链表相邻位置的对应节点及其邻边；

响应于客户端的删除操作，执行图数据库的边删除操作的原有逻辑。

7.一种分布式图数据库中可达性索引的分层构建系统，其特征在于，所述系统包括：双层索引模块，用于基于图数据的分区特性，采用多种随机游走方式对跨分区和分区内的图数据分别构建可达性索引，形成双层可达性索引：采用多种随机游走方式对跨分区内的图数据构建可达性索引时，以第一候选集中的节点作为索引的链表的元素，选择与所述节点相邻且未游走过的分区中的其他节点加入所述链表；

采用多种随机游走方式对分区内的图数据构建可达性索引时，以第二候选集中的节点作为索引的链表的元素，选择与所述节点相邻且与所述节点处于相同分区内的节点加入所述链表；

所述双层索引模块包括频率控制单元，所述频率控制单元用于，在构建双层可达性索引的过程中，随着图数据库中数据的持续更新，控制跨分区的索引的变动频率低于分区内的索引的变动频率。

8.一种电子装置，包括存储器和处理器，其特征在于，所述存储器中存储有计算机程序，所述处理器被设置为运行所述计算机程序以执行权利要求1至6中任一项所述的分布式图数据库中可达性索引的分层构建方法。

9.一种存储介质，其特征在于，所述存储介质中存储有计算机程序，其中，所述计算机程序被设置为运行时执行权利要求1至6中任一项所述的分布式图数据库中可达性索引的分层构建方法。

说明书

分布式图数据库中可达性索引的分层构建方法和系统

技术领域

[0001] 本申请涉及可达性索引技术领域，特别是涉及一种分布式图数据库中可达性索引的分层构建方法和系统。

背景技术

[0002] 以图论理论为基础的图结构被广泛应用于各个领域，如社交、通信、欺诈检测等。通过图结构可以构建社交网络、通信网络、欺诈链等，从而发现有价值的数据。图结构中任意两个点之间可能存在关系，其核心要素有：点（也称为节点）和边（也称为关联或关系）。例如，社交网络中的人可以看做图中的节点，人与人之间的关系就是节点之间的边，由于人与人之间可以通过“转账”、“关注”等方式连接起来，边可以对应不同的关系。图数据库是一种擅长于处理图这种数据结构的数据库，它可以在毫秒级别完成图的遍历操作。

[0003] 随着现代社会信息的不断增加，大规模图技术被广泛采用。可达性是图论中的一个重要问题，其目的是研究图中的两点之间是否存在一条路径。换句话说，可达性问题，就是判断两个点之间是不是有一条通路，只要有一条通路，就叫做“可达”（reachable）。可达性技术的应用场景包括在安全网络中，可达性技术可以用于检查是否存在攻击者和被攻击设备之间的路径；在生物基因网络中，可以检查两个基因之间是否存在间接的表达控制关系；在传染病传播网络中，检查两个患者是否存在传染因果链条等等。

[0004] 技术上，在图数据库中，可达性索引是可达性技术中一种较为常见的实现方式。通过构建可达性索引的方式，不但可以用于回答可达性问题；此外还可以大大加速相关图算法的性能，例如加快子图查询和最短路径查询性能。迄今为止，已经有大量可达性索引技术被提出，包括传递闭包、基于链上编码的索引方案、基于2/3‑hop的技术、基于树的方式。这些方法在小规模数据集上，在构建时间、索引大小、查询耗时上，已经取得了一定的性能权衡，并且已经在一些图数据库中有对应商业产品功能。

[0005] 但由于万亿点边级别的数据量远远超出单机图数据库的处理能力，目前分布式图数据库逐渐成为市场主流。在分布式的图数据库系统，由于存在大量基于网络的跨进程通信，多台机器之间的网络通信开销巨大，特别是索引构建和更新时的开销太过巨大，适用于单机系统的可达性索引技术对于分布式图数据库来说，缺乏实用性。

[0006] 针对相关技术中，缺乏适用于分布式图数据库的可达性索引构建方法的问题，尚未提出有效的解决方案。

发明内容

[0007] 本申请实施例提供了一种分布式图数据库中可达性索引的分层构建方法和系统，以至少解决相关技术中，缺乏适用于分布式图数据库的可达性索引构建方法的问题。

[0008] 第一方面，本申请实施例提供了一种分布式图数据库中可达性索引的分层构建方法，所述方法包括：

[0009] 基于图数据的分区特性，采用多种随机游走方式对跨分区和分区内的图数据分别构建可达性索引，形成双层可达性索引；

[0010] 其中，在构建双层可达性索引的过程中，随着图数据库中数据的持续更新，控制跨分区的索引的变动频率低于分区内的索引的变动频率。

[0011] 在其中一些实施例中，构建双层可达性索引过程包括：

[0012] 在构建跨分区可达性索引时，以第一候选集中的节点作为索引的链表的元素，选择与所述节点相邻且未游走过的分区中的其他节点加入所述链表；

[0013] 在构建分区内可达性索引时，以第二候选集中的节点作为索引的链表的元素，选择与所述节点相邻且与所述节点处于相同分区内的节点加入所述链表。

[0014] 在其中一些实施例中，所述随机游走的方式包括：

[0015] 在同一个分区内，赋予当前节点的每个邻居节点相同的概率，随机选择与所述节点相邻的节点加入所述链表；或者，根据当前节点的邻居与当前节点上一步的来源节点的距离，赋予每个邻居节点对应的概率，根据概率选择与所述节点相邻的节点加入所述链表。

[0016] 在其中一些实施例中，所述随机游走的方式还包括：

[0017] 确定当前节点是否有邻居节点落在所述第一候选集或所述第二候选集中，若是，则选择所述邻居节点加入所述链表。

[0018] 在其中一些实施例中，所述方法包括：

[0019] 在所有分区均已被访问的情况下，或者，在由跨分区链表组成的集合占用的内存达到第一阈值的情况下，终止对跨分区可达性索引的更新；

[0020] 在由分区内链表组成的集合占用的内存达到第二阈值的情况下，终止对本分区可达性索引的更新。

[0021] 在其中一些实施例中，所述方法还包括：

[0022] 在构建双层可达性索引的过程中，针对第一候选集和第二候选集，不断换出未被使用的链表上的点；通过在同分区内或者跨分区进行多组随机游走，确定序列中出现频率最高的点或出入度较高的点并将其换入，以降低假阴率。

[0023] 在其中一些实施例中，所述方法包括：

[0024] 在客户端对边发起删除操作的情况下，删除边的两端的节点在分区内所有链表中的对应节点及其邻边，并删除边的两端的节点在跨分区链表中处于链表相邻位置的对应节点及其邻边；

[0025] 响应于客户端的删除操作，执行图数据库的边删除操作的原有逻辑。

[0026] 第二方面，本申请实施例提供了一种分布式图数据库中可达性索引的分层构建系统，所述系统包括：

[0027] 双层索引模块，用于基于图数据的分区特性，采用多种随机游走方式对跨分区和分区内的图数据分别构建可达性索引，形成双层可达性索引；

[0028] 所述双层索引模块包括频率控制单元，所述频率控制单元用于，在构建双层可达性索引的过程中，随着图数据库中数据的持续更新，控制跨分区的索引的变动频率低于分区内的索引的变动频率。

[0029] 第三方面，本申请实施例提供了一种电子装置，包括存储器和处理器，所述存储器中存储有计算机程序，所述处理器被设置为运行所述计算机程序以执行所述分布式图数据库中可达性索引的分层构建方法。

[0030] 第四方面，本申请实施例提供了一种存储介质，所述存储介质中存储有计算机程序，其中，所述计算机程序被设置为运行时执行所述分布式图数据库中可达性索引的分层构建方法。

[0031] 相比于相关技术中，缺乏适用于分布式图数据库的可达性索引构建方法的问题，本申请实施例通过基于图数据的分区特性，采用多种随机游走方式对跨分区和分区内的图数据分别构建可达性索引，形成双层可达性索引，并在构建双层可达性索引的过程中，随着图数据库中数据的持续更新，控制可达性索引也在线相应持续更新，其中针对跨分区这种较高成本的索引，和分区内这种较低成本的索引，采用不同的索引更新频率，控制跨分区的索引的变动频率低于分区内的索引的变动频率，以减少跨分区的网络通信开销，解决了相关技术中缺乏适用于分布式图数据库的可达性索引构建方法的问题；

[0032] 另外，这种分层构建索引的方式，还可以减少索引占用的空间，跨分区索引和分区内索引，可以各自设定占用空间（硬盘和内存）的上限，而相关技术中的做法，通常只能限定索引能处理的路径最大长度（k‑hop），本申请实施例的索引占用空间更小；

[0033] 本申请实施例还通过多种随机游走方式，来逐步寻找图中有着重要性的“中心节点”，索引结果不会有假阳性，并且通过重采样不断换出未被使用的链表上的点，换入序列中出现频率最高的点或出入度较高的点等方式，逐步优化索引结构，在有限的空间容量下，迭代找到假阴率更低的索引，降低假阴率；

[0034] 本申请实施例支持分布式图数据库的增删改查，在客户端对边发起删除操作的情况下，先删除索引中的对应内容，再响应于客户端的删除操作，执行图数据库的边删除操作的原有逻辑，索引无需离线构建。

附图说明

[0035] 此处所说明的附图用来提供对本申请的进一步理解，构成本申请的一部分，本申请的示意性实施例及其说明用于解释本申请，并不构成对本申请的不当限定。在附图中：

[0036] 图1是根据本申请实施例的边切分的数据库存储数据的方式示意图；

[0037] 图2是根据本申请实施例的分布式图数据库中可达性索引的分层构建方法的示意图；

[0038] 图3是根据本申请实施例的node2vec模型提出的一种游走方式的示意图；

[0039] 图4是根据本申请实施例的广度优先遍历和深度优先遍历的示意图；

[0040] 图5是根据本申请实施例的全局的协调者角色的示意图；

[0041] 图6是根据本申请实施例的电子设备的内部结构示意图。

具体实施方式

[0042] 为了使本申请的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本申请进行描述和说明。应当理解，此处所描述的具体实施例仅仅用以解释本申请，并不用于限定本申请。基于本申请提供的实施例，本领域普通技术人员在没有作出创造性劳动的前提下所获得的所有其他实施例，都属于本申请保护的范围。

[0043] 显而易见地，下面描述中的附图仅仅是本申请的一些示例或实施例，对于本领域的普通技术人员而言，在不付出创造性劳动的前提下，还可以根据这些附图将本申请应用于其他类似情景。此外，还可以理解的是，虽然这种开发过程中所作出的努力可能是复杂并且冗长的，然而对于与本申请公开的内容相关的本领域的普通技术人员而言，在本申请揭露的技术内容的基础上进行的一些设计，制造或者生产等变更只是常规的技术手段，不应当理解为本申请公开的内容不充分。

[0044] 在本申请中提及“实施例”意味着，结合实施例描述的特定特征、结构或特性可以包含在本申请的至少一个实施例中。在说明书中的各个位置出现该短语并不一定均是指相同的实施例，也不是与其它实施例互斥的独立的或备选的实施例。本领域普通技术人员显式地和隐式地理解的是，本申请所描述的实施例在不冲突的情况下，可以与其它实施例相结合。

[0045] 除非另作定义，本申请所涉及的技术术语或者科学术语应当为本申请所属技术领域内具有一般技能的人士所理解的通常意义。本申请所涉及的“一”、“一个”、“一种”、“该”等类似词语并不表示数量限制，可表示单数或复数。本申请所涉及的术语“包括”、“包含”、“具有”以及它们任何变形，意图在于覆盖不排他的包含；例如包含了一系列步骤或模块（单元）的过程、方法、系统、产品或设备没有限定于已列出的步骤或单元，而是可以还包括没有列出的步骤或单元，或可以还包括对于这些过程、方法、产品或设备固有的其它步骤或单元。本申请所涉及的“连接”、“相连”、“耦接”等类似的词语并非限定于物理的或者机械的连接，而是可以包括电气的连接，不管是直接的还是间接的。本申请所涉及的“多个”是指两个或两个以上。“和/或”描述关联对象的关联关系，表示可以存在三种关系，例如，“A和/或B”可以表示：单独存在A，同时存在A和B，单独存在B这三种情况。字符“/”一般表示前后关联对象是一种“或”的关系。本申请所涉及的术语“第一”、“第二”、“第三”等仅仅是区别类似的对象，不代表针对对象的特定排序。

[0046] 本申请实施例以三种主流的分布式图数据库（Nebula Graph，Huge Graph，Janus Graph）方案来说明其分区存储特点（三者是类似的，本申请以Nebula Graph来举例。Neo4j 4.x 的分布式版本，虽然存储格式不同，但分区原理是类似的，并不影响本申请的适用。事实上，只要采用分区方式的分布式图数据库，其可达性索引都可以参考本申请方式来构建。）另外，需要说明的是，本申请所需的图分区，对在一个分区内的图结构没有任何额外的连接要求；例如并不需要使用Metis进行一次预先重分区，或者预先得到联通分量(Connect Component)，或者预先得到每个点的出入度。Nebula Graph图数据将点和边存储在不同逻辑分区（Partition）上，例如，分区x（Partition x）、分区y（Partition y）等，使用边切分的方式存储边数据。图1是根据本申请实施例的边切分的数据库存储数据的方式示意图，如图
1所示，切分后，点存储在不同的分区（例如分区x、分区y、……），图中的数字1、2、3分别代表图数据库中存储在不同分区内的点，一条物理边（例如边A）切分后存储为两条逻辑边，这两条边分别与起始点、目的点存储在一个分区，具体存储格式如下：

[0047] 在分区x中，边A的出向（EdgeA_Out）：

[0048] 在分区y中，边A的入向（EdgeA_In）：

[0049]

[0050] 分布式场景下，图数据量达到万亿点边级别，数据分区在不同机器上，跨机器的通信成本是同一个机器内（分区内）的成百上千倍，通信成本存在巨大差异；现有技术中，没有查到有专利或者论文考虑了这种分两层的通信成本差异问题，基于此发现，本申请实施例提出了针对跨分区和分区内的不同变动策略，高成本的索引（跨分区）应该减少变动；低成本的索引（分区内）可以多变动。本申请提供了一种分布式图数据库中可达性索引的分层构建方法，图2是根据本申请实施例的分布式图数据库中可达性索引的分层构建方法的示意图，如图2所示，该流程包括如下步骤：

[0051] 步骤S201，基于图数据的分区特性，采用多种随机游走方式对跨分区和分区内的图数据分别构建可达性索引，形成双层可达性索引；

[0052] 步骤S202，其中，在构建双层可达性索引的过程中，随着图数据库中数据的持续更新，控制跨分区的索引的变动频率低于分区内的索引的变动频率。

[0053] 通过上述步骤S201至S202，相对于相关技术中缺乏适用于分布式图数据库的可达性索引构建方法的问题，本申请实施例通过基于图数据的分区特性，采用多种随机游走方式对跨分区和分区内的图数据分别构建可达性索引，形成双层可达性索引，并在构建双层可达性索引的过程中，随着图数据库中数据的持续更新，控制可达性索引也在线持续更新，其中针对跨分区这种较高成本的索引，和分区内这种较低成本的索引，采用不同的索引更新频率，控制跨分区的索引的变动频率低于分区内的索引的变动频率，以减少跨分区的网络通信开销，解决了相关技术中缺乏适用于分布式图数据库的可达性索引构建方法的问题；另外，这种分层构建索引的方式，还可以减少索引占用的空间，跨分区索引和分区内索引，可以各自设定占用空间（硬盘和内存）的上限，而相关技术中的做法，通常只能限定索引能处理的路径最大长度（k‑hop），本申请实施例的索引占用空间更小。

[0054] 本申请实施例还通过多种随机游走方式，来逐步寻找图中有着重要性的“中心节点”，索引结果不会有假阳性。本申请根据随机游走的办法找到图里这些中心节点，而现有的相关技术，则是将所有节点一视同仁处理，忽视了图论中的幂率特征（少数几个点联通了绝大多数）；或者，现有的相关技术考虑了节点的出入度，却忽视了出入度无法表征的“孤岛”（少数与世隔绝的点）；或者，现有的相关技术需要依赖联通分量，但实际上在大图上计算联通分量的成本极大，计算联通分量的成本足以完成可达性计算。

[0055] 至于随机游走的算法，考虑到图的随机游走是图数据分析和图机器学习的重要工具，随机游走的算法有很多方式，在本申请中并不依赖特定的游走算法。在图随机游走的计算中，会有很多游走者，每个游走者从给定的起点开始，每次从当前点的邻边中（以某种概率函数随机)选择一条边，并沿着该边走到下一个点，直到达到终止条件。通过图的随机游走计算，可以发现被很多游走者访问到的点。其本质是通过一定的随机采样来得到近似的图结构，通过控制随机性的产生方式，来得到有倾向性的图结构采样。例如，图3是根据本申请实施例的由node2vec模型提出的一种游走方式的示意图，图4是根据本申请实施例的广度优先遍历和深度优先遍历的示意图。如图3和图4所示，图4中的箭头代表走向，当前位置在节点u，如果是广度优先遍历（Breadth First Search，简称BFS），则下一步走节点s1，s2，s3中的一个，如果是深度优先遍历（Depth First Search，简称DFS），则下一步走s4；通过控制游走概率，可以控制优先向远端走(DFS)，或者优先向近距离走(BFS)；同时，如图3所示，上一步在节点t，当前位置在节点v，下一步走x1，x2，x3中的哪一个，可以根据设定概率p和概率q来确定，图中α=1代表下一步访问x1节点的概率，α=1/q代表下一步访问x2节点的概率，α＝1/q代表下一步访问x3节点的概率，α＝1/p代表回退到顶点t的概率。本申请同样适用“边上带权重”的情况。最后需要说明的是，无向图的边是没有方向的，例如 A,B 两者是好友，这是没有方向的；有向图的边是有方向的，例如 AB 之间转账，转账是有方向的；本申请技术方案对于有向图和无向图均适用，在本申请中，为了简化描述复杂度，以无向图的可达性为例。

[0056] 本申请还提供了几个实施例涉及的技术功能，这些技术功能是后续算法中所依赖的基本操作；通常各种分布式图数据库都有相应的操作，即使没有，为其添加也较为简单。技术功能1，判断两个点A，B是否直接相连(相邻)，不论A，B两点是在同一个分区，或者不同分区，都可以通过一次查询就完成，而不需要跨分区进行网络查询，例如，在Nebula Graph、Huge Graph，或者在Janus Graph中都是存储引擎一次KV查找，使用符号(A)−(B)来表示A，B直接相连。技术功能2，对于点A，要找到其所有邻居，通过范围查询就可以完成，不需要跨分区的网络查询，获取A的所有邻居操作，记为符号N(A)。技术功能3，判断点A在哪个分区，其操作是一次简单计算，通常是一个Hash运算后取模计算；或者是一个查表操作。技术功能4，随机游走，在本申请中，主要会使用三种类型的随机游走，第一种，在同一个分区内，给每个邻居相同的概率，第二种，在同一个分区内，根据<当前点v上一步的来源节点t>和<当前点的邻居与t之间的距离>控制其概率（这也是node2vec方法中控制BFS或者DFS的方式），第三种，视v的邻居中，是否有候选集中的点；如果有则选用该点。

[0057] 技术功能5，协调者，本申请不依赖于外部的数据库，因此，本申请中每个分区只能先处理各自内部的部分（构建各自的局部的可达性），然后再将少量需要统一处理的信息交给协调者统一处理；也正是因为缺乏全局信息，因此才提出分层构建的方式。为了协调跨分区的通信问题，图5是根据本申请实施例的全局的协调者角色的示意图，如图5所示，Graph数据库中包括分区1、分区2、分区3和协调者，DVi代表跨分区集合中落在分区i内的部分点，CVi代表落在分区i的分区内集合中的部分点，Ci代表分区i内的其他点，V1、V2代表协调者D中的节点，从而基于图数据的分区特性，采用多种随机游走方式对跨分区和分区内的图数据分别构建可达性索引，其中协调者可以由某个分区兼任、或者在图数据库中由其他引擎兼任，目的是为了处理跨分区的索引构建。

[0058] 本申请还提供了几个实施例涉及的主要符号说明，|·|用于取集合元素的数量。∏是累乘符号。∀取集合中所有元素。∃元素不存在。A+=a，A−=a表示向左侧A增加或者删除右侧a。对于每个分区Pi，都存在集合DVi和集合CVi：DVi是Pi内的部分节点的集合。CVi是Pi内的部分节点的集合。{P1，P2，..Pn}，n是分区数量。符号∼用于表示可达。不难证明∼有传递性、对称性：∃a，b:a∼b⇐⇒b∼a；∃A，BA∼B⇐⇒a∼b，∀a∈A，∀b∈B。

[0059] 本申请实施例还提供了跨分区的可达性索引的构建代码，以下算法1由协调者运行：

[0060] 算法1：跨分区的可达性索引构建

[0061] // 初始化定义部分：

[0062] 1  各分区将 DVi 发送给协调者 // RPC

[0063] 2  定义未访问分区的集合为 AP = {P2, ..Pn} // 从 P1 开始处理

[0064] 3  待访问的下个分区为 N P = Pi, i = 1

[0065] 4  初始化为空; //  是一个链表 (list)，< v1, v2... > 下标为分区id，上标为链表内 id

[0066] 5  D = { ..} 是一个集合初始化为空 // 由跨分区链表 i 组成

[0067]    // 循环处理部分:

[0068] 6  while |AP|  0 // 终止条件

[0069] 7  do

[0070] 8        k=1;

[0071] 9        for ∈ DVi  do

[0072]       // 取 DVi 中的第 k 个节点

[0073] 10       .append() ;

[0074] 11       Let Vn = N (v) ∩ AP    // RPC: 取其邻居且未游走过的分区[0075] 12       for ∀vj ∈ Vn  do

[0076] 13           if vj   DVj then

[0077] 14               j = Rand(AP ) // 否则 AP 随机选择一个分区

[0078] 15           .append(vj ) // 加到链表上

[0079] 16       end

[0080] 17       NP = Pj , AP −= Pj , i = j // 下一个处理 Pj

[0081] 18  end

[0082] 19  D+ = {i } // 第一个点的链表处理完

[0083] 20  end

[0084] 其中，终止条件为：除了AP中所有元素都已经被处理完，也可以为D占用内存达到阈值（例如5%）。以上流程的主要过程是：协调者构建跨分区的链表，从候选集DVi中每个元素开始，进行一个深度优先的游走；游走时，期望下一个点在未访问过的分区且优先其也在DV中。以上流程中，跨网络操作以“//RPC”注释说明：包括初始化时获取DVi，和N()操作需要协调者远程到对应分区请求——由于N()在循环体中，因此它将被最多远程执行|DV|∗n次。值得说明的是，流程的循环部分(while,for)可以并发多线程处理，即第i次与第j次循环执行之间并无依赖。

[0085] 本申请实施例还提供了分区内的可达性索引的构建代码，代码流程上，分区内可达性索引的构建方式类似于跨分区可达性索引构建，但不需要任何远程调用：

[0086] 算法2：分区 Pi 内可达性索引

[0087] // 初始化定义部分

[0088] 1 未访问分区的集合为 AP = Pi

[0089] 2 待访问的下个分区为 N P = Pi.

[0090] 3  初始化为空 // i 是一个链表，=< v1, v2... > 表示在处理的

[0091] 一条链表, 元素为节点

[0092] 4 Ci = { , ..} 是一个集合, 由分区内链表组成

[0093] // 循环处理部分

[0094] 5 while end‑condition // 终止条件

[0095] 6 do

[0096] 7 for ∀  ∈ DVi do

[0097] // 取 DVi 中的第一个节点

[0098] 8   .append() ;

[0099] 9   Let V n = N () ∩ Pi // 取其邻居且在相同分区，这里不需要 RPC；

[0100] 10  if |V n| = 0 then continue ;

[0101] 11   for ∀vj ∈ Vn do

[0102] 12   j = Randwalk(Vn) // 随机游走方式可以为上文提到的技术特点 4 中任一种

[0103] 13   .append(vj ) // 加到链表上

[0104] 14   end

[0105] 15  end

[0106] 16  Ci+ =  // 第一个点的链表处理完

[0107] 17 end

[0108] 终止条件为C占用本分区内存达到阈值（例如5%）。这种分层构建索引的方式，可以减少索引占用的空间，跨分区索引和分区内索引，可以各自设定占用空间（硬盘和内存）的上限，而相关技术中的做法，通常只能限定索引能处理的路径最大长度（k‑hop），本申请实施例的索引占用空间更小。

[0109] 本申请实施例还提供了任意两点可达性判定的代码，其中所述“一般可达性问题”是基于BFS/DFS方式的经典算法，此处不再赘述：

[0110] 算法3：查询分区 Pi 内 vi 和分区 Pj 内 vj 的可达性

[0111] // 并发的，在分区 Pi 中:

[0112] 1 if vi ∼ R(vi) := {, ...} then

[0113] 2  将 R(vi) 发送给协调者

[0114] 3 else

[0115] 4  退化为一般可达性问题; 并将 vi 加入 DVi ;

[0116] 5  return 不可达

[0117] 6 end

[0118] // 并发的，在分区 Pj 中:

[0119] 7 if vj ∼ R(vj ) := {, ...} then

[0120] 8  将 R(vj ) 发送给协调者

[0121] 9 else

[0122] 10 退化为一般性问题; 并将 vj 加入 DVj ;

[0123] 11  return 不可达

[0124] 12 end

[0125] //  在协调者处

[0126] 13 if 存在一个链表 Dk: 使得 Ci ∼ Dk, 且Dk ∼ Cj  , Ci ∈ R(vi), Cj ∈ R(vj ) then

[0127] 14  return 可达

[0128] 15 else

[0129] 16  return 不可达

[0130] 17 end

[0131] 在本申请中，对于图数据库本身的更新是实时发生的，索引也实时更新。考虑到图数据库中的数据是持续更新的，因此可达性索引也必须持续更新；而离线批量构建索引的方式比较容易，但时效性很差，要等待漫长的构建过程；通常，用户希望通过即时查询方式知道是否存在一条路径从起点u到达终点t，而不是通过离线预计算加查表的方式来判断可达性——即，前一晚通过大数据方案计算所有可能的两两可达组合，并存储在redis中，白天业务系统直接在redis中查表，这样的方案时效性只能做到T+1；此外，包括专利CN103399902B在内的现有技术公开的，在静态数据上的编码优化规则和技巧，也难以利用到实时更改的数据上。本申请实施例支持分布式图数据库的增删改查，在客户端对边发起删除操作的情况下，先删除索引中的对应内容，再响应于客户端的删除操作，执行图数据库的边删除操作的原有逻辑，索引无需离线构建。在其中一些实施例中，针对图数据库实时的写入和删除，考虑到在大多数业务中，写入的数量远多于删除，新的点和边的写入不会破坏原有的可达性，但是边的删除会导致可达性索引错误。为了避免这种情况，当客户端发起删除操作时，要先更新索引，再删除图数据库中的数据。这里以一条边(vi)−(vj )，vi∈Pi，vj∈Pj的删除为例，说明如何相应更新索引：

[0132] 算法4：删除边 (vi) − (vj )

[0133] 1 if vi, vj 是否在同一个分区 i 中 then

[0134] 2  在分区 i 中:

[0135] 3  检查 vi ∼ R(vi) := { , ...}，从中删除 vj (如果存在)；

[0136] 4  检查 vj ∼ R(vj ) := { , ...}，从中删除 vi(如果存在)

[0137] 5 else

[0138] 6  则发送到协调者, 在 D 中的所有链表中删除直接相邻的两个元素 < vi, vj >(如果存在)

[0139] 7  end

[0140] 8 继续图数据库边删除操作的原有逻辑

[0141] 点vi的删除等价于删除该点周围所有的邻边和该点，其中邻边的删除可以重复以上Algorithm 4，而点vi本身的删除还需要在CVi、DVi中对应删除。相比于相关技术，由于一些相关技术中（例如专利CN109658094B、CN108021610A）是依赖于一个外部的数据库（保存图数据的数据库）；服务器集群与工作机集群可以从在该数据库中，获取全局的图信息，因此需要先从外部数据库读取，加工，然后写回外部数据库；这是一个长耗时的过程；这期间发生的图数据更新，都只能放在下一轮<读取，加工，写回>中，这会是第二轮长耗时的过程；因此不适合于数据频繁更新的情况，而本专利可以实时的更新（增加、删除），因此在时效性上更有优势。

[0142] 由于是根据随机游走的办法，因此，本申请方案具备零假阳性（zero false positive）和假阴性（false negative）的特性，零假阳性意味着通过本申请的索引找到的通路一定是可达的，也即如果索引判断存在可达性，则实际图数据上一定存在可达性；假阴性意味着按照本申请实施后，如果通过可达性索引没有找到两个点之间的路径，不表示实际中没有通路；尽管本申请存在假阴性，但是本申请仍然希望降低假阴性，从而提出了对假阴性的改进方法，即，可以采用多种随机游走方式，逐步找出图中经常被访问到的那些重要节点，以及，通过过重采样等方式，逐步优化索引结构，降低假阴率。在其中一些实施例中，针对事实上存在可达性，但索引未能引入的情况，可以通过重采样的方式，降低可达性索引的假阴率。在分区内部分节点的集合（C、D）的容量有限的情况下，可以采用如下办法：删除C、D中较短的链表，换入更长的链表；将最近未被使用的链表上的点换出，将最近常被访问的点换入，或者，将假阴的点换入，或者，通过在同分区（或者跨分区）内进行多组随机游走，将序列中出现频率最高的点或出入度较高的点换入。

[0143] 结合上述实施例中的分布式图数据库中可达性索引的分层构建方法，本申请实施例可提供一种存储介质来实现。该存储介质上存储有计算机程序；该计算机程序被处理器执行时实现上述实施例中的任意一种分布式图数据库中可达性索引的分层构建方法。

[0144] 在一个实施例中，提供了一种计算机设备，该计算机设备可以是终端。该计算机设备包括通过系统总线连接的处理器、存储器、网络接口、显示屏和输入装置。其中，该计算机设备的处理器用于提供计算和控制能力。该计算机设备的存储器包括非易失性存储介质、内存储器。该非易失性存储介质存储有操作系统和计算机程序。该内存储器为非易失性存储介质中的操作系统和计算机程序的运行提供环境。该计算机设备的网络接口用于与外部的终端通过网络连接通信。该计算机程序被处理器执行时以实现一种分布式图数据库中可达性索引的分层构建方法。该计算机设备的显示屏可以是液晶显示屏或者电子墨水显示屏，该计算机设备的输入装置可以是显示屏上覆盖的触摸层，也可以是计算机设备外壳上设置的按键、轨迹球或触控板，还可以是外接的键盘、触控板或鼠标等。

[0145] 在一个实施例中，图6是根据本申请实施例的电子设备的内部结构示意图，如图6所示，提供了一种电子设备，该电子设备可以是服务器，其内部结构图可以如图6所示。该电子设备包括通过内部总线连接的处理器、网络接口、内存储器和非易失性存储器，其中，该非易失性存储器存储有操作系统、计算机程序和数据库。处理器用于提供计算和控制能力，网络接口用于与外部的终端通过网络连接通信，内存储器用于为操作系统和计算机程序的运行提供环境，计算机程序被处理器执行时以实现一种分布式图数据库中可达性索引的分层构建方法，数据库用于存储数据。

[0146] 本领域技术人员可以理解，图6中示出的结构，仅仅是与本申请方案相关的部分结构的框图，并不构成对本申请方案所应用于其上的电子设备的限定，具体的电子设备可以包括比图中所示更多或更少的部件，或者组合某些部件，或者具有不同的部件布置。

[0147] 本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，该计算机程序可存储于一非易失性计算机可读取存储介质中，该计算机程序在执行时，可包括如上述各方法的实施例的流程。其中，本申请所提供的各实施例中所使用的对存储器、存储、数据库或其它介质的任何引用，均可包括非易失性和/或易失性存储器。非易失性存储器可包括只读存储器（ROM）、可编程ROM（PROM）、电可编程ROM（EPROM）、电可擦除可编程ROM（EEPROM）或闪存。易失性存储器可包括随机存取存储器（RAM）或者外部高速缓冲存储器。作为说明而非局限，RAM以多种形式可得，诸如静态RAM（SRAM）、动态RAM（DRAM）、同步DRAM（SDRAM）、双数据率SDRAM（DDRSDRAM）、增强型SDRAM（ESDRAM）、同步链路（Synchlink） DRAM（SLDRAM）、存储器总线（Rambus）直接RAM（RDRAM）、直接存储器总线动态RAM（DRDRAM）、以及存储器总线动态RAM（RDRAM）等。

[0148] 本领域的技术人员应该明白，为使描述简洁，未对上述实施例中的各个技术特征所有可能的组合都进行描述，然而，只要这些技术特征的组合不存在矛盾，都应当认为是本说明书记载的范围。

[0149] 以上所述实施例仅表达了本申请的几种实施方式，其描述较为具体和详细，但并不能因此而理解为对发明专利范围的限制。应当指出的是，对于本领域的普通技术人员来说，在不脱离本申请构思的前提下，还可以做出若干变形和改进，这些都属于本申请的保护范围。因此，本申请专利的保护范围应以所附权利要求为准。