Lt304888.ru

Туристические услуги

Теорема CAP

15-04-2023

Теорема CAP (известная также как теорема Брюера), в информатике — эвристическое утверждение о том, что в любой реализации распределённых вычислений возможно обеспечить не более двух из трёх следующих свойств:

  • согласованность данных (англ. consistency) — во всех вычислительных узлах в один момент времени данные не противоречат друг другу;
  • доступность (англ. availability) — любой запрос к распределённой системе завершается корректным откликом;
  • устойчивость к разделению (англ. partition tolerance) — расщепление распределённой системы на несколько изолированных секций не приводит к некорректности отклика от каждой из секций.

Акроним CAP в наименовании теоремы сформирован из первых букв английских наименований этих трёх свойств.

Принцип был предложен профессором Калифорнийского университета в Беркли Эриком Брюером в июле 2000 года[1][2] и впоследствии получил широкую популярность и признание в среде специалистов по распределённым вычислениям[3][4]. Концепция NoSQL, в рамках которой создаются распределённые нетранзакционные системы управления базами данных, зачастую использует этот принцип в качестве обоснования неизбежности отказа от согласованности данных[5][6][7]. Однако, многими учёными[8] и практиками[9] теорема CAP критикуется за вольность трактовки и даже недостоверность в том смысле, в котором она распространена в сообществе.

Содержание

Обоснования

В 2002 году Сет Джилберт и Нэнси Линч из Массачусетского технологического института подобрали формальные модели асинхронных и синхронных распределённых вычислений, в рамках которых показано выполнение теоремы CAP в условиях отсутствия синхронизации (общих часов) у узлов распределённой системы и принципиальную возможность компромисса в частично синхронных системах[10]. В этой работе «согласованность» в смысле теоремы CAP соотнесена с выполнением первых двух требований ACID — атомарности и согласованности. В дальнейшем, многие практики ссылались на данную работу как на доказательство теоремы CAP[4][11][3].


Следствия

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

CA

Система, во всех узлах которой данные согласованы и обеспечена доступность, жертвует устойчивостью к распаду на секции. Такие системы возможны на основе технологического программного обеспечения, поддерживающего транзакционность в смысле ACID. Примерами таких систем могут быть решения на основе кластерных систем управления базами данных или распределённая служба каталогов LDAP[12].

CP

Распределённая система, в каждый момент обеспечивающая целостный результат и способная функционировать в условиях распада, в ущерб доступности может не выдавать отклик. Устойчивость к распаду на секции требует обеспечения дублирования изменений во всех узлах системы, в этой связи отмечается практическая целесообразность использования в таких системах распределённых пессимистических блокировок для сохранения целостности[13].

AP

Распределённая система, отказывающаяся от целостности результата. Хотя системы такого рода известны задолго до формулировки принципа CAP (например, распределённые веб-кэши или DNS)[14], рост популярности систем с этим набором свойств связывается именно с распространением теоремы CAP. Так, большинство NoSQL-систем принципиально не гарантируют целостности данных, и ссылаются на теорему CAP как на мотив такого ограничения[5]. Задачей при построении AP-систем становится обеспечение некоторого практически целесообразного уровня целостности данных, в этом смысле про AP-системы говорят как о «целостных в конечном итоге» (англ. eventually consistent)[15] или как о «слабо целостных» (англ. weak consistent)[16].

BASE-архитектура

Во второй половине 2000-х годов сформулирован подход к построению распределённых систем, в которых требования целостности и доступности выполнены не в полной мере, названый акронимом BASE (от англ. Basically Available, Soft-state, Eventually consistent — базовая доступность, неустойчивое состояние, согласованность в конечном счёте), при этом такой подход напрямую противопоставляется ACID[17]. Под базовой доступностью подразумевается такой подход к проектированию приложения, чтобы сбой в некоторых узлах приводил к отказу в обслуживании только для незначительной части сессий при сохранении доступности в большинстве случаев[18]. Неустойчивое состояние подразумевает возможность жертвовать долговременным хранением состояния сессий (таких как промежуточные результаты выборок, информация о навигации, контексте), при этом концентрируясь на фиксации обновлений только критичных операций. Согласованности в конечном счёте (англ. Eventual consistency), трактующейся как возможность противоречивости данных в некоторых случаях, но при обеспечении согласования в практически обозримое время, посвящено значительное количество самостоятельных исследований[19][20].

Критика

См. также

Примечания

  1. ↑ Brewer, 2000
  2. ↑ Gilbert, Lynch, 2002, At PODC 2000, Brewer, in an invited talk, made the following conjecture: it is impossible for a web service to provide the following three guarantees: • Consistency • Availability • Partition-tolerance
  3. ↑ White Paper Beating the CAP Theorem  (англ.) (Архивировано из первоисточника 1 августа 2012. Проверено 7 июня 2011.
  4. ↑ Brewer’s CAP Theorem  (англ.) (11 January 2009). Архивировано из первоисточника 1 августа 2012. Проверено 7 июня 2011.
  5. ↑ 1 2 Brewer, 2010, Designers of wide-area systems, in which network partitions are considered inevitable, know they cannot have both availability and consistency, and thus can now justify weaker consistency. The rise of the “NoSQL” movement (“Not Only SQL”) is an expression of this freedom
  6. ↑ Rys, 2011, p. 49
  7. ↑ Кузнецов, 2011, Более серьёзным “теоретическим” основанием NoSQL-разработок, в которых общепринятые полезные свойства систем управления данными приносятся в жертву доступности этих систем, является так называемая “теорема CAP”, впервые сформулированная Эриком Брювером
  8. ↑ Кузнецов, 2011, я заключаю слово теорема в кавычки, поскольку утверждение, названное Брювером теоремой, таковым я признать не могу из-за отсутствия какой-либо чёткой и хотя бы немного формальной постановки задачи … но широко распространено мнение, что она означает невозможность поддержки в одной распределенной системе управления данных свойств согласованности данных (Consistency), доступности (Availability) и устойчивости к разделению сети (Partitioning)
  9. ↑ Rys, 2011, So why are many of the leading social networking sites (Facebook, MySpace, Twitter), e-commerce Web sites (hotel reservation systems and shopping sites), and large banking applications still implemented using traditional database systems such as MySQL (Facebook, Twitter) or SQL Server (MySpace, Choice Hotels International, Bank Itau) instead of using the new NoSQL systems? … The high-level answer is that the application architecture is still weighing the same trade-offs required by the CAP theorem
  10. ↑ Gilbert, Lynch, 2002, In an asynchronous model, when no clocks are available, the impossibility result is fairly strong: it is impossible to provide consistent data, even allowing stale data to be returned when messages are lost. However in partially synchronous models it is possible to achieve a practical compromise between consistency and availability
  11. ↑ Grigorik, 2010, Problem is, the CAP theorem proposed by Eric Brewer and later proved by Seth Gilbert and Nancy Lynch, shows that together, these three requirements are impossible to achieve at the same time
  12. ↑ Carter, 2011, Some CA systems include: single site databases, cluster databases and LDAP
  13. ↑ Демидов, 2010, CP (отказы обслуживания) – это подход с наличием дублирования, строгой ACID непротиворечивостью и синхронной репликацией изменений с применением метода пессимистических блокировок
  14. ↑ Carter, 2011, Some AP Systems include: Web caching systems and the Domain Name System (DNS)
  15. ↑ Carter, 2010, Eventual consistency – performing a read operation may give stale data to the client, but all writes will eventually propagate through the entire system
  16. ↑ Grigorik, 2010, CAP Implies Weak Consistency
  17. ↑ Pritchett, 2008, If ACID provides the consistency choice for partitioned databases, then how do you achieve availability instead? One answer is BASE (basically available, soft state, eventually consistent). BASE is diametrically opposed to ACID
  18. ↑ Pritchett, 2008, The availability of BASE is achieved through supporting partial failures without total system failure. Here is a simple example: if users are partitioned across five database servers, BASE design encourages crafting operations in such a way that a user database failure impacts only the 20 percent of the users on that particular host
  19. ↑ Стоунбрейкер, 2010
  20. ↑ Vogels, 2008

Литература

  • Brewer, Eric A. Towards robust distributed systems (англ.) // Proceedings of the XIX annual ACM symposium on Principles of distributed computing. — 10.1145/343477.343502
  • Brewer, Eric A. A Certain Freedom: Thoughts on the CAP Theorem (англ.) // Proceeding of the XXIX ACM SIGACT-SIGOPS symposium on Principles of distributed computing. — N. Y.: 10.1145/1835698.1835701
  • Carter, Andrew The CAP Theorem as it Applies to Contemporary NoSQL Storage Systems  (англ.). Memorial University (22 May 2011). Проверено 11 июня 2011.
  • Демидов А.А. Проектирование распределённых систем обработки объектных структур данных (рус.) // Труды XII конференции RCDL. — Казань: Казанский государственный университет, 2010. — В. 12. — С. 441-447.
  • Gilbert, Seth and Lynch, Nancy Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services (англ.) // ACM SIGACT News. — 0163-5700. — 10.1145/564585.564601
  • Grigorik, Ilya Weak Consistency and CAP Implications  (англ.). Igvita (24 June 2010). Архивировано из первоисточника 14 мая 2012. Проверено 11 июня 2011.
  • Кузнецов, Сергей MapReduce: внутри, снаружи или сбоку от параллельных СУБД? (рус.) // Труды Института системного программирования РАН. — М.: 2079-8156.
  • Кузнецов, Сергей Транзакционные параллельные СУБД: новая волна (рус.) // Труды Института системного программирования РАН. — М.: 2079-8156.
  • Pritchett, Dan BASE: An Acid Alternative (англ.) // ACM Queue. — N. Y.: 1542-7730. — 10.1145/1394127.1394128
  • Rys, Michael Scalable SQL. How do large-scale sites and applications remain SQL-based? (англ.) // 0001-0782. — 10.1145/1953122.1953141
  • Ошибки в системах баз данных, согласованность "в конечном счете" и теорема CAP  (рус.). Citforum (19 мая 2010). Проверено 4 июня 2011.
  • Stonebraker, Michael and Cattel, Rick Scalable SQL. How do large-scale sites and applications remain SQL-based? (англ.) // 0001-0782. — 10.1145/1953122.1953144
  • Vogels, Werner Eventually Consistent (англ.) // ACM Queue. — N. Y.: 1542-7730. — 10.1145/1466443.1466448


Это заготовка статьи по информатике. Вы можете помочь проекту, исправив и дополнив её.

Теорема CAP.

© 2020–2023 lt304888.ru, Россия, Волжский, ул. Больничная 49, +7 (8443) 85-29-01