Cap theorem теорема брюера

admin

From Wikipedia, the free encyclopedia

In theoretical computer science, the CAP theorem, also named Brewer’s theorem after computer scientist Eric Brewer, states that any distributed data store can provide only two of the following three guarantees:[1][2][3]

Consistency
Every read receives the most recent write or an error.
Availability
Every request receives a (non-error) response, without the guarantee that it contains the most recent write.
Partition tolerance
The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes.

When a network partition failure happens, it must be decided whether to do one of the following:

  • cancel the operation and thus decrease the availability but ensure consistency
  • proceed with the operation and thus provide availability but risk inconsistency.

Thus, if there is a network partition, one has to choose between consistency or availability. Note that consistency as defined in the CAP theorem is quite different from the consistency guaranteed in ACID database transactions.[4]

Eric Brewer argues that the often-used «two out of three» concept can be somewhat misleading because system designers need only to sacrifice consistency or availability in the presence of partitions, but that in many systems partitions are rare.[5][6]

Explanation[edit]

No distributed system is safe from network failures, thus network partitioning generally has to be tolerated.[7][8] In the presence of a partition, one is then left with two options: consistency or availability. When choosing consistency over availability, the system will return an error or a time out if particular information cannot be guaranteed to be up to date due to network partitioning. When choosing availability over consistency, the system will always process the query and try to return the most recent available version of the information, even if it cannot guarantee it is up to date due to network partitioning.

In the absence of a partition, both availability and consistency can be satisfied.[9]

Database systems designed with traditional ACID guarantees in mind such as RDBMS choose consistency over availability, whereas systems designed around the BASE philosophy, common in the NoSQL movement for example, choose availability over consistency.[5]

History[edit]

According to University of California, Berkeley computer scientist Eric Brewer, the theorem first appeared in autumn 1998.[5] It was published as the CAP principle in 1999[10] and presented as a conjecture by Brewer at the 2000 Symposium on Principles of Distributed Computing (PODC).[11] In 2002, Seth Gilbert and Nancy Lynch of MIT published a formal proof of Brewer’s conjecture, rendering it a theorem.[1]

In 2012, Brewer clarified some of his positions, including why the often-used «two out of three» concept can be somewhat misleading because system designers only need to sacrifice consistency or availability in the presence of partitions; partition management and recovery techniques exist. Brewer also noted the different definition of consistency used in the CAP theorem relative to the definition used in ACID.[5][6]

A similar theorem stating the trade-off between consistency and availability in distributed systems was published by Birman and Friedman in 1996.[12] Birman and Friedman’s result restricted this lower bound to non-commuting operations.

The PACELC theorem, introduced in 2010,[9] builds on CAP by stating that even in the absence of partitioning, there is another trade-off between latency and consistency. PACELC means, if partition (P) happens, the trade-off is between availability (A) and consistency (C); Else (E), the trade-off is between latency (L) and consistency (C).

Blockchain technology often sacrifices immediate consistency for availability and partition tolerance. By requiring a specific number of «confirmations», Blockchain consensus algorithms are basically reduced to eventual consistency. [13]

See also[edit]

  • Fallacies of distributed computing
  • PACELC theorem
  • Paxos (computer science)
  • Raft (computer science)
  • Zooko’s triangle

References[edit]

  1. ^ a b Seth Gilbert and Nancy Lynch, «Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services», ACM SIGACT News, Volume 33 Issue 2 (2002), pg. 51–59. doi:10.1145/564585.564601.
  2. ^ «Brewer’s CAP Theorem», julianbrowne.com, Retrieved 02-Mar-2010
  3. ^ «Brewers CAP theorem on distributed systems», royans.net
  4. ^ Liochon, Nicolas. «The confusing CAP and ACID wording». This long run. Retrieved 1 February 2019.
  5. ^ a b c d Eric Brewer, «CAP twelve years later: How the ‘rules’ have changed», Computer, Volume 45, Issue 2 (2012), pg. 23–29. doi:10.1109/MC.2012.37.
  6. ^ a b Carpenter, Jeff; Hewitt, Eben (July 2016). «Cassandra: The Definitive Guide, 2nd Edition [Book]». www.oreilly.com. Archived from the original on 2020-08-07. Retrieved 2020-12-21. In February 2012, Eric Brewer provided an updated perspective on his CAP theorem [..] Brewer now describes the «2 out of 3» axiom as somewhat misleading. He notes that designers only need sacrifice consistency or availability in the presence of partitions, and that advances in partition recovery techniques have made it possible for designers to achieve high levels of both consistency and availability.
  7. ^ Kleppmann, Martin (2015-09-18). «A Critique of the CAP Theorem». Apollo — University of Cambridge Repository. arXiv:1509.05393. Bibcode:2015arXiv150905393K. doi:10.17863/CAM.13083. S2CID 1991487. Retrieved 24 November 2019.
  8. ^ Martin, Kleppmann. «Please stop calling databases CP or AP». Martin Kleppmann’s Blog. Retrieved 24 November 2019.
  9. ^ a b Abadi, Daniel (2010-04-23). «DBMS Musings: Problems with CAP, and Yahoo’s little known NoSQL system». DBMS Musings. Retrieved 2018-01-23.
  10. ^ Armando Fox and Eric Brewer, «Harvest, Yield and Scalable Tolerant Systems», Proc. 7th Workshop Hot Topics in Operating Systems (HotOS 99), IEEE CS, 1999, pg. 174–178. doi:10.1109/HOTOS.1999.798396
  11. ^ Eric Brewer, «Towards Robust Distributed Systems»
  12. ^ Ken Birman and Roy Friedman, «Trading Consistency for Availability in Distributed Systems», April 1996. hdl:1813/7235.
  13. ^ Bashir, Imran. (2018). Mastering blockchain. Birmingham, England: Packt Publishing. p. 41. ISBN 978-1-78883-904-4.

External links[edit]

  • CAP Twelve Years Later: How the «Rules» Have Changed Brewer’s 2012 article on conflict-free replicated data types (CRDT)
  • Spanner, TrueTime and the CAP Theorem
  • A Critique of the CAP Theorem
  • Please stop calling databases CP or AP Kleppmann’s 2015 blog post corresponding with the publication of «A Critique of the CAP Theorem»
Источник

По большей части эта статья — изложение сути статьи «Brewer’s CAP Theorem» Джулиана Брауна. В оригинале много полезных ссылок и интересных примеров, поэтому если позволяет время и знание языка, почитайте его. А здесь у меня просто самая суть, покороче и по-русски.

В 2000 году Эрик Брюер выдвинул гипотезу, касающуюся ключевых свойств распределённых систем, которую затем доказали в MIT, и с тех пор она называется теоремой Брюера или теоремой CAP (Consistency-Availability-Partition tolerance). Вольная формулировка:

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

Что это за свойства.

Корректность (Consistency)

Говорит о том, что система всегда выдаёт только логически непротиворечивые ответы. То есть не бывает такого, что вы добавили в корзину товар, а после рефреша страницы его там не видите.

Доступность (Availability)

Означает, что сервис отвечает на запросы, а не выдаёт ошибки о том, что он недоступен.

Устойчивость к сбоям сети (Partition tolerance)

Означает, что распределённая по кластеру система работает в расчёте на случаи произвольной потери пакетов внутри сети.

Для лучшего осознания, вот три соответствующих примера того, что могут представлять собой системы без одного из этих свойств:

+Availability +Consistency -Parition tolerance

Система, которая рассчитывает на то, что сеть абсолютно надёжна, и благодаря этому может обеспечить консистентность данных на всех живых узлах. Или, в вырожденном случае, система из одного узла, где неконсистентности быть не может, и которая доступна всегда, когда доступен её узел. Другими словами, на практике таких систем или не существует, или они не являются распределёнными (см. также).

+Consistency +Partition tolerance -Availability

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

+Availability +Partition tolerance -Consistency

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

Важность того, что невозможность обеспечить все три свойства сразу, доказана математически, избавляет нас (тупых инженеро́в 🙂 ) от тщетных попыток создать некую идеальную систему, которая никогда-никогда не ломается. Вместо этого мы теперь можем делать привычный нам инженерный выбор двух из трёх.

Как в известном предложении клиенту: «быстро, дёшево, качественно — выбирайте любые два».

Причём, как в большинстве инженерных ситуаций, этот выбор не стоит как «всё или ничего». Система может располагаться где угодно в пределах этого воображаемого треугольника, быть «более» консистентной, «менее» доступной и «слегка» нецелой. В анти-идеале можно написать систему, у которой будет плохо со всеми тремя компонентами. Уверен, вы с такими встречались :-).

Одно из интересных практических следствий этой теоремы в том, что в последнее время многие бизнесы решили для себя, что совсем не обязательно упираться в принципы дизайна ACID, который ставит во главу угла Consistency, жертвуя двумя другими свойствами. Теперь у нас есть такая альтернатива, как BASE (известная также как «eventual consistency»), которую например очень любят и используют в Amazon. Там во главе угла стоит Availability.

А ещё один дядька — Гай Пардон — вообще предлагает инженерное решение, которое обходит проблему CAP. Правда, он немного читерствует (с математикой трудно спорить), говоря, что хоть и нельзя обеспечить все три свойства одновременно, можно построить систему так, чтобы она достигала желаемого постепенно.

P.S. Андрей, спасибо за давешнюю ссылку на описание BASE.

Источник

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

Содержание

  1. Что такое теорема CAP?
  2. Доказательство теоремы CAP
  3. Объяснение согласованности, доступности и допустимости разделов
  4. Последовательность
  5. Доступность
  6. Допуск на разделение
  7. CAP-теорема NoSQL базы данных
  8. Базы данных CA
  9. Базы данных CP
  10. Базы данных AP
  11. Теорема CAP и микросервисы
  12. Подведение итогов и следующие шаги

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

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

Распределенная система — это совокупность компьютеров, которые работают вместе, образуя единый компьютер для конечных пользователей. Все распределенные машины имеют одно общее состояние и работают одновременно. В распределенных системах пользователи должны иметь возможность связываться с любой из распределенных машин, не зная, что это только одна машина. Сеть распределенной системы хранит свои данные не только на одном узле, но и на нескольких физических или виртуальных машинах одновременно.

Доказательство теоремы CAP

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

Распределенная система действует как обычный регистр со значением переменной X. Произошел сетевой сбой, который приводит к разделению сети между двумя узлами в системе. Конечный пользователь выполняет запрос записи, а затем запрос чтения. Давайте рассмотрим случай, когда каждый запрос обрабатывает другой узел системы. В этом случае у нашей системы есть два варианта:

  • Может выйти из строя по одному из запросов, нарушив доступность системы
  • Он может выполнять оба запроса, возвращая устаревшее значение из запроса на чтение и нарушая согласованность системы.

Система не может успешно обработать оба запроса, одновременно гарантируя, что чтение возвращает последнее значение, записанное при записи. Это связано с тем, что результаты операции записи не могут быть переданы с узла A на узел B из-за сетевого раздела.

Объяснение согласованности, доступности и допустимости разделов

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

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

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

Доступность

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

Допуск на разделение

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

CAP-теорема NoSQL базы данных

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

Базы данных CA

Базы данных CA обеспечивают согласованность и доступность на всех узлах. К сожалению, базы данных CA не могут обеспечить отказоустойчивость. В любой распределенной системе разделы неизбежны, а это означает, что этот тип базы данных не очень практичный выбор. При этом вы все равно можете найти базу данных CA, если она вам нужна. Некоторые реляционные базы данных, такие как PostgreSQL, обеспечивают согласованность и доступность. Вы можете развернуть их на узлах с помощью репликации.

Базы данных CP

Базы данных CP обеспечивают согласованность и устойчивость к разделам, но не доступность. Когда происходит разделение, система должна отключить несогласованные узлы, пока раздел не будет исправлен. MongoDB — это пример базы данных CP. Это система управления базами данных (СУБД) NoSQL, которая использует документы для хранения данных. Считается, что он не имеет схемы, что означает, что для него не требуется определенная схема базы данных. Он обычно используется в больших данных и приложениях, работающих в разных местах. Система CP структурирована так, что есть только один первичный узел, который получает все запросы на запись в данном наборе реплик. Вторичные узлы реплицируют данные в первичных узлах, поэтому в случае отказа первичного узла вторичный узел может заменить.

Базы данных AP

Базы данных AP обеспечивают доступность и устойчивость к разделам, но не согласованность. В случае раздела доступны все узлы, но не все они обновлены. Например, если пользователь пытается получить доступ к данным с неисправного узла, он не получит самую последнюю версию данных. Когда раздел в конечном итоге будет разрешен, большинство баз данных AP синхронизируют узлы для обеспечения согласованности между ними. Apache Cassandra — это пример базы данных AP. Это база данных NoSQL без первичного узла, что означает, что все узлы остаются доступными. Cassandra обеспечивает возможную согласованность, потому что пользователи могут повторно синхронизировать свои данные сразу после разрешения раздела.

Теорема CAP и микросервисы

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

Подведение итогов и следующие шаги

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

  • Распределенные хранилища данных
  • Алгоритмы распределенной системы
  • Атомарность
Источник

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *