分散式技術原理與演算法解析之分散式互斥 學習筆記 （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）系統支援廣播/組播通訊模式，演算法會更加高效。

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

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

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