前言
前段時(shí)間忙雙11忙到廢寢忘食栓拜，這期間又被各種奇奇怪怪的小病折騰了半個(gè)多月座泳，整個(gè)人狀態(tài)不是很好，博客也連續(xù)吃灰到現(xiàn)在幕与，請(qǐng)看官勿怪。好在今天感覺還不錯(cuò)镇防，可以繼續(xù)寫點(diǎn)東西了啦鸣。
為了應(yīng)對(duì)業(yè)務(wù)數(shù)據(jù)的爆炸性增長(zhǎng)以及MySQL業(yè)務(wù)庫(kù)分庫(kù)分表現(xiàn)狀的各種不便，筆者的團(tuán)隊(duì)近期用一周時(shí)間突擊調(diào)研TiDB来氧，并部署了由16個(gè)節(jié)點(diǎn)組成的TiDB集群诫给，同時(shí)開始逐漸探索利用它替代MySQL的可能性。在調(diào)研過程中啦扬，我們了解到TiDB能夠100%支持ACID事務(wù)中狂。并且不同于傳統(tǒng)的XA，TiDB采用的是Google提出的Percolator分布式事務(wù)協(xié)議扑毡。本文聊一聊Percolator的部分細(xì)節(jié)胃榕，之后的文章再說它在TiDB事務(wù)（包括樂觀事務(wù)和悲觀事務(wù)）中的具體應(yīng)用。
從Bigtable跨行事務(wù)到Percolator
Bigtable是Google實(shí)現(xiàn)的分布式結(jié)構(gòu)化大數(shù)據(jù)存儲(chǔ)系統(tǒng)瞄摊，我們耳熟能詳?shù)腍Base就是Bigtable的開源版本實(shí)現(xiàn)勋又。其數(shù)據(jù)模型可以視為多維的苦掘、支持MVCC的K-V Map，即：
(row:string, column:string, timestamp:int64) -> data:string
Bigtable原生支持單行事務(wù)楔壤，即能夠保證一行內(nèi)一個(gè)或多個(gè)列族上的多個(gè)操作的ACID特性鹤啡。但是，很多情況下用戶都需要在單個(gè)事務(wù)中更改多行數(shù)據(jù)蹲嚣，只有單行事務(wù)顯然不夠用递瑰。而基于Bigtable的分布式特性，跨行事務(wù)與單行事務(wù)相比更加復(fù)雜隙畜，需要注意的三個(gè)要點(diǎn)列舉如下：
- 必須有精準(zhǔn)的全局授時(shí)服務(wù)抖部，消除服務(wù)器之間時(shí)鐘無法嚴(yán)格同步的影響，從而保證事務(wù)的順序不會(huì)錯(cuò)亂禾蚕；
- 必須有高效的全局鎖機(jī)制您朽，保證兩個(gè)并發(fā)的事務(wù)不能同時(shí)修改一行數(shù)據(jù)，并且避免事務(wù)出現(xiàn)死鎖换淆；
- 必須高效哗总，在實(shí)現(xiàn)ACID語(yǔ)義的基礎(chǔ)上不能影響原有系統(tǒng)的吞吐量與并發(fā)度。
在這三個(gè)要點(diǎn)的基礎(chǔ)上倍试，Google的大佬們又設(shè)計(jì)了Percolator分布式事務(wù)協(xié)議讯屈，借助Bigtable原生的單行事務(wù)實(shí)現(xiàn)了跨行事務(wù)。Percolator的設(shè)計(jì)理念集中體現(xiàn)在OSDI 2010的一篇論文《Large-scale Incremental Processing Using Distributed Transactions and Notifications》中县习。下圖示出啟用Percolator之后的Bigtable服務(wù)架構(gòu)涮母。
Bigtable依靠Chubby（等同于ZooKeeper）提供分布式協(xié)調(diào)服務(wù)。圖中的每一個(gè)大矩形表示一臺(tái)服務(wù)器躁愿，其上運(yùn)行的服務(wù)包括Tablet Server（等同于HBase RegionServer）叛本、Chunk Server（等同于HDFS DataNode），以及新加入的Percolator Worker彤钟。另外来候，還引入了Timestamp Oracle（簡(jiǎn)稱TSO）作為全局授時(shí)服務(wù)。也就是說逸雹，Percolator的實(shí)現(xiàn)僅需要增加2個(gè)服務(wù)营搅，以及在客戶端提供與Percolator協(xié)議兼容的庫(kù)。
Percolator事務(wù)流程
Percolator事務(wù)分為兩個(gè)階段：預(yù)寫（Pre-write）和提交（Commit）梆砸，本質(zhì)上相當(dāng)于一個(gè)加強(qiáng)的2PC转质。另外，所有啟用了Percolator事務(wù)的表中帖世，每一個(gè)列族都會(huì)預(yù)先增加兩個(gè)列休蟹，分別是：
- lock：存儲(chǔ)事務(wù)過程中的鎖信息；
- write：存儲(chǔ)當(dāng)前行可見（最近一次提交）的版本號(hào)。為了避免混淆鸡挠，在這里不將其稱為時(shí)間戳辉饱。
另外拣展，為了簡(jiǎn)化場(chǎng)景彭沼，假設(shè)存儲(chǔ)用戶數(shù)據(jù)的列只有一個(gè)，名為data备埃。
預(yù)寫階段
- 客戶端啟動(dòng)事務(wù)姓惑，從TSO獲取時(shí)間戳，記為start_ts按脚，并向Percolator Worker發(fā)起Pre-write請(qǐng)求于毙。
- 在該事務(wù)包含的所有寫操作中選取一個(gè)作為主（primary）操作，其余的作為次（secondary）操作辅搬。主操作將作為整個(gè)事務(wù)的互斥點(diǎn)唯沮，標(biāo)記事務(wù)的狀態(tài)。
- 先預(yù)寫主操作堪遂，成功后再預(yù)寫次操作介蛉。
在預(yù)寫過程中，對(duì)每一個(gè)寫操作都要執(zhí)行檢查：
- 檢查寫入的行對(duì)應(yīng)的write列版本號(hào)是否晚于start_ts溶褪，如果是币旧，說明有版本沖突，直接取消整個(gè)事務(wù)猿妈；
- 檢查寫入的行對(duì)應(yīng)的lock列是否有鎖吹菱，如果有，說明其他事務(wù)正在寫彭则，直接取消整個(gè)事務(wù)鳍刷。
- 檢查通過后，以start_ts作為版本號(hào)將數(shù)據(jù)寫入data列俯抖，但不更新write列倾剿，亦即此時(shí)寫入的數(shù)據(jù)仍然不可見。
- 對(duì)操作行加鎖蚌成，即更新lock列的鎖信息：主操作行的lock直接標(biāo)為primary，次操作行的lock則標(biāo)為主操作行的行鍵和列名凛捏。
注意：處理每一行時(shí)担忧，上述步驟3、4坯癣、5每次都會(huì)在同一個(gè)Bigtable單行事務(wù)中進(jìn)行瓶盛，保證原子性。
提交階段
- 客戶端從TSO獲取時(shí)間戳，記為commit_ts惩猫，并向Percolator Worker發(fā)起Commit請(qǐng)求芝硬。
- 檢查主操作行對(duì)應(yīng)的lock列所在的primary標(biāo)記是否存在，如果不存在（可能已經(jīng)被清理轧房，見后文所述）則失敗拌阴，取消事務(wù)；如果存在則繼續(xù)奶镶。
- 以commit_ts作為版本號(hào)迟赃，將start_ts更新到write列中。也就是說在本階段完成后厂镇，預(yù)寫階段寫入的數(shù)據(jù)將會(huì)可見纤壁。
- 對(duì)該行解鎖，即刪除lock列的鎖信息捺信。
- 若步驟1~4均成功酌媒，說明主操作行成功，代表整個(gè)事務(wù)實(shí)際上已經(jīng)提交迄靠。接下來只需異步地提交每個(gè)次操作即可秒咨，即重復(fù)步驟3、4的更新write列和清除lock列操作梨水。
注意：上述步驟2拭荤、3、4會(huì)在同一個(gè)Bigtable單行事務(wù)中進(jìn)行疫诽，保證原子性舅世。另外，如果次操作的提交失敗奇徒，則仍然要回滾事務(wù)雏亚。
示例：經(jīng)典轉(zhuǎn)賬流程
下圖來自原始論文，描述了Percolator協(xié)議下的一次轉(zhuǎn)賬流程（Bob向Joe轉(zhuǎn)賬$7）摩钙。注意每一列中冒號(hào)之前的是版本號(hào)罢低，冒號(hào)之后的則是該列存儲(chǔ)的數(shù)據(jù)。附帶的說明清楚易懂胖笛，筆者就不多廢話了网持。
要點(diǎn)簡(jiǎn)析
快照隔離級(jí)別
傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)中定義的隔離級(jí)別有4種（RU、RC长踊、RR功舀、S），而Percolator提供的隔離級(jí)別是快照隔離（Snapshot Isolation, SI）身弊，它也是與MVCC相輔相成的辟汰。SI的優(yōu)點(diǎn)是：
- 對(duì)于讀操作列敲，保證能夠從時(shí)間戳/版本號(hào)指定的穩(wěn)定快照獲取，不會(huì)發(fā)生幻讀帖汞；
- 對(duì)于寫操作戴而，保證在多個(gè)事務(wù)并發(fā)寫同一條記錄時(shí)，不會(huì)有多于一個(gè)事務(wù)提交成功翩蘸。
SI下的事務(wù)都會(huì)帶有兩個(gè)時(shí)間戳所意，即上文講解Percolator流程時(shí)提到的start_ts（下圖中空心方塊）與commit_ts（下圖中實(shí)心圓點(diǎn)）。SI硬性要求一個(gè)事務(wù)提交時(shí)的commit_ts大于所有之前產(chǎn)生的start_ts和commit_ts鹿鳖，當(dāng)然這已經(jīng)由TSO來保證了扁眯。
看圖說話：
- 因?yàn)閟tart_ts[2] < commit_ts[1]，所以事務(wù)1的結(jié)果對(duì)事務(wù)2不可見翅帜；
- 因?yàn)閟tart_ts[3] > commit_ts[2] > commit_ts[1]姻檀，所以事務(wù)1和2的結(jié)果都對(duì)事務(wù)3可見；
- 如果事務(wù)1和2寫了同一條記錄涝滴，那么1和2中至少有一個(gè)會(huì)失敗绣版。
SI存在的主要問題是寫偏斜（Write-skew），看官可自行查找資料去了解歼疮，不再贅述杂抽。
分散的鎖機(jī)制
由上文的描述可以看出，Percolator巧妙地反其道而行之韩脏，把事務(wù)相關(guān)的鎖信息分散到了每一行中缩麸，并通過將主操作作為互斥點(diǎn)，免去了重新設(shè)計(jì)一套全局鎖機(jī)制的麻煩赡矢。另外杭朱，預(yù)寫階段的步驟3中檢查到任意鎖沖突都會(huì)取消事務(wù)，簡(jiǎn)單粗暴地避免了死鎖的發(fā)生吹散。最后弧械，Percolator構(gòu)建在帶冗余的分布式文件系統(tǒng)（論文的語(yǔ)境中是GFS）之上，所以不必?fù)?dān)心鎖信息會(huì)丟失空民。
快照讀與鎖清理
相對(duì)于寫流程刃唐，讀流程就簡(jiǎn)單很多了：從TSO獲取當(dāng)前start_ts，然后檢查lock列界轩，判斷早于當(dāng)前start_ts的區(qū)間內(nèi)是否有鎖画饥。如果沒有，則從write列中根據(jù)commit_ts獲取到最新提交的start_ts浊猾，再根據(jù)獲取到的start_ts從data列中獲取數(shù)據(jù)荒澡。如果有鎖，則意味著存在未提交的事務(wù)与殃，需要等待持鎖的事務(wù)提交单山，才能讀取最新的數(shù)據(jù)。讀流程也是在Bigtable單行事務(wù)中進(jìn)行的幅疼。
這里會(huì)產(chǎn)生兩個(gè)問題：
- 第一米奸，為什么不能在有沖突時(shí)直接返回版本號(hào)小于當(dāng)前start_ts的最新版本數(shù)據(jù)？
很顯然爽篷，基于持鎖事務(wù)結(jié)果的不確定性（可能提交也可能回滾）悴晰，這樣會(huì)打破SI對(duì)讀操作的保證，亦即產(chǎn)生幻讀逐工≌∠看官稍稍思考一下即可理解。
- 第二泪喊，如果客戶端崩潰或者失聯(lián)棕硫，導(dǎo)致它發(fā)起的事務(wù)的鎖遺留下來，讀操作一直不能成功袒啼，該怎么辦哈扮？
答案是由讀操作來自主完成，即不會(huì)無限等待下去蚓再，而是在一定時(shí)長(zhǎng)的延遲之后直接將卡住的主操作鎖信息清理掉滑肉，并讀取最新版本的數(shù)據(jù)。
分兩種情況討論：其一摘仅，讀操作直接讀到了原事務(wù)中具有primary鎖信息的行靶庙，說明原事務(wù)未提交成功，需要回滾（即清理鎖）娃属；其二六荒，讀操作讀到了原事務(wù)中具有secondary鎖信息的行，此時(shí)仍然要去對(duì)應(yīng)的primary行上查找鎖是否存在膳犹，如果存在恬吕，說明原事務(wù)未提交成功，將其回滾须床；如果不存在铐料，說明已提交成功，將其前滾（即清理鎖的同時(shí)更新對(duì)應(yīng)的write列）豺旬。
可見钠惩，主操作鎖和從操作鎖存在的緊密關(guān)聯(lián)能夠有效保證Percolator事務(wù)的安全性與活性，即：同一事務(wù)中的任意兩個(gè)寫操作結(jié)果肯定一致族阅，且所有操作的結(jié)果要么是提交成功篓跛，要么是提交失敗。
客戶端的作用
如果套用2PC的概念坦刀，客戶端（在TiDB內(nèi)部是tikv-client）顯然扮演了協(xié)調(diào)者（Coordinator）的角色愧沟。傳統(tǒng)2PC的協(xié)調(diào)者存在單點(diǎn)問題蔬咬，但是Percolator中的客戶端并沒有此問題——就算客戶端失敗，事務(wù)也只會(huì)有成功與失敗兩種狀態(tài)沐寺，不會(huì)破壞一致性林艘。
有缺點(diǎn)么？
當(dāng)然有混坞。
- 網(wǎng)絡(luò)I/O和RPC的負(fù)載較大狐援，事務(wù)預(yù)寫成本較高；
- 依靠讀操作清理鎖究孕，如果清理不及時(shí)啥酱，會(huì)增加其他正常事務(wù)寫沖突的概率；
- Percolator鎖的本質(zhì)為樂觀鎖厨诸，如果大量事務(wù)并發(fā)寫熱點(diǎn)數(shù)據(jù)镶殷，則根本無法阻塞，造成回滾風(fēng)暴泳猬。
- 考慮另一個(gè)場(chǎng)景：有一個(gè)大事務(wù)和很多小事務(wù)批钠，且它們的熱點(diǎn)overlap，那么大事務(wù)可能受小事務(wù)的影響進(jìn)入饑餓狀態(tài)（即很長(zhǎng)時(shí)間內(nèi)無法執(zhí)行）得封。為了克服該問題埋心，TiDB提出了悲觀事務(wù)模型，不過這就是后話了忙上。
The End
寫了這么多拷呆，似乎找回一點(diǎn)手感了，2020年剩下的這二十多天慢慢恢復(fù)更新吧疫粥。
民那晚安晚安茬斧。
