Распределенная система: выборы лидера

Проблема в том, что мы хотели бы избежать того, чтобы все компьютеры знали друг друга, а только лидер.

Выборы лидеров — это проблема выбора единственного лидера из множества потенциальных кандидатов в лидеры. Считайте, что у него есть два обязательных свойства: живучесть и безопасность. Здесь живость будет означать, что «большую часть времени есть лидер», а безопасность будет означать, что «лидеров нет или один». Давайте рассмотрим, как мы будем решать это свойство безопасности в вашем примере, используя широковещательную рассылку.

Давайте выберем простой (сломанный) алгоритм, предполагая, что каждый узел имеет уникальный идентификатор. Каждый узел транслирует свой идентификатор и слушает. При получении более высокого ID, чем его собственный, прекращает участие. Если он получает более низкий идентификатор, чем его собственный, он снова отправляет широковещательную рассылку. Предполагая синхронную сеть, последний идентификатор, который все получают, является идентификатором лидера. Теперь представьте сетевой раздел. Протокол благополучно продолжится по обе стороны раздела, и будут избраны два лидера.

Это верно для этого сломанного протокола, но также верно для всех возможных протоколов. Как отличить узлы, с которыми вы не можете связаться, и узлы, которые не существуют, если вы не знаете (по крайней мере), сколько узлов существует? Итак, есть первый результат безопасности: вам нужно знать, сколько существует узлов, иначе вы не сможете гарантировать наличие только одного лидера.

Теперь давайте ослабим наше ограничение безопасности, сделав его вероятностным: «лидеров может быть ноль или больше, но в большинстве случаев он один». Это делает проблему разрешимой, и широко используемым решением являются сплетни (эпидемические протоколы). Например, см. Служба обнаружения сбоев в стиле сплетен, в которой обсуждается вариант именно эта проблема. Статья в основном посвящена вероятностно правильному обнаружению и перечислению отказов, но если вы можете это сделать, вы также можете провести вероятностно правильный выбор лидера.

Насколько я могу судить, безопасные невероятностные выборы лидеров в общих сетях невозможны без хотя бы перечисления участников.

В качестве одного из интересных решений «распределенной механики», которые я видел в прошлый раз, я бы рекомендовал Apache проект zookeeper. Это решение с открытым исходным кодом, поэтому, по крайней мере, вы сможете почерпнуть оттуда пару идей. Кроме того, он интенсивно развивается, поэтому, возможно, вы можете повторно использовать его как часть своего решения.

ZooKeeper — это централизованная служба для хранения информации о конфигурации, именования, обеспечения распределенной синхронизации и предоставления групповых услуг. Все эти виды услуг в той или иной форме используются распределенными приложениями. Каждый раз, когда они реализуются, требуется много работы, направленной на исправление ошибок и условий гонки, которые неизбежны. Из-за сложности реализации таких сервисов приложения изначально обычно экономят на них, что делает их неустойчивыми при наличии изменений и сложными в управлении. Даже если все сделано правильно, разные реализации этих служб приводят к сложности управления при развертывании приложений.

Я бы рекомендовал JGroups для решения этой проблемы, если вы строите систему поверх JVM.

http://www.jgroups.org/

Используйте LockService, чтобы убедиться, что только 1 узел в кластере является ведущим. JGroups можно настроить для использования Peer Lock или Central Lock — любой из них должен работать в вашем случае.

См. http://withmeta.blogspot.com/2014/01/leader-election-problem-in-elastic.html для реализации Clojure или http://javabender.blogspot.com.au/2012/01/jgroups-lockservice-example.html для Java.

Практическим решением является использование БД в качестве точки «встречи».

Это решение ОЧЕНЬ удобно, особенно если вы уже используете базу данных SQL, все, что вам нужно, это новая таблица. Если вы используете кластер БД, вы можете воспользоваться его высокой доступностью.

Вот таблица, которую использует моя реализация:

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

Идея состоит в том, чтобы иметь строку для каждого общего ресурса. Лидеры будут соревноваться за один и тот же ряд.

Моя упрощенная реализация С# выглядит так:

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-соединение и низкоуровневый доступ к таблице.

Используйте разумные сроки. Помните, что в случае отказа текущего лидера ресурс будет заблокирован до истечения срока действия.

@Marc очень хорошо это описал. Я хотел бы добавить некоторые моменты по этому поводу.

Если все участвующие системы не должны знать друг о друге, то идентификатор вещания (или, скажем, временная метка) не раскрывает свое состояние, если только она не выбрана в качестве ведущей. Будучи избранным в качестве лидера, он теперь может транслировать состояние машины для всех других узлов в кластере для подключения.

Если участвующие системы вообще не должны раскрывать свое присутствие, то должна быть система для связи, например. БД (как упомянул Игорь), система на основе TCP или смонтированное местоположение (способ, который выбирает зоопарк), где хранится все состояние машин, но меньше всего (или первое доступно с разрешением на чтение), а лидер продолжает обновлять его состояние этой системы. Если лидер выходит из строя, система выбирает следующий узел в качестве лидера, делая его доступным для чтения другим узлам, очищая последнюю запись лидера.

Zookeeper создает эфемерный узел, доступный для чтения всем узлам. Это поведение можно переопределить, сделав доступным для чтения только верхний узел всякий раз, когда происходит изменение состояния кластера.

Параллелизм может быть проблемой только в том случае, если большое количество узлов запускается одновременно (в миллисекундах), а промежуточной системе требуется слишком много времени, чтобы вернуть мизерный результат.