事务基础

ACID
事务演进
隔离级别
MVCC
2pl
主流数据库实现

PG事务

pg高链接数导致tps下降 1|2

简单总结

更新xmin的ping-pong问题，缓存失效，之前的结构设计不合理，xid存放位置不连续，且xmin每次都需要从 pgxact 中获取，此值会被频繁修改
修改事务相关的组织格式，xids 现在单独存放在数组中
使用 xactCompletionCount 进行事务计算，快照原则上只要没有变化，则不需要重新获取，所以在事务提交或者事务abort的时候，进行自增，只有检测到 xactCompletionCount 变化了才重新获取快照
之前需要 xmin 用于vacuum ，现在使用新机制判断，现在在循环中遍历 xids 取 min ，不对立刻同步其他的 min，所以这是一个粗略值，在之后可以简单进行判断，如果在之后获得了比 min 更大的值，才进行精确判断，且更新 min

无锁算法提交事务，减少proc加锁时间，提升并发

无锁算法是利用CPU的原子操作实现的数据结构和算法来解决原来只能用锁才能解决的并发控制问题

CAS
Fetch-and-add
Test-and-set

内存屏障

内存屏障相关函数，包括 compiler barrier 和 read/write barrier
语义上的布尔值（PG代码里叫flag，具体实现上可能映射到一个字节，或一个整数）的原子操作，包括：

  pg_atomic_init_flag，初始化一个flag
  pg_atomic_test_set_flag, Test-And-Set，这也是flag的唯一支持的原子 操作函数
  pg_atomic_unlocked_test_flag，检查flag是否没有被设置
  pg_atomic_clear_flag，清除已设置的flag

32位无符号整数的原子操作，包括：

  pg_atomic_init_u32, pg_atomic_read_u32, pg_atomic_write_u32，初始化、读、写操作
  pg_atomic_exchange_u32，给原子变量赋值并返回原值
  pg_atomic_compare_exchange_u32, 32位无符号整数的CAS操作，比较原子变量和另一个变量的值， 如果相等就赋一个新值到原子变量里，返回一个布尔值标识是否进行了赋值操作
  pg_atomic_fetch_add_u32, pg_atomic_fetch_sub_u32, pg_atomic_fetch_and_u32, pg_atomic_fetch_or_u32 对某个原子变量进行加、减、与、或操作，并返回变量改变之前的值
  pg_atomic_add_fetch_u32, pg_atomic_sub_fetch_u32 对某个原子变量进行加、减操作，并返回变量改变之后的值

64位无符号整数的原子操作，与32位的实现的操作函数相似，只是实现的是64位版本，这里需要注意的是， 64位版本并不保证所有平台的都支持，目前在PostgreSQL的源代码中还没有被使用。

实际案例：

pg中事务在结束之后，需要设置 PGPROC 中的事务信息，确保其他 session 中再次获取 snapshot 的时候，完成事务不会在活跃列表中。此时会使用 ProcArrayLock 尝试对 ProcArray 加排他锁，此时锁竞争严重，后来对此进行优化，使用无锁编程技术，批量进行xid的重置，具体函数为 ProcArrayEndTransaction

ProcArrayGroupClearXid
  大意为:
        如果竞争锁失败，则把 xid 加入一个数组中，有 leader 进行此数组的 xid  的重置工作，此过程没有加锁，全部使用原子操作
* [v] 主要知道 PGPROC 的具体的组织结构
* [v] 需要只要事务结束的操作函数 ProcArrayEndTransactionInternal 的大致原因
* [v] 需要知道无锁编程带来的收益以及大致的无锁编程技术，以及锁实现

PGPROC数据结构
PGPROC 在共享内存中以数组的形式组织，ProcArrayStruct 中 pgprocnos 字段记录映射关系，对应 PGPROC 中的 pgprocno 字段

(gdb) p * arrayP
$35 = {
  numProcs = 3,
  maxProcs = 122,
  maxKnownAssignedXids = 7930,
  numKnownAssignedXids = 0,
  tailKnownAssignedXids = 0,
  headKnownAssignedXids = 0,
  known_assigned_xids_lck = 0 '\000',
  lastOverflowedXid = 0,
  replication_slot_xmin = 0,
  replication_slot_catalog_xmin = 0,
  pgprocnos = 0x7fe4b541c928
}
(gdb) p  arrayP->pgprocnos[0]
$36 = 99
(gdb) p  arrayP->pgprocnos[1]
$37 = 103
(gdb) p  arrayP->pgprocnos[2]
$38 = 111
(gdb) p allProcs[99]
$40 = {
  links = {
    prev = 0x0,
    next = 0x0
  },
  procgloballist = 0x7fe4b5400fa8,
  sem = 0x7fe4ac86d1b8,
  waitStatus = PROC_WAIT_STATUS_OK,
  procLatch = {
    is_set = 0,
    maybe_sleeping = 0,
    is_shared = true,
    owner_pid = 6629
  },
  xid = 0,
  xmin = 0,
  lxid = 92,
  pid = 6629,
  pgxactoff = 0,
  pgprocno = 99,
  backendId = 3,
  databaseId = 16384,
  roleId = 10,
  tempNamespaceId = 0,
  isBackgroundWorker = false,
  recoveryConflictPending = false,
  lwWaiting = false,
  lwWaitMode = 0 '\000',

事务实现框架

快照

WAL

数据写到buffer中时候，不会选择立刻刷盘，如果任何的数据改动都需要一次IO，则有性能损失，但是只是保留在磁盘中，在系统崩溃的时候，数据会丢失，所以一般都会使用wal保留一部分未刷盘的数据。

REDO log
Redo log通常称为重做日志，在写入数据文件前，每个变更都会先行写入到Redo log中。其用途和意义在于存储数据库的所有修改历史，用于数据库故障恢复（Recovery）、增量备份（Incremental Backup）、PITR(Point In Time Recovery)和复制（Replication）。
WAL segment file
为了便于管理，PG把事务日志文件划分为N个segment，每个segment称为WAL segment file，每个WAL segment file大小默认为16MB。
pg最大可以管理64位地址的wal文件，当前默认wal文件大小为16M，然后文件名的组织格式代表了剩下的寻址空间，首先文件名称可以分为三部分，
- 第一部分8位代表timelineId，和backup有关
- 第二部分是逻辑地址，可全部使用
- 第三是最后部分，只使用低2位
此时地址的组织形式位 (8 * 4 + 2 * 4 + 24) = 64
XLOG Record
这是一个逻辑概念，可以理解为PG中的每一个变更都对应一条XLOG Record，这些XLOG Record存储在WAL segment file中。PG读取这些XLOG Record进行故障恢复/PITR等操作。
WAL buffer
WA缓冲区，不管是WAL segment file的header还是XLOG Record都会先行写入到WAL缓冲区中，在"合适的时候"再通过WAL writer写入到WAL segment file中。
LSN
LSN即日志序列号Log Sequence Number。表示XLOG record记录写入到事务日志中位置。LSN的值为无符号64位整型（uint64）。在事务日志中，LSN单调递增且唯一。
前面说到WAL的64位地址，LSN就是一个变相的，映射wal文件的地址，首先0/28BD908为例，
- 0代表的是逻辑地址
- 后面的字符串中，6位之前的是物理文件编号
- 后6位是文件内的偏移地址
可以使用函数pg_walfile_name和pg_walfile_name_offset查看LSN的具体信息，例如下面的例子，9457712的16进制就是lsn的后六位905030
```
esoye=# SELECT pg_walfile_name_offset('0/1905030');
       pg_walfile_name_offset
------------------------------------
 (000000010000000000000001,9457712)
(1 row)

esoye=# SELECT pg_walfile_name('0/1905030');
     pg_walfile_name
--------------------------
 000000010000000000000001
(1 row)
```
checkpointer
checkpointer是PG中的一个后台进程，该进程周期性地执行checkpoint。当执行checkpoint时，该进程会把包含checkpoint信息的XLOG Record写入到当前的WAL segment file中，该XLOG Record记录包含了最新Redo pint的位置。
checkpoint
检查点checkpoint由checkpointer进程执行，主要的处理流程如下：
a. 获取Redo point，构造包含此Redo point检查点（详细请参考Checkpoint结构体）信息的XLOG Record并写入到WAL segment file中；
b. 刷新Dirty Page到磁盘上；
c. 更新Redo point等信息到pg_control文件中。
REDO point
REDO point是PG启动恢复的起始点，是最后一次checkpoint启动时事务日志文件的末尾亦即写入Checkpoint XLOG Record时的位置（这里的位置可以理解为事务日志文件中偏移量）。
pg_control
pg_control是磁盘上的物理文件，保存检查点的基本信息，在数据库恢复中使用，可通过命令pg_controldata查看该文件中的内容。

[test] `pg_waldump`调试和`pg_walinspect`插件

pg_waldump是一个读取wal文件结构的命令，pg_walinspect具有相同的作用，但是是SQL语句

pg_walinspect pg_get_wal_record_info pg_get_wal_records_info pg_get_wal_records_info_till_end_of_wal pg_get_wal_stats pg_get_wal_stats_till_end_of_wal

SELECT pg_current_wal_lsn(),now();
insert into ta values(1);
SELECT pg_current_wal_lsn(),now();
select start_lsn, end_lsn, prev_lsn, xid, resource_manager, record_type, record_length, main_data_length, fpi_length, description::varchar(50), block_ref from pg_get_wal_records_info_till_end_of_wal('0/1905030') ;

select * from pg_get_wal_stats_till_end_of_wal('0/1905030', true);

可以调式pg_get_wal_record_info获取wal文件的格式信息

typedef struct XLogPageHeaderData
{
    uint16        xlp_magic;        /* magic value for correctness checks */
    uint16        xlp_info;        /* flag bits, see below */
    TimeLineID    xlp_tli;        /* TimeLineID of first record on page */
    XLogRecPtr    xlp_pageaddr;    /* XLOG address of this page */

    /*
     * When there is not enough space on current page for whole record, we
     * continue on the next page.  xlp_rem_len is the number of bytes
     * remaining from a previous page; it tracks xl_tot_len in the initial
     * header.  Note that the continuation data isn't necessarily aligned.
     */
    uint32        xlp_rem_len;    /* total len of remaining data for record */
} XLogPageHeaderData;

typedef struct XLogLongPageHeaderData
{
    XLogPageHeaderData std;        /* standard header fields */
    uint64        xlp_sysid;        /* system identifier from pg_control */
    uint32        xlp_seg_size;    /* just as a cross-check */
    uint32        xlp_xlog_blcksz;    /* just as a cross-check */
} XLogLongPageHeaderData;

typedef struct XLogRecord
{
    uint32        xl_tot_len;        /* total len of entire record */
    TransactionId xl_xid;        /* xact id */
    XLogRecPtr    xl_prev;        /* ptr to previous record in log */
    uint8        xl_info;        /* flag bits, see below */
    RmgrId        xl_rmid;        /* resource manager for this record */
    /* 2 bytes of padding here, initialize to zero */
    pg_crc32c    xl_crc;            /* CRC for this record */

    /* XLogRecordBlockHeaders and XLogRecordDataHeader follow, no padding */

} XLogRecord;

XLogLongPageHeaderData 文件最开始的一个page的head，除了常规head之外，还记录sysis和其他配置信息，主要是为了检测wal文件和平台是否兼容
XLogPageHeaderData 常规header，记录page的位置以及page信息等
The logical and physical structures of the WAL (transaction log)
The internal layout of WAL data
Writing of WAL data
WAL writer process
The checkpoint processing
The database recovery processing
Managing WAL segment files
Continuous archiving

可见性与隔离级别

https://smartkeyerror.com/PostgreSQL-MVCC-01

mvcc

pg使用直接数据插入，使用快照判断数据的可见性

快照不同的隔离级别，获取事务快照的机制不一样 * RC每次都会重新获取，所以其他事务或者操作只要改变事务状态，都会被rc事务感知到， * RR之上的只会在开始的时候获取一次，所以其他事务在一定程度上对当前事务是不可见的，可以设置不同的隔离级别，然后在事务内使用select txid_current_snapshot();观察快照信息 * 所以后端的事务可见性的判别机制是一样的，只需要限制快照信息即可 undo log mysql的innodb，oracle使用此机制

http://postgres.cn/docs/14/pageinspect.html

文章收藏

作者：henry liang  
链接：https://www.zhihu.com/question/449949351/answer/2692285376  
来源：知乎

数据库研究群体主要关注的是在单个主机的情况下，多个并发事务同时操作的情况下，如果保证数据库系统中数据项的一致性，包括：物理上数据不被破坏，数据的约束（唯一性约束，引用约束），或者业务约束（x + y == 10) 不被破坏。
分布式系统主要关注在跨网络相互连接，且数据有多副本复制的集群中，对于逻辑上单个数据项（可能有多个物理副本）的操作，能否和单机系统中对于单个数据项操作的效果一样，始终看到正确的符合操作顺序的数据结果。

https://www.cnblogs.com/three-fighter/p/15293310.html https://www.zhihu.com/question/449949351 分布式事务，理论与实践

分布式一致性

https://jepsen.io/consistency

事务的AICD和分布式的C是完全不一致的东西，事务的C要求的是事务的一致性约束不能被破坏，而分布式事务的C则是对系统整体正确性的描述，例如修改一个数据成功，且没有违背事务一致性，但是数据没有立刻同步到其他节点，导致分布式一致性被破坏

分布式数据库中多副本的同步，需要确保一致性，需要一定的约束规则，不用角度的约束规则，可以理解为不同程度的一致性
- 强一致性，任何读写都可以确保得到的是最新的数据，简而言之，所有的读写都是原子性，不存在中间状态
- 弱一致性
  - 最终一致性，不能确保数据写下之后立刻得到最新的数据，但是保证一段时间之后，数据对所有节点是同步的，不过此时间不确定
  - 读写一致性，在某节点写了数据，但是自己读的时候是从另一节点读取的，但是数据尚未同步，导致读到老的数据，此时应该限定读取节点，或者使用其他机制保证自己的读写是一致的
  - 单调一致性，类似读写一致性，后面的读操作没有读到之前读的数据，可能是不同的节点读的结果
  - 因果一致性，相同key的数据，应当保证顺序和实际的操作顺序是一致的，因为不同的操作之间，具有因果关系，
网络通信时间不一致，实际的执行发出时间，执行时间，和结果的接收时间不能单纯的确定先后，实际的事件存在重叠现象
主流分布式理论
- CAP理论，一致性，可用性，分区容错性三者最多只能支持两个，且由于P问题的客观存在，所以不能一定确保P，最多只能在CA中二选一
- BASE理论，BA为基本可用，S为软状态，即中间状态，E为最终一致性，他认为，强一致性无法达到的情况下的，可以在一定程度上允许最终一致性即可

强一制性是最终的追求，但是实际上可以进行一定的妥协，就像事务的不同隔离级别，大多数场景只要求可重复读即可

当前绝大多数分布式系统默认支持的最终一致性
即使无法做到强一致性（Strong consistency），但每个应用都可以根据自身的业务特点，采用适当的方式来使系统达到最终一致性（Eventual consistency）。

分布式一致性的核心是事件的先后顺序，可以想下单机数据库的顺序保证，一般都是提供一个单调递增的事务号

TSO，Timestamp Oracle，中心授时服务，由于是中心化的，所以肯定存在单点问题，但是也是由于中心化，所以可以在确保线性一致性，所以当前大部分数据库使用的是TSO，例如polarDB，TIDB等
true time，spanner为了实现数据库的全球部署，并且为了保证线性一致性，使用原子钟加GPS实现误差仅为7ms的时间戳和commit waite机制，但是需要硬件的配合，所以貌似只此一家
NTP，软同步，做不到true time，那就尽量的避免误差过大，毕竟即使是true time，也还是有7ms的误差
混合时钟，CRDB的解决方案，在软同步的基础上使用消息传递的机制进行事件顺序同步，只要有消息交互，则可以保证先后顺序
各种优化机制

中心化的授时机制和true time，可以保证线性一致性，但是TSO有单点问题，true time需要硬件支持。退而求其次的混合时钟，个人理解是使用事件之间消息传递机制来保证事件的先后顺序，这隐含一个必要条件就是需要是事件之间具有因果关系，所以 CRDB能做到因果一致性，对于不相干的key，则无法保证事件顺序。

https://github.com/xitu/gold-miner/blob/master/TODO/postgres-atomicity.md

快照		
    改造快照数据结构				
            新增全局时间戳、prepare列表等等						
						改造视图、函数						
		改造申请快照的接口				
            添加获取全局时间戳的接口						
						删除目前的全局活跃列表的处理						
						调整RecentGlobalXmin的更新逻辑，涉及Vacuum						
		改造可见性判断逻辑				
            调整快照以start_ts和commit_ts判断的逻辑						
						所有的判断接口有HeapTupleSatisfiesMVCC等8个都需要改造						
		改造commit_ts日志				
            默认要开启commit_ts，且不允许关闭						
						梳理一下目前commit_ts的功能和antdb分布式是否适配，从没启用过，可能本来功能就有缺陷						
						吕亚宁建议不修改tuple的存储结构，每次都从cts日志读取。那高并发下，应该会有锁争用的情况，需要优化

事务知识简记

事务基础 #

PG事务 #

pg高链接数导致tps下降 1|2 #

无锁算法提交事务，减少proc加锁时间，提升并发 #

内存屏障 #

实际案例： #

事务实现框架 #

快照 #

WAL #

[test] pg_waldump调试和pg_walinspect插件 #

可见性与隔离级别 #

文章收藏 #

分布式一致性 #