CAP Theorem

CAP Theorem применима к распределенным системам, которые хранят данные. Распределенная система состоит из множества нод (серверов/компьютеров/узлов), которые могут взаимодействовать друг с другом. Сервера имеют шаренное состояние, которое реплицируется между нодами. Запросы на запись и на чтение от клиента могут приходить на разные ноды системы.

Теорема утверждает, что распределенная система не может одновременно обладать следующими тремя свойствами: consistency, availability и partition tolerance.

Consistency

Каждый запрос на чтение к распределенной системе возвращает самые последние, успешно записанные данные или ошибку, если consistency не может быть гарантирована.
Это значит, что все узлы/сервера в распределённой системе видят одни и те же данные в одно и то же время. Это позволяет всем клиентам, независимо от того, к какому серверу в распределённой системе, в конечном счёте, поступил запрос на чтение, видеть одни и те же данные.
Не нужно путать Consistency в CAP Theorem c Consistency в ACID.
В CAP теореме, Consistency относится к репликам данных, которые распределенны по разным серверам системы. В ACID под Consistency имеют ввиду то, что транзакции обязаны менять данные только в соотвествии с integrity constraints указанных на схеме данных (таблице и т.д.).

Например, у нас есть распределённая система, состоящая из двух серверов. Мы храним баланс банковского счёта в этой системе. Допустим, изначально баланс счёта составляет 100 долларов. Клиент может прочитать это значение с разных узлов и получить одно и то же консистентное значение — 100 долларов.

Теперь он снял 30 долларов. После завершения операции, значения баланса должны обновиться на всех репликах, иначе будет момент времени, когда клиент может считать неправильное состояние баланса.

В данном случае, после коммита операции снятия, значения обновились консистентно на всех репликах:

А в данном случае, есть момент, когда значение баланса не обновилось на второй ноде и клиент может его прочитать:

Availability

Availability означает, что каждый запрос на чтение или запись данных, полученный рабочей нодой, вернет результат. Каждая нода, которая не вышла из строя, должна вернуть результат за приемлемое время. Это не значит, что все ноды должны всегда работать. Нет. Ноды как раз могут выходить из строя. Но если запрос приходит на рабочую ноду, то мы гарантированно получим какой-то результат (не факт что правильный и самый свежий, это должна гарантировать Consistency). Если мы иногда возвращаем ошибку при приходе запроса на рабочий сервер (например, потому что там значение не корректное, устаревшее), то такая система не будет Available.

Partition tolerance

Partition tolerance означает, что система продолжит работать, даже если связь между нодами не работает/частично не работает/теряются пакеты/теряются сообщения.

На примере про баланс из Consistency - когда мы обновляем значение баланса со 100 до 70 долларов. Вначале, запрос на обновление баланса поступит на один из серверов, далее будут происходить обновления значения баланса на остальных нодах (синхронно или асинхронно). Для обновления значение баланса на остальных нодах, нам нужно иметь соединения через сеть между серверами. Но если сеть между серверами упала, то мы не сможем обновить значения на всех остальных нодах.
Далее, если в такой ситуации приходит запрос на чтение баланса, то если система partition tolerant, то она продолжит работу и вернет значения с ноды, даже если там не обновилось значение. Если она не partition tolerant, то она вернет ошибку.

Начальное состояние системы:

Далее у нас падает сеть:

И мы обновляем значение баланса, но не можем обновить на остальных репликах из-за отказа сети:

Далее клиент читает значение баланса с еще не обновленным значение. Если у нас система Partition tolerant и Available (нода не лежит, мы должны что-то вернуть), то мы вернем устаревшее значение:

Если система у нас не Partition Tolerant, то мы вернем ошибку. Если у нас система еще и Consistent, то у нас сама операция изменения баланса со 100 на 70 завершится ошибкой, если у нас сеть не работает.

Простое "доказательство" CAP теоремы.

На том же примере, давайте поймем, почему система не может одновременно удовлетворять всем трех характеристикам.
У нас имеется 2 сервера. Мы храним на них баланс банковского счета. Пусть сначала счет равен 100 и его значение было успешно реплицированно на оба сервера.
Далее мы обновляем баланс со 100 до 70. Этот запрос приходит на первый сервер. И пусть в этот момент у нас падает сеть.
В таком случае возможны следующие сценарии:

• Система не обновляет баланс ни на каком из серверов и возвращает ошибку. Но т.к. обе ноды доступны, то это противоречит понятию Availability. Т.е. в таком случае система не будет Available.
• Система, не фейлит запрос на обновление баланса. И меняет его с 100 на 70, но только на первом сервере. В таком случае, если мы разрешаем читать со второго сервера, то клиент прочитает устаревшее значение (100). Что делает систему не Consistent. Или же система не позволяет прочитать значение со второй ноды, что делает систему не Available.

Поэтому, на практике бывают 3 типа распределенных систем хранения данных:

CP (Consistent и Partition Tolerant)

Такие системы фейлят (возвращают ошибку) на запросы для чтения или обновления данных, если имеются проблемы сети между нодами.
Примерами таких баз являются: MongoDB, HBase, Redis.

AP (Available и Partition Tolerant)

Такие системы не фейлят запросы на чтение и запись данных, если имеются проблемы сети между нодами. Но они могут возвращать устаревшие данные.

Примеры таких баз: Amazon Dynamo DB, Cassandra, CouchDB

CA (Consistent и Available)

На практике систем, которые одновременно и Consistent и Available нет. Обычно, гарантируется одно из этих свойств. Например, мы хотим обновить значение в базе. Если у нас проблемы сети между репликами, то если мы не зафейлим запрос на обновление, то на сервере с репликой у нас будет устревшее значение. Тогда нам нельзя давать доступ к этим устаревшим данным. Но тогда система не будет Available.
Обычно, в таких случаях предпочитают Consistency, чем Availability.

Примеры таких баз - обычные реляционные базы, вроде, MySQL или PostgreSQL.