作者：littlemagic

來源：https://littlemagic.blog.csdn.net/article/details/110732647

前言

前段時(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ù)寫階段

1. 客戶端啟動(dòng)事務(wù)，從TSO獲取時(shí)間戳，記為start_ts，并向Percolator Worker發(fā)起Pre-write請(qǐng)求。

2. 在該事務(wù)包含的所有寫操作中選取一個(gè)作為主(primary)操作，其余的作為次(secondary)操作。

   主操作將作為整個(gè)事務(wù)的互斥點(diǎn)，標(biāo)記事務(wù)的狀態(tài)。

3. 先預(yù)寫主操作，成功后再預(yù)寫次操作。

   
   在預(yù)寫過程中，對(duì)每一個(gè)寫操作都要執(zhí)行檢查：

• 檢查寫入的行對(duì)應(yīng)的write列版本號(hào)是否晚于start_ts，如果是，說明有版本沖突，直接取消整個(gè)事務(wù)；

• 檢查寫入的行對(duì)應(yīng)的lock列是否有鎖，如果有，說明其他事務(wù)正在寫，直接取消整個(gè)事務(wù)。

1. 檢查通過后，以start_ts作為版本號(hào)將數(shù)據(jù)寫入data列，但不更新write列，亦即此時(shí)寫入的數(shù)據(jù)仍然不可見。

2. 對(duì)操作行加鎖，即更新lock列的鎖信息：

   主操作行的lock直接標(biāo)為primary，次操作行的lock則標(biāo)為主操作行的行鍵和列名。

注意：處理每一行時(shí)，上述步驟3、4、5每次都會(huì)在同一個(gè)Bigtable單行事務(wù)中進(jìn)行，保證原子性。

提交階段

1. 客戶端從TSO獲取時(shí)間戳，記為commit_ts，并向Percolator Worker發(fā)起Commit請(qǐng)求。

2. 檢查主操作行對(duì)應(yīng)的lock列所在的primary標(biāo)記是否存在，如果不存在(可能已經(jīng)被清理，見后文所述)則失敗，取消事務(wù)；

   如果存在則繼續(xù)。

3. 以commit_ts作為版本號(hào)，將start_ts更新到write列中。

   也就是說在本階段完成后，預(yù)寫階段寫入的數(shù)據(jù)將會(huì)可見。

4. 對(duì)該行解鎖，即刪除lock列的鎖信息。

5. 若步驟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ù)模型，不過這就是后話了。

特別推薦一個(gè)分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒關(guān)注的小伙伴，可以長(zhǎng)按關(guān)注一下：

			

			

				
			


		
長(zhǎng)按訂閱更多精彩▼
			

		
如有收獲，點(diǎn)個(gè)在看，誠(chéng)摯感謝