深入解析 PostgreSQL 系列整理自 The Internals of PostgreSQL 等系列文章，从碎片化地阅读到体系化地学习，感觉对数据库有了更深入地了解；触类旁通，相互印证，也是有利于掌握 MySQL 等其他的关系型数据库或者 NoSQL 数据库。
深入解析 PostgreSQL 系列之并发控制与事务机制
并发控制旨在针对数据库中对事务并行的场景，保证 ACID 中的一致性（Consistency）与隔离（Isolation）。数据库技术中主流的三种并发控制技术分别是：Multi-version Concurrency Control (MVCC), Strict Two-Phase Locking (S2PL), 以及 Optimistic Concurrency Control (OCC)，每种技术也都有很多的变种。在 MVCC 中，每次写操作都会在旧的版本之上创建新的版本，并且会保留旧的版本。当某个事务需要读取数据时，数据库系统会从所有的版本中选取出符合该事务隔离级别要求的版本。MVCC 的最大优势在于读并不会阻塞写，写也不会阻塞读；而像 S2PL 这样的系统，写事务会事先获取到排他锁，从而会阻塞读事务。
PostgreSQL 以及 Oracle 等 RDBMS 实际使用了所谓的 Snapshot Isolation（SI）这个 MVCC 技术的变种。Oracle 引入了额外的 Rollback Segments，当写入新的数据时，老版本的数据会被写入到 Rollback Segment 中，随后再被覆写到实际的数据块。PostgreSQL 则是使用了相对简单的实现方式，新的数据对象会被直接插入到关联的 Table Page 中；而在读取表数据的时候，PostgreSQL 会通过可见性检测规则（Visibility Check Rules）来选择合适的版本。
SI 能够避免 ANSI SQL-92 标准中定义的三个反常现象：脏读（Dirty Reads），不可重复读（Non-Repeatable Reads）以及幻读（Phantom Reads）；在 9.1 版本后引入的 Serializable Snapshot Isolation（SSI）则能够提供真正的顺序读写的能力。
Isolation Level
Dirty Reads
Non-repeatable Read
Phantom Read
Serialization Anomaly
READ COMMITTED
Not possible
Possible
Possible
Possible
REPEATABLE READ
Not possible
Not possible
Not possible in PG; See Section 5.7.2. (Possible in ANSI SQL)
Possible
SERIALIZABLE
Not possible
Not possible
Not possible
Not possible
Tuple 结构
Transaction ID
当某个事务开启时，PostgreSQL 内置的 Transaction Manager 会为它分配唯一的 Transaction ID(txid)；txid 是 32 位无类型整型值，可以通过 txid_current() 函数来获取当前的 txid：
testdb=# BEGIN;
BEGIN
testdb=# SELECT txid_current();
txid_current
————–
100
(1 row)
PostgreSQL 还保留了三个关键 txid 值作特殊标记：0 表示无效的 txid，1 表示启动时的 txid，仅在 Database Cluster 启动时使用；2 代表了被冻结的（Frozen）txid，用于在序列化事务时候使用。PostgreSQL 选择数值类型作为 txid，也是为了方便进行比较；对于 txid 值为 100 的事务而言，所有小于 100 的事务是发生在过去的，可见的；而所有大于 100 的事务，是发生在未来，即不可见的。
鉴于实际系统中的 txid 数目的需要可能会超过最大值，PostgreSQL 实际是将这些 txid 作为环来看待。
HeapTupleHeaderData
Table Pages 中的 Heap Tuples 往往包含三个部分：HeapTupleHeaderData 结构，NULL bitmap 以及用户数据。
其中 HeapTupleHeaderData 与事物处理强相关的属性有：
(TransactionId)t_xmin: 存放插入该 Tuple 时的 txid
(TransactionId)t_xmax: 存放删除或者更新该 Tuple 时的 txid，如果还没更新或者删除，那么置 0，表示无效
(CommandId)t_cid: 存放 Command ID，即 创建该 Tuple 的命令在该事务内执行的所有 SQL 命令中的编号；譬如 BEGIN; INSERT; INSERT; INSERT; COMMIT; 这个事务，如果是首个 INSERT 命令创建的 Tuple，那么其 t_cid 值为 0，第二个就是 1
(ItemPointerData)t_ctid: 当某个 Tuple 更新时，该值就指向新创建的 Tuple，否则指向自己
Tuple 的插入、删除与更新
如上所述，Table Pages 中的 Tuples 呈如下布局：
插入
在执行插入操作时，PostgreSQL 会直接将某个新的 Tuple 插入到目标表的某个页中：
假如某个 txid 为 99 的事务插入了新的 Tuple，那么该 Tuple 的头域会被设置为如下值：
t_xmin 与创建该 Tuple 的事务的 txid 保持一致，即 99
t_xmax 被设置为 0，因为其还未被删除或者更新
t_cid 被设置为 0，因为该 Tuple 是由事务中的首个 Insert 命令创建的
t_ctid 被设置为了 (0, 1)，即指向了自己
testdb=# CREATE EXTENSION pageinspect;
CREATE EXTENSION
testdb=# CREATE TABLE tbl (data text);
CREATE TABLE
testdb=# INSERT INTO tbl VALUES(‘A’);
INSERT 0 1
testdb=# SELECT lp as tuple, t_xmin, t_xmax, t_field3 as t_cid, t_ctid
FROM heap_page_items(get_raw_page(‘tbl’, 0));
tuple | t_xmin | t_xmax | t_cid | t_ctid
——-+——–+——–+——-+——–
1 | 99 | 0 | 0 | (0,1)
删除
在删除操作中，目标 Tuple 会被先逻辑删除，即将 t_xmax 的值设置为当前删除该 Tuple 的事务的 txid 值。
当该事务被提交之后，PostgreSQL 会将该 Tuple 标记为 Dead Tuple，并随后在 VACUUM 处理过程中被彻底清除。
更新
在更新操作时，PostgreSQL 会首先逻辑删除最新的 Tuple，然后插入新的 Tuple：
上图所示的行被 txid 为 99 的事务插入，被 txid 为 100 的事务连续更新两次；在该事务提交之后，Tuple_2 与 Tuple_3 就会被标记为 Dead Tuples。
Free Space Map
当插入某个 Heap Tuple 或者 Index Tuple 时，PostgreSQL 使用相关表的 FSM 来决定应该选择哪个 Page 来进行具体的插入操作。每个 FSM 都存放着表或者索引文件相关的剩余空间容量的信息，可以使用如下方式查看：
testdb=# CREATE EXTENSION pg_freespacemap;
CREATE EXTENSION
testdb=# SELECT *, round(100 * avail/8192 ,2) as “freespace ratio”
FROM pg_freespace(‘accounts’);
blkno | avail | freespace ratio
——-+——-+—————–
0 | 7904 | 96.00
1 | 7520 | 91.00
2 | 7136 | 87.00
3 | 7136 | 87.00
4 | 7136 | 87.00
5 | 7136 | 87.00
….
Commit Log
PostgreSQL 使用 Commit Log，亦称 clog 来存放事务的状态；clog 存放于 Shared Memory 中，在整个事务处理的生命周期中都起到了重要的作用。PostgreSQL 定义了四种不同的事务状态：IN_PROGRESS, COMMITTED, ABORTED, 以及 SUB_COMMITTED。
Clog 有 Shared Memory 中多个 8KB 大小的页构成，其逻辑上表现为类数组结构，数组下标即是关联的事务的 txid，而值就是当前事务的状态：
如果当前的 txid 超过了当前 clog 页可承载的最大范围，那么 PostgreSQL 会自动创建新页。而在 PostgreSQL 停止或者 Checkpoint 进程运行的时候，clog 的数据会被持久化存储到 pg_xact 子目录下，以 0000，0001 依次顺序命名，单个文件的最大尺寸为 256KB。而当 PostgreSQL 重启的时候，存放在 pg_xact 目录下的文件会被重新加载到内存中。而随着 PostgreSQL 的持续运行，clog 中势必会累计很多的过时或者无用的数据，Vacuum 处理过程中同样会清除这些无用的数据。
Transaction Snapshot | 事务快照
事务快照即是存放了当前全部事务是否为激活状态信息的数据结构，PostgreSQL 内部将快照表示为简单的文本结构，xmin:xmax:xip_list’；譬如 “100”，其意味着所有 txid 小于或者等于 99 的事务是非激活状态，而大于等于 100 的事务是处在了激活状态。
testdb=# SELECT txid_current_snapshot();
txid_current_snapshot
———————–
100:104:100,102
(1 row)
xmin: 最早的仍处在激活状态的 txid，所有更早之前的事务要么处于被提交之后的可见态，要么就是被回滚之后的假死态。
xmax: 首个至今仍未分配的事务编号，所有 txid 大于或者等于该值的事务，相对于该快照归属的事务都是尚未发生的，因此是不可见的。
xip_list: 快照时候处于激活状态的 txids，仅会包含在 xmin 与 xmax 之间的 txids。
以 100:104:100,102 为例，其示意图如下所示：
事务快照主要由事务管理器（Transaction Manager）提供，在 READ COMMITTED 这个隔离级别，无论是否有 SQL 命令执行，该事务都会被分配到某个快照；而对于 REPEATABLE READ 或者 SERIALIZABLE 隔离级别的事务而言，仅当首个 SQL 语句被执行的时候，才会被分配到某个事务快照用于进行可见性检测。事务快照的意义在于，当某个快照进行可见性判断时，无论目标事务是否已经被提交或者放弃，只要他在快照中被标记为 Active，那么其就会被当做 IN_PROGRESS 状态的事务来处理。
事务管理器始终保存有关当前运行的事务的信息。假设三个事务一个接一个地开始，并且 Transaction_A 和 Transaction_B 的隔离级别是 READ COMMITTED，Transaction_C 的隔离级别是 REPEATABLE READ。
T1：
Transaction_A 启动并执行第一个 SELECT 命令。执行第一个命令时，Transaction_A 请求此刻的 txid 和快照。在这种情况下，事务管理器分配 txid 200，并返回事务快照 ’200：200：’。
T2：
Transaction_B 启动并执行第一个 SELECT 命令。事务管理器分配 txid 201，并返回事务快照 ’200：200：’，因为 Transaction_A（txid 200）正在进行中。因此，无法从 Transaction_B 中看到 Transaction_A。
T3：
Transaction_C 启动并执行第一个 SELECT 命令。事务管理器分配 txid 202，并返回事务快照 ’200：200：’，因此，Transaction_A 和 Transaction_B 不能从 Transaction_C 中看到。
T4：
Transaction_A 已提交。事务管理器删除有关此事务的信息。
T5：
Transaction_B 和 Transaction_C 执行各自的 SELECT 命令。
Transaction_B 需要事务快照，因为它处于 READ COMMITTED 级别。在这种情况下，Transaction_B 获取新快照 ’201：201：’，因为 Transaction_A（txid 200）已提交。因此，Transaction_B 不再是 Transaction_B 中不可见的。
Transaction_C 不需要事务快照，因为它处于 REPEATABLE READ 级别并使用获得的快照，即 ’200：200：’。因此，Transaction_A 仍然是 Transaction_C 不可见的。
Visibility Check | 可见性检测
Rules | 可见性检测规则
可见性检测的规则用于根据 Tuple 的 t_xmin 与 t_xmax，clog 以及自身分配到的事务快照来决定某个 Tuple 相对于某个事务是否可见。
t_xmin 对应事务的状态为 ABORTED
当某个 Tuple 的 t_xmin 值对应的事务的状态为 ABORTED 时候，该 Tuple 永远是不可见的：
/* t_xmin status = ABORTED */
// Rule 1: If Status(t_xmin) = ABORTED ⇒ Invisible
Rule 1: IF t_xmin status is ‘ABORTED’ THEN
RETURN ‘Invisible’
END IF
t_xmin 对应事务的状态为 IN_PROGRESS
对于非插入该 Tuple 的事务之外的其他事务关联的 Tuple 而言，该 Tuple 永远是不可见的；仅对于与该 Tuple 同属一事务的 Tuple 可见（此时该 Tuple 未被删除或者更新的）。
/* t_xmin status = IN_PROGRESS */
IF t_xmin status is ‘IN_PROGRESS’ THEN
IF t_xmin = current_txid THEN
// Rule 2: If Status(t_xmin) = IN_PROGRESS ∧ t_xmin = current_txid ∧ t_xmax = INVAILD ⇒ Visible
Rule 2: IF t_xmax = INVALID THEN
RETURN ‘Visible’
// Rule 3: If Status(t_xmin) = IN_PROGRESS ∧ t_xmin = current_txid ∧ t_xmax ≠ INVAILD ⇒ Invisible
Rule 3: ELSE /* this tuple has been deleted or updated by the current transaction itself. */
RETURN ‘Invisible’
END IF
// Rule 4: If Status(t_xmin) = IN_PROGRESS ∧ t_xmin ≠ current_txid ⇒ Invisible
Rule 4: ELSE /* t_xmin ≠ current_txid */
RETURN ‘Invisible’
END IF
END IF
t_xmin 对应事务的状态为 COMMITTED
此时该 Tuple 在大部分情况下都是可见的，除了该 Tuple 被更新或者删除。
/* t_xmin status = COMMITTED */
IF t_xmin status is ‘COMMITTED’ THEN
// If Status(t_xmin) = COMMITTED ∧ Snapshot(t_xmin) = active ⇒ Invisible
Rule 5: IF t_xmin is active in the obtained transaction snapshot THEN
RETURN ‘Invisible’
// If Status(t_xmin) = COMMITTED ∧ (t_xmax = INVALID ∨ Status(t_xmax) = ABORTED) ⇒ Visible
Rule 6: ELSE IF t_xmax = INVALID OR status of t_xmax is ‘ABORTED’ THEN
RETURN ‘Visible’
ELSE IF t_xmax status is ‘IN_PROGRESS’ THEN
// If Status(t_xmin) = COMMITTED ∧ Status(t_xmax) = IN_PROGRESS ∧ t_xmax = current_txid ⇒ Invisible
Rule 7: IF t_xmax = current_txid THEN
RETURN ‘Invisible’
// If Status(t_xmin) = COMMITTED ∧ Status(t_xmax) = IN_PROGRESS ∧ t_xmax ≠ current_txid ⇒ Visible
Rule 8: ELSE /* t_xmax ≠ current_txid */
RETURN ‘Visible’
END IF
ELSE IF t_xmax status is ‘COMMITTED’ THEN
// If Status(t_xmin) = COMMITTED ∧ Status(t_xmax) = COMMITTED ∧ Snapshot(t_xmax) = active ⇒ Visible
Rule 9: IF t_xmax is active in the obtained transaction snapshot THEN
RETURN ‘Visible’
// If Status(t_xmin) = COMMITTED ∧ Status(t_xmax) = COMMITTED ∧ Snapshot(t_xmax) ≠ active ⇒ Invisible
Rule 10: ELSE
RETURN ‘Invisible’
END IF
END IF
END IF
可见性检测流程
以简单的双事务更新与查询为例：
上图中 txid 200 的事务的隔离级别是 READ COMMITED，txid 201 的隔离级别为 READ COMMITED 或者 REPEATABLE READ。
当在 T3 时刻执行 SELECT 命令时：
根据 Rule 6，此时仅有 Tuple_1 是处于可见状态：
# Rule6(Tuple_1) ⇒ Status(t_xmin:199) = COMMITTED ∧ t_xmax = INVALID ⇒ Visible
testdb=# — txid 200
testdb=# SELECT * FROM tbl;
name
——–
Jekyll
(1 row)
testdb=# — txid 201
testdb=# SELECT * FROM tbl;
name
——–
Jekyll
(1 row)
当在 T5 时刻执行 SELECT 命令时：
对于 txid 200 的事务而言，根据 Rule 7 与 Rule 2 可知，Tuple_1 可见而 Tuple_2 不可见：
# Rule7(Tuple_1): Status(t_xmin:199) = COMMITTED ∧ Status(t_xmax:200) = IN_PROGRESS ∧ t_xmax:200 = current_txid:200 ⇒ Invisible
# Rule2(Tuple_2): Status(t_xmin:200) = IN_PROGRESS ∧ t_xmin:200 = current_txid:200 ∧ t_xmax = INVAILD ⇒ Visible
testdb=# — txid 200
testdb=# SELECT * FROM tbl;
name
——
Hyde
(1 row)
而对于 txid 201 的事务而言，Tuple_1 是可见的，Tuple_2 是不可见的：
# Rule8(Tuple_1): Status(t_xmin:199) = COMMITTED ∧ Status(t_xmax:200) = IN_PROGRESS ∧ t_xmax:200 ≠ current_txid:201 ⇒ Visible
# Rule4(Tuple_2): Status(t_xmin:200) = IN_PROGRESS ∧ t_xmin:200 ≠ current_txid:201 ⇒ Invisible
testdb=# — txid 201
testdb=# SELECT * FROM tbl;
name
——–
Jekyll
(1 row)
当在 T7 时刻执行 SELECT 命令时：
如果此时 txid 201 的事务处于 READ COMMITED 的隔离级别，那么 txid 200 会被当做 COMMITTED 来处理，因为此时获取到的事务快照是 201:201:，因此 Tuple_1 是不可见的，而 Tuple_2 是可见的：
# Rule10(Tuple_1): Status(t_xmin:199) = COMMITTED ∧ Status(t_xmax:200) = COMMITTED ∧ Snapshot(t_xmax:200) ≠ active ⇒ Invisible
# Rule6(Tuple_2): Status(t_xmin:200) = COMMITTED ∧ t_xmax = INVALID ⇒ Visible
testdb=# — txid 201 (READ COMMITTED)
testdb=# SELECT * FROM tbl;
name
——
Hyde
(1 row)
如果此时 txid 201 的事务处于 REPEATABLE READ 的隔离级别，此时获取到的事务快照还是 200:200:，那么 txid 200 的事务必须被当做 IN_PROGRESS 状态来处理；因此此时 Tuple_1 是可见的，而 Tuple_2 是不可见的：
# Rule9(Tuple_1): Status(t_xmin:199) = COMMITTED ∧ Status(t_xmax:200) = COMMITTED ∧ Snapshot(t_xmax:200) = active ⇒ Visible
# Rule5(Tuple_2): Status(t_xmin:200) = COMMITTED ∧ Snapshot(t_xmin:200) = active ⇒ Invisible
testdb=# — txid 201 (REPEATABLE READ)
testdb=# SELECT * FROM tbl;
name
——–
Jekyll
(1 row)
Preventing Lost Updates | 避免更新丢失
所谓的 更新丢失（Lost Update），也就是写冲突（ww-conflict），其出现在两个事务同时更新相同的行；在 PostgreSQL 中，REPEATABLE READ 与 SERIALIZABLE 这两个级别都需要规避这种异常现象。
(1) FOR each row that will be updated by this UPDATE command
(2) WHILE true
/* The First Block */
(3) IF the target row is being updated THEN
(4) WAIT for the termination of the transaction that updated the target row
(5) IF (the status of the terminated transaction is COMMITTED)
AND (the isolation level of this transaction is REPEATABLE READ or SERIALIZABLE) THEN
(6) ABORT this transaction /* First-Updater-Win */
ELSE
(7) GOTO step (2)
END IF
/* The Second Block */
(8) ELSE IF the target row has been updated by another concurrent transaction THEN
(9) IF (the isolation level of this transaction is READ COMMITTED THEN
(10) UPDATE the target row
ELSE
(11) ABORT this transaction /* First-Updater-Win */
END IF
/* The Third Block */
ELSE /* The target row is not yet modified or has been updated by a terminated transaction. */
(12) UPDATE the target row
END IF
END WHILE
END FOR
在上述流程中，UPDATE 命令会遍历每个待更新行，当发现该行正在被其他事务更新时进入等待状态直到该行被解除锁定。如果该行已经被更新，并且隔离级别为 REPEATABLE 或者 SERIALIZABLE，则放弃更新。
Being updated 意味着该行由另一个并发事务更新，并且其事务尚未终止。因为 PostgreSQL 的 SI 使用 first-updater-win 方案，在这种情况下，当前事务必须等待更新目标行的事务的终止。假设事务 Tx_A 和 Tx_B 同时运行，并且 Tx_B 尝试更新行；但是 Tx_A 已更新它并且仍在进行中，Tx_B 等待 Tx_A 的终止。在更新目标行提交的事务之后，继续当前事务的更新操作。如果当前事务处于 READ COMMITTED 级别，则将更新目标行; 否则 REPEATABLE READ 或 SERIALIZABLE，当前事务立即中止以防止丢失更新。
空间整理
PostgreSQL 的并发控制机制还依赖于以下的维护流程：
移除那些被标记为 Dead 的 Tuples 与 Index Tuples
移除 clog 中过时的部分
冻结旧的 txids
更新 FSM，VM 以及其他统计信息
首先讨论下 txid 环绕式处理的问题，假设 txid 100 的事务插入了某个 Tuple_1，则该 Tuple 对应的 t_xmin 值为 100；而后服务器又运行了许久，Tuple_1 期间并未被改变。直到 txid 为 2^31 + 101 时，对于该事务而言，其执行 SELECT 命令时，是无法看到 Tuple_1 的，因为 txid 为 100 的事务相对于其是发生在未来的，由其创建的 Tuple 自然也就是不可见的。
为了解决这个问题，PostgreSQL 引入了所谓的 frozen txid（被冻结的 txid），并且设置了 FREEZE 进程来具体处理该问题。前文提及到 txid 2 是保留值，专门表征那些被冻结的 Tuple，这些 Tuple 永远是非激活的、可见的。FREEZE 进程同样由 Vacuum 进程统一调用，它会扫描所有的表文件，将那些与当前 txid 差值超过 vacuum_freeze_min_age 定义的 Tuple 的 t_xmin 域设置为 2。在 9.4 版本之后，则是将 t_infomask 域中的 XMIN_FROZEN 位设置来表征该 Tuple 为冻结状态。
延伸阅读
如果希望深入浅出 分布式系统，分布式计算，分布式存储，数据库，操作系统，虚拟化 等内容，可以参阅 深入浅出分布式基础架构，DistributedSystem CheatSheet, Database CheatSheet, Linux CheatSheet, MySQL CheatSheet, Docker CheatSheet, Flink CheatSheet, Kafka CheatSheet 等。
如果想获取分布式系统、虚拟化调度、数据库、分布式存储、分布式计算、操作系统等领域更多资料：Docker List, Kubernetes List, Linux List, HTTP List, Distributed System List, Blockchain List, Flink List, Kafka List, Database List, MySQL List, PostgreSQL List, etc.