一、 MVCC常用实现方法
一般MVCC有2种实现方法：
- 写新数据时，把旧数据快照存入其他位置（如oracle的回滚段、sqlserver的tempdb）。当读数据时，读的是快照的旧数据。
- 写新数据时，旧数据不删除，直接插入新数据。PostgreSQL就是使用的这种实现方法。
1. PostgreSQL的MVCC实现方式优缺点
优点
- 无论事务进行了多少操作，事务回滚可以立即完成
- 数据可以进行很多更新，不必像Oracle和MySQL的Innodb引擎需要保证回滚段不会被用完，也不会经常遇到“ORA-1555”错误的困扰
缺点
- 旧版本的数据需要清理。当然，PostgreSQL 9.x版本中已经增加了自动清理的辅助进程来定期清理
- 旧版本的数据可能会导致查询需要扫描的数据块增多，从而导致查询变慢
2. PostgreSQL中MVCC的实现思路
为了实现MVCC机制，必须要：
- 定义多版本的数据——使用元组头部信息的字段来标示元组的版本号
- 定义数据的有效性、可见性、可更新性——通过当前的事务快照和对应元组的版本号判断
- 实现不同的数据库隔离级别——通过在不同时机获取快照实现
下面我们分别来看，首先了解一些基本概念。
二、 基本概念
1. 事务标识
当事务开始（执行begin第一条命令时），事务管理器会为该事务分配一个txid（transaction id）作为唯一标识符。txid是一个32位无符号整数，取值空间大小约42亿（2^32-1）。
txid可通过txid_current()函数获取
testdb=# BEGIN;BEGINtestdb=# SELECT txid_current(); txid_current -------------- 100(1 row)三个特殊的txid
- 0：InvalidTransactionId，表示无效的事务ID
- 1：BootstrapTransactionId，表示系统表初始化时的事务ID，比任何普通的事务ID都旧。
- 2：FrozenTransactionId，冻结的事务ID，比任何普通的事务ID都旧。
- 大于2的事务ID都是普通的事务ID。
事务间的可见性
txid间可以相互比较大小，任何事务只可见txid＜其自身txid的事务修改结果。但txid并不是无限的，当42亿数据用尽之后又应该如何判断可见性？这个问题我们下篇再讨论。
2. 元组结构
pg中元组由三部分组成——元组头结点、空值位图、用户数据。
官方文档中解释如下https://www.postgresql.org/docs/9.6/storage-page-layout.html
| Field | Type | Length | Description |
|---|---|---|---|
| t_xmin | TransactionId | 4 bytes | insert XID stamp |
| t_xmax | TransactionId | 4 bytes | delete XID stamp |
| t_cid | CommandId | 4 bytes | insert and/or delete CID stamp (overlays with t_xvac) |
| t_xvac | TransactionId | 4 bytes | XID for VACUUM operation moving a row version |
| t_ctid | ItemPointerData | 6 bytes | current TID of this or newer row version |
| t_infomask2 | uint16 | 2 bytes | number of attributes, plus various flag bits |
| t_infomask | uint16 | 2 bytes | various flag bits |
| t_hoff | uint8 | 1 byte | offset to user data |
其中与MVCC相关的重要信息为：
- t_xmin：保存插入该元组的事务txid（该元组由哪个事务插入）
- t_xmax：保存更新或删除该元组的事务txid。若该元组尚未被删除或更新，则t_xmax=0，即invalid
- t_cid：保存命令标识（command id,cid），指在该事务中，执行当前命令之前还执行过几条sql命令（从0开始计算）
- t_ctid：一个指针，保存指向自身或新元组的元组的标识符（tid）。
当更新该元组时，t_ctid会指向新版本元组。若元组被更新多次，则该元组会存在多个版本，各版本通过t_cid串联，形成一个版本链。通过这个版本链，可以找到最新的版本。t_ctid是一个二元组（页号,页内偏移量），其中页号从0开始，页内偏移量从1开始。
pg提供了pageinspect插件，可查看指定表对应的page header内容
testdb=# CREATE EXTENSION pageinspect;CREATE EXTENSIONtestdb=# CREATE TABLE tbl (data text);CREATE TABLEtestdb=# INSERT INTO tbl VALUES('A');INSERT 0 1testdb=# 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)(1 row)三、 元组的增、删、改
1. 插入
插入操作最简单，直接将新元组插入目标表中页面即可
插入操作的过程和结果分析：
- t_xmin 被设置为99，表示插入该元组的txid
- t_xmax 被设置为0，因为该元组还未被更新或删除过
- t_cid 被设置为0，因为这是该事务的第一条命令
- t_ctid 指向自身，被设置为（0,1），表示该元组位于0号page的第1个位置上
2. 删除
pg的删除只是将目标元组在逻辑上标为删除（将t_xmax设为执行delete命令的事务txid），实际该元组依然存在于数据库的存储页面，直至该元组被清理进程清理掉。
删除操作的过程和结果分析：
- t_xmin 不变，表示插入该元组的txid
- t_xmax 被设置为111，即删除该元组的txid
- t_cid 被设置为0，因为这是该事务的第一条命令
- t_ctid 指向自身，被设置为（0,1），表示该元组位于0号page的第1个位置上
当txid=111的事务提交时，tuple_1就不再需要了，称为dead tuple。但是这个tuple依然残留在页面上， 随着数据库的运行，这种死元组越来越多，它们会在VACUUM时最终被清理掉。
3. 更新
pg不会直接修改数据，而是将目标元组标记为删除，并插入一条新元组，同时修改t_ctid执行新版本元组。
更新操作的过程和结果分析
首先看第一条update：
Tuple_1
- t_xmin 不变，表示插入该元组的txid
- t_xmax 被设置为100，即删除该元组的txid
- t_cid 被设置为0，因为这是该事务的第一条命令
- t_ctid 指向新版本元组，被设置为（0,2），表示新元组位于0号page的第2个位置上
Tuple_2
- t_xmin 被设置为100，表示插入该元组的txid
- t_xmax 被设置为0，因为该元组还未被更新或删除过
- t_cid 被设置为0，因为这是该事务的第一条命令（虽然又删又增，实际都是一条update操作的）
- t_ctid 指向自身，被设置为（0,2），表示该元组位于0号page的第2个位置上
再看第二条update：
Tuple_2
- t_xmin 不变，表示插入该元组的txid
- t_xmax 被设置为100，即删除该元组的txid
- t_cid 被设置为1，因为这是该事务的第二条命令
- t_ctid 指向新版本元组，被设置为（0,3），表示新元组位于0号page的第3个位置上
Tuple_3
- t_xmin 被设置为100，表示插入该元组的txid
- t_xmax 被设置为0，因为该元组还未被更新或删除过
- t_cid 被设置为1，因为这是该事务的第二条命令
- t_ctid 指向自身，被设置为（0,3），表示该元组位于0号page的第3个位置上
四、 提交日志
pg在提交日志（commit log,CLOG）中保存事务的状态。
1. 事务状态
pg定义了四种事务状态——IN_PROGRESS, COMMITTED, ABORTED和SUB_COMMITTED，其中SUB_COMMITTED状态用于子事务，此处不讨论。
#define TRANSACTION_STATUS_IN_PROGRESS 0x00#define TRANSACTION_STATUS_COMMITTED 0x01#define TRANSACTION_STATUS_ABORTED 0x02#define TRANSACTION_STATUS_SUB_COMMITTED 0x03四种事务状态仅需两个bit即可记录。以一个块8KB为例，可以存储8KB*8/2 = 32K个事务的状态。内存中缓存CLOG的buffer 大小为Min(128,Max(4,NBuffers/512))。
2. 工作原理
CLOG在逻辑上是一个数组，由共享内存中一系列8K页面组成。数组下标对应事务txid，数组内容则为事务状态：
- T1时刻：txid=200事务提交，对应状态从IN_PROGRESS改为COMMITED
- T2时刻：txid=201事务回滚，对应状态从IN_PROGRESS改为ABORTED
当需要获取事务状态时，pg调用内部函数读取CLOG返回所请求事务状态，详情参考下篇——提示位。
3. CLOG的维护
当shutdown pg或Checkpoint运行时，CLOG数据会由内存写入pg_clog（pg 10后叫pg_xact）目录中的文件。这些文件被命名为0000,0001，最大256KB。当pg启动时，会加载这些文件用于初始化CLOG。
CLOG数据会不断增长，但并非所有数据都是必要的，清理过程也会定期清理掉不再需要的CLOG页面和文件。
五、 事务快照
快照是一个很形象的词，就像拍下一张照片，记录下此刻的信息。 观察者通过快照只能获取当前时间点之前的信息，而按下快门以后的信息便无法察觉，即不可见。
类比于快照，事务快照就是存储着某个特定事务在某个特定时间段所看到的事务状态信息的数据集。
1. 快照信息
可将前面提到的事务状态归纳为2种：
- 活跃事务（active txid）：正在进行中或尚未开始的事务，其修改结果不可见
- 不活跃事务（inactive txid）：已提交或回滚的事务，若已提交则修改结果可见
通过txid_current_snapshot函数可以看到当前事务的快照信息。
testdb=# SELECT txid_current_snapshot(); txid_current_snapshot ----------------------- 100:104:100,102(1 row)快照由这样一个序列构成：xmin:xmax:xip_list
注意不要与元组的t_xmin和t_xmax弄混
- xmin：最早的状态仍为active的事务txid，所有比它更早的事务（txid<xmin），要么已提交并可见，要么已回滚并生成死元组。
- xmax：获取快照时第一个尚未分配的xid，所有txid>=xmax的事务在获取快照时尚未启动，因此其结果对当前事务不可见。
- xip_list：获取快照时，所有active事务的txid列表，该列表仅包含[xmin,xmax)范围内的活跃事务txid
‘100:100:’含义如下
- xmin=100，所以txid<100的事务均不活跃
- xmax=100，所以txid>=100的事务均活跃
- xip_list为空，表示[xmin,xmax)范围内无活跃事务
- 本事务txid=99，且已提交或已回滚
‘100:104:100,102’含义如下
- xmin=100，所以txid<100的事务均不活跃
- xmax=104，所以txid>=104的事务均活跃
- xip_list为100,102，表示[xmin,xmax)范围内100,102为活跃事务
- 本事务txid=103，且已提交或已回滚
2. 事务快照举例
pg会根据不同隔离级别设置，获取不同时刻的快照：
- 已提交读：在该事务的每条sql执行之前都会重新获取一次snapshot
- 可重复读和可串行化：该事务只在第一条sql执行之前获取一次snapshot
参考
http://www.interdb.jp/pg/pgsql05.html
http://mysql.taobao.org/monthly/2019/08/01/
http://mysql.taobao.org/monthly/2017/10/01/