В теоретической информатике , то теорема CAP , также названа теорема Брюэров после ученого Эрика Брюэра , заявляет , что это невозможно для распределенного хранилища данных для одновременного обеспечения более двух из трех следующих гарантий: [1] [2] [3 ]
- Согласованность : каждое чтение получает самую последнюю запись или ошибку
- Доступность : каждый запрос получает ответ (без ошибок), без гарантии, что он содержит самую последнюю запись.
- Допуск на разделение : система продолжает работать, несмотря на то, что произвольное количество сообщений отбрасывается (или задерживается) сетью между узлами.
Если происходит сбой сетевого раздела, следует ли нам решить
- Отмените операцию и тем самым уменьшите доступность, но обеспечьте согласованность
- Продолжить операцию и, таким образом, обеспечить доступность, но рисковать несогласованностью.
Теорема CAP подразумевает, что при наличии сетевого раздела нужно выбирать между согласованностью и доступностью. Обратите внимание, что согласованность, определенная в теореме CAP, сильно отличается от согласованности, гарантированной транзакциями базы данных ACID . [4]
Эрик Брюэр утверждает, что часто используемая концепция «два из трех» может вводить в заблуждение, потому что разработчикам системы нужно только пожертвовать согласованностью или доступностью при наличии разделов, а во многих системах разделы встречаются редко. [5] [6]
Объяснение
Ни одна распределенная система не застрахована от сетевых сбоев, поэтому обычно следует допускать разделение сети . [7] [8] При наличии раздела остается два варианта: согласованность или доступность . При выборе согласованности вместо доступности система вернет ошибку или тайм-аут, если нельзя гарантировать актуальность конкретной информации из-за разделения сети. При выборе доступности вместо согласованности система всегда будет обрабатывать запрос и пытаться вернуть самую последнюю доступную версию информации, даже если она не может гарантировать ее актуальность из-за разделения сети.
В отсутствие сбоя сети, то есть когда распределенная система работает нормально, можно обеспечить как доступность, так и согласованность.
CAP часто неправильно понимают, как будто каждый должен отказаться от одной из трех гарантий в любое время. Фактически, выбор действительно стоит между согласованностью и доступностью только тогда, когда происходит сетевой раздел или сбой; в остальное время не нужно идти на компромисс. [9] [10]
Системы баз данных, разработанные с учетом традиционных гарантий ACID, такие как РСУБД, предпочитают согласованность доступности, тогда как системы, разработанные на основе философии BASE , распространенной, например, в движении NoSQL , предпочитают доступность согласованности. [5]
Теорема PACELC основана на CAP, утверждая, что даже в отсутствие разделения происходит еще один компромисс между задержкой и согласованностью.
История
По словам специалиста по информатике из Беркли Эрика Брюэра из Калифорнийского университета , эта теорема впервые появилась осенью 1998 года. [5] Она была опубликована как принцип CAP в 1999 году [11] и представлена как гипотеза Брюэром на Симпозиуме 2000 года по принципам распределенного распределения. Вычислительная техника (PODC). [12] В 2002 году Сет Гилберт и Нэнси Линч из Массачусетского технологического института опубликовали формальное доказательство гипотезы Брюера, превратив ее в теорему . [1]
В 2012 году Брюэр разъяснил некоторые из своих позиций, в том числе почему часто используемая концепция «два из трех» может вводить в заблуждение, поскольку разработчикам систем нужно только пожертвовать согласованностью или доступностью при наличии разделов; существуют методы управления разделами и восстановления. Брюэр также отметил различное определение согласованности, используемое в теореме CAP, по сравнению с определением, используемым в ACID . [5] [6]
Похожая теорема, устанавливающая компромисс между согласованностью и доступностью в распределенных системах, была опубликована Бирманом и Фридманом в 1996 году. [13] Результат Бирмана и Фридмана ограничил эту нижнюю границу некоммутирующими операциями.
Технология Blockchain жертвует согласованностью ради доступности и устойчивости к разделам, но достигается за счет проверки между узлами с течением времени, в результате чего создается впечатление, что теорема недействительна. [14]
Смотрите также
- Заблуждения распределенных вычислений
- Теорема PACELC
- Paxos (информатика)
- Raft (информатика)
Рекомендации
- ^ a b Сет Гилберт и Нэнси Линч, «Гипотеза Брюера и возможность создания согласованных, доступных, устойчивых к разделам веб-сервисов» , Новости ACM SIGACT , том 33, выпуск 2 (2002), стр. 51–59. DOI : 10.1145 / 564585.564601 .
- ^ "Теорема Brewer's CAP" , julianbrowne.com, дата обращения 2 марта 2010 г.
- ^ "Теорема Брюерса CAP о распределенных системах" , royans.net
- ^ Liochon, Николя. «Запутанная формулировка CAP и ACID» . Это долгий пробег . Дата обращения 1 февраля 2019 .
- ^ a b c d Эрик Брюэр, «CAP двенадцать лет спустя: как изменились« правила »» , Компьютер , том 45, выпуск 2 (2012), стр. 23–29. DOI : 10,1109 / MC.2012.37 .
- ^ а б Карпентер, Джефф; Хьюитт, Эбен (июль 2016 г.). «Кассандра: Полное руководство, 2-е издание [книга]» . www.oreilly.com . Проверено 21 декабря 2020 .
В феврале 2012 года Эрик Брюэр представил обновленный взгляд на свою теорему CAP [...] Брюэр теперь описывает аксиому «2 из 3» как несколько вводящую в заблуждение. Он отмечает, что разработчикам нужно только пожертвовать согласованностью или доступностью при наличии разделов, и что прогресс в методах восстановления разделов позволил дизайнерам достичь высоких уровней согласованности и доступности.
- ^ Клеппманн, Мартин (18 сентября 2015 г.). «Критика теоремы CAP» . arXiv : 1509.05393 . Bibcode : 2015arXiv150905393K . DOI : 10.17863 / CAM.13083 . S2CID 1991487 . Проверено 24 ноября 2019 . Цитировать журнал требует
|journal=
( помощь ) - ^ Мартин, Клеппманн. «Пожалуйста, прекратите называть базы данных CP или AP» . Блог Мартина Клеппманна . Проверено 24 ноября 2019 .
- ^ «Лучшее объяснение теоремы CAP» . DZone Big Data . Проверено 2 сентября 2016 .
- ^ Абади, Даниэль (23 апреля 2010 г.). "DBMS Musings: Проблемы с CAP и малоизвестной системой NoSQL Yahoo" . СУБД Musings . Проверено 23 января 2018 .
- ^ Армандо Фокс и Эрик Брюэр, «Урожай, урожайность и масштабируемые устойчивые системы», Proc. Горячие темы 7-го семинара по операционным системам (HotOS 99) , IEEE CS, 1999, стр. 174–178. DOI : 10,1109 / HOTOS.1999.798396
- ^ Эрик Брюэр, "К надежным распределенным системам"
- ^ Кен Бирман и Рой Фридман, " Торговая согласованность для доступности в распределенных системах ", апрель 1996 г. hdl : 1813/7235 .
- ^ Башир, Имран. (2018). Освоение блокчейна . Бирмингем, Англия: Packt Publishing. п. 41. ISBN 978-1-78883-904-4 .
Внешние ссылки
- CAP Двенадцать лет спустя: как «правила» изменили статью Брюера 2012 года о CRDT (бесконфликтных реплицированных типах данных)
- Шпаннер, TrueTime и теорема CAP
- Критика теоремы CAP
- Пожалуйста, прекратите называть базы данных CP или сообщение в блоге AP Kleppmann в 2015 году, соответствующее публикации «Критика теоремы CAP»