什么是分布式互斥？

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

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

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

霸道總裁：集中式算法

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

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

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

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

集中式算法的優點：

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

集中式算法的缺點：

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

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

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

民主協商：分布式算法

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

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

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

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

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

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

分布式算法的優點：

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

分布式算法的缺點：

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

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

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

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

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

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

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

輪值CEO：令牌環算法

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

圖片

令牌環算法優點：

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

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

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

令牌環算法缺點：

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

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

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