Консенсус
Посли того как мы рассмотрели линеаризуемость, пришло время самой сложной проблем в мире распределенных систем и эта проблема консенсуса.
Если отойти от строгих определений, то консенсус означает достижение согласованности между несколькими узлами по какому-то вопросу. Допустим, несколько человек одновременно пытаются забронировать последнее место в самолете или одно и то же место в театре или зарегистрировать учетную запись с одинаковым именем пользователя. Консенсусный алгоритм позволяет определить, какой из этих несовместимых операций отдать предпочтение.
Лично у меня сразу возникает вопрос "Почему мы не можем использовать репликацию с одним ведущим узлом совместно с синхронной репликацией? Мы же получаем линеаризуемость записи и чтения. А ведущий узел в этой ситуации становиться диктатором для всех остальных. Вроде как это все, что нам нужно". Ответ как не странно прост. И кроется он в алгоритме выбора ведущего. Необходимо достичь согласованности всех узлов в выборе ведущего. А это задача как раз консенсуса. В итоге мы получаем замкнутый круг. Чтобы достичь консенсуса, нужен консенсус
И все-таки когда же нам важен консенсус:
Выбор ведущего узла. В распределенной системе обработки данных с репликацией с одним ведущим узлом все узлы должны прийти к единому мнению о том, какой из них является ведущим. Если же согласования не будет велик риск разделение интелекта (split brain). Ситуация в которой несколько узлов в кластере думают, что они главные. Это приводит к конкурентным записям и невозможности достижения линеаризуемости.
Атомарная фиксация. В распределенной системе обработки данных, которая поддерживает транзакции, охватывающие несколько узлов или разделов, иногда возникает проблема: транзакция может не сработать на одних узлах, но успешно закончиться на других.
Реализация отказоустойчивого консенсуса не самая простая задача и углубляться в реализацию я не буду (это может занять слишком много времени). Хочу только подсветить, что современные алгоритмы отказоустойчивого консенсуса используют кворум для предотвращения ситуации разделения сети (ситуация при которой каждая часть разделенной системы считает себя главной и продолжает производить запись, тем самым накапливая конфликты записи).
Рисунок ниже прекрастно демонстрирует проблему разделения сети.
- Клиент подключается к мастер узлу и активно пишет в него
- В какой-то момент сетевая доступность между мастером и репликой, мастером и монитором нарушается
- Монитор промоутит реплику до мастера и в системе появляется два мастера, а как мы помним мастер-мастер репликация не линеаризуема из-за возникновения конфликтов записи
- Сеть восстанавливается, но конфликты уже накоплены
Кворумом является любое большинство узлов системы. Если перевести это на язык формул, но кворум будет выглядеть так k/2 + 1, где k - общее число услов в системе.

