分布式技術(shù)中不可或缺的分布式互斥方案

作者：斯巴達(dá)人 2024-01-10 08:02:03

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

什么是分布式互斥？

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

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

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

霸道總裁：集中式算法

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

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

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

一個(gè)程序完成一次臨界資源訪問，需要如下幾個(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è)程序完成一次臨界資源訪問，需要進(jìn)行3次消息交互。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

當(dāng)然可以通過檢測(cè)其他程序是否可用的方式可以解決阻塞停滯問題，但是無疑增加了系統(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ī)的同意消息后，開始修改該文件；計(jì)算機(jī)1修改完成后，向計(jì)算機(jī)2、3發(fā)送文件修改完成的消息，并發(fā)送修改后的文件數(shù)據(jù)；計(jì)算機(jī)2和3收到計(jì)算機(jī)1的新文件數(shù)據(jù)后，更新本地的備份文件。

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

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

圖片