Теорема CAP - Википедия - CAP theorem

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

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

Если происходит сбой сетевого раздела, следует ли нам решить

  • Отмените операцию и тем самым уменьшите доступность, но обеспечьте согласованность
  • Продолжите операцию и тем самым обеспечьте доступность, но рискуйте несоответствием

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

Объяснение

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

В отсутствие сбоя сети, то есть когда распределенная система работает нормально, можно обеспечить как доступность, так и согласованность.

CAP часто понимают неправильно, как если бы человек всегда должен был отказаться от одной из трех гарантий. Фактически, выбор действительно стоит между согласованностью и доступностью только при возникновении сетевого раздела или сбоя; в остальное время не нужно идти на компромисс.[7][8]

Системы баз данных, разработанные с использованием традиционных КИСЛОТА гарантии в виду, такие как СУБД выберите последовательность над доступностью, тогда как системы, разработанные на ОСНОВАНИЕ философия, распространенная в NoSQL движение, например, выберите доступность, а не постоянство.[9]

В Теорема PACELC основан на CAP, утверждая, что даже в отсутствие разделения происходит еще один компромисс между задержкой и согласованностью.

История

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

В 2012 году Брюэр разъяснил некоторые из своих позиций, в том числе о том, почему часто используемая концепция «два из трех» может вводить в заблуждение или неправильно применяться, а также о том, что определение согласованности, используемое в CAP, отличается от того, которое используется в КИСЛОТА.[9]

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

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

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

  1. ^ а б Сет Гилберт и Нэнси Линч, «Гипотеза Брюера и возможность создания согласованных, доступных, устойчивых к разделам веб-сервисов», Новости ACM SIGACT, Том 33, выпуск 2 (2002), стр. 51–59. Дои:10.1145/564585.564601.
  2. ^ "Теорема Брюера CAP", julianbrowne.com, дата обращения 2 марта 2010 г.
  3. ^ "Теорема Брюерса ​​CAP о распределенных системах", royans.net
  4. ^ Лиохон, Николас. «Запутанная формулировка CAP и ACID». Этот долгий путь. Получено 1 февраля 2019.
  5. ^ Клеппманн, Мартин (18 сентября 2015 г.). «Критика теоремы CAP». arXiv:1509.05393. Bibcode:2015arXiv150905393K. Дои:10.17863 / CAM.13083. S2CID  1991487. Получено 24 ноября 2019. Цитировать журнал требует | журнал = (помощь)
  6. ^ Мартин, Клеппманн. «Пожалуйста, прекратите называть базы данных CP или AP». Блог Мартина Клеппманна. Получено 24 ноября 2019.
  7. ^ «Лучшее объяснение теоремы CAP». DZone Big Data. Получено 2016-09-02.
  8. ^ Абади, Даниэль (23 апреля 2010 г.). "DBMS Musings: проблемы с CAP и малоизвестной системой NoSQL Yahoo". СУБД Musings. Получено 2018-01-23.
  9. ^ а б c Эрик Брюэр, «CAP двенадцать лет спустя: как изменились« правила »», Компьютер, Том 45, Выпуск 2 (2012), стр. 23–29. Дои:10.1109 / MC.2012.37.
  10. ^ Армандо Фокс и Эрик Брюэр, «Урожай, урожайность и масштабируемые устойчивые системы», Proc. Горячие темы 7-го семинара по операционным системам (HotOS 99), IEEE CS, 1999, стр. 174–178. Дои:10.1109 / HOTOS.1999.798396
  11. ^ Эрик Брюэр, «На пути к надежным распределенным системам»
  12. ^ Кен Бирман и Рой Фридман "Торговая согласованность для доступности в распределенных системах ", Апрель 1996 г. HDL:1813/7235.

внешняя ссылка