PolarDB-PG分布式整体架构
PolarDB-PG开源是一个分布式的数据库，第一期开源是单机和三节点高可用的部分，但是现在开源的单机的部分已经具备了支撑分布式的一些基本功能，包括基于时间戳的MVCC，以及事务可见性方面的一些特性。
本文会介绍单机如何支撑分布式事务，以及如何保证可见性、一致性等特性，这些在开源的代码里面也已经有了，我们在后期会把分布式协调节点的逻辑开源，就可以真正地跑起一个分布式的数据库，并且保证分布式事务全局一致性，提供ACID特性。
基于提交时间戳的MVCC的设计动机
我们基于提交时间戳的MVCC的设计动机有两个，一方面是改进单机的性能，就是消除基于快照的多核可拓展瓶颈，Postgre采用的是基于ID的快照来保证事务的隔离性，这样的话会有一些快照的生成，还有生成的瓶颈。
另一方面，我们在单机上支持基于时间戳的分布式事务协议。这样的话，我们既可以单机来跑，在部署成分布式以后，也可以去支持分布式事务。
消除基于快照的多核可扩展瓶颈
可以看到传统PG基于快照的一些瓶颈，MySQL也是一样的，都会从运行事务列表里获取一个快照来获知在事务或语句开始的时候，当前正在运行的事务。
这样的话会有一个问题，就是它会去加 Proc Array 的锁去遍历，虽然是共享锁，那么这在高并发下就有一个遍历的开销。
另外一个就是共享锁的竞争，因为事务在结束的时候需要加互斥锁去清理，那么这个时候就会造成锁的竞争以及获取快照的开销，O（N）的开销，即要遍历N个Proc。
支持基于时间戳的分布式事务协议
我们在分布式场景下也是一样的，如果在分布式场景也采用XID Snapshot的话，也会造成生成全局快照的单点GTM瓶颈，每个节点也需要通过网络从GTM获取一个分布式的快照，当集群并发事务很高的时候，快照获取的开销也很大。
基于提交时间戳的MVCC
基于提交时间戳的MVCC的话，假如有任意的两个事务T1、T2，T1提交的修改对T2可见的条件就会很简单，就只要T1的提交时间戳小于或等于T2的开始时间戳。事务开始和提交的时候，我们都会给它分配时间戳，对于单机数据库，比如说现在开源的，我们就会采用一个原子变量来生成单调递增的64位时间戳。
我们以一个事例来看，图中有三个事务T1、T2、T3，我们可以看到T1、T2是串行的，相当于T2在T1结束以后才开始的，所以T1的修改对T2是可见的。T3和T2是并行的，这样的话T3对T2不可见，我们可以通过时间戳来确定它的开始及结束的绝对顺序，来保证可见性和隔离性。
提交时间戳存储和访问
在基于时间戳的MVCC中，为了做可见性判断，我们就要存储每个事务的提交时间戳。
存储的管理有空间分配、回收、持久化、故障恢复等。对于单机数据库可以采用非持久化的存储机制，就是PG社区里CSN（Commit Sequence Number）的方案，它维护了一个对全局所有事务都可见的最小的Transaction Xmin。
当XID小于Transaction Xmin的提交时间戳的空间就可以回收，因为它对所有的事务都可见了，只要它的XID小于这个，判断它可见性的时候就可以直接判定为可见，所以就不需要存储，它存储提交时间戳的空间就可以回收，用来存储其他事务的时间戳。
XID小于Transaction Xmin可以通过CLOG去判断可见性，就是提交即可见。对于数据库重启，重启之前提交的事务对当前正在运行的事务均可见。
对于一个分布式数据库就不一样，它需要一个持久化的存储，为什么？一是我们的每个节点是去中心化的，每个节点都独立维护了自己的XID的分配，要去计算一个全局的Transaction Xmin不太可行。我们可能会有另外一种方法，就是用一个中心节点，比如说GTM，去维护全局唯一的XID，这样的话计算全局Transaction Xmin就会有开销。
同时分布式的逻辑就会很复杂，而且这样的话XID消耗也会比较快。当规模很大的时候，比如几百个节点的时候， XID消耗就会很快，因为32位的XID很快就会进入回卷的状态。
当没有全局XID分配的情况下，分布式数据库中一个节点重启，重启之前的事务不一定可见，所以需要恢复提交时间戳去判断可见性，所以一个理想的方案就是要把提交时间戳持久化存储。
提交时间戳存储设计与实现
可以看一下持久化存储的系统。
最底层是提交时间戳的一个存储，这是一个物理上的按页持久化存储，并且可故障恢复。上面Buffer层用来缓存访问过的物理页面。
我们同时用了Hash-Partitioned的方法，实现多分区的LRU Buffer，来提高它的可扩展性，减少锁竞争。
事务在提交的时候就会以XID为Key，以CTS为值，写入整个存储中。在做MVCC Scan可见性判断的时候，我们就会去存储里面去读XID的Timestamp。为了加速，我们在Tuple Header里也会缓存这些 Timestamp ，这就跟缓存CLOG的提交状态一样，就是为了减少对CTS的访问。
多核可扩展CTS buffer管理
接下来看一下多核可扩展CTS buffer的管理。
CTS在存储上跟CLOG类似,是连续的空间，就是存储32位连续XID的提交时间戳，每个XID占用8字节去存储它的Timestamp，物理上用连续的一些的文件来存储。同时将文件逻辑上切分成一组物理页，然后可以按需加载到LRU Buffer里面。如果有一个全局的Buffer的话，我们可能会在LRU发生替换的时候，写回的时候会有全局锁的竞争，在加锁的时候等待IO的完成，这样会序列化IO访问，并造成比较严重的可扩展性瓶颈。
我们实现了一个LRU多分区划分。每个XID对应在一个固定的物理页里，然后物理页再按照固定的算法映射到Hash-partitioned的LRU分区中，这样的话我们可以去掉中心的竞争，这样每个分区可以独立地进行LRU替换、刷盘、读取磁盘，这样可以消除全局锁的竞争，并且并行化IO处理。
多核可扩展性
上图是一个实验，我们在一个机器上，实验是客户端数目从1并发到128， LRU从1个LRU分区到64个LRU分区，但即便是不同的分区，它总的Buffer大小是一样的。
在上图中可以看到在不同并发（1~128）下不同LRU Partition的数目的吞吐。随着LRU的数目越多，它的性能和可扩展性越好。最下方的那条线就是单LRU，在32个并发的时候，它的性能就开始出现转折，就会慢慢变差，甚至会并发越高性能越低，而多分区LRU会保证并发越高，性能能够线性增长。
总体来说，我们可以保证性能更好，这样频繁访问CTS不会带来很大的瓶颈和开销。
CTS持久化和故障恢复
关于CTS持久化和故障恢复，我们每个事务XID在CTS中有四个状态，分别是提交，终止，运行和2PC prepared。那么在同步提交模式下，事务提交时间戳先写入WAL，再写入CTS，从而支持故障恢复。同时，我们用2PC record记录来恢复CTS中prepared状态。异步提交模式下就跟CLOG一样，我们会去记录最大提交的LSN，在CTS页面在写入磁盘之前，保证WAL已经持久化到该LSN。
CTS快速事务状态查询机制（1）
另外一个就是，我们相比社区CSN也好，PG也好，我们可以更好地做到快速事务状态查询。
Postgre SQL判断事务状态的时候，会结合CLOG和Proc Array去判断，我们从CLOG中能够获取事务是否提交状态，而判断事务是否正在运行，需要遍历Proc Array来确定，判断事务是否运行在tuple update，hot-chain pruning的时候关键路径会被频繁调用，造成 Proc Array锁的竞争，以及高并发下遍历开销O（N）的时间开销。
那PostgreSQL为什么不能用CLOG来独立地判断事务是否运行，而要去遍历Proc Array呢？
这是因为CLOG中每个XID的Commit的状态都是准确的,REDO可以恢复所有提交状态，只要提交了肯定都有。Abort的状态就不一定了，因为Abort分为事务主动Abort，或者是报错，它会记录在CLOG中。但是数据库Crash的时候，比如断电或其他原因造成的事务abort，就来不及写入CLOG， REDO也没法恢复。对于CLOG中未写入提交状态的事务，它可能是正在运行，也有可能是Crash Aborted，这个时候我们就没法通过CLOG去做判断，所以PG需要结合Proc Array去判断是否正在运行。
CTS快速事务状态查询机制（2）
我们设计了一种oldest active xid机制实现通过CTS O(1) 免锁快速查询所有事务状态，可以去掉Proc Array的遍历。和CLOG一样，CTS中提交事务状态都是准确的，重启以后，我们可以确定一个oldest active xid。这个XID怎么确定,就是通过 next xid, next xid也是故障恢复以后会确定下一个可用的xid初始化，并且要小于等于所有的2PC prepared xid。
故障恢复时，我们会把oldest active xid到next xid这一段区间里面，CTS为0的全部会设成aborted，“P”就恢复成Prepared，“C”就恢复成Commit。“0”表示未设置，我们就认为它是在上一次故障的时候就aborted掉了还没来得及写，我们就把它主动恢复成abort。
运行时，小于oldest active xid的CTS，如果是非提交的，例如0，它 就是aborted，是在上一次crash aborted。如果大于这个的，就通过CTS直接去返回。这样的话我们就不需要去遍历Proc Array，Proc Array在高并发的时候开销就会很大。这样的话只要O(1)的时间查询就可以确定状态是提交，abort还是运行，这样性能会更好，并且会没有锁的竞争。
CTS存储空间回收
下面介绍CTS存储空间回收。
因为我们是以XID为索引的Key，从2的32次方，PG会存在XID回卷，我们会跟着XID回卷去truncate CTS的空间。
PG的XID逻辑就是它有2的32次方的空间，它会一分为二，这样它在回卷的时候保证可见性判断。如上图所示，next xid往上是它过去的xid，往下是它未来的xid。它不管怎么转，都是可以回卷，都可以正确比较两个XID的大小。它会定期地创建一个Frozen xid cutoff，等于oldest xid减去一个配置的guc的一个Frozen参数，这样把之前的xid全给回卷了。
并将之前回卷的XID在每个tuple中改成Frozen xid，这样表示它对其它所有正在运行的事务均可见的，这一部分xid就被回收，可以再用了。
CTS就随着xid的逻辑，在它回卷的时候会把回收的XID空间对应的CTS存储空间给Truncate掉，然后回卷的时候又重复利用来存储提交时间戳。这样的话就可以2的32方XID对应32GB的CTS文件存储就可以保证一直用下去，不会溢出。
基于CTS支持分布式全局一致性事务（1）
我们基于CTS支持分布式全局一致性的事务，相当于每个节点都会有个CTS，但是同一个分布式事务的提交时间戳是一样的，比如1001。但是它在每个节点，XID是各自独立分配的，各自独立维护，但是它的提交时间戳是一样的，可见性判断都是全局一致的。
开始和提交时间戳可以用中心化的时钟GTM来生成，或者用混合逻辑时钟HLC来生成。
基于CTS支持分布式全局一致性事务（2）
我们目前主要开源的是HLC的版本，在分布式下，每个提交时间戳提交的物理时间并不一定完全一致。比如T1在A节点和B节点，我们不能保证完全同时提交，另一个并发事务T2，可能会看到T1部分的修改，比如看到A提交了，看到了它的修改，但是B正在运行还没提交，根据隔离性它不可见，此时就无法保证分布式的一致性和隔离性。
我们可以采用2PC Prepare等待机制来解决全局提交一致性：采用2PC来提交一个分布式事务，在Prepare阶段，每个节点在CTS中写入该分布式事务的Prepared状态。Commit的时候，我们会去决策一个提交时间戳，再把提交时间戳发下去，把Prepare的状态原子的替换成提交时间戳，当另外一个并发事务T2对T1的修改进行可行性判断时，如果T1处于prepare的状态，我们就要等待T1结束，再进行时间戳的比较。
这样的话，我们就能避免在A节点、B节点看到部分提交结果的问题。
基于PostgreSQL数据结构的读等待机制设计
那么就有一个问题，就是基于PostgreSQL数据结构实现读等待机制。
我们在读等待的时候，不能把Buffer的锁加上，这样的话会阻塞写，影响并发性能。如果发现它是prepare的，要等待它，我们首先要解锁Buffer shared锁，允许并发写进来，同时等待xid结束再去加buffer。
这个地方可以保证它还能找到原来的位置进行扫描，这是因为PG的逻辑就是它会有item去指向这些Tuple，Tuple可能会移动进行页面的compact，但是item是不会动的，它可以找到正确的位置，这样的话就可以保证正确性。同时buffer也会引用计数，这样保证buffer不会被删掉或做其它的操作。
基于HLC的分布式事务时钟算法（1）
我们基于HLC的去中心化的分布式事务时钟来支持分布式事务。
这个 HLC的算法在开源的代码里已经有了，但是协调逻辑分布式的代码还没有开源。我们后面加上分布式协调逻辑的代码以后，就可以支持真正的分布式事务。
我们现在单机上采用HLC来支持单机的事务，就是跑一个单机也能正确地跑，跑分布式的时候，基于HLC可以保证全局一致的事务。HLC的设计是物理和逻辑时钟混合，64位时钟由最低16位为逻辑时钟，中间46位物理时钟（毫秒）和最高两个保留位组成。
这样的话，逻辑时钟主要是用来追踪事务之间的因果先后顺序。物理时钟主要是用NTP或PTP去同步不同节点之间的物理时钟，来保证它们可以读到一个相对很新的快照。
每个节点维护一个max_ts时钟，并周期性持久化，重启后REDO恢复最大值。
我们有三个时钟操作，分别是ClockCurrent，ClockUpdate和ClockAdvance。
ClockCurrentc就是读取当前的Clock，相当于我们用Max_ts和本地的物理时钟local-phys-ts取最大值返回。
ClockUpdate就是用一个Timestamp去更新Max_ts，我们取最大值。
ClockAdvance是把max_ts和 local-phys-ts取最大值后再加1返回，整个过程都是加锁来保证原子性。
上述操作中，local- phys-ts是本地机器获取的物理时钟，并取毫秒时间。左移16位与max_ts 对其进行运算（max-ts最低16位是逻辑时钟）。
不同机器的物理时钟可以通过NTP或PTP协议进行同步，保证很小的时钟倾斜，保证跨协调节点之间的事务可以获取一个freshness的快照。
基于HLC的分布式事务时钟算法（2）
我们的时钟算法就是在事务Begin的时候，会在协调节点上为它分配ClockCurrent进行startTS，startTS到了每个DN节点以后，会用startTS去更新本地的Max-ts混合逻辑时钟。
事务Prepare的时候会去每个参与节点调用ClockAdvance，获取prepareTS，同时返回给协调节点。协调节点会从所有的prepareTS选最大值作为commitTS，同时更新CN的混合逻辑时钟，并且下发给每个DN去提交事务，并且用commitTS去推动每个参与DN的混合逻辑时钟前进。
版本链提交时间戳递增
这个特性可以保证在版本链提交时间戳递增。
假设我们在一个DN上有两个事务T2、T3，T2先获得锁先进行提交，那么ClockUpdate就会用T2的commit_ts，使得该节点的max_ts大于等于T2的commit_ts，那T3获得锁再进行提交，决策的T3的commit-ts，就会大于等于DN1的 prepare_ts，它就会大于等于 max{max_ts, local_phys_ts} + 1，这样就能保证T3.commit_ts > max_ts >= T2.commit_ts，这样的话版本链时间戳是递增的。
Repeatable Read下，T3会被abort，从而避免丢失写问题。
全局一致性正确性证明
上面HLC的算法，我们可以证明它的正确性。
我们假设在任意一个节点如DN1上，如果有两个并发事务T1、T2,如果T2在扫描T1的修改时，T1还未prepare，那么T1对T2是不可见，因为没有prepare，也没有提交时间戳，所以直接就判断不可见了。
这样的话，T2的start_ts一定会小于T1的commit_ts，这个是因为T1在prepare阶段分布式决策的T1的commit_ts一定会大于等于DN1的prepare_ts，则大于DN1的max_ts。而T2的start_ts 在到达本节点时，一定会更新max_ts，使得 max _ts大于等于 T2的start_ts。因此，当T2扫描T 1的修改时，T 1还未进入prepared状态，则说明T 1的commit_ts一定会大于T2的start_ts。
由于commit_ts和start_ts是全局统一的，因此在任意节点，T1的commit_ts大于T2的start_ts条件都成立，根据时间戳比较判断可见性，T1的修改对T2均不可见。
如果T2在扫描T1修改时，T1处于prepared状态，T2需要等待T1的提交，或者说abort。如果abort，则不可见；如果提交，那就有commit_ts，直接时间戳比较进行可见性判断，即如果T2.start_ts >= T1.commit_ts，则可见。
如果T2在其他节点没有看到T1 的prepared状态,根据上面第一点的证明，最终T1的commit_ts会大于T2的start_ts，则在本节点T2等待结束，也看不到T1的修改。因此，T2可能看到T1的修改，仅当T2在所有节点都看到了T1过了prepare阶段。
根据上面的证明总结，如果T2在某个节点扫描时未看到T 1的prepared状态，T1的修改对T2不可见，最终T2.start_ts < T1.commit_ts，因此T2在其它节点也不会看到T1的修改。如果在某个节点看到T1的prepared状态，T2会等待T 1结束，这样如果T2.start_ts >= T1.commit_ts，则可以看到T1的修改。从而我们可以保证T2要看到T1的修改，当且仅当T2的start_ts大于或等于T1的commit_ts。
外部一致性正确性证明
另外比较关心的就是外部一致性，HLC可以保证跨session之间的快照隔离（内部一致性），以及同一个CN的强外部一致性，跨CN的弱外部一致性。
外部一致性的定义是数据库事务T1提交成功返回，此时开启的事务T2一定能够看到T1的修改，相当于 T2在T1提交成功返回以后，立即可以看到T1的修改。如果T1、T2都连接到一个CN的客户端，我们就可以保证外部一致性。T1结束的时候会用T1的commit_ts更新CN的max_ts，T1返回给客户端，发起T2请求，可以是不同的客户端。T2的start_ts会大于等于T1的commit_ts，所以T2一定能看到T1的修改。
不同的CN之间有时钟偏移，此时不定能保障立马能看到，会有一定的时钟倾斜，PTP协议将一个IDC的时钟倾斜同步在1us内。客户端到CN之间的网络来回延迟远大于时钟偏移，此时就可以保证强一致性。
不同CN之间，如果我们依赖传统通用的NTP进行同步，可以保证读到小于时钟倾斜的提交事务修改。比如在CN1上刚提交了，CN2上时钟偏移可能有5毫秒，要等5毫秒才能看到它的修改。当然，从CN1上返回给客户端，让客户端知道它已经提交成功了，也会有一定的时差，所以一般场景下读不到最新提交，相对来说偏差是比较小的。
大部分场景下，跨Session要求读到前面已经提交的需求一般相对较少，大部分情况下都是在同一个Session里面的事务要求看到前面的修改，所以HLC可以保证即便是跨Session，不同的CN可以保证快照隔离，同一个CN是强外部一致性的，跨CN会有弱外部一致性，未来引入先进的 PPT协议就可以保证强外部一致性。
Remote Recovery 设计动机
接下来介绍一下另外一个性能的优化——Remote Recovery机制。
PostgreSQL会通过full page writes来解决故障时部分写入的页面，因为故障的时候页面可能会没有完全写入，在页面写入的中间就crash了。
此时，PG采用的是checkpoint后第一次修改，在WAL中写入full page，回放时，用WAL中的full page来进行回放，此时full page写的开销就会很大。
Remote Recovery 设计想法
我们有一个Remote Recovery的设计想法，就是通常情况下一个数据库节点是有多节点进行容灾，像我们这次开源的三节点，它就有两个节点进行容灾。我们可以采用Remote Recovery机制在多个副本之间进行恢复，就是一个机器节点的页面可能损坏了，但其他副本有最新的有正确页面，就会备机去读然后再进行故障恢复。
这个特性Oracle里面也有，我们的特性和它的不同点在于Oracle的是做checksum的时候发现它不一致了，就去其他节点恢复。我们还是沿用full page write的特性，在checkpoint后发现是第一次修改，就去备机读。因为checksum并不一定保证完全的正确，而我们这样的话可以保证完全的正确性。
Remote Recovery 实现
上图为Remote Recovery的原理框架图。
我们在回放的时候，发现它是checkpoint后第一次修改，我们就会从远程mirrored节点，比如备机从主机，主机从备机，或者备机从备机，可以把另外一个full page先读过来，然后再Apply。
Apply的时候跟WAL回放的原理一样，就是只有LSN大于远程页面的LSN才会回放，否则的话就直接跳过，说明在备机或远程的一个节点已经回放过了。
这里有个很核心的问题，就是何时需要去取remote full page？
在每个checkpoint后第一次修改页面时，我们不写full page，而是在WAL中写入remote fetch page bit，记录一下需要去远程读取页面。
在节点故障恢复重做时，碰到remote fetch page bit，则从mirrored节点远程fetch full page。主机写入checkpoint的时候需要等待备机同步完成，因为我们需要保证主备之间最近的一个checkpoint大家都有，因为回放都是从最近的一个checkpoint开始的，所以必须保证之前的修改在其他节点已经有了，这样我们才能保证回放正确。
这样的话,我们回放的流程跟原来的单机回放是差不多的，也就是当LSN大于page LSN才重做。如果小于，那说明在mirrored的节点已经重做过了，我们就不需要再回放，直接跳过。
还有一些不存在的页，说明它在后面已经删除掉该页了，比如说删除表空间，回收等，我们也可以简单跳过。
我们去连接mirrored节点的时候，需要判断mirrored节点回放是否过了故障恢复节点最近的一个checkpoint点。如果没有，就要等它过了这个点，保证两边最近的 checkpoint点是一样的，因为恢复是从最近的checkpoint点来恢复，这样就可以保证两边是一致的。
Remote Recovery的正确性是保证两个节点之间checkpoint点是一样的，这样我们后面回放的时候就有最新的数据，无非是LSN在另外一个节点是否回放过的区别。
