分佈式互斥#
內容來自極客時間專欄: 《分佈式技術原理與算法解析》
互斥指的是對於一個條件資源，在同一時間只能被一個單位佔用，在分佈式系統裡，這種排他性的資源訪問方式，叫作分佈式互斥（Distributed Mutual Exclusion），而這種被互斥訪問的共享資源就叫作臨界資源（Critical Resource）
分佈式互斥的幾種實現方式:
集中式算法#
聯想到
Yarn的資源調度機制
系統引入一個協調者的角色，每個程序在請求資源的時候先向協調者發送一個請求，然後協調者判斷資源是否空閒，空閒的話就直接分配給這個程序，如果被佔用的話，就給這個請求排號，相當於一個請求隊列排隊獲取資源。但同時也會存在以下兩個問題:
- 單點問題，協調者故障，會導致所有的程序均無法訪問臨界資源，導致整個系統不可用，因此需要額外的機制保障協調者的正常運行狀態 (其實感覺 zookeeper 也是類似這種)
- 協調者通常會成為系統的性能瓶頸，協調者處理的消息數量會隨著需要訪問臨界資源的程序數量線性增加
集中式算法示意圖如下所示:
分佈式算法#
HDFS 中文件修改機制採用了這種算法
不同於集中式算法，分佈式算法實現的原理是當某個程序請求資源時，先向系統內所有其他程序發送請求，其他程序如果沒有佔用這個資源那麼返回同意的結果，在接收到所有其他程序返回的同意消息後，才可以訪問臨界資源。
這個算法可用性很低，主要包括兩方面的原因：
- 隨著系統內程序數增多，消息數量會隨著需要訪問臨界資源的程序數量呈指數級增加 (
2n * (n-1))，容易產生“信令風暴”，也就是程序收到的請求完全超過了自己的處理能力，而導致自己正常的業務無法開展 - 我們知道在計算機網絡中消息的可靠性保證也是很難的，會出現比如消息丟失，消息延遲到達等情況，在分佈式算法中也同樣， 比如某個程序發生故障，導致無法發送同意請求資源的響應消息或者延遲響應，那麼其他程序往往就會因此而陷入等待使系統阻塞，導致系統不可用
分佈式算法根據 “先到先得” 以及 “投票全票通過” 的機制，讓每個程序按時間順序公平地訪問資源，簡單粗暴、易於實現，適用於臨界資源使用頻度較低，且系統規模較小的場景
令牌環算法#
算法示意圖如下：
如同所示，程序排成環形結構，令牌循環傳遞，收到令牌的程序有權訪問臨界資源，訪問完成後將令牌傳送到下一個程序；若該程序不需要訪問臨界資源，則直接把令牌傳送給下一個程序；
ps: 我一開始想到了限流機制的令牌桶算法，但其實不一樣
總結 & 思考#
思考：#
以下思考內容可能存在問題，歡迎指正
集中式算法#
改進思路：可參照 redis 集群通信模式，通過 hash key 將大量的請求分散到不同的 master, 以處理大量請求，每個 master 由小集群主從節點來保障單點故障
分佈式算法#
設置超時，如果某個節點發生故障遲遲沒有響應達到超時時間限制，將其從系統中剔除出去，或者直接忽略
令牌環算法#
改進思路：可根據參與者使用頻率列出權重，結合平滑加權輪詢算法選出下一個參與者
同時需要注意若環中某個節點發生故障需要及時剔除出去，保證令牌在正常節點之間傳遞
傳統單機上的互斥方法，為什麼不能用於分佈式環境呢#
單機上互斥可以用信號量、鎖機制、線程同步等方法，可以在 jvm 層級或單機硬體層面做到互斥。分佈式環境，彼此都是運行在不同的伺服器彼此不可感知，需要用額外的手段保證各節點訪問互斥