分佈式技術原理與算法解析之分佈式互斥 學習筆記 （3）

• 2021 年 1 月 28 日
• AI
• 深度學習

• 背景：

對於同一個共享資源（什麼是共享資源？），一個程序使用的時候不希望被其他程序打擾，即同一時刻只能有一個程序訪問這種資源，這種共享資源稱為臨界資源（Critical Resource）,這種訪問方式稱之為分佈式互斥（Distributed Mutual Exclusion）。

• 我們需要考慮的方面，（1）公平性（2）實時性（3）信息通信效率/溝通成本（4)健壯性
• 幾種分佈式互斥算法
  • 集中式算法（中央服務器算法）
    • 特點：唯一協調者，代表着集中程序或中央服務器。
    • 優勢：（1）簡單、直觀、信息量少、易於實現（2）程序之間無需通信，效率高。
    • 劣勢：（1）協調者性能瓶頸（2）單點故障問題（性能可靠性高的服務器很有必要）
    • 應用注意事項：中央服務器計算能力強、故障率低/注意時刻備份。
    • 三次信息交互：程序發送請求——>協調者發放授權信息——>程序釋放授權信息。
  • 分佈式算法（使用組播和邏輯時鐘的算法）
  • 特點：程序之間互相平等，請求消息（請求的資源；請求者ID；請求發起的時間）需所有程序同一方可訪問臨界資源。
  • 優勢：簡單粗暴，易於實現，公平訪問。
  • 劣勢：若有n個程序需要訪問臨界資源，則會產生2n(n-1)次信息交互，特別不適合在大型系統中使用分佈式算法，消息數量指數級增加，溝通成本高昂。
  • 應用注意事項：（1）實際可用性極低
  • 訪問請求過多容易產生「信令風暴」。
  • 某一程序發生故障，無法發送同意信息，導致系統停滯。

（2）適合節點數目少且變動不頻繁，由於每個程序都需要通信交互，適合P2P結構的系統。

（3）改進：程序故障直接忽略，但故障檢測帶來複雜性

• 典型場景：Hadoop中的分佈式文件系統HDFS文件修改。
  

• 令牌環算法

  • 特點：令牌在由程序構成的環結構中傳遞（不管你需不需要，都得問你一句要不要），令牌在手，天下我有。
    

• 優點：（1）更高的通信效率，不用徵求其他程序意見。（2）公平性很好。
  （3）健壯性好，令牌會跳過故障程序。

• 劣勢：（1）無效通信（不管你需不需要，都得問你一句要不要）（2）實時性差，等待時間長。

• 應用注意事項：（1）適用於系統規模小且使用臨界資源使用頻率高且使用時間短的系統。（2）系統支持廣播/組播通信模式，算法會更加高效。

• 典型場景：移動自組織網絡系統（無人機之間的通信）

• 大規模系統中的分佈式互斥算法（兩層結構的分佈式令牌環算法）

  • 特點：把整個廣域網（多個局域網組成）系統中的節點組織成兩層結構，在全局環與局域環存在兩個令牌， 分別作用且局域環與局域環之間通過各自的協調進程進行通信。