什么是分布式互斥？

減庫(kù)存是一個(gè)很常見(jiàn)的例子，假如兩個(gè)線程同時(shí)查到庫(kù)存還有10件，同時(shí)賣出10件后，去庫(kù)存中減10件，這樣就會(huì)造成庫(kù)存還剩下-10件。這顯然是不合理的，這就需要當(dāng)一個(gè)線程操作的時(shí)候，另一個(gè)線程不能操作，這就是排他性資源訪問(wèn)。

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

我們一起來(lái)看下分布式技術(shù)中是如何對(duì)臨界資源進(jìn)行互斥訪問(wèn)的。

霸道總裁：集中式算法

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

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

這個(gè)互斥算法，就是我們所說(shuō)的集中式算法，也可以叫做中央服務(wù)器算法。之所以這么稱呼，是因?yàn)閰f(xié)調(diào)者代表著集中程序或中央服務(wù)器。

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

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

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

集中式算法的缺點(diǎn)：

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

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

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

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

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

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

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

這個(gè)算法中，一個(gè)程序完成一次臨界資源的訪問(wèn)，需要進(jìn)行如下的信息交互：

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

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

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

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

分布式算法的缺點(diǎn)：

當(dāng)系統(tǒng)內(nèi)需要訪問(wèn)臨界資源的程序增多時(shí)，容易產(chǎn)生“信令風(fēng)暴”，也就是程序收到的請(qǐng)求完全超過(guò)了自己的處理能力，而導(dǎo)致自己正常的業(yè)務(wù)無(wú)法開(kāi)展。

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

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

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

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

處于同一個(gè)局域網(wǎng)內(nèi)的計(jì)算機(jī)1、2、3中都有同一份文件的備份信息，且它們可以相互通信。這個(gè)共享文件，就是臨界資源。當(dāng)計(jì)算機(jī)1想要修改共享的文件時(shí)，需要進(jìn)行如下操作：

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

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

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

圖片

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

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

公平性更好，在一個(gè)周期內(nèi)，每個(gè)程序都能訪問(wèn)到臨街資源。

不存在單點(diǎn)問(wèn)題，如果某個(gè)訪問(wèn)者故障了，令牌可以直接往下一個(gè)訪問(wèn)者傳遞，故障的訪問(wèn)者會(huì)自動(dòng)出局。

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

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

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

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