Алгоритмы консенсуса в распределенных системах

Заканчиваем 9 главу кабанчика. В этой главе рассматривались алгоритмы построения отказоустойчивых распределенных систем. Прошлый раз мы разобрали двухфазный коммит, сегодня кратко разберём алгоритмы консенсуса.

Что значит консенсус среди узлов? Это значит, несколько узлов пришли к согласию по какому-то вопросу.

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

Если не учитывать отказоустойчивость, то добиться консенсуса легко: назначаем один узел лидером, и он принимает все решения. Как в репликации с одним ведущим узлом.

Однако если лидер выйдет из строя, то всё, система больше не сможет принимать решения.

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

Сколько узлов мы можем потерять, чтобы система продолжала работать? Для отказоустойчивости обычно нужно, чтобы рабочими остались большинство узлов — они могут собрать кворум.

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

Наиболее известные отказоустойчивые алгоритмы консенсуса:
🟣Paxos
🟣Raft

🤝 Нумерация периодов и кворумы

Для работы консенсусного алгоритма нужен ведущий узел. В алгоритме Paxos такие узлы называются proposers, в Raft — лидеры. Чтобы не было конфликтов, кто сейчас является лидером, консенсусные алгоритмы используют систему периодов: для каждого периода времени определяется свой лидер.

Каждый раз, когда становится ясно, что действующий лидер вышел из строя, между узлами начинается голосование с целью выбрать новый. Каждым таким выборам присваивается порядковый номер периода. Номера периодов монотонно возрастают. В случае конфликта между двумя лидерами преимущество имеет лидер с более высоким номером периода.

Чтобы стать лидером, узел должен собрать голоса кворума узлов. Обычно кворум состоит из большинства узлов (2 из 3, 3 из 5 и др.). Узел голосует за предложение только если ему неизвестен другой лидер с более высоким номером периода.

🤨 Ограничения консенсуса

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

Хотя консенсус — очень крутая штука для распределенных систем, его стоит использовать только там, где это точно нужно. Потому что за преимущества приходится расплачиваться снижением производительности. Так как дополнительное общение узлов занимает время.

✔️ «Аутсорсинг» консенсуса

Допустим, нашей системе нужен алгоритм консенсуса. Сначала у нас было 3 узла, потом 5, потом мы выросли до системы с тысячами узлов. Попытка получить большинство голосов на таком количестве узлов будет совершенно неэффективной. Вместо этого удобно использовать для задач консенсуса уже готовый сервис, например хранилища ZooKeeper, Google Chubby.

ZooKeeper работает на фиксированном количестве узлов (3 или 5) и может «аутсорсить» услуги консенсуса для внешнего сервиса с большим количеством узлов.

Когда это может понадобиться?

👉 для определения ведущего сервиса среди нескольких, например, нового ведущего узла при репликации с одним лидером

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

Хранилище etcd, которое использует Kubernetes, тоже основано на консенсусном алгоритме Raft.

Ух, на этом мы закончили главу 9 🔥 Всего в книге 12 глав, ссылки на разобранные есть в закрепе.

#кабанчик #сисдиз