Это финальная статья серии про распределённые данные. В проблемах распределённых систем мы разобрали, чему в такой системе нельзя доверять: сети, часам, собственному процессу. Здесь — про абстракции, которые всё это прячут, и про консенсус — согласие нескольких узлов по одному вопросу.
Главный вывод будет неожиданным: половина задач, которые выглядят совершенно разными (выбрать ведущего, гарантировать уникальность имени, зафиксировать распределённую транзакцию), — на самом деле одна и та же задача. Пойдём к этому выводу шаг за шагом.
Линеаризуемость: иллюзия единственной копии
В базе с конечной согласованностью один и тот же запрос к двум репликам может вернуть разное — одна успела обновиться, другая отстала. Линеаризуемость (её ещё называют сильной согласованностью) это убирает: система ведёт себя так, будто копия данных всего одна и каждая операция происходит мгновенно и целиком. Как только клиент записал новое значение, любой следующий читатель видит именно его. Это гарантия актуальности — не «когда-нибудь сойдётся», а «прямо сейчас последнее».
Классический пример нарушения. Алиса и Боб смотрят финал матча в одной комнате. Алиса обновила страницу, увидела счёт и крикнула его Бобу. Боб обновляет у себя — а его запрос попал на отставшую реплику, и там матч «ещё идёт». Отставание реплики превратилось в видимый баг именно потому, что между Алисой и Бобом был второй канал связи — её голос.
Линеаризуемость нужна не везде — она медленная (почему — см. про CAP ниже), — но в нескольких местах без неё нельзя:
- Выбор ведущего. Ведущий должен быть ровно один (иначе split brain). Узлы обязаны прийти к единому мнению, кто это.
- Ограничения уникальности. Два человека одновременно занимают одно имя / бронируют одно место / снимают с одного счёта — выиграть должен ровно один.
- Межканальные зависимости. Пример выше: два разных пути к данным (кеш и база, очередь и хранилище) рождают гонку, которую как раз и закрывает линеаризуемость.
Важно не путать линеаризуемость с сериализуемостью. Сериализуемость — про изоляцию транзакций (несколько объектов, порядок транзакций между собой). Линеаризуемость — про актуальность чтения-записи одного объекта. Это разные гарантии, хотя названия похожи.
Теорема CAP без мифов
Раз линеаризуемость такая полезная — почему бы не сделать линеаризуемым вообще всё? Мешает сеть. Представь два дата-центра с репликацией между ними, и вот связь между ними оборвалась. Клиент на «отрезанной» стороне хочет что-то записать. Выбор жёсткий:
- Настаиваем на линеаризуемости. Реплика в меньшинстве не может подтвердить, что её данные актуальны, поэтому обязана отказать — стать недоступной — пока связь не восстановится. Это буква «C»: согласованность ценой доступности.
- Хотим доступность. Тогда принимаем запись локально, но реплики двух дата-центров неизбежно разойдутся (это уже не линеаризуемо). Это буква «A».
Это и есть CAP. Но популярная расшифровка «выбери 2 из 3: Consistency, Availability, Partition tolerance» — неверна. Разрыв сети (буква «P») — это не то, что можно «выбрать» или «не выбрать»: он просто случается, хотим мы того или нет. Честная формулировка короче: когда сеть разорвана — выбирай между согласованностью и доступностью. А пока сеть исправна, получаешь и то, и другое сразу.
Раз P (разрыв сети) в распределённой системе неизбежен, реальный выбор — это сторона CP или AP: что делать при разрыве — держать согласованность (и на время отказать в записи) или доступность (и позволить репликам разойтись). Сторона CA — это вообще один узел, где разрыва между узлами не бывает. Базы по сторонам треугольника подписаны именно так: MongoDB/HBase — CP, Cassandra/DynamoDB — AP.
К тому же CAP очень узок: он говорит лишь про один тип сбоя (разрыв связи) и одну модель (линеаризуемость) и молчит про задержки и мёртвые узлы. Поэтому на практике у теоремы скорее исторический интерес.
И отдельный любопытный факт: удивительно мало систем на самом деле линеаризуемы — причём отказываются от неё не ради переживания сбоев, а ради скорости. Линеаризуемость медленная всегда (время ответа тянется за сетевой задержкой), и большинство систем сознательно её не дают.
Порядок, причинность и рассылка
Линеаризуемость подразумевает полный порядок операций: единую шкалу, на которой любые две операции можно сравнить, что было раньше. Но есть порядок послабее, которого часто достаточно, — причинный (causal). Он упорядочивает только те операции, что связаны отношением «происходит до»: вопрос должен идти раньше ответа, строку надо сначала создать, а потом уже обновлять. А операции, которые ничего не знают друг о друге, — одновременные (конкурентные), и их порядок остаётся неопределённым. Причинный порядок — частичный: это как история коммитов в Git, где ветки расходятся и потом сливаются.
Причинность можно сохранять дешевле, чем полную линеаризуемость. Метки настенного времени для порядка не годятся (часы расходятся), а вот метки Лампорта — простые логические счётчики, которые растут при каждой операции и передаются в каждом сообщении, — дают полный порядок, согласованный с причинностью. Но и их недостаточно, чтобы решить вопрос уникальности имени: по меткам Лампорта порядок становится известен только постфактум, когда все операции уже собраны вместе, — а «занято ли имя прямо сейчас?» так не решить.
Что действительно нужно — понимать, в какой момент последовательность окончательно зафиксирована. Это даёт рассылка общей последовательности (total order broadcast): протокол, который гарантирует, что все узлы получают одни и те же сообщения в одном и том же порядке, надёжно, даже при сбоях. По сути это и есть журнал репликации: «доставить сообщение» = «дописать в журнал», и все реплики, проигрывая журнал в одном порядке, обязательно сходятся к одному состоянию.
Консенсус: всё это — одна задача
А вот и кульминация. Оказывается, все следующие задачи эквивалентны — реши одну по-настоящему, и получишь решение остальных:
- рассылка общей последовательности;
- линеаризуемая ячейка с операцией «сравни и присвой» (compare-and-set);
- выбор ведущего;
- ограничение уникальности;
- атомарная фиксация распределённой транзакции.
Все они — это консенсус: заставить несколько узлов договориться об одном значении. И у консенсуса есть строгие требования: единое решение для всех, его нельзя отменить, оно должно быть реально предложенным кем-то из узлов, и — завершённость: алгоритм обязан рано или поздно принять решение, пока живо большинство.
Атомарная фиксация — знакомый частный случай. Классический протокол — двухфазная фиксация (2PC). Координатор рассылает всем участникам «приготовьтесь» (фаза 1), собирает от всех «да», записывает решение в свой журнал (это точка невозврата) и рассылает «фиксируйте» (фаза 2). Ответив «да», участник теряет право откатиться сам. И если координатор упал ровно между фазами, участник застревает в неопределённости — держит блокировки и ждёт, пока координатор воскреснет. Поэтому 2PC называют блокирующим: координатор здесь — единая точка отказа. Это, по сути, плохой консенсус.
Хороший консенсус — это Raft, Paxos, Zab, VSR. Все они опираются на кворум большинства (два больших не пересечься не могут → двух противоречащих решений не будет) и на «эпохи»: в каждой эпохе не больше одного ведущего, а решение принимает голосование большинства. Теория пугает результатом FLP (в полностью асинхронной системе гарантированного консенсуса не существует), но на практике достаточно частичной синхронности или капли случайности — и консенсус достижим.
Практический вывод один и жёсткий: не пишите консенсус сами. Сделать это правильно почти невозможно. Возьмите готовый сервис — ZooKeeper или etcd: они дают линеаризуемое хранилище, выбор ведущего, распределённые блокировки и ограждающие маркеры «из коробки». Именно так внутри устроены HBase, Kafka, Kubernetes.
Где это применяется
Каждый раз, когда системе нужен ровно один ведущий, уникальное имя, «атомарно занять ресурс» или согласованный порядок событий, — вы упёрлись в консенсус, даже если не называли его этим словом. Практическая рамка: не тяните линеаризуемость и распределённые транзакции без нужды (они медленные и хрупкие — приложения обходят их сагами и outbox); а там, где согласие узлов действительно необходимо, — не изобретайте протокол, отдайте координацию ZooKeeper или etcd.
Где спотыкаются начинающие:
- Путают линеаризуемость и сериализуемость. Первая — про актуальность одного объекта, вторая — про изоляцию транзакций. Гарантии разные.
- Расшифровывают CAP как «2 из 3». Разрыв сети не выбирают; выбор «согласованность или доступность» встаёт только в момент разрыва.
- Упорядочивают события меткой Лампорта и думают, что решили уникальность. Полный порядок известен только постфактум; для проверки «сейчас» нужна рассылка общей последовательности.
- Пишут свой распределённый лок или выбор ведущего. Это консенсус, который почти невозможно реализовать верно. Берите ZooKeeper/etcd.
- Тянут 2PC между микросервисами. Это блокирующий протокол с координатором — единой точкой отказа; в микросервисах почти всегда лучше сага.
Что почитать дальше: проблемы распределённых систем — частичные отказы и fencing token, с которых начинается консенсус; модели репликации — кворумы и конечная согласованность; распределённые транзакции — почему приложения обходят 2PC сагами; ACID и изоляция — сериализуемость, которую важно не путать с линеаризуемостью.