分佈式系統：領導者選舉

Question

我目前正在分佈式系統上工作，我們必須實現某種Leader Election。 問題是，我們想避免所有的計算機必須相互認識 - 但只有領導者。有沒有一種快速的方式，我們可以使用廣播來實現我們想要的？

抑或，我們只需要知道至少有一個，執行一個好的領導人選舉？

假設所有的計算機都在同一個子網上。

感謝您的幫助。

Answer 1

作爲有趣的「分配機制」的解決方案我有看到上次我會建議阿帕奇zookeeper項目。這是開源的解決方案，所以至少你應該能夠從那裏得到幾個想法。此外，它正在密集開發，因此您可以將其作爲解決方案的一部分重用。

ZooKeeper的是維持配置 信息，命名，提供分佈式同步，並提供 服務組集中式服務。所有這些類型的服務都以分佈式應用程序的形式在 中以某種形式使用。每次他們執行 時，都會進行大量工作來解決錯誤和不可避免的競爭條件。由於 實施這類服務的難度，應用最初通常 吝嗇對他們來說，這使他們在變化的存在和 難以管理脆。即使正確完成，當部署應用程序時，這些服務的不同實施導致管理的複雜性。

Answer 2

我會推薦JGroups來解決這個問題 - 假設你正在JVM上構建一個系統。

使用的LockService，以確保只有1集羣中的節點中的佼佼者。 JGroups可以設置爲使用同級鎖或中央鎖 - 兩者都應該適用於您的案例。

爲Java一見http://withmeta.blogspot.com/2014/01/leader-election-problem-in-elastic.html了Clojure的實現，或http://javabender.blogspot.com.au/2012/01/jgroups-lockservice-example.html。

Answer 3

問題是我們想避免所有的計算機必須相互認識 - 但只有領導者。

領導者選舉是從一組潛在的領導者候選人中挑選出單個領導者的問題。看它有兩個所需的屬性：活躍和安全。在這裏，活躍將意味着「大部分的時候，有一個領導者」，而安全將意味着「有零個或一個領袖」。讓我們考慮一下如何在您的示例中使用廣播來解決這個安全屬性。

讓我們舉一個簡單的（碎）算法，假設每個節點都有一個唯一的ID。每個節點廣播其ID並監聽。當收到比自己更高的ID時，它會停止參與。如果它收到的ID比自己低，它會再次發送自己的廣播。假設一個同步網絡，每個人收到的最後一個ID就是領導者的ID。現在，介紹一個網絡分區。該協議將愉快地繼續分區的兩邊，兩名領導人將被選舉。

對於這個破損的協議來說也是如此，但所有可能的協議也是如此。如果你不知道（至少）存在多少個節點，你如何區分不能通信的節點和不存在的節點？所以有一個第一個安全結果：你需要知道有多少個節點存在，或者你不能確保只有一個領導。現在，讓我們放鬆我們的安全約束爲一個概率：「可以有零個或更多的領導者，但大多數時候有一個」。這使問題變得易於處理，而一種廣泛使用的解決方案就是八卦（流行病協議）。例如，請參閱A Gossip-Style Failure Detection Service，其中討論了該確切問題的一個變體。本文主要關注概率正確的失敗檢測和枚舉，但如果你能做到這一點，你也可以做概率正確的領導選舉。

據我所知，你不能在普通網絡中進行安全的非概率性領導選舉，至少沒有列舉參與者。

Answer 4

一個實用的解決方案是使用DB作爲「會議」點。

如果您已經在使用SQL DB，那麼這個解決方案非常有用，它只需要一個新表。如果您使用數據庫集羣，則可以利用其高可用性。

這是我實現使用表：

CREATE TABLE Lease (
    ResourceId varchar(64), 
    Expiration datetime, 
    OwnerId varchar(64), 
    PRIMARY KEY(ResourceId) 
); 

的想法是讓每個共享資源的行。領導者將爭奪同一排。

我在簡化C＃實現看起來喜歡這樣的：

class SqlLease { 
    private ISqlLeaseDal _dal; 
    private string _resourceId; 
    private string _myId; 

    public SqlLease(ISqlLeaseDal dal, string resourceId) { 
    _dal = dal; 
    _resourceId = resourceId; 
    _myId = Guid.NewGuid().ToString(); 
    } 

    class LeaseRow { 
     public string ResourceId {get; set;} 
     public string OwnerId {get; set;} 
     public Datetime Expiration {get; set;} 
     public byte[] RowVersion {get; set;} 
    } 

    public bool TryAcquire(Datetime expiration) { 
    expiration = expiration.ToUniversalTime(); 
    if (expiration < DateTime.UtcNow) return false; 
    try { 
     var row = _dal.FindRow(_resourceId); 
     if (row != null) { 
     if (row.Expiration >= DateTime.UtcNow && row.OwnerId != _myId) { 
      return false; 
     } 
     row.OwnerId = _myId; 
     row.Expiration = expiration; 
     _dal.Update(row); 
     return true; 
     } 
     _dal.Insert(new LeaseRow { 
     ResourceId = _resourceId, 
     OwnerId = _myId, 
     Expiration = expiration, 
     }); 
     return true; 
    } catch (SqlException e) { 
     if (e.Number == 2601 || e.Number == 2627) return false; 
     throw e; 
    } catch (DBConcurrencyException) { 
     return false; 
    } 
    } 
} 

的ISqlLeaseDal類封裝SQL連接和表低級別的訪問。

使用合理的期限。請記住，如果當前領導失敗，資源將被鎖定，直到失效結束。