分布式互斥算法解析

文章目錄

• ​​引言​​

• ​​集中式算法​​
• ​​分布式算法​​

• ​​基于請求的算法​​
• ​​基于令牌的算法​​

• ​​總結​​

引言

分布式系統中可能會出現多個節點通路一個資源或者同時執行一個給定的函數,這些資源或者函數一般成為臨界資源(Critical Resource),有時這些 臨界資源需要在同一時刻隻有一個程序執行,這就是分布式互斥.保證任何給定時刻隻允許一個程序或者給定的程序去執行臨界區的算法稱為互斥算法.

傳統的單機達到互斥的方法有互斥鎖,條件變量,讀寫鎖,共享記憶體,信号量,記憶體序,記憶體屏障等,這些方法在分布式系統中通通不可用,在分布式系統中消息傳遞是實作互斥的唯一的方法.

分布式互斥算法可以分為集中式算法(Centralized Algorithm)和分布式算法(Distributed Algorithm),其中分布式算法又可以分為基于令牌的算法(Token Based Algorithm)和基于請求的算法(Permission Based Algorithm).下來我們就來看看吧!

集中式算法

在所有的節點中引入一個協調者,這個協調者負責所有節點申請資源請求的排程.每個節點想要申請資源需要向協調者發送請求,如果目前節點沒有人使用的話,協調者就授權這個節點進行通路.對于協調者來說維護一個隊列,用先來後到的順序為沒有申請到資源的節點排序,當得到資源的節點執行完畢以後傳回一個消息代表使用完畢,這個時候協調者再次配置設定.

集中式互斥算法在一次申請資源的互動中需要三次消息互動:

1. 節點向協調者請求資源.
2. 協調者給予權限.
3. 節點完成以後傳回釋放消息.

這也是集中式算法的優點,即通信成本較低,且直覺,簡單,所有的節點隻需要于協調者通信.當然這也正是它的缺點,因為所有的壓力全部落在了協調者身上,這裡有兩個問題:

1. 可用性,如果協調者當機,整個服務直接不可用,假如重新開機以後資訊丢失,還有可能破壞一緻性假設.可以搭配哨兵和主從複制模型,這樣可以保證一定的可用性,但還是會出現一定時間内服務下線.
2. 有效率瓶頸,所有的壓力全部落在了協調者上,一定會有瓶頸,最好選一個不錯的硬體來做協調者.

分布式算法

在分布式算法中又分為基于令牌的算法和基于請求的算法,它們之間也是各有優缺點.

基于請求的算法

這裡介紹Ricart-Agrawala算法,其他基于請求的算法大都在這個基礎上修改.如果把一次選舉的leader看做是資源的話,選舉的過程其實也是一個分布式互斥算法的實作.這樣看來這種基于請求的算法其實比較常見,也就是所有的節點之間互相連接配接,形成網狀的網絡拓撲結構,在每次使用資源的時候向其他節點發起資源的申請,如果擷取全票同意的話則擷取資源使用權,在使用的過程中也可能有其他節點同樣請求資源,發送請求的雙方都可以得到對方使用資源的消息,這個時候對比出時間戳最小的(基于邏輯時鐘而不是實體時間戳,見另一篇文章 ​​不可靠的時鐘​​),即最先發起請求的擷取資源通路權,得到資源通路權的節點也要維護一個隊列,存儲其他申請請求,在完成資源通路以後向其他申請資源的節點發送同意使用資源的消息,一般不申請資源的節點在收到其他申請資源的請求時直接同意.

從以上流程不難看出,資訊的互動過程是這樣的,首先我們假設叢集有N個節點:

1. 向其他N-1個節點發送請求資源消息.需要N-1次互動.
2. 需要接收N-1個節點的回複消息,需要N-1次互動.

這樣每個節點每次申請資源需要2(N-1)此資訊互動.而且當叢集内每個節點都進行資源申請的時候會有2N(N-1)次互動,也就是說随着叢集的擴充,通信成本是平方上漲的.它還有以下問題:

1. 當系統内需要通路臨界資源的程式增多時,容易産生“信令風暴”,也就是程式收到的請求完全超過了自己的處理能力,而導緻自己正常的業務無法開展.
2. 因為采用的是全部節點同意,為了防止隻有兩個節點請求,它們之間隻有一個可以得到N-1個投票剩下一個得到N-2個投票,這意味着一個節點故障的話整個系統就處于停滞狀态.

這種基于請求的分布式互斥算法适合與節點數目少,變動不頻繁的系統,且适用與P2P結構,因為每個程式之間都需要互互相動.HDFS就是一個典型的運用場景.

基于令牌的算法

如下圖所示,所有程式構成一個邏輯上的環結構,令牌按照順時針(或逆時針)方向在程式之間傳遞,收到令牌的程式有權通路臨界資源,通路完成後将令牌傳送到下一個程式.若該程式不需要通路臨界資源,則直接把令牌傳送給下一個程式.

這樣每一個節點在适用資源之前就不需要向每一個節點請求了,隻需要傳遞令牌即可,得到令牌的節點擷取資源,這樣在一個周期内全部節點都有機會适用資源,不需要的話直接轉發就可以了.當然這也帶來一些無效的通信成本,且降低了實時性.因為就算隻有一個節點請求資源,全部的節點都需要進行資訊傳遞,而且考慮到節點當機,每個節點也不能僅存儲自己的下一位節點.令牌環算法非常适合通信模式為令牌環方式的分布式系統.

總結

1. ​

   ​集中式算法​

   ​: 優點就是簡單,易于實作,隻有搭配上哨兵和主從複制可用性才說的過去,但是當機仍會服務下線.且有單機的效率瓶頸.’
2. ​

   ​分布式算法-基于請求​

   ​: 可用性強,一般也不使用全部同意,而是配置紀元搭配選舉,可容忍一半以下節點當機,比較類似與無主節點的結構.缺點就是通信成本過高.适用于臨界資源使用頻率較低的時候.(redis中故障轉移選舉執行的節點不就是這樣實作的)
3. ​

   ​分布式算法-基于令牌​

   ​: 通信效率高且可用性不差.使用與請求資源頻繁且使用時間短的情況,缺點就是容易帶來大量的無用通信.

其實分布式互斥算法應用很廣泛,比如選舉的過程(一次隻需要一個leader),Redlock(Redis官方欽點的分布式鎖實作),HDFS(Hadoop的分布式檔案系統),它對于我們學習分布式至關重要.

參考:

​​​P2P結構​​

​​邏輯時鐘​​