作者：littlemagic

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

前言

前段時間忙雙11忙到廢寢忘食，這期間又被各種奇奇怪怪的小病折騰了半個多月，整個人狀態(tài)不是很好，博客也連續(xù)吃灰到現(xiàn)在，請看官勿怪。好在今天感覺還不錯，可以繼續(xù)寫點東西了。

為了應(yīng)對業(yè)務(wù)數(shù)據(jù)的爆炸性增長以及MySQL業(yè)務(wù)庫分庫分表現(xiàn)狀的各種不便，筆者的團隊近期用一周時間突擊調(diào)研TiDB，并部署了由16個節(jié)點組成的TiDB集群，同時開始逐漸探索利用它替代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實現(xiàn)的分布式結(jié)構(gòu)化大數(shù)據(jù)存儲系統(tǒng)，我們耳熟能詳?shù)腍Base就是Bigtable的開源版本實現(xiàn)。其數(shù)據(jù)模型可以視為多維的、支持MVCC的K-V Map，即：

(row:string, column:string, timestamp:int64) -> data:string

Bigtable原生支持單行事務(wù)，即能夠保證一行內(nèi)一個或多個列族上的多個操作的ACID特性。但是，很多情況下用戶都需要在單個事務(wù)中更改多行數(shù)據(jù)，只有單行事務(wù)顯然不夠用。而基于Bigtable的分布式特性，跨行事務(wù)與單行事務(wù)相比更加復(fù)雜，需要注意的三個要點列舉如下：

• 必須有精準(zhǔn)的全局授時服務(wù)，消除服務(wù)器之間時鐘無法嚴(yán)格同步的影響，從而保證事務(wù)的順序不會錯亂；

• 必須有高效的全局鎖機制，保證兩個并發(fā)的事務(wù)不能同時修改一行數(shù)據(jù)，并且避免事務(wù)出現(xiàn)死鎖；

• 必須高效，在實現(xiàn)ACID語義的基礎(chǔ)上不能影響原有系統(tǒng)的吞吐量與并發(fā)度。

在這三個要點的基礎(chǔ)上，Google的大佬們又設(shè)計了Percolator分布式事務(wù)協(xié)議，借助Bigtable原生的單行事務(wù)實現(xiàn)了跨行事務(wù)。Percolator的設(shè)計理念集中體現(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ù)。圖中的每一個大矩形表示一臺服務(wù)器，其上運行的服務(wù)包括Tablet Server(等同于HBase RegionServer)、Chunk Server(等同于HDFS DataNode)，以及新加入的Percolator Worker。另外，還引入了Timestamp Oracle(簡稱TSO)作為全局授時服務(wù)。也就是說，Percolator的實現(xiàn)僅需要增加2個服務(wù)，以及在客戶端提供與Percolator協(xié)議兼容的庫。

Percolator事務(wù)流程

Percolator事務(wù)分為兩個階段：預(yù)寫(Pre-write)和提交(Commit)，本質(zhì)上相當(dāng)于一個加強的2PC。另外，所有啟用了Percolator事務(wù)的表中，每一個列族都會預(yù)先增加兩個列，分別是：

• lock：

  存儲事務(wù)過程中的鎖信息；

• write：

  存儲當(dāng)前行可見(最近一次提交)的版本號。

  為了避免混淆，在這里不將其稱為時間戳。

另外，為了簡化場景，假設(shè)存儲用戶數(shù)據(jù)的列只有一個，名為data。

預(yù)寫階段

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

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

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

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

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

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

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

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

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

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

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

提交階段

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

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

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

3. 以commit_ts作為版本號，將start_ts更新到write列中。

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

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

5. 若步驟1~4均成功，說明主操作行成功，代表整個事務(wù)實際上已經(jīng)提交。

   接下來只需異步地提交每個次操作即可，即重復(fù)步驟3、4的更新write列和清除lock列操作。

注意：上述步驟2、3、4會在同一個Bigtable單行事務(wù)中進行，保證原子性。另外，如果次操作的提交失敗，則仍然要回滾事務(wù)。

示例：經(jīng)典轉(zhuǎn)賬流程

下圖來自原始論文，描述了Percolator協(xié)議下的一次轉(zhuǎn)賬流程(Bob向Joe轉(zhuǎn)賬$7)。注意每一列中冒號之前的是版本號，冒號之后的則是該列存儲的數(shù)據(jù)。附帶的說明清楚易懂，筆者就不多廢話了。

要點簡析

快照隔離級別

傳統(tǒng)關(guān)系型數(shù)據(jù)庫中定義的隔離級別有4種(RU、RC、RR、S)，而Percolator提供的隔離級別是快照隔離(Snapshot Isolation, SI)，它也是與MVCC相輔相成的。SI的優(yōu)點是：

• 對于讀操作，保證能夠從時間戳/版本號指定的穩(wěn)定快照獲取，不會發(fā)生幻讀；

• 對于寫操作，保證在多個事務(wù)并發(fā)寫同一條記錄時，不會有多于一個事務(wù)提交成功。

SI下的事務(wù)都會帶有兩個時間戳，即上文講解Percolator流程時提到的start_ts(下圖中空心方塊)與commit_ts(下圖中實心圓點)。SI硬性要求一個事務(wù)提交時的commit_ts大于所有之前產(chǎn)生的start_ts和commit_ts，當(dāng)然這已經(jīng)由TSO來保證了。

看圖說話：

• 因為start_ts[2] < commit_ts[1]，所以事務(wù)1的結(jié)果對事務(wù)2不可見；

• 因為start_ts[3] > commit_ts[2] > commit_ts[1]，所以事務(wù)1和2的結(jié)果都對事務(wù)3可見；

• 如果事務(wù)1和2寫了同一條記錄，那么1和2中至少有一個會失敗。

SI存在的主要問題是寫偏斜(Write-skew)，看官可自行查找資料去了解，不再贅述。

分散的鎖機制

由上文的描述可以看出，Percolator巧妙地反其道而行之，把事務(wù)相關(guān)的鎖信息分散到了每一行中，并通過將主操作作為互斥點，免去了重新設(shè)計一套全局鎖機制的麻煩。另外，預(yù)寫階段的步驟3中檢查到任意鎖沖突都會取消事務(wù)，簡單粗暴地避免了死鎖的發(fā)生。最后，Percolator構(gòu)建在帶冗余的分布式文件系統(tǒng)(論文的語境中是GFS)之上，所以不必?fù)?dā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ù)中進行的。

這里會產(chǎn)生兩個問題：

• 第一，為什么不能在有沖突時直接返回版本號小于當(dāng)前start_ts的最新版本數(shù)據(jù)？

很顯然，基于持鎖事務(wù)結(jié)果的不確定性(可能提交也可能回滾)，這樣會打破SI對讀操作的保證，亦即產(chǎn)生幻讀?？垂偕陨运伎家幌录纯衫斫?。

• 第二，如果客戶端崩潰或者失聯(lián)，導(dǎo)致它發(fā)起的事務(wù)的鎖遺留下來，讀操作一直不能成功，該怎么辦？

答案是由讀操作來自主完成，即不會無限等待下去，而是在一定時長的延遲之后直接將卡住的主操作鎖信息清理掉，并讀取最新版本的數(shù)據(jù)。

分兩種情況討論：其一，讀操作直接讀到了原事務(wù)中具有primary鎖信息的行，說明原事務(wù)未提交成功，需要回滾(即清理鎖)；其二，讀操作讀到了原事務(wù)中具有secondary鎖信息的行，此時仍然要去對應(yīng)的primary行上查找鎖是否存在，如果存在，說明原事務(wù)未提交成功，將其回滾；如果不存在，說明已提交成功，將其前滾(即清理鎖的同時更新對應(yīng)的write列)。

可見，主操作鎖和從操作鎖存在的緊密關(guān)聯(lián)能夠有效保證Percolator事務(wù)的安全性與活性，即：同一事務(wù)中的任意兩個寫操作結(jié)果肯定一致，且所有操作的結(jié)果要么是提交成功，要么是提交失敗。

客戶端的作用

如果套用2PC的概念，客戶端(在TiDB內(nèi)部是tikv-client)顯然扮演了協(xié)調(diào)者(Coordinator)的角色。傳統(tǒng)2PC的協(xié)調(diào)者存在單點問題，但是Percolator中的客戶端并沒有此問題——就算客戶端失敗，事務(wù)也只會有成功與失敗兩種狀態(tài)，不會破壞一致性。

有缺點么？

當(dāng)然有。

• 網(wǎng)絡(luò)I/O和RPC的負(fù)載較大，事務(wù)預(yù)寫成本較高；

• 依靠讀操作清理鎖，如果清理不及時，會增加其他正常事務(wù)寫沖突的概率；

• Percolator鎖的本質(zhì)為樂觀鎖，如果大量事務(wù)并發(fā)寫熱點數(shù)據(jù)，則根本無法阻塞，造成回滾風(fēng)暴。

• 考慮另一個場景：

  有一個大事務(wù)和很多小事務(wù)，且它們的熱點overlap，那么大事務(wù)可能受小事務(wù)的影響進入饑餓狀態(tài)(即很長時間內(nèi)無法執(zhí)行)。

  為了克服該問題，TiDB提出了悲觀事務(wù)模型，不過這就是后話了。

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

			

			

				
			


		
長按訂閱更多精彩▼
			

		
如有收獲，點個在看，誠摯感謝