《A Critique of Snapshot Isolation》

《A Critique of ANSI SQL Isolation Levels》論文中第一次提出了Snapshot Isolation隔離級别（後面簡稱為SI）。傳統OLTP資料庫，在實作SI時通過行鎖來解決WW沖突防止LostUpdate的問題，通過SI能達到RC和RR隔離級别（嚴格意義上說SI和RR之間沒有可比較性，SI有A5B的異象，而RR的定義中沒有這個問題；同時RR有P3的異象）。

在lock-based的SI基礎上要實作串行化隔離級别，還要解決A5B的問題，需要引入其他機制來檢測RW，PostgreSQL通過SIRead結構記錄每個事務操作的對象（表，頁面，Tuple，索引頁）并檢測是否存在環。

SI+RW檢測是串行化的充分不必要條件，存在誤判的case。

Percolator本質上是把單機lock-based的SI進行了擴充：

1. LOCK COLUMN：對應單機的行鎖，Prewrite階段通過LOCK來檢測WW沖突；
2. WRITE COLUMN：對應單機的CLog，分布式下通過随機選取一個key做為Primary，事務的原子送出發生在這個key上，然後再異步的更新其他key的WRITE COLUMN，加速後續讀取；

本文提出了lock-free的Write Snapshot Isolation隔離級别，符合串行化隔離的排程要求。核心思想是檢測RW沖突，并論述了在這個算法中WW沖突是不必要的。另外，Write-SI是串行化隔離的充分不必要條件，是以它也存在誤判的case。

Write-SI系統需要有一個元件來檢測RW沖突，記錄所有最近送出的WriteSet。

FoundationDB實作了分布式的Write-SI，把對RW檢測的元件也做成了分布式化，按照key rangge進行了切分。

下面是正文。

Abstract

SI沒有達到串行化隔離級别，開發者仍然需要考慮非串行化的異象。

Google Percolator在BigTable上進行了事務的支援，它是lock-based snapshot isolation。而本文提出了lock-free的write-snapshot isolation，它支援串行化隔離，基礎的想法是檢測RW沖突。

1. Introduction

SI的好處是讀寫互相不阻塞，在寫事務更新時讀事務可以讀取某個版本進而不會被寫事務阻塞。存在WW沖突的問題：并發事務更新同一行。

WW沖突一個顯而易見的解法是在更新一行之前對這個行上鎖，就是所謂的行鎖。一個長事務可能會更新大量的行，是以行鎖被記錄到了Tuple所屬的頁面中，會随着頁面刷髒一起被刷到盤上。如果存在WW沖突則abort（PG中根據事務隔離級别是RC還是RR來決定是否abort）。

對于ReadOnly的事務無需維護額外的鎖。

在上述基礎上實作串行化還需進一步檢測RW沖突，可以看到不僅要檢測WW還要檢測RW沖突才能達到串行化。

本文論述WW檢測并不是串行化的必要條件，僅僅做RW檢測就能提供串行化隔離，同時RW的并發性和WW的并發性相當。

2. Snapshot Isolation

上圖中，

1. 事務TXNn能讀取TXNo的更新；
2. TXNn和TXNc都更新了r，同時也是并發的事務，是以兩者要abort一個;

SI中每個事務對應2個timestamp：

1. 事務開始時間（在發生read之前），Ts(txni);
2. 事務送出時間（在commit之前）Tc(txni)；

WW沖突的條件：

1. Spatial overlap：修改了一個r；
2. Temporal over：并發執行Ts(txni) < Tc(txnj) and Ts(txnj) < Tc(txni)；

2.1 Lock-based Implementation of Snapshot Isolation

未送出資料直接寫入DB，此時這些資料的版本為事務開始時的時間戳。

Percolator有3個COLUMN和事務相關：

1. LOCK COLUMN: 事務送出時寫本項，并記錄 primary key的位置。事務成功送出後，該記錄會被清理；
2. DATA COLUMN：存儲實際使用者資料；
3. WRITE COLUM：記錄事務送出時的timestamp，關鍵在于WRITE COLUMN，隻有該列正确寫入後，事務的修改才會真正被其他事務可見。讀請求會首先在該 COLUMN中尋找最新一次送出的 start timestamp,這決定了接下來從 DATA COLUMNI的哪個版本的key讀取最新資料；

Client端執行2PC過程如下；

1. Prewrite：用戶端首先從 Oracle擷取全局唯一時間戳作為目前事務的start_ts，從所有key中選出一個作為primary。并将所有的 key/value資料寫入請求并行地發往對應的存儲節點。存儲節點需要檢測WW沖突：從 WRITE COLUMN列中擷取目前key的最新資料，若其commit_ts大于等于start_ts，說明在該事務的更新過程中其他事務送出過對該key的修改，傳回 Write Conflict錯誤；然後檢查key是否已被鎖，如果是，傳回 Keylslock的錯誤；如果沒有沖突，則向LOCK COLUMN寫入鎖資訊；
2. Commit階段：從Oracle擷取時間戳作為事務的送出時間commit_ts；向primary key所在的存儲節點發送 commit請求，并寫入WRITE COLUMN；步驟2正确完成後該事務即可标記為成功，接下來異步并行地向 secondary keys所在的節點發送 commit請求；

鎖清理的關鍵是識别出鎖是否由一個失敗事務殘留下來的垃圾鎖。

2.2 Lock-free Implementation of Snapshot Isolation

在lock-free的實作中需要一個組價來決策事務間是否存在Spatial overlap和Temporal overlap。

3. Serializability

3.1 Is Write-write Conflict Avoidance Sufficient for Serializability?

WW沖突檢測不是串行化的充分條件，比如前面提到的A5B write skew：

H1. r1[x] r2[y] w1[y] w2[x] c1 c2

3.2 Is Write-write Conflict Avoidance Necessary for Serializability?

WW沖突檢測不是串行化的必要條件，它需要阻止Lostupdate問題：

H3. r1[x] r2[x] w2[x] w1[x] c1 c2

WW沖突檢測會誤判：

H4. r1[x] w2[x] w1[x] c1 c2

H4中事務2并沒有read(x)，直接write(x)，而且事務1和事務2都是并發的關系，是以WW會abort其中一個；

H4的執行順序和H5是等價的（事務執行速率稍微慢一點）：

H5. r1[x] w1[x] c1 w2[x] c2

而H5是并沒有産生Lostupdate問題。

事務1一旦送出就應該被事務2讀取到，H5是合法的執行。

WW沖突檢測對于直接寫的事務會誤判。

4. Read-Write vs. Write-Write

将事務分成讀和寫兩個階段：

1. read snapshot isolation：事務的讀階段不會被中斷，寫會被中斷（檢測到了WW沖突）；
2. write snapshot isolation：事務的寫階段不會被中斷，讀階段會被中斷（檢測到了RW沖突）；

4.1 Write-Snapshot Isolation

RW沖突的條件：

1. RW-spatial overlap: 事務txnj 寫r同時事務 txni讀取r；

2. RW-temporal overlap: 事務txni和事務txnj是并發關系，Ts(txni) < Tc(txnj) < Tc(txni)；

   總結：事務j在事務i的生命周期内修改了事務i的讀集合。

注意：RW-temporal overlap和前面的不同，下圖中TXNn和TXNc''在RW-temporal overlap并不構成沖突，因為TXNc''對TXNn中讀集合的修改，并沒有在事務TXNn的生命周期中得到送出。而TXNn在TXNc''的生命周期送出了，但是他卻沒有修改TXNc''的讀集合（為空）。

事務TXNc'寫集合和TXNn沖突，并且是在TXN的生命周期得到了送出，是以存在RW沖突（如果串行執行事務TXNn本應該可能讀取到最新的r，也可能不應該讀取，但是為了防止萬一，仍然需要abort，此處也是RW的誤判原因）；

事務TXNc雖然和TXNn都修改了相同的寫集合（滿足ReadSnapshot的WW沖突），但是并沒有修改讀集合，是以不滿足RW沖突，這兩個事務可以得到串行化的效果（事務TXNc先送出了更改了r'，随後事務TXNn也修改了r'，這是允許的）；

可以看到RW允許隻有寫沒有讀的事務間的并發執行，而WW不允許。

Read-only transactions

隻讀事務是指寫集合為空，隻讀事務不會被abort。

4.2 Is Read-write Conflict Avoidance Sufficient for Serializability?

為了證明Write-SI是串行化的，需要把每種場景的執行history都映射到串行化的執行history。

Write-SI阻止了RW沖突，而通過快照讀取到的内容是不變的，是以可對事務進行如下變換：

1. 對于寫事務，commit order不變；
2. 事務内部讀寫操作順序不變；
3. 所有隻讀的操作可以等價的向左移動到事務開始的時間點（隻要拿到了一個快照，無論何時讀取，内容都是一樣的）；
4. 所有寫操作向右移動到commit時間點；

總結：所有事務在時間軸上可以變換成隻有2個點：

1. 事務start時間點：對應所有讀操作；
2. 事務commit時間點：對應所有寫操作；

Read-Only事務

下圖中：TXNr的read操作可等價的移動到事務開始時間點，那麼TXNc本來是在TXNr的事務執行期間得到了送出修改了它的讀集合，通過等價變化後，TXNr的執行時間變成了無窮小，是以也就不會被其他事務修改其讀集合。是以，所有read-only事務都不會被abort掉。

Write-Only事務

下圖中：

Lemma 1. History serial(h) is serial.

在時間軸上：

隻讀和隻寫事務變換成了一個點；

讀寫事務變換成了一個線段；

RW阻止了線段之間的交集；

是以，RW排程等價于串行執行；

RW能阻止LostUpdate問題，比如：

事務1寫入x，并先commit，修改了事務2執行期間的x，是以會被RW阻止。

4.3 Is Read-write Conflict Avoidance Necessary for Serializability?

Write-SI的一個優勢是，允許在标準SI下被誤判的排程順序被執行，比如：

H4. r1[x] w2[x] w1[x] c1 c2 -- SI阻止此History

SI誤判的原因是：事務1和事務2都修改了x，但是事務2并沒有讀取操作不存在RR的問題。

同理，Write-SI也會出現誤判，比如：

H6. r1[x] r2[z] w2[x] w1[y] c2 c1 -- Write-SI阻止次History

H6的執行順序存在RW沖突會被阻止，事務2修改了事務1的讀集合；

而如果使用下面H7的排程順序，先放行事務1，再放行事務2，事務1并沒有修改事務2的讀集合，是以不存在沖突；

出現誤判的原因是：

事務2修改了事務1的讀集合，而事務1沒有修改事務2的讀集合，此時依賴排程順序。

H7. r1[x] w1[y] c1 r2[z] w2[x] c2

也就是：SI和Write-SI都會出出現誤判，誤判的機率依賴實際的workload。

5. Lock-free Implementation of Write-snapshot Isolation

lock-free的實作需要一個中心化的元件status oracle server來做RW檢測，RW中的讀集合是指真正被事務讀取到的keys，而不用關心事務的搜尋條件。

相比于SI，Write-SI的commit消息會比較大因為多出了Rr讀集合。

5.1 Read-only Transactions

不管是SI還是Write-SI對隻讀事務的處理是一樣的。

5.2 Analytical Traffic

對于分析型的查詢，通常會讀取大量的資料，那麼讀集合會很大，可以使用描述性表達式來描述讀集合。另外，對于AP場景大查詢通常是隻讀事務。

6. Evaluation

在壓力不高時WW和RW性能相當；壓力大時RW比WW慢一點，原因是在RW沖突檢測時先load讀集合，然後load寫集合；而WW檢測直接load寫集合；

下圖在測試zipfian測試時，RW性能稍弱，原因是該測試的讀集合是從剛剛寫入集合中選取，增大了RW沖突機率。

status oracle server中需要在記憶體中存最近送出事務，為了防止記憶體耗盡：隻處理最近一段時間的事務Tmax。清理Tmax之前事務所占用的記憶體，所有在Tmax之前的長事務直接abort掉。

此外，status oracle server為了能做failover，需要把commit的資訊寫入自己的WAL日志中。同理，為了高可用可對WAL進行複制。

7. FoundationDB的實作

FoundationDB實作了一個分布式的Write-SI：

1. 使用KeyRange将RW檢測分散到多個Resolver程序上；
2. Resolver程序是無狀态的，狀态從LS上擷取；
3. 為了解決lastCommit記憶體問題，隻允許5s的事務，是以Resolver可以清理超過5秒的資料了；