并發(fā)控制
- 了解事務(wù)ID和元組結(jié)構(gòu)
- 元組增刪改
- 提交日志
- 事務(wù)快照
- 可見性檢查及相應(yīng)的規(guī)則
參考文檔：http://www.interdb.jp/pg/pgsql05.html
并發(fā)控制是一種機制买置，當多個事務(wù)并發(fā)運行時拖陆，用來維持一致性和隔離性（ACID的兩個屬性）。
有三種廣泛的并發(fā)控制技術(shù)，MVCC，S2PL，OCC，每種技術(shù)有多個變種。在MVCC中喻括，每個寫操作創(chuàng)建一個數(shù)據(jù)項的新版本，同時保留老版本忽舟。當事務(wù)讀取數(shù)據(jù)時双妨，系統(tǒng)選擇一個版本以確保單個事務(wù)的隔離。PostgreSQL使用MVCC的變種：快照隔離（SI）叮阅。
PostgreSQL實現(xiàn)SI的方式：一個新的數(shù)據(jù)項被直接插入到相關(guān)的表頁中刁品，當讀取條目時，PostgreSQL通過應(yīng)用可見性檢查規(guī)則來選擇條目的適當版本以響應(yīng)單個事務(wù)浩姥。
SI不允許ANSI SQL-92標準中定義的三種異常挑随，即臟讀、不可重復(fù)讀和幻讀勒叠。SI不能實現(xiàn)真正的序列化兜挨，因為它允許序列化異常，如寫傾斜和只讀事務(wù)傾斜眯分。注意拌汇，基于經(jīng)典串行性定義的ANSI SQL-92標準并不等同于現(xiàn)代理論中的定義。為處理此問題弊决，PostgreSQL在9.1版時添加了可序列化快照隔離(SSI)噪舀。SSI可以檢測到序列化異常，并解決由序列化異常引起的沖突飘诗。因此与倡，PostgreSQL 9.1及以后版本提供了一個真正的SERIALIZABLE隔離級別。
PostgreSQL DML使用SI昆稿，DDL使用2PL纺座。
PostgreSQL的事務(wù)隔離級別
| 隔離級別 | 臟讀 | 不可重復(fù)讀 | 幻讀 | 序列化異常 |
|---|---|---|---|---|
| READ COMMITTED | Not possible | Possible | Possible | Possible |
| REPEATABLE READ | Not possible | Not possible | Not possible | Possible |
| SERIALIZABLE | Not possible | Not possible | Not possible | Not possible |
事務(wù)ID
開始一個事務(wù)時，事務(wù)管理器分配一個唯一標識符溉潭，稱為事務(wù)ID（txid）净响。txid是32位的無符號整型。開始一個事務(wù)后岛抄，可以使用內(nèi)置函數(shù) txid_current() 查詢當前的事務(wù)ID别惦。
cc1=# begin;
BEGIN
cc1=# select txid_current();
txid_current
--------------
14536
(1 row)
cc1=#
PostgreSQL保留了三種特殊的txid：
0：Invalid txid
1：Bootstrap txid，在初始化數(shù)據(jù)庫集簇時使用
2：Frozen txid夫椭，事務(wù)ID回卷問題相關(guān)
txid可以相互比較。如氯庆，txid=100時蹭秋，大于100的txid是不可見的扰付，小于100的txid是可見的。
由于txid空間在實際系統(tǒng)中不足仁讨，PostgreSQL將txid空間視為一個圓羽莺。但這會引起事務(wù)ID回卷問題，在后面介紹洞豁。
元組結(jié)構(gòu)
表頁中的堆元組分為普通數(shù)據(jù)元組和TOAST元組盐固，這里介紹普通數(shù)據(jù)元組。
堆元組包含HeapTupleHeaderData丈挟，NULL bitmap刁卜，User data。
HeapTupleHeaderData結(jié)構(gòu)如下：
typedef struct HeapTupleFields {
ShortTransactionId t_xmin; /* inserting xact ID */
ShortTransactionId t_xmax; /* deleting or locking xact ID */
union {
CommandId t_cid; /* inserting or deleting command ID, or both */
ShortTransactionId t_xvac; /* old-style VACUUM FULL xact ID */
} t_field3;
} HeapTupleFields;
typedef struct DatumTupleFields {
int32 datum_len_; /* varlena header (do not touch directly!) */
int32 datum_typmod; /* -1, or identifier of a record type */
Oid datum_typeid; /* composite type OID, or RECORDOID */
/*
* Note: field ordering is chosen with thought that Oid might someday
* widen to 64 bits.
*/
} DatumTupleFields;
typedef struct HeapTupleHeaderData {
union {
HeapTupleFields t_heap;
DatumTupleFields t_datum;
} t_choice;
ItemPointerData t_ctid; /* current TID of this or newer tuple */
/* 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 -- VARIABLE LENGTH */
/* MORE DATA FOLLOWS AT END OF STRUCT */
} HeapTupleHeaderData;
t_min：insert元組的事務(wù)ID
t_max：delete,update元組的事務(wù)ID
t_cid：command ID曙咽，當前事務(wù)執(zhí)行了多少SQL命令蛔趴，起始值為0。如例朱，一個事務(wù)有三個insert語句孝情，則第一個命令insert了元組，t_cid=0洒嗤，第二個命令insert元組箫荡，t_cid=1，以此類推
t_ctid：保存了一個元組標識符（tid）渔隶，它指向自身或一個新元組
插入羔挡，刪除，更新元組
-
插入
在insert操作中派撕，新元組寫入目標表的頁婉弹。
insert操作.png
假設(shè)txid為99的事務(wù)insert了一個元組到頁面，則該元組頭部信息如下：
Tuple_1：
t_xmin 設(shè)為99终吼，該元組由txid為99的事務(wù)寫入
t_xmax 設(shè)為0镀赌，該元組未被delete和update
t_cid 設(shè)為0，該元組為txid為99事務(wù)的第一個元組
t_ctid 設(shè)為(0, 1)际跪，指向其自身
cc1=# create table t(id int);
CREATE TABLE
cc1=# insert into t values(1);
INSERT 0 1
cc1=# insert into t values(2);
INSERT 0 1
cc1=# insert into t values(3);
INSERT 0 1
cc1=# SELECT * from heap_page_items(get_raw_page('t',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 | 14547 | 0 | 0 | (0,1) | 1 | 2048 | 24 | |
2 | 8128 | 1 | 28 | 14548 | 0 | 0 | (0,2) | 1 | 2048 | 24 | |
3 | 8096 | 1 | 28 | 14549 | 0 | 0 | (0,3) | 1 | 2048 | 24 | |
(3 rows)
-
刪除
在刪除操作中商佛，目標元組在邏輯上刪除。執(zhí)行delete命令的txid被寫到元組的t_xmax姆打。
delete操作.png
假設(shè)Tuple_1被txid為111的事務(wù)刪除良姆，則該元組頭部信息如下：
Tuple_1：
t_xmax 被設(shè)為 111。
如果txid 111的事務(wù)提交了幔戏，則Tuple_1則不再被需要玛追。這種不被需要的元組在PostgreSQL中被稱為死元組。死元組最終會被從頁面中刪除，VACUUM清理死元組痊剖。
cc1=# delete from t where id=3;
DELETE 1
cc1=# SELECT * from heap_page_items(get_raw_page('t',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 | 14547 | 0 | 0 | (0,1) | 1 | 2304 | 24 | |
2 | 8128 | 1 | 28 | 14548 | 0 | 0 | (0,2) | 1 | 2304 | 24 | |
3 | 8096 | 1 | 28 | 14549 | 14550 | 0 | (0,3) | 1 | 256 | 24 | |
(3 rows)
-
更新
在更新操作中韩玩，PostgreSQL邏輯上刪除元組并插入新元組。
更新操作.png
假設(shè)之前由txid 99寫入的行陆馁，被txid 100更新了兩次找颓。
執(zhí)行第一個update后，通過設(shè)置Tuple_1的t_xmax為100叮贩，Tuple_1在邏輯上刪除击狮，并寫入Tuple_2。然后Tuple_1的t_ctid重寫為(0,2)指向Tuple_2益老。元組1彪蓬，2頭部信息如下：
Tuple_1：
t_xmax 設(shè)為100
t_ctid 從(0,1)被重寫為(0,2)
Tuple_2：
t_xmin 設(shè)為100
t_xmax 設(shè)為0
t_cid 設(shè)為0
t_ctid 設(shè)為(0, 2)
執(zhí)行第二個update后，如同第一個update杨箭，Tuple_2在邏輯上刪除寞焙，并寫入Tuple_3。元組2互婿，3頭部信息如下：
Tuple_2：
t_xmax 設(shè)為100
t_ctid 從(0,2)重寫為(0,3)
Tuple_3：
t_xmin 設(shè)為100
t_xmax 設(shè)為0
t_cid 設(shè)為1
t_ctid 設(shè)為(0,3)
如果txid 100提交捣郊，則Tuple_1和Tuple_2為死元組。如果txid 100被中止慈参，則Tuple_2和Tuple_3為死元組酪刀。
cc1=# insert into t values(5);
INSERT 0 1
cc1=# SELECT * from heap_page_items(get_raw_page('t',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 | 14547 | 14551 | 0 | (0,4) | 16385 | 256 | 24 | |
2 | 8128 | 1 | 28 | 14548 | 0 | 0 | (0,2) | 1 | 2304 | 24 | |
3 | 8096 | 1 | 28 | 14549 | 14550 | 0 | (0,3) | 1 | 1280 | 24 | |
4 | 8064 | 1 | 28 | 14551 | 0 | 0 | (0,4) | 32769 | 10240 | 24 | |
5 | 8032 | 1 | 28 | 14552 | 0 | 0 | (0,5) | 1 | 2048 | 24 | |
(5 rows)
cc1=# begin;
BEGIN
cc1=# update t set id=6 where id=5;
UPDATE 1
cc1=# SELECT * from heap_page_items(get_raw_page('t',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 | 14547 | 14551 | 0 | (0,4) | 16385 | 1280 | 24 | |
2 | 8128 | 1 | 28 | 14548 | 0 | 0 | (0,2) | 1 | 2304 | 24 | |
3 | 8096 | 1 | 28 | 14549 | 14550 | 0 | (0,3) | 1 | 1280 | 24 | |
4 | 8064 | 1 | 28 | 14551 | 0 | 0 | (0,4) | 32769 | 10496 | 24 | |
5 | 8032 | 1 | 28 | 14552 | 14553 | 0 | (0,6) | 16385 | 256 | 24 | |
6 | 8000 | 1 | 28 | 14553 | 0 | 0 | (0,6) | 32769 | 10240 | 24 | |
(6 rows)
cc1=# update t set id=7 where id=6;
UPDATE 1
cc1=# SELECT * from heap_page_items(get_raw_page('t',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 | 14547 | 14551 | 0 | (0,4) | 16385 | 1280 | 24 | |
2 | 8128 | 1 | 28 | 14548 | 0 | 0 | (0,2) | 1 | 2304 | 24 | |
3 | 8096 | 1 | 28 | 14549 | 14550 | 0 | (0,3) | 1 | 1280 | 24 | |
4 | 8064 | 1 | 28 | 14551 | 0 | 0 | (0,4) | 32769 | 10496 | 24 | |
5 | 8032 | 1 | 28 | 14552 | 14553 | 0 | (0,6) | 16385 | 256 | 24 | |
6 | 8000 | 1 | 28 | 14553 | 14553 | 0 | (0,7) | 49153 | 8224 | 24 | |
7 | 7968 | 1 | 28 | 14553 | 0 | 1 | (0,7) | 32769 | 10240 | 24 | |
(7 rows)
cc1=#
- 空閑空間映射（FSM）
當插入堆元組或索引元組時精耐，PostgreSQL使用相應(yīng)的表占贫，索引FSM來選擇可被寫入的頁同诫。
所有表和索引有FSM，每個FSM在對應(yīng)的表或索引文件中存儲每個頁面的可用空間信息壮锻。所有FSM都以"fsm"后綴存儲琐旁，必要時將它們加載到共享內(nèi)存中。
提交日志（clog）
PostgreSQL在clog中存儲事務(wù)的狀態(tài)猜绣。clog被分配到共享內(nèi)存灰殴，并在事務(wù)處理過程中被使用。
- 事務(wù)狀態(tài)
事務(wù)有四種狀態(tài)掰邢，IN_PROGRESS牺陶，COMMITTED，ABORTED辣之，SUB_COMMITTED掰伸。其中SUB_COMMITTED在子事務(wù)中存在。 -
Clog怎么執(zhí)行
clog在共享內(nèi)存中由1個或多個8KB的頁面組成怀估。clog在邏輯上構(gòu)成一個數(shù)組狮鸭。數(shù)組的索引對應(yīng)各自的事務(wù)ID，數(shù)組的每一項保存事務(wù)ID相應(yīng)的狀態(tài)。
clog.png
當當前事務(wù)ID一直增長怕篷，而clog不能再保存它時历筝，會增加一個新頁面酗昼。
當需要讀取事務(wù)的狀態(tài)時廊谓，內(nèi)存函數(shù)會被調(diào)用。這些函數(shù)讀取clog并返回請求的事務(wù)的狀態(tài)麻削。 - 維護Clog
當PostgreSQL停止運行或checkpoint進程運行時蒸痹，clog數(shù)據(jù)會寫到文件中，這些文件保存在pg_clog目錄下呛哟。文件的最大大小為256KB叠荠，如，當clog使用了8個頁面（總大小64KB）扫责，數(shù)據(jù)會被保存到一個文件榛鼎，當clog使用了37個頁面（總大小296KB），數(shù)據(jù)會被保存到兩個文件鳖孤，一個文件保存256KB者娱，一個40KB。
當PostgreSQL啟動時苏揣，保存在pg_clog目錄下文件的數(shù)據(jù)會被加載黄鳍，以初始化clog。
clog被寫滿后平匈，會增加新頁面框沟，然后clog大小會持續(xù)增長。但是增炭，不是所有clog數(shù)據(jù)都是必要的忍燥，VACUUM會定時刪除舊數(shù)據(jù)（同時刪除clog頁和文件）。 - 事務(wù)快照
事務(wù)快照是一個數(shù)據(jù)集隙姿，它存儲了關(guān)于單個事務(wù)在某一時間點是否所有事務(wù)都處于活動狀態(tài)的信息梅垄。在這里，活動事務(wù)意味著它正在進行或尚未啟動孟辑。
PostgreSQL內(nèi)部定義事務(wù)快照的文本表示格式為'100:100:'哎甲。如，’100:100:‘表示txid<100的事務(wù)是不活躍的饲嗽，txid>=100是活躍的炭玫。 - txid_current_snapshot內(nèi)置函數(shù)
txid_current_snapshot函數(shù)顯示當前事務(wù)的快照。
cc1=# select txid_current_snapshot();
txid_current_snapshot
-----------------------
14557:14559:
(1 row)
txid_current_snapshot的文本表現(xiàn)為'xmin:xmax:xip_list'：
xmin：活躍的最小txid貌虾，所有早于該txid的事務(wù)可能被提交吞加，從而可見，或者被回滾，不可見
xmax：還未被分配的txid衔憨，所有大于或等于這個值的txid在快照時間點還未啟動叶圃，所以不可見
xip_list：在快照時間點活躍的txid，只包含在xmin,xmax之前的活躍txid
如：快照'100:104:100,102'践图，xmin=100掺冠，xmax=104，xip_list=100,102
上圖(a)中码党，事務(wù)快照 '100:100:' 表示：
xmin=100 則 txid <= 99 是不活躍的德崭，xmax=100 則 txid >= 100 是活躍的。
上圖(b)中揖盘，事務(wù)快照 '100:104:100,102' 表示：
xmin=100 則 txid <= 99 是不活躍的眉厨，xmax=104 則 txid >= 104 是活躍的，txid為100兽狭，102 是活躍的憾股，txid為101，103是不活躍的箕慧。
事務(wù)管理器提供事務(wù)快照服球，在隔離級別READ COMMITTED，每次SQL命令執(zhí)行時销钝，事務(wù)會獲取快照有咨，在其他隔離級別（REPEATABLE READ，SERIALIZABLE）蒸健，事務(wù)只在第一條SQL命令執(zhí)行時獲取快照座享。獲取的快照用于元組的可見性檢查。
當使用獲得的快照進行可見性檢查時似忧，必須將快照的活動事務(wù)視為IN PROGRESS渣叛，即使它們已經(jīng)被提交或中止。這個規(guī)則非常重要盯捌，因為這在READ COMMITTED淳衙，REPEATABLE READ(或者SERIALIZABLE)中有不同表現(xiàn)。
事務(wù)管理器始終保存當前正在運行的事務(wù)信息饺著。上圖中事務(wù)A,B使用隔離級別READ COMMITTED箫攀，事務(wù)C使用REPEATABLE READ。
T1時間點：
事務(wù)A啟動幼衰，執(zhí)行了第一個SELECT命令靴跛。當執(zhí)行第一個命令時，事務(wù)A請求txid和快照渡嚣，在當前場景梢睛，事務(wù)管理器分配txid 200肥印，并返回快照 '200:200:'。
T2時間點：
事務(wù)B啟動绝葡，執(zhí)行了第一個SELECT命令深碱。事務(wù)管理器分配txid 201，并返回快照 '200:200:'藏畅。事務(wù)A（txid=200）狀態(tài)是IN PROGRESS敷硅，所以事務(wù)A對于事務(wù)B不可見。
T3時間點：
事務(wù)C啟動墓赴，執(zhí)行了第一個SELECT命令竞膳。事務(wù)管理器分配txid 202，并返回快照 '200:200:'诫硕。所以事務(wù)A，事務(wù)B對于事務(wù)C不可見刊侯。
T4時間點：
事務(wù)A提交章办，事務(wù)管理器刪除事務(wù)A相關(guān)信息。
T5時間點：
事務(wù)B滨彻，事務(wù)C執(zhí)行第二個SELECT命令藕届。
事務(wù)B是READ COMMITTED，它請求事務(wù)快照亭饵，在這個場景休偶，事務(wù)B獲得快照 '201:201:'，由于事務(wù)A（txid=200）已經(jīng)提交辜羊，所以事務(wù)A對于事務(wù)B可見踏兜。
事務(wù)C是REPEATABLE READ，它不重新請求快照八秃，還是使用原來的快照 '200:200:'碱妆，所以事務(wù)A對于事務(wù)C還是不可見。
可見性檢查規(guī)則
可見性檢查規(guī)則是一組規(guī)則昔驱，它利用元組的t_xmin疹尾，t_xmax，clog骤肛，獲取的事務(wù)快照纳本，來確定每個元組是否可見。這些規(guī)則比較復(fù)雜腋颠，這里只介紹需要的最小規(guī)則繁成。在下文中，我們省略了與子事務(wù)相關(guān)的規(guī)則秕豫，并忽略了關(guān)于t_ctid的討論朴艰，即我們不考慮在事務(wù)中更新兩次以上的元組观蓄。
- t_xmin狀態(tài)為中止（ABORTED）
元組的t_xmin狀態(tài)為中止時，該元組始終不可見祠墅，因為insert該元組的事務(wù)已經(jīng)被中止侮穿。
/* t_xmin status == ABORTED */
Rule 1: IF t_xmin status is 'ABORTED' THEN
RETURN 'Invisible'
END IF
該規(guī)則的數(shù)學(xué)表達式表示為：
Rule 1: If Status(t_xmin) = ABORTED ? Invisible
- t_xmin狀態(tài)為進行中（IN_PROGRESS）
/* t_xmin status == IN_PROGRESS */
IF t_xmin status is 'IN_PROGRESS' THEN
IF t_xmin = current_txid THEN
Rule 2: IF t_xmax = INVALID THEN
RETURN 'Visible'
Rule 3: ELSE /* this tuple has been deleted or updated by the current transaction itself. */
RETURN 'Invisible'
END IF
Rule 4: ELSE /* t_xmin ≠ current_txid */
RETURN 'Invisible'
END IF
END IF
Rule 4: 如果該元組是其他事務(wù)插入的，且t_xmin的狀態(tài)是IN_PROCESS毁嗦，則該元組對當前事務(wù)不可見亲茅。
Rule 3: 如果元組的t_xmin等于當前的txid（該元組是由當前事務(wù)插入），并且t_xmax不是INVALID狗准，則該元組對當前事務(wù)不可見克锣，它已經(jīng)被當前事務(wù)刪除或者更新。
Rule 2: 如果元組是由當前事務(wù)插入并且t_xmax為INVALID腔长，則元組對當前事務(wù)可見袭祟。
Rule 2: If Status(t_xmin) = IN_PROGRESS ∧ t_xmin = current_txid ∧ t_xmax = INVAILD ? Visible
Rule 3: If Status(t_xmin) = IN_PROGRESS ∧ t_xmin = current_txid ∧ t_xmax ≠ INVAILD ? Invisible
Rule 4: If Status(t_xmin) = IN_PROGRESS ∧ t_xmin ≠ current_txid ? Invisible
- t_xmin狀態(tài)為已提交（COMMITTED）
/* t_xmin status == COMMITTED */
IF t_xmin status is 'COMMITTED' THEN
Rule 5: IF t_xmin is active in the obtained transaction snapshot THEN
RETURN 'Invisible'
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
Rule 7: IF t_xmax = current_txid THEN
RETURN 'Invisible'
Rule 8: ELSE /* t_xmax ≠ current_txid */
RETURN 'Visible'
END IF
ELSE IF t_xmax status is 'COMMITTED' THEN
Rule 9: IF t_xmax is active in the obtained transaction snapshot THEN
RETURN 'Visible'
Rule 10: ELSE
RETURN 'Invisible'
END IF
END IF
END IF
Rule 6：由于t_xmin已提交，t_max為INVALID或者ABORTED捞附，此時元組對當前事務(wù)可見巾乳。
Rule 5：t_xmin在獲取的事務(wù)快照中是活躍的，這種情況下鸟召，元組是不可見的胆绊，因為被當做IN_PROGRESS。
Rule 7：t_xmax等于當前txid欧募，在這個條件下压状，結(jié)合Rule 3，元組不可見跟继，元組已經(jīng)被當前事務(wù)刪除或更新种冬。
Rule 8：t_xmax狀態(tài)為IN_PROGRESS且不等于當前txid時，元組可見还栓，因為元組未被刪除碌廓。
Rule 9：t_xmax狀態(tài)為COMMITTED，且t_xmax在事務(wù)快照中是活躍的剩盒，元組可見谷婆。
Rule 10：t_xmax狀態(tài)為COMMITTED，且t_xmax在事務(wù)快照中是不活躍的辽聊，元組不可見纪挎，已被其他事務(wù)刪除。
Rule 5: If Status(t_xmin) = COMMITTED ∧ Snapshot(t_xmin) = active ? Invisible
Rule 6: If Status(t_xmin) = COMMITTED ∧ (t_xmax = INVALID ∨ Status(t_xmax) = ABORTED) ? Visible
Rule 7: If Status(t_xmin) = COMMITTED ∧ Status(t_xmax) = IN_PROGRESS ∧ t_xmax = current_txid ? Invisible
Rule 8: If Status(t_xmin) = COMMITTED ∧ Status(t_xmax) = IN_PROGRESS ∧ t_xmax ≠ current_txid ? Visible
Rule 9: If Status(t_xmin) = COMMITTED ∧ Status(t_xmax) = COMMITTED ∧ Snapshot(t_xmax) = active ? Visible
Rule 10: If Status(t_xmin) = COMMITTED ∧ Status(t_xmax) = COMMITTED ∧ Snapshot(t_xmax) ≠ active ? Invisible
可見性檢查
-
可見性檢查
可見性檢查.png
上圖場景中跟匆，SQL命令的執(zhí)行順序如下：
T1時間點：開始事務(wù) txid=200
T2時間點：開始事務(wù) txid=201
T3時間點：txid 200,201執(zhí)行select命令
T4時間點：txid 200 執(zhí)行update命令
T5時間點：txid 200,201執(zhí)行select命令
T6時間點：txid 200 執(zhí)行commit
T7時間點：txid 201執(zhí)行select命令
以上開始了兩個事務(wù)异袄，txid 200，201玛臂，其中txid 200的隔離級別為READ COMMITTED烤蜕，txid 201隔離級別模擬為READ COMMITTED封孙，REPEATABLE READ。
下面我們看下SELECT語句如何對每個元組進行可見性檢查的讽营。
T3 Select命令：
此時只有Tuple_1虎忌，通過Rule 6，我們知道該元組是可見的橱鹏，所以兩個事務(wù)的select語句都返回'Jekyll'膜蠢。
Rule6(Tuple_1) ? Status(t_xmin:199) = COMMITTED ∧ t_xmax = INVALID ? Visible
T3 Select.png
T5 Select命令：
txid 200的Select命令，Tuple_1不可見(Rule 7)莉兰，Tuple_2可見(Rule 2)挑围，所以該事務(wù)select返回'Hyde'。
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
txid 201的Select命令糖荒，Tuple_1可見(Rule 8)杉辙，Tuple_2不可見(Rule 4)，所以該事務(wù)select返回'Jekyll'寂嘉。
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
T5 Select.png
T7 Select命令：
txid 201隔離級別為READ COMMITTED時奏瞬，由于txid 200已提交，此時txid 201獲取的事務(wù)快照為 '201:201:'泉孩，所以，Tuple_1不可見(Rule 10)并淋，Tuple_2可見(Rule 6)寓搬，此時select返回'Hyde'。
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
這個結(jié)果與之前txid 200提交前的結(jié)果是不一致的县耽，此現(xiàn)象稱為不可重復(fù)讀句喷。
txid 201隔離級別為REPEATABLE READ時，事務(wù)快照還是 '200:200:'兔毙，所以唾琼，Tuple_1可見(Rule 9)，Tuple_2不可見(Rule 5)澎剥，select返回 'Jekyll'锡溯。REPEATABLE READ不會出現(xiàn)不可重復(fù)讀。
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
T7 Select.png -
REPEATABLE READ隔離級別的幻讀
ANSI SQL-92標準中定義的REPEATABLE READ允許幻讀哑姚。然而祭饭，PostgreSQL的實現(xiàn)不允許它們。原則上叙量，SI不允許幻讀倡蝙。
開啟兩個事務(wù)，事務(wù)A txid 14567绞佩，事務(wù)B txid 14568寺鸥，隔離級別分別為READ COMMITTED猪钮，REPEATABLE READ。在事務(wù)A插入一行數(shù)據(jù)并提交胆建，然后在事務(wù)B執(zhí)行select語句查詢烤低，結(jié)合Rule 5，此時事務(wù)A插入的數(shù)據(jù)對于事務(wù)B不可見眼坏。所以幻讀不會出現(xiàn)拂玻。
Rule5(new tuple): Status(t_xmin:14567) = COMMITTED ∧ Snapshot(t_xmin:14567) = active ? Invisible
REPEATABLE READ.png
防止丟失更新
丟失更新，也稱為寫寫沖突宰译，是并發(fā)事務(wù)更新相同行時發(fā)生的異常檐蚜，必須在REPEATABLE READ和SERIALIZABLE級別上防止。(READ COMMITTED級別不需要防止丟失更新)沿侈。
- 并發(fā)事務(wù)更新的表現(xiàn)
以下是更新命令執(zhí)行時闯第，調(diào)用的ExecUpdate函數(shù)的偽代碼。
(1) FOR each row that will be updated by this UPDATE command // 獲取UPDATE命令會更新的每一行
(2) WHILE true // 循環(huán)直到目標行被更新或者事務(wù)被中止
/* The First Block */
(3) IF the target row is being updated THEN // 目標行正在更新缀拭，進入以下代碼塊
// 等待更新目標行的事務(wù)終止
(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
// 如果更新目標行的事務(wù)提交了咳短，中止當前事務(wù)
(6) ABORT this transaction /* First-Updater-Win */
ELSE
// 否則重復(fù)循環(huán)
(7) GOTO step (2)
END IF
/* The Second Block */
(8) ELSE IF the target row has been updated by another concurrent transaction THEN
// 目標行已經(jīng)被其他并行事務(wù)更新
(9) IF (the isolation level of this transaction is READ COMMITTED THEN
// 如果隔離級別為READ COMMITTED
(10) UPDATE the target row
ELSE
// 否則中止事務(wù)，首次更新勝利
(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. */
// 目標行未被終止的事務(wù)更新蛛淋，則更新目標行
(12) UPDATE the target row
END IF
END WHILE
END FOR
以上圖表展示了函數(shù)ExecUpdate的三個分支咙好。
(1) 目標行正在被更新
該場景，目標行已經(jīng)被其他并行事務(wù)更新褐荷，且這個事務(wù)還未終止勾效，當前事務(wù)必須等待更新目標行的事務(wù)終止，因為PostgreSQL的SI使用first-update-win模式叛甫。
如圖所示层宫，事務(wù)A，事務(wù)B并行執(zhí)行其监，事務(wù)B要更新行萌腿，這行數(shù)據(jù)已經(jīng)被事務(wù)A更新，此時事務(wù)B等待事務(wù)A終止抖苦，當事務(wù)A提交時毁菱，事務(wù)B的更新行命令開始執(zhí)行，如果當前事務(wù)的隔離級別為READ COMMITTED睛约，則目標行會被更新鼎俘，如果隔離級別為REPEATABLE READ,SERIALIZABLE，事務(wù)B會被中止辩涝，以防止丟失更新贸伐。
(2) 目標行已經(jīng)被并行事務(wù)更新
當前事務(wù)要更新目標行，但是目標行已經(jīng)被其他并行事務(wù)更新且已提交怔揩，在這個場景捉邢，如果當前事務(wù)隔離級別為READ COMMITTED脯丝，則當前事務(wù)可以更新目標行，否則伏伐，當前事務(wù)會被中止宠进，以防止丟失更新。
(3) 沒有沖突
沒有沖突的情況下藐翎，當前事務(wù)正常更新目標行材蹬。
注：PostgreSQL基于SI的并發(fā)控制采用first-update-win方案。PostgreSQL的SSI使用的是first-committer-win的方案吝镣。
序列化快照隔離（SSI）
Serializable Snapshot Isolation (SSI)從9.1版開始就被嵌入到SI中堤器，以實現(xiàn)真正的Serializable隔離級別。
-
實現(xiàn)SSI的基礎(chǔ)策略
如果在優(yōu)先圖中出現(xiàn)了帶有一些沖突的循環(huán)末贾，則會出現(xiàn)序列化異常闸溃。這可以用最簡單的異常來解釋，即寫傾斜拱撵。
寫傾斜時間表.png
如上圖辉川，事務(wù)A讀取Tuple_B，事務(wù)B讀取Tuple_A拴测，然后乓旗，事務(wù)A寫Tuple_A，事務(wù)B寫Tuple_B集索，在這種情況下寸齐，出現(xiàn)了兩個讀寫沖突。
從概念上來講抄谐，有三種類型的沖突：寫讀沖突(臟讀)，寫寫沖突(丟失更新)扰法，讀寫沖突蛹含。臟讀在PostgreSQL中不會出現(xiàn)，丟失更新PostgreSQL已處理塞颁，SSI只需處理讀寫沖突浦箱。
PostgreSQL實現(xiàn)SSI使用以下策略：
- 事務(wù)訪問到的所有對象(元組，頁面祠锣，關(guān)系)記錄為SIREAD鎖酷窥。
- 在寫任何堆或索引元組時，使用SIREAD鎖檢測讀寫沖突伴网。
- 如果通過檢查檢測到的讀寫沖突檢測到序列化異常蓬推，則中止事務(wù)。
- PostgreSQL實現(xiàn)SSI
SIREAD鎖：SIREAD鎖在內(nèi)部稱為謂詞鎖澡腾，它是一對對象和(虛擬)txids沸伏，用于存儲關(guān)于誰訪問了哪個對象的信息糕珊。
例如，txid 100讀取目標表的Tuple_1毅糟，SIREAD鎖 {Tuple_1, {100}} 創(chuàng)建红选。如果另一個事務(wù) txid 101，讀取Tuple_1姆另，則SIREAD鎖更新為 {Tuple_1, {100,101}}喇肋。SIREAD鎖也能在索引頁被創(chuàng)建，當僅索引掃描時迹辐。
SIREAD鎖有三個級別：元組蝶防，頁，關(guān)系右核。如果創(chuàng)建了單個頁面中所有元組的SIREAD鎖慧脱，則將它們聚合為該頁面的單個SIREAD鎖，并釋放(刪除)相關(guān)元組的所有SIREAD鎖贺喝，以減少內(nèi)存空間菱鸥。讀取所有頁面也是如此。
當為索引創(chuàng)建SIREAD鎖時躏鱼，開始將創(chuàng)建頁級SIREAD鎖氮采。當使用順序掃描時，從一開始就創(chuàng)建關(guān)系級SIREAD鎖染苛，而不管是否存在索引和/或WHERE子句鹊漠。注意，在某些情況下茶行，此實現(xiàn)可能導(dǎo)致對序列化異常的誤報檢測躯概。
讀寫沖突：讀寫沖突是一個SIREAD鎖和兩個讀寫SIREAD鎖的txid的三元組。 - SSI執(zhí)行
這里介紹SSI如何解決寫傾斜異常畔师。
// 準備以下表
postgres=# CREATE TABLE tbl (id INT primary key, flag bool DEFAULT false);
CREATE TABLE
postgres=# INSERT INTO tbl (id) SELECT generate_series(1,2000);
INSERT 0 2000
postgres=# ANALYZE tbl;
ANALYZE
測試以下場景娶靡，假設(shè)所有命令使用索引掃描，則將讀取堆及索引頁：
上圖中：
T1時間點看锉，事務(wù)A讀取Tuple_2000姿锭，內(nèi)部函數(shù)創(chuàng)建了L1,L2 SIREAD鎖，分別關(guān)聯(lián)Pkey_2, Tuple_2000伯铣。
T2時間點呻此，事務(wù)B讀取Tuple_1，內(nèi)部函數(shù)創(chuàng)建了L3,L4 SIREAD鎖腔寡，分別關(guān)聯(lián)Pkey_1, Tuple_1焚鲜。
T3時間點，事務(wù)A更新Tuple_1，內(nèi)部函數(shù)創(chuàng)建讀寫沖突 C1恃泪，它是事務(wù)B和事務(wù)A之間的Pkey_1和Tuple_1的沖突郑兴，因為Pkey_1和Tuple_1都是由事務(wù)B讀取和事務(wù)A寫入的。
T4時間點贝乎，事務(wù)B更新Tuple_2000情连，內(nèi)部函數(shù)創(chuàng)建讀寫沖突 C2，它是事務(wù)B和事務(wù)A之間的Pkey_2和Tuple_2000的沖突览效。
在這個場景中却舀，C1和C2在優(yōu)先圖中創(chuàng)建一個循環(huán)。因此锤灿，事務(wù)A和事務(wù)B處于非序列化狀態(tài)挽拔。但是，事務(wù)A和事務(wù)B兩個事務(wù)都沒有提交但校，因此事務(wù)B不會被中止螃诅。這是因為PostgreSQL的SSI實現(xiàn)是基于first-committer-win方案。
T5時間點状囱，事務(wù)A提交术裸。
T6時間點，事務(wù)B提交亭枷，由于讀寫沖突和first-committer-win方案袭艺，事務(wù)B被中止。
需要維護流程
PostgreSQL并發(fā)控制機制需要以下維護流程：
- 刪除死元組和指向關(guān)聯(lián)死元組的索引元組
- 刪除clog不需要的數(shù)據(jù)
- 凍結(jié)舊txid
- 更新FSM, VM和統(tǒng)計信息
其中1叨粘，2已在前面介紹猾编，3關(guān)聯(lián)事務(wù)ID回卷問題。
- 凍結(jié)處理
假設(shè)txid 100寫入元組Tuple_1升敲，則Tuple_1的t_xmin為100答倡，服務(wù)器已經(jīng)運行了很長時間，Tuple_1沒有被修改驴党。當前txid為231+100苇羡，然后執(zhí)行SELECT語句。這個時間點鼻弧，Tuple_1可見，因為txid 100在past部分锦茁，再將執(zhí)行select語句攘轩，此時當前txid為txid為231+101。而Tuple_1不可見码俩，因為txid 100在future部分度帮。這個問題在PostgreSQL稱為事務(wù)ID回卷問題。
回卷問題.png
為了處理這個問題，PostgreSQL引入了凍結(jié)txid的概念笨篷，并實現(xiàn)了FREEZE進程瞳秽。
一個凍結(jié)txid，是一個特殊的保留txid 2率翅，被定義為總是比其他所有txid更早练俐。換句話說，凍結(jié)的txid總是不活躍和可見的冕臭。
FREEZE進程被VACUUM進程調(diào)用腺晾。FREEZE進程掃描所有表文件，如果t_xmin比當前txid - vacuum_freeze_min_age(默認為5千萬)的值老時辜贵，F(xiàn)REEZE進程重寫元組的t_xmin為凍結(jié)txid悯蝉。
在版本9.4及以后的版本，XMIN_FROZEN被寫到元組的t_infomask字段托慨，而不是重寫t_xmin為凍結(jié)id鼻由。
