Фундаментальная концепция каждой распределенной базы данных

Что такое CAP-теорема?

Теорема CAP, также известная как теорема Брюера, была сформулирована Э. Брюэром на Симпозиуме по принципам распределенных вычислений в 2000 г. Двумя годами позже С. Гилберт и Н. А. Линч опубликовали формальное доказательство [3].

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

В итоге это дает нам три возможных комбинации дизайна системы:

  • CA Systems (непротиворечивость и доступность без допусков на разделы)
  • Системы CP (непротиворечивость и устойчивость к разделам без доступности)
  • Системы AP (доступность и устойчивость к разделам без согласованности)

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

Последовательность

В соответствии с этой гарантией непротиворечивости должен существовать общий порядок всех операций, чтобы каждая операция выглядела так, как если бы она была завершена в одном экземпляре. [3]

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

Кроме того, не следует путать его с определением согласованности из гарантий ACID.

Доступность

Каждый запрос, полученный исправным узлом в системе, должен привести к ответу. [3]

Обратите внимание, что доступность в формализации теоремы не полностью соответствует первоначальному предложению Фокса и Брюера о принципах CAP. Определение теоремы требует полной доступности, а это означает, что любой исправный узел должен иметь возможность генерировать действительные ответы [6].

Допуск перегородки

Сети будет позволено потерять произвольное количество сообщений, отправленных с одного узла на другой. [3]

По сути, это означает, что наша система должна работать правильно, даже если все сообщения между узлами потеряны.

Практическое значение

Распространенная и вводящая в заблуждение интерпретация теоремы CAP гласит, что мы можем выбрать любые две из этих трех желаемых характеристик в зависимости от наших потребностей. Однако в реальной жизни сетевые разделы неизбежны, и вы не можете использовать системы CA в распределенной среде. Иногда вы можете найти некоторые реляционные базы данных, такие как PostgreSQL или MySQL, в качестве примеров систем CA, но это верно только тогда, когда используется конфигурация с одним экземпляром, а это означает, что вы в основном отбрасываете распределенный характер теоремы CAP, что делает ее практически бесполезна с практической точки зрения.

Для иллюстрации следствия теоремы рассмотрим следующий пример. Представьте себе примитивную систему, состоящую из двух узлов: основного узла и его реплики. Вначале оба узла синхронизированы, и система находится в согласованном состоянии.Клиент, который может быть реальным пользователем или другим узлом, обновляет значение с v1 до версия 2.

В идеальном мире все работает хорошо, а наша система остается доступной и согласованной. Более того, чем надежнее сеть, тем выше доля времени, когда наша система может гарантировать оба свойства. Но что произойдет, если на 3-м или 4-м шаге произойдет сетевой раздел?

Теперь первичный узел не знает фактического состояния реплики, поскольку проблема может возникнуть на 3-м или 4-м шаге. Значение может быть v1, что делает нашу систему несогласованной, или v2, что означает, что наш основной узел не получил подтверждения после успешного обновления.

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

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

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

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

В общем, есть три возможных варианта, из которых можно выбрать:

Лучшая доступность

Мы фиксируем линеаризуемость и пытаемся добиться максимально возможной доступности.

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

Постоянство лучших усилий

Мы фиксируем общую доступность и пытаемся добиться максимально возможной согласованности.

Apache Cassandra — классический пример, но его можно настроить с помощью коэффициента репликации и уровня согласованности.

Жертвовать обоими

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

Кроме того, классификация, основанная исключительно на теореме CAP, очень ограничена и может ввести в заблуждение, поскольку многие современные базы данных очень гибки и попадают в разные категории в зависимости от применяемой конфигурации. Задача архитектора — найти оптимальный компромисс для каждой системы и варианта использования.

Краткое содержание

По словам Э. Брюера, цель первоначальной теоремы состояла в том, чтобы спровоцировать дискуссию и дальнейшие исследования, а не установить строгие правила и границы. Несомненно, с этой точки зрения цель была достигнута, и теорема CAP сыграла свою роль в развитии информатики, побудив многих инженеров и ученых исследовать новые подходы к проектированию распределенных систем.

Однако не следует переоценивать практическое значение теоремы [6]. На сегодняшний день существует множество более глубоких и практических исследований ограничений в распределенных системах [5]. Кроме того, в своей классической формализации теорема CAP игнорирует задержку, которая рассматривается в теореме PACELC [7].

Если вам понравилась эта статья, пожалуйста, подпишитесь на меня здесь, на Medium, чтобы увидеть больше историй.

[1] А. Фокс и Э. А. Брюэр, «Урожай, доходность и масштабируемые толерантные системы», Материалы седьмого семинара по актуальным темам в операционных системах, Рио-Рико, Аризона, США, 1999, стр. 174–178, doi: 10.1109/ХОТОС.1999.798396.

[2] Э. Брюэр, «CAP двенадцать лет спустя: как изменились «правила»», Computer, vol. 45, нет. 2, стр. 23–29, февраль 2012 г., doi: 10.1109/MC.2012.37.

[3] С. Гилберт и Н. Линч, «Гипотеза Брюера и возможность создания согласованных, доступных, устойчивых к разделам веб-сервисов», ACM SIGACT News, 33 (2), стр. 51–59, июнь 2002 г., doi: 10.1145/564585.564601.

[4] С. Гилберт и Н. Линч, «Взгляды на теорему CAP», в Computer, vol. 45, нет. 2, стр. 30–36, февраль 2012 г., doi: 10.1109/MC.2011.389.

[5] Х. Аттия, Ф. Эллен и А. Моррисон, «Ограничения высокодоступных в конечном счете согласованных хранилищ данных», IEEE Transactions on Parallel and Distributed Systems, vol. 28, нет. 1, стр. 141–155, январь 2017 г., doi: 10.1109/TPDS.2016.2556669.

[6] М. Клеппманн, «Критика теоремы CAP», CoRR, сентябрь 2015 г., arXiv:1509.05393.

[7] Д. Абади, «Компромисс согласованности в современном дизайне системы распределенных баз данных: CAP — это только часть истории», Computer, vol. 45, нет. 2, стр. 37–42, февраль 2012 г., doi: 10.1109/MC.2012.33.