基于Redis的分布式鎖到底安全嗎（下）？

2017-02-24

自從我寫完這個話題的上半部分之後，就感覺頭腦中出現了許多細小的聲音，久久揮之不去。它們就像是在為了一些雞毛蒜皮的小事而互相争吵個不停。的确，有關分布式的話題就是這樣，瑣碎異常，而且每個人說的話聽起來似乎都有道理。

今天，我們就繼續探讨這個話題的後半部分。本文中，我們将從antirez反駁Martin Kleppmann的觀點開始講起，然後會涉及到Hacker News上出現的一些讨論内容，接下來我們還會讨論到基于Zookeeper和Chubby的分布式鎖是怎樣的，并和Redlock進行一些對比。最後，我們會提到Martin對于這一事件的總結。

還沒有看過上半部分的同學，請先閱讀：

基于Redis的分布式鎖到底安全嗎（上）

antirez的反駁

Martin在發表了那篇分析分布式鎖的blog (How to do distributed locking)之後，該文章在Twitter和Hacker News上引發了廣泛的讨論。但人們更想聽到的是Redlock的作者antirez對此會發表什麼樣的看法。

Martin的那篇文章是在2016-02-08這一天發表的，但據Martin說，他在公開發表文章的一星期之前就把草稿發給了antirez進行review，而且他們之間通過email進行了讨論。不知道Martin有沒有意料到，antirez對于此事的反應很快，就在Martin的文章發表出來的第二天，antirez就在他的部落格上貼出了他對于此事的反駁文章，名字叫”Is Redlock safe?”，位址如下:

http://antirez.com/news/101

這是高手之間的過招。antirez這篇文章也條例非常清晰，并且中間涉及到大量的細節。antirez認為，Martin的文章對于Redlock的批評可以概括為兩個方面（與Martin文章的前後兩部分對應）：

帶有自動過期功能的分布式鎖，必須提供某種fencing機制來保證對共享資源的真正的互斥保護。Redlock提供不了這樣一種機制。
Redlock建構在一個不夠安全的系統模型之上。它對于系統的記時假設(timing assumption)有比較強的要求，而這些要求在現實的系統中是無法保證的。

antirez對這兩方面分别進行了反駁。

首先，關于fencing機制。antirez對于Martin的這種論證方式提出了質疑：既然在鎖失效的情況下已經存在一種fencing機制能繼續保持資源的互斥通路了，那為什麼還要使用一個分布式鎖并且還要求它提供那麼強的安全性保證呢？即使退一步講，Redlock雖然提供不了Martin所講的遞增的fencing token，但利用Redlock産生的随機字元串(

my_random_value

)可以達到同樣的效果。這個随機字元串雖然不是遞增的，但卻是唯一的，可以稱之為unique token。antirez舉了個例子，比如，你可以用它來實作“Check and Set”操作，原話是：

When starting to work with a shared resource, we set its state to “ <token>
”, then we operate the read-modify-write only if the token is still the same when we write.

（譯文：當開始和共享資源互動的時候，我們将它的狀态設定成“
<token> ”，然後僅在token沒改變的情況下我們才執行“讀取-修改-寫回”操作。）

第一遍看到這個描述的時候，我個人是感覺沒太看懂的。“Check and Set”應該就是我們平常聽到過的CAS操作了，但它如何在這個場景下工作，antirez并沒有展開說（在後面講到Hacker News上的讨論的時候，我們還會提到）。

然後，antirez的反駁就集中在第二個方面上：關于算法在記時(timing)方面的模型假設。在我們前面分析Martin的文章時也提到過，Martin認為Redlock會失效的情況主要有三種：

時鐘發生跳躍。
長時間的GC pause。
長時間的網絡延遲。

antirez肯定意識到了這三種情況對Redlock最緻命的其實是第一點：時鐘發生跳躍。這種情況一旦發生，Redlock是沒法正常工作的。而對于後兩種情況來說，Redlock在當初設計的時候已經考慮到了，對它們引起的後果有一定的免疫力。是以，antirez接下來集中精力來說明通過恰當的運維，完全可以避免時鐘發生大的跳動，而Redlock對于時鐘的要求在現實系統中是完全可以滿足的。

Martin在提到時鐘跳躍的時候，舉了兩個可能造成時鐘跳躍的具體例子：

系統管理者手動修改了時鐘。
從NTP服務收到了一個大的時鐘更新事件。

antirez反駁說：

手動修改時鐘這種人為原因，不要那麼做就是了。否則的話，如果有人手動修改Raft協定的持久化日志，那麼就算是Raft協定它也沒法正常工作了。
使用一個不會進行“跳躍”式調整系統時鐘的ntpd程式（可能是通過恰當的配置），對于時鐘的修改通過多次微小的調整來完成。

而Redlock對時鐘的要求，并不需要完全精确，它隻需要時鐘差不多精确就可以了。比如，要記時5秒，但可能實際記了4.5秒，然後又記了5.5秒，有一定的誤差。不過隻要誤差不超過一定範圍，這對Redlock不會産生影響。antirez認為呢，像這樣對時鐘精度并不是很高的要求，在實際環境中是完全合理的。

好了，到此為止，如果你相信antirez這裡關于時鐘的論斷，那麼接下來antirez的分析就基本上順理成章了。

關于Martin提到的能使Redlock失效的後兩種情況，Martin在分析的時候恰好犯了一個錯誤（在本文上半部分已經提到過）。在Martin給出的那個由用戶端GC pause引發Redlock失效的例子中，這個GC pause引發的後果相當于在鎖伺服器和用戶端之間發生了長時間的消息延遲。Redlock對于這個情況是能處理的。回想一下Redlock算法的具體過程，它使用起來的過程大體可以分成5步：

擷取目前時間。
完成擷取鎖的整個過程（與N個Redis節點互動）。
再次擷取目前時間。
把兩個時間相減，計算擷取鎖的過程是否消耗了太長時間，導緻鎖已經過期了。如果沒過期，
用戶端持有鎖去通路共享資源。

在Martin舉的例子中，GC pause或網絡延遲，實際發生在上述第1步和第3步之間。而不管在第1步和第3步之間由于什麼原因（程序停頓或網絡延遲等）導緻了大的延遲出現，在第4步都能被檢查出來，不會讓用戶端拿到一個它認為有效而實際卻已經過期的鎖。當然，這個檢查依賴系統時鐘沒有大的跳躍。這也就是為什麼antirez在前面要對時鐘條件進行辯護的原因。

有人會說，在第3步之後，仍然可能會發生延遲啊。沒錯，antirez承認這一點，他對此有一段很有意思的論證，原話如下：

The delay can only happen after steps 3, resulting into the lock to be considered ok while actually expired, that is, we are back at the first problem Martin identified of distributed locks where the client fails to stop working to the shared resource before the lock validity expires. Let me tell again how this problem is common with all the distributed locks implementations, and how the token as a solution is both unrealistic and can be used with Redlock as well.

（譯文：延遲隻能發生在第3步之後，這導緻鎖被認為是有效的而實際上已經過期了，也就是說，我們回到了Martin指出的第一個問題上，用戶端沒能夠在鎖的有效性過期之前完成與共享資源的互動。讓我再次申明一下，這個問題對于所有的分布式鎖的實作是普遍存在的，而且基于token的這種解決方案是不切實際的，但也能和Redlock一起用。）

這裡antirez所說的“Martin指出的第一個問題”具體是什麼呢？在本文上半部分我們提到過，Martin的文章分為兩大部分，其中前半部分與Redlock沒有直接關系，而是指出了任何一種帶自動過期功能的分布式鎖在沒有提供fencing機制的前提下都有可能失效。這裡antirez所說的就是指的Martin的文章的前半部分。換句話說，對于大延遲給Redlock帶來的影響，恰好與Martin在文章的前半部分針對所有的分布式鎖所做的分析是一緻的，而這種影響不單單針對Redlock。Redlock的實作已經保證了它是和其它任何分布式鎖的安全性是一樣的。當然，與其它“更完美”的分布式鎖相比，Redlock似乎提供不了Martin提出的那種遞增的token，但antirez在前面已經分析過了，關于token的這種論證方式本身就是“不切實際”的，或者退一步講，Redlock能提供的unique token也能夠提供完全一樣的效果。

另外，關于大延遲對Redlock的影響，antirez和Martin在Twitter上有下面的對話：

antirez:

@martinkl so I wonder if after my reply, we can at least agree about unbound messages delay to don’t cause any harm.

Martin:

@antirez Agree about message delay between app and lock server. Delay between app and resource being accessed is still problematic.

（譯文：

antirez問：我想知道，在我發文回複之後，我們能否在一點上達成一緻，就是大的消息延遲不會給Redlock的運作造成損害。

Martin答：對于用戶端和鎖伺服器之間的消息延遲，我同意你的觀點。但用戶端和被通路資源之間的延遲還是有問題的。）

通過這段對話可以看出，對于Redlock在第4步所做的鎖有效性的檢查，Martin是予以肯定的。但他認為用戶端和資源伺服器之間的延遲還是會帶來問題的。Martin在這裡說的有點模糊。就像antirez前面分析的，用戶端和資源伺服器之間的延遲，對所有的分布式鎖的實作都會帶來影響，這不單單是Redlock的問題了。

以上就是antirez在blog中所說的主要内容。有一些點值得我們注意一下：

antirez是同意大的系統時鐘跳躍會造成Redlock失效的。在這一點上，他與Martin的觀點的不同在于，他認為在實際系統中是可以避免大的時鐘跳躍的。當然，這取決于基礎設施和運維方式。
antirez在設計Redlock的時候，是充分考慮了網絡延遲和程式停頓所帶來的影響的。但是，對于用戶端和資源伺服器之間的延遲（即發生在算法第3步之後的延遲），antirez是承認所有的分布式鎖的實作，包括Redlock，是沒有什麼好辦法來應對的。

讨論進行到這，Martin和antirez之間誰對誰錯其實并不是那麼重要了。隻要我們能夠對Redlock（或者其它分布式鎖）所能提供的安全性的程度有充分的了解，那麼我們就能做出自己的選擇了。

Hacker News上的一些讨論

針對Martin和antirez的兩篇blog，很多技術人員在Hacker News上展開了激烈的讨論。這些讨論所在位址如下：

針對Martin的blog的讨論：https://news.ycombinator.com/item?id=11059738
針對antirez的blog的讨論：https://news.ycombinator.com/item?id=11065933

在Hacker News上，antirez積極參與了讨論，而Martin則始終置身事外。

下面我把這些讨論中一些有意思的點拿出來與大家一起分享一下（集中在對于fencing token機制的讨論上）。

關于antirez提出的“Check and Set”操作，他在blog裡并沒有詳加說明。果然，在Hacker News上就有人出來問了。antirez給出的答複如下：

You want to modify locked resource X. You set X.currlock = token. Then you read, do whatever you want, and when you write, you “write-if-currlock == token”. If another client did X.currlock = somethingelse, the transaction fails.

翻譯一下可以這樣了解：假設你要修改資源X，那麼遵循下面的僞碼所定義的步驟。

先設定X.currlock = token。
讀出資源X（包括它的值和附帶的X.currlock）。
按照”write-if-currlock == token”的邏輯，修改資源X的值。意思是說，如果對X進行修改的時候，X.currlock仍然和當初設定進去的token相等，那麼才進行修改；如果這時X.currlock已經是其它值了，那麼說明有另外一方也在試圖進行修改操作，那麼放棄目前的修改，進而避免沖突。

随後Hacker News上一位叫viraptor的使用者提出了異議，它給出了這樣一個執行序列：

A: X.currlock = Token_ID_A
A: resource read
A: is X.currlock still Token_ID_A? yes
B: X.currlock = Token_ID_B
B: resource read
B: is X.currlock still Token_ID_B? yes
B: resource write
A: resource write

到了最後兩步，兩個用戶端A和B同時進行寫操作，沖突了。不過，這位使用者應該是了解錯了antirez給出的修改過程了。按照antirez的意思，判斷X.currlock是否修改過和對資源的寫操作，應該是一個原子操作。隻有這樣了解才能合乎邏輯，否則的話，這個過程就有嚴重的破綻。這也是為什麼antirez之前會對fencing機制産生質疑：既然資源伺服器本身都能提供互斥的原子操作了，為什麼還需要一個分布式鎖呢？是以，antirez認為這種fencing機制是很累贅的，他之是以還是提出了這種“Check and Set”操作，隻是為了證明在提供fencing token這一點上，Redlock也能做到。但是，這裡仍然有一些不明确的地方，如果将”write-if-currlock == token”看做是原子操作的話，這個邏輯勢必要在資源伺服器上執行，那麼第二步為什麼還要“讀出資源X”呢？除非這個“讀出資源X”的操作也是在資源伺服器上執行，它包含在“判斷-寫回”這個原子操作裡面。而假如不這樣了解的話，“讀取-判斷-寫回”這三個操作都放在用戶端執行，那麼看不出它們如何才能實作原子性操作。在下面的讨論中，我們暫時忽略“讀出資源X”這一步。

這個基于random token的“Check and Set”操作，如果與Martin提出的遞增的fencing token對比一下的話，至少有兩點不同：

“Check and Set”對于寫操作要分成兩步來完成（設定token、判斷-寫回），而遞增的fencing token機制隻需要一步（帶着token向資源伺服器發起寫請求）。
遞增的fencing token機制能保證最終操作共享資源的順序，那些延遲時間太長的操作就無法操作共享資源了。但是基于random token的“Check and Set”操作不會保證這個順序，那些延遲時間太長的操作如果後到達了，它仍然有可能操作共享資源（當然是以互斥的方式）。

對于前一點不同，我們在後面的分析中會看到，如果資源伺服器也是分布式的，那麼使用遞增的fencing token也要變成兩步。

而對于後一點操作順序上的不同，antirez認為這個順序沒有意義，關鍵是能互斥通路就行了。他寫下了下面的話：

So the goal is, when race conditions happen, to avoid them in some way.

……

Note also that when it happens that, because of delays, the clients are accessing concurrently, the lock ID has little to do with the order in which the operations were indented to happen.

（譯文：我們的目标是，當競争條件出現的時候，能夠以某種方式避免。

還需要注意的是，當那種競争條件出現的時候，比如由于延遲，用戶端是同時來通路的，鎖的ID的大小順序跟那些操作真正想執行的順序，是沒有什麼關系的。）

這裡的lock ID，跟Martin說的遞增的token是一回事。

随後，antirez舉了一個“将名字加入清單”的操作的例子：

T0: Client A receives new name to add from web.
T0: Client B is idle
T1: Client A is experiencing pauses.
T1: Client B receives new name to add from web.
T2: Client A is experiencing pauses.
T2: Client B receives a lock with ID 1
T3: Client A receives a lock with ID 2

你看，兩個用戶端（其實是Web伺服器）執行“添加名字”的操作，A本來是排在B前面的，但獲得鎖的順序卻是B排在A前面。是以，antirez說，鎖的ID的大小順序跟那些操作真正想執行的順序，是沒有什麼關系的。關鍵是能排出一個順序來，能互斥通路就行了。那麼，至于鎖的ID是遞增的，還是一個random token，自然就不那麼重要了。

Martin提出的fencing token機制，給人留下了無盡的疑惑。這主要是因為他對于這一機制的描述缺少太多的技術細節。從上面的讨論可以看出，antirez對于這一機制的看法是，它跟一個random token沒有什麼差別，而且，它需要資源伺服器本身提供某種互斥機制，這幾乎讓分布式鎖本身的存在失去了意義。圍繞fencing token的問題，還有兩點是比較引人注目的，Hacker News上也有人提出了相關的疑問：

（1）關于資源伺服器本身的架構細節。
（2）資源伺服器對于fencing token進行檢查的實作細節，比如是否需要提供一種原子操作。

關于上述問題（1），Hacker News上有一位叫dwenzek的使用者發表了下面的評論：

…… the issue around the usage of fencing tokens to reject any late usage of a lock is unclear just because the protected resource and its access are themselves unspecified. Is the resource distributed or not? If distributed, does the resource has a mean to ensure that tokens are increasing over all the nodes? Does the resource have a mean to rollback any effects done by a client which session is interrupted by a timeout?

（譯文：…… 關于使用fencing token拒絕掉延遲請求的相關議題，是不夠清晰的，因為受保護的資源以及對它的通路方式本身是沒有被明确定義過的。資源服務是不是分布式的呢？如果是，資源服務有沒有一種方式能確定token在所有節點上遞增呢？對于用戶端的Session由于過期而被中斷的情況，資源服務有辦法将它的影響復原嗎？）

這些疑問在Hacker News上并沒有人給出解答。而關于分布式的資源伺服器架構如何處理fencing token，另外一名分布式系統的專家Flavio Junqueira在他的一篇blog中有所提及（我們後面會再提到）。

關于上述問題（2），Hacker News上有一位叫reza_n的使用者發表了下面的疑問：

I understand how a fencing token can prevent out of order writes when 2 clients get the same lock. But what happens when those writes happen to arrive in order and you are doing a value modification? Don’t you still need to rely on some kind of value versioning or optimistic locking? Wouldn’t this make the use of a distributed lock unnecessary?

（譯文：我了解當兩個用戶端同時獲得鎖的時候fencing token是如何防止亂序的。但是如果兩個寫操作恰好按序到達了，而且它們在對同一個值進行修改，那會發生什麼呢？難道不會仍然是依賴某種資料版本号或者樂觀鎖的機制？這不會讓分布式鎖變得沒有必要了嗎？）

一位叫Terr_的Hacker News使用者答：

I believe the “first” write fails, because the token being passed in is no longer “the lastest”, which indicates their lock was already released or expired.

（譯文：我認為“第一個”寫請求會失敗，因為它傳入的token不再是“最新的”了，這意味着鎖已經釋放或者過期了。）

Terr_的回答到底對不對呢？這不好說，取決于資源伺服器對于fencing token進行檢查的實作細節。讓我們來簡單分析一下。

為了簡單起見，我們假設有一台（先不考慮分布式的情況）通過RPC進行遠端通路檔案伺服器，它無法提供對于檔案的互斥通路（否則我們就不需要分布式鎖了）。現在我們按照Martin給出的說法，加入fencing token的檢查邏輯。由于Martin沒有描述具體細節，我們猜測至少有兩種可能。

第一種可能，我們修改了檔案伺服器的代碼，讓它能多接受一個fencing token的參數，并在進行所有處理之前加入了一個簡單的判斷邏輯，保證隻有目前接收到的fencing token大于之前的值才允許進行後邊的通路。而一旦通過了這個判斷，後面的處理不變。

現在想象reza_n描述的場景，用戶端1和用戶端2都發生了GC pause，兩個fencing token都延遲了，它們幾乎同時到達了檔案伺服器，而且保持了順序。那麼，我們新加入的判斷邏輯，應該對兩個請求都會放過，而放過之後它們幾乎同時在操作檔案，還是沖突了。既然Martin宣稱fencing token能保證分布式鎖的正确性，那麼上面這種可能的猜測也許是我們了解錯了。

當然，還有第二種可能，就是我們對檔案伺服器确實做了比較大的改動，讓這裡判斷token的邏輯和随後對檔案的處理放在一個原子操作裡了。這可能更接近antirez的了解。這樣的話，前面reza_n描述的場景中，兩個寫操作都應該成功。

基于ZooKeeper的分布式鎖更安全嗎？

很多人（也包括Martin在内）都認為，如果你想建構一個更安全的分布式鎖，那麼應該使用ZooKeeper，而不是Redis。那麼，為了對比的目的，讓我們先暫時脫離開本文的題目，讨論一下基于ZooKeeper的分布式鎖能提供絕對的安全嗎？它需要fencing token機制的保護嗎？

我們不得不提一下分布式專家Flavio Junqueira所寫的一篇blog，題目叫“Note on fencing and distributed locks”，位址如下：

https://fpj.me/2016/02/10/note-on-fencing-and-distributed-locks/

Flavio Junqueira是ZooKeeper的作者之一，他的這篇blog就寫在Martin和antirez發生争論的那幾天。他在文中給出了一個基于ZooKeeper建構分布式鎖的描述（當然這不是唯一的方式）：

用戶端嘗試建立一個znode節點，比如 /lock 。那麼第一個用戶端就建立成功了，相當于拿到了鎖；而其它的用戶端會建立失敗（znode已存在），擷取鎖失敗。
持有鎖的用戶端通路共享資源完成後，将znode删掉，這樣其它用戶端接下來就能來擷取鎖了。
znode應該被建立成ephemeral的。這是znode的一個特性，它保證如果建立znode的那個用戶端崩潰了，那麼相應的znode會被自動删除。這保證了鎖一定會被釋放。

看起來這個鎖相當完美，沒有Redlock過期時間的問題，而且能在需要的時候讓鎖自動釋放。但仔細考察的話，并不盡然。

ZooKeeper是怎麼檢測出某個用戶端已經崩潰了呢？實際上，每個用戶端都與ZooKeeper的某台伺服器維護着一個Session，這個Session依賴定期的心跳(heartbeat)來維持。如果ZooKeeper長時間收不到用戶端的心跳（這個時間稱為Sesion的過期時間），那麼它就認為Session過期了，通過這個Session所建立的所有的ephemeral類型的znode節點都會被自動删除。

設想如下的執行序列：

用戶端1建立了znode節點 /lock ，獲得了鎖。
用戶端1進入了長時間的GC pause。
用戶端1連接配接到ZooKeeper的Session過期了。znode節點 /lock 被自動删除。
用戶端2建立了znode節點 /lock ，進而獲得了鎖。
用戶端1從GC pause中恢複過來，它仍然認為自己持有鎖。

最後，用戶端1和用戶端2都認為自己持有了鎖，沖突了。這與之前Martin在文章中描述的由于GC pause導緻的分布式鎖失效的情況類似。

看起來，用ZooKeeper實作的分布式鎖也不一定就是安全的。該有的問題它還是有。但是，ZooKeeper作為一個專門為分布式應用提供方案的架構，它提供了一些非常好的特性，是Redis之類的方案所沒有的。像前面提到的ephemeral類型的znode自動删除的功能就是一個例子。

還有一個很有用的特性是ZooKeeper的watch機制。這個機制可以這樣來使用，比如當用戶端試圖建立

/lock

的時候，發現它已經存在了，這時候建立失敗，但用戶端不一定就此對外宣告擷取鎖失敗。用戶端可以進入一種等待狀态，等待當

/lock

節點被删除的時候，ZooKeeper通過watch機制通知它，這樣它就可以繼續完成建立操作（擷取鎖）。這可以讓分布式鎖在用戶端用起來就像一個本地的鎖一樣：加鎖失敗就阻塞住，直到擷取到鎖為止。這樣的特性Redlock就無法實作。

小結一下，基于ZooKeeper的鎖和基于Redis的鎖相比在實作特性上有兩個不同：

在正常情況下，用戶端可以持有鎖任意長的時間，這可以確定它做完所有需要的資源通路操作之後再釋放鎖。這避免了基于Redis的鎖對于有效時間(lock validity time)到底設定多長的兩難問題。實際上，基于ZooKeeper的鎖是依靠Session（心跳）來維持鎖的持有狀态的，而Redis不支援Sesion。
基于ZooKeeper的鎖支援在擷取鎖失敗之後等待鎖重新釋放的事件。這讓用戶端對鎖的使用更加靈活。

順便提一下，如上所述的基于ZooKeeper的分布式鎖的實作，并不是最優的。它會引發“herd effect”（羊群效應），降低擷取鎖的性能。一個更好的實作參見下面連結：

http://zookeeper.apache.org/doc/r3.4.9/recipes.html#sc_recipes_Locks

我們重新回到Flavio Junqueira對于fencing token的分析。Flavio Junqueira指出，fencing token機制本質上是要求用戶端在每次通路一個共享資源的時候，在執行任何操作之前，先對資源進行某種形式的“标記”(mark)操作，這個“标記”能保證持有舊的鎖的用戶端請求（如果延遲到達了）無法操作資源。這種标記操作可以是很多形式，fencing token是其中比較典型的一個。

随後Flavio Junqueira提到用遞增的epoch number（相當于Martin的fencing token）來保護共享資源。而對于分布式的資源，為了友善讨論，假設分布式資源是一個小型的多備份的資料存儲(a small replicated data store)，執行寫操作的時候需要向所有節點上寫資料。最簡單的做标記的方式，就是在對資源進行任何操作之前，先把epoch number标記到各個資源節點上去。這樣，各個節點就保證了舊的（也就是小的）epoch number無法操作資料。

當然，這裡再展開讨論下去可能就涉及到了這個資料存儲服務的實作細節了。比如在實際系統中，可能為了容錯，隻要上面講的标記和寫入操作在多數節點上完成就算成功完成了（Flavio Junqueira并沒有展開去講）。在這裡我們能看到的，最重要的，是這種标記操作如何起作用的方式。這有點類似于Paxos協定（Paxos協定要求每個proposal對應一個遞增的數字，執行accept請求之前先執行prepare請求）。antirez提出的random token的方式顯然不符合Flavio Junqueira對于“标記”操作的定義，因為它無法區分新的token和舊的token。隻有遞增的數字才能確定最終收斂到最新的操作結果上。

在這個分布式資料存儲服務（共享資源）的例子中，用戶端在标記完成之後執行寫入操作的時候，存儲服務的節點需要判斷epoch number是不是最新，然後确定能不能執行寫入操作。如果按照上一節我們的分析思路，這裡的epoch判斷和接下來的寫入操作，是不是在一個原子操作裡呢？根據Flavio Junqueira的相關描述，我們相信，應該是原子的。那麼既然資源本身可以提供原子互斥操作了，那麼分布式鎖還有存在的意義嗎？應該說有。用戶端可以利用分布式鎖有效地避免沖突，等待寫入機會，這對于包含多個節點的分布式資源尤其有用（當然，是出于效率的原因）。

Chubby的分布式鎖是怎樣做fencing的？

提到分布式鎖，就不能不提Google的Chubby。

Chubby是Google内部使用的分布式鎖服務，有點類似于ZooKeeper，但也存在很多差異。Chubby對外公開的資料，主要是一篇論文，叫做“The Chubby lock service for loosely-coupled distributed systems”，下載下傳位址如下：

https://research.google.com/archive/chubby.html

另外，YouTube上有一個的講Chubby的talk，也很不錯，播放位址：

https://www.youtube.com/watch?v=PqItueBaiRg&feature=youtu.be&t=487

Chubby自然也考慮到了延遲造成的鎖失效的問題。論文裡有一段描述如下：

a process holding a lock L may issue a request R, but then fail. Another process may ac- quire L and perform some action before R arrives at its destination. If R later arrives, it may be acted on without the protection of L, and potentially on inconsistent data.

（譯文：一個程序持有鎖L，發起了請求R，但是請求失敗了。另一個程序獲得了鎖L并在請求R到達目的方之前執行了一些動作。如果後來請求R到達了，它就有可能在沒有鎖L保護的情況下進行操作，帶來資料不一緻的潛在風險。）

這跟Martin的分析大同小異。

Chubby給出的用于解決（緩解）這一問題的機制稱為sequencer，類似于fencing token機制。鎖的持有者可以随時請求一個sequencer，這是一個位元組串，它由三部分組成：

鎖的名字。
鎖的擷取模式（排他鎖還是共享鎖）。
lock generation number（一個64bit的單調遞增數字）。作用相當于fencing token或epoch number。

用戶端拿到sequencer之後，在操作資源的時候把它傳給資源伺服器。然後，資源伺服器負責對sequencer的有效性進行檢查。檢查可以有兩種方式：

調用Chubby提供的API，CheckSequencer()，将整個sequencer傳進去進行檢查。這個檢查是為了保證用戶端持有的鎖在進行資源通路的時候仍然有效。
将用戶端傳來的sequencer與資源伺服器目前觀察到的最新的sequencer進行對比檢查。可以了解為與Martin描述的對于fencing token的檢查類似。

當然，如果由于相容的原因，資源服務本身不容易修改，那麼Chubby還提供了一種機制：

lock-delay。Chubby允許用戶端為持有的鎖指定一個lock-delay的時間值（預設是1分鐘）。當Chubby發現用戶端被動失去聯系的時候，并不會立即釋放鎖，而是會在lock-delay指定的時間内阻止其它用戶端獲得這個鎖。這是為了在把鎖配置設定給新的用戶端之前，讓之前持有鎖的用戶端有充分的時間把請求隊列排空(draining the queue)，盡量防止出現延遲到達的未處理請求。

可見，為了應對鎖失效問題，Chubby提供的三種處理方式：CheckSequencer()檢查、與上次最新的sequencer對比、lock-delay，它們對于安全性的保證是從強到弱的。而且，這些處理方式本身都沒有保證提供絕對的正确性(correctness)。但是，Chubby确實提供了單調遞增的lock generation number，這就允許資源伺服器在需要的時候，利用它提供更強的安全性保障。

關于時鐘

在Martin與antirez的這場争論中，沖突最為嚴重的就是對于系統時鐘的假設是不是合理的問題。Martin認為系統時鐘難免會發生跳躍（這與分布式算法的異步模型相符），而antirez認為在實際中系統時鐘可以保證不發生大的跳躍。

Martin對于這一分歧發表了如下看法（原話）：

So, fundamentally, this discussion boils down to whether it is reasonable to make timing assumptions for ensuring safety properties. I say no, Salvatore says yes — but that’s ok. Engineering discussions rarely have one right answer.

（譯文：從根本上來說，這場讨論最後歸結到了一個問題上：為了確定安全性而做出的記時假設到底是否合理。我認為不合理，而antirez認為合理 —— 但是這也沒關系。工程問題的讨論很少隻有一個正确答案。）

那麼，在實際系統中，時鐘到底是否可信呢？對此，Julia Evans專門寫了一篇文章，“TIL: clock skew exists”，總結了很多跟時鐘偏移有關的實際資料，并進行了分析。這篇文章位址：

http://jvns.ca/blog/2016/02/09/til-clock-skew-exists/

Julia Evans在文章最後得出的結論是：

clock skew is real （時鐘偏移在現實中是存在的）

Martin的事後總結

我們前面提到過，當各方的争論在激烈進行的時候，Martin幾乎始終置身事外。但是Martin在這件事過去之後，把這個事件的前後經過總結成了一個很長的故事線。如果你想最全面地了解這個事件發生的前後經過，那麼建議去讀讀Martin的這個總結：

https://storify.com/martinkl/redlock-discussion

在這個故事總結的最後，Martin寫下了很多感性的評論：

For me, this is the most important point: I don’t care who is right or wrong in this debate — I care about learning from others’ work, so that we can avoid repeating old mistakes, and make things better in future. So much great work has already been done for us: by standing on the shoulders of giants, we can build better software.

By all means, test ideas by arguing them and checking whether they stand up to scrutiny by others. That’s part of the learning process. But the goal should be to learn, not to convince others that you are right. Sometimes that just means to stop and think for a while.

（譯文：

對我來說最重要的一點在于：我并不在乎在這場辯論中誰對誰錯 —— 我隻關心從其他人的工作中學到的東西，以便我們能夠避免重蹈覆轍，并讓未來更加美好。前人已經為我們創造出了許多偉大的成果：站在巨人的肩膀上，我們得以建構更棒的軟體。

對于任何想法，務必要詳加檢驗，通過論證以及檢查它們是否經得住别人的詳細審查。那是學習過程的一部分。但目标應該是為了獲得知識，而不應該是為了說服别人相信你自己是對的。有時候，那隻不過意味着停下來，好好地想一想。）

關于分布式鎖的這場争論，我們已經完整地做了回顧和分析。

按照鎖的兩種用途，如果僅是為了效率(efficiency)，那麼你可以自己選擇你喜歡的一種分布式鎖的實作。當然，你需要清楚地知道它在安全性上有哪些不足，以及它會帶來什麼後果。而如果你是為了正确性(correctness)，那麼請慎之又慎。在本文的讨論中，我們在分布式鎖的正确性上走得最遠的地方，要數對于ZooKeeper分布式鎖、單調遞增的epoch number以及對分布式資源進行标記的分析了。請仔細審查相關的論證。

Martin為我們留下了不少疑問，尤其是他提出的fencing token機制。他在blog中提到，會在他的新書《Designing Data-Intensive Applications》的第8章和第9章再詳加論述。目前，這本書尚在預售當中。我感覺，這會是一本值得一讀的書，它不同于為了出名或賺錢而出版的那種短平快的書籍。可以看出作者在這本書上投入了巨大的精力。

最後，我相信，這個讨論還遠沒有結束。分布式鎖(Distributed Locks)和相應的fencing方案，可以作為一個長期的課題，随着我們對分布式系統的認識逐漸增加，可以再來慢慢地思考它。思考它更深層的本質，以及它在理論上的證明。

（完）

感謝：

由衷地感謝幾位朋友花了寶貴的時間對本文草稿所做的review：CacheCloud的作者付磊，快手的李偉博，阿裡的李波。當然，文中如果還有錯漏，由我本人負責^-^。

其它精選文章：

Redis内部資料結構詳解(7)——intset
Redis内部資料結構詳解(6)——skiplist
Redis内部資料結構詳解(5)——quicklist
Redis内部資料結構詳解(4)——ziplist
Redis内部資料結構詳解(3)——robj
Redis内部資料結構詳解(2)——sds
Redis内部資料結構詳解(1)——dict
知識的三個層次
技術的成長曲線
技術的正宗與野路子