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

上文我们聊了在设计高性能、高可用图数据库的时候，从单实例、单节点出发，一般有3种架构演进选项：主备高可用，今天我们具体讲讲分布式共识，以及大规模水平分布式。

主备高可用、分布式共识、大规模水平分布式，我们都知道这3套系统的实现复杂度是从低到高渐进的，但这并不意味着复杂度更高的系统在不同的应用场景、用户需求、查询模式、查询复杂度、数据特征条件下就能获得更好的效果。

分布式共识系统

前面提到即便在最简单的主备系统架构中也可能发生系统内无法保证一致性的情况，这是因为任何分布式系统在本质上都是异步分布式。所有操作（网络传输、数据处理、发送回执、信息同步、程序启动或重启等）都需要时间来完成，任何交易、任何事务处理在一个实例内都是异步的，而在多个实例之间这种异步性会被放大很多。分布式系统设计最重要的一个原则就是与异步性共存，不追求完美的一致性，但可以假设整个系统在大部分时间内是正常工作的，即便部分进程或网络出现问题，整个系统依然可以对外提供服务。

分布式共识系统，特别是分布式共识算法就由此应运而生，被用来保证即便在分布式系统中出现了各种各样的问题，但是整体服务依然可以保持在线。

分布式共识算法有3个核心特性：合法有效（validated proposal）​、达成一致（reaching agreement或unanimity）​、快速终止（processcan be terminated）​。

合法有效指的是进程间的指令信息传播需要基于合理有效的数据，且能让有效的进程集合达成一致，并且最终形成共识，进而终止同步过程的时耗需要在合理的、较短的时间内完成。在高性能分布式系统中可毫秒级完成同步，而在较大规模跨地域的分布式共识系统中，可能会出现秒级甚至需要人工介入的分钟级形成共识，具体的终止时间延迟取决于具体的业务需求。

达成一致等同于形成共识，类似于多个进程间的民主选举，一旦它们形成了共识，任何参与了选举的进程都不再允许对结果产生异议或按照与结果不符的方式或内容执行任务——这种情况就是我们前面提到过的分布式系统无法解决的“两军通信问题”​“拜占庭将军问题”​。

图1示意了多任务（多进程）间形成共识的过程，这一过程与我们日常生活中的行为并无本质不同。

图1： 多任务间形成共识

A、B、C、D四个人在一起讨论晚上去哪里，一开始A提议去看电影，得到了B的赞同，但是C很快提出去吃晚餐，D赞同C的提议，随后B改口赞同C的提议，最终A也改为同意C的提议。此时，四人达成了晚上去吃晚餐的共识。这就是多任务共识形成的简单例子。在实际的分布式共识算法中还会引入如角色、阶段以及如何终止共识等问题，下面逐一分析。

形成共识的过程需要有明确的终止算法，否则就会出现悬而不决、无限等待的问题。例如当某个实例（进程）下线后，剩余进程如果无限等待其重新上线，或是如图1所示，A、B、C、D四个进程出现层出不穷的新方案，以至于四人永远无法达成共识。共识算法需要考虑这些情况，并规避其发生。本质上，无论采用何种跨进程的集群内通信方式，都要使用尽可能简洁的算法，让共识的达成（进而终止）代价较低。

那么，分布式共识系统应该采用何种通信手段呢？前面提到过网络系统的3种通信方式：中心化（广播式）​、去中心化（分层区域广播或多播式）以及点对点分布式，对小型分布式系统而言，最简单和最直接的方式是广播式，因为发起广播者与信息接收者之间的互动逻辑决定了这个交互过程是属于“尽人事听天命”类型的单向一次性传送模式，还是其他更可靠的交互模式。

理解这个过程需要考虑这样一种可能发生的情况，即如果发起者A在发出请求给B、C后下线，但是并没有向D发送，那么在广播算法中，就需要考虑加上B、C可以向D继续广播的逻辑。从通信的复杂度角度看，这样的实现就是一种“可靠广播”模式，在有N个实例的分布式系统中，其复杂度为，显然，这种漫灌式重度通信模式（floodingcommunication）对于大型分布式系统是不合适的，但是它已经具备了通过冗余通信来实现系统完整性、一致性的特征。

下面分析如何在分布式共识通信的过程中保证消息的有序性，即至少需要实现2个功能：多消息的事务性（原子性、不可分割性）和序列性。

一种比较简单的原子广播算法是分布式KV项目Apache Zookeeper中的ZAB（Zookeeper Atomic Broadcast）​，它把Zookeeper集群内的所有进程分为两个角色：领导者（leader）和跟随者（follower）​，3种状态：跟随（following）​、领导（leading）和选举（election）​；它的通信协议分为4个阶段：启动选举阶段（leader election phase）​、发现阶段（discovery phase）​、同步阶段（synchronization phase）​、广播阶段（broadcasting phase）​。

在启动选举阶段（阶段0）​，某个进程在选举状态中开始执行启动选举算法，并找到集群内的其他进程投票成为领导者。

在发现阶段（阶段1）​，进程检查选票并判断是否要成为两个角色之一，被选举为潜在领导者的进程称作意向领导（prospective leader）​，之后该进程通过与其他跟随进程通信发现最新的被接受的事务执行顺序。

在同步阶段（阶段2）​，发现过程被终止，跟随进程通过意向领导更新的历史记录进行同步。如果跟随进程自身的历史记录不晚于意向领导的历史，则向意向领导进程发送确认信息。当意向领导得到了主体选举人（quorum）的确认后，它会发送确认（commit）信息，这时意向领导成为确认领导（established leader）​。该阶段的算法逻辑如下：

在广播阶段（阶段3）​，如果没有新的宕机类问题发生，集群会一直保持在本阶段。在此阶段，不会出现两个领导进程，当前领导进程会允许新的跟随者加入，并接受事务广播信息的同步。

ZAB的阶段1～3都采用异步的方式，并通过定期的跟随进程与领导进程间的心跳信息来探测是否出现故障。如果领导进程在预定的超时时间内没有收到心跳，它会切换至选举状态，并进入阶段0，同样地，跟随进程也可以在没有收到领导进程心跳后进入阶段0。

在ZAB的具体实现逻辑中，leader选举是最核心的部分，ZAB采用的策略是拥有最新历史记录的进程会被选举为leader，并且假设拥有全部已提交事务（commitedtransactions）的进程同样拥有最新的已提议事务（most recent proposed transaction）​。当然，这个假设的前提是集群内的ID序列化及顺序增长，这一假设让leader选举的逻辑大幅简化，因此称为快速领导选举（Fast Leader Election,FLE）​。即便如此，FLE过程中的判断逻辑，特别是各种边界情况的考量依然很多，下面是节选的参与选举进程的FLE实现代码逻辑： 

 

ZAB最早是作为Yahoo！内部Hadoop项目的一个子项目，后来被拆分独立出来作为一款分布式服务器间进程通信及同步框架，并在2010年后成为Apache开源社区中的一个顶级项目。从上面的伪码中就可以看出，ZAB所采用的算法逻辑和通信步骤较为复杂。类似地，Paxos类算法的实现对于跨地理区域的系统实例间时钟同步有着严苛的要求，且算法逻辑复杂，不容易被理解。头部企业谷歌在其Spanner系统中通过原子钟的帮助实现基于Paxos的大规模分布式共识系统，但是对缺少同等系统架构把控能力的企业而言，Paxos就显得门槛过高了。 

在2013年之后，更简单、可解释的分布式共识算法应运而生，其中最知名的是2014年DiegoOngaro提出的RAFT算法及一种称作LogCabin的代码实现。

 在RAFT算法中，集群内的每个共识算法参与进程有3种角色：候选者（candidate）​、领导者（leader）和跟随者（follower）​。

与Poxos通过时钟同步来保证数据（事务）全局顺序一致不同（但是类似于ZAB）​，RAFT把时间块切分为terms（选举任期，类似于ZAB中的epoch）​，在每个任期期间（系统采用唯一的ID来标识每个任期，以保证不会出现任期冲突）​，领导者具有唯一性和稳定性。

RAFT算法有3个主要组件（或阶段）​：选举阶段、定期心跳阶段和广播及日志复制阶段。

图2示意了在一个3节点的RAFT集群中客户端与服务器集群的互动，整个流程围绕领导者角色进程展开，可分解为10步，而这只覆盖了RAFT算法的广播及日志复制阶段。 

图2：RAFT集群C/S工作流程步骤分解

如图3所示，3种角色及所负责的任务内容如下：

· 跟随者，不会主动发起任何通信，只被动接收RPC调用（Remote Procedure Calls）​。

· 候选者，会发起新的选举，对选举任期进行增量控制，发出选票，或重启以上任务。

在该过程中，只有含有全部已提交命令的候选者会成为领导者，并通过RPC调用的方式通知其他候选者选举结果，并避免出现split vote（平票）的问题（在RAFT算法中，通过随机选举超时，例如在0.15～0.3s间随机制造超时来避免因两个实例的候选进程同时发出导致选票计数出现平票）​。

另外，每个进程都维护了自己的一套日志，在原生的RAFT算法实现中称为logcabin（木筏）​。

· 领导者，会定期向所有跟随者发送心跳RPC，以防止因过长的空闲时间而过期（和重新选举）​。领导者通常是最先面向客户端进程请求的，对日志进程进行添加处理以及发起日志复制，提交并更改自身的状态机，并向所有跟随者同步log。

图3：RAFT共识算法集群进程间的角色转换关系

RAFT描述的是一种通用的算法逻辑，它的具体实现有很多种，并且有很大调整空间。例如，原始的RAFT算法与一主多备的架构类似，任何时候只有一个实例在服务客户端请求。如果我们结合图数据库的可能查询请求场景，完全可以分阶段地改造为如下几种（难度从低到高）​。

· 多实例同时接收读请求负载：写入依然通过leader节点实现，读负载在全部在线节点间均衡。

· 多实例同时接收先读再写类请求负载：典型的如回写类的图算法，全部节点都可以承载图算法，回写部分先进行本地回写，再异步同步给其他节点。

 · 多实例同时接收更新请求负载并转发：写入请求可以发送给任意集群内节点，但是跟随者会转发给leader节点处理。

· 多实例同时处理更新请求：这是最复杂的一种情况，取决于具体的隔离层级需求，如果多个请求同时在多个实例上更改同一段数据，并且有不同的赋值，会造成数据的不一致性。在这种情况下实现一致性的最可靠途径就是对关键区域采用序列化访问。这也是本章反复提到的，任何分布式系统在最底层、最细节、最关键的部分一定要考虑到有需要串行处理的情况。

目前已知的RAFT算法可能远超100种，如ETCD、HazelCast、Hashicorp、TiKV、CockrochDB、Neo4j、Ultipa Graph、嬴图等，并且以各种编程语言实现，如C、C++、Java、Rust、Python、Erlang、Golang、C#、Scala、Ruby等，足以体现分布式共识算法及系统的生命力。

在基于共识算法的高可用分布式系统架构中，我们做了一个比较重要的假设，即大多数时候，系统的每个实例上都存有全量的数据。注意，我们限定的是“大多数时候”​，言下之意是在某个时间点或切片下，多个实例间可能存在数据或状态的不一致性，也因此需要在分布式系统内通过共识算法来实现数据同步，以形成最终的数据一致性。

下篇继续聊大规模水平分布式。最近很忙，不过老夫会尽快更文。

· END ·

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