解讀Google分布式鎖服務

背景介紹

　　在2010年4月，Google的網頁索引更新實現了實時更新，在今年的OSDI大會上，Google首次公布了有關這一技術的論文。

　　在此之前，Google的索引更新，采用的的批處理的方式(map/reduce)，也就是當增量數據達到一定規模之后，把增量數據和全量索引 庫Join，得到最新的索引數據。采用新的索引更新系統之后，數據的生命周期縮短了50%，所謂的數據生命周期是指，數據從網頁上爬下來，到展現在搜索結 果中這段時間間隔，但是正如Google所強調的，這一系統僅僅是為增量更新所建立的，并沒有取代map/reduce的批量作業處理模式。

　　架構Overview

　　Google的新一代增量索引更新 – Percolator，是建立在Bigtable之上，提供的API也盡量接近Bigtable的方式，所以整個架構大致是如下的樣子：

?

　　事務（Transaction）和鎖（Lock）有區別嗎？

　　在關系數據庫領域，二者還是有很大區別的，但是對Percolator而言，Transaction = Lock，所以我們這里討論的分布式鎖，也可以說是分布式事務，所以下面提到的鎖或者事務，指的都是同一件事。

　　Percolator利用Bigtable原有的行鎖，再加上自己的一些巧妙的做法，實現了分布式鎖服務，這就意味著，Google可以實時的 更新PB級別的索引庫。最近我們發現Google的搜索結果時效性很好，剛寫好的文章，幾分鐘之后，Google就可以檢索到，原因就在Google的 Crawler在抓到新的網頁之后，不用再等待一定的時間批量更新索引，而是實時的更新，數據生命周期大大縮短。

　　Percolator支持跨行，跨表的事務，充分利用了Bigtable本身已經有的行事務、備份機制。

　　簡單的示例

　　在分析Percolator的細節之前，先看一個簡單的例子，對Percolator有一個大概的認識，有利于后面的理解。

　　下面的這個例子是把UserA的人氣分減掉10，加到UserB的人氣分上，key表示每一行的key，data，lock，write是列名字，data存儲數據，lock存儲鎖狀態，write表示事務提交后的數據位置引用.

　　初始狀態：UserA有100個人氣分，UserB有50個人氣分

　　最終狀態：UserA有90個人氣分，UserB有60個人氣分

　　Step0(初始狀態)

Key	Data	Lock	Write
UserA	100:t1	?	?
UserB	50:t2	?	?

　　Step1(從UserA中拿出10個人氣分)

Key	Data	Lock	Write
UserA	90:t2100:t1	Primary Lock:t2	t2
UserB	50:t2	?	?

　　Step2(把UserB的人氣分加10)

Key	Data	Lock	Write
UserA	90:t2100:t1	primary_lock:t2	t2
UserB	60:t350:t2	Primary_lock:UserA@data	t3

　　Step3(事務提交)

　　A：先提交primary(移除鎖，寫入新的timestamp，在write列寫入新數據的位置引用)

Key	Data	Lock	Write
UserA	t390:t2100:t1	?	t3:data:t2t2
UserB	60:t350:t2	Primary_lock@UserA.data	t3

　　B：再提交非primary（步驟同上）

Key	Data	Lock	Write
UserA	t390:t2100:t1	?	t3:data:t2t2
UserB	t460:t350:t2	?	t4:data:t3t3

　　事務結束了，UserA有90個人氣分，timestamp是t3，Userb有60個人氣分，timestamp是t4。（至于鎖的寫法和write列為什么那樣寫，后面再詳細解釋）

　　事務的執行過程

　　Percolator鎖分為兩種，primary和non-primary，在事務提交的過程中，先提交primary鎖，無論是跨行還是跨表，primary鎖都是沒有區別的。

　　事務的提交

　　事務的提交的過程分兩步，以UserA為例：

　　首先，在write列寫入新數據的位置引用，注意不是數據，是引用（理解成指針會更形象），上面step3A 中t3:data:t2表示在t3時刻提交的數據，最新的數據在data列的t2 timestamp

　　然后，移除lock列的內容。

　　因為Bigtable支持行鎖定，所以上述兩步都是在一個Bigtable事務內完成的。

　　讀操作

　　當一個client在發起讀操作之后，首先會向oracle server申請time stamp，接下來Percolator會檢查lock列，如果lock列不空，那么讀操作試圖移除（修復）這個lock或者等待，在后續鎖沖突處理詳細介紹如何修復。

　　補充：oracle發放time stamp是嚴格遞增的，而且不是一次發放一個，而是采取批量的方式。

　　寫操作

　　當一個client發起寫操作之后，首先會向oracle server申請time stamp，Percolator會檢查write列，如果write列的timestamp大于當前client的timestamp，那么寫失敗（不 能覆蓋新的數據 write-write conflict）；如果lock列有鎖存在，說明當前行正在被另外的client鎖定，client要么寫失敗，要么試圖修復(lock conflict)！

　　Notify機制

　　Percolator定義了一系列的Observer（類似于數據庫的trigger），位于Bigtable的tablet server上，Observer會監視某一列或者某幾列，當數據發生變化就會觸發Observer，Observer執行完之后，又會創建或者通知后續 的Observer，從而形成一個通知的傳遞。

　　鎖沖突的處理

　　當一個client在事務提交階段，crash掉了，那么鎖還保留，這樣后續的client訪問就會被阻止，這種情況叫做鎖沖突，Percolator提供了一種簡單的機制來解決這個問題。

　　每個client定期向Chubby Server寫入token，表明自己還活著，當某個client發現鎖沖突，那么會檢查持有鎖的client是否還活著，如果client是working狀態，那么client等待鎖釋放。否則client要清除掉當前鎖。

　　Roll ?forward & roll ?back：

　　Client先檢查primary lock是否存在，因為事務提交先從primary開始，如果primary不存在，那么說明前面的client已經提交了數據，所以client執行 roll forward操作：把non-primary對應的數據提交，并且清除non-primary lock；如果primary存在，說明前面的client還沒有提交數據就crash了，此時client執行roll back操作：把primary和non-primary的數據清除掉，并且清除lock。

　　小結

　　Google的分布式鎖服務很好了支持了增量索引的實時更新，縮短了數據的生命周期。本文對notify機制介紹的比較簡單，感興趣的請參考論文原文

　　《Large-scale Incremental Processing Using Distributed Transactions and Notifications》