CAP‑теорема — суть
- Формулировка: в распределённой системе при наличии сетевых разрывов невозможно одновременно обеспечить все три свойства: согласованность (Consistency), доступность (Availability) и переносимость разделения сети (Partition tolerance). Практически нужно выбирать между C и A при P (разрывах) — обычно жертвуют либо доступностью, либо согласованностью.
- Интерпретация: при partition system must choose C (отказ в обслуживании части запросов, чтобы не нарушить согласованность) или A (отвечать с потенциально устаревшими данными).
Консенсусные алгоритмы (Paxos / Raft) — ключевые идеи
- Общая цель: добиться единого решения (например, порядок транзакций/лог) среди отказоустойчивых узлов.
- Кворумы: решение принимается только если поддержка большинства; размер большинства $\lceil \frac{N}{2}\rceil$.
- Paxos: двух/трёхфазный протокол (prepare/accept/learn), очень устойчив к сбоям, но сложен и труден для реализации в виде понятного API; multi‑Paxos оптимизирует для серии записей (лидер держит право предлагать).
- Raft: проектировался для простоты понимания и реализации. Главные механизмы: выбор лидера (election), реплицируемый журнал (log replication), применение записей в порядке лога. Обеспечивает безопасность (согласованность лога) и ливнесс (при наличии большинства и нормальной сети).
- Последствия: консенсус обеспечивает сильную согласованность (linearizability/serializability для операций, использующих консенсус), но при partition или если узел не в кворуме — доступность падает (CP).
Eventual consistency — когда приемлема
- Приемлема, если система допускает временну́ю расходимость данных, а затем — сходимость без вмешательства:
- пользовательские профили, ленты новостей, кэширование, аналитика, некоторые каталоги и поисковые индексы;
- сценарии с высокой доступностью и геораспределённостью, где небольшая задержка согласования более критична, чем строгая консистентность.
- Неприемлема для: банковских переводов, денежных расчётов, распределённых блокировок, метаданных согласования или любых сторон, где нарушение порядка/потеря транзакционной согласованности критично.
- Механизмы контроля: настройка временной допускной разницы, гарантий повторной синхронизации и разрешения конфликтов (см. ниже).
Паттерны разрешения и гарантий при eventual consistency
- Quorum (Dynamo‑style): для обеспечения некоторой согласованности используется правило $R+W>N$, где $N$ — число реплик, $W$ — число подтверждений записи, $R$ — число ответов чтения.
- Разрешение конфликтов: last‑write‑wins (LWW), vector clocks, application‑level merge, CRDT (конфликто‑устойчивые типы данных) — выбор зависит от требований к детерминированности и потере данных.
- Репликация: асинхронная (высокая доступность, возможна рассогласованность) vs синхронная (позволяет сильную согласованность, но выше задержки).
Паттерны применения: лидеры, шардинг, репликация
- Лидер (primary/leader‑based replication)
- Все записи идут через лидера; упрощает согласованность и порядок; чтения можно масштабировать через реплики.
- Минус: лидер — узкое место и точка отказа (требуется быстрый failover/авто‑элекшн).
- Мульти‑лидер (multi‑master)
- Параллельные лидеры для разных географических зон; повышает доступность и локальную запись.
- Нужно решение конфликтов при репликации между лидерами (также подходит CRDT).
- Leaderless / quorum (Dynamo, Cassandra)
- Нет единого лидера; операции согласуются через кворумы; хорошо масштабируется и устойчиво к локальным отказам.
- Требует хорошо продуманной стратегии разрешения конфликтов.
- Шардинг (partitioning)
- Горизонтальное разделение данных по ключу: хеш‑шардинг (consistent hashing) или range‑sharding.
- Плюс: линейное масштабирование по объёму и пропускной способности. Минус: сложность перемещения данных и кросшардовые транзакции.
- Репликация
- Количество реплик $N$ определяет надёжность/доступность; конфигурация синхронная vs асинхронная влияет на задержку и риск потери данных.
- Read replicas для масштабирования чтений; следует учитывать читаемые задержки согласования.
Рекомендации по выбору
- Нужна строгая согласованность (банки, координаторы): используйте консенсус (Raft/Paxos), leader‑based репликацию, синхронные commit‑quorums.
- Нужна высокая доступность и геораспределённость, допускается рассогласование: eventual consistency с quorum или multi‑leader, конфликт‑разрешение (CRDT) и асинхронная репликация.
- Для масштабирования: шардинг + репликация; для критичных метаданных — держать через консенсусный сервис (CP), для «тёплых» данных — eventual (AP).
Краткое резюме
- CAP: при partition приходится выбирать C или A.
- Paxos/Raft дают сильную консистентность, но снижают доступность при partition (CP).
- Eventual consistent системы дают высокую доступность и масштабируемость (AP), но требуют механизмов разрешения конфликтов.
- Практика: комбинируют паттерны (лидеры для критичных операций, шардинг для масштабирования, репликация и quorum‑политики для балансировки C/A).