• 深入解析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）则能够提供真正的顺序读写的能力。

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: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为冻结状态。