书接上文 图数据库 | 12、图数据库架构设计——高性能计算架构​​​​​​。昨天老夫就图数据库架构设计中的 实时图计算系统架构、图数据库模式与数据模型、核心引擎如何处理不同的数据类型、图计算引擎中的数据结构 这四块内容进行了展开讲解，今儿继续往下、往深聊，就如何对大图分区（分片）、高可用性及可扩展性、故障与恢复进行具体展开。

---

对一张大图进行分区（分片）可能是一项艰巨的工作。

传统意义上，图分片问题是个NP困难（NP-Hard）问题，求解的复杂度至少与NP完全（NP-Complete）问题一样困难，非常具有挑战性。

即使对一个图进行了分区，由于分区后形成的各个子图之间的复杂依赖关系，可能会导致整个集群系统面临性能指数级降低的结果。

5、如何对大图分区（分片）

图分区（也称为切图）是图论研究中一个有趣的课题，一般有两种切图的方式，即切边（edge-cut）和切点（vertex-cut）​，如图1所示：

仔细观察上图，我们会发现切边后所形成的2张新的子图中，不但点（A、C、E）被重复放置，边（AC、AE）也被重复；而切点后，只有一个顶点（A）被复制。

另外，切边的逻辑整体而言没有切点清晰，因此大多数学术界的图计算框架都采用切点的模式。例如下图3中的基于ApacheSpark系统的GraphX图计算框架就采用的是典型的切点方式。图中A、D两个顶点被切分后，GraphX用了3套分布式数据结构来表达完整的原图：顶点表、路由表和边表。

切点（或点切）模式的逻辑和具体数据结构设计还有其他的方案和变种，例如源自卡内基梅隆大学（CMU）的PowerGraph图计算框架针对其他图计算框架中存在的超级节点处理效率低、切点子图效率差等问题进行了优化，并获得了在一些图算法计算效率上的大幅提升（例如最常见的PageRank算法）​。

图计算框架由于历史原因，绝大多数面对的数据集都属于合成数据集（例如在超级计算中常见的Graph500数据集）​，而真实世界（naturalgraph）的数据集一般都源自互联网、社交网络或公路网络，例如常见的Twitter、Livejuornal等数据集。这些数据集大体上有几个共有特征：单边图、无属性（点、边无属性）和存在超级节点（hotspot/supernode）​。

也许是因为这些共性导致图计算框架上的图分析与算法研究普遍集中在如下几类算法中：PageRank（网页排序）​、三角形计算（按顶点统计）​、最短路径或其变种、联通分量（弱联通分量）​、图上色问题。

这些算法的一个普遍特点是查询深度较浅，除了最短路径算法以外，其他算法可以简单地理解为查询深度只有1～2层，这意味着分图带来的集群节点间通信增加问题可以被忍受。但是，随着工业界（例如金融行业）对于图技术的关注，图计算框架的局限性开始暴露，特别是这些共性需求需要架构层面的支持。

·多边图：顶点间存在多条边，例如多笔转账交易、刷卡交易、通话记录。

·多属性：顶点及边上都可能存在多个属性字段。

·动态性：图上的数据，即顶点和边及其属性都可能会动态地增加、删除甚至改变。

·实时性：在某些场景中需要实时进行计算分析并返回结果。

·查询深度：深度在3层以上的查询。

·时序特征：多数工业界的图数据都会带有时序属性。

结合以上全面的图数据普遍特征，至少有以下4种方法来切分一个图。

1）暴力分区（brute-force partitioning）​：暴力分区与随机划分非常类似，它基本上忽略了图内在的拓扑结构（从人类的视角来理解，一张大图可能包含形成社区的子图，使得某些子图非常密集，而其他区域非常松散，因此给了划分图的机会）​，只需在任意的（例如均分的）顶点或边之间进行剪切即可。目前大多数的图计算框架的分区逻辑都采用点切的方式，少部分采用边切的方式。

2）基于时间序列的分区（time-series-based partitioning）​：这迎合了数据模型包含时间序列数据的场景，例如，有10亿个账户，每周记录100亿个事务，如果在过去12个月内查找账户组之间的连接，那么创建一个包含52个子图的集群是非常有意义的。

集群中的每个计算节点捕获1周的事务数据。每个查询都可以发送到所有52个子图进行执行，最后合并（聚合）到某个指定的（额外的）计算与管理节点进行最终结果聚合。这样分区的逻辑非常清晰，也符合大数据分而治之的理念，可以解决相当一部分场景的需求。

3）用户指定分区（user-specified partioning）​：类似于时序分区的逻辑，由用户来定义如何对图数据集进行切分，这种切图模式可以看作是时序切图的超集。

4）智能分区（smart partitioning）​：智能切图在理论上依然属于NP困难（≥NP完全）问题。但是，实际上因为真实世界的图的连通性都属于稀疏图，即远远没有达到完全联通的稠密程度，因此在逻辑上是可以找到一张大图中联通最稀疏的顶点的最小集合，并且做出尽可能让子图规模均衡的切分。当然这种切分可能存在的一个问题是，如果图数据在切分后继续动态改变，可能会造成已切分的子图间产生负载不平衡等问题。因此如何解决动态平衡的切图问题是产学研界都在关注的问题。

下图示意了在数据结构层面一种可能的切图方式，但是仔细观察，这种方式似乎并非典型的切点或切边的方式，因为这套数据结构自身很难完成跨子图操作（因为在某个顶点的边当中可能会指向的终止顶点属于另一张子图，但是该数据结构自身并没有另一子图的记录）​。因此，类似于图2的逻辑，我们需要一张路由表或一张映射表来查询任意顶点的子图归属关系，以便完成跨子图查询。很显然，图切得越多，可能会造成越重的跨子图通信负担。

有研究表明，一张大图被切分为10张子图后，有90%的节点会落在多张子图内，如果切成100张子图，则99%节点都会被切割。在这种切割后的子图上运行复杂的路径查询、K邻查询、随机游走或社区识别等算法会是一个巨大的挑战，切图后的性能（时效性）可能会产生数以万倍的落差。

6.高可用性及可扩展性

任何企业级商用系统都必须具备高可用性、可扩展性以及快速的故障恢复能力。

（1）高可用性

和主流的数据库、数据仓库或大数据系统类似，图系统提供和实现高可用性的方法有多种，具体如下。

1）双机集群系统（HA）​：标准的HA设置非常简单，主服务器和辅助（备份）服务器各自有100%的图系统，它们保
持同步，任何增删改操作都通过双机集群系统的内部同步体制进行，一旦主服务器关闭或掉线，备份服务器则立刻被激活（通常存在毫秒级延迟）​。这种双机集群系统也叫热备系统。

2）主从服务器（MSS）​：一个主服务器和多个从服务器组成一个由多台（≥3）服务器组成的集群，它们都有读的权限，但只有主服务器可以进行增删改操作。它与经典的MySQL数据库的主-从双机集群系统的设置非常类似。主从服务器的设置模式之一是分布式共识（RAFT）集群，通常由3个实例构成，基于分布式共识算法实现，为了简化集群数据同步，通常写操作由一台服务器负责，所有服务器都可以参与集群负载均衡，只要集群内超过50%的节点在线，整个集群就可以正常工作，当某个实例下线后，集群可以进行重新选举出主节点来作为写入节点。在某些基于原生RAFT协议实现的图数据库集群中，备份节点（或从属节点）并不参与集群负载，它们只在主节点掉线的情况下才通过选举机制推举某个节点上线成为主节点，例如Neo4j的因果集群（causality cluster）就是这种典型的基于分布式共识的热备份模式，它的缺点在于浪费了2/3节点的计算资源，它们没有参与负载。

3）分布式高可用DHA-HTAP集群：分布式高可用集群的最小规模通常是3个节点，这个时候每个节点的角色（所承载的查询与计算操作类型的差异）如果按照TP与AP来区分，参与实时TP类型操作的和参与AP类型操作的可以根据需要进行预先设定或动态分配。通常因为AP类型的操作（如全图遍历类的算法操作）对于计算资源消耗大，因此不适合与TP操作混搭在同一个节点之上。也正是出于这种操作分离的考量，混合事务与分析处理架构（HTAP）应运而生。在较大规模分布式集群中（大于6实例）​，通常会存在管理节点、计算节点、存储节点等不同类型的实例，并通过尽可能避免实例间的频繁通信的方式来保障分布式对于整体系统吞吐率的负面影响。

4）容灾式分布式高可用（DR-DHA）​：需要支持同城、异地多数据中心的灾备。与上面的DHA-HTAP模式类似，但显然集群的规模更大（倍增）​，跨数据中心的通信因时延更大而让数据同步显得更为复杂。对于大型企业用户，特别是金融用户而言，这个相对复杂的方案虽然是必要的，但基本是以主集群作为唯一运营的实体，只有在主集群被迫下线后才会启动灾备集群。
 

（2）可扩展性

随着商用PC服务器架构、云计算，以及互联网场景的兴起，横向扩展（水平缩放）比纵向扩展（垂直缩放）更受欢迎。

许多开发者认为水平缩放是放之四海皆可行的，但忽略了大多数图数据集并不大，不足以需要真正意义的水平缩放的事实；另一方面，现代商用服务器的架构即便是一台服务器也是具备高并发处理能力的，充分利用每一台服务器每一个CPU的并发计算能力，依然非常有意义——一台40线程算力的单机的计算能力大于5台8线程多机，特别是在图数据库查询的场景下。

图数据库的可扩展性，同样有以下两种途径：

1）垂直扩展。充分考虑到目前计算机的处理能力，一台4块CPU、每个CPU 20核（40线程）的主板性能比4节点集群（每个节点有1个CPU，8核，16线程）强大得多——不仅因为前者有更高的核数而具备了更密集的计算资源，还因为一台机器内部的通信效率远高于多机通过网络通信的效率。只要有意识地简单升级你的硬件，就能获得更好的系统性能，特别是在图系统中。

通常内存越大，性能就越高，也能大大提高系统的性能和容量。例如，你有一台CPU功能强大的服务器，但是只有64GB内存，那么你无法存储100亿条边的数据，可把内存升级至512GB——事实上，CPU的线程数与内存GB数量保持在8～16倍的配比是比较合适的，例如16线程对应128G～256GB内存，32线程对应256G～512GB内存，依此类推。

2）水平扩展。水平扩展存在一个分层的概念，最简单的水平扩展是通过增加硬件资源来获得更高的系统吞吐率，如上面介绍过的主从或基于分布式共识算法的架构，当提供3个实例的硬件资源后，系统的吞吐率可以在一定程度上获得线性的增加，例如系统负载能力（侧重于非写入类型负载）​。

图数据库系统最复杂的地方在于它强调整体性（不可分割性）​，如果逻辑上是一张图，并且分布在一个可水平扩展的物理架构之上，那么读、写无法兼顾——随着越来越多的机器参与到水平扩展架构中，系统的吞吐率反而会下降，因为越扩展，图的查询性能会随着节点间通信越频繁而越低。

有鉴于此，通常在工业界的水平分布式图架构设计实现都采用多图模式，即逻辑上，一个大的（分层）集群内会存储多张图，每张图都可以独立完成一个业务场景的查询与计算需求，每一张图都尽可能存储于一个小集群内，集群之间的通信仅限于多图联动的场景，多集群通过域名服务器同步和管理。
 

7.故障与恢复

在图计算中，有两种类型的故障。

1）实例故障：属于严重的故障类型，它意味着运行实例（最糟糕的情况是，整个双机或集群系统）离线，通常情况下实例会自动重启。如果有热备用实例，它将起到自动接管主实例的作用。但如果没有，这个问题需要一张IT热票，并尽快解决。

2）事务失败：导致事务失败的原因有很多，因为事务失败是ACID类型的，如果它失败了，必须发生某种回滚以确保系统范围内的状态是同步的，否则问题最终会变得更大。通常失败会记录日志供开发人员查看，如果比较复杂，则应发出IT支持通知单，否则只能重新运行事务。如果问题不再存在，则可能是错误警报或其他非表层原因。

上面所有的讨论大体假设所有图服务器连接到同一个高速骨干网，以实现非常小的网络延迟（用于状态和数据同步）​。现在要解决的一个大问题是：如何支持跨数据中心灾难恢复？以双数据中心灾备为例，至少有两种方案：

第一种方案采用的是准实时地把主集群的数据同步到异地从集群。当主集群发生故障时，业务可以切换至从集群。这种方案两个集群间采用日志来异步复制（log replication）​，在极端情况下可能会出现数据不一致性（数据短暂的丢失）的情况，如下图5所示：

 
第二种方案采用的是单集群跨双中心，每个中心有3个副本，任一中心发生灾难，业务连续性虽然可能会被短暂影响，但是因为有多副本数据强一致性的协议级限定，数据不会丢失，并且可以通过（维护人员来手动操作）降低副本数量来快速恢复业务——例如在第二个中心中以3个副本拉起业务，如下图所示。

 

 在构建业务连续性计划和灾难恢复计划（BD/DR）时，需要考虑的问题（和假设）如下：

·设计业务连续性和灾难恢复计划（BD/DR规划）​；

·建立必须恢复系统和进程的时间框架；

·评估IT基础设施、数据中心（或云）合同并了解其局限性；

·评估图数据库在整个面向业务的IT支撑体系中的优先级；

·实施业务连续性和灾难恢复计划；

·通过演习和模拟演习测试真实情况；

·迭代优化以上计划和实施方案。

图计算与分析适用的场景非常广泛。Gartner公司在2021年5月的一份市场预测报告中分析，到2025年，80%的商务智能领域的创新都会涉及图分析。随着越来越多行业的应用开始探索基于图数据库的解决方案，我们有理由相信图数据库的架构层面会有越来越多创新性、颠覆性的设计方案出炉。笔者在此梳理了以下几种可能的“颠覆性”架构设计（排名不分先后）​。

·持久化内存架构：大规模使用大内存架构，硬盘不参与计算。

·分布式内存网格架构：在水平分布式架构中采用内存计算与存储网格，对海量内存虚拟化（容器化）​，通过低延迟网络进行多节点互联与数据交换。

·高密度并发架构：通过系统架构设计优化，充分发挥底层硬件并发计算能力，用更少的节点实现更高的系统吞吐率、更低的时延（主要是软件层面的性能提升）​。

·融合多种处理器的加速架构：例如采用FPGA、GPU、ASIC、SoC等与CPU配合的计算加速架构。

·智能分图、动态多图负载平衡架构：在软件层面做到对于大图的智能切分并面对动态变化的数据集保持多图多集群的动态平衡及高效性。

· END ·

（文/Ricky - HPC高性能计算与存储专家、大数据专家、数据库专家及学者）