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

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

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

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

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

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

Теорема. Конечный обмен сообщениями по каналу с потерями не может дать обоим генералам гарантированное общее знание о согласованной атаке. Доказательство — от противного. Предположим, существует успешное исполнение корректного протокола с конечным числом доставленных сообщений, и рассмотрим последнее сообщение m от A к B. После отправки m A уже не получает подтверждений и потому принимает то же решение и в неотличимом для него исполнении, где m потерялось. Чтобы в этом исполнении не возникло расхождения, B также обязан принять прежнее решение без 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.
• Детекторы отказов — формализация тайм-аутов: оракул, помечающий процессы подозреваемыми. Теория точно измерила, оракула какой силы достаточно для консенсуса, — разберём это подробно, заодно введя обозначения, которые понадобятся и дальше.

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

• □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 — то есть с оракулом, которому разрешено врать сколь угодно долго, лишь бы не вечно. (Более того, найден и слабейший достаточный детектор — Ω, «когда-нибудь все корректные доверяют одному и тому же живому лидеру»; узнаёте выборы 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 в одну таблицу «предположения → что достижимо»:

Модель / предположение              Что невозможно                Что покупается
──────────────────────────────      ───────────────────────────   ─────────────────────────────
Канал с потерями                    общее знание, exactly-once    at-least-once + идемпотентность,
                                    (два генерала)                сверки и компенсации
Асинхронность + 1 отказ             детерминированный консенсус   безопасность всегда (Raft/Paxos)
                                    с гарантией завершения (FLP)
+ частичная синхронность / ◇P       —                             живость в периоды стабильности
+ рандомизация                      —                             завершение с вероятностью 1
Сетевое разделение                  C + A одновременно (CAP)      осознанный выбор CP или AP
                                                                  по классам данных
Отсутствие общих часов (гл. 2)      порядок по физич. меткам      причинный порядок (Лэмпорт,
                                                                  векторы), HLC

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

Итоги главы

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

Упражнения

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

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

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. J. Gray, "Notes on Data Base Operating Systems," 1978 — §5.8: первоисточник задачи двух генералов в приложении к транзакциям.
5. M. Kleppmann, "A Critique of the CAP Theorem," 2015. arxiv.org/abs/1509.05393
6. D. Abadi, "Consistency Tradeoffs in Modern Distributed Database System Design (PACELC)," IEEE Computer 45(2), 2012.

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