192
技術社區[雲棲]
【轉載——兩個很基礎的選舉算法】分布式係統進程的選舉
在分布式係統中，為了協調一組進程的動作，我們常常需要一個進程扮演協調者、初始者或管理者的角色。這個進程可以是進程組的任何一個，但關鍵的是進程組必須選舉出唯一一個而且必須達到共識。
如果所有的進程都完全一樣，它們之間沒有任何可區別的屬性，那麼也就沒有辦法選舉出一個特別的進程。因此，我們假設進程有一個全局唯一的編號，這個編號可以是網絡地址或其他方法產生的編號。不失一般性，我們可以假設選舉算法總是選舉編號最大的進程作為協調進程。
我們另外還假設，每個進程都知道組內其他進程的編號。如果最大編號的進程總是在運行中並且總是能夠擔當協調者的角色，那麼選舉就變成了指派。選舉算法需要考慮的是，當最大編號的進程因為這樣和那樣的原因不能成為協調者時，選舉過程才會發生。我們稱它為一個進程召集選舉。
如果一個進程啟動了選舉算法的一次執行，且每次隻能啟動一次召集選舉的過程，則原則上有 n 個進程的分布式係統可以並發地召集 n 次選舉。算法的一個基本要求是對當選進程的選擇必須是唯一的，即使有多個並發的召集過程在執行，最後的結果必須保證所有召集選舉和參與選舉的進程對當選的進程達成共識。
霸道算法Garcia-Monila 在 1982 年的一篇論文中發明了所謂的霸道選舉算法（Bully Algorithm）。當一個進程 P 發現協調者進程不再響應時，這個進程就召集選舉。由於進程的獨立性，在同一個時刻，係統中可能有多個召集選舉的過程。假設 P 是召集選舉的進程，每個召集選舉的過程如下：
- P 向所有比自己編號大的進程發送一條 ELECTION（選舉）消息。
- 如果 P 得不到任何回複，則 P 贏得選舉，P 向所有進程發送 COORDINATOR（協調者）消息，宣布自己的勝利。
- 如果 P 得到任何一個回複，回複一定來自於比自己編號大的進程。P 的召集選舉的工作結束，因為 P 此時已經不可能贏得選舉。
其他進程或正在召集選舉，或可能接收到比自己編號小的進程的 ELECTION 消息。當它收到一個 ELECTION 後，它回複一個 OK 消息給發送消息的進程；如果這時它還不是召集選舉的進程，它也將開始一個召集選舉的過程，即執行 1 到 3 的操作。
擁有最大編號的進程不召集選舉，它直接發送 COORDINATOR 消息宣布勝利，霸道算法的名字由此得來。
關於選舉的另一個著名算法是基於進程環的機製設計的。與一般的環算法不同的是，環選舉算法並不使用令牌。在這個算法中，我們假設所有進程能夠在物理上或邏輯上組成一個環結構，每個進程都保留一個按進程編號邏輯排序的一個表，因此知道自己的所有後繼進程。
算法的過程非常簡單。當一個進程 P 注意到協調者進程不再工作時，它將啟動一個召集選舉的過程：
- 進程 P 構造一個包含自己進程編號的 ELECTION 給後繼進程，如果直接後繼進程沒有響應，進程 P 就將消息發送給環上的下一個進程，直到找到一個正常運行的進程。
- 接收到 ELECTION 消息的進程將自己的編號增加到 ELECTION 消息中，然後按照同樣的方式將消息發送給後繼進程。這樣，消息在環上的傳遞將構造一個包含所有正常運行的進程的編號表。
- 當 ELECTION 消息最後回到召集選舉的進程時，消息中最大編號的進程即成為選舉的勝利者。召集選舉的進程將消息類型改為 COORDINATOR，然後將消息沿著環重新發送一次，將選舉結果通知所有的進程。
- 當 COORDINATOR 消息重新回到召集選舉的進程時，算法終止。
同樣，在環選舉算法中，也可能同時存在多個召集選舉的過程。當在這個時刻環結構不變時，最後的結果也是一致的，隻是消息數量多一些，並無大礙。
關於選舉算法的討論霸道選舉算法和環選舉算法都依賴一係列苛刻的假設：
- 假設了可靠的通道通信，更進一步的假設是係統中任何兩個進程之間都可以通信。
- 每個進程都知道其他進程的編號，也就是說算法依賴一個全局的數據。
- 在多個並發召集選舉的過程中，進程組的正常進程數量保持穩定，而且在環選舉算法中，環結構也必須穩定。
- 假設進程能夠明確地判斷出一個正常運行的進程和一個已經崩潰的進程。
有很多放寬假設條件下如何改進算法的討論，但就算法的應用來說，召集選舉的過程不應該是很頻繁的，參與選舉的進程數量和結構應該是相對穩定的。我們看不到頻繁故障下的頻繁選舉的應用價值。因此，雖然算法的適用條件比較苛刻，但它們基本能夠滿足應用的需求。
最後更新：2017-04-02 15:32:47