В теоретической информатике теорема CAP , также называемая теоремой Брюера в честь ученого-компьютерщика Эрика Брюэра , утверждает, что любое распределенное хранилище данных может обеспечить только две из следующих трех гарантий: [1] [2] [3]
При возникновении сбоя сетевого раздела необходимо решить, следует ли выполнять одно из следующих действий:
Таким образом, при наличии сетевого раздела приходится выбирать между согласованностью или доступностью. Обратите внимание, что согласованность, определенная в теореме 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).
В феврале 2012 года Эрик Брюэр представил обновленный взгляд на свою теорему CAP [...] Брюэр теперь описывает аксиому «2 из 3» как несколько вводящую в заблуждение. Он отмечает, что разработчикам нужно жертвовать согласованностью или доступностью только при наличии разделов, и что достижения в методах восстановления разделов позволили разработчикам достичь высоких уровней как согласованности, так и доступности.