CAP-теорема

CAP-теорема – это утверждение о том, что в любой распределенной системе можно обеспечить выполнение только 2-х из 3-х следующих свойств:

1. Consistency (согласованность) – все узлы распределенной системы содержат актуальные и одинаковые данные в любой момент времени. Это свойство гарантирует, что любой запрос к системе вернет правильный и последний результат, независимо от того, к какому узлу он обращается.

2. Availability (доступность) – каждый запрос к системе возвращает результат. Без гарантий, что результат содержит последние данные. Даже если какие-то узлы выпали, система всё равно должна вернуть ответ.

3. Partition tolerance (устойчивость к разделению) – система продолжает работать даже при потере коммуникации между узлами. Например, если между двумя узлами отвалилась связь, то они продолжают работать независимо друг от друга.

Варианты сочетания свойств

Consistency + Availability

Все узлы системы имеют одинаковые и актуальные данные, и все запросы получают ответ. Такие системы возможны при поддержке ACID-требований к транзакциям (Атомарность, Согласованность, Изоляция, Долговечность) и абсолютной надежности сети. На практике таких решений почти не существует. Классическим примером CA-системы называют распределённую службу каталогов LDAP, а также реляционные базы данных (PostgreSQL, MySQL, MS SQL Server).

Consistency + Partition tolerance

Все узлы системы имеют одинаковые и актуальные данные, и система продолжает работать, даже если между узлами потеряно соединение. Однако, эти системы могут не отвечать на некоторые запросы. Устойчивость к разделению требует дублирования изменений во всех узлах системы. Примеры хранилищ данных: Apache HBase, MongoDB, Redis.

Availability + Partition tolerance

Все запросы получают ответ, и система продолжает работать, даже если между узлами потеряно соединение. Эти системы подходят для обработки данных, когда требуется высокая доступность, но можно претерпеть небольшие расхождения в данных. AP-система может быть представлена кластером из нескольких узлов, каждый из которых может принимать данные, но не обязуется в тот же момент распространять их на другие сервера. Примеры: CoucheDB, Cassandra, Amazon DynamoDB.

Так как де-факто в распределённых системах сеть может пропадать, приходится поддерживать устойчивость к разделению (P). Остаётся пойти на компромисс между согласованностью (C) и доступностью (A).

Применимость CAP-теоремы

Следует учитывать недостатки теоремы CAP. Большинство из них сводится к тому, что теорема CAP заставляет делать жесткий выбор между двумя из трех свойств, хотя на практике можно достичь различных компромиссов и гибридных решений. CAP не даёт метрик для измерения доступности или согласованности данных.

Основная ценность CAP-теоремы в том, что она поднимает вопрос о неизбежности компромиссов при проектировании распределённых систем. Необходимо осознанно выбирать, какие из принципов будут иметь приоритет, исходя из конкретных требований системы.

Статьи по теме

1. CAP-теорема: принципы согласованности, доступности и устойчивости
2. CAP-теорема простым, доступным языком
3. Несколько фактов о CAP-«теореме»
4. CAP двенадцать лет спустя: как изменились «правила»
5. Всё, что вы не знали о CAP теореме
6. Мифы о CAP теореме
7. Критика CAP-теоремы
8. Балансируем между консистентностью и доступностью в распределённой системе: опыт Tarantool

Видео

1. CAP теорема или теорема Брюера
2. Распределенные системы. CAP теорема и основные заблуждения
3. ACID требования, CAP-теорема, BASE архитектура
4. Обсуждение CAP-теоремы разработчиками