PostgreSQL串列化隔離級別(SSI)的能力與實現

05-25

PostgreSQL9.1是第一個採用Serializable Snapshot Isolation（SSI）實現串列化隔離級別的生產級資料庫。本文是對相關論文與文檔的學習筆記，目標是分析與學習SSI的設計，以及在PG中的實現與優化。本文首先介紹了隔離級別以及實現其的兩個基本並發控制機制、給出了PG的SI未達到串列化的案例並分析原因與給出直觀的解決思路，其次闡述了SSI的技術思路與關鍵環節，最後就PG下SSI的實現與優化進行了分析。

1.SI的異常現象與直觀分析

1.1隔離性與其實現機制

隔離性

隔離性是事務的關鍵特徵之一，用於保證並發訪問時的數據一致性。如果一個並發操作序列與一個串列序列的結果相同，則認為此並發操作的結果是一致性（資料庫只在此層面保證一致，語義的一致由應用保證）。兩個事務對相同數據對象的寫寫（WW）、寫讀（WR）、讀寫（RW）操作存在衝突，讀讀（RR）操作無衝突。

對於衝突的序列，需要資料庫進行並發控制，使其不發生（或者發生後回滾）。鎖機制和Snapshot機制是實現該並發控制的基礎設施。

S2PL（謂詞鎖）可實現串列化，但卻有較大的性能負擔。為了平衡性能與正確性，隔離性被分為分為多個等級，每個等級中鎖與Snapshot的處理流程有差異，低等級隔離級別的隔離能力弱但性能負擔小。

基於鎖的並發控制

鎖模式：讀操作申請讀鎖、寫操作申請寫鎖

衝突處理：相同對象的讀寫、寫讀、寫寫會發生衝突，衝突則等待

鎖的粒度：行、頁、表、謂詞（index range）

鎖的持續時間：短-操作結束時結束釋放，長-事務結束時釋放

2PL, S2PL

基於鎖定義的隔離級別

lock based read committed:W操作，長寫鎖，數據對象鎖；R操作，短讀鎖，數據對象鎖
lock based Repeatable read:W操作，長寫鎖，數據對象鎖；R操作，長讀鎖，數據對象鎖
lock based Serializable :W操作，長寫鎖，數據對象鎖+謂詞鎖；R操作，長讀鎖，數據對象鎖+謂詞鎖

基於Snapshot的並發控制

記錄的MVCC結構:PG的記錄鏈表與Innodb的回滾區兩種方式。

Snapshot的數據結構-xmin、xmax、list，含義-可以確定在獲取snapshot的時間點，某事務是否已完成。

Snapshot的獲取時機：每語句-即每條語句獲取一次，每事務-每個事務獲取一次（第一次訪問前）

操作流程:

相同對象讀寫、寫讀不阻塞，寫寫阻塞
讀操作：如果某事務在當前事務獲取snapshot時，已經結束，則某事務的操作結果（插入或刪除）對當前事務可見。
寫操作：First Commit Win。實際採用寫鎖實現，寫操作加鎖，獲取寫鎖後流程與基於鎖的隔離級別不同。獲取寫鎖後的兩種流程：

繼續加鎖型：找到最新的記錄版本，繼續加鎖。
版本檢查型：如果獲取鎖的記錄被不可見，則回滾，否則繼續。

基於Snapshot的隔離級別

snapshot based read committed：W操作，長寫鎖，數據對象鎖。獲取snapshot-每語句，持續加鎖型。
snapshot based Repeatable：W操作，長寫鎖，數據對象鎖。獲取snapshot-每事務，版本檢查型。

資料庫產品中的隔離級別

PG/Oracle

read committed：snapshot based read committed
Repeatable read：snapshot based Repeatable

InnoDB

read committed：snapshot based read committed
Repeatable read：snapshot based Repeatable（使用繼續加鎖而不是版本檢查，不能避免更新丟失）
Serializable：lock based Serializable

1.2 異常案例

PG的snapshot based Repeatable read（下面簡稱SI）可以避免ansi標準中提出的三種具體的異常操作序列，但卻沒有達到串列化級別（SI<< Lock based Serializable）。InnoDB的lock based Serializable實現了串列化級別，可以避免PG的問題。

《A Critique of ANSI SQL Isolation Levels》中給出了異常操作序列的定義，這裡只看其中的6個案例。可以看出PG的SI未達到InnoDB的串列化級別。

讀未提交A1：PG的SI可避免。
不可重複讀A2：PG的SI可避免
幻象A3：PG的SI可避免
更新丟失P4：PG的SI可避免
幻象A3B：PG的SI無法避免，InnoDB串列化可以避免
write skew A5B：PG的SI無法避免，InnoDB串列化可以避免

PostgreSQL

設置PostgreSQL隔離級別

SET SESSION CHARACTERISTICS AS TRANSACTION isolation level serializable;

讀未提交A1：PG的SI可避免。

不可重複讀A2：PG的SI可避免

幻象A3：PG的SI可避免

更新丟失P4：PG的SI可避免

幻象A3B：PG的SI無法避免

write skew A5B：PG的SI無法避免

InnoDB

設置隔離級別

set session transaction isolation level serializable;

幻象A3B：InnoDB串列化可以避免

write skew A5B：InnoDB串列化可以避免

1.3 異常的特點分析與直觀解決思路

SI中，事務內讀到的數據都是一致的（複雜情況也會錯誤，見後），因此可以避免A1、A2和A3，對於A3B和A5B，事務內部讀到的數據也是一致的，但是在外部整體上出現了不一致。

P4與A5B非常類似，都是根據先前的數據，進行寫操作，只是P4的讀與寫是相同對象，A3B的讀與寫是不同對象。P4沒有問題，因為寫操作有版本檢查，這正好可以處理讀到數據發生變化的情況，而A3B中讀寫不同對象，寫操作不能發現讀的數據發生變化。因此SI的讀，需要做登記工作（與lock manager類似，只是不阻塞），用於衝突的判斷。

A3B的操作序列中，讀操作是一個範圍。對這類讀操作登記，需要採用類似於謂詞鎖（range lock）的技術。

根據以上兩點，需要在事務提交時，判斷讀到的數據，是否發生了變化。當發生變化時，一定會導致不一致嗎？不一定，對於只有讀操作的事務，即使其讀到的數據發生了變化，也不一定會影響一致性。因此還需要額外的信息。

S1中讀寫不衝突，是通過讀寫同一數據的不同版本實現的。SI中兩個調度，R1W2（T1讀後T2寫），W2R1（W2先寫T1讀）是等價的，因為W2R1中事務1讀到的數據版本與R1W2相同。

基於鎖的串列化在處理A3B和A5B時，使用了死鎖檢測，發現了操作中的特定的依賴關係。基於SI的串列化需要的額外信息正是此類信息，需要在事務提交前，保存依賴並識別出與死鎖類似的結構，並進行衝突處理。

下面兩部分基於《serializable Snapshot Isolation in PostgreSQL》

2.SSI的技術路線

2.1隻讀事務異常案例與分析

論文中給出了一個違反直覺的只讀事務異常案例。應用為一個事務批處理系統，包括三個事務。receipts表記錄了產生的的receipt（可理解為訂單，多行記錄），control表記錄了一個批處理號（只有一行記錄）。T2（New Receipt）會定時將新的receipt插入receipts表，具體的信息欄位不用關心，只需要關注的批處理號欄位。批處理號為一個整數，該信息被儲存在control表中。T2插入receipts表前，首先會從control表中獲取批處理號，設置為插入記錄的批處理號欄位。T3（Close Batch）會定期更新control表，原有批處理號增一。T1（Report）是一個只讀事務，統計當前批處理號之前的那個批處理信息。

在T1、T2、T3串列執行時，T1每次執行的結果是相同的。而在異常案例中，T1會出現兩次讀到結果不同的異常。

出現異常的原因是，當前批處理號之前的批處理，必須已經完成，這個串列時存在的假設，在並行時被破壞了。在日常生活也會遇到這樣的情況，如統計企業的年度財務報表，不會在新年的第一天，而是要等到所有上一年度的業務全部完成後。

2.2 SI中的讀寫依賴關係

多版本中事務的依賴關係

Adya給出了一種表示多版本中事務讀寫依賴關係的方式。圖中的節點表示事務。從T1指向T2的邊，如T1->T2，表示T1的操作在T2前發生，並可能存在以下的依賴：

理解

WR依賴與WW依賴，均是T1提交後，T2才啟動，T2可以看到T1對數據的修改。

RW反依賴，是T1與T2並發時發生的。T2讀操作，T1寫操作，無論T2讀先執行還是T1寫先執行，依賴關係均是讀操作指向寫操作，因為讀操作讀到的記錄版本比寫操作老。

為什麼不考慮RW依賴？因為讀操作事務提交後，不會對之後啟動的寫操作事務產生影響。

2.2串列理論

定理1

在發生異常有向圖環中，必然存在三個事務T1到T2、T2到T3存在讀寫反向依賴，並且T3最先提交。

推論2

T1與T2並發，T2與T3並發。

採用上述方式描述write skew與只讀事務異常。

write skew依賴圖

只讀事務異常依賴圖

定理的理解

只讀事務異常案例中，依賴關係如定義所述，T1與T2有RW反向依賴、T2與T3有反向依賴，且T3先提交。這裡可以發現，T1與T2哪一個先提交，均會引起異常。

T1與T3可以為相同事務，write skew就是此種情況。

為什麼是T3提交而不是T2先提交呢？從只讀事務異常案例中，可以看出T1與T2先提交均不會引起異常。

推論的理解

推論中說T1與T2並發，T2與T3並發。並不是說T1、T2、T3同時並發。例如，T2與T3並發，T3提交之後，T1才啟動，此時只有T1與T2並發。

因此T3提交後，其與T2的反向依賴關係必須要保留到T1結束。

2.3 SSI大致處理流程

Cahill介紹了一種SSI檢查方法，該方法檢查運行中的事務依賴關係圖，並選擇事務abort，以保證事務的一致性。SSI方法類似於一種基於串列圖檢測的並發控制協議，該協議中跟蹤所有的依賴，並避免cycle的形成。SSI與其不同，SSI只檢測"dangerous structure"，即有一條入邊和一條出邊的結構。當發現此結構時，SSI選擇事務回滾。根據定理1，SSI的方法可以保證串列化，但卻會有誤殺，當僅僅有dangerous structure而沒有cycle時。SSI的好處是，不需要記錄WR和WW依賴，同時dangerous structure的識別要比cycle檢測工作量小很多。

與S2PL和OCC相比，SSI並發性好。在並發事務中，出現一個RW反向依賴時，2PL和OCC都有阻塞，而SSI不會。

SSI需要檢測到多版本讀寫下的衝突的情況，對於讀操作需要加SIREAD鎖（讀寫不阻塞，只用於生成RW反向依賴。與S2PL不同，事務commit後SIREAD不能釋放，因為與該事務之前並發的事務，可能會寫該事務讀過（加SIREAD鎖）的記錄。

SSI的variants

Cahill介紹了一種優化的SSI，可以減少誤殺。原有的SSI只判斷dangerous structure，根據定理1，優化的SSI上增加了T3先提交的判斷。PG的SSI演算法採用了該方法。優化的SSI也存在誤殺，因為並沒有判斷依賴中的cycle。

PSSI記錄了所有的WR、WW依賴與RW反向依賴，可以判斷cycle，從而消除所有的誤殺。PG的SSI因為性能的原因，沒有採用此方法。

2.4 只讀事務的優化

大量的應用場景中，存在只讀事務比例高，執行時間長的特點。SSI讀操作加SIREAD鎖會帶來很大負擔。為對只讀事務進行優化，發展了只讀事務異常的串列化理論。基於該理論，做了兩點優化

採用read-only snapshot ordering優化，減少了誤殺。
識別safe snapshot。採用safe snapshot的只讀事務可以不採用SIREAD鎖。進一步發展出deferrable事務，該事務可以延遲執行以確保採用safe snapshot。

只讀事務串列理論定理3

解釋：當dangerous structure結構被識別後，如果T1是只讀事務，除非T3在T1前提交，否則不會產生異常。對於只讀事務，是否產生異常，與其獲取snapshot的時間有關，與提交無關。

safe snapshot

基於定理3，可得到Safe snapshot。

T1、T2、T3，當前不存在事務T2到T3的RW反依賴，且T3在T1前已經提交，則T1獲取的就是safe snapshot。

safe snapshot不能T1啟動時就完全確定。例如，T1啟動時，T2到T3有RW反向依賴，但T1到T2是否有反向依賴，此時還不確定。PostgreSQL的實現中，T1啟動時，記錄活躍的事務，並採用SIREAD鎖。當所有活躍事務列表事務都結束，且沒有定理3的情況時，T1釋放其獲取的SIREAD，在其後的操作中不再申請SIREAD鎖。

deferrable事務

對於大數量的查詢，根據safe snapshot，T1獲取活躍事務列表後，可以等待列表中的所有事務結束，再啟動查詢，完全避免對SIREAD的獲取。

3.PG中SSI的實現與優化

在BerkeleyDB和InnoDB中已經有SSI的實現，PG中SSI的實現與其不同。由於沒有可以直接利用的鎖管理器，PG中新實現了一個鎖管理器，由於沒有可以直接利用的鎖管理器，在PG上實現SSI難度很大。

3.1基本實現

PG的基本並發控制結構

記錄與索引。記錄採用多版本。沒有原地修改，修改操作轉換為刪除與插入記錄，記錄的版本直接通過ctid連接（老版本指向新版本）。索引沒有版本信息，記錄的索引變化會新建索引項。非索引項的修改，採用hot技術。

可見性。記錄中包含xmin與xmax欄位，分別是插入與刪除的事務。事務是否已提交可以通過clog查詢。如果根據本事務的snapshot查詢，xmin或xmax已經完成且clog的信息為已經提交，則操作效果對本事務可見。

PG中實現了多個類型鎖。SpinLock為忙等Mutex，LWLock為讀寫鎖（有等待，無死鎖檢查，類似latch）， RegularLock為事務級別鎖（有等待，有死鎖檢測），行鎖無衝突時，鎖信息保存在記錄中（通過xmin與xmax狀態表示），有衝突時保存在RegularLock中。

衝突檢測（檢測RW反依賴）

SSI lock manager

鎖模式：只有一個SIREAD類型鎖
鎖的粒度：表、頁、行，意圖鎖採用index page的粒度，未來計劃改進為next-key locking。支持鎖粒度的升級。
未支持意圖鎖。在各個級別依次檢查。
鎖持續的時間：如前面的分析，SIREAD要維持到與本事務一起活躍的事務結束時。
額外的處理

與DDL操作的關係（自己未分析過DDL鎖，未理解，待分析）
數據重組時，鎖的對象的ID（記錄或index）發生變化，鎖的粒度升級為表。

讀寫處理

讀到一個記錄時的處理：當並行事務對該記錄有寫鎖時（通過snapshot查詢，xmin或xmax未完成），產生RW反依賴。
寫一個記錄時的處理：通過SSI lock manager查詢，檢查記錄是否有SIREAD鎖，範圍查詢使用index page的SIREAD鎖。當數據對象有SIREAD鎖時，產生RW反依賴。

衝突跟蹤（事務依賴關係的數據結構）

為每個事務記錄所有的RW反依賴。RW反依賴中指向了關聯的事務。

記錄詳細的信息有利於以下處理。

實現commit ordering優化。見SSI的variants。
只讀事務優化。
發現dangerous structure時的abort處理
內存優化（aggressive清理）

衝突解決

當dangerous structure被識別，且提交順序（定義1中，T3先提交）滿足時，選擇某事務回滾，以避免異常發生。

選擇回滾的事務滿足safe retry原則：該事務被重試時，不應因為原先的情況，再次失敗（不準確，大意）。

safe retry原則：

T3提交後，才考慮回滾事務。
T1與T2中選擇T2回滾，因為T2再次執行不會與已經提交的T3有RW關係，而T1再次執行會與T2再次建立RW關係。
T2與T3都提交的情況下，回滾T2，再次執行T2不會有RW關係。

3.2內存優化

面對問題

與傳統鎖管理器相比，SILOCK和RW反依賴不能在事務結束後釋放，會佔用更多的內存資源。

由於鎖表和事務依賴關係可佔用的內存大小是固定的（配置文件中指定），需要提供降級能力。在長時間運行事務的情況下，系統不應沒有內存資源而拒絕連接，應該通過提高鎖的粒度（這樣會提高誤判率），減少內存佔用，從而能接受新的連接。

PG採用進程間共享內存是使用System V的shared memory。默認配置大小為32M（這點自己不理解）。鎖表的內存大小無法動態分配。

解決方法

（1）safe snapshot和延遲事務降低了長時間運行的只讀事務的影響。

（2）細粒度到粗粒度的鎖對象升級。

（3）aggressive cleanup 已提交事務的狀態。

對於提交事務，其鎖表與RW反依賴要保存多長時間？對於SILOCK，需要保存到與其並發的所有事務結束，而事務依賴的信息需要保留更長的時間。（文章中下面舉的例子感覺有問題，自己理解如下）。定理1中，例如，T2與T3並發，T3提交之後，T1才啟動，此時只有T1與T2並發。因此T3提交後，其提交順序號必須要保留到T1結束。為防止此問題，在事務節點中記錄與其衝突已事務的最早提交順序號。
很明顯，當系統中的活躍事務只有隻讀事務時，已提交事務的SILOCK可以被釋放。
已提交事務的RW反依賴中in的信息可以被丟棄。（自己理解in是寫信息，out是讀信息，應該是out信息可以丟棄）

（4）已提交事務狀態的summarization

PG的SSI中能夠保存的已提交事務數量是固定的。當有更多已提交事務時，需要對已提交事務的信息進行summarize。通常，只需要檢測到當前事務與之前已提交的事務發生了衝突，並不需要知道具體的已提交事務。概括在減少內存佔用的同時，會提高誤判率。

已提交事務狀態的概括是基於以下兩個發現：

活躍事務寫一條記錄時，需要判斷是否某些已提交事務（之前並發的）讀過此記錄。此衝突只需要知道有已提交事務獲取了SILOCK，並不需要知道具體的事務。將已提交事務的SLock關聯到一個dummy lock，並在SILOCK中記錄最新事務的提交順序號，用於釋放SILOCK。
活躍事務讀一條記錄時，需要判斷是否某些已提交事務（之前並發的）寫過此記錄。兩種可能的dangerous structure為：

對於第二種情況，需要知道T3的提交順序。在概括的情況下，由於此信息被丟棄，增加了一個事務號到與其衝突的最老已提交事務號，來解決此問題。

3.3對主要模塊的影響

兩階段提交

顯示兩階段提交時，事務會處於prepared狀態。對於非SI鎖，PG將該prepared事務獲取的鎖會保存在磁碟上，這樣故障恢復時，可以從磁碟中恢復該prepared事務的鎖信息。對於SSI鎖表及事務依賴關係，佔用的容量大，這麼做不可行。

由於Prepared成功的事務必須能提交成功，一個優化思路是在Prepared時，做一致性檢查。通過檢測的事務，需要做summarize。summarization信息是需要保存到磁碟的。

流複製

目前沒有在Slave實現SSI。我理解主要是因為查詢操作不寫日誌，為了在Slave構造鎖表，需要將SI Lock操作寫日誌，有工作量。更重要的是，由於safe snapshot機制，slave可以讀到一致的數據。擴展safe snapshot機制，Master生成Safesnapshot，並通過xlog複製到Slave節點。Slave節點的讀操作使用此Snapshot。

保存點與子事務

自己對於保存點和子事務，未做分析。待處理。

索引類型

目前謂詞鎖是基於B+樹，後面計劃擴展到GiST索引。

3.4 SILOCK加鎖案例分析

執行write skew案例，查看加鎖信息。

創建表、插入數據、查看索引名

create table a5b( a int primary key, b int) ;

insert into a5b values(1,100);

insert into a5b values(2,200);

查看數據文件

SELECT lp, lp_flags, t_xmin, t_xmax, t_ctid,

to_hex(t_infomask), explain_infomask(t_infomask)

FROM heap_page_items(get_raw_page(a5b, 0));

查看索引

SELECT * FROM bt_metap(a5b_pkey);

SELECT * FROM bt_page_items(a5b_pkey, 1);

查看錶與索引的文件oid

select relname, relfilenode from pg_class where relname like a5%;

查詢鎖表

select pid, transactionid, locktype, mode,relation, page, tuple, granted from pg_locks where pid !=pg_backend_pid() and locktype!=virtualxid order by pid, locktype;

可看出兩個會話分別在記錄和索引頁上獲取了SILOCK鎖。

4.參考資料

論文

《A Critique of ANSI SQL Isolation Levels》

《Serializable Snapshot Isolation in PostgreSQL》

書

《Designing Data-Intensive Applications》第7章

《Transaction Processing Concepts and Techniques》第7、8章

-------------------------------------------------------------------------------