PG vs MySQL mvcc機制實現的異同

MVCC實現方法比較

MySQL
寫新數據時，把舊數據寫入回滾段中，其他人讀數據時，從回滾段中把舊的數據讀出來

PostgreSQL
寫新數據時，舊數據不刪除，直接插入新數據。

MVCC實現的原理

PG的MVCC實現原理

定義多版本的數據——使用元組頭部信息的字段來標示元組的版本號
定義數據的有效性、可見性、可更新性——通過當前的事務快照和對應元組的版本號判斷
實現不同的數據庫隔離級別——通過在不同時機獲取快照實現

PG的數據多版本實現

pg中元組由三部分組成——元組頭結點、空值位圖、用戶數據。沒一行元組，都有一個版本號。
該版本由如下幾個數據組成。

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開始。

元組insert時版本號規則

postgres=# CREATE TABLE test (id int);
CREATE TABLE
postgres=# begin;
BEGIN
postgres=*# SELECT txid_current();txid_current 
--------------778
(1 row)postgres=*# insert into test values(1);
INSERT 0 1
postgres=*# SELECT lp as tuple, t_xmin, t_xmax, t_field3 as t_cid, t_ctid FROM heap_page_items(get_raw_page('test', 0));tuple | t_xmin | t_xmax | t_cid | t_ctid 
-------+--------+--------+-------+--------1 |    778 |      0 |     0 | (0,1)
(1 row)

t_xmin 被設置為778，表示插入該元組的txid
（當事務開始，事務管理器會為該事務分配一個txid（transaction id）作為唯一標識符。）
t_xmax 被設置為0，因為該元組還未被更新或刪除過
t_cid 被設置為0，因為這是該事務的第一條命令
t_ctid 指向自身，被設置為（0,1），表示該元組位于0號page的第1個位置上

元組delete時版本號規則

pg的刪除只是將目標元組在邏輯上標為刪除（將t_xmax設為執行delete命令的事務txid），實際該元組依然存在于數據庫的存儲頁面，直至該元組被清理進程清理掉。

postgres=# begin;
BEGIN
postgres=*# SELECT txid_current();txid_current 
--------------779
(1 row)postgres=*# delete from test where id=1;
DELETE 1
postgres=*# SELECT lp as tuple, t_xmin, t_xmax, t_field3 as t_cid, t_ctid FROM heap_page_items(get_raw_page('test', 0));tuple | t_xmin | t_xmax | t_cid | t_ctid 
-------+--------+--------+-------+--------1 |    778 |    779 |     0 | (0,1)
(1 row)

t_xmin 不變，表示插入該元組的txid
t_xmax 被設置為779，即刪除該元組的txid
t_cid 被設置為0，因為這是該事務的第一條命令
t_ctid 指向自身，被設置為（0,1），表示該元組位于0號page的第1個位置上

當txid=779的事務提交時，tuple_1就不再需要了，稱為dead tuple。但是這個tuple依然殘留在頁面上，隨著數據庫的運行，這種死元組越來越多，它們會在VACUUM時最終被清理掉。

元組update時版本號規則

pg不會直接修改數據，而是將目標元組標記為刪除，并插入一條新元組，同時修改t_ctid執行新版本元組。

postgres=# begin;
BEGIN
postgres=*# SELECT txid_current();txid_current 
--------------783
(1 row)postgres=*# SELECT lp as tuple, t_xmin, t_xmax, t_field3 as t_cid, t_ctid FROM heap_page_items(get_raw_page('test', 0));tuple | t_xmin | t_xmax | t_cid | t_ctid 
-------+--------+--------+-------+--------1 |    778 |    779 |     0 | (0,1)2 |    781 |      0 |     0 | (0,2)3 |    782 |      0 |     0 | (0,3)
(3 rows)postgres=*# update test set id = 8;
UPDATE 1
postgres=*# SELECT lp as tuple, t_xmin, t_xmax, t_field3 as t_cid, t_ctid FROM heap_page_items(get_raw_page('test', 0));tuple | t_xmin | t_xmax | t_cid | t_ctid 
-------+--------+--------+-------+--------1 |    778 |    779 |     0 | (0,1)2 |    781 |      0 |     0 | (0,2)3 |    782 |    783 |     0 | (0,4)4 |    783 |      0 |     0 | (0,4)
(4 rows)

Tuple_3

t_xmin 不變，表示插入該元組的txid
t_xmax 被設置為783，即刪除該元組的txid
t_cid 被設置為0，因為這是該事務的第一條命令
t_ctid 指向新版本元組，被設置為（0,4），表示新元組位于0號page的第4個位置上

Tuple_4

t_xmin 被設置為783，表示插入該元組的txid
t_xmax 被設置為0，因為該元組還未被更新或刪除過
t_cid 被設置為1，因為這是該事務的第一條命令
t_ctid 指向自身，被設置為（0,4），表示該元組位于0號page的第4個位置上

PG的事務快照實現

事務狀態

pg定義了四種事務狀態——IN_PROGRESS, COMMITTED, ABORTED和SUB_COMMITTED。

事務快照

事務快照就是當一個事務執行期間，那些事務active、那些非active。即這個事務要么在執行中，要么還沒開始。

postgres=*# SELECT txid_current_snapshot();txid_current_snapshot 
-----------------------796:796:
(1 row)

快照由這樣一個序列構成 xmin:xmax:xip_list

xmin : 最早的active的 tid，所有小于該值的事務狀態為visible(commit)或dead(abort)
xmax: 第一個還未分配的xid，大于等于該值的事務在快照生成時都不可見
xip_list 快照生成時所有active事務的txid

事務快照是用來存儲數據庫的事務運行情況。一個事務快照的創建過程可以概括為：

查看當前所有的未提交并活躍的事務，存儲在數組中
選取未提交并活躍的事務中最小的XID，記錄在快照的xmin中
選取所有已提交事務中最大的XID，加1后記錄在xmax中
根據不同的情況，賦值不同的satisfies，創建不同的事務快照

可見性舉例子

session 1：

postgres=# create table test(id int);
CREATE TABLE
postgres=# insert into test values(1);
INSERT 0 1
postgres=# begin;
BEGIN
postgres=*# insert into test values(2);
INSERT 0 1
postgres=*# select txid_current();txid_current 
--------------791
(1 row)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 |   t_data   
----+--------+----------+--------+--------+--------+----------+--------+-------------+------------+--------+--------+-------+------------1 |   8160 |        1 |     28 |    790 |      0 |        0 | (0,1)  |           1 |       2304 |     24 |        |       | \x010000002 |   8128 |        1 |     28 |    791 |      0 |        0 | (0,2)  |           1 |       2048 |     24 |        |       | \x02000000
(2 rows)

session 2

postgres=# select txid_current_snapshot();txid_current_snapshot 
-----------------------791:791:
(1 row)postgres=# select * from test;id 
----1
(1 row)

session 1的事務791在session 2中并不可見，不僅因為txid>=xmax,還因為791的事務狀態是

postgres=# select txid_status('791');txid_status 
-------------in progress
(1 row)

emp2
session 1

postgres=# begin;
BEGIN
postgres=*# insert into test values(5);
INSERT 0 1
postgres=*# select txid_current();txid_current 
--------------793
(1 row)postgres=*# rollback;

該事務回滾
在session2 中

postgres=# select * from test;id 
----123
(3 rows)postgres=# select txid_current_snapshot();txid_current_snapshot 
-----------------------794:794:
(1 row)postgres=# select txid_status('793');txid_status 
-------------aborted
(1 row)

雖然txid<xmin 但是事務狀態為aborted所以依然不可見。

PG的隔離級別實現

PostgreSQL中根據獲取快照時機的不同實現了不同的數據庫隔離級別

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

比如說

session 1中

postgres=# truncate table test;
TRUNCATE TABLE
postgres=# insert into test values(1);
INSERT 0 1
postgres=# begin;
BEGIN
postgres=*# insert into test values(2);
INSERT 0 1
postgres=*# commit;
COMMIT

表test中插入兩條數據，再插入第二條數據的時候開啟了session 2，且隔離級別為RR，即使session 1提交了第二個事務，session 2 的快照依然沒有變，也就沒法讀取到最新的數據。


postgres=# begin transaction isolation level repeatable read ;
BEGIN
postgres=*# select * from test;id 
----1
(1 row)postgres=*# select txid_current_snapshot();txid_current_snapshot 
-----------------------796:796:
(1 row)postgres=*# select * from test;id 
----1
(1 row)

MySQL的MVCC實現原理

MySQL的數據多版本實現

區別于PG使用元組頭部信息的字段來標示元組的版本號，MySQL 采用row trx_id來標示行數據的不同版本。同樣，InnoDB 也會在事務開始的時候，申請一個順序遞增的事務 ID，叫作 transaction id。并且把 transaction id 賦值給這個數據版本的事務 ID，記為 row trx_id。

同時，舊的數據版本要保留到undo中，并且在新的數據版本中，能夠有信息可以直接拿到它。也就是說，數據表中的一行記錄，其實可能有多個版本 (row)，每個版本有自己的 row trx_id。

這里可以看出MySQL和PG標示不同的數據版本的差異，MySQL將舊數據寫入到undo中，用row trx_id標識。而PG因為舊數據并沒有刪除，還在原堆表上，所以不能只用一個id標識，因此PG使用了t_xmin ，t_xmax等來多個id來和其他版本區分開。

MySQL的事務快照實現

在 MySQL 中，實際上每條記錄在更新的時候都會同時記錄一條回滾操作。記錄上的最新值，通過回滾操作，都可以得到前一個狀態的值。這個功能的實現依賴于UNDO。

InnoDB 為每個事務構造了一個數組，用來保存這個事務啟動瞬間，當前正在“活躍”的所有事務 ID。“活躍”指的就是，啟動了但還沒提交。數組里面事務 ID 的最小值記為低水位，當前系統里面已經創建過的事務 ID 的最大值加 1 記為高水位。這個視圖數組和高水位，就組成了當前事務的一致性視圖（read-view）。也叫快照。

這個其實和PG的實現是一樣的低水位就相當于PG快照的xmin，高水位相當于PG快照的xmax。而活躍未提交的事務就相當于PG中的xip_list 。

如果落在低水位之前的部分，表示這個版本是已提交的事務或者是當前事務自己生成的，這個數據是可見的；
如果落在高水位的，表示這個版本是由將來啟動的事務生成的，是肯定不可見的；
如果落在低水位和高水位之間的部分，那就包括兩種情況
a. 若 row trx_id 在數組中，表示這個版本是由還沒提交的事務生成的，不可見；
b. 若 row trx_id 不在數組中，表示這個版本是已經提交了的事務生成的，可見。

MySQL的隔離級別實現

和PG的實現原理一致，和快照的創建時間有關。

在“可重復讀”隔離級別下，這個視圖是在事務啟動時創建的，整個事務存在期間都用這個視圖。
在“讀提交”隔離級別下，這個視圖是在每個 SQL 語句開始執行的時候創建的。
這里需要注意的是，“讀未提交”隔離級別下直接返回記錄上的最新值，沒有視圖概念；
“串行化”隔離級別下直接用加鎖的方式來避免并行訪問。

PG vs MySQL

在MVCC實現上，PG和MySQL的原理類似，只是舊數據的處理上的差異。PG在工作負載頻繁更新/刪除的情況下，存儲空間會過大。pg永遠不用擔心回滾段不夠用的問題，他的rollback可以立刻執行，而對大表的DML操作MySQL回滾會很慢。同樣pg會存在一些無用的垃圾數據，所以需要vacuum來定時清理。否則舊版本的數據可能會導致查詢需要掃描的數據塊增多，從而導致查詢變慢。空間持續上漲，存儲沒有被有效利用的問題也需要考慮到。

參考

PgSQL· 引擎特性 · 多版本并發控制介紹及實例分析
http://mysql.taobao.org/monthly/2019/08/01/

PgSQL · 特性分析 · MVCC機制淺析
http://mysql.taobao.org/monthly/2017/10/01/

事務到底是隔離的還是不隔離的？
https://time.geekbang.org/column/article/70562