并發(fā)控制

• 了解事務(wù)ID和元組結(jié)構(gòu)
• 元組增刪改
• 提交日志
• 事務(wù)快照
• 可見性檢查及相應(yīng)的規(guī)則
  參考文檔：http://www.interdb.jp/pg/pgsql05.html

并發(fā)控制是一種機(jī)制，當(dāng)多個(gè)事務(wù)并發(fā)運(yùn)行時(shí)，用來維持一致性和隔離性（ACID的兩個(gè)屬性）。
有三種廣泛的并發(fā)控制技術(shù)，MVCC，S2PL，OCC，每種技術(shù)有多個(gè)變種。在MVCC中，每個(gè)寫操作創(chuàng)建一個(gè)數(shù)據(jù)項(xiàng)的新版本，同時(shí)保留老版本。當(dāng)事務(wù)讀取數(shù)據(jù)時(shí)，系統(tǒng)選擇一個(gè)版本以確保單個(gè)事務(wù)的隔離。PostgreSQL使用MVCC的變種：快照隔離（SI）。
PostgreSQL實(shí)現(xiàn)SI的方式：一個(gè)新的數(shù)據(jù)項(xiàng)被直接插入到相關(guān)的表頁中，當(dāng)讀取條目時(shí)，PostgreSQL通過應(yīng)用可見性檢查規(guī)則來選擇條目的適當(dāng)版本以響應(yīng)單個(gè)事務(wù)。
SI不允許ANSI SQL-92標(biāo)準(zhǔn)中定義的三種異常，即臟讀、不可重復(fù)讀和幻讀。SI不能實(shí)現(xiàn)真正的序列化，因?yàn)樗试S序列化異常，如寫傾斜和只讀事務(wù)傾斜。注意，基于經(jīng)典串行性定義的ANSI SQL-92標(biāo)準(zhǔn)并不等同于現(xiàn)代理論中的定義。為處理此問題，PostgreSQL在9.1版時(shí)添加了可序列化快照隔離(SSI)。SSI可以檢測(cè)到序列化異常，并解決由序列化異常引起的沖突。因此，PostgreSQL 9.1及以后版本提供了一個(gè)真正的SERIALIZABLE隔離級(jí)別。
PostgreSQL DML使用SI，DDL使用2PL。
PostgreSQL的事務(wù)隔離級(jí)別

事務(wù)ID

開始一個(gè)事務(wù)時(shí)，事務(wù)管理器分配一個(gè)唯一標(biāo)識(shí)符，稱為事務(wù)ID（txid）。txid是32位的無符號(hào)整型。開始一個(gè)事務(wù)后，可以使用內(nèi)置函數(shù) txid_current() 查詢當(dāng)前的事務(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ù)庫集簇時(shí)使用
2：Frozen txid，事務(wù)ID回卷問題相關(guān)

txid可以相互比較。如，txid=100時(shí)，大于100的txid是不可見的，小于100的txid是可見的。
由于txid空間在實(shí)際系統(tǒng)中不足，PostgreSQL將txid空間視為一個(gè)圓。但這會(huì)引起事務(wù)ID回卷問題，在后面介紹。

事務(wù)ID.png

元組結(jié)構(gòu)

表頁中的堆元組分為普通數(shù)據(jù)元組和TOAST元組，這里介紹普通數(shù)據(jù)元組。
堆元組包含HeapTupleHeaderData，NULL bitmap，User data。

元組結(jié)構(gòu).png

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，當(dāng)前事務(wù)執(zhí)行了多少SQL命令，起始值為0。如，一個(gè)事務(wù)有三個(gè)insert語句，則第一個(gè)命令insert了元組，t_cid=0，第二個(gè)命令insert元組，t_cid=1，以此類推
t_ctid：保存了一個(gè)元組標(biāo)識(shí)符（tid），它指向自身或一個(gè)新元組

插入，刪除，更新元組

元組.png

• 插入
  在insert操作中，新元組寫入目標(biāo)表的頁。

  
  
  insert操作.png
  
  

  假設(shè)txid為99的事務(wù)insert了一個(gè)元組到頁面，則該元組頭部信息如下：
  Tuple_1：
  t_xmin 設(shè)為99，該元組由txid為99的事務(wù)寫入
  t_xmax 設(shè)為0，該元組未被delete和update
  t_cid 設(shè)為0，該元組為txid為99事務(wù)的第一個(gè)元組
  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)

• 刪除
  在刪除操作中，目標(biāo)元組在邏輯上刪除。執(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中被稱為死元組。死元組最終會(huì)被從頁面中刪除，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í)行第一個(gè)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í)行第二個(gè)update后，如同第一個(gè)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）
  當(dāng)插入堆元組或索引元組時(shí)，PostgreSQL使用相應(yīng)的表，索引FSM來選擇可被寫入的頁。
  所有表和索引有FSM，每個(gè)FSM在對(duì)應(yīng)的表或索引文件中存儲(chǔ)每個(gè)頁面的可用空間信息。所有FSM都以"fsm"后綴存儲(chǔ)，必要時(shí)將它們加載到共享內(nèi)存中。

提交日志（clog）

PostgreSQL在clog中存儲(chǔ)事務(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個(gè)或多個(gè)8KB的頁面組成。clog在邏輯上構(gòu)成一個(gè)數(shù)組。數(shù)組的索引對(duì)應(yīng)各自的事務(wù)ID，數(shù)組的每一項(xiàng)保存事務(wù)ID相應(yīng)的狀態(tài)。

  
  
  clog.png
  
  

  當(dāng)當(dāng)前事務(wù)ID一直增長(zhǎng)，而clog不能再保存它時(shí)，會(huì)增加一個(gè)新頁面。
  當(dāng)需要讀取事務(wù)的狀態(tài)時(shí)，內(nèi)存函數(shù)會(huì)被調(diào)用。這些函數(shù)讀取clog并返回請(qǐng)求的事務(wù)的狀態(tài)。

• 維護(hù)Clog
  當(dāng)PostgreSQL停止運(yùn)行或checkpoint進(jìn)程運(yùn)行時(shí)，clog數(shù)據(jù)會(huì)寫到文件中，這些文件保存在pg_clog目錄下。文件的最大大小為256KB，如，當(dāng)clog使用了8個(gè)頁面（總大小64KB），數(shù)據(jù)會(huì)被保存到一個(gè)文件，當(dāng)clog使用了37個(gè)頁面（總大小296KB），數(shù)據(jù)會(huì)被保存到兩個(gè)文件，一個(gè)文件保存256KB，一個(gè)40KB。
  當(dāng)PostgreSQL啟動(dòng)時(shí)，保存在pg_clog目錄下文件的數(shù)據(jù)會(huì)被加載，以初始化clog。
  clog被寫滿后，會(huì)增加新頁面，然后clog大小會(huì)持續(xù)增長(zhǎng)。但是，不是所有clog數(shù)據(jù)都是必要的，VACUUM會(huì)定時(shí)刪除舊數(shù)據(jù)（同時(shí)刪除clog頁和文件）。
• 事務(wù)快照
  事務(wù)快照是一個(gè)數(shù)據(jù)集，它存儲(chǔ)了關(guān)于單個(gè)事務(wù)在某一時(shí)間點(diǎn)是否所有事務(wù)都處于活動(dòng)狀態(tài)的信息。在這里，活動(dòng)事務(wù)意味著它正在進(jìn)行或尚未啟動(dòng)。
  PostgreSQL內(nèi)部定義事務(wù)快照的文本表示格式為'100:100:'。如，’100:100:‘表示txid<100的事務(wù)是不活躍的，txid>=100是活躍的。
• txid_current_snapshot內(nèi)置函數(shù)
  txid_current_snapshot函數(shù)顯示當(dāng)前事務(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，所有大于或等于這個(gè)值的txid在快照時(shí)間點(diǎn)還未啟動(dòng)，所以不可見
xip_list：在快照時(shí)間點(diǎn)活躍的txid，只包含在xmin,xmax之前的活躍txid
如：快照'100:104:100,102'，xmin=100，xmax=104，xip_list=100,102

事務(wù)快照.png

事務(wù)管理器和事務(wù).png

可見性檢查規(guī)則

可見性檢查規(guī)則是一組規(guī)則，它利用元組的t_xmin，t_xmax，clog，獲取的事務(wù)快照，來確定每個(gè)元組是否可見。這些規(guī)則比較復(fù)雜，這里只介紹需要的最小規(guī)則。在下文中，我們省略了與子事務(wù)相關(guān)的規(guī)則，并忽略了關(guān)于t_ctid的討論，即我們不考慮在事務(wù)中更新兩次以上的元組。

• t_xmin狀態(tài)為中止（ABORTED）
  元組的t_xmin狀態(tài)為中止時(shí)，該元組始終不可見，因?yàn)閕nsert該元組的事務(wù)已經(jīng)被中止。

 /* t_xmin status == ABORTED */
Rule 1: IF t_xmin status is 'ABORTED' THEN
                  RETURN 'Invisible'
            END IF

該規(guī)則的數(shù)學(xué)表達(dá)式表示為：
Rule 1: If Status(t_xmin) = ABORTED ? Invisible

• t_xmin狀態(tài)為進(jìn)行中（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，則該元組對(duì)當(dāng)前事務(wù)不可見。
Rule 3: 如果元組的t_xmin等于當(dāng)前的txid（該元組是由當(dāng)前事務(wù)插入），并且t_xmax不是INVALID，則該元組對(duì)當(dāng)前事務(wù)不可見，它已經(jīng)被當(dāng)前事務(wù)刪除或者更新。
Rule 2: 如果元組是由當(dāng)前事務(wù)插入并且t_xmax為INVALID，則元組對(duì)當(dāng)前事務(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，此時(shí)元組對(duì)當(dāng)前事務(wù)可見。
Rule 5：t_xmin在獲取的事務(wù)快照中是活躍的，這種情況下，元組是不可見的，因?yàn)楸划?dāng)做IN_PROGRESS。
Rule 7：t_xmax等于當(dāng)前txid，在這個(gè)條件下，結(jié)合Rule 3，元組不可見，元組已經(jīng)被當(dāng)前事務(wù)刪除或更新。
Rule 8：t_xmax狀態(tài)為IN_PROGRESS且不等于當(dāng)前txid時(shí)，元組可見，因?yàn)樵M未被刪除。
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
  
  

  上圖場(chǎng)景中，SQL命令的執(zhí)行順序如下：
  T1時(shí)間點(diǎn)：開始事務(wù) txid=200
  T2時(shí)間點(diǎn)：開始事務(wù) txid=201
  T3時(shí)間點(diǎn)：txid 200,201執(zhí)行select命令
  T4時(shí)間點(diǎn)：txid 200 執(zhí)行update命令
  T5時(shí)間點(diǎn)：txid 200,201執(zhí)行select命令
  T6時(shí)間點(diǎn)：txid 200 執(zhí)行commit
  T7時(shí)間點(diǎn)：txid 201執(zhí)行select命令
  以上開始了兩個(gè)事務(wù)，txid 200，201，其中txid 200的隔離級(jí)別為READ COMMITTED，txid 201隔離級(jí)別模擬為READ COMMITTED，REPEATABLE READ。
  下面我們看下SELECT語句如何對(duì)每個(gè)元組進(jìn)行可見性檢查的。
  T3 Select命令：
  此時(shí)只有Tuple_1，通過Rule 6，我們知道該元組是可見的，所以兩個(gè)事務(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隔離級(jí)別為READ COMMITTED時(shí)，由于txid 200已提交，此時(shí)txid 201獲取的事務(wù)快照為 '201:201:'，所以，Tuple_1不可見(Rule 10)，Tuple_2可見(Rule 6)，此時(shí)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
  這個(gè)結(jié)果與之前txid 200提交前的結(jié)果是不一致的，此現(xiàn)象稱為不可重復(fù)讀。
  txid 201隔離級(jí)別為REPEATABLE READ時(shí)，事務(wù)快照還是 '200:200:'，所以，Tuple_1可見(Rule 9)，Tuple_2不可見(Rule 5)，select返回 'Jekyll'。REPEATABLE READ不會(huì)出現(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隔離級(jí)別的幻讀
  ANSI SQL-92標(biāo)準(zhǔn)中定義的REPEATABLE READ允許幻讀。然而，PostgreSQL的實(shí)現(xiàn)不允許它們。原則上，SI不允許幻讀。
  開啟兩個(gè)事務(wù)，事務(wù)A txid 14567，事務(wù)B txid 14568，隔離級(jí)別分別為READ COMMITTED，REPEATABLE READ。在事務(wù)A插入一行數(shù)據(jù)并提交，然后在事務(wù)B執(zhí)行select語句查詢，結(jié)合Rule 5，此時(shí)事務(wù)A插入的數(shù)據(jù)對(duì)于事務(wù)B不可見。所以幻讀不會(huì)出現(xiàn)。
  Rule5(new tuple): Status(t_xmin:14567) = COMMITTED ∧ Snapshot(t_xmin:14567) = active ? Invisible

  
  
  REPEATABLE READ.png

防止丟失更新

丟失更新，也稱為寫寫沖突，是并發(fā)事務(wù)更新相同行時(shí)發(fā)生的異常，必須在REPEATABLE READ和SERIALIZABLE級(jí)別上防止。(READ COMMITTED級(jí)別不需要防止丟失更新)。

• 并發(fā)事務(wù)更新的表現(xiàn)
  以下是更新命令執(zhí)行時(shí)，調(diào)用的ExecUpdate函數(shù)的偽代碼。

(1)  FOR each row that will be updated by this UPDATE command // 獲取UPDATE命令會(huì)更新的每一行
(2)       WHILE true // 循環(huán)直到目標(biāo)行被更新或者事務(wù)被中止

               /* The First Block */
(3)            IF the target row is being updated THEN // 目標(biāo)行正在更新，進(jìn)入以下代碼塊
                      // 等待更新目標(biāo)行的事務(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
                                // 如果更新目標(biāo)行的事務(wù)提交了，中止當(dāng)前事務(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
                      // 目標(biāo)行已經(jīng)被其他并行事務(wù)更新
(9)               IF (the isolation level of this transaction is READ COMMITTED THEN
                               // 如果隔離級(jí)別為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. */
                      // 目標(biāo)行未被終止的事務(wù)更新，則更新目標(biāo)行
(12)                  UPDATE the target row
                END IF
           END WHILE 
      END FOR 

ExecUpdate.png

沖突情況.png

序列化快照隔離（SSI）

Serializable Snapshot Isolation (SSI)從9.1版開始就被嵌入到SI中，以實(shí)現(xiàn)真正的Serializable隔離級(jí)別。

• 實(shí)現(xiàn)SSI的基礎(chǔ)策略
  如果在優(yōu)先圖中出現(xiàn)了帶有一些沖突的循環(huán)，則會(huì)出現(xiàn)序列化異常。這可以用最簡(jiǎn)單的異常來解釋，即寫傾斜。

  
  
  寫傾斜時(shí)間表.png
  
  

  如上圖，事務(wù)A讀取Tuple_B，事務(wù)B讀取Tuple_A，然后，事務(wù)A寫Tuple_A，事務(wù)B寫Tuple_B，在這種情況下，出現(xiàn)了兩個(gè)讀寫沖突。
  從概念上來講，有三種類型的沖突：寫讀沖突(臟讀)，寫寫沖突(丟失更新)，讀寫沖突。臟讀在PostgreSQL中不會(huì)出現(xiàn)，丟失更新PostgreSQL已處理，SSI只需處理讀寫沖突。
  PostgreSQL實(shí)現(xiàn)SSI使用以下策略：

1. 事務(wù)訪問到的所有對(duì)象(元組，頁面，關(guān)系)記錄為SIREAD鎖。
2. 在寫任何堆或索引元組時(shí)，使用SIREAD鎖檢測(cè)讀寫沖突。
3. 如果通過檢查檢測(cè)到的讀寫沖突檢測(cè)到序列化異常，則中止事務(wù)。

• PostgreSQL實(shí)現(xiàn)SSI
  SIREAD鎖：SIREAD鎖在內(nèi)部稱為謂詞鎖，它是一對(duì)對(duì)象和(虛擬)txids，用于存儲(chǔ)關(guān)于誰訪問了哪個(gè)對(duì)象的信息。
  例如，txid 100讀取目標(biāo)表的Tuple_1，SIREAD鎖 {Tuple_1, {100}} 創(chuàng)建。如果另一個(gè)事務(wù) txid 101，讀取Tuple_1，則SIREAD鎖更新為 {Tuple_1, {100,101}}。SIREAD鎖也能在索引頁被創(chuàng)建，當(dāng)僅索引掃描時(shí)。
  SIREAD鎖有三個(gè)級(jí)別：元組，頁，關(guān)系。如果創(chuàng)建了單個(gè)頁面中所有元組的SIREAD鎖，則將它們聚合為該頁面的單個(gè)SIREAD鎖，并釋放(刪除)相關(guān)元組的所有SIREAD鎖，以減少內(nèi)存空間。讀取所有頁面也是如此。
  當(dāng)為索引創(chuàng)建SIREAD鎖時(shí)，開始將創(chuàng)建頁級(jí)SIREAD鎖。當(dāng)使用順序掃描時(shí)，從一開始就創(chuàng)建關(guān)系級(jí)SIREAD鎖，而不管是否存在索引和/或WHERE子句。注意，在某些情況下，此實(shí)現(xiàn)可能導(dǎo)致對(duì)序列化異常的誤報(bào)檢測(cè)。
  讀寫沖突：讀寫沖突是一個(gè)SIREAD鎖和兩個(gè)讀寫SIREAD鎖的txid的三元組。
• SSI執(zhí)行
  這里介紹SSI如何解決寫傾斜異常。

// 準(zhǔn)備以下表
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

測(cè)試以下場(chǎng)景，假設(shè)所有命令使用索引掃描，則將讀取堆及索引頁：

寫傾斜.png

SIREAD鎖和讀寫沖突.png

上圖中：
T1時(shí)間點(diǎn)，事務(wù)A讀取Tuple_2000，內(nèi)部函數(shù)創(chuàng)建了L1,L2 SIREAD鎖，分別關(guān)聯(lián)Pkey_2, Tuple_2000。
T2時(shí)間點(diǎn)，事務(wù)B讀取Tuple_1，內(nèi)部函數(shù)創(chuàng)建了L3,L4 SIREAD鎖，分別關(guān)聯(lián)Pkey_1, Tuple_1。
T3時(shí)間點(diǎn)，事務(wù)A更新Tuple_1，內(nèi)部函數(shù)創(chuàng)建讀寫沖突 C1，它是事務(wù)B和事務(wù)A之間的Pkey_1和Tuple_1的沖突，因?yàn)镻key_1和Tuple_1都是由事務(wù)B讀取和事務(wù)A寫入的。
T4時(shí)間點(diǎn)，事務(wù)B更新Tuple_2000，內(nèi)部函數(shù)創(chuàng)建讀寫沖突 C2，它是事務(wù)B和事務(wù)A之間的Pkey_2和Tuple_2000的沖突。
在這個(gè)場(chǎng)景中，C1和C2在優(yōu)先圖中創(chuàng)建一個(gè)循環(huán)。因此，事務(wù)A和事務(wù)B處于非序列化狀態(tài)。但是，事務(wù)A和事務(wù)B兩個(gè)事務(wù)都沒有提交，因此事務(wù)B不會(huì)被中止。這是因?yàn)镻ostgreSQL的SSI實(shí)現(xiàn)是基于first-committer-win方案。
T5時(shí)間點(diǎn)，事務(wù)A提交。
T6時(shí)間點(diǎn)，事務(wù)B提交，由于讀寫沖突和first-committer-win方案，事務(wù)B被中止。

寫傾斜測(cè)試.png

需要維護(hù)流程

PostgreSQL并發(fā)控制機(jī)制需要以下維護(hù)流程：

1. 刪除死元組和指向關(guān)聯(lián)死元組的索引元組
2. 刪除clog不需要的數(shù)據(jù)
3. 凍結(jié)舊txid
4. 更新FSM, VM和統(tǒng)計(jì)信息
   其中1，2已在前面介紹，3關(guān)聯(lián)事務(wù)ID回卷問題。

• 凍結(jié)處理
  假設(shè)txid 100寫入元組Tuple_1，則Tuple_1的t_xmin為100，服務(wù)器已經(jīng)運(yùn)行了很長(zhǎng)時(shí)間，Tuple_1沒有被修改。當(dāng)前txid為2³¹+100，然后執(zhí)行SELECT語句。這個(gè)時(shí)間點(diǎn)，Tuple_1可見，因?yàn)閠xid 100在past部分，再將執(zhí)行select語句，此時(shí)當(dāng)前txid為txid為2³¹+101。而Tuple_1不可見，因?yàn)閠xid 100在future部分。這個(gè)問題在PostgreSQL稱為事務(wù)ID回卷問題。
  
  回卷問題.png
  
  為了處理這個(gè)問題，PostgreSQL引入了凍結(jié)txid的概念，并實(shí)現(xiàn)了FREEZE進(jìn)程。
  一個(gè)凍結(jié)txid，是一個(gè)特殊的保留txid 2，被定義為總是比其他所有txid更早。換句話說，凍結(jié)的txid總是不活躍和可見的。
  FREEZE進(jìn)程被VACUUM進(jìn)程調(diào)用。FREEZE進(jìn)程掃描所有表文件，如果t_xmin比當(dāng)前txid - vacuum_freeze_min_age(默認(rèn)為5千萬)的值老時(shí)，F(xiàn)REEZE進(jìn)程重寫元組的t_xmin為凍結(jié)txid。
  在版本9.4及以后的版本，XMIN_FROZEN被寫到元組的t_infomask字段，而不是重寫t_xmin為凍結(jié)id。