2017-08-03 11:32:00
來源：
導語 : 在單機環境下，由于使用環境簡單和通信可靠，鎖的可見性和原子性很容易可以保證，可以簡單和可靠地實現鎖功能。到了分布式的環境下，由于公共資源和使用方之間的分離，以及使用方和使用方之間的分離，相互之間的通信由線程間的內存通信變為網絡通信。網絡通信的時延和不可靠，加上分布式環境中各種故障的常態化發生，導致實現一個可靠的分布式鎖服務需要考慮更多更復雜的問題。
前言
鎖，核心是協調各個使用方對公共資源使用的一種機制。當存在多個使用方互斥地使用某一個公共資源時，為了避免并行使用導致的修改結果不可控，需要在某個地方記錄一個標記，這個標記能夠被所有使用方看到，當標記不存在時，可以設置標記并且獲得公共資源的使用權，其余使用者發現標記已經存在時，只能等待標記擁有方釋放后，再去嘗試設置標記。這個標記即可以理解為鎖。
在單機多線程的環境下，由于使用環境簡單和通信可靠，鎖的可見性和原子性很容易可以保證，所以使用系統提供的互斥鎖等方案，可以簡單和可靠地實現鎖功能。到了分布式的環境下，由于公共資源和使用方之間的分離，以及使用方和使用方之間的分離，相互之間的通信由線程間的內存通信變為網絡通信。網絡通信的時延和不可靠，加上分布式環境中各種故障的常態化發生，導致實現一個可靠的分布式鎖服務需要考慮更多更復雜的問題。
目前常見的分布式鎖服務，可以分為以下兩大類：
基于分布式緩存實現的鎖服務及其變種：典型代表是使用Redis實現的鎖服務和基于Redis實現的RedLock方案;
基于分布式一致性算法實現的鎖服務：典型代表為Zookeeper和Chubby。
本文從上述兩大類常見的分布式鎖服務實現方案入手，從分布式鎖服務的各個核心問題(核心架構、鎖數據一致性、鎖服務可用性、死鎖預防機制、易用性、性能)展開，嘗試對比分析各個實現方案的優劣和特點。
1、基于分布式緩存實現的鎖服務
基于分布式緩存實現的鎖服務，思路最為簡單和直觀。和單機環境的鎖一樣，我們把鎖數據存放在分布式環境中的一個唯一結點，所有需要獲取鎖的調用方，都去此結點訪問，從而實現對調用方的互斥，而存放鎖數據的結點，使用各類分布式緩存產品充當。其核心架構如下(以Redis為例)：
圖1.基于分布式緩存實現的鎖服務典型架構
1.1 加解鎖流程
基于Redis官方的文檔，對于一個嘗試獲取鎖的操作，流程如下：
1、 向Redis結點發送命令：
SET (key=Lock_Name，value=my_random_value) NX PX 30000
其中：
(1)my_random_value是由客戶端生成的一個隨機字符串，它要保證在足夠長的一段時間內在所有客戶端的所有獲取鎖的請求中都是唯一的，用于唯一標識鎖持有方。
(2)NX表示只有當Lock_Name對應的key值不存在的時候才能SET成功。這保證了只有第一個請求的客戶端才能獲得鎖，而其它客戶端在鎖被釋放之前都無法獲得鎖。
(3)PX 30000表示這個鎖結點有一個30秒的自動過期時間。(自動過期時間，目的是為了防止持有鎖的客戶端故障后，鎖無法被釋放導致死鎖而設置，從而要求鎖擁有者必須在過期時間之內執行完相關操作并釋放鎖)。(對于第二、三點的特性，目前應該絕大部分緩存產品都具備)
2、 如果命令返回成功，則代表獲取鎖成功，否則獲取鎖失敗。
對于一個擁有鎖的客戶端，釋放鎖，其流程如下：
(1) 向Redis結點發送命令：
GET (key=Lock_Name)
(2) 如果查詢回來的value和本身my_random_value一致，則表示自己是鎖的持有者，可以發起解鎖操作，發送命令：
DEL (key=Lock_Name)
1.2 鎖安全性分析
基于上述流程，由于Redis結點是單點存在，所以在鎖過期時間之內且Redis結點不發生故障的情況下，鎖的安全性(即互斥性)可以得到保證。但是仍然有如下幾個問題需要考慮：
1、 預防死鎖的必要性
考慮如下場景，一個客戶端獲取鎖成功，但是在釋放鎖之前崩潰了，此時實際上它已經放棄了對公共資源的操作權，但是卻沒有辦法請求解鎖，那么它就會一直持有這個鎖，而其它客戶端永遠無法獲得鎖。因此，對于絕大部分場景，此類死鎖場景是應該得到考慮和避免。
2、 引入鎖自動過期時間來預防死鎖帶來的問題
為了預防死鎖，利用分布式緩存的結點自動過期特性來定期刪除死鎖結點，看似可以解決問題。但是其中隱藏的隱患是：實質上，鎖自動過期清理是釋放了一個不屬于自己的鎖。那么幾乎必然的，會破壞鎖的互斥性，考慮如下場景：
(1)客戶端1獲取鎖成功
(2)客戶端1在某個操作上阻塞了很長時間
(3)過期時間到，鎖自動釋放
(4)客戶端2獲取到了對應同一個資源的鎖
(5)客戶端1從阻塞中恢復過來，認為自己依舊持有鎖，繼續操作同一個資源，導致互斥性失效
也許有一個疑問，第五步中，客戶端1恢復回來后，可以比較下目前已經持有鎖的時間，如果發現已經快過期，則放棄對共享資源的操作即可避免互斥性失效的問題。事實上，客戶端1的時間和Redis結點的時間本身就存在偏移的可能性，更極端一點，Redis上的時間還可能發生跳變或者比客戶端時間跑得更快，所以，嚴格來講，任何依賴兩個時間比較的互斥性算法，都存在潛在的隱患。
3、 解鎖操作的原子性
引入全局唯一的my_random_value，目的是想保證每次解鎖操作，一定是解鎖的自己加的鎖。由于Redis沒有能夠提供基于數據版本號來刪除Key的原子操作的特性，其Watch的CAS機制本身基于連接(有其他的分布式緩存產品能夠支持這個特性)。因此解鎖需要兩步，先查鎖回來確認Value這把鎖是自己加的，然后再發起Del解鎖。由于Get和Del操作的非原子性，那么解鎖本身也會存在破壞互斥性的情況，考慮如下場景：
(1)客戶端1獲取鎖成功。
(2)客戶端1訪問共享資源。
(3)客戶端1為了釋放鎖，先執行'GET'操作獲取隨機字符串的值。
(4)客戶端1判斷隨機字符串的值，與預期的值相等。
(5)客戶端1由于某個原因阻塞住了很長時間。
(6)過期時間到了，鎖自動釋放了。
(7)客戶端2獲取到了對應同一個資源的鎖。
(8)客戶端1從阻塞中恢復過來，執行DEL操縱，釋放掉了客戶端2持有的鎖。
4、 Redis結點故障后，主備切換的數據一致性
考慮Redis結點宕機，如果長時間無法恢復，則導致鎖服務長時間不可用。為了保證鎖服務的可用性，通常的方案是給這個Redis節點掛一個Slave，當Master節點不可用的時候，系統自動切到Slave上。但是由于Redis的主從復制(replication)是異步的，這可能導致在宕機切換過程中喪失鎖的安全性。考慮下面的時序：
(1)客戶端1從Master獲取了鎖。
(2)Master宕機了，存儲鎖的key還沒有來得及同步到Slave上。
(3)Slave升級為Master。
(4)客戶端2從新的Master獲取到了對應同一個資源的鎖。
(5)客戶端1和客戶端2同時持有了同一個資源的鎖。鎖的安全性被打破。
設想下，如果要避免這種情況，只有在寫數據的時候，就阻塞地把數據寫多份，全部寫成功才返回，這樣才能保證鎖的安全性(分布式緩存的同步主從復制)。但這樣就可以即保證數據一致性，又保證服務可用性了嗎?其實不然，在鎖數據寫Master和Slave兩份，都寫成功才認為加鎖成功的情況下，如果Master寫成功，Slave寫超時(其實寫成功了)，這個時候認為加鎖是失敗的，但是主和備的數據產生了不一致，而且Slave自身穩定性以及Master和Slave的通信穩定性還成為了導致服務不可用的額外因素。所以基于分布式緩存實現的鎖服務，要想解決分布式系統一致性和可用性的核心問題，并不是簡單的主從同步可以搞定(核心還是要靠Paxos這樣的分布式一致性協議)。
1.3 總結
1、鎖服務性能
由于鎖數據基于Redis等分布式緩存保存，基于內存的數據操作特性使得這類鎖服務擁有著非常好的性能表現。同時鎖服務調用方和鎖服務本身只有一次RTT就可以完成交互，使得加鎖延遲也很低。所以，高性能、低延遲是基于分布式緩存實現鎖服務的一大優勢。因此，在對性能要求較高，但是可以容忍極端情況下丟失鎖數據安全性的場景下，非常適用。
2、數據一致性和可用性
鎖數據一致性基于上述的分析，基于分布式緩存的鎖服務受限于通用分布式緩存的定位，無法完全保證鎖數據的安全性，核心的問題可以概括為三點：
(1)鎖數據寫入的時候，沒有保證同時寫成功多份：任何事后的同步在機制上都是不夠安全的，因此在故障時，鎖數據存在丟失的可能。解決此類問題，需要在寫多份和服務可用性之間找到平衡(典型思想：多數派，詳細描述見后面的兩類鎖服務方案)。
(2)沒有原子性的保證持有者才能解鎖：鎖服務需要提供一種機制，使得在網絡各種亂序以及包重放的時候，保證只有鎖當前持有者方能解鎖，同時要保證解鎖操作的原子性。
(3)鎖服務缺乏和調用方(或者公共資源方)的確認機制：預防死鎖等問題，光靠鎖服務自身，是不夠安全的，只有調用方和公共資源的一同參與，方能全面保證(Chubby提供了一種做法，詳細見后面的描述)
2、基于分布式緩存實現鎖服務的變種
基于分布式緩存實現鎖服務，在業界還存在各類變種的方案，其核心是利用不同分布式緩存產品的額外特性，來改善基礎方案的各類缺點，各類變種方案能提供的安全性和可用性也不盡相同。此處介紹一種業界最出名，同時也是引起過最大爭論的一個鎖服務變種方案-RedLock。
RedLock由Redis的作者Antirez提出，算是Redis官方對于實現分布式鎖的指導規范。Redlock的算法描述就放在Redis的官網上(https://redis.io/topics/distlock)。
選擇對比分析RedLock，第一是因為它作為Redis官方的鎖服務指導規范，在提出的時候業內也對其進行過很多爭議和討論;第二是RedLock的算法中，已經有了分布式一致性算法中最核心的概念-多數派的思想。因此我們在眾多變種中選擇RedLock來進行介紹和分析。
2.1 核心架構和流程
圖2.RedLock鎖服務流程圖
對于一個客戶端，依次執行下面各個步驟，來完成獲取鎖的操作：
(1)獲取當前時間(毫秒數)。
(2)按順序依次向N個Redis節點執行獲取鎖的操作(其實可以并發同時向N個Redis獲取鎖)。這個獲取操作跟前面基于單Redis節點的獲取鎖的過程相同，包含隨機字符串my_random_value，也包含過期時間。為了保證在某個Redis節點不可用的時候算法能夠繼續運行，這個獲取鎖的操作還有一個超時時間，它要遠小于鎖的有效時間。客戶端在向某個Redis節點獲取鎖失敗以后，應該立即嘗試下一個Redis節點。這里的失敗，應該包含任何類型的失敗，比如該Redis節點不可用，或者該Redis節點上的鎖已經被其它客戶端持有。
(3)計算整個獲取鎖的過程總共消耗了多長時間，計算方法是用當前時間減去第1步記錄的時間。如果客戶端從大多數Redis節點(>= N/2+1)成功獲取到了鎖，并且獲取鎖總共消耗的時間沒有超過鎖的有效時間，那么這時客戶端才認為最終獲取鎖成功;否則，認為最終獲取鎖失敗。
(4)如果最終獲取鎖成功了，那么這個鎖的有效時間應該重新計算，它等于最初的鎖的有效時間減去第3步計算出來的獲取鎖消耗的時間。
(5)如果最終獲取鎖失敗了(可能由于獲取到鎖的Redis節點個數少于N/2+1，或者整個獲取鎖的過程消耗的時間超過了鎖的最初有效時間)，那么客戶端應該立即向所有Redis節點發起釋放鎖的操作(同基于單Redis節點的釋放一致)。釋放鎖的過程比較簡單，客戶端向所有Redis節點發起釋放鎖的操作，不管這些節點當時在獲取鎖的時候成功與否。
2.2 鎖安全性分析
RedLock算法的最核心也是最有價值之處，是引入了多數派思想，來解決單點故障對數據安全性和服務可用性的影響。由于加鎖成功需要所有Redis結點中的多數結點同意，因此只要集群中結點有一半能夠提供服務時，服務的可用性就能夠保證。同時對于數據的一致性，只要對于一把鎖，其多數派結點的數據不丟，那么鎖就不可能被另外的調用方同時獲得(不夠多數派)，所以鎖的安全性也可以得到保證。所以從核心算法來說，多數派的思想是對數據一致性的保證下，向保證服務可用性又進了一大步。
但是，多數派僅僅是算法最核心的理論保證。要實現一個工程上完全保證鎖數據安全性，同時高可用的鎖服務，RedLock還有很遠的距離，這也是RedLock在業界引起很多爭議的地方，核心的問題見下面的分析。
1、 RedLock的安全性依舊強依賴于系統時間
在之前單點Redis鎖服務的時候已經分析過，由于為了預防死鎖，使用了過期自動刪除鎖的機制，所以導致安全性依賴于單機Redis上的時間服務不能異常，從而存在隱患(本質是違反了鎖持有者才能刪除鎖的原則)。同樣的，到了RedLock中，仍然有此問題，考慮如下的時序：假設一共有5個Redis節點：A, B, C, D, E。
(1)客戶端1成功鎖住了A, B, C，獲取鎖成功(但D和E沒有鎖住)。
(2)節點C時間異常，導致C上的鎖數據提前到期，而被釋放。
(3)客戶端2此時嘗試獲取同一把鎖：鎖住了C, D, E，獲取鎖成功。
所以一個安全的算法，是不應該依賴于系統時間的。消息可能在網絡中延遲任意長的時間，甚至丟失，系統時鐘也可能以任意方式出錯。一個好的分布式算法，這些因素不應該影響它的安全性，只可能影響到它的有效性，也就是說，即使在非常極端的情況下(比如系統時鐘嚴重錯誤)，算法頂多是不能在有限的時間內給出結果而已，而不應該給出錯誤的結果。
2、 缺乏鎖數據丟失的識別機制和恢復機制
假設一共有5個Redis節點：A, B, C, D, E。見如下的事件序列：
(1)客戶端1成功鎖住了A, B, C，獲取鎖成功(但D和E沒有鎖住)。
(2)節點C崩潰重啟了，但客戶端1在C上加的鎖沒有持久化下來，丟失了。(Redis的AOF持久化方式是每秒寫一次磁盤(即執行fsync)，因此最壞情況下可能丟失1秒的數據。為了盡可能不丟數據，Redis允許設置成每次修改數據都進行fsync，但這會降低性能。當然，即使執行了fsync也仍然有可能丟失數據(這取決于系統而不是Redis的實現)。
(3)節點C重啟后，客戶端2鎖住了C, D, E，獲取鎖成功。
(4)客戶端1和客戶端2現在都認為自己持有了鎖。
此類問題的本質，是作為多數派數據的一個結點，數據丟失之后(比如故障未落地、超時被清理等等)，首先沒有能夠區分丟失了哪些數據的能力，其次還沒有恢復丟失數據的能力。這兩種能力都缺乏的情況下，數據結點就繼續正常地參與投票，從而導致的數據一致性被破壞。
RedLock也意識到了這個問題，所以在其中有一個延遲重啟(delayed restarts)的概念。也就是說，一個節點崩潰后，先不立即重啟它，而是等待一段時間再重啟，這段時間應該大于其上所有鎖的有效時間的最大值。這樣的話，這個節點在重啟前所參與的鎖都會過期，它在重啟后就不會對現有的鎖造成影響。這個方案，是在缺乏丟失數據識別的能力下，實現的較“悲觀”的一個替代方案，首先其方案依舊依賴于時間，其次如何確定最大過期時間，也是一個麻煩的事情，因為最大過期時間很可能也一起丟失了(未持久化)，再有延遲重啟使得故障結點恢復的時間延長，增加了集群服務可用性的隱患。怎么來看，都不算一個優雅的方案。
2.3 總結
1、鎖服務性能
由于RedLock鎖數據仍然基于Redis保存，所以和基于單點的Redis鎖一樣，具有高性能和低延遲的特性，不過由于引入多數派的思想，加鎖和解鎖時的并發寫，所以在流量消耗來說，比基于單點的Redis鎖消耗要大。從資源角度來說，是用流量換取了比單點Redis稍高的數據一致性和服務可用性。
2、數據一致性和可用性
RedLock的核心價值，在于多數派思想。不過根據上面的分析，它依然不是一個工程上可以完全保證鎖數據一致性的鎖服務。相比于基于單點Redis的鎖服務，RedLock解決了鎖數據寫入時多份的問題，從而可以克服單點故障下的數據一致性問題，但是還是受限于通用存儲的定位，其鎖服務整體機制上的不完備，使得無法完全保證鎖數據的安全性。在繼承自基于單點的Redis鎖服務缺陷(解鎖不具備原子性;鎖服務、調用方、資源方缺乏確認機制)的基礎上，其核心的問題為：缺乏鎖數據丟失的識別和學習機制。
RedLock中的每臺Redis，充當的仍舊只是存儲鎖數據的功能，每臺Redis之間各自獨立，單臺Redis缺乏全局的信息，自然也不知道自己的鎖數據是否是完整的。在單臺Redis數據的不完整的前提下，沒有識別和學習機制，使得在各種分布式環境的典型場景下(結點故障、網絡丟包、網絡亂序)，沒有完整數據但參與決策，從而破壞數據一致性。
