stringtranslate.com

Теорема CAP

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

Последовательность
Каждое чтение получает самую последнюю запись или ошибку.
Доступность
Каждый запрос получает ответ (без ошибок) без гарантии того, что он содержит самую последнюю запись.
Допуск раздела
Система продолжает работать, несмотря на то, что произвольное количество сообщений отбрасывается (или задерживается) сетью между узлами.

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

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

Таким образом, при наличии сетевого раздела приходится выбирать между согласованностью или доступностью. Обратите внимание, что согласованность, определенная в теореме CAP, сильно отличается от согласованности, гарантированной в транзакциях базы данных ACID . [4]

Объяснение

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

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

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

История

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

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

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

Теорема PACELC , представленная в 2010 году [7], основывается на CAP, утверждая, что даже при отсутствии разделения существует еще один компромисс между задержкой и согласованностью. PACELC означает, что если произойдет разделение (P), компромисс будет между доступностью (A) и согласованностью (C); В противном случае (E) приходится выбирать между задержкой (L) и согласованностью (C).

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

Рекомендации

  1. ^ аб Гилберт, Сет; Линч, Нэнси (2002). «Гипотеза Брюэра и возможность создания последовательных, доступных и устойчивых к разделению веб-сервисов». Новости ACM SIGACT . Ассоциация вычислительной техники (ACM). 33 (2): 51–59. дои : 10.1145/564585.564601. ISSN  0163-5700. S2CID  15892169.
  2. ^ "Теорема Брюера CAP" . www.julianbrowne.com . 11 января 2009 г.
  3. ^ "Теорема Брюэрса CAP о распределенных системах" . Роянс.нет . 14 февраля 2010 г.
  4. ^ Лиошон, Николас. «Сбивающая с толку формулировка CAP и ACID». Этот долгий путь . Проверено 1 февраля 2019 г.
  5. ^ Клеппманн, Мартин (18 сентября 2015 г.). Критика теоремы CAP (доклад). Apollo - Репозиторий Кембриджского университета. arXiv : 1509.05393 . Бибкод : 2015arXiv150905393K. дои : 10.17863/CAM.13083. S2CID  1991487 . Проверено 24 ноября 2019 г.
  6. ^ Мартин, Клеппманн. «Пожалуйста, прекратите звонить в базы данных CP или AP». Блог Мартина Клеппманна . Проверено 24 ноября 2019 г.
  7. ^ Аб Абади, Дэниел (23 апреля 2010 г.). «Размышления о СУБД: проблемы с CAP и малоизвестной системой NoSQL Yahoo». Размышления о СУБД . Проверено 23 января 2018 г.
  8. ^ abc Брюэр, Эрик (2012). «CAP двенадцать лет спустя: как изменились «правила». Компьютер . Институт инженеров по электротехнике и электронике (IEEE). 45 (2): 23–29. дои : 10.1109/mc.2012.37. ISSN  0018-9162. S2CID  890105.
  9. ^ Армандо Фокс; Эрик Брюэр (1999). Урожай, урожайность и масштабируемые толерантные системы . Учеб. 7-й семинар «Актуальные темы операционных систем» (HotOS 99). IEEE CS. стр. 174–178. дои : 10.1109/HOTOS.1999.798396.
  10. ^ Эрик Брюэр. «На пути к надежным распределенным системам» (PDF) .
  11. ^ Карпентер, Джефф; Хьюитт, Эбен (июль 2016 г.). Кассандра: Полное руководство (2-е изд.). Орейли. ISBN 9781491933657. В феврале 2012 года Эрик Брюэр представил обновленный взгляд на свою теорему CAP [...] Брюэр теперь описывает аксиому «2 из 3» как несколько вводящую в заблуждение. Он отмечает, что разработчикам нужно жертвовать согласованностью или доступностью только при наличии разделов, и что достижения в методах восстановления разделов позволили разработчикам достичь высоких уровней как согласованности, так и доступности.
  12. ^ Кен Бирман; Рой Фридман (апрель 1996 г.). «Торговая последовательность ради доступности в распределенных системах». hdl : 1813/7235.

Внешние ссылки