“分布式鎖”這個問題快被說爛了,奈何筆者實在沒有找到一個滿意的答案,故記錄自己尋找答案、總結的過程。分布式鎖的設計涉及了許多分布式系統相關的問題,許多地方值得推敲,非常有意思。
太長不看?沒關系,我已經做好了思維導圖,點個分享再收藏,支持一下,也方便以后查閱。
分布式鎖三個屬性和兩大類
多線程編程通常使用 mutex 或信號量等方式進行同步;在同一個操作系統下的多進程也能通過共享內存等方式同步;但在分布式系統多進程之間的資源爭搶,例如下單搶購,就需要額外的分布式鎖。
分布式鎖大多都是 Advisory lock,即在訪問數據前先獲取鎖信息,再根據信息決定是否可以訪問;相對的是 mandatory lock,未授權訪問鎖定的數據時會產生異常。
分布式鎖屬于分布式互斥問題(distributed mutual exclusion),實際上 Lamport 在那篇經典論文 “Time, clocks, and the ordering of events in a distributed system” 中早就證明了使用狀態機能夠去中心化解決多進程互斥問題,而共識算法就能實現這樣的狀態機。但大多時候我們還是會使用一個分布式鎖而不是構建一個共識庫,主要因為:
很多(業務)系統很難改造成使用共識算法,鎖服務更易于保持已存在的程序結構和通信模式;
基于鎖的接口更為程序員所熟悉。雖然可能只是表面熟悉 :),但肯定好過使用一個共識庫;
鎖服務能減少客戶端系統運行的服務器數目。一個共識算法需要 quorum 做決策,即我們常說的超過半數節點可用,每個客戶端都構建成 quorum 需要大量的服務器,而一套分布式鎖服務可以安全地服務多個客戶端。
因此,相比于客戶端實現一個共識庫,使用分布式鎖服務耦合更松、更易用、也更節省資源。
提起分布式鎖,大家可能馬上會想到各種實現方式,以及一場關于基于 Redis 實現的分布式鎖是否安全的論戰,這些文章可能很多地方都能搜到。但在開始討論這些東西之前,我們首先要思考,一個分布式鎖到底需要具備哪些性質?
總的來說,分布式鎖服務有三個必備的性質:
互斥(Mutual Exclusion),這是鎖最基本的功能,同一時刻只能有一個客戶端持有鎖;
避免死鎖(Dead lock free),如果某個客戶端獲得鎖之后花了太長時間處理,或者客戶端發生了故障,鎖無法釋放會導致整個處理流程無法進行下去,所以要避免死鎖。最常見的是通過設置一個 TTL(Time To Live,存活時間) 來避免死鎖。假設設置 TTL 為 3 秒,如果 3 秒過后鎖還沒有被釋放,系統也會自動釋放該鎖(TTL 的設置要非常小心!這個時長取決于你的業務邏輯)。可是這也存在一個問題,假如進程1獲取了鎖,然后由于某些原因(下面會說到)沒有來得及更新 TTL;3秒后進程2來獲取鎖,由于 TTL 已過,進程2可以獲得鎖并開始處理,此時同時有兩個客戶端持有鎖,可能會產生意外行為。所以我們不能只有 TTL,還需要給鎖附加一個唯一 ID (或 fencing token)來標識鎖。上述邏輯中,當進程 1 獲取到鎖后記為 LOCK_1;TTL 過后進程 2 獲取到的鎖記為 LOCK_2。之后,我們可以在應用層面或鎖服務層面檢查該 id,來阻斷舊的請求。
容錯(Fault tolerance),為避免單點故障,鎖服務需要具有一定容錯性。大體有兩種容錯方式,一種是鎖服務本身是一個集群,能夠自動故障切換(ZooKeeper、etcd);另一種是客戶端向多個獨立的鎖服務發起請求,其中某個鎖服務故障時仍然可以從其他鎖服務讀取到鎖信息(Redlock),代價是一個客戶端要獲取多把鎖,并且要求每臺機器的時鐘都是一樣的,否則 TTL 會不一致,可能有的機器會提前釋放鎖,有的機器會太晚釋放鎖,導致出現問題。
值得注意的是,容錯會以性能為代價,容錯性取決于你的系統級別,如果你的系統可以承擔分布式鎖存在誤差,那么單節點或者簡單的主從復制也許就能滿足;如果你的系統非常嚴格,例如金融系統或航天系統,那么就要考慮每個 corner case——本文更傾向于討論后者。
我們會拿著這三個屬性逐一分析各種分布式鎖的實現。在此之前,先把分布式鎖分為兩大類:自旋類和監聽類。
自旋類包括基于數據庫的實現和基于 Redis 的實現,這類實現需要客戶端不停反復請求鎖服務查看是否能夠獲取到鎖;
監聽類主要包括基于 ZooKeeper 或 etcd 實現的分布式鎖,這類實現客戶端只需監聽(watch) 某個 key,當鎖可用時鎖服務會通知客戶端,無需客戶端不停請求鎖服務。
因此,本文默認讀者大概了解 Redis、ZooKeeper 和 etcd 是什么。
如此,我們在頭腦中已經有了一個很好的框架,現在開始往思維導圖中填充知識。
基于數據庫的實現
最簡單的,我們想到通過某個獨立的數據庫(或文件),當獲取到數據時,往數據庫中插入一條數據。之后的進程想要獲取數據,會先檢查數據庫是否存在記錄,就能夠知道是否有別的進程持有鎖,這便實現了分布式鎖的互斥性。
數據庫可以通過主從同步復制來實現容錯,雖然主從復制切換時不會非常輕松,可能需要管理員參與。
為了避免死鎖,我們需要增加時間戳字段和自增 id 字段,同時在后臺啟動一個線程定時釋放和清理過期的鎖。
字段作用
id自增 id,唯一標識鎖
key鎖名稱
value自定義字段
ttl存活時間,定時清理,避免死鎖
可見基于數據庫的實現較為繁瑣,要自己維護鎖的 TTL;除非使用分布式數據庫,否則主從復制的故障切換并不輕松。
除了麻煩之外,如果經常用數據庫你也知道,在高并發常見下數據庫讀寫是非常緩慢的,會導致我們的系統性能存在瓶頸。如果采用多個獨立數據庫進行容錯,那性能就更差了。
于是,為了分布式鎖的性能,開始轉向基于 Redis 或者 memcache 等內存存儲系統來實現分布式鎖。
基于 Redis 的實現
分布式鎖最多的恐怕就是基于 Redis 的實現。首先我們從單節點 Redis 開始。
基于單節點 Redis 的分布式鎖
總的來說就是一條命令實現寫 key + 設置過期時間,否則原子性無法保證可能出現死鎖。于是就有了以下命令:
set key value nx px 10000
set 命令后的 5 個參數分別是:
第一個為 key 作為鎖名;
第二個為 value,一般傳入一個唯一 id,例如一個隨機數或者客戶端 mac 地址 + uuid;
第三個為 NX,意思是 SET IF NOT EXIST,即只有 key 不存在時才進行 set 操作;若 key 已經存在(鎖已被占),則不做任何操作;
第四個為 PX,作用是給這個 key 加一個過期時間,具體時間長短由第五個參數決定;
第五個為具體的過期時間,對應第四個參數 PX 是毫秒,EX 是秒;
這個方案在互斥性和避免死鎖上性能良好,且非常輕量。但單節點的 Redis 存在單點故障。注意,Redis 主從復制是異步的,所以加入從節點會增加破壞互斥性的風險。為了實現容錯性,就有了基于多節點 Redis 的分布式鎖,即 Redlock。
基于多節點 Redis 的分布式鎖
Redlock 用到多個獨立的 Redis 節點,其思想簡而言之,是在多個 Redis 實際都獲取鎖,其中一個宕機了,只要還有超過半數節點可用,就可以繼續提供鎖服務。
如圖所示,Redlock 獲取鎖的大致步驟如下,:
依次對多個 Redis 實例進行加鎖(一般是3個或5個),加鎖命令使用單實例 Redis 的加鎖命令;
為了避免在某個節點長時間獲取不到鎖而阻塞,每次獲取鎖操作也有一個超時時間,遠小于 TTL,超過超時時間則認為失敗,繼續向下一個節點獲取鎖;
計算整個獲取多把鎖的總消耗時間,只有在超過半數節點都成功獲取鎖,并且總消耗時間小于 TTL,則認為成功持有鎖;
成功獲取鎖后,要重新計算 TTL = TTL - 總消耗時間;
如果獲取鎖失敗,要向所有 redis 實例發送釋放鎖的命令。
釋放鎖操作就是向所有實例都發送刪除 key 命令。
Redlock 容錯性依賴于一個時間戳的計算,這在分布式系統中并不受待見,于是有了一場著名的論戰。
Redlock 論戰
DDIA 的作者 Martin Kleppmann 大佬發表了著名的文章《How to do distributed locking》,表示 Redlock 并不可靠,該文章主要闡述了兩個觀點:
Redis 命令避免了死鎖但可能會不滿足互斥性,因為沒有自增 id 或 fencing token 來阻斷同時獲得鎖的兩個客戶端;
Redlock 基于時間戳的合理性值得懷疑,多臺服務器難以保證時間一致;
第一點如下圖所示,Client 1 獲取鎖后發生了 STW GC(或缺頁等問題),TTL 過期后 Client 2 獲取了鎖,此時兩個客戶端持有鎖,違反了互斥性。后續寫操作自然就可能存在問題。
我們在避免死鎖時提到,需要另外用單調遞增 id (Martin 稱之為 fencing token,也叫序列號)來標識每一個鎖。增加 id 后邏輯如下圖所示,最后的 Client 1 的寫請求因為 token 是舊的,會被存儲系統拒絕。
第二點 Martin 認為,Redlock 的時間戳計算方式不可靠,每臺服務器的走時并不絕對準確,例如 NTP 進行同步時系統會發生時鐘漂移,即當前服務器的時間戳突然變大或變小,這都會影響 Redlock 的計算。
Martin 的這篇文章引起了大家對分布式鎖廣泛討論。Redis 作者 antirez 也不甘示弱,發表文章《Is Redlock safe?》進行反駁,回應了上述兩個問題,我總結了 antirez 的論點:
針對第一點,雖然 Redlock 提供不了自增 id 這樣的字段,但是由客戶端指定的字段 value 也可以實現唯一標識,并通過 read-modify-write 原子操作來進行檢查;
時鐘發送漂移肯定會影響 Redlock 安全性,可是通過恰當的運維,例如不要隨意人為修改時鐘、將一次大的 NTP 時鐘調整轉換成多次微小的調整等方式,使時鐘修改不超過某個范圍就不會對 Redlock 產生影響。
非常推薦閱讀爭論的兩篇文章,但篇幅所限我只提取了觀點。關于爭論的詳細內容張鐵蕾老師的文章《基于Redis的分布式鎖到底安全嗎(下)?》也有著比較完整的中文回顧。
對于這兩個問題,我想談談我的理解。
對于第一個問題,文章開頭“三大屬性”我們就分析過,增加 TTL 來避免死鎖就會對互斥性產生影響,無論基于 Redis 還是基于 Zookeeper 實現都會存在該問題。antirez 觀點是 Redlock 也可以用 value 作為唯一標識來阻斷操作,這確實沒問題,我也挑不出毛病。但我們可以思考下,實際編程中讀者您覺得使用一個自增 id 進行判斷容易還是使用 read-modify-write 操作更容易呢?(實際上,一開始我都不怎么理解什么是 read-modify-write 操作)
我認為 fencing token 是一個更好的解決方案,一個單調自增的 id 更符合我們的直覺,同時也更好進行 debug。
作為 fencing token 的一個實際參考,Hazelcast 的文章 “Distributed Locks are Dead; Long Live Distributed Locks!” 給出了一個 FencedLock 解決方案,并且通過了 Jepsen 測試。
第二個問題,時鐘漂移是否應該引起注意呢?antirez 的觀點是時鐘確實會影響 Redlock,但可以通過合理運維避免。
Julia Evans(也是很出名的技術博主)也寫了一篇后續文章 “TIL: clock skew exists”,來討論時鐘漂移的問題是否真的值得引起注意。最終得出的結論是:有界的時鐘漂移不是一個安全的假設。
事實上,時鐘問題并不罕見,例如:
Nelson Minar 在1999年發表了論文,通過調查發現,NTP 服務器經常提供不正確的時間;
aphyr 的文章《The trouble with timestamps》也總結了時間戳在分布式系統中的麻煩;
Google 在 Spanner 中投入大量精力來處理時間問題,并發明了 TrueTime 這一授時系統;
閏秒也會導致時鐘漂移,不過閏秒確實非常罕見(即使是現在,閏秒依然會導致許多問題,以后我們會專門談談)。
通過上述例子,時鐘問題是真實存在的,如果你的系統對分布式鎖的安全性要求嚴格,不想造成任何系統和金錢上的損失,那么你應該考慮所有的邊緣情況。
Martin Kleppmann 沒有回復任何 Hacker News 的評論,他覺得自己想要表達的都已經說完了,他不想參與爭論,他認為實際上一個分布式系統到底該怎么做取決于你如何管理你的系統。
本文想表達的也是這樣的觀點,軟件工程沒有銀彈,這些 trade-off 取決于你系統的重要級別,你怎么管理你的分布式系統。
只不過分布式系統研究人員通常會非常關注那些看似非常不可能在你的電腦上發生的事情(例如:時鐘偏移),原因是:
需要找出某個算法來解決此類問題,因此需要考慮所有 corner case;
分布式系統中會有成千上萬的機器,那么不大可能發生的事情會變得極有可能;
其中一些問題其實是很常見的(例如:網絡分區)。
基于 ZooKeeper 實現
除了 Redlock,還有哪些既能容錯又能避免死鎖的方式呢?
容錯性當然離不開我們的老朋友共識算法,我們不再讓客戶端依次上多個鎖,而是讓鎖服務器通過共識算法復制到多數派節點,然后再回復客戶端。由于共識算法本身不依賴系統時間戳而是邏輯時鐘(Raft 的任期或 Paxos 的 epoch),故不存在時鐘漂移問題。
其次,死鎖避免問題依然需要 TTL 和自增 id 等手段,我們通過鎖服務給每次加鎖請求標識上單調遞增 id。
通過以上兩種方法,我們可以得到一個更可靠的分布式鎖。代價是,我們需要一個實現共識算法的第三方組件。下文主要介紹三個此類實現:ZooKeeper、etcd 和 Chubby。
ZooKeeper 是一個分布式協調服務,參見:《ZooKeeper 設計原理》。
基于 ZooKeeper 實現的分布式鎖依賴以下兩個節點屬性:
sequence:順序節點,ZooKeeper 會將一個10位帶有0填充的序列號附加到客戶端設置的 znode 路徑之后。例如 locknode/guid-lock- 會返回 locknode/guid-lock-0000000001;
ephemeral:臨時節點,當客戶端和 ZooKeeper 連接斷開時,臨時節點會被刪除,能夠避免死鎖。但這個斷開檢測依然有一定心跳延遲,所以仍然需要自增 id 來避免互斥性被破壞。
ZooKeeper 官方文檔有提供現成的分布式鎖實現方法:
首先調用 create(),鎖路徑例如 locknode/guid-lock-,并設置 sequence 和 ephemeral 標志。guid 是客戶端的唯一標識,如果 create() 創建失敗可以通過 guid 來進行檢查,下面會提到;
調用 getChildren() 獲取子節點列表,不要設置 watch 標志(很重要,可以避免 Herd Effect,即驚群效應);
檢查 2 中的子節點列表,如果步驟 1 中創建成功并且返回的序列號后綴是最小的,則客戶端持有該分布式鎖,到此結束;
如果發現序列不是最小的,則從子節點列表中選擇比當前序列號小一位的節點記為 p,客戶端調用 exist(p, watch=true),即監聽 p,當 p 被刪除時收到通知(該節點只有比自己小一位的節點釋放時才能獲得鎖);
如果 exist() 返回 null,即前一個分布式鎖被釋放了,轉到步驟 2;否則需要一直等待步驟 4 中 watch 的通知。
每個客戶端只監聽比自己小的 znode,可以避免驚群效應。
獲取鎖的偽代碼如下:
n = create(l + “/guid-lock-”, EPHEMERAL|SEQUENTIAL)
C = getChildren(l, false)
if n is lowest znode in C, exit
p = znode in C ordered just before n
goto 2
釋放鎖非常簡單:客戶端直接刪除他們在步驟 1 創建的 znode 節點。
有幾點需要注意:
刪除一個 znode 只會導致一個客戶端被喚醒,因為每個節點正好被一個客戶端 watch 著,通過這種方式,可以避免驚群效應;
沒有輪詢或超時;
如果在調用 create() 時 ZooKeeper 創建鎖成功但沒有返回給客戶端就失敗了,客戶端收到錯誤響應后,應該先調用 getChildren() 并檢查該路徑是否包含 guid 來避免這一問題。
當然,雖然 ZooKeeper 的實現看起來更為可靠,但根據你實現鎖的方式,可能還是會有大量的鎖邏輯調試、鎖爭搶等問題。
基于 ZooKeeper 的分布式鎖性能介于基于 Mysql 和基于 Redis 的實現之間,性能上當然不如單節點 Redis。
ZooKeeper 的另一個缺點是需要另外維護一套 ZooKeeper 服務(已有則忽略)。
etcd
Etcd 是著名的分布式 key-value 存儲結構,因在 Kubernetes 中使用而聞名。etcd 同樣可以用來實現分布式鎖,官方也很貼心的提供了 clientv3 包給開發者快速實現分布式鎖。
我們來看下 etcd 是如何解決分布式鎖“三大問題”的:
互斥:etcd 支持事務,通過事務創建 key 和檢查 key 是否存在,可以保證互斥性;
容錯:etcd 基于 Raft 共識算法,寫 key 成功至少需要超過半數節點確認,這就保證了容錯性;
死鎖:etcd 支持租約(Lease)機制,可以對 key 設置租約存活時間(TTL),到期后該 key 將失效刪除,避免死鎖;etc 也支持租約續期,如果客戶端還未處理完可以繼續續約;同時 etcd 也有自增 id,在下文介紹。
為了幫助開發者快速實現分布式鎖,etcd 給出了 clientv3 包,其中分布式鎖在 concurrency 包中。按照官方文檔給出的案例1,首先創建一個新的會話(session)并指定租約的 TTL,然后實例化一個 NewMutex() 之后就可以調用 Lock() 和 Unlock() 進行搶鎖和釋放鎖。代碼如下:
cli, err := clientv3.New(clientv3.Config{Endpoints: endpoints})
if err != nil {
log.Fatal(err)
}
defer cli.Close()
s, err := concurrency.NewSession(cli, concurrency.WithTTL(10))
if err != nil {
log.Fatal(err)
}
defer s.Close()
m := concurrency.NewMutex(s, “/my-lock/”)
if err := m.Lock(context.TODO()); err != nil {
log.Fatal(err)
}
fmt.Println(“acquired lock for s”)
if err := m.Unlock(context.TODO()); err != nil {
log.Fatal(err)
}
fmt.Println(“released lock for s”)
其中 Lock() 函數的源代碼很容易找到,由于篇幅我就不放出來了,但源代碼中可以看到的一些其他機制包括:
Revision 機制。一個全局序列號,跟 ZooKeeper 的序列號類似,可以用來避免 watch 驚群;
Prefix 機制。即上述代碼中 etcd 會創建一個前綴為 /my-lock/ 的 key(/my-lock/ + LeaseID),分布式鎖由該前綴下 revision 最小(最早創建)的 key 獲得;
Watch 機制。跟 ZooKeeper 一樣,客戶端會監聽 revision 比自己小的 key,當比自己小的 key 釋放鎖后,嘗試去獲得鎖。
本質上 etcd 和 ZooKeeper 對分布式鎖的實現是類似的。
選擇 etcd 的原因可能有:
生產環境中已經大規模部署了 etcd 集群;
etcd 在保證強一致性的同時真的夠快,性能介于 Redis 和 ZooKeeper 之間;
許多語言都有 etcd 的客戶端庫,很容易使用;
Chubby
最后簡要談一下 Chubby。由于 Chubby 沒有開源,沒法直接使用,細節也難以得知,很少會有造一個 Chubby 的需求(雖然我老東家真的用 C++ 造了一個)。因此,Chubby 部分只是 Paper 讀后感,不感興趣的讀者可以跳過。
Chubby 是 Google 研發的松耦合分布式鎖服務,此外 GFS 和 BigTable 使用 Chubby 來存儲一些元數據。Chubby 有以下幾大特點:
粗粒度(Coarse-grained)。相對于細粒度(Fine-grained),粗粒度鎖會持續幾小時或幾天;
可用性、可靠性;
可以存儲一些元數據;
大量廉價機器部署;
Chubby 依賴于 Paxos 共識算法來實現容錯,數據以 UNIX 文件系統方式進行組織(稱為 Node),同樣有 Ephemeral 類型的臨時節點,斷開連接后會被刪除;支持監聽某個 Node——總而言之,我們可以從 ZooKeeper 上看到許多 Chubby 的影子,ZooKeeper 和 Chubby 解決的問題是比較類似的,因此很多人認為 ZooKeeper 是 Chubby 的開源實現,不過兩者的具體架構還是略有不同。
為了容錯,一個 Chubby 集群包含 5 個節點,組成一個 Chubby cell。這 5 個節點只有一個是 master 其余都是 replicas,只有 Master 能夠處理請求和讀寫文件,其它副本節點通過 Paxos 算法復制 Master 的行為來容錯。
Chubby 還支持:
Sequencer:鎖的序列號(更好的避免死鎖和 watch);
Session:客戶端會話,包括租約時間;
KeepAlive:在租約快要過期時可以發送 KeepAlive 續約;
Cache:鎖服務支持大量的客戶端,為了減少讀請求支持客戶端無感知的緩存;
比較有意思的是 Chubby 的故障恢復。當 Master 發生故障,其內存的 session 和鎖信息會丟失,session 中最重要的租約信息,Paxos 算法會選舉出新的 Master,然后:
選擇新的 epoch,可以理解為 Raft 中的任期,小于 epoch 的客戶端請求會被拒絕,保證了 Master 不會響應舊 Master 的請求;
根據數據庫(持久化存儲)中的數據恢復出 session 和鎖相關信息,并將 session 租約延長到一個可能的最大期限;
只接受 KeepAlive 請求;下圖步驟 4 中第一個 KeepAlive 請求會由于epoch錯誤而被 Maser 拒絕,但客戶端也因此獲得了最新的 epoch;步驟 6 中第二個 KeepAlive 成功,由于上一步延長的租約夠長,步驟 7 的響應會延長客戶端本地的租約時間;接著恢復正常的通信。
從新請求中發現老 Master 創建的 Handle 時,新 Master 也需要重建,一段時間后(一般是一分鐘),刪除沒有 Handle 的臨時節點。
整個過程如圖所示。其中綠色都是安全時期,橙色部分是危險時期,Chubby 集群切換到新的 Master。
Chubby 我不想太過深入,我想大家沒有再造一個 Chubby 的動力了。
結語
寫這篇文章的時候內心是忐忑的,為了 ego 和不被大家罵我盡量不犯錯,但錯誤實在難免,并且隨著時間推移可能兩三年后一些解決方案并不適用。這篇文章實在花了我許多時間和精力。
想要深入分布式鎖問題的同學,我推薦好好看一遍 Lamport 的 “Time, clocks, and the ordering of events in a distributed system”。
最后,本文如有不妥之處,希望讀者能夠留言指出,我會積極改正。
責任編輯:haq
-
數據
+關注
關注
8文章
7015瀏覽量
88989 -
分布式
+關注
關注
1文章
895瀏覽量
74501
原文標題:萬字長文說透分布式鎖
文章出處:【微信號:DBDevs,微信公眾號:數據分析與開發】歡迎添加關注!文章轉載請注明出處。
發布評論請先 登錄
相關推薦
評論