图数据库 | 19、高可用分布式设计（下）

相信大家对分布式系统设计与实现的复杂性已经有了一定的了解，本篇文章对分布式图数据库系统中最复杂的一类系统架构设计进行探索，即水平分布式图数据库系统（这个挑战也可以泛化为水平分布式图数据仓库、图湖泊、图中台或任何其他依赖图存储、图计算及图查询组件而形成的系统）。

水平分布式系统

在开始探索之前，我们应该先明确一点，水平可扩展的图数据库系统构建的目的不是让更低配置的机器以集群的方式来承载原来单机才能完成的任务，也不是随着机器配置的降低以更大的集群规模来完成同样的任务。与此相反，在同样的机器配置下，多机构成的集群可以实现更大规模的数据吞吐，最好是实现系统吞吐率随硬件资源增长呈线性分布。

上面描述的两种路线，举例来说明。

· 路线1：原来1台机器8核CPU、128GB内存、1TB硬盘，现在要实现利用8台低配的机器，每台1核CPU、16GB内存、0.125TB硬盘来完成同样的任务，甚至效果更好。

· 路线2：原来1台机器8核CPU、128GB内存、1TB硬盘，现在以同样配置的8台实例来实现之前1台实例的数倍量级（理论上小于等于8）的挑战。

在路线1中，如果只是向客户端提供非常简单的微服务，那么1台拆分为8台是可行的，并且因为8台机器的8块硬盘提供潜在的更高的IOPS，简单数据字段的读写效率会提升，但是，1核CPU的算力可能会小于8核CPU的1/8,1核计算资源的限定会让任何操作只能以串行的方式进行，任何扩展都要与集群内其他实例进行网络通信，也会因此大幅降低任务执行效率。这意味着降配（低配）操作只适合短链条、单线程、简单类型的数据库查询操作，换言之，存储密集型或I/O优先类型的操作可以用“低配分布式”解决。这也是为什么过去在以关系型数据库为主流的数据库发展历程中，存储引擎是“一等公民”，而计算是依附存储引擎而存在的，是“二等公民”。

在对路线1的分析中，有个重要的概念：短链条任务，在互联网和金融行业中也称作短链条交易，如秒杀类操作、简单的库存查询等。它涉及的操作逻辑通常比较直白，即使在很大的数据集上，也只需要通过定位和访问极少量的数据即可返回，因此完全可以做到低延时和大规模并发。

对应于短链条任务，长链条任务则要复杂得多，它的数据访问和处理逻辑更复杂，即便在少量数据集上，也可能会牵涉相对大量的数据。如果采用传统的架构（如关系型数据库），长链条任务的操作时间会大大长于短链条，每个操作本身对于计算和存储资源的占用程度也更高，不利于形成规模化并发。图1形象地展示了这两种操作的差异性。在路线1中，短链条的任务可能被满足，但是长链条的任务则因每个实例的算力缺失而无法有效完成。典型的长链任务有在线风控、实时决策、指标计算等，对应图数据库上的操作有路径查询、模板查询、K邻查询，或者是多个子查询形成的一个完整查询任务等。

有鉴于此，在路线2中，在从1台实例扩增到8台实例时，我们不降低实例的配置，目标是让集群可以以水平分布式的方式应对如下3大挑战。

·挑战1：承载更大量的数据集。

·挑战2：提供更高的数据吞吐率（并发请求处理能力）。

·挑战3：提供兼顾长链条与短链条任务的处理能力（算力提升）。

如图2所示，在一个由多实例构成的集群内，每个实例都是典型的X86系统架构，在该架构中突出了围绕CPU的北桥（northbridge）算力部分，淡化了南桥（southbridge）相连的存储等I/O设备。事实上，每个实例都是一个可规模化并发的微系统，如CPU的多核（多线程）、CPU指令缓存、CPU数据缓存、多核间共享的多级缓存、系统总线、内存控制器、I/O控制器、外存、网卡等。以路线1的1台8核CPU与8台1核CPU为例，在充分并发的前提下，后者的计算性能低于前者，前者的存储IOPS（I/O Operations per Second）则低于后者。而路线2的1台8核到8台8核则可能实现算力与存储能力倍增。水平分布式系统的挑战1、2主要通过南桥相连的设备解决（存储、网络）；挑战2、3主要通过北桥相连的设备解决（CPU、内存）。

在路线2中，算力终于成为了“一等公民”，这一点对图数据库而言至关重要。在图数据库的架构设计中，算力引擎第一次和存储引擎平起平坐，这在其他NoSQL或SQL类型数据库中是非常罕见的。只有这样，图数据库才能解决其他数据库所不能解决的复杂查询实时化、深度遍历与下钻、复杂归因分析等棘手的问题。

在我们开始设计一款水平分布式（图）数据库系统架构前，需要厘清一组重要的概念，即分区（partitioning）与分片（sharding）。一般把分片定义为一种水平分区模式，而分区则默认等同于狭义的垂直分区（或垂直分片）模式。在很多场景下，分区与分片被等同对待，但是通过水平或垂直前缀来修饰具体的切割模式。图5-20示意了一张原始数据库表如何被垂直分区及水平分区。

从图3中可以清晰地看出，在垂直分区（传统分区模式）中，不同的列被重新划分到不同的分区中；在水平分区中，不同的行则切分到不同的分片中。两者的另一个主要区别在于主键是否被重复使用，在垂直分区中主键在两个不同的分区中被100%复用，而在水平分片中则不存在复用。但是，水平分片也意味着需要一个额外的表（或其他数据结构）来对哪个分片中有哪些主键进行跟踪，否则无法高效地完成分表查询。因此，分区还是分片取决于设计者本身的喜好、具体业务查询场景中哪种方式能取得更好的效果、性价比等因素。

· 顶点数据集如何切分；

· 边数据集如何切分；

· 属性字段如何切分；

· 完成以上切分后，如何实现具体的查询及效率。

之前老夫就介绍过在图数据集中如何进行切点或切边（见下图4、图5、图6）来实现水平分布式的图计算框架。下面我们来推演一种可能的点切与边切融合的水平分布式系统的构建方式。

下图展示了一种可能的多实例分布式系统的构建方式，其中每个实例内都有各自的顶点集、边集以及其他图集相关信息，另外最重要的一个组建就是分布式ID服务（如图5-21右上箭头出处所示），任何涉及定位任意点、边在哪个（可能存在多个）实例上可以访问都需要调用这个ID服务，ID服务器只负责以下几项工作：

·插入点或边时，生成相应的ID及对应的实例ID；

·查询或更新时，提供相应的ID；

·删除时，提供相应的ID，并回收点或边的ID。

工作看似很简单，但是我们仅以插入点、边为例来分析一下可能的情况。

1）插入新的顶点。

·在唯一实例上；

·在HA主备实例对上；

·在多个实例上。

2）为顶点插入一条出边（outbound-edge）。

·在唯一实例上；

·在HA主备实例对上；·在多个实例上。

3）为顶点插入一条入边（inbound-edge）。

·在唯一实例上；

·在主备实例上；

·在多个实例上。

4）为顶点添加一个新的属性。

·在唯一实例上；

·在主备实例上；

·在多个实例上。

5）为边添加一个新的属性。

·在唯一实例上；

·在主备实例上；

·在多个实例上。

仅仅是围绕点或边的插入操作就分拆出来如上15种可能的组合情况，其他操作如更新、删除等，要考虑的情况更为复杂。在图数据库中，边是依附顶点而存在的，意味着要先有两端的顶点，才会有边，且边存在方向。关于边的方向这一点非常重要，在图论中有无向边的概念，但是在计算机代码实现中，因为涉及图遍历的问题，从某个起始顶点到终止顶点途经一条边，边是有方向的。类似地，在存储一条边的时候，需要考虑如何存储另一条反向边，否则就无法实现从起点反向遍历到终点。图5-22示意了反向边存在的必要，当我们增加一条从点B指向点C的单向边后，系统需要默认同步增加一条反向边，否则从点D无法反向触达点B或其左侧的任何相连顶点，反之亦然。

同样，删除边的时候无须删除顶点，但是删除顶点需要先从删除边开始，否则系统会立刻出现很多孤边，进而造成内存泄漏等严重问题。事实上，图数据库中批量删除顶点和边是个比较复杂的操作，特别是在分布式数据库中，操作的复杂度与点及边的数量成正比（删边还需要考虑反向边删除的问题）。删除边的一种可能步骤如下：

1）根据边的ID定位被删除边所在的实例ID（可能存在因一条边的起点、终点在不同实例上的情况，会返回两个甚至多个实例的ID）；

2）（并发的）在上一步返回的每个实例上搜索定位该边ID在数据结构中的具体位置；

3）（并发的）如果采用当前边所属顶点的全部边连续存储的数据结构，把当前位置所在边与尾部边置换，并删除置换后的尾部边；

4）如果每个实例存在多个副本，同步至副本；

5）以上所有操作全部成功后，确认并提交该条边被删除成功，整个集群内的状态同步；

6）（可选的）回收该条边ID。

考虑到具体的架构设计、数据结构和算法复杂度，删除边操作的时间复杂度可能有很大的差异。一种可能的实现方式的复杂度为O(3 log N)，其中N为全部点的数量，3表示类似的定位查询与实例间同步操作重复的次数。显然，如果是一个有100万条边的超级节点的删除，一整套操作非常复杂，需要先在一个实例上删除100万条边，然后再删除全部反向的100万条边，如果这些边分布在不同的实例上，会触发100万次的边对应实例查询……我们当然可以把所有边的ID整体一次性（或打包分多次查询）提交给服务器来减少网络请求次数，但是这个操作的复杂度与传统数据库中需要大批量删除某些大表中一些行的复杂程度类似。

下面举一个具体例子展示如何对图数据集进行切分，并且如何把数据存储在不同的水平分布的实例上。以图9为例，在系统设计中需要考虑如何处理以下的情形：

·支持多边图，即允许任意两个顶点间可以有多条边。

·支持自环，即可以出现从某个顶点出发回到自身的边。

·允许点、边携带有各自的属性。

·允许从任一顶点出发沿出边或入边访问相邻的顶点（换言之，支持反向边、有向图）。·允许对图数据集中的顶点进行水平切割（sharding）。

·（可选的）所有顶点的邻居在同一实例存储。

·（可选的）任一顶点关联的全部边在同一实例存储（无论该实例是否有多个备份）。

·（可选的）对图数据集中的边进行切割，被切割的边会在两个不同的实例中重复存在。

下表列出了上图中全部顶点及属性的一种可能存储结构，以及将该图一分为三后每个实例上顶点的存储情况。

表2列出了一种可能的边近邻存储数据结构，注意我们是按照顶点顺序排列的，且每个顶点的所有相邻的边按照正向与反向聚合存储。

边的切分逻辑同表1中的顶点切分逻辑，如表5-3所示。

下面验证这种简单的切图方式是否对图查询有显著的性能影响，有如下几种情况：

·查点（包括读、更新、删除，下逻辑同）。

·查边。

·查某点的全部1度邻居。

·查某点的K度邻居（K≥2）。

·查任意两点间的最短路径（假设边上权重相同、忽略方向）。

·两点在同一实例上；

·两点在不同实例上。

·其他可能的查询方式。

·图算法；

·模板查询、其他方式的路径查询等。

查点又可以细分为很多种情况：

·按照ID查。

·按照系统全局序列化唯一ID查询（又称UUID）；

·按照原始ID（输入时提供）查询。

·按照某个属性查。

·按照某个属性字段中的文字的模糊匹配（全文搜索）。

·其他可能的查询方式，例如查询某个范围的全部ID等。

在最简单的情况下，客户端先向ID Server发送查询指令，通过顶点的原始ID，查询其对应的UUID以及对应的实例ID，这个查询的复杂度可以做到不大于O(log N)。

最复杂的是全文搜索，在这种情况下，客户端请求可能会被ID Server转发给全文搜索引擎，取决于引擎的具体分布式设计逻辑，该引擎可能有两种方案：

·继续向全部实例分发，并在实例上完成具体的搜索所对应的顶点ID列表；

·引擎返回含有对应顶点的ID所对应的全部实例ID以及顶点ID列表。

查边与查点类似，但是逻辑略为复杂，前面提到过由于每一条边涉及正向存储与反向存储，因此复杂度至少是顶点的2倍。另外，边隶属于顶点，可能会出现需要遍历某个顶点的部分甚至全部边才能定位某一条边的情况。当然，我们可以对所有可能出现遍历的情况进行优化，例如用空间换时间，但是依然要考虑实施的代价与性价比问题。

水平分布式系统最大的考验是如何处理关联数据查询（数据穿透），例如从某个点出发查找它的全部邻居。以图58和表5-3中的顶点1为例，要查询其全部1-Hop邻居，完整的步骤如下：

1）（可选的）根据原始ID查询其UUID；

2）根据UUID查询其所在实例的ID；

3）在该实例上定位到边数据结构中该UUID所在位置；

4）计算该阶段的全部边的数量、关联的顶点ID；

5）对关联ID进行去重运算，并返回结果集。

上操作中，最核心的逻辑是步骤4）与步骤5）。在步骤4）中，所有顶点1的出边和入边如果以连续存储的方式存在，则可以极低的复杂度O(1)计算出其出入度之和（数值为7）；在步骤5）中，由于可能出现顶点1与其他顶点多次相连的情形，因此它的1-Hop的结果不是7，而是需要对与顶点1、2关联的3条边进行去重，得到的结果为4。示意如表4所示。

在上述的数据结构设计中，我们可以在任一顶点所在的实例中计算其全部的1-Hop邻居（隐含的也包括其全部的出度边、入度边），而无须任何与其他实例间的网络交互。这样相当于能把浅层（小于2层）的操作性能保持与非水平分布式架构持平，并发查询能力却倍增。

我们再来看一下如何计算顶点1的2-Hop邻居数量并返回结果集。依旧以图9为例，具体步骤如下：

1）获取并定位顶点1所在实例的ID。

2）在该实例上定位顶点1及其边数据结构，获取全部相邻顶点ID，对ID去重（获得2、3、5、6）。

3）对上一步中的顶点集合进行“分而治之”。

·对以上去重的ID查询其所在分片实例的具体服务器ID，并发送给相应的实例服务；

·顶点2、3因处于当前实例，以类似于步骤2）的方式处理；

·分片2所在实例处理顶点5、6，处理方法同上。

4）对结果集进行组装、去重。

5）向客户端返回。表5-7示意了在多个分片上计算顶点1的2-Hop邻居的流程，按照以上步骤可以分解推导如下结果：

1）顶点1处于分片1。

2）1-Hop：在分片1对顶点1操作去重后的邻居顶点为2、3、5、6。

3）2-Hop：以多线程并发的方式在各个实例上操作。

·顶点2的下一度邻居：4、1，其中1需要去重（因为已经在0度访问过）；

·顶点3的下一度邻居：7、6、4、1，其中6、1需要去重（因为在1度和0度都访问过，但是此时如果不与同实例或其他实例的其他线程通信，并不知道顶点4需要去重）；

·顶点5的下一度邻居：1、7、4，其中1需要去重（逻辑同上）；

·顶点6的下一度邻居：1、3，其中1需要去重（逻辑同上）。

4）上一步的结果需要全部汇总，逻辑如下。

·所有分片实例向实例1汇总数据；

·顶点序列如下。

·Hop-0:1；

·Hop-1:2、3、5、6；

·Hop-2:4、1；7、6、4、1；1、7、4；1、3。

·跨步去重后2-Hop结果：4、7。

5）向客户端返回去重后的计算结果：顶点1的2-Hop邻居为2个，包含顶点4、7。

在上面的具体操作步骤中，最复杂、最核心的算法逻辑在于如何对数据进行去重。重复的数据带来了几个显著的弊端：

·非去重的数据会导致结果错误，图计算是精准计算，不是概率问题。

·非去重的数据，特别是中间结果，会导致不必要的计算量增大，耗费算力、加大网络通信压力。

但是，如何对数据去重是个非常有技巧和挑战的问题。如前面所述的推导过程，我们在步骤2）、3）及4）中对计算结果进行了去重，也就是说，在尽可能避免分片实例间通信的前提下，在每一层中都对结果集进行去重操作，并且可以在从上一层向下一层转播的过程中，把之前每一层的去重ID列表向下传播，这个操作可以以一种类似于递归的逻辑实现。

如果我们把这个K邻查询的深度扩展为3-Hop或4-Hop，或者是图的数据量级指数级增加，上面的算法是否还能够保持高效呢？

以图9为例，从顶点1出发，最大深度的Hop就是2-Hop，这时如果进行3-Hop的计算，返回的结果应当为0（空集合）。但是如果不去校验、去重每一层的数据，在不完成2-Hop之前，无法得知该图数据集并不存在相对于顶点1的3-Hop非空结果集。

以上描述的去重算法的具体实现有以下两种：

1）当前层（跳）向下传播过程中，去重数据，并向下传递自上一层传递下来的数据。

·优点：在每一层内都可以尽可能实现部分去重，降低下一层重复运算的压力。

·缺点：可能会传递大量数据，造成网络压力，且当前分片实例仅能完成局部去重。

2）当前层数据去重，但是不向下一层传播，等待到最后一层做最终的汇总、去重。

·优点：逻辑较为简单。

·缺点：可能会出现大量重复的计算（算力浪费、网络带宽浪费），且最后一层汇总的数据量大，不符合分而治之的原理。

用同样的逻辑也可以完成前面描述的其他查询及算法。笔者在这里仅仅列出了一种可能的水平分布式的实现方式，相信聪明的读者可以设计出自己的水平分布式原生图架构。

最后总结一下本章分享的分布式图系统的一些重要理念：

·分布式不是试图用多台低配的设备来取代高配的设备，并寄希望于可以获得更好的效果。毕竟（高性能的）图数据库系统不是用Hadoop的理念与框架可以实现的——如果你还停留在Hadoop时代，那么你的知识栈与认知需要一次很好的升级了。