7

我目前正在研究一个分布式系统，我们必须在其中实施某种领导人选举。问题是我们希望避免所有计算机都必须相互了解——但只有领导者。有没有一种快速的方法可以让我们使用例如广播来实现我们想要的？

还是我们只需要知道至少一个，就可以进行一次好的领导人选举？

假设所有计算机都在同一个子网上。

谢谢你的帮助。

4

5 回答 5

13

问题是我们希望避免所有计算机都必须相互了解——但只有领导者。

领导者选举是从一组潜在领导者候选人中挑选一个领导者的问题。将其视为具有两个必需的属性：liveness和safety。在这里，活跃性意味着“大多数时候，有一个领导者”，而安全性意味着“有零个或一个领导者”。让我们考虑如何在您的示例中使用广播解决此安全属性。

让我们选择一个简单的（损坏的）算法，假设每个节点都有一个唯一的 ID。每个节点广播其 ID 并进行侦听。当收到比自己更高的 ID 时，它会停止参与。如果它接收到比它自己的 ID 低的 ID，它会再次发送它自己的广播。假设一个同步网络，每个人收到的最后一个 ID 是领导者的 ID。现在，介绍一个网络分区。该协议将愉快地在分区的任何一侧继续，并且将选出两个领导者。

这个损坏的协议确实如此，但所有可能的协议也是如此。如果您不知道（至少）存在多少个节点，您如何区分无法通信的节点和不存在的节点？所以有第一个安全结果：您需要知道存在多少个节点，否则您无法确保只有一个领导者。

现在，让我们将安全约束放宽为概率约束：“可以有零个或多个领导者，但大多数时候只有一个”。这使得问题易于处理，一个广泛使用的解决方案是八卦（流行病协议）。例如，请参阅A Gossip-Style Failure Detection Service，其中讨论了这个确切问题的一个变体。该论文主要关注概率正确的故障检测和枚举，但如果你能做到这一点，你也可以进行概率正确的领导者选举。

据我所知，如果不至少枚举参与者，就无法在一般网络中进行安全的非概率领导者选举。

于 2014-04-13T23:59:59.167 回答
1

作为我上次看到的有趣的“分布式机制”解决方案之一，我推荐 Apache zookeeper项目。这是开源解决方案，因此至少您应该能够从那里获得一些想法。此外，它正在密集开发，因此您可能可以将其作为解决方案的一部分重用。

ZooKeeper 是一个集中式服务，用于维护配置信息、命名、提供分布式同步和提供组服务。所有这些类型的服务都以某种形式被分布式应用程序使用。每次实施它们时，都会进行大量工作来修复不可避免的错误和竞争条件。由于实现这些服务的难度，应用程序最初通常会忽略它们，这使得它们在发生变化时变得脆弱并且难以管理。即使正确完成，这些服务的不同实现也会在部署应用程序时导致管理复杂性。

于 2013-04-17T09:31:13.883 回答
1

我会推荐 JGroups 来解决这个问题——假设你正在 JVM 之上构建一个系统。

http://www.jgroups.org/

使用 LockService 确保集群中只有 1 个节点是领导者。JGroups 可以设置为使用 Peer Lock 或 Central Lock - 两者都应该适用于您的情况。

有关Clojure 实现，请参见http://withmeta.blogspot.com/2014/01/leader-election-problem-in-elastic.html ，或http://javabender.blogspot.com.au/2012/01/jgroups-用于 Java 的lockservice-example.html。

于 2014-01-03T03:44:51.017 回答
1

一个实用的解决方案是使用数据库作为“会面”点。

如果您已经在使用 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 连接和对表的低级访问。

使用合理的截止日期。请记住，如果当前领导者失败，资源将被锁定直到到期结束。

于 2017-02-22T11:28:50.980 回答
0

@Marc 已经很好地描述了它。我想在上面补充几点。

如果所有参与系统必须不知道彼此，则广播 ID（或说时间戳）不会显示其状态，除非它被选为领导者。一旦被选为领导者，它现在可以广播机器的状态以供集群中的所有其他节点连接。

如果参与的系统根本不能透露它们的存在，那么必须有一个系统来进行通信，例如一个 DB（如 Igor 所提到的）、一个基于 TCP 的系统或一个安装位置（zookeeper 选择的方式），所有机器状态都是存储但最少（或第一个具有读取权限）并且领导者不断将其状态更新到该系统。如果领导者宕机，则系统通过使其可供其他节点读取来选择下一个节点作为领导者，从而清理最后一个领导者条目。

Zookeeper 创建一个可用于所有节点读取的临时节点。每当集群状态发生变化时，可以通过仅使顶部节点可供读取来覆盖此行为。

仅当大量节点同时启动（以毫秒为单位）并且中间系统需要很长时间才能返回微不足道的结果时，并发才会成为问题。

于 2020-02-08T19:11:37.527 回答