什么是分布式互斥？

減庫存是一個很常見的例子，假如兩個線程同時查到庫存還有10件，同時賣出10件后，去庫存中減10件，這樣就會造成庫存還剩下-10件。這顯然是不合理的，這就需要當一個線程操作的時候，另一個線程不能操作，這就是排他性資源訪問。

在分布式系統(tǒng)里，這種排他性的資源訪問方式，叫作分布式互斥，而這種被互斥訪問的共享資源就叫作臨界資源。

我們一起來看下分布式技術中是如何對臨界資源進行互斥訪問的。

霸道總裁：集中式算法

集中式算法就是建立一個協(xié)調者，任何三方想要訪問臨界資源都要通過協(xié)調者，協(xié)調者認為你可以訪問，你才可以訪問，否則就不能訪問。

具體操作就是訪問者先訪問協(xié)調者，協(xié)調者發(fā)現(xiàn)現(xiàn)在沒有其他訪問者占用資源，就給當前訪問者發(fā)送放行信號，否則就要按照協(xié)調者的規(guī)則進行下一步動作，包括排隊，自旋等。

這個互斥算法，就是我們所說的集中式算法，也可以叫做中央服務器算法。之所以這么稱呼，是因為協(xié)調者代表著集中程序或中央服務器。

一個程序完成一次臨界資源訪問，需要如下幾個流程和消息交互： 向協(xié)調者發(fā)送請求授權信息，1次消息交互； 協(xié)調者向程序發(fā)放授權信息，1次消息交互； 程序使用完臨界資源后，向協(xié)調者發(fā)送釋放授權，1次消息交互。 因此，每個程序完成一次臨界資源訪問，需要進行3次消息交互。

集中式算法的優(yōu)點：

直觀、簡單、信息交互量少、易于實現(xiàn)，并且所有程序只需和協(xié)調者通信，程序之間無需通信。

集中式算法的缺點：

一方面，協(xié)調者會成為系統(tǒng)的性能瓶頸。 想象一下，如果有100個程序要訪問臨界資源，那么協(xié)調者要處理100*3=300條消息。也就是說，協(xié)調者處理的消息數(shù)量會隨著需要訪問臨界資源的程序數(shù)量線性增加。

另一方面，容易引發(fā)單點故障問題。協(xié)調者故障，會導致所有的程序均無法訪問臨界資源，導致整個系統(tǒng)不可用，因此，在使用集中式算法的時候，一定要選擇性能好、可靠性高的服務器來運行協(xié)調者。

目前市場上集中式算法的實現(xiàn)主要通過redis zookeeper 數(shù)據(jù)庫實現(xiàn)，這些組件對于在應對高可用，高性能方面都有自己的方案。開發(fā)者需要根據(jù)不同的業(yè)務選擇使用哪種方式。

民主協(xié)商：分布式算法

集中式算法是訪問者訪問資源前征求協(xié)調者的同意，那么分布式算法就是訪問者在訪問資源前征求其他訪問者的同意。

具體操作為當一個程序要訪問臨界資源時，先向系統(tǒng)中的其他程序發(fā)送一條請求消息，在接收到所有程序返回的同意消息后，才可以訪問臨界資源。其中，請求消息需要包含所請求的資源、請求者的ID，以及發(fā)起請求的時間。

這就是民主協(xié)商法。在分布式領域中，我們稱之為分布式算法，或者使用組播和邏輯時鐘的算法。

這個算法中，一個程序完成一次臨界資源的訪問，需要進行如下的信息交互：

1. 向其他n-1個程序發(fā)送訪問臨界資源的請求，總共需要n-1次消息交互；
2. 需要接收到其他n-1個程序回復的同意消息，方可訪問資源，總共需要n-1次消息交互。

可以看出，一個程序要成功訪問臨界資源，至少需要2*(n-1)次消息交互。假設，現(xiàn)在系統(tǒng)中的n個程序都要訪問臨界資源，則會同時產生2n(n-1)條消息。在大型系統(tǒng)中使用分布式算法，消息數(shù)量會隨著需要訪問臨界資源的程序數(shù)量呈指數(shù)級增加，容易導致高昂的“溝通成本”。

分布式算法的優(yōu)點：

分布式算法根據(jù)“先到先得”以及“投票全票通過”的機制，讓每個程序按時間順序公平地訪問資源，簡單粗暴、易于實現(xiàn)。

分布式算法的缺點：

當系統(tǒng)內需要訪問臨界資源的程序增多時，容易產生“信令風暴”，也就是程序收到的請求完全超過了自己的處理能力，而導致自己正常的業(yè)務無法開展。

一旦某一程序發(fā)生故障，無法發(fā)送同意消息，那么其他程序均處在等待回復的狀態(tài)中，使得整個系統(tǒng)處于停滯狀態(tài)，導致整個系統(tǒng)不可用。所以，相對于集中式算法的協(xié)調者故障，分布式算法的可用性更低。

當然可以通過檢測其他程序是否可用的方式可以解決阻塞停滯問題，但是無疑增加了系統(tǒng)的復雜性。

因此，分布式算法適合節(jié)點數(shù)目少且變動不頻繁的系統(tǒng)，且由于每個程序均需通信交互，因此適合P2P結構的系統(tǒng)。比如，運行在局域網中的分布式文件系統(tǒng)，具有P2P結構的系統(tǒng)等。

Hadoop是我們非常熟悉的分布式系統(tǒng)，其中的分布式文件系統(tǒng)HDFS的文件修改就是一個典型的應用分布式算法的場景。

處于同一個局域網內的計算機1、2、3中都有同一份文件的備份信息，且它們可以相互通信。這個共享文件，就是臨界資源。當計算機1想要修改共享的文件時，需要進行如下操作：

計算機1向計算機2、3發(fā)送文件修改請求； 計算機2、3發(fā)現(xiàn)自己不需要使用資源，因此同意計算機1的請求； 計算機1收到其他所有計算機的同意消息后，開始修改該文件； 計算機1修改完成后，向計算機2、3發(fā)送文件修改完成的消息，并發(fā)送修改后的文件數(shù)據(jù)； 計算機2和3收到計算機1的新文件數(shù)據(jù)后，更新本地的備份文件。

輪值CEO：令牌環(huán)算法

程序訪問臨界資源問題也可按照輪值CEO的思路實現(xiàn)。 如下圖所示，所有程序構成一個環(huán)結構，令牌按照順時針（或逆時針）方向在程序之間傳遞，收到令牌的程序有權訪問臨界資源，訪問完成后將令牌傳送到下一個程序；若該程序不需要訪問臨界資源，則直接把令牌傳送給下一個程序。 在分布式領域，這個算法叫作令牌環(huán)算法，也可以叫作基于環(huán)的算法。為了便于理解與記憶，你完全可以把這個方法形象地理解為輪值CEO法。

圖片

令牌環(huán)算法優(yōu)點：

相對于分布式算法，令牌環(huán)算法不需要再征求其他所有訪問者的同意，只需要將令牌傳遞給下一個訪問者即可，這樣通信壓力相對變小，通信效率更高。

公平性更好，在一個周期內，每個程序都能訪問到臨街資源。

不存在單點問題，如果某個訪問者故障了，令牌可以直接往下一個訪問者傳遞，故障的訪問者會自動出局。

令牌環(huán)算法缺點：

不管環(huán)中的程序是否想要訪問資源，都需要接收并傳遞令牌，所以也會帶來一些無效通信。假設系統(tǒng)中有100個程序，那么程序1訪問完資源后，即使其它99個程序不需要訪問，也必須要等令牌在其他99個程序傳遞完后，才能重新訪問資源，這就降低了系統(tǒng)的實時性。

令牌環(huán)算法的公平性高，在改進單點故障后，穩(wěn)定性也很高，適用于系統(tǒng)規(guī)模較小，并且系統(tǒng)中每個程序使用臨界資源的頻率高且使用時間比較短的場景。

本篇介紹了分布式技術中常見的分布式互斥算法，下一篇我們探討下具體的分布式互斥實現(xiàn)方案-分布式鎖具體實現(xiàn)。