鎖 分布式鎖 distributed locks

distributedlocks.png

資源有限，爭(zhēng)搶難免，最簡(jiǎn)單粗暴的辦法是誰(shuí)的拳頭大誰(shuí)就可以搶到最好的資源。那在計(jì)算機(jī)世界里是如何搶奪資源(cpu, 內(nèi)存, 網(wǎng)絡(luò)等)的呢？

鎖

在多線程的軟件世界里，對(duì)共享資源的爭(zhēng)搶過(guò)程(Data Race)就是并發(fā)，而對(duì)共享資源數(shù)據(jù)進(jìn)行訪問(wèn)保護(hù)的最直接辦法就是引入鎖！。

POSIX threads(簡(jiǎn)稱Pthreads)是在多核平臺(tái)上進(jìn)行并行編程的一套常用的API。線程同步(Thread Synchronization)是并行編程中非常重要的通訊手段，其中最典型的應(yīng)用就是用Pthreads提供的鎖機(jī)制(lock)來(lái)對(duì)多個(gè)線程之間共 享的臨界區(qū)(Critical Section)進(jìn)行保護(hù)(另一種常用的同步機(jī)制是barrier)。

無(wú)鎖編程也是一種辦法，但它不在本文的討論范圍，并發(fā)多線程轉(zhuǎn)為單線程(Disruptor)，函數(shù)式編程，鎖粒度控制(ConcurrentHashMap桶)，信號(hào)量(Semaphore)等手段都可以實(shí)現(xiàn)無(wú)鎖或鎖優(yōu)化。

技術(shù)上來(lái)說(shuō)，鎖也可以理解成將大量并發(fā)請(qǐng)求串行化，但請(qǐng)注意串行化不能簡(jiǎn)單等同為** 排隊(duì) ，因?yàn)檫@里和現(xiàn)實(shí)世界沒(méi)什么不同，排隊(duì)意味著大家是公平Fair的領(lǐng)到資源，先到先得，然而很多情況下為了性能考量多線程之間還是會(huì)不公平Unfair**的去搶。Java中ReentrantLock可重入鎖，提供了公平鎖和非公平鎖兩種實(shí)現(xiàn)

再注意一點(diǎn)，串行也不是意味著只有一個(gè)排隊(duì)的隊(duì)伍，每次只能進(jìn)一個(gè)。當(dāng)然可以好多個(gè)隊(duì)伍，每次進(jìn)入多個(gè)。比如餐館一共10個(gè)餐桌，服務(wù)員可能一次放行最多10個(gè)人進(jìn)去，有人出來(lái)再放行同數(shù)量的人進(jìn)去。Java中Semaphore信號(hào)量，相當(dāng)于同時(shí)管理一批鎖

鎖的類型

1 自旋鎖 (Spin Lock)

自旋鎖如果已經(jīng)被別的線程獲取，調(diào)用者就一直循環(huán)在那里看是否該自旋鎖的保持者已經(jīng)釋放了鎖，”自旋”一詞就是因此而得名。

自旋鎖是一種非阻塞鎖，也就是說(shuō)，如果某線程需要獲取自旋鎖，但該鎖已經(jīng)被其他線程占用時(shí)，該線程不會(huì)被掛起，而是在不斷的消耗CPU的時(shí)間，不停的試圖獲取自旋鎖。

Java沒(méi)有默認(rèn)的自旋鎖實(shí)現(xiàn)，示例代碼如下：
<pre>
public class SpinLock {
private AtomicReference<Thread> sign =new AtomicReference<>();
public void lock(){
Thread current = Thread.currentThread();
while(!sign .compareAndSet(null, current)){
}
}
public void unlock (){
Thread current = Thread.currentThread();
sign .compareAndSet(current, null);
}
}
</pre>

通過(guò)示例，可以看到CAS原子操作將sign從期望的null設(shè)置為當(dāng)前線程，線程A第一次調(diào)用lock()可以獲取鎖，第二次調(diào)用將進(jìn)入循環(huán)等待，因?yàn)閟ign已經(jīng)被設(shè)置為了current。
簡(jiǎn)單加個(gè)當(dāng)前鎖的owner比對(duì)判斷和鎖計(jì)數(shù)器，即可實(shí)現(xiàn)重入。

2 互斥鎖 (Mutex Lock)

互斥鎖是阻塞鎖，當(dāng)某線程無(wú)法獲取互斥鎖時(shí)，該線程會(huì)被直接掛起，不再消耗CPU時(shí)間，當(dāng)其他線程釋放互斥鎖后，操作系統(tǒng)會(huì)喚醒那個(gè)被掛起的線程。

阻塞鎖可以說(shuō)是讓線程進(jìn)入阻塞狀態(tài)進(jìn)行等待，當(dāng)獲得相應(yīng)的信號(hào)（喚醒，時(shí)間）時(shí)，才可以進(jìn)入線程的準(zhǔn)備就緒狀態(tài)，準(zhǔn)備就緒狀態(tài)的所有線程，通過(guò)競(jìng)爭(zhēng)進(jìn)入運(yùn)行狀態(tài)。它的優(yōu)勢(shì)在于，阻塞的線程不會(huì)占用 CPU 時(shí)間， 不會(huì)導(dǎo)致 CPU 占用率過(guò)高，但進(jìn)入時(shí)間以及恢復(fù)時(shí)間都要比自旋鎖略慢。在競(jìng)爭(zhēng)激烈的情況下阻塞鎖的性能要明顯高于自旋鎖。

<pre>
JAVA中，能夠進(jìn)入/退出、阻塞狀態(tài)或包含阻塞鎖的方法有:
synchronized
ReentrantLock
Object.wait()/notify()
LockSupport.park()/unpart()(j.u.c經(jīng)常使用)
</pre>

自旋鎖 VS 互斥鎖
兩種鎖適用于不同場(chǎng)景：
如果是多核處理器，預(yù)計(jì)線程等待鎖的時(shí)間很短，短到比線程兩次上下文切換時(shí)間要少的情況下，使用自旋鎖是劃算的。

如果是多核處理器，如果預(yù)計(jì)線程等待鎖的時(shí)間較長(zhǎng)，至少比兩次線程上下文切換的時(shí)間要長(zhǎng)，建議使用互斥鎖。

如果是單核處理器，一般建議不要使用自旋鎖。因?yàn)?，在同一時(shí)間只有一個(gè)線程是處在運(yùn)行狀態(tài)，那如果運(yùn)行線程發(fā)現(xiàn)無(wú)法獲取鎖，只能等待解鎖，但因?yàn)樽陨聿粧炱?，所以那個(gè)獲取到鎖的線程沒(méi)有辦法進(jìn)入運(yùn)行狀態(tài)，只能等到運(yùn)行線程把操作系統(tǒng)分給它的時(shí)間片用完，才能有機(jī)會(huì)被調(diào)度。這種情況下使用自旋鎖的代價(jià)很高。

如果加鎖的代碼經(jīng)常被調(diào)用，但競(jìng)爭(zhēng)情況很少發(fā)生時(shí)，應(yīng)該優(yōu)先考慮使用自旋鎖，自旋鎖的開(kāi)銷比較小，互斥量的開(kāi)銷較大。

3 可重入鎖 (Reentrant Lock)

可重入鎖是一種特殊的互斥鎖，它可以被同一個(gè)線程多次獲取，而不會(huì)產(chǎn)生死鎖。

1. 首先它是互斥鎖：任意時(shí)刻，只有一個(gè)線程鎖。即假設(shè)A線程已經(jīng)獲取了鎖，在A線程釋放這個(gè)鎖之前，B線程是無(wú)法獲取到這個(gè)鎖的，B要獲取這個(gè)鎖就會(huì)進(jìn)入阻塞狀態(tài)。
2. 其次，它可以被同一個(gè)線程多次持有。即，假設(shè)A線程已經(jīng)獲取了這個(gè)鎖，如果A線程在釋放鎖之前又一次請(qǐng)求獲取這個(gè)鎖，那么是能夠獲取成功的。

<pre>Java中的synchronized, ReentrantLock都是可重入鎖。</pre>

4 輕量級(jí)鎖(Lightweight Lock) & 偏向鎖(Biased Lock)

首先互斥是一種會(huì)導(dǎo)致線程掛起，并在較短時(shí)間內(nèi)又需要重新調(diào)度回原線程的，較為消耗資源的操作。

Java6為了減少獲得鎖和釋放鎖所帶來(lái)的性能消耗，引入了“偏向鎖”和“輕量級(jí)鎖”，所以在Java6里鎖一共有四種狀態(tài)，無(wú)鎖狀態(tài)，偏向鎖狀態(tài)，輕量級(jí)鎖狀態(tài)和重量級(jí)鎖狀態(tài)，它會(huì)隨著競(jìng)爭(zhēng)情況逐漸升級(jí)。鎖可以升級(jí)但不能降級(jí)，意味著偏向鎖升級(jí)成輕量級(jí)鎖后不能降級(jí)成偏向鎖。這種鎖升級(jí)卻不能降級(jí)的策略，目的是為了提高獲得鎖和釋放鎖的效率。
<pre>數(shù)據(jù)庫(kù)中針對(duì)不同的鎖層級(jí)(Lock Hierarchy，表/頁(yè)/行等)，
也有類似鎖升級(jí)(Lock Escalations)的理念。</pre>

5 JUC

并發(fā)大師Doug Lea在JUC包中實(shí)現(xiàn)了大量的并發(fā)工具類，并發(fā)思想在源碼中得到了很好的體現(xiàn)。比如Semaphore, CountDownLatch, CyclicBarrier都是特定場(chǎng)景下的經(jīng)典實(shí)現(xiàn)，大家有興趣可以自行研究，最終一嘆：** 鎖 **原來(lái)可以玩出這么多花樣來(lái)。

java-7-concurrent-executors-uml-class-diagram-example.png

鎖的后遺癥

在并發(fā)世界里，鎖扮演了一個(gè)個(gè)亦正亦邪的角色，甚至很多時(shí)候是個(gè)大反派。鎖的后遺癥包括：死鎖，饑餓，活鎖，Lock Convoying(多個(gè)同優(yōu)先級(jí)的線程重復(fù)競(jìng)爭(zhēng)同一把鎖，此時(shí)大量雖然被喚醒而得不到鎖的線程被迫進(jìn)行調(diào)度切換，這種頻繁的調(diào)度切換相當(dāng)影響系統(tǒng)性能)，優(yōu)先級(jí)反轉(zhuǎn)，不公平和低效率等。而這些問(wèn)題都是在實(shí)現(xiàn)鎖的過(guò)程中普遍存在而又不得不面對(duì)的。
這里只拋出問(wèn)題讓讀者了解，具體解決方案不在本文范疇。

活鎖和死鎖的區(qū)別在于，處于活鎖的實(shí)體是在不斷的改變狀態(tài)，所謂之“活”， 而處于死鎖的實(shí)體表現(xiàn)為等待；活鎖有可能自行解開(kāi)，死鎖則不能。

分布式鎖

相對(duì)于單機(jī)應(yīng)用設(shè)定的單機(jī)鎖，為分布式應(yīng)用各節(jié)點(diǎn)對(duì)共享資源的排他式訪問(wèn)而設(shè)定的鎖就是分布式鎖。在分布式場(chǎng)景下，有很多種情況都需要實(shí)現(xiàn)多節(jié)點(diǎn)的最終一致性。比如全局發(fā)號(hào)器，分布式事務(wù)等等。

傳統(tǒng)實(shí)現(xiàn)分布式鎖的方案一般是利用持久化數(shù)據(jù)庫(kù)（如利用InnoDB行鎖，或事務(wù)，或version樂(lè)觀鎖），當(dāng)然大部分時(shí)候可以滿足大部分人的需求。而如今互聯(lián)網(wǎng)應(yīng)用的量級(jí)已經(jīng)幾何級(jí)別的爆發(fā)，利用諸如zookeeper，redis等更高效的分布式組件來(lái)實(shí)現(xiàn)分布式鎖，可以提供高可用的更強(qiáng)壯的鎖特性，并且支持豐富化的使用場(chǎng)景。
開(kāi)源實(shí)現(xiàn)已有不少比如Redis作者基于Redis設(shè)計(jì)的Redlock，Redission等。

小插曲：
鎖存在的地方就有爭(zhēng)議，Redlock也不例外。有一位分布式專家曾經(jīng)發(fā)表過(guò)一片文章<How to do distributed locking>, 質(zhì)疑Redlock的正確性，Redis作者則在<Is Redlock safe?>中給予了回應(yīng)，爭(zhēng)鋒相對(duì)精彩無(wú)比，有興趣的讀者可以自行前往。

前人栽樹(shù)后人乘涼，當(dāng)下各種的鎖實(shí)現(xiàn)已經(jīng)給我們提供了很多優(yōu)雅的設(shè)計(jì)范本，我們具體來(lái)分析下分布式鎖到底應(yīng)該怎么設(shè)計(jì)呢？

分布式鎖的設(shè)計(jì)要點(diǎn)

我們以Redis為例，簡(jiǎn)單思考下這個(gè)鎖的實(shí)現(xiàn)。
似乎加鎖的時(shí)候只要一個(gè)*** SETNX 命令就搞定了，返回1代表加鎖成功，返回0 表示鎖被占用著。然后再用 DEL ***命令解鎖，返回1表示解鎖成功，0表示已經(jīng)被解鎖過(guò)。
接著問(wèn)題就來(lái)了:
SETNX會(huì)存在鎖競(jìng)爭(zhēng)，如果在執(zhí)行過(guò)程中客戶端宕機(jī)，會(huì)引起死鎖問(wèn)題，也就是鎖資源無(wú)法釋放。解決死鎖的問(wèn)題其實(shí)可以可以向Mysql的死鎖檢測(cè)學(xué)習(xí)，設(shè)置一個(gè)失效時(shí)間，通過(guò)key的時(shí)間戳來(lái)判斷是否需要強(qiáng)制解鎖。
但是強(qiáng)制解鎖也存在問(wèn)題，一個(gè)就是時(shí)間差問(wèn)題，不同的機(jī)器的本地時(shí)間可能也存在時(shí)間差，在很小事務(wù)粒度的高并發(fā)場(chǎng)景下還是會(huì)存在問(wèn)題，比如刪除鎖的時(shí)候，會(huì)判斷時(shí)間戳已經(jīng)超過(guò)時(shí)效，有可能刪除其他已經(jīng)獲取鎖的客戶端的鎖。
另外，如果設(shè)置了一個(gè)超時(shí)時(shí)間，若程序執(zhí)行時(shí)間超過(guò)了超時(shí)時(shí)間，那么還沒(méi)執(zhí)行完鎖會(huì)被自動(dòng)釋放，原來(lái)持鎖的客戶端再次解鎖的時(shí)候會(huì)出現(xiàn)問(wèn)題，而且最為嚴(yán)重的還是一致性沒(méi)有得到保障。如何合理的設(shè)置這個(gè)超時(shí)時(shí)間可能是一個(gè)觀測(cè)并不斷調(diào)整的過(guò)程。

那么，總結(jié)下設(shè)計(jì)的幾個(gè)要點(diǎn)：

• 鎖的時(shí)效。避免單點(diǎn)故障造成死鎖，影響其他客戶端獲取鎖。但是也要保證一旦一個(gè)客戶端持鎖，在客戶端可用時(shí)不會(huì)被其他客戶端解鎖。
• 持鎖期間的check。盡量在關(guān)鍵節(jié)點(diǎn)檢查鎖的狀態(tài)，所以要設(shè)計(jì)成可重入鎖。
• 減少獲取鎖的操作，盡量減少redis壓力。所以需要讓客戶端的申請(qǐng)鎖有一個(gè)等待時(shí)間，而不是所有申請(qǐng)鎖的請(qǐng)求線程不斷的循環(huán)申請(qǐng)鎖。
• 加鎖的事務(wù)或者操作盡量粒度小，減少其他客戶端申請(qǐng)鎖的等待時(shí)間，提高處理效率和并發(fā)性。
• 持鎖的客戶端解鎖后，要能通知到其他等待鎖的節(jié)點(diǎn)，否則其他節(jié)點(diǎn)只能一直等待一個(gè)預(yù)計(jì)的時(shí)間再觸發(fā)申請(qǐng)鎖。類似線程的notifyAll,要能同步鎖狀態(tài)給其他客戶端，并且是分布式消息。
• 考慮任何執(zhí)行句柄中可能出現(xiàn)的異常，狀態(tài)的正確流轉(zhuǎn)和處理。比如，不能因?yàn)橐粋€(gè)節(jié)點(diǎn)解鎖失敗，或者鎖查詢失?。╮edis 超時(shí)或者其他運(yùn)行時(shí)異常），影響整個(gè)等待的任務(wù)隊(duì)列，或者任務(wù)池。
• 若Redis服務(wù)器宕機(jī)或者網(wǎng)絡(luò)異常，要有其他備份方案，比如單機(jī)鎖限流+最終數(shù)據(jù)庫(kù)的持久化鎖來(lái)做好最終一致性控制。

如果大家想自己實(shí)現(xiàn)分布式鎖的話，建議先把開(kāi)源的一些實(shí)現(xiàn)先讀一讀，拓展下思路。
還是那句話，如非必要，勿增實(shí)體！

參考文章：
基于Redis實(shí)現(xiàn)分布式鎖，Redisson使用及源碼分析
聊一聊分布式鎖的設(shè)計(jì)