Кратко о теореме CAP
- CAP говорит о трёх свойствах: Consistency (C) — все клиенты видят одно и то же состояние, Availability (A) — каждый запрос получает ответ (не обязательно актуальный), Partition tolerance (P) — система продолжает работать при разрыве сети.
- Формально: при наличии сетевого разрыва $P$ нельзя одновременно иметь и $C$ и $A$: $$P\Rightarrow \neg (C\wedge A).$$
Пример на распределённой базе для чата
Топология: репликация сообщений на $N$ серверов (например, $N=3$), пользователи подключены к ближайшему серверу. Сценарий: сеть разделилась на две части (partition) — пользователи в обеих частях продолжают отправлять сообщения.
1) Выбор CP (Consistency over Availability).
- Механизм: записи требуют кворума (например, write quorum $W$, read quorum $R$ с условием $W+R>N$). Пример: $N=3,W=2,R=2$.
- Поведение при partition: если узел не может собрать кворум — он отказывает в записи -> система остаётся согласованной, но часть клиентов получает ошибку (снижается доступность).
- Пример в чате: при partition пользователь получает ошибку «не могу отправить сообщение», пока кворум не восстановится; после восстановления порядок и наличие сообщений едины.
2) Выбор AP (Availability over Consistency).
- Механизм: локальные записи принимаются немедленно и реплицируются асинхронно (multi-master, gossip).
- Поведение при partition: все операции принимаются, но разные реплики могут расходиться; при восстановлении выполняется слияние/конфликт-решение.
- Пример в чате: оба пользователя отправили сообщения; оба сообщения видны локально сразу; после слияния возможны дубликаты, конфликтные порядки или рассогласование меток прочтения.
Эластичная (ослабленная) согласованность
- Eventual consistency: если в какой‑то момент перестают приходить новые обновления, все реплики со временем сходятся к одному состоянию. Гарантия не даёт порядка или моментальной консистентности, но обеспечивает сходимость. Частые механизмы: anti-entropy (госсип), Merkle‑деревья, репликация лога.
CRDT (Conflict-free Replicated Data Type)
- CRDT — структура данных, у которой операции либо коммутируют (op-based), либо объединяются через моноидные операции (state-based), что гарантирует детерминированное сходство без централизованного координирования. Гарантируется Strong Eventual Consistency (SEC): при отсутствии новых обновлений все реплики сходятся автоматически.
- Примеры для чата:
- Множество сообщений: OR‑Set (add с уникальным тегом, remove удаляет конкретные теги) — после слияния ни одно добавленное сообщение не потеряется, удаление корректно применяется к конкретным тегам.
- Упорядоченные последовательности (сообщения в чате): RGA, LSEQ, WOOT — CRDT для последовательностей сохраняют согласованный порядок вставок без центрального сервера, используя позиционные идентификаторы (например, пары $(timestamp,nodeId)$ или более сложные позиционные коды).
- Счётчики прочтений: G‑Counter или PN‑Counter для агрегатов (детерминированное слияние сумм).
Недостатки и нюансы CRDT/EC:
- Логика конфликтов в CRDT встроена заранее; не всегда подходит для сложных семантик (например, транзакций, банковских переводов).
- LWW (last‑write‑wins) прост, но теряет обновления при рассинхронизации (ненадёжно для важных данных).
- Некоторые CRDT (последовательности) сложны и могут требовать дополнительных метаданных (тёмбстоны, id’s), что увеличивает размер данных.
Практические рекомендации при проектировании чата
- Для обычного чата чаще выбирают AP + Eventual/causal consistency: низкая задержка, доступность важнее моментальной глобальной согласованности. Добавляют:
- Гарантии сессий: read‑your‑writes, monotonic reads — пользователь видит свои отправленные сообщения сразу.
- Краудсорсинг порядка: использовать causal+timestamps+clientId для детерминизма; или CRDT RGA для корректного порядка правок/вставок.
- Фоновые механизмы слияния (anti‑entropy), дедупликацию по уникальным id сообщений.
- Для критичных операций (платежи, права доступа) предпочитают CP: жёсткие кворумы, синхронная репликация, откат и транзакции.
Коротко: CAP говорит, что при разрыве сети нужно выбирать между консистентностью и доступностью. Для чата обычно выбирают доступность + слабую/каузальную согласованность (eventual, CRDT), чтобы обеспечить быстрый отклик и автоматическое слияние при восстановлении; для критичных данных выбирают консистентность и жертвуют доступностью.