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