开发者学堂课程【PolarDB for PostgreSQL 入门：PolarDB forPG 核心 feature 介绍】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/813/detail/13918
PolarDB forPG 核心 feature 介绍
PolarDB 总体的开源是一个分布式的数据库，第一期开源是单机和三节点高可用的部分，但是单机的部分已经具备了支撑分布式的一些基本的功能包括基于时间戳的 mvcc 以及事物可见性方面的一些特性。
这节课主要讲单机如何支撑分布式事物以及保证可见性还有一致性这些特性是怎么做到的介绍一下，这些在开源的代码中已经有了，后期会把分布式协调节点的逻辑开源以后就可以真正的跑起一个分布式的数据库，并且保证分布式事务全局一致性保证提供 ncid 的特性。
1.基于提交时间戳的 MVCC 的设计动机
1）改变单机的性能，消除基于快照的多核可扩展瓶颈
2）支持基于时间戳的分布式事务协议
既可以单机来跑，也可以去支持分布式的事物。
2.消除基于快照的多核可扩展瓶颈
都会从运行事物列表里获取快照来获知在事物或者语句开始的时候当前正在运行的事物，这时会产生一个问题，会产生一个 Proc Array Lock 锁，虽然是共享锁去变例，有一个变例的开销在高并发下，另外一个就是共享锁的竞争，因为事物在结束的时候需要加复制锁去清理，这个时候就会造成锁的竞争，以及获取快照的开销。
（1）锁冲突竞争
（2）获取快照需要加共享锁遍历 Proc Array
（3）事务结束时需要加锁清理自己的 Proc
3. 支持基于时间戳的分布式事务协议
在分布式场景下也是一样的，分布式场景也采用 XID Snapshot 的话也会造成每个结点发一个很大的快照到一个地方去汇总一个分布式的快照，这个开销也是相对来说比较大的。
（1）基于 XID Snapshot 的分布式事务带来的瓶颈
（2）每次需要生成集群范围内的活跃 XID 列表，比如在 GTM 上管理活跃 XID
（3）造成网络瓶颈和 GTM 的 CPU 瓶颈
4.基于提交时间戳的 MVCC
（1）任意并发事务T1和 T2
（2）T1提交的修改对 T2可见的条件：T1.committs<=T2.start ts
（3）事务开始和提交时分配时间戳
单机数据库采用原子变量生成单调递增的64位时间戳
T1对 T2可见，T3对 T2不可见。可以通过时间戳来决定它开始的时间和顺序，来保证可见性和隔离性。
5.提交时间戳存储和访问
（1）为了支持 MVCC 可见性判断，需要存储每个提交事务 XID 对应的提交时间戳
存储空间的管理：空间分配和回收
持久化和故障恢复
（2）对于单机数据库，可以采用非持久化存储机制（社区 CSN 的方案）
维护一个对全局所有事务都可见的最小的 TransactionXmin
XID<TransactionXmin 的提交时间戳存储空间均可以回收
XID<TransactionXmin 通过 CLOG 判断可见性（提交即可见)
不需要持久化，数据库重启，重启之前提交的事务均可见，因为不存在一个事物开启的时候还在运行。
（3）分布式数据库需要一个持久化存储
去中心化，每个节点独立维护自己的 XID=>维护全局
TransactionXmin 不可行
采用 GTM 中心化 XID 维护计算全局TransactionXmin开销大，分布式 vacuum 和 XIDwraparound 逻辑复杂，所有的节点就会绕到一起，XID 消耗就会很快
一个节点重启，重启之前的事务不一定可见，需要恢复时间戳去判断可见性
所以一个理想的方案就是给它做一个持久化存储。
5.提交时间戳存储设计与实现
最底层就是一个提交时间戳的存储，是一个物理化的存储持久化并且可故障恢复，上面有一个八核用来加速，提高他的可扩展性减少锁性针。
事物提交时就会以 xid 为替以 cts 为值就会写入整个存储中。在做 mvcc scan 做可见性判断的时候就会去存储里面去读 xid，为了加速也会在 tuple header 里面也会缓存。
（1）事务提交时，将该 XID 的提交时间戳存入 CTS
（2）MVCC scan 时，首先从 tuple header 中读取 cts，如果不在，则从 CTS 中读取并缓存在 tupleheader
6. 多核可扩展 CTS buffer 管理
Cts 是一个连续的空间，如果有一个全局的 buffer，可能会在 lu 发生替换写回的时候有全局锁的竞争，会造成严重的可扩展性瓶颈，所以做了一个划分。
（1）采用多 LRU 分区的 BUFFER 管理机制来避免全局锁竞争
（2）每个 LRU 分区独立加互斥锁进行 LRU 替 换，刷盘，读取磁盘
（3）当 CTS 在缓存中时，采用共享锁进行读写
7. 多核可扩展性
简单做了个实验，客户端从1变化到128，lru 分寸从1个到64个
（1）在不同并发下1~128下不同 LRUPartition 数目的吞吐
（2）不同 LRU Partition 的总 Buffer 大小一样，lu数目越多可扩展性越好，性能越好。
（3）随着 LRU 数目变多，总的线性可扩展性变好
8.CTS 持久化和故障恢复
（1）事务 X D 在 CTS 中有四个状态
提交，终止，运行，2PCprepared
（2）同步提交模式下，事务提交时间戳 cts 先写 WAL，再写入 C
故障恢复的时候，用 WAL 中的提交记录的 cts 恢复 CTS
用2PCrecord 记录来恢复事务在 CTS 中 prepared 状态
（3）异步提交模式下，CTS 页面组记录最大提交的 LSN，与 CLOG 机制类似
CTS 页面在写入 disk 之前，保证 WAL 已经持久化到该 LSN
减少元数据，一组页面维护一个 LSN
9.CTS 快速事务状态查询机制(1)
（1）PostgreSQL 判断事务状态是结合 CLOG 和 Proc Array
从在 CLOG 中获取事务是否提交状态
判断事务状态是否正在运行，遍历 ProcArray 来确定
判断事务是否运行在 tuple update，hot-chain pruning 等关键路径被频繁调用，会造成 Proc Array 锁竞争，以及高并发下的遍历开销 O(N)
（2）PostgreSQL 为什么不能用 CLOG 来判断事务是否正在运行?
CLOG 中每个 XID 的 Commit 状态都是准确的，REDO可 以恢复所有提交状态
Abort 状态分为事务主动 abort，则记录在 CLOG 中
数据库 Crash 造成的事务 abort，则未写入 CLOG 中，REDO 也无法恢复
对于 CLOG 中未写入提交状态的事务，可能是正在运行，也有可能是 Crash Aborted
10.CTS 快速事务状态查询机制(2)
（1）设计 oldest activexid 机制实现通过CTSO(1)免锁快速查询所有事务状态和 CLOG 一样，CTS 中提交事务状态是精确的，重启后，确定一个 oldest active xid oldest active xid:nextxid 初始化，并小于或等于最小的2PC prepared xid
故障恢复时[oldest active xidnextxid)中 CTS 为0的状态，全部设置为 aborted 运行时，小于 oldestactivexid的CTS非提交事务均为 aborted 事务，否则，直接根据 CTS 返回:运行，提交或终止状态
（2）'C 表示 commit，存储的 cts 没有显示
（3）'A 表示 abort，存储 cts 为2
（4）'P 表示 prepared，64位最高预留位标识
（5）0表示未设置，在 oldestactivexid 后表示运行，在之前为 crashaborted 这样的话性能会更好没有锁的竞争。
11.CTS 存储空间回收
（1）CTS 以 XID 为索引 Kev 存储时间戳或状态为 Value
（2）XID 为32位，最大存储空间:2的32次方乘以8字节(32GB
（3）随着 PostgreSOL 的 XID 冻结和回卷，CTS 复用之前的存储空间
（4）分布式场景下，需要确定全局可以冻结的 XIDcutoff(以后再讨论)
（5）XID32位空间被一分为二，来保证 xid 回卷后正确的大小判断
12.基于 CTS 支持分布式全局一致性事务(1)
（1）每个节点的 CTS 存储分布式事务/单机事务的状态和提交时间戳
分布式事务在每个节点各自分配 XID=>同一个事务在不同参与节点分配不同的 XID
分布式事务在提交时分配提交时间戳，发送所有参与节点
XID 充当索引 key，提交时间戳为 value，写入 CTS
由于每个事务的提交时间戳在每个节点是一样的，从而保证全局一致的可见性
支持中心化时钟(TSO)，或分布式时钟来生成时钟(HLC)
13.基于 CTS 支持分布式全局一致性事务(2)
（1）分布式下，每个节点提交的时间不同以及和并发事务之间的交替可能会导致不一致读
即 T1在节点 A 和 B 提交不能保证完全同时，另一个并发事务 T2可能看到 T1部分的修改
（2）采用2PCprepare 等 待机制来解决全局提交一致性
采用2PC 提交一个分布式事务 T1
在 prepare 阶段，每个节点在 CTS 中写入该分布式事务 T1prepared 状态
在 commit 阶段，每个节点将 prepared 状态用协调节点下发的提交时间戳覆盖
当另一个并发事务 T2对 T1的修改进行可见性判断时:
如果 T1处于 prepared 状态，需要等待 T1结束，再进行时间戳的比较
14.基于 PostgreSQL 数据结构的读等待机制设计
（1）PostgreSQL 依次扫描 item 数组，根据 item 再找到相应的tuple Tuple位置可能会发生变化(hot-chaincompact)
item 在 compact 时可能被设置为 dead，redirected 或者 unused 但 Item位置绝对不会发生变化
（2）XID 已经 prepared，等待提交或 abort
解锁 buffer shared 锁(允许并发写)
等待 xid 结束
加 buffer 锁
通过原 item 再找一次 tuple
进行可见性判断
15.基于 HLC 的分布式事务时钟算法(1)
（1）设计基于 HLC 的去中心化的分布式事务时钟算法
64位时钟由最低16位为逻辑时钟，中间46位物理时钟(毫秒)和最高两个保留位组成
每个节点维护一个 max_ts 时钟，并周期性持久化，重启后 REDO 恢复最大值
（2）时钟操作
ClockCurrent(): max_ts =max{max_ts,local_phys_ts);return max_ts
ClockUpdate(ts): max_ts=max {max_ts,ts};
ClockAdvance0: max ts =max{max tslocal phys ts}+1: return max tsi
上述操作中，local_physts 为本地机器获取的物理时钟并取毫秒时间，左移16位与 max_ts 对齐进行运算
不同机器的物理时钟可以通过 NTP 或 PTP 协议进行同步，保证很小的时钟倾斜，保证跨协调节点之间的事务可以获取一个 freshness 的快照
16. 基于 HLC 的分布式事务时钟算法(2)
17.版本链提交时间戳递增
（1）下面证明发生在任意某个节点，假设为 DN1，并发事务 T2和 T3
假设 T2先获得锁，先进行提交，ClockUpdate(T2.committs)会使得该节点
maxts>=T2.commit ts
T3获得锁，再进行提交，决策的
T2.committs>=dn1prepare_ts=max{max tslocal_phys_ts} +1
因此，T3.commit ts>maxts>=T2committs，版本链时间戳是递增的。
（2) RepeatableRead 下，T3会被 abort，从而避免丢失写问题
18.全局一致性正确性证明
下面证明发生在任意某个节点，假设为DN1
1.)如果 T2扫描 T1的修改时，T1还未 prepare，则 T1对 T2不可见
则T2.start ts<T1.committs，因为T1在prepare阶段分布式决策的 T1.committs>=dn1prepare_ts=max{maxtslocal_phys_ts}+1
而T2.startts 在到达本节点时，一定会更新 maxts，使得 max_ts>= T2.start ts，因此 T1.committs>maxts>=T2.start ts 由于 committs 和 startts 是全局统一的，
因此，在任意节点，T1.committs>T2startts 条 件都成立，均不可见
2.)如果 T2扫描 T1的修改时，T1已经 prepare，则T2需要等待T1的 committs
如果 T2在其它某节点没有看到 T1prepare，则根据上面(1)的证明，最终 T1.committs>T2startts，则在本节点 T2等待结束，也看不到 T1的修改因此，T2可能看到 T1的修改，当且仅当，T2在所有参与节点都看到 T1过了 prepare阶段
19.外部一致性正确性证明
（1）外部一致性定义:数据库事务 T1提交成功返回，此时开启的事务 T2一定能够看到 T1的修改
（2）连接到同一个 CN 的客户端，可以保证外部一致性
事务T1结束时会用 T1committs 更新 CN 的 maxts
T1返回到客户端，发起 T2请求(可以来自不同客户端)
T2.start_ts=max{CN.max_ts,local_phys_ts>=max_ts>=T1.commit_ts。因此，T2一定可以看到 T1的修改
（3）不同 CN 之间依赖 PTP 同步可以保证外部一致性
PTP 协议将一个 IDC 的时钟倾斜同步在1us 内
客户端 到 CN 之间的网络来回延迟远大于时钟偏移
（4）不同 CN 之间依赖 NTP 同步可以保证读到小于时钟倾斜的提交事务修改
（5）总结:HLC可以保证跨 session 之间的快照隔离(内部一致性)，以及同一个 CN 的强外部一致性，跨 CN 的弱外部一致性;通过引入先进的 PTP 协议，也可以再一 个 IDC 保证强外部一致性
20.Remote Recovery 设计动机
（1）PostgreSQL 采用 full pagewrites 来解决故障时部分写入页面
checkpoint 后第一次修改，在 WAL 中写入 full page
回放时，用 WAL 中的 full page 来进行回放
问题:性能开销很大
21.Remote Recovery 设计想法
（1）一个数据库节点通常有多个备机进行容灾
（2）采用 Remote Recovery 机制进行多副本之间恢复
一个主机故障恢复时，从一个备机读取 full page 进行回放避免部分写不一致
一个备机故障恢复时，从主机或者另一个备机读取 full page 进行回放
22.Remote Recovery 实现 原理和框架图
（1）After appliedthe remote page's LSN is updated to the WAL record's LSN
（2）The remote page would be written to local disk later
23.Remote Recovery 实现
核心问题:何时需要去取 remote full page?
在每个 checkpoint 后第一次修改页面时，在 WAL 中写入 remotefetch page bit
在节点故障恢复重做时，碰到 remote fetch page bit，则从 mirrored 节点远程 fetch full page
主机写入 checkpoint 时，需要等待备机同步完成，因为要保证主备之间最近的 point 都有，因为回方都是从最近的point 开始的。
24.Remote Recovery 实现
Remotepage 取回本地后，在 redo 过程中，如果 WAL 的 LSN 大于该 page 的 LSN，则重做;
否则，跳过重做
WAL 的 LSN 小于或等于 page 的 LSN，则说明 mirrored 节点上的页已经回放了该 WAL 记录
如果 mirrored 节点上不存在该页，则跳过重做
如果 mirrored 节点上不存在该页，说明在该 WAL 后的数据库删除了该页(比如删除表，空间回收等)。
该情况下，简单跳过重做
25.Remote Recovery 实现
（1）节点建立 streaming 连接去 mirrored 节点开始
remotefetchpage 前，进行检查
需要判断 mirrored 节点回放是否已经过了故障恢复节点最近的 checkpoint 点。
如果没有过，则需要等待回放至少过了该点
（2）备机去主机恢复
主机需要停服务，以免备机读取 buffer 被锁住
26. Remote Recovery 实现
（1）Remote Recovery 的正确性:保证 checkpoint 的点是一样的
·主机建立 streamingfetchpage 连接时，会确保备机节点上的页已经回放到最近的 checkpoint(ckpt)之后
·则我们可以保证备机上的页的 LSN>=ckpt LSN
节点故障恢复是从 ckpt 开始重做，这样可以保证 remotepage 上不会出现没有回放的 WAL
（2）备机去主机恢复
·主机上的页肯定是最新的
