最近對(duì) TiDB 特別感興趣，稍微研究了一下他們應(yīng)用到的 Percolator 事務(wù)模型。

BigTable

BigTable 是一個(gè)分布式, 多維, 映射表。本質(zhì)上說(shuō)，BigTable 是一個(gè)鍵值（key-value）映射。主要有三個(gè)維度，分別是行、列、時(shí)間戳。

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

從存儲(chǔ)的映射時(shí)間戳維度不難看出，BigTable 是支持可以多版本控制（MVCC）的。

BigTable支持單行的事務(wù)，可以保證一行多列的 ACID 特性。明顯單行事務(wù)對(duì)于一個(gè)現(xiàn)代化系統(tǒng)來(lái)說(shuō)略顯不足，Percolator 借助 BigTable 實(shí)現(xiàn)了多行的分布式事務(wù)。

Percolator事務(wù)流程

Percolator事務(wù)分為兩個(gè)階段：預(yù)寫(xiě)（Pre-write）和提交（Commit），本質(zhì)上相當(dāng)于一個(gè)加強(qiáng)的2PC。

需要應(yīng)用 Percolator 事務(wù)的 BigTable 的表中，都需要加入下面兩個(gè)列族：

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

為什么說(shuō)列族呢？首先 BigTable 一行中每一個(gè)列是允許存儲(chǔ)多個(gè)時(shí)間版本的數(shù)據(jù)，方便實(shí)現(xiàn)例如：讀已提交、讀未提交、可重復(fù)度、序列化等事務(wù)隔離級(jí)別。

預(yù)寫(xiě)（Pre-write）

這里引用 Percolator 原文的一個(gè)例子，我們需要將 Bob 的賬戶中的 7 元轉(zhuǎn)給 Joe 的賬戶中。

初始狀態(tài)

首先我們看 bal:write 列，此時(shí) Bob 和 Joe 最新的一個(gè)時(shí)間戳版本 6 都指向各自的 data@5，說(shuō)明在 6 這個(gè)時(shí)間戳版本中： Bob 的賬戶余額有 10 元，Joe 的賬戶余額有 5 元。那么持有大于時(shí)間戳 6 的事務(wù)進(jìn)行讀未提交的時(shí)候，可以讀到時(shí)間戳版本為 5 的 bal:data。

初始狀態(tài)

Pre-Write

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

首先進(jìn)行的是 Primary Row 的 Pre-Write 操作：

1. 從 TSO 拿到當(dāng)前時(shí)間戳 start_ts = 7
2. 檢查 <Bob bal:write> 列，如果有大于 7 的數(shù)據(jù)版本則提交失敗，有則說(shuō)明其他事務(wù)已經(jīng)寫(xiě)入數(shù)據(jù)（寫(xiě)沖突），沒(méi)有則繼續(xù)處理
3. 檢查 <Bob bal:lock> 列，如果有小于 7 的數(shù)據(jù)版本鎖則提交失敗，有則說(shuō)明其他事務(wù)已經(jīng)占用數(shù)據(jù)，沒(méi)有則加鎖繼續(xù)處理
4. 設(shè)置 <Bob bal:data 7> 為 3

此時(shí)已經(jīng)完成了 Primary Row 的 Pre-Write 操作。2~4 步驟需要在同一個(gè) bigtable 事務(wù)里面進(jìn)行原子操作。

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

Primary Row Pre-Write

那么針對(duì)多個(gè) Secondary Row 的 Pre-Write 也與 Primary Row 類似，只是鎖的記錄需要指向 Primary Row 的鎖。這樣子實(shí)現(xiàn)了去中心化的鎖管理，把Secondary Lock 與 Primary Lock 關(guān)聯(lián)了起來(lái)。

Secondary Row 的 Pre-Write 操作：

1. 拿到 Primary Row 的 Pre-Write 中獲得的時(shí)間戳 start_ts = 7。
2. 檢查 <Joe bal:write> 列，如果有大于 7 的數(shù)據(jù)版本則提交失敗，有則說(shuō)明其他事務(wù)已經(jīng)寫(xiě)入數(shù)據(jù)（寫(xiě)沖突），沒(méi)有則繼續(xù)處理。
3. 檢查 <Joe bal:lock> 列，如果有小于 7 的數(shù)據(jù)版本鎖則提交失敗，有則說(shuō)明其他事務(wù)已經(jīng)占用數(shù)據(jù)，沒(méi)有則加鎖繼續(xù)處理。
4. 設(shè)置 <Joebal:data 7> 為 9。

多個(gè) key 也是類似，在實(shí)際應(yīng)用場(chǎng)景中，可以異步對(duì)多個(gè) key 加鎖，加快速度。

Secondary Row Pre-Write

自此預(yù)寫(xiě)（Pre-write）過(guò)程已經(jīng)完成了！

提交（Commit）

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

首先進(jìn)行的是 Primary Row 的 Commit 操作：

1. 從 TSO 拿到當(dāng)前時(shí)間戳 commit_ts = 8。
2. 檢查 <Bob bal:lock> 列，看鎖是否存在，不存在則可能已經(jīng)被清除了，取消事務(wù)；存在則繼續(xù)。
3. 以 commit_ts 為版本號(hào)，指向 bal:write 列的 start_ts 對(duì)應(yīng)數(shù)據(jù)版本。也就是把 <Bob bal:write 8> 設(shè)置為 data@7。此步驟完成后，寫(xiě)入的數(shù)據(jù)版本已經(jīng)生效，也就是對(duì)讀已提交事務(wù)可見(jiàn)了。
4. 刪除鎖信息，讓其可寫(xiě)。

1~3步驟需要在一個(gè) bigtable 事務(wù)里面進(jìn)行原子操作。

Primary Row Commit

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

Secondary Row Commit

隨便聊點(diǎn)

事務(wù)隔離級(jí)別

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

優(yōu)點(diǎn)：

• 保證事務(wù)中的讀操作讀到對(duì)應(yīng)數(shù)據(jù)版本，避免產(chǎn)生不可重復(fù)讀的問(wèn)題。
• 保證多事務(wù)中的寫(xiě)操作不會(huì)更新到同一條記錄。

缺點(diǎn)也比較明顯：

• 寫(xiě)傾斜（Write）問(wèn)題。
• 樂(lè)觀事務(wù)會(huì)產(chǎn)生寫(xiě)熱點(diǎn)問(wèn)題。

鎖管理

Percolator 拋棄中心鎖管理，把鎖信息分散數(shù)據(jù)當(dāng)中。通過(guò)區(qū)分 Primary 和 Secondary，巧妙的設(shè)置了一個(gè)標(biāo)志，后續(xù)的異常處理都可以通過(guò)這個(gè)標(biāo)簽來(lái)進(jìn)行。

鎖有可能有以下異常：

1. Prewrite 中斷，還進(jìn)行 primary lock 或者寫(xiě) secondary lock 到一半系統(tǒng)崩潰。
2. Commit 中斷，未進(jìn)行 primary commit 或者 primary commit 到一半系統(tǒng)崩潰。

此時(shí)就需要用到鎖清理，鎖清理不需要另外開(kāi)任務(wù)去管理和回收。只需要在讀操作的時(shí)候遇到鎖的時(shí)候特殊處理即可。減輕了鎖維護(hù)的成本，也簡(jiǎn)化了整個(gè)鎖的管理模型。

那是怎么處理的呢？

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

1. 不在；說(shuō)明此鎖可讀：首先讀取 write 列小于 start_ts 的最大的數(shù)據(jù)，然后去讀 data 列。
2. 在；說(shuō)明此鎖不可讀，此時(shí)如果按照鎖可讀情況處理的話，可能會(huì)產(chǎn)生讀未提交的問(wèn)題。

在鎖不可讀的情況下，也不可能無(wú)休止等待，在一定的延遲后，會(huì)進(jìn)行以下操作：

1. 遇到 primary lock 還在，可以進(jìn)行鎖清除。
2. 遇到 secondary lock 還在，檢查 primary lock。
   1. primary lock 還在，事務(wù) commit 失敗，回滾事務(wù)
   2. primary lock 不在，事務(wù) commit 已經(jīng)成功了，進(jìn)行事務(wù)前滾（沒(méi)錯(cuò)，就是前滾）。

Percolator 缺點(diǎn)

1. 由于依賴 TSO，會(huì)發(fā)現(xiàn)網(wǎng)絡(luò)交互比較多；TiDB 團(tuán)隊(duì)針對(duì)退出了 Async Commit，可以減少網(wǎng)絡(luò)交互。
2. 樂(lè)觀鎖存在熱點(diǎn)讀寫(xiě)回滾風(fēng)暴問(wèn)題；TiDB 團(tuán)隊(duì)針對(duì)此推出了悲觀事務(wù)模型。
3. 依賴讀清理鎖，會(huì)有寫(xiě)沖突問(wèn)題。