stringtranslate.com

Теорема CAP

В теории баз данных теорема CAP , также называемая теоремой Брюэра в честь ученого-компьютерщика Эрика Брюэра , утверждает, что любое распределенное хранилище данных может предоставить только две из следующих трех гарантий: [1] [2] [3]

Последовательность
Каждое чтение получает самую последнюю запись или ошибку. Обратите внимание, что согласованность, как определено в теореме CAP, сильно отличается от согласованности, гарантированной в транзакциях базы данных ACID . [4]
Доступность
Каждый запрос, полученный исправным узлом в системе, должен привести к ответу. Это определение доступности в теореме CAP, как определено Гилбертом и Линчем. [1] Обратите внимание, что доступность, как определено в теореме CAP, отличается от высокой доступности в архитектуре программного обеспечения. [5]
Допуск раздела
Система продолжает работать, несмотря на произвольное количество сообщений, отброшенных (или задержанных) сетью между узлами.

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

Теорема CAP Диаграмма Эйлера

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

Объяснение

Ни одна распределенная система не застрахована от сетевых сбоев, поэтому сетевое разделение, как правило, приходится мириться. [7] [8] При наличии раздела остается два варианта: согласованность или доступность . При выборе согласованности вместо доступности система вернет ошибку или тайм-аут, если нельзя гарантировать актуальность определенной информации из-за сетевого разделения. При выборе доступности вместо согласованности система всегда будет обрабатывать запрос и пытаться вернуть самую последнюю доступную версию информации, даже если она не может гарантировать ее актуальность из-за сетевого разделения.

При отсутствии раздела могут быть удовлетворены как доступность, так и согласованность. [9]

Системы баз данных, разработанные с учетом традиционных гарантий ACID , такие как СУРБД, выбирают согласованность вместо доступности, тогда как системы, разработанные на основе философии BASE , распространенной, например, в движении NoSQL , выбирают доступность вместо согласованности. [10]

История

По словам Эрика Брюэра, специалиста по информатике из Калифорнийского университета в Беркли , теорема впервые появилась осенью 1998 года. [10] Она была опубликована как принцип CAP в 1999 году [11] и представлена ​​Брюэром в качестве гипотезы на Симпозиуме по принципам распределенных вычислений (PODC) 2000 года. [12] В 2002 году Сет Гилберт и Нэнси Линч из Массачусетского технологического института опубликовали формальное доказательство гипотезы Брюэра, сделав ее теоремой . [1]

В 2012 году Брюэр разъяснил некоторые из своих позиций, включая то, почему часто используемая концепция «два из трех» может быть несколько вводящей в заблуждение, поскольку разработчикам систем нужно жертвовать согласованностью или доступностью только при наличии разделов; существуют методы управления разделами и восстановления. Брюэр также отметил различное определение согласованности, используемое в теореме CAP, относительно определения, используемого в ACID . [10] [13]

Похожая теорема, устанавливающая компромисс между согласованностью и доступностью в распределенных системах, была опубликована Бирманом и Фридманом в 1996 году. [14] Результат Бирмана и Фридмана ограничил эту нижнюю границу некоммутирующими операциями.

Теорема PACELC , представленная в 2010 году, [9] основывается на CAP, утверждая, что даже при отсутствии разделения существует другой компромисс между задержкой и согласованностью. PACELC означает, что если происходит разделение (P), то компромисс заключается между доступностью (A) и согласованностью (C); в противном случае (E), то компромисс заключается между задержкой (L) и согласованностью (C). Некоторые эксперты, такие как Марк Брукер, утверждают, что теорема CAP особенно актуальна в периодически подключаемых средах, таких как те, которые связаны с Интернетом вещей (IoT) и мобильными приложениями . В этих контекстах устройства могут стать разделенными из-за сложных физических условий, таких как отключение электроэнергии или при входе в замкнутые пространства, такие как лифты. Для распределенных систем , таких как облачные приложения , более целесообразно использовать теорему PACELC , которая является более всеобъемлющей и учитывает компромиссы, такие как задержка и согласованность, даже при отсутствии сетевых разделов. [15]

Смотрите также

Ссылки

  1. ^ abc Гилберт, Сет; Линч, Нэнси (2002). «Гипотеза Брюера и осуществимость согласованных, доступных, устойчивых к разделам веб-сервисов». ACM SIGACT News . 33 (2). Ассоциация вычислительной техники (ACM): 51–59. doi :10.1145/564585.564601. ISSN  0163-5700. S2CID  15892169.
  2. ^ "Теорема Брюэра CAP". julianbrowne.com . 2009-01-11.
  3. ^ "Теорема Брюэрса CAP о распределенных системах". royans.net . 2010-02-14.
  4. ^ Лиошон, Николас. "Запутанная формулировка CAP и ACID". Этот длинный пробег . Получено 1 февраля 2019 г.
  5. ^ Фаулер, Адам (2015). NoSQL для чайников . Для чайников. ISBN 978-8126554904.
  6. ^ Фаулер, Адам (2015). NoSQL для чайников . Для чайников. ISBN 978-8126554904.
  7. ^ Клеппманн, Мартин (2015-09-18). Критика теоремы CAP (Отчет). Apollo - Репозиторий Кембриджского университета. arXiv : 1509.05393 . Bibcode :2015arXiv150905393K. doi :10.17863/CAM.13083. S2CID  1991487 . Получено 24 ноября 2019 г. .
  8. ^ Мартин, Клеппманн. «Пожалуйста, прекратите называть базы данных CP или AP». Блог Мартина Клеппманна . Получено 24 ноября 2019 г.
  9. ^ ab Abadi, Daniel (2010-04-23). ​​"DBMS Musings: Проблемы с CAP и малоизвестная система NoSQL от Yahoo". DBMS Musings . Получено 2018-01-23 .
  10. ^ abc Brewer, Eric (2012). «CAP двенадцать лет спустя: как изменились «правила»». Computer . 45 (2). Institute of Electrical and Electronics Engineers (IEEE): 23–29. doi :10.1109/mc.2012.37. ISSN  0018-9162. S2CID  890105.
  11. ^ Армандо Фокс; Эрик Брюэр (1999). Урожай, урожайность и масштабируемые толерантные системы . Труды 7-го семинара «Горячие темы в операционных системах» (HotOS 99). IEEE CS. стр. 174–178. doi :10.1109/HOTOS.1999.798396.
  12. ^ Эрик Брюэр. «На пути к надежным распределенным системам» (PDF) .
  13. ^ Карпентер, Джефф; Хьюитт, Эбен (июль 2016 г.). Cassandra: The Definitive Guide (2-е изд.). O'Reilly Media. ISBN 9781491933657. В феврале 2012 года Эрик Брюэр представил обновленную точку зрения на свою теорему CAP  ... Брюэр теперь описывает аксиому "2 из 3" как несколько вводящую в заблуждение. Он отмечает, что проектировщикам нужно жертвовать согласованностью или доступностью только при наличии разделов, и что достижения в методах восстановления разделов позволили проектировщикам достичь высоких уровней как согласованности, так и доступности.
  14. ^ Кен Бирман; Рой Фридман (апрель 1996 г.). «Торговля согласованностью ради доступности в распределенных системах». hdl :1813/7235.
  15. ^ Проектирование приложений с интенсивным использованием данных: Великие идеи, лежащие в основе надежных, масштабируемых и обслуживаемых систем . O'Reilly Media. ISBN 978-1449373320.