一、高可用集群架构
（一）高可用架构
首先我们先了解一下PolarDB for PG的高可用架构。
总的来说，PolarDB for PG的高可用架构是把物理复制跟一致性协议相结合，来保证各个节点上的默认值的强一致性。我们看一下原生PG的物理复制方案，也就是流复制方案。
PG原生的流复制支持异步、同步、Quorum Base的机制来同步WAL日志，我们简单分析一下这三种复制方式。首先是同步复制，同步复制的首要目标是保证不丢数据，但其实它会有一些问题，第一个问题是它无法满足可用性的要求，就是当备库出现故障的时候，或者网络链路上有抖动的时候，这个时候可能会影响主库的可用性，或者主库的RT。其次，它本身并不具备故障自动切换的能力，意味着它并不会去探测主库的可用性，更不用说触发自动的故障切换。另外，旧的主库在故障恢复之后，可能无法重新加入到集群里面来。比如当事务在主库上WAL日志已经持久化成功了，但是在备库上还没有收到日志的时候，如果主库出现故障了，这个时候可能需要通过手动或者通过管控系统来把备库promote成新的主库。
过了一段时间之后，如果旧的主库恢复了，正常的逻辑应该是旧的主库以Standby的方式重新从新的主库上同步WAL日志，但这个时候由于旧的主库在挂掉之前，本身自己会有一些多余的WAL日志，所以这个时候是无法直接从主库上直接拉取日志，因为拉取日志的时候，会发现自己本身已有的日志在主库上不存在，在流复制里面它是会失败的，所以说这个时候我需要先执行一下pg_rewind。
另外，对于不丢数据这一点，其实它也不完全是丢数据，比如说到Master上面，其实是在事务提交的时候，它会等待Standby同步日志，从而保证当Master可见的数据在Standby上肯定是已经同步到了。但是当Master写入了本地日志，然后Standby上还没有写入日志的时候，Master重启了，这时候Master重启之后，它会回放自己所有WAL日志，导致没有被同步到Standby的日志也会被回放。回放之后会出现一个现象，就是Master上已经看到的这些数据，但是对应的WAL日志还没有同步到Standby上，所以严格意义上来说，同步复制也并不能保证不丢数据。
其次我们看一下异步复制，异步复制跟同步复制相比，不需要等待StandbyWAL日志持久化成功。它发送过去行了，根本不关心备库到底有没有持久化成功，然后本地的事务就可以提交了。跟同步复制相比，它可用性比较好，或者说性能比较好，但它的问题是可能会丢数据。
最后一个是Quorum复制，Quorum复制看起来是说如果我们使用了一个多数派的方案之后，是否可以保证不丢数据。但其实在一致性协议里，它除了多数派同步的方案之外，它本身还会有一些选主、日志一致性、集群在线变更等方面的逻辑，但是PG本身Quorum复制里面，它并没有涉及到这些逻辑，所以从本质上来说，它其实并不是一个完整的RPO=0的高可用方案。
那么分析完PG的三种复制方式之后，我们再看一下我们PolarDB for PG的一个高可用方案。
首先我们通过把一致性协议引入到物理复制里，使用的一致性协议是阿里的X-Paxos协议，X-Paxos协议在阿里内部的业务中，包括阿里云的多个产品中，已经稳定使用了很长一段时间，包括企业版的AliSQL、PolarDB for MySQL以及PolarDB-X等产品，都使用了X-Paxos，具体的协议这里就不详细展开阐述，跟其他的一致性协议基本类似。这块主要讲一下，我们在物理复制里面引入了一致性协议之后的主要能力。
首先整个高可用集群是一个单点写入、多点可读的集群系统，其中Leader节点可以作为单点的写入节点来对外提供读写服务，产生了WAL日志之后，它会向其他节点进行同步，Follower节点是不可写入的，它主要是接受来自于Leader的WAL日志，然后进行回放，最终它可以对外提供一个只读服务。
那么我们高可用系统的特点是什么？
首先，它能保证集群数据的强一致性，也就是RPO=0。当多数派节点的WAL日志写入成功后，我们才认为日志是提交成功了。
另外一点是本身我们支持自动failover的，当发生failover之后，WAL日志会首先跟Leader对齐，然后再次从Leader上拉去日志，对齐主要是通过一致性协议来实现，后面会详细讲一下。
第三个特点是刚才提到自动failover，大家知道在我们的高可用集群里面，只要半数以上节点存活的时候，就能保证集群正常对外提供服务。但是当Leader节点出现故障的时候，我们就会自动触发集群的重新选主流程，然后由新主对外提供读写服务，然后Follower节点也会自动从新的Leader节点上同步WAL日志，同时自动跟新的Leader对齐WAL日志。
第四点是在线集群变更，就是可以在线增删节点，包括手动切换，这些操作不影响业务的正常运行，具体也是由一致性协议来保证的，最终集群内的配置肯定会达成一致。即使在集群配置变更过程中发生一些异常，比如主库挂了或其中一个备库挂了这样的情况，最终集群成员状态还是能保证一致性。
除了Leader、Follower节点之外，我们在集群中还有其他两个节点，其中一个是Logger节点。Logger节点不存储数据，它从Leader中拉取到日志之后，它不进行回放，只保留实时日志，日志的目的是三个节点成本与主备基本相当。
另外一个是Learner节点，它本身没有多数派的决策权，但是它能提供只读服务。比如Leader节点在判断多数派节点的时候，其实并不考虑Learner节点，这个节点主要作用是它作为加节点的一个中间状态，比如新加的节点相对于Leader节点延迟比较大的时候，此时如果直接把它当做一个多数派决策的节点加进来，可能会影响Leader的可用性，或者影响Leader的提交延迟，所以我们先把它以Learner的角色加入到集群中，让它先同步数据，当数据基本追上的时候，我们再把它升级成Follower节点。
其次，Learner节点另外一个作用就是我们可以把它作为一个异地的灾备节点，主要特点是当时发生地点切换之后，自动从新的地方同步日志，对于原生的standby，当发生了主库切换之后，它并不会自动地从新主库上同步日志。
在集中部署方面，我们支持跨机房和跨域的部署，包括同机房三副本，同城三机房三副本，以及两地三机房五副本，还有三地三机房五副本的部署。
另外是跨域，刚才提到可以用Learner节点进行灾备，此时并不会影响Leader节点的可用性。另外，我们这个架构里最重要的一点也是比较关键一点，就是我们兼容PG原生的流复制和逻辑复制，能保证下游的消费者不受影响。
二、一致性协议复制实现
（一）基本原理
接下来介绍一致性协议复制的具体实现。
首先我们看一下PolarDB for PG一致性协议复制的基本原理，主要包含两方面，第一方面是过原生的异步流复制来传输WAL日志，另一方面是哪些日志在多数派上已经同步成功，这是由Leader节点上通过X-Paxos协议来确定的。
对X-Paxos来说，日志提交位点它是以Consensus Log为载体的，然后推进Consensus Log提交位点，所以我们会针对每一段WAL日志生成一个相应的Consensus Log etnry，然后Consensus Log etnry中记录的是这段WAL日志的一个结束LSN。
如上图的例子，比如在Leader节点上，我们已经有三段日志，有了相应的一个Consensus Log etnry，第一段LSN是从100-200，第二段是从200-300，第三段是从300-450，然后生成的 Consensus Log Index分别是1、2和3，我们把Consensus Log etnry和WAL日志位点首先要结合起来，然后我们又引入了持久化的依赖，就是说每个Log etnry在持久化的时候，它必须要确保相应位点的WAL日志已经持久化成功了。
LogIndex1要持久化之前，我们必须要确保LSN等于200之前的WAL日志都已经回刷了，这样Consensus Log的回刷位点本身跟WAL日志的回刷位点也结合起来了。
在引入了这两个机制之后，如果Consensus Log提交成功了，那么就是说Consensus Log肯定已经在多数派上持久化成功了。根据刚才的依赖，对应位点的WAL日志肯定也已经在多数派上持久化成功了。
大家可以看看下面的例子，Leader上面有三段WAL日志已经生成对应的Log etnry，然后三个Log etnry对应的WAL日志也都已经持久化了，包括Consensus Log etnry自己也都已经持久化了。那么在Follower1这个节点上，虽然Log index为3的WAL日志已经持久化成功了，但是可能由于并没有接收到Log Index为3的Consensus etnry，所以Log etnry并没有持久化成功。然后Follower2上面Log Index为3的Consensus etnry和WAL日志，因为WAL日志本身都没有持久化成功，所以Consensus Log就根本不可能持久化成功。
在根据这三个节点的现有状态，就是根据X-Paxos协议，当前Leader会发现LogIndex为2的日志在多数派节点上已经都持久化成功了，所以在Consensus Log层面的Commit Index是2，转化成LSN之后，Commit LSN也就是300，这是我们针对LSN多数派同步的基本原理。
（二）进程/线程架构
下面讲一下实现层面的几个关键点。
首先是进程和线程的架构，PG本身是多进程的架构，而X-Paxos是多线程架构，这里面会涉及到的一些问题，就是PG的进程本身无法直接调用X-Paxos的接口，或者它无法直接访问X-Paxos内部的私有内存，所以我们最终选择以X-Paxos为基础，然后新引入了一个Consensus的服务进程。
进程内部会包含多个线程，然后其中包含了X-Paxos的多线程，对外它主要提供多数派日志提交以及相关服务。这个服务是一个常驻的进程，就是说当startup进程启动之后，在这个进程中启动。
首先介绍一下Consensus进程内部的几类线程，第一部分就是X-Paxos内部的一些线程，包括I/O线程和工作线程。I/O线程主要负责节点间的网络通信，工作线程主要负责协议的处理，比如发起选举，比如Follower节点要处理日志的Append请求，可能需要发起选举的请求，主要是跟一致性协议、算法相关的处理逻辑。
除了这些线程外，Consensus进程本身又引入了四类线程，首先是Append Thread。刚才在原理里提到说，我们会对每一段的WAL日志生成Consensus log，这主要是由Append Thread来完成的。它根据当前WAL日志的回刷位点来生成Consensus log etnry，然后把 log etnry传递给X-Paxos进行同步。
第二类线程是Advance thread，是推进WAL日志的提交位点，它主要就是从X-Paxos中获取当前Consensus log的提交位点，然后把它转化成LSN位点。另外，Advance thread同时会根据Consensus协议层的一些状态变化，来驱动PG层进行状态变更。比如Consensus层发生了切除操作，那么Advance层检测到切除的动作或事件之后，它就会触发驱动Postmaster或startup进程进行一些相应的变动，这个下文会具体阐述。
第三个是Command 线程，它主要是处理一些集群变更的命令。比如Leader切换、增删节点等命令，一般来说在PG内部的处理方式是用户发生的请求一般由Server Process处理，但Server Process本身又无法直接调用X-Paxos内部的一些接口，所以我们的处理方式是Server Process把所有的管理请求放到一个共享队列里，然后由Command threads从共享队列里面拿请求来处理，处理完成之后再把执行结果放到执行队列里面去，然后返回给Server进程。
第四类是统计类的线程，这一类线程主要是处理一些状态和统计信息获取的类型图，也就是获取X-Paxos协议内部的一些状态。整个处理的逻辑跟集群变更的命令差不多，也是通过共享队列进行交互。
接下来讲一下Consensus内部的内存情况，以及它的并发控制机制。
内部内存主要分为两种，一种是X-Paxos本身分配的私有内存，这部分内存只有Consensus内部的一些线程，包括X-Paxos线程，以及刚才提到的Server Threads。Server Threads包括 Command Threads和统计的Statistics线程。
除了这一类内存之外，另外一种内存可以由X-Paxos线程，Consensus线程以及PG进程都可以访问的共享内存。这些内存主要是进行Consensus process以及 PG进程之间的一些状态交互，这类内存的访问接口必须是线程安全的。
对于PG侧的一些共享内存，Consensus Process内部可能也是需要访问的，这时候我们必须要确保Consensus Process内部只有一个线程会访问这些内存，可以认为Consensus Process来访问这块内存。
第三个是Consensus Log的管理，这里能确保只有Consensus process内部的一些线程进行读写。
以上是整个进程和线程的架构。
（三）一致性协议复制流程
下面我们看一下一致性协议复制的流程。
当PG进程需要提交WAL日志的时候，首先本地会写入WAL日志，然后开始等待提交LSN超过当前要提交的位点。
提交了请求之后，我们会在两个链路上并行进行同步，在流复制链路上，它跟原生的逻辑其实是差不多的，它首先是通过WAL Sender来发送WAL日志，然后在Follower节点上由WAL Receiver接收，并持久化WAL日志。
在Consensus提交链路上，它主要流程是在Leader上，刚才也提到了由Append Thread根据当前的WAL日志回刷点来生成Consensus Log etnry，然后它需要把Consensus Log etnry写入本地，之后会传递给X-Paxos，开始发送到Follower节点。
在Follower节点上接收到Consensus Log之后，首先要确保所对应位点的WAL日志已经持久化成功了，确保之后就可以在本地写入Consensus Log，完成之后就可以回复Leader，表示本地已经持续化成功了。
Leader节点会根据当前所有节点Consensus Log的持续化位点来确定当前最新的提交位点，之后Advance线程会把提交位点转化成LSN，然后推进Commit LSN，再唤醒所有等待的PG进程。
正常的流程可能会比较简单一些，复杂的是当集群的状态、节点的状态发生变化的时候，应该如何进行协同处理，这个问题下文会阐述。
（四）Consensus日志存储
下面看一下Consensus日志的存储问题。
X-Paxos协议本身只负责日志的强一致同步，日志的持久化是通过API的方式由外部实现。
我们看一下在一致性协议中，X-Paxos内部有两类日志，首先是刚才提到由Append thread产生的，就是与日志同步本身相关的一些正常Log etnry。
从上文可以看到，这类日志本身除了一致性协议相关的一些信息，比如Term、 Log Index 、Type，还会自带一个CRC。除了这些信息之外，它其实只是包含了当前所对应那段WAL日志的结束LSN，所以它的长度是固定的，这类日志在Consensus Log里面是占据了大多数。
第二类是X-Paxos协议，它本身会产生一些成员变更或者集群配置变更的日志，这些日志肯定是变长的，因为它里面要包含各个节点的配置信息，但是这个日志只占了非常小的一部分。
所以在日志存储这方面，我们结合大部分日志都是固定长度的特点，采用了定长日志和变长日志混合存储。这个方案就是在定长日志流中，对于定长日志它存储了完整的日志；变长日志只存储了它的偏移和长度，然后把变长日志的Payload，我们会在另外一个日志流里面存储。
在日志读取的时候，首先根据日志类型来确定是定长日志还是变长日志，如果是定长日志的话，就直接获取LSN信息，就可以获取到完整的信息。如果是变长日志，我们就根据日志中记录的偏移和长度去变长日志流里读取相应的内容。
这样的好处是大部分情况下，当我们要获取定长日志的时候，可以直接通过Log Index定位日志所在的页面，以及这个页面上到底在哪个etnry，它的偏移是什么。
我们可以加速这个页面的定位，另外我们也引入了页面缓存，同时也引入了相关的一个LRU替换策略。
（五）Consensus状态机与DB状态机协同
介绍完日志复制的主要逻辑之后，接下来介绍如何根据X-Paxos内部Consensus的状态变化来推动DB状态的变化。
首先，我们采用的方案是由Consensus进程主动探测X-Paxos层的状态变化，然后根据状态的变化产生一些变更的事件信号，然后通知Postmaster进行状态变更。如上图所示，左半部分是根据Consensus状态的状态变化产生事件，右边是 DB侧收到这些信号之后，推进DB层的状态变化。
这会涉及到WAL日志对齐的问题，举个例子，比如发生了一个切主状态变化之后，如果Follower节点上从旧主库上拉取的WAL日志在新主库上不存在，那么当我们从新主库上重新去拉取WAL日志的时候，需要先充填掉多余的WAL日志。对于这一类状态变更，只有当日志对齐了之后，Consensus才能继续向前推进。
为了解决这个问题，我们给WAL日志也赋予了一个Term状态，也就是说只有当WAL日志的Term推进到最新之后，有相应的Term的Consensus log才能持久化，这样就能保证把上一个Term的WAL日志，多余的日志截断完成之后，下一个Term的Consensus Log才能持久化，否则根本不知道LSN对应的是一个上轮Term还是当前Term。
除了刚才提到的WAL日志截断情况，在一致性协议里面，Consensus Log本身可能也会出现截断的情况。在这种情况下，本地的WAL日志也是需要被截断的。在以上两种情况下，WAL日志被截断之后，DB侧的一些数据状态，比如数据页面clog页面，这些应该如何处理？
首先，我们处理的策略主要包含三点。第一点是数据页面或者Clog页面在回刷磁盘持久化之前，必须要确保对应的WAL日志都已经在多数派上提交成功了，因为一旦持久化之后的状态肯定不会退，在一致性协议里面不会发生提交的状态、日志被截断。
另外一个点是在Follower节点上，只有当WAL日志在多数派上提交成功之后才开始回访。这个时候 Follower节点上不管是缓存还是持久化的状态，其实都不可能出现回退的情况。
说到缓存,本身PG的机制是先修改比如说数据的Buffer，之后它会持久化WAL日志，所以可能当出现Leader降级之后，需要回退cache的情况，这里的处理逻辑是直接重启。因为此时需要从一个正常的读写状态进入到Recovery状态，目前 PG里没有从读写状态进入到Recovery状态的逻辑，所以就直接重启再重新进入到Recover状态。
（六）双状态机协同-示例1
接下来会通过一个例子来具体介绍一下整个状态变更的过程。
比如当前是Follower状态，原来的状态如上图所示，每种状态是上半部分，下半部分是新的状态。
首先，比如Consensus进程探测到Term和Leader ID发生了变化，原来的Term是5，Leader ID是2，新的Term变成了6，新的Leader ID也变成了3。
当Consensus进程发现了这个状态变化之后，首先需要额外再获取当前Leader的信息，比如把ID转化成IP和Port，然后再获取一下当前Consensus Log的日志位点。获取到这些信息之后，就会直接去修改Postmaster的状态。修改完Postmaster状态之后，就给Postmaster发一个信号，然后Postmaster收到的信号事件，就是Leader发生了变化。Postmaster进程在收到这个信号之后，因为这个时候是Stream复制状态，所以需要去触发startup进程进行Recovery状态的变更。其中就会修改startup进程的recovery状态，比如还是保持Stream复制状态，becameLeader仍然是false，把Term变成6，再设置一下最新的Leader的IP和Port，其中也包含当前Consensus Log的位点。
修改完这个状态之后，就通知startup进程状态变更，然后startup进程本身会不断检测自己的Recovery状态，当发现Leader状态发生变化了就会重启流复制，然后从新的Leader上拉取。比如刚才提到的可能会截断日志，这里不详细展开，有兴趣的话可以对照代码仔细看一下。
三、代码结构
（一）主要代码修改
上文介绍了一致性协议复制的原理和大体实现，接下来看一下相关的代码修改。
主要包含以下几个方面，首先是一致性协议复制，第一部分是Consensus进程管理和提交主流程，第二部分是Consensus日志管理，比如日志的Append，日志根据Log Index的读取，都在Consensus日志管理文件里，第三部分是Consensus日志页面，就是具体缓存和持久化的相关管理。
第二块是流复制，主要包含两部分，第一部分是要收到包括从Consensus状态如何触发Postmaster的状态变化，然后Postmaste去触发startup进程的状态变化，主要是在xlog.c里。另外，流复制walsender和walreceiver这块也做了一些简单的修改，主要是在walsender.c和walreceiver.c文件里，大家可以去看一下。
另外，我们知道PG是C语言，X-Paxos是C++语言，所以这里需要相互的Wrapper。第一个是需要基于X-Paxos的相关接口提供一个c的Wrapper，另外日志管理这块是用C实现的，那么为了给X-Paxos使用，所以这块会提供日志管理接口的C++的Wrapper。
X-Paxos主要包含两部分，一个是算法的实现，就是在Libconsensus下面Consensus文件夹里，另外一块是X-Paxos本身依赖的高性能的网络编程框架，就是Libeasy。
最后一块是日志节点的实现，也就是Logger Syncer的功能，主要在polar_datamax.c这个文件里面，主要是如何驱动流复制的逻辑，其次是从Consensus状态变化，如何驱动Logger Syncer的状态变化。
