CAP теорема

CAP теорема обычно всплывает в обсуждении распределенных систем и звучит она так “Between consistency (C), availability (A) and partition tolerance (P) you can pick any two. It is impossible to achieve all three”. Обычно в такой формулировке не очень понятно, что такое вообще partition tolerance и что за система (CA) получится если мы от него откажемся? Для начала рассмотрим более детальные определения каждой части

  1. Consistency. Или согласованность. Если данные записаны на кластер, то все следующие чтения эти данные увидят. Самая сильная форма согласованности - данные по всему кластере одинаковые и их можно читать/писать с любой машины и результат будет всегда одинаковый.
  2. Availability. Кластер доступен даже если сколько-то машин выпало.
  3. Partition-tolerance. Кластер продолжает работать, даже если есть сетевая ошибка, которая разделит машины на две непустые группы, которые не могут общаться между собой.

С такими определениями становится совсем не понятно, что значит система в которой нет partition tolerance (CA). Есть другое определение P из оригинальной статьи: “In order to model partition tolerance, the network will be allowed to lose arbitrarily many messages sent from one node to another”. То есть P это не свойство кластера, а свойство сети, которое нельзя игнорировать. В таком случае CAP теорема должна звучать примерно так: в распределенной системе во время образования network partition можно либо потерять согласованность (потому что разрешаем апдейты на обе части кластера), либо потерять доступность (потому что выключаем кластер пока сетевая проблема не устранена).

Другими словами CA система - система в которой данные согласованы и кластер доступен пока не произойдет сетевой сбой (P). Если сбой произойдет то данные разъедутся и не восстановятся, когда сетевая проблема будет устранена. Работоспособной такая система может быть, если сетевых проблем не бывает, то есть когда система - большой монолитный объект, который если падает, то падает целиком. Но такая система по определению не является распределенной.

CP and AP

  1. CP. Данные согласованы по всем нодам. Если происходит P - кластер останавливает все операции, которые работали с данными, задетыми проблемой.
  2. AP. При P ноды остаются онлайн и синхронизируют данные позже, когда проблема будет решена. Не гарантируется, что на всех нодах будут те же данные (во время или даже после того как проблема устранена).

CP и AP системы асимметричны

  1. CP. Доступностью жертвуют только тогда, когда возникает проблема
  2. AP. Согласованностью жертвуют всегда. В лучше случае система может гарантировать только “eventual consistency”. В этом случае иногда система может вернуть данные отличные от только что записанных. Плюс клиенты, читающие данные по одному ключу, могут получать разные результаты. Может получится так, что часть апдейтов не доедет до всех реплик или в одну реплику приедут конфликтующие апдейты. Решение таких конфликтов остается на совести системы. Можно пытаться мержить такие апдейты, например, используя vector clock алгоритм, в кассандре это называется read repair.

Надо понимать, что в реальности согласованность и доступность не всегда полные. Например, HDFS, по умолчанию пишет в три ноды, если все они сломаются, то блок станет недоступным. Zookeeper отвечает на запись ОК, если больше половины кворума сказали ОК, он станет недоступным если выпадут больше половины машин.

Latency

Одна из проблема с CAP подходом состоит в том, что из рассмотрения выкинули задержки. Иногда распределенные системы жертвуют согласованностью не для того, чтобы улучшить доступность, а чтобы снизить время ответа. Например можно отказаться от согласованности в пользу так называемой “timeline consistency”, в этом случае реплики могут быть не согласованы между собой, но есть гарантия того, что апдейты будут применяться в одном порядке ко всем репликам.

Для гарантии согласованности надо, до того как ответить ОК на запись, убедится, что сколько-то реплик получили и применили это запись. На это нужно время. Если говорить ОК сразу после записи в мастер-реплику, а репликацию делать асинхронно - задержки уменьшатся. Но в этом случае пострадает и доступность, если выпала мастер-реплика для части данных, то эти данные становятся недоступны для обновления.

PACELC

Умные люди придумали альтернативу CAP, которая учитывает все выше перечисленное и облегчает понимание архитектуры распределенной системы.

PACELC — if there is a partition (P) how does the system trade off between availability and consistency (A and C); else (E) when the system is running as normal in the absence of partitions, how does the system trade off between latency (L) and consistency (C)?

Кассандра например PA/EL. Если есть P, то выбираем доступность. Если сетевых проблем нет - жертвуем согласованностью ради скорости.

ACID базы данных PC/EC. Если реплики не могут общаться - все записи запрещаются. Пока все реплики не скажут ОК, данные не запишутся - жертвуем скоростью.

References

Пост родился в попытках разобраться с сабжем и по сути является переработкой с переводом и компановкой следующих статей:

  1. http://dbmsmusings.blogspot.ru/2010/04/problems-with-cap-and-yahoos-little.html
  2. http://blog.cloudera.com/blog/2010/04/cap-confusion-problems-with-partition-tolerance/
  3. http://cacm.acm.org/blogs/blog-cacm/83396-errors-in-database-systems-eventual-consistency-and-the-cap-theorem/fulltext
  4. http://nathanmarz.com/blog/how-to-beat-the-cap-theorem.html
  5. http://stackoverflow.com/questions/12346326/nosql-cap-theorem-availability-and-partition-toleranc

Rodion's blog

put it on the cloud and kill it with fire
Tags
Connect