Голосование в кластере

Голосование в кластере — это механизм принятия решений в распределённой вычислительной системе (кластере), при котором несколько узлов (серверов, процессов) обмениваются данными и на основе определённого алгоритма выбирают единый результат, устраняя конфликты и обеспечивая согласованность данных. Данный подход используется для повышения отказоустойчивости, достижения консенсуса и предотвращения расщепления сознания (split-brain) в системах, где критична целостность информации.

История и происхождение

Концепция голосования в кластере восходит к теории распределённых систем и алгоритмам консенсуса, разработанным в 1970–1980-х годах. Одним из первых формальных решений стал алгоритм Paxos, предложенный Лесли Лэмпортом в 1989 году (опубликован в 1998 году). Он описывал процесс, при котором узлы голосуют за предложенное значение, а большинство (кворум) определяет принятие решения. В 1990-х годах развитие получил алгоритм Raft, созданный Диего Онгаро и Джоном Остерхаутом (2013 год), который упростил понимание и реализацию консенсуса за счёт разделения на лидера, голосование и репликацию лога.

В СССР и России исследования в области распределённых систем велись в рамках создания отказоустойчивых вычислительных комплексов, например, в МИЭМ и ИПМ РАН. Однако практическое применение голосования в кластерах стало массовым с распространением кластерных технологий в 2000-х годах, особенно в системах управления базами данных (СУБД) и облачных платформах.

Цели и задачи голосования

Голосование в кластере решает несколько ключевых проблем распределённых систем:

Обеспечение согласованности данных: при одновременном изменении данных на разных узлах голосование выбирает единственную версию, которая считается истинной.
Предотвращение расщепления сознания (split-brain): когда из-за сбоя связи кластер распадается на изолированные группы, каждая из которых может считать себя лидером. Голосование с кворумом блокирует принятие решений в группе, не имеющей большинства.
Отказоустойчивость: при выходе из строя одного или нескольких узлов система продолжает работу, если оставшиеся узлы могут сформировать кворум.
Выбор лидера: в кластерных системах, где один узел выполняет роль координатора (лидера), голосование используется для его назначения или переизбрания при сбое.

Классификация методов голосования

По типу кворума

Простой кворум (majority quorum): решение принимается, если за него проголосовало более половины узлов (N/2 + 1). Например, в кластере из 5 узлов требуется 3 голоса.
Взвешенный кворум (weighted quorum): каждый узел имеет вес (например, в зависимости от производительности или объёма данных). Решение принимается при сумме весов, превышающей порог.
Кворум с приоритетом (priority quorum): узлам присваиваются приоритеты, и голосование учитывает их, чтобы отдать предпочтение более надёжным или быстрым узлам.
Динамический кворум (dynamic quorum): состав кворума может меняться в зависимости от текущего состояния кластера (например, при сбоях или добавлении новых узлов).

По механизму голосования

Голосование за предложение (proposal voting): узел-инициатор (лидер) предлагает значение, и другие узлы голосуют «за» или «против». Используется в Paxos и Raft.
Голосование за лидера (leader election): узлы голосуют за кандидата на роль лидера. Победитель становится координатором на определённый срок (термин).
Голосование за фиксацию транзакции (commit voting): применяется в распределённых базах данных (например, двухфазный протокол фиксации — 2PC). Узлы голосуют за успешное завершение транзакции.

Устройство и алгоритмы

Алгоритм Raft (пример)

Raft — один из наиболее популярных алгоритмов консенсуса, используемый в системах управления базами данных (например, etcd, Consul, TiKV). Его работа включает следующие этапы:

Выбор лидера: все узлы находятся в одном из трёх состояний — лидер, кандидат, последователь. Если последователь не получает сообщений от лидера в течение тайм-аута, он становится кандидатом и запрашивает голоса у других узлов.
Голосование: каждый узел отдаёт голос только одному кандидату за один термин (логический период). Кандидат, набравший большинство голосов (кворум), становится лидером.
Репликация лога: лидер принимает запросы от клиентов, записывает их в свой лог и отправляет копии всем последователям. После получения подтверждения от большинства узлов запись считается зафиксированной (committed).
Обработка сбоев: если лидер выходит из строя, запускается новый раунд выборов. При разделении кластера (split-brain) голосование блокирует работу в группе, не имеющей кворума.

Алгоритм Paxos (общий принцип)

Paxos работает в несколько фаз:

Фаза подготовки (prepare): лидер (прокси) отправляет запрос с номером предложения (n) всем узлам. Узлы обещают не принимать предложения с меньшими номерами и возвращают последнее принятое значение.
Фаза принятия (accept): лидер выбирает значение (например, из ответов) и отправляет запрос на принятие (accept) с номером n. Узлы принимают его, если не обещали более высокий номер.
Решение: решение считается принятым, если большинство узлов приняли предложение.

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

Применение

Системы управления базами данных (СУБД)

PostgreSQL: в режиме потоковой репликации (streaming replication) используется голосование для выбора синхронного или асинхронного режима. В кластерных решениях, таких как Patroni, голосование определяет, какой узел станет мастером.
MySQL: в кластере InnoDB Cluster (на основе Group Replication) узлы голосуют за фиксацию транзакций и выбор лидера.
Cassandra: использует взвешенное голосование для обеспечения согласованности данных при операциях чтения и записи (настраиваемый уровень согласованности — QUORUM, ALL, ONE).

Облачные платформы и распределённые хранилища

etcd (используется в Kubernetes): распределённое хранилище ключей-значений, работающее на Raft. Голосование обеспечивает консенсус при записи конфигураций кластера.
ZooKeeper: сервис координации распределённых приложений, использующий алгоритм Zab (аналогичный Paxos). Голосование применяется для выбора лидера и фиксации транзакций.
Consul: система обнаружения сервисов, также основанная на Raft.

Отказоустойчивые кластеры высокой доступности (HA)

Pacemaker и Corosync: кластерные менеджеры, используемые в Linux для обеспечения отказоустойчивости. Голосование (через механизм quorum) определяет, какой узел будет активным, а какой — резервным. При потере кворума кластер может перейти в состояние «остановлен» (fencing) для предотвращения повреждения данных.
Windows Server Failover Cluster: использует кворум на основе голосования узлов и, опционально, свидетеля (диск, файловая доля или облачный witness).

Блокчейн и криптовалюты

Proof of Stake (PoS): в блокчейн-сетях, таких как Ethereum (после перехода на PoS), валидаторы голосуют за добавление новых блоков. Голосование основано на доле (stake) — чем больше средств заблокировано, тем выше вес голоса.
Делегированное доказательство доли (DPoS): владельцы токенов голосуют за делегатов, которые затем принимают решения о валидации транзакций.

Критика и ограничения

Задержки и производительность: голосование требует обмена сообщениями между узлами, что увеличивает время ответа (latency). В системах с высокими требованиями к скорости (например, высокочастотная торговля) это может быть неприемлемо.
Сложность реализации: алгоритмы, такие как Paxos, сложны в правильной реализации и отладке. Ошибки в логике голосования могут приводить к неконсистентности данных.
Уязвимость к сбоям сети: при нестабильной связи или задержках узлы могут не получить вовремя запросы на голосование, что приводит к ложным выборам лидера или блокировке системы.
Проблема кворума при чётном числе узлов: в кластере из 2 узлов кворум (2/2) не может быть достигнут при сбое одного узла, что делает систему неработоспособной. Рекомендуется нечётное количество узлов (3, 5, 7) или использование свидетеля (witness).
Безопасность: в системах без криптографической защиты голосование может быть скомпрометировано злоумышленником, который подделывает голоса. В блокчейн-сетях это решается доказательствами с нулевым разглашением или криптографическими подписями.

Интересные факты

В кластере из 5 узлов при использовании простого кворума для принятия решения требуется 3 голоса. При этом система может выдержать отказ до 2 узлов.
Алгоритм Raft был разработан специально для обучения студентов, так как Paxos считается трудным для понимания. Название «Raft» происходит от «Reliable, Replicated, Redundant, And Fault-Tolerant».
В некоторых системах (например, в MongoDB) используется модифицированный Raft, где голосование может быть отложенным (deferred voting) для снижения нагрузки.
В России кластерные технологии с голосованием применяются в государственных информационных системах (например, в Единой государственной информационной системе в сфере здравоохранения — ЕГИСЗ) для обеспечения отказоустойчивости и целостности данных.

Источники

Lamport, L. (1998). «The Part-Time Parliament». ACM Transactions on Computer Systems.
Ongaro, D., Ousterhout, J. (2013). «In Search of an Understandable Consensus Algorithm (Raft)». USENIX ATC.
Tanenbaum, A. S., Van Steen, M. (2007). «Distributed Systems: Principles and Paradigms».
Официальная документация etcd, Consul, ZooKeeper, Pacemaker.
Стандарты и рекомендации по отказоустойчивым кластерам (RFC 5766, RFC 6962).

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →