Курс «Распределённые системы». Глава 3. Невозможности

Цели главы. Разобрать три классических отрицательных результата — задачу двух генералов, теорему FLP и теорему CAP — и научиться читать их правильно: не как приговоры, а как карту границ, внутри которых живёт всё проектирование. Каждую теорему мы сопровождаем ответом на два вопроса: что именно она запрещает (обычно меньше, чем принято думать) и какими предположениями запрет обходится на практике (обычно честной ценой, которую надо знать). Глава завершает теоретические основания курса; со следующей начинаются конструкции.

3.1. Зачем инженеру теоремы о невозможности

Отрицательный результат — самый полезный вид знания в инженерии: он закрывает целые направления поиска. Тот, кто знает FLP, не станет обещать заказчику «кластер, который гарантированно выбирает лидера за 500 мс при любых сетевых условиях»; тот, кто понимает двух генералов, не будет искать библиотеку с честной доставкой exactly-once; тот, кто читал не только аббревиатуру CAP, не будет требовать «строгую согласованность и стопроцентную доступность» в одном ТЗ. Невозможности экономят годы: каждая из теорем этой главы когда-то остановила индустриальную гонку за недостижимым.

3.2. Разминка: два генерала

Начнём с результата, доказываемого в четыре строки. Два генерала на холмах должны атаковать одновременно; связь — гонцы через долину, где их перехватывают (канал с потерями, глава 1). Требуется протокол, по завершении которого оба точно знают, что атака согласована.

Теорема. Конечный обмен сообщениями по каналу с потерями не может дать обоим генералам гарантированное общее знание о согласованной атаке. Доказательство — от противного. Предположим, существует успешное исполнение корректного протокола, и возьмём среди таких исполнений одно с минимальным числом доставленных сообщений; рассмотрим последнее доставленное в нём сообщение m (пусть от A к B). После отправки m A уже не получает подтверждений и потому принимает то же решение и в неотличимом для него исполнении, где m потерялось. Чтобы в этом исполнении не возникло расхождения, B также обязан принять прежнее решение без m. Значит, m не было необходимо — а это противоречит минимальности. (Ту же операцию можно повторять: удаляя последнее сообщение снова и снова, пришли бы к согласованной атаке вообще без связи, что невозможно при независимых исходных состояниях генералов.) ∎

Формально: по каналу с потерями недостижимо общее знание (я знаю, что ты знаешь, что я знаю... — до бесконечности). Практические следствия: обещанная в главе 1 теорема о недостижимости exactly-once-доставки — это два генерала в профиль (упражнение 1); двухфазная фиксация транзакций (глава 9) не «плохо спроектирована», а упирается в этот предел; TCP-рукопожатие завершается не абсолютной уверенностью, а «достаточной для практики». Обход у индустрии один: заменить «оба точно знают» на «расхождение обнаружимо и устранимо потом» — подтверждения, повторы, сверки, идемпотентность.

3.3. Теорема FLP

Центральный отрицательный результат области. Сформулируем задачу консенсуса (она же — сердце глав 6 и далее): каждый процесс предлагает значение; требуется, чтобы (1) все корректные процессы в итоге решили — завершаемость; (2) решили одно и то же — согласие; (3) решённое было кем-то предложено — обоснованность (без неё «всегда решай 0» — законный протокол).

Теорема (Фишер, Линч, Патерсон, 1985): в асинхронной системе с надёжными каналами ни один детерминированный протокол не решает консенсус, если хотя бы один процесс может отказать (crash-stop). Обратите внимание на скупость условий: каналы даже надёжны, отказ всего один — и всё равно невозможно.

Идея доказательства (эскиз, достаточный для понимания механики). Назовём конфигурацию системы бивалентной, если из неё ещё достижимы оба исхода (решение 0 и решение 1), и унивалентной — если исход предрешён. Два шага: (а) у любого корректного протокола существует бивалентная начальная конфигурация — иначе решение зависело бы только от входов, и тогда, меняя вход одного процесса по цепочке от «все предложили 0» к «все предложили 1», найдём соседние конфигурации с разным предрешённым исходом, различающиеся входом одного процесса; «убив» его, получим противоречие; (б) из любой бивалентной конфигурации, как ни планируй доставку сообщений, противник-планировщик может доставить их в таком порядке, что система останется бивалентной: решающий шаг — доставку сообщения, превращающего систему в унивалентную, — можно откладывать неограниченно, пользуясь тем, что в асинхронной модели «медленное» неотличимо от «мёртвого». Итог: существует бесконечное исполнение, в котором решение не принимается никогда — нарушена завершаемость. ∎

Что теорема означает: в честной модели интернета нельзя гарантировать консенсус за конечное время в худшем случае. Чего она не означает: что консенсус не работает на практике. Запрет касается детерминированных протоколов и гарантий худшего случая; худший случай — бесконечно изобретательный противник-планировщик, реальная сеть таковым не является. Легальные обходы, каждый со своей ценой:

• Частичная синхронность (глава 1): предположить, что «когда-нибудь сеть стабилизируется». Raft и Paxos безопасны всегда (согласие и обоснованность не нарушаются ни при каком поведении сети!), а завершаемость гарантируют лишь в периоды стабильности. Это идеальное разделение труда: FLP бьёт только по живости, безопасность неприкосновенна.
• Рандомизация: случайная монетка ломает стратегию противника-планировщика; рандомизированные протоколы (Бен-Ор и наследники) завершаются с вероятностью 1 — детерминированной границы времени по-прежнему нет. Не путать с этим случайные тайм-ауты выборов в Raft: они лишь снижают вероятность повторного раскола голосов, а живость Raft по-прежнему опирается на частичную синхронность.
• Детекторы отказов — формализация тайм-аутов: оракул, помечающий процессы подозреваемыми. Теория точно измерила, оракула какой силы достаточно для консенсуса, — разберём это подробно, заодно введя обозначения, которые понадобятся и дальше.

Отступление: язык темпоральной логики. Утверждения о распределённых системах — это утверждения о поведении во времени: «плохое не случится никогда», «хорошее когда-нибудь произойдёт». Для них в литературе используются два оператора темпоральной логики, и оба уже неявно работали в этой главе:

• □A (квадрат, читается «всегда A»): утверждение A истинно в каждый момент любого исполнения. Пример: «в одном терме Raft не бывает двух избранных лидеров».
• ◇A (ромб, читается «когда-нибудь A», «в конце концов A»): в исполнении существует момент, когда A истинно. Момент конечен, но заранее неизвестен и ничем не ограничен — «когда-нибудь» без обещания срока. Пример: «когда-нибудь лидер будет избран».

Операторы комбинируются: ◇□A — «с некоторого момента A истинно всегда» (побыв ложным конечное время, A устанавливается навсегда). На этом языке точно формулируется деление свойств, которым мы пользуемся с раздела о FLP и будем пользоваться до конца курса (особенно в главе 11): безопасность — свойства вида □(не плохое): «два процесса не решают разные значения», «зафиксированное никогда не теряется»; живость (liveness) — свойства вида ◇(хорошее): «когда-нибудь решение будет принято». Для лидерских протоколов корректное утверждение обычно звучит как «не более одного лидера в одном терме» или «не более одного лидера способен фиксировать записи», а не как запрет двум узлам временно считать себя лидерами разных эпох. FLP на этом языке — теорема о том, что живость консенсуса недостижима с гарантией; безопасность она не затрагивает.

Теперь — детекторы отказов строго (Чандра–Туэг, 1996). Детектор отказов — это оракул при каждом процессе, выдающий список подозреваемых в отказе; протоколу разрешается им пользоваться, а качество оракула описывается двумя свойствами:

• полнота: каждый действительно отказавший процесс когда-нибудь (◇) и навсегда попадает в подозреваемые у всех корректных;
• точность: корректные процессы не подозреваются.

P (perfect, совершенный детектор) требует точности всегда (□): ни один живой процесс никогда не подозревается. В асинхронной системе P нереализуем — это переформулировка вывода главы 1: тайм-аут не доказывает смерть, значит, любой детектор на тайм-аутах иногда клевещет на живых. ◇P (eventually perfect, «в конце концов совершенный») ослабляет точность ромбом: детектору разрешено конечное время ошибаться как угодно — подозревать живых, снимать подозрения, снова подозревать, — но с некоторого момента и навсегда его точность становится безупречной. Формально приставка ◇ здесь означает «◇□»: когда-нибудь — и затем всегда.

◇P — это математический портрет тайм-аута в частично синхронной сети: пока сеть штормит, тайм-ауты срабатывают ложно (медленный узел объявляется мёртвым); когда сеть стабилизируется и задержки входят в границы, срабатывания становятся правдой. Результат Чандры–Туэга: при большинстве корректных процессов консенсус решается уже с детектором ◇P — то есть с оракулом, которому разрешено врать сколь угодно долго, лишь бы не вечно; более того, достаточно ещё более слабого ◇S, которому и после стабилизации разрешено клеветать на кого угодно, кроме хотя бы одного корректного процесса. (А слабейший детектор, при котором консенсус вообще разрешим, — Ω, «когда-нибудь все корректные доверяют одному и тому же живому лидеру» (Чандра, Хадзилакос, Туэг, 1996); узнаёте выборы Raft?) Практический смысл, ради которого всё отступление и затевалось: консенсусу не нужны точные тайм-ауты — достаточно тайм-аутов, когда-нибудь перестающих врать; именно поэтому Raft может позволить себе грубые рандомизированные тайм-ауты выборов, а инженер, подбирающий election timeout, настраивает не корректность (она безусловна — □), а скорость наступления того самого «когда-нибудь» (◇).

3.4. Теорема CAP

Самая известная и самая перевираемая. Дадим строгие определения — в них вся суть. C (согласованность) = линеаризуемость: система отвечает так, как будто копия одна (строго — в главе 4). A (доступность) = каждый запрос к любому неотказавшему узлу получает содержательный ответ (не ошибку, не вечное ожидание). P (устойчивость к разделению) = в модели допускаются разделения — сообщения между группами узлов могут теряться сколь угодно долго, — и система обязана иметь определённое поведение на это время.

Теорема (гипотеза Брюера 2000, доказательство Гилберта–Линч 2002): свойства C, A, P одновременно недостижимы. Доказательство — почти одна картинка: пусть сеть разделила узлы на группы G1 и G2. Клиент пишет x := 1 в G1; по доступности G1 обязана подтвердить (ждать G2 нельзя — ожидание неограниченно, это отказ в обслуживании). Затем клиент читает x из G2; по доступности G2 обязана ответить — но о записи она физически не могла узнать (сообщений через разрез нет) и ответит старым значением. Линеаризуемость нарушена. ∎

Как читать правильно. Во-первых, P — не опция: разделения в реальной сети случаются, «отказаться от P» означает лишь «не определить поведение системы при разделении» — худший из вариантов. Реальный выбор: при разделении жертвовать доступностью (CP: меньшинство отвечает ошибкой — так ведут себя системы на кворумах и консенсусе: etcd, ZooKeeper) или согласованностью (AP: отвечают все, копии расходятся, потом сливаются — Dynamo-наследники, кэши, DNS). Во-вторых, выбор не общесистемный, а по операциям и данным: одна и та же СУБД может отдавать линеаризуемые чтения с лидера и итогово-согласованные с реплик. В-третьих, полезное расширение PACELC: при разделении (P) — выбор A либо C, а в остальное время (E) — выбор между задержкой (L) и согласованностью (C): строгая согласованность стоит координационного round-trip в каждой записи, и эту цену платят всегда, а не только в аварию.

И предостережение от суеверия: CAP — теорема о двух конкретных сильных свойствах при разделении, не более. Она ничего не говорит о задержках без разделений, о долговечности, о поведении при отказах узлов без разрыва сети; сводить проектирование к «выбору двух букв» — значит потерять всё содержание глав 4–5, где спектр промежуточных гарантий и есть главный предмет.

3.5. Сводная карта границ

Соберём часть I в одну таблицу «предположения → что достижимо»:

Эта таблица — точный чертёж дизайн-пространства: каждая конструкция частей II–III курса занимает в ней своё место, честно объявляя, какими предположениями и какими жертвами она куплена.

Итоги главы

• Два генерала: по ненадёжному каналу недостижимо общее знание — отсюда невозможность exactly-once-доставки и пределы атомарной фиксации; индустриальный ответ — обнаруживать и устранять расхождения, а не исключать их.
• FLP: в асинхронной модели с одним отказом детерминированный консенсус не может гарантировать завершения. Бьёт только по живости: Raft/Paxos безопасны всегда, а завершаются «когда сеть стабильна» (частичная синхронность, детекторы отказов ◇P/◇S/Ω) или «с вероятностью 1» (рандомизация).
• CAP: при разделении — C или A; P не выбирают. Читать как «спроектируйте поведение на время разделения по каждому классу данных»; PACELC напоминает, что согласованность стоит задержки и в мирное время.
• Теоремы невозможности — карта границ дизайн-пространства, а не повод для пессимизма: всё, что не запрещено, в следующих главах будет построено.

Упражнения

1. Примените задачу двух генералов к удалённому вызову из главы 1: покажите, почему потеря последнего подтверждения оставляет отправителю неопределённость. Затем отдельно укажите, как долговечная дедупликация обеспечивает один эффект внутри БД и почему это не становится доставкой сообщения «ровно один раз».
2. В доказательстве двух генералов найдите точное место, где используется ненадёжность канала. Останется ли результат в силе, если канал надёжен, но с неограниченной задержкой (асинхронный)? Указание: требуется ли обоим генералам решить к фиксированному сроку?
3. Протокол «лидер — узел с наименьшим идентификатором из отвечающих на пинги» предлагается для выбора лидера. Покажите два исполнения: (а) при разделении два узла одновременно считают себя лидерами; (б) при череде ложных подозрений лидер не стабилизируется. Какое свойство выбора лидера — безопасность или живость — нарушено в каждом случае?
4. Объясните, почему Raft не противоречит FLP: какое дополнительное временное предположение нужно ему для живости и какое свойство не гарантировано в полностью асинхронном исполнении? Приведите сценарий повторных перевыборов и объясните, почему случайные тайм-ауты уменьшают их вероятность, но не дают жёсткой границы времени.
5. В доказательстве CAP замените требование линеаризуемости на итоговую согласованность. Где доказательство ломается? Сформулируйте, что именно AP-система обещает клиенту, прочитавшему старое значение.
6. Классифицируйте по поведению при разделении (CP/AP, и для каких операций): кластер etcd из 5 узлов; Dynamo-стиль хранилище с W=1, R=1, N=3; DNS; кэш CDN; репликация PostgreSQL «лидер + асинхронная реплика» при чтениях с реплики.
7. Заказчик требует в ТЗ: «система должна сохранять строгую согласованность и стопроцентную доступность при любых сетевых сбоях». Составьте короткий (5–7 предложений) профессиональный ответ: что невозможно дословно, какие уточняющие вопросы задать (какие данные, какой срок недоступности терпим, что дороже — отказ или расхождение) и какие два честных варианта предложить.

Ответы и указания. 1: запрос и ответы играют роль гонцов. После потери последнего ответа отправитель не знает, был ли эффект, и выбирает между риском пропуска и риском повтора. Долговечная дедупликация даёт один эффект только внутри своей транзакционной границы, но не гарантирует единственную доставку сообщения. 2: ненадёжность используется при удалении последнего доставленного сообщения. Если канал гарантирует конечную доставку и нет отказов, узлы могут дождаться сообщений; если совместное действие требуется к сроку, но верхней границы задержки нет, своевременное общее знание всё равно не гарантируется. 3: при разделении две группы выбирают своих минимальных узлов — нарушена безопасность выбора лидера; при бесконечной череде ложных подозрений лидер не стабилизируется — нарушена живость. 4: безопасность Raft не требует границы задержки, а живость требует периода частичной синхронности. В полностью асинхронной сети сообщения можно задерживать так, чтобы выборы повторялись бесконечно; случайные тайм-ауты снижают вероятность одинаковых раундов, но не создают детерминированного предела. 5: доказательство ломается на обязанности чтения увидеть завершённую запись: итоговая модель разрешает старое значение, но обещает сходимость после прекращения обновлений, доставки версий и разрешения конфликтов. 6: линеаризуемые операции etcd при разделении доступны только стороне с кворумом; Dynamo-стиль W=1,R=1 может отвечать с разных реплик и затем разрешать конфликты; DNS и кэши обычно допускают устаревание; PostgreSQL с одним лидером прекращает запись без доступного лидера, а чтение с асинхронной реплики может быть устаревшим. 7: требование дословно противоречит CAP при разделении. Нужно разделить данные и операции по инвариантам, определить допустимое окно отказа и цену устаревшего ответа. Вариант с линеаризуемостью отказывает стороне без кворума; вариант с доступностью обеих сторон допускает расхождение и требует правил слияния. Для разных операций одной системы допустимы разные решения, и это следует зафиксировать в контракте.

Литература к главе

1. M. Fischer, N. Lynch, M. Paterson, "Impossibility of Distributed Consensus with One Faulty Process," JACM 32(2), 1985.
2. S. Gilbert, N. Lynch, "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services," ACM SIGACT News 33(2), 2002.
3. T. Chandra, S. Toueg, "Unreliable Failure Detectors for Reliable Distributed Systems," JACM 43(2), 1996.
4. T. Chandra, V. Hadzilacos, S. Toueg, "The Weakest Failure Detector for Solving Consensus," JACM 43(4), 1996.
5. J. Gray, "Notes on Data Base Operating Systems," 1978 — §5.8: первоисточник задачи двух генералов в приложении к транзакциям.
6. M. Kleppmann, "A Critique of the CAP Theorem," 2015. arxiv.org/abs/1509.05393
7. D. Abadi, "Consistency Tradeoffs in Modern Distributed Database System Design (PACELC)," IEEE Computer 45(2), 2012.

Предыдущая глава || Содержание курса || Следующая глава