PgSQL · 特性分析 · MVCC機製淺析

背景

我們在使用PostgreSQL的時候，可能會碰到表膨脹的問題（關於表膨脹可以參考之前的月報），即表的數據量並不大，但是占用的磁盤空間比較大，查詢比較慢。為什麼PostgreSQL有可能發生表膨脹呢？這是因為PostgreSQL引入了MVCC機製來保證事務的隔離性，實現數據庫的隔離級別。

在數據庫中，並發的數據庫操作會麵臨髒讀（Dirty Read）、不可重複讀（Nonrepeatable Read）、幻讀（Phantom Read）和串行化異常等問題，為了解決這些問題，在標準的SQL規範中對應定義了四種事務隔離級別：
- RU(Read uncommitted)：讀未提交
- RC(Read committed)：讀已提交
- RR(Repeatable read)：重複讀
- SERIALIZABLE(Serializable)：串行化

當前PostgreSQL已經支持了這四種標準的事務隔離級別（可以使用SET TRANSACTION語句來設置，詳見文檔），下表是PostgreSQL官方文檔上列舉的四種事務隔離級別和對應數據庫問題的關係：

Isolation Level	Dirty Read	Nonrepeatable Read	Phantom Read	Serialization Anomaly
Read uncommitted	Allowed, but not in PG	Possible	Possible	Possible
Read committed	Not possible	Possible	Possible	Possible
Repeatable read	Not possible	Not possible	Allowed, but not in PG	Possible
Serializable	Not possible	Not possible	Not possible	Not possible

需要注意的是，在PostgreSQL中：
- RU隔離級別不允許髒讀，實際上和Read committed一樣
- RR隔離級別不允許幻讀

在PostgreSQL中，為了保證事務的隔離性，實現數據庫的隔離級別，引入了MVCC(Multi-Version Concurrency Control)多版本並發控製。

MVCC常用實現方法

一般MVCC有2種實現方法：
- 寫新數據時，把舊數據轉移到一個單獨的地方，如回滾段中，其他人讀數據時，從回滾段中把舊的數據讀出來，如Oracle數據庫和MySQL中的innodb引擎。
- 寫新數據時，舊數據不刪除，而是把新數據插入。PostgreSQL就是使用的這種實現方法。

兩種方法各有利弊，相對於第一種來說，PostgreSQL的MVCC實現方式優缺點如下：
- 優點
- 無論事務進行了多少操作，事務回滾可以立即完成
- 數據可以進行很多更新，不必像Oracle和MySQL的Innodb引擎那樣需要經常保證回滾段不會被用完，也不會像oracle數據庫那樣經常遇到“ORA-1555”錯誤的困擾
- 缺點
- 舊版本的數據需要清理。當然，PostgreSQL 9.x版本中已經增加了自動清理的輔助進程來定期清理
- 舊版本的數據可能會導致查詢需要掃描的數據塊增多，從而導致查詢變慢

PostgreSQL中MVCC的具體實現

為了實現MVCC機製，必須要：
- 定義多版本的數據。在PostgreSQL中，使用元組頭部信息的字段來標示元組的版本號
- 定義數據的有效性、可見性、可更新性。在PostgreSQL中，通過當前的事務快照和對應元組的版本號來判斷該元組的有效性、可見性、可更新性
- 實現不同的數據庫隔離級別

接下來，我們會按照上麵的順序，首先介紹多版本元組的存儲結構，再介紹事務快照、數據可見性的判斷以及數據庫隔離級別的實現。

多版本元組存儲結構

為了定義MVCC 中不同版本的數據，PostgreSQL在每個元組的頭部信息HeapTupleHeaderData中引入了一些字段如下：

struct HeapTupleHeaderData
{
	union
	{
		HeapTupleFields t_heap;
		DatumTupleFields t_datum;
	}			t_choice;

	ItemPointerData t_ctid;		/* current TID of this or newer tuple (or a
								 * speculative insertion token) */

	/* Fields below here must match MinimalTupleData! */

	uint16		t_infomask2;	/* number of attributes + various flags */

	uint16		t_infomask;		/* various flag bits, see below */

	uint8		t_hoff;			/* sizeof header incl. bitmap, padding */

	/* ^ - 23 bytes - ^ */

	bits8		t_bits[FLEXIBLE_ARRAY_MEMBER];	/* bitmap of NULLs */

	/* MORE DATA FOLLOWS AT END OF STRUCT */
};

其中：
- t_heap存儲該元組的一些描述信息，下麵會具體去分析其字段
- t_ctid存儲用來記錄當前元組或新元組的物理位置
- 由塊號和塊內偏移組成
- 如果這個元組被更新，則該字段指向更新後的新元組
- 這個字段指向自己，且後麵t_heap中的xmax字段為空，就說明該元組為最新版本
- t_infomask存儲元組的xmin和xmax事務狀態，以下是t_infomask每位分別代表的含義：

#define HEAP_HASNULL        0x0001    /* has null attribute(s) */
#define HEAP_HASVARWIDTH        0x0002    /* has variable-width attribute(s) 有可變參數 */
#define HEAP_HASEXTERNAL        0x0004    /* has external stored attribute(s) */
#define HEAP_HASOID        0x0008    /* has an object-id field */
#define HEAP_XMAX_KEYSHR_LOCK    0x0010    /* xmax is a key-shared locker */
#define HEAP_COMBOCID        0x0020    /* t_cid is a combo cid */
#define HEAP_XMAX_EXCL_LOCK    0x0040    /* xmax is exclusive locker */
#define HEAP_XMAX_LOCK_ONLY    0x0080    /* xmax, if valid, is only a locker */
/* xmax is a shared locker */
#define HEAP_XMAX_SHR_LOCK  (HEAP_XMAX_EXCL_LOCK | HEAP_XMAX_KEYSHR_LOCK)
#define HEAP_LOCK_MASK    (HEAP_XMAX_SHR_LOCK | HEAP_XMAX_EXCL_LOCK | \
                         HEAP_XMAX_KEYSHR_LOCK)
#define HEAP_XMIN_COMMITTED    0x0100    /* t_xmin committed 即xmin已經提交*/
#define HEAP_XMIN_INVALID        0x0200    /* t_xmin invalid/aborted */
#define HEAP_XMIN_FROZEN        (HEAP_XMIN_COMMITTED|HEAP_XMIN_INVALID)
#define HEAP_XMAX_COMMITTED    0x0400    /* t_xmax committed即xmax已經提交*/
#define HEAP_XMAX_INVALID        0x0800    /* t_xmax invalid/aborted */
#define HEAP_XMAX_IS_MULTI        0x1000    /* t_xmax is a MultiXactId */
#define HEAP_UPDATED        0x2000    /* this is UPDATEd version of row */
#define HEAP_MOVED_OFF        0x4000    /* moved to another place by pre-9.0                    * VACUUM FULL; kept for binary                     * upgrade support */
#define HEAP_MOVED_IN        0x8000    /* moved from another place by pre-9.0                * VACUUM FULL; kept for binary                  * upgrade support */
#define HEAP_MOVED (HEAP_MOVED_OFF | HEAP_MOVED_IN)
#define HEAP_XACT_MASK        0xFFF0    /* visibility-related bits */

上文HeapTupleHeaderData中的t_heap存儲著元組的一些描述信息，結構如下：

typedef struct HeapTupleFields
{
TransactionId t_xmin;   /* inserting xact ID */
TransactionId t_xmax;   /* deleting or locking xact ID */

union
{
   CommandId t_cid;   /* inserting or deleting command ID, or both */
   TransactionId t_xvac; /* VACUUM FULL xact ID */
}    t_field3;
} HeapTupleFields;

其中:
- t_xmin 存儲的是產生這個元組的事務ID，可能是insert或者update語句
- t_xmax 存儲的是刪除或者鎖定這個元組的事務ID
- t_cid 包含cmin和cmax兩個字段，分別存儲創建這個元組的Command ID和刪除這個元組的Command ID
- t_xvac 存儲的是VACUUM FULL 命令的事務ID

這裏需要簡單介紹下PostgreSQL中的事務ID：
- 由32位組成，這就有可能造成事務ID回卷的問題，具體參考文檔
- 順序產生，依次遞增
- 沒有數據變更，如INSERT、UPDATE、DELETE等操作，在當前會話中，事務ID不會改變

PostgreSQL主要就是通過t_xmin，t_xmax，cmin和cmax，ctid，t_infomask來唯一定義一個元組（t_xmin，t_xmax，cmin和cmax，ctid實際上也是一個表的隱藏的標記字段），下麵以一個例子來表示元組更新前後各個字段的變化。

創建表test，插入數據，並查詢t_xmin，t_xmax，cmin和cmax，ctid屬性

postgres=# create table test(id int);
CREATE TABLE
postgres=# insert into test values(1);
INSERT 0 1
postgres=# select ctid, xmin, xmax, cmin, cmax,id from test;
 ctid  | xmin | xmax | cmin | cmax | id
-------+------+------+------+------+----
 (0,1) | 1834 |    0 |    0 |    0 |  1
(1 row)

更新test，並查詢t_xmin，t_xmax，cmin和cmax，ctid屬性

postgres=# update test set id=2;
UPDATE 1
postgres=# select ctid, xmin, xmax, cmin, cmax,id from test;
 ctid  | xmin | xmax | cmin | cmax | id
-------+------+------+------+------+----
 (0,2) | 1835 |    0 |    0 |    0 |  2
(1 row)

使用heap_page_items 方法查看test表對應page header中的內容

postgres=# select * from heap_page_items(get_raw_page('test',0));
 lp | lp_off | lp_flags | lp_len | t_xmin | t_xmax | t_field3 | t_ctid | t_infomask2 | t_infomask | t_hoff | t_bits | t_oid
----+--------+----------+--------+--------+--------+----------+--------+-------------+------------+--------+--------+-------
  1 |   8160 |        1 |     28 |   1834 |   1835 |        0 | (0,2)  |       16385 |       1280 |     24 |        |
  2 |   8128 |        1 |     28 |   1835 |      0 |        0 | (0,2)  |       32769 |      10496 |     24 |        |

從上麵可知，實際上數據庫存儲了更新前後的兩個元組，這個過程中的數據塊中的變化大體如下：

Tuple1更新後會插入一個新的Tuple2，而Tuple1中的ctid指向了新的版本，同時Tuple1的xmax從0變為1835，這裏可以被認為被標記為過期（隻有xmax為0的元組才沒過期），等待PostgreSQL的自動清理輔助進程回收掉。

也就是說，PostgreSQL通過HeapTupleHeaderData 的幾個特殊的字段，給元組設置了不同的版本號，元組的每次更新操作都會產生一條新版本的元組，版本之間從舊到新形成了一條版本鏈（舊的ctid指向新的元組）。

不過這裏需要注意的是，更新操作可能會使表的每個索引也產生新版本的索引記錄，即對一條元組的每個版本都有對應版本的索引記錄。這樣帶來的問題就是浪費了存儲空間，舊版本占用的空間隻有在進行VACCUM時才能被回收，增加了數據庫的負擔。

為了減緩更新索引帶來的影響，8.3之後開始使用HOT機製。定義符合下麵條件的為HOT元組：
- 索引屬性沒有被修改
- 更新的元組新舊版本在同一個page中，其中新的被稱為HOT元組

更新一條HOT元組不需要引入新版本的索引，當通過索引獲取元組時首先會找到最舊的元組，然後通過元組的版本鏈找到HOT元組。這樣HOT機製讓擁有相同索引鍵值的不同版本元組共用一個索引記錄，減少了索引的不必要更新。

事務快照的實現

為了實現元組對事務的可見性判斷，PostgreSQL引入了事務快照SnapshotData，其具體數據結構如下：

typedef struct SnapshotData
{
    SnapshotSatisfiesFunc satisfies;    /* tuple test function */
    TransactionId xmin;        /* all XID < xmin are visible to me */
    TransactionId xmax;        /* all XID >= xmax are invisible to me */
    TransactionId *xip;    //所有正在運行的事務的id列表
    uint32    xcnt;    /* # of xact ids in xip[]，正在運行的事務的計數 */
    TransactionId *subxip;           //進程中子事務的ID列表
    int32    subxcnt;        /* # of xact ids in subxip[]，進程中子事務的計數 */
    bool    suboverflowed;    /* has the subxip array overflowed? */
    bool    takenDuringRecovery;    /* recovery-shaped snapshot? */
    bool    copied;            /* false if it's a static snapshot */
    CommandId    curcid;    /* in my xact, CID < curcid are visible */
    uint32    speculativeToken;
    uint32    active_count;    /* refcount on ActiveSnapshot stack，在活動快照鏈表裏的
*引用計數 */
    uint32    regd_count;    /* refcount on RegisteredSnapshots，在已注冊的快照鏈表
*裏的引用計數 */
    pairingheap_node ph_node;    /* link in the RegisteredSnapshots heap */
    TimestampTz  whenTaken;    /* timestamp when snapshot was taken */
    XLogRecPtr   lsn;        /* position in the WAL stream when taken */
} SnapshotData;

這裏注意區分SnapshotData的xmin，xmax和HeapTupleFields的t_xmin，t_xmax

事務快照是用來存儲數據庫的事務運行情況。一個事務快照的創建過程可以概括為：
- 查看當前所有的未提交並活躍的事務，存儲在數組中
- 選取未提交並活躍的事務中最小的XID，記錄在快照的xmin中
- 選取所有已提交事務中最大的XID，加1後記錄在xmax中
- 根據不同的情況，賦值不同的satisfies，創建不同的事務快照

其中根據xmin和xmax的定義，事務和快照的可見性可以概括為：
- 當事務ID小於xmin的事務表示已經被提交，其涉及的修改對當前快照可見
- 事務ID大於或等於xmax的事務表示正在執行，其所做的修改對當前快照不可見
- 事務ID處在 [xmin, xmax)區間的事務, 需要結合活躍事務列表與事務提交日誌CLOG，判斷其所作的修改對當前快照是否可見，即SnapshotData中的satisfies。

satisfies是PostgreSQL提供的對於事務可見性判斷的統一操作接口。目前在PostgreSQL 10.0中具體實現了以下幾個函數：

HeapTupleSatisfiesMVCC：判斷元組對某一快照版本是否有效
HeapTupleSatisfiesUpdate：判斷元組是否可更新
HeapTupleSatisfiesDirty：判斷當前元組是否已髒
HeapTupleSatisfiesSelf：判斷tuple對自身信息是否有效
HeapTupleSatisfiesToast：用於TOAST表（參考文檔）的判斷
HeapTupleSatisfiesVacuum：用在VACUUM，判斷某個元組是否對任何正在運行的事務可見，如果是，則該元組不能被VACUUM刪除
HeapTupleSatisfiesAny：所有元組都可見
HeapTupleSatisfiesHistoricMVCC：用於CATALOG 表

上述幾個函數的參數都是 (HeapTuple htup, Snapshot snapshot, Buffer buffer)，其具體邏輯和判斷條件，本文不展開具體討論，有興趣的可以參考《PostgreSQL數據庫內核分析》的7.10.2 MVCC相關操作。

此外，為了對可用性判斷的過程進行加速，PostgreSQL還引入了Visibility Map機製（詳見文檔）。Visibility Map標記了哪些page中是沒有dead tuple的。這有兩個好處：
- 當vacuum時，可以直接跳過這些page
- 進行index-only scan時，可以先檢查下Visibility Map。這樣減少fetch tuple時的可見性判斷，從而減少IO操作，提高性能

另外visibility map相對整個relation，還是小很多，可以cache到內存中。

隔離級別的實現

PostgreSQL中根據獲取快照時機的不同實現了不同的數據庫隔離級別（對應代碼中函數GetTransactionSnapshot）：

讀未提交/讀已提交：每個query都會獲取最新的快照CurrentSnapshotData
重複讀：所有的query 獲取相同的快照都為第1個query獲取的快照FirstXactSnapshot
串行化：使用鎖係統來實現

總結

為了保證事務的原子性和隔離性，實現不同的隔離級別，PostgreSQL引入了MVCC多版本機製，概括起就是：
- 通過元組的頭部信息中的xmin，xmax以及t_infomask等信息來定義元組的版本
- 通過事務提交日誌來判斷當前數據庫各個事務的運行狀態
- 通過事務快照來記錄當前數據庫的事務總體狀態
- 根據用戶設置的隔離級別來判斷獲取事務快照的時間

如上文所講，PostgreSQL的MVCC實現方法有利有弊。其中最直接的問題就是表膨脹，為了解決這個問題引入了AutoVacuum自動清理輔助進程，將MVCC帶來的垃圾數據定期清理，這部分內容我們將在下期月報進行分析，敬請期待。

最後更新：2017-10-21 09:03:52

PgSQL · 特性分析 · MVCC機製淺析

背景

MVCC常用實現方法

PostgreSQL中MVCC的具體實現

多版本元組存儲結構

事務快照的實現

隔離級別的實現

總結

上一篇： MySQL · 性能優化· CloudDBA SQL優化建議之統計信息獲取

下一篇：怎樣開發一款操作係統（持續更新ing）

相關內容

熱門內容

最新內容

PgSQL · 特性分析 · MVCC機製淺析

背景

MVCC常用實現方法

PostgreSQL中MVCC的具體實現

多版本元組存儲結構

事務快照的實現

隔離級別的實現

總結

上一篇： MySQL · 性能優化· CloudDBA SQL優化建議之統計信息獲取

下一篇： 怎樣開發一款操作係統（持續更新ing）

相關內容

熱門內容

最新內容

下一篇：怎樣開發一款操作係統（持續更新ing）