CAP и FLP — две фундаментальные теоремы, дающие разные, но взаимодополняющие ограничения для проектирования распределённых систем.
Кратко о формулировках
- CAP (Brewer): в распределённой системе нельзя одновременно обеспечить все три свойства при наличии сетевых разрывов (partitions): Consistency (C), Availability (A) и Partition tolerance (P). На практике это формулируют как выбор между C и A в случае P. Иначе: во время разрыва система вынуждена жертвовать либо согласованностью, либо доступностью.
- FLP (Fischer–Lynch–Paterson): в полностью асинхронной системе с возможностью хотя бы одного сбоя процесса ($f\ge 1$) не существует детерминированного алгоритма, гарантирующего достижение консенсуса (и одновременно сохранение безопасных свойств) при любых задержках сети и сбоях. Следствие: нельзя обеспечить одновременно безопасный и живой (liveness) консенсус без дополнительных допущений о синхронности или случайности.
Чем отличаются по смыслу
- Область: CAP — высокий уровень практической рекомендации о поведении системы при сетевых разрывах; FLP — формальное невозможностное утверждение о консенсусе в модели асинхронности.
- Фокус: CAP говорит «при partition нужно выбирать между C и A», FLP говорит «в асинхронной модели с крашами консенсуса с детерминированной гарантией прогресса не существует».
- Последовательность: FLP объясняет, почему алгоритмы консенсуса (Paxos, Raft) не могут иметь абсолютных гарантий в чисто асинхронной среде и поэтому вводят таймауты/предположения о частичной синхронности; CAP — шаблон выбора дизайна, что делать при реальных partition'ах.
Практические следствия и компромиссы в дизайне
- Выбор CP vs AP:
- CP (Consistency + Partition tolerance): системы типа HBase, CP-последовательности используют консенсус/кворумы, жертвуя доступностью при разрыве (часть реплик может блокировать операции). Обычно требуется большинство: кворум $>\frac{N}{2}$.
- AP (Availability + Partition tolerance): системы типа Dynamo, Cassandra (с соответствующими настройками) предпочитают ответить, даже если реплики расходятся; согласованность достигается позже (eventual consistency), используются механизмы разрешения конфликтов (vector clocks, CRDT).
- Кворумы и параметры: прочность согласованности через кворумы требует условия $R+W>N$ для чтений/записей (чтобы пересечение реплик давало последнюю запись). Это прямо выражает компромисс между задержкой, пропускной способностью и согласованностью.
- Последствия FLP для алгоритмов консенсуса:
- Нужны дополнительные допущения: частичная синхронность (DLS-модель), детекторы сбоев или рандомизация. Практически это реализовано таймаутами, re-election в Raft/Paxos.
- Даже с консенсусом доступность может падать: если лидера нельзя выбрать в одной части сети, система блокируется (жизнеспособность теряется) — это проявление и CAP, и FLP одновременно.
- Архитектурные подходы:
- Для строгой согласованности — использовать консенсус для метаданных/контроля, и репликацию с кворумами для данных; ожидать возможную недоступность при partition.
- Для высокой доступности — применять ап-ориентированные модели: eventual consistency, CRDT, разрешение конфликтов на клиенте/сервисе.
- Гибриды: настраиваемые уровни согласованности (например, quorum конфигурации, read-your-write, bounded staleness) позволяют балансировать C/A в разных сценариях.
- Операционные практики: мониторинг и обнаружение partition'ов, ограничение времени ожидания (timeouts), graceful degradation, явная экспозиция консистентности клиентам (консистентность как настройка).
Краткая резюме-правило:
- CAP говорит, что при network partition вам придётся выбирать между C и A.
- FLP объясняет, почему для поддержания C в практике нужны таймауты/предположения (частичная синхронность) или рандомизация — иначе невозможно гарантировать прогресс при сбоях.
Вывод: проектируя отказоустойчивый сервис, нужно сознательно выбрать модель согласованности и механизмы (кворумы/консенсус/CRDT), понимать, какие сценарии (partition/задержки) система будет терпеть, и строить операционные допущения (timeouts, мониторинг, режимы деградации) в соответствии с теоретическими ограничениями CAP и FLP.