并发控制总结

PostgreSQL中的事务隔离等级

隔离等级	脏读	不可重复读	幻读	串行化异常
读已提交	不可能	可能	可能	可能
可重复读[1]	不可能	不可能	PG中不可能，见5.7.2小节 但ANSI SQL中可能	可能
可串行化	不可能	不可能	不可能	不可能

read-uncommit

脏读：不判断元组可见性，只要存在就读。这个比较非主流，一般没有数据库会支持这个级别，也没这种需求。

read-commit

提交读：在每次执行SQL语句之前，做一次Snapshot，保证语句执行过程中可见性是一致的，但同一个事务语句与语句之前的Snapshot可能不一样。

repeatable-read

可重读：在事务执行第一条语句时，做一次Snapshot，后面执行的所有语句都使用这个Snapshot，保证事务执行过程中可见性是一致的。

serializable

串行化：事务之前串行执行，这个也就不用考虑可见性问题了，串行是由锁来实现。

元组结构

• t_xmin保存插入此元组的事务的txid。
• t_xmax保存删除或更新此元组的事务的txid。如果尚未删除或更新此元组，则t_xmax设置为0，即无效。
• t_cid保存命令标识（command id, cid），cid意思是在当前事务中，执行当前命令之前执行了多少SQL命令，从零开始计数。例如，假设我们在单个事务中执行了三条INSERT命令BEGIN;INSERT;INSERT;INSERT;COMMIT;。如果第一条命令插入此元组，则该元组的t_cid会被设置为0。如果第二条命令插入此元组，则其t_cid会被设置为1，依此类推。
• t_ctid保存着指向自身或新元组的元组标识符（tid）。如第1.3节中所述，tid用于标识表中的元组。在更新该元组时，其t_ctid会指向新版本的元组；否则t_ctid会指向自己。

空闲空间映射

表和索引都有各自的FSM。 它记录着对应表或者索引文件中每个页面可用空间空间容量的信息

FSM并不记录页面空闲空间的具体大小，而是记录空闲空间范围。比如0代表0~31；255代表8164~8192。

• 一个页空闲空间太小（0~31字节），则不会在这个页上增加数据。
• 申请的空闲空间太大（8164~8192字节），则会直接分配新页面。

可见性

快照（事务开启时，会产生一个快照）

PostgreSQL会为每个事务生成一个事务ID，即xid。xid是一个32位的整数，按照事务开启的先后顺序递增，所以通过xid就可以判断事务开启的先后顺序。PostgreSQL会在clog记录，所以通过clog也可以判断事务是否提交。通过xid和clog可以很方便的判断事务何时开启以及是否提交。此外PostgreSQL还维护了全局的活跃事务数组，里面存放了所有当前活跃事务的xid。所以当一个事务开启时，我们可以很方便的获取一下重要的信息，这些信息就可以组成一个快照：

• xmin

  最早仍然活跃的事务的txid。所有比它更早的事务txid < xmin要么已经提交并可见，要么已经回滚并生成死元组。

• xmax

  第一个尚未分配的txid。所有txid ≥ xmax的事务在此快照获取时尚未启动，因而其结果对当前事务不可见。

• xip_list

  获取快照时活跃事务的txid列表。该列表仅包括xmin与xmax之间的txid。

  例如，在快照100:104:100,102中，xmin是100，xmax是104，而xip_list为100,102。

事务xid的可见性判断

设某事务T的事务id为xid，根据上述性质，我们可以很方便的得出事务T可见性的判断流程：

1. 比较xid与xmin

​ 如果xid < xmin，则T对当前事务可见，否则执行步骤2。

2. 比较xid与xmax

​ 如果xid >= xmax，则T对当前事务不可见，否则执行步骤3。

3. 在活跃事务数组中查找xid

​ 如果xid存在于活跃事务数组，则T对当前事务不可见，否则T对当前事务可见。

对于步骤1，是一个优化步骤，去掉步骤1，不会出现任何正确性问题，只不过对于xid < xmin的事务都需要到在步骤3中通过遍历活跃数组的方式来判断可见性，这样性能会比较低。步骤2必须有，如果当前事务开启后，又开启事务，就算新事务是活跃的，快照中活跃事务列表也没有，因此会误将新事务当做不活跃的。

元组可见性

每条元组上记录了两个xid，t_xmin和t_xmax，注意这里的t_xmin、t_xmax和前面事务可见性的xmin、xmax完全不是一回事！！在元组中，t_xmin表示对该元组执行插入操作的事务的xid，t_xmax表示对该元组执行删除操作的事务的xid，如果元组没有被删除t_xmax为0。在PostgreSQL中，update操作删除+插入操作，先删除原始的元组，再插入新的元组，所以t_xmin和t_xmax逻辑也完全适用于更新操作。

• 如果某元组的t_xmin对当前事务不可见，那么该元组对当前事务不可见。

  ​ 这是显而易见的，t_xmin不可见意味着，插入这条元组的事务对当前事务不可见，自然该元组对当前事务也就不可见。

• 如果元组的t_xmax对当前事务可见，那么该元组对当前事务不可见。

  ​ t_xmax对当前事务可见，就意味着删除对当前事务可见，删除既然可见，就说明了对当前事务而言，该元组已经被删除了，元组既然被删除自然也就不可见了。

可见性的两个要素：获取快照前提交、最新版本

CLOG（Commit Log）

• 分配于在共享内存中；
• 记录着每个事务号的事务状态（IN_PROGRESS，COMMITTED，ABORTED和SUB_COMMITTED）；
• 10版本中，pg_clog被重命名为pg_xact；
• 当PostgreSQL关机或执行存档过程时，clog数据会写入至pg_clog子目录下的文件中，文件的最大尺寸为256 KB，超过256KB，会新建一个文件；
• 当更新pg_database.datfrozenxid时，PostgreSQL会尝试删除不必要的clog文件，例如clog文件0002中包含最小的pg_database.datfrozenxid，则可以删除旧文件（0000和0001）

WAL预写式日志

WAL（Write Ahead Logging）：XLOG先于数据落盘，事务相关的XLOG全部落盘事务才能提交。当插入、删除、提交等变更动作发生时，PostgreSQL会将XLOG记录写入内存中的WAL缓冲区（WAL Buffer）。当事务提交或中止之前，它们会被立即写入持久存储上的WAL段文件（WAL segment file）中。

XLOG记录的日志序列号（Log Sequence Number, LSN）标识了该记录在事务日志中的位置，记录的LSN被用作XLOG记录的唯一标识符。

XLOG、事务日志、WAL段文件

• XLOG：记录插入、删除、提交等变更动作。
• 事务日志：PostgreSQL将XLOG记录写入事务日志
• WAL段文件：PostgreSQL中的事务日志实际上默认被划分为16M大小的一系列文件，这些文件被称作WAL段（WAL Segment）。

WAL段文件的内部布局

一个WAL段文件大小默认为16MB，并在内部划分为大小为8192字节（8KB）的页面。第一个页包含了由XLogLongPageHeaderData 定义的首部数据，其他的页包含了由XLogPageHeaderData 定义的首部数据。每页在首部数据之后，紧接着就是以降序写入的XLOG记录

​ 图 1 WAL段文件内部布局

XLOG Record的内部布局

一条XLOG Record就是一个XLOG记录。它由两部分组成：XLogRecord（通用首部部分）+ XLOG record data（特定数据部分）。

• XLogRecord（通用首部部分）

  typedef struct XLogRecord
  {
  	uint32 xl_tot_len; /* 整条记录的全长 */
  	TransactionId xl_xid; /* 事务ID */
  	uint32 xl_len; /* 资源管理器的数据长度 */
  	uint8 xl_info; /* 标记位，如下所示 */
  	RmgrId xl_rmid; /* 本记录的资源管理器 */
  	/* 这里有2字节的填充，初始化为0 */
  	XLogRecPtr xl_prev; /* 在日志中指向先前记录的指针 */
  	pg_crc32 xl_crc; /* 本记录的CRC */
  } XLogRecord;
  

  xl_rmid 与xl_info 都是与资源管理器（resource manager）相关的变量。

  例如：

  • 如果发起的是INSERT 语句，则其相应XLOG记录首部中的变量xl_rmid 与xl_info 会相应地被设置为RM_HEAP 与XLOG_HEAP_INSERT 。当恢复数据库集簇时，就会按照xl_info 选用资源管理器RM_HEAP 的函数heap_xlog_insert() 来重放当前XLOG记录。
  • 当事务提交时，相应XLOG记录首部的变量xl_rmid 与xl_info 会被相应地设置为RM_XACT 与XLOG_XACT_COMMIT 。当数据库恢复时， RM_XACT 的xact_redo_commit() 就会执行本记录的重放。

• XLOG record data（特定数据部分）

  XLOG记录的数据部分可以被划分为两个部分：首部（与XLogRecord不同，这是数据部分的首部）与数据。

  数据部分则由零或多个区块数据与零或一个主数据组成，区块数据与XLogRecordBlockHeader(s)对应，而**主数据（main data）**则与XLogRecordDataHeader对应。

typedef struct XLogRecordBlockHeader
{
    uint8        id;                /* 块引用 ID */
    uint8        fork_flags;        /* 分支标号放在fork_flags的低4位中，高位用于标记位  */
    uint16       data_length;    /* 荷载字节数（不包括页面镜像） */

    /* 如果设置 BKPBLOCK_HAS_IMAGE, 紧接一个XLogRecordBlockImageHeader结构 */
    /* 如果未设置 BKPBLOCK_SAME_REL, 紧接着一个RelFileNode结构 */
    /* 紧接着区块号码 */
} XLogRecordBlockHeader;
/* 这个结构体用于表明我们的XLOG在重启恢复时会作用于哪个表空间、哪个数据库、哪张表 */
typedef struct RelFileNode
{
	Oid			spcNode;		/* tablespace */
	Oid			dbNode;			/* database */
	Oid			relNode;		/* relation */
} RelFileNode;
/* XLogRecordDataHeaderShort/Long 被用于本记录的“主数据”部分。如果数据的长度小于256字节
 * 则会使用Short版本的格式，即使用单个字节来保存长度，否则会使用长版本的格式。 */
typedef struct XLogRecordDataHeaderShort
{
    uint8        id;                /* XLR_BLOCK_ID_DATA_SHORT */
    uint8        data_length;    /* 载荷字节数目 */
} XLogRecordDataHeaderShort;

typedef struct XLogRecordDataHeaderLong
{
    uint8        id;                /* XLR_BLOCK_ID_DATA_LONG */
    /* 紧随其后的是uint32类型的data_length, 未对齐 */
} XLogRecordDataHeaderLong;

• xl_heap_header

xl_heap_header是HeapTupleHeaderData,也就是元组头的一个简化版。不将整个HeapTupleHeaderData都写入XLOG，是因为HeapTupleHeaderData中的很多信息都可以重构或者不需要重构。所以只用存放一些必要的信息，而xl_heap_header就用于记录这些必要信息。

xl_heap_header结构体大小为5个字节。

typedef struct xl_heap_header
{
	uint16		t_infomask2;
	uint16		t_infomask;
	uint8		t_hoff;
} xl_heap_header;

• 再往后是元组具体信息，与xl_heap_header组成元组整体信息，这部分数据和插入的时候写入到数据页中的数据完全一样。

• xl_heap_insert

  这个结构体表明了该元组所在的物理块中的偏移，定义如下：

  typedef struct xl_heap_insert
  {
  	OffsetNumber offnum;		/* inserted tuple's offset */
  	uint8		flags;
  
  	/* xl_heap_header & TUPLE DATA in backup block 0 */
  } xl_heap_insert;
  

Reference:
https://www.interdb.jp/pg