最近對 TiDB 特別感興趣麸祷，稍微研究了一下他們應用到的 Percolator 事務模型。

BigTable

BigTable 是一個分布式, 多維, 映射表褒搔。本質上說阶牍，BigTable 是一個鍵值（key-value）映射。主要有三個維度星瘾，分別是行走孽、列、時間戳琳状。

BigTable 存儲映射為：(row:string, column:string, time:int64)→string

從存儲的映射時間戳維度不難看出磕瓷，BigTable 是支持可以多版本控制（MVCC）的。

BigTable支持單行的事務念逞，可以保證一行多列的 ACID 特性困食。明顯單行事務對于一個現(xiàn)代化系統(tǒng)來說略顯不足，Percolator 借助 BigTable 實現(xiàn)了多行的分布式事務翎承。

Percolator事務流程

Percolator事務分為兩個階段：預寫（Pre-write）和提交（Commit）硕盹，本質上相當于一個加強的2PC。

需要應用 Percolator 事務的 BigTable 的表中叨咖，都需要加入下面兩個列族：

• L列： 也就是 Lock 列瘩例，需要記錄該行數(shù)據(jù)的鎖信息
• W列：也就是 Write 列，需要記錄該行數(shù)據(jù) Last Committed 的數(shù)據(jù)版本甸各，用來做版本控制垛贤。

為什么說列族呢？首先 BigTable 一行中每一個列是允許存儲多個時間版本的數(shù)據(jù)趣倾，方便實現(xiàn)例如：讀已提交聘惦、讀未提交、可重復度儒恋、序列化等事務隔離級別部凑。

預寫（Pre-write）

這里引用 Percolator 原文的一個例子露乏，我們需要將 Bob 的賬戶中的 7 元轉給 Joe 的賬戶中。

初始狀態(tài)

首先我們看 bal:write 列涂邀，此時 Bob 和 Joe 最新的一個時間戳版本 6 都指向各自的 data@5瘟仿，說明在 6 這個時間戳版本中： Bob 的賬戶余額有 10 元，Joe 的賬戶余額有 5 元比勉。那么持有大于時間戳 6 的事務進行讀未提交的時候劳较，可以讀到時間戳版本為 5 的 bal:data。

初始狀態(tài)

Pre-Write

在 Percolator 里面浩聋，首先需要把在同一個事務里面多個 Key 隨機選出一個 Primary Key 和多個 Secondary Key观蜗。所在數(shù)據(jù)行分別稱為 Primary Row 和 Secondary Row。

首先進行的是 Primary Row 的 Pre-Write 操作：

1. 從 TSO 拿到當前時間戳 start_ts = 7
2. 檢查 <Bob bal:write> 列衣洁，如果有大于 7 的數(shù)據(jù)版本則提交失敗墓捻，有則說明其他事務已經(jīng)寫入數(shù)據(jù)（寫沖突），沒有則繼續(xù)處理
3. 檢查 <Bob bal:lock> 列坊夫，如果有小于 7 的數(shù)據(jù)版本鎖則提交失敗砖第，有則說明其他事務已經(jīng)占用數(shù)據(jù)，沒有則加鎖繼續(xù)處理
4. 設置 <Bob bal:data 7> 為 3

此時已經(jīng)完成了 Primary Row 的 Pre-Write 操作环凿。2~4 步驟需要在同一個 bigtable 事務里面進行原子操作梧兼。

可能會有疑問為什么在此時已經(jīng)把數(shù)據(jù)列 <Bob bal:data 7> 寫上了？其實由于 <Bob bal:write> 列最新的數(shù)據(jù)還未寫入智听，在其他事務看來羽杰，這屬于未提交內(nèi)容，其他事務可以根據(jù)事務隔離級別有選擇讀取 <Bob bal:data> 的時間戳版本數(shù)據(jù)到推。

Primary Row Pre-Write

那么針對多個 Secondary Row 的 Pre-Write 也與 Primary Row 類似考赛，只是鎖的記錄需要指向 Primary Row 的鎖。這樣子實現(xiàn)了去中心化的鎖管理莉测，把Secondary Lock 與 Primary Lock 關聯(lián)了起來欲虚。

Secondary Row 的 Pre-Write 操作：

1. 拿到 Primary Row 的 Pre-Write 中獲得的時間戳 start_ts = 7。
2. 檢查 <Joe bal:write> 列悔雹，如果有大于 7 的數(shù)據(jù)版本則提交失敗，有則說明其他事務已經(jīng)寫入數(shù)據(jù)（寫沖突）欣喧，沒有則繼續(xù)處理腌零。
3. 檢查 <Joe bal:lock> 列，如果有小于 7 的數(shù)據(jù)版本鎖則提交失敗唆阿，有則說明其他事務已經(jīng)占用數(shù)據(jù)益涧，沒有則加鎖繼續(xù)處理。
4. 設置 <Joebal:data 7> 為 9驯鳖。

多個 key 也是類似闲询，在實際應用場景中久免，可以異步對多個 key 加鎖，加快速度扭弧。

Secondary Row Pre-Write

自此預寫（Pre-write）過程已經(jīng)完成了阎姥！

提交（Commit）

目前為止已經(jīng)把想要修改到的數(shù)據(jù)已經(jīng)加好鎖了，接下來需要進行 Commit 操作鸽捻。

首先進行的是 Primary Row 的 Commit 操作：

1. 從 TSO 拿到當前時間戳 commit_ts = 8呼巴。
2. 檢查 <Bob bal:lock> 列，看鎖是否存在御蒲，不存在則可能已經(jīng)被清除了衣赶，取消事務；存在則繼續(xù)厚满。
3. 以 commit_ts 為版本號府瞄，指向 bal:write 列的 start_ts 對應數(shù)據(jù)版本。也就是把 <Bob bal:write 8> 設置為 data@7碘箍。此步驟完成后遵馆，寫入的數(shù)據(jù)版本已經(jīng)生效，也就是對讀已提交事務可見了敲街。
4. 刪除鎖信息团搞，讓其可寫。

1~3步驟需要在一個 bigtable 事務里面進行原子操作多艇。

Primary Row Commit

Secondary Row 的 Commit 操作與 Primary Row 的類似逻恐。

Secondary Row Commit

隨便聊點

事務隔離級別

與傳統(tǒng)數(shù)據(jù)庫事務隔離級別（讀已提交、讀未提交峻黍、可重復度复隆、可序列化）相比，Percolator 提供了快照隔離級別姆涩。

優(yōu)點：

• 保證事務中的讀操作讀到對應數(shù)據(jù)版本挽拂，避免產(chǎn)生不可重復讀的問題。
• 保證多事務中的寫操作不會更新到同一條記錄骨饿。

缺點也比較明顯：

• 寫傾斜（Write）問題亏栈。
• 樂觀事務會產(chǎn)生寫熱點問題。

鎖管理

Percolator 拋棄中心鎖管理宏赘，把鎖信息分散數(shù)據(jù)當中绒北。通過區(qū)分 Primary 和 Secondary，巧妙的設置了一個標志察署，后續(xù)的異常處理都可以通過這個標簽來進行闷游。

鎖有可能有以下異常：

1. Prewrite 中斷，還進行 primary lock 或者寫 secondary lock 到一半系統(tǒng)崩潰。
2. Commit 中斷脐往，未進行 primary commit 或者 primary commit 到一半系統(tǒng)崩潰休吠。

此時就需要用到鎖清理，鎖清理不需要另外開任務去管理和回收业簿。只需要在讀操作的時候遇到鎖的時候特殊處理即可瘤礁。減輕了鎖維護的成本，也簡化了整個鎖的管理模型辖源。

那是怎么處理的呢蔚携？

每個事務開啟的時候都會從 TSO 獲取事務開始時間 start_ts ，通過判斷某一行數(shù)據(jù)的 lock 列是否在 (0, start_ts] 范圍內(nèi)為兩種情況：

1. 不在克饶；說明此鎖可讀：首先讀取 write 列小于 start_ts 的最大的數(shù)據(jù)酝蜒，然后去讀 data 列。
2. 在矾湃；說明此鎖不可讀亡脑，此時如果按照鎖可讀情況處理的話，可能會產(chǎn)生讀未提交的問題邀跃。

在鎖不可讀的情況下霉咨，也不可能無休止等待，在一定的延遲后拍屑，會進行以下操作：

1. 遇到 primary lock 還在途戒，可以進行鎖清除。
2. 遇到 secondary lock 還在僵驰，檢查 primary lock喷斋。
   1. primary lock 還在，事務 commit 失敗蒜茴，回滾事務
   2. primary lock 不在星爪，事務 commit 已經(jīng)成功了，進行事務前滾（沒錯粉私，就是前滾）顽腾。

Percolator 缺點

1. 由于依賴 TSO，會發(fā)現(xiàn)網(wǎng)絡交互比較多诺核；TiDB 團隊針對退出了 Async Commit抄肖，可以減少網(wǎng)絡交互。
2. 樂觀鎖存在熱點讀寫回滾風暴問題窖杀；TiDB 團隊針對此推出了悲觀事務模型漓摩。
3. 依賴讀清理鎖，會有寫沖突問題陈瘦。