Теорема CAP

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Теорема CAP (известная также как теорема Брюера), в информатике — эвристическое утверждение о том, что в любой реализации распределённых вычислений возможно обеспечить не более двух из трёх следующих свойств:

  • согласованность данных (англ. consistency) — во всех вычислительных узлах в один момент времени данные не противоречат друг другу;
  • доступность (англ. availability) — любой запрос к распределённой системе завершается корректным откликом;
  • устойчивость к разделению (англ. partition tolerance) — расщепление распределённой системы на несколько изолированных секций не приводит к некорректности отклика от каждой из секций.

Акроним CAP в наименовании теоремы сформирован из первых букв английских наименований этих трёх свойств.

Принцип был предложен профессором Калифорнийского университета в Беркли Эриком Брюером в июле 2000 года[1][2] и впоследствии получил широкую популярность и признание в среде специалистов по распределённым вычислениям[3][4]. Концепция NoSQL, в рамках которой создаются распределённые нетранзакционные системы управления базами данных, зачастую использует этот принцип в качестве обоснования неизбежности отказа от согласованности данных[5][6][7]. Однако многими учёными[8] и практиками[9] теорема CAP критикуется за вольность трактовки и даже недостоверность в том смысле, в котором она распространена в сообществе.

Обоснования[править | править вики-текст]

В 2002 году Сет Джилберт и Нэнси Линч из Массачусетского технологического института подобрали формальные модели асинхронных и синхронных распределённых вычислений, в рамках которых показано выполнение теоремы CAP в условиях отсутствия синхронизации (общих часов) у узлов распределённой системы и принципиальную возможность компромисса в частично синхронных системах[10]. В этой работе «согласованность» в смысле теоремы CAP соотнесена с выполнением первых двух требований ACID — атомарности и согласованности. В дальнейшем, многие практики ссылались на данную работу как на доказательство теоремы CAP[4][11][3].


Следствия[править | править вики-текст]

Согласно теореме CAP, распределённые системы в зависимости от пары практически поддерживаемых свойств из трёх возможных распадаются на три класса.

CA[править | править вики-текст]

Система, во всех узлах которой данные согласованы и обеспечена доступность, жертвует устойчивостью к распаду на секции. Такие системы возможны на основе технологического программного обеспечения, поддерживающего транзакционность в смысле ACID. Примерами таких систем могут быть решения на основе кластерных систем управления базами данных или распределённая служба каталогов LDAP[12].

CP[править | править вики-текст]

Распределённая система, в каждый момент обеспечивающая целостный результат и способная функционировать в условиях распада, в ущерб доступности может не выдавать отклик. Устойчивость к распаду на секции требует обеспечения дублирования изменений во всех узлах системы, в этой связи отмечается практическая целесообразность использования в таких системах распределённых пессимистических блокировок для сохранения целостности[13].

AP[править | править вики-текст]

Распределённая система, отказывающаяся от целостности результата. Хотя системы такого рода известны задолго до формулировки принципа CAP (например, распределённые веб-кэши или DNS)[14], рост популярности систем с этим набором свойств связывается именно с распространением теоремы CAP. Так, большинство NoSQL-систем принципиально не гарантируют целостности данных, и ссылаются на теорему CAP как на мотив такого ограничения[5]. Задачей при построении AP-систем становится обеспечение некоторого практически целесообразного уровня целостности данных, в этом смысле про AP-системы говорят как о «целостных в конечном итоге» (англ. eventually consistent)[15] или как о «слабо целостных» (англ. weak consistent)[16].

BASE-архитектура[править | править вики-текст]

Во второй половине 2000-х годов сформулирован подход к построению распределённых систем, в которых требования целостности и доступности выполнены не в полной мере, названый акронимом BASE (от англ. Basically Available, Soft-state, Eventually consistent — базовая доступность, неустойчивое состояние, согласованность в конечном счёте), при этом такой подход напрямую противопоставляется ACID[17]. Под базовой доступностью подразумевается такой подход к проектированию приложения, чтобы сбой в некоторых узлах приводил к отказу в обслуживании только для незначительной части сессий при сохранении доступности в большинстве случаев[18]. Неустойчивое состояние подразумевает возможность жертвовать долговременным хранением состояния сессий (таких как промежуточные результаты выборок, информация о навигации, контексте), при этом концентрируясь на фиксации обновлений только критичных операций. Согласованности в конечном счёте (англ. Eventual consistency), трактующейся как возможность противоречивости данных в некоторых случаях, но при обеспечении согласования в практически обозримое время, посвящено значительное количество самостоятельных исследований[19][20].

Критика[править | править вики-текст]

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Brewer, 2000
  2. Gilbert, Lynch, 2002, At PODC 2000, Brewer, in an invited talk, made the following conjecture: it is impossible for a web service to provide the following three guarantees: • Consistency • Availability • Partition-tolerance, p. 55
  3. 1 2 White Paper Beating the CAP Theorem (англ.) (PDF). genedb.com (17 April 2011). Проверено 7 июня 2011. Архивировано из первоисточника 1 августа 2012.
  4. 1 2 Browne, Julian Brewer’s CAP Theorem (англ.) (11 January 2009). Проверено 7 июня 2011. Архивировано из первоисточника 1 августа 2012.
  5. 1 2 Brewer, 2010, Designers of wide-area systems, in which network partitions are considered inevitable, know they cannot have both availability and consistency, and thus can now justify weaker consistency. The rise of the “NoSQL” movement (“Not Only SQL”) is an expression of this freedom, p. 335
  6. Rys, 2011, p. 49
  7. Кузнецов, 2011, Более серьёзным “теоретическим” основанием NoSQL-разработок, в которых общепринятые полезные свойства систем управления данными приносятся в жертву доступности этих систем, является так называемая “теорема CAP”, впервые сформулированная Эриком Брювером
  8. Кузнецов, 2011, я заключаю слово теорема в кавычки, поскольку утверждение, названное Брювером теоремой, таковым я признать не могу из-за отсутствия какой-либо чёткой и хотя бы немного формальной постановки задачи … но широко распространено мнение, что она означает невозможность поддержки в одной распределенной системе управления данных свойств согласованности данных (Consistency), доступности (Availability) и устойчивости к разделению сети (Partitioning)
  9. Rys, 2011, So why are many of the leading social networking sites (Facebook, MySpace, Twitter), e-commerce Web sites (hotel reservation systems and shopping sites), and large banking applications still implemented using traditional database systems such as MySQL (Facebook, Twitter) or SQL Server (MySpace, Choice Hotels International, Bank Itau) instead of using the new NoSQL systems? … The high-level answer is that the application architecture is still weighing the same trade-offs required by the CAP theorem, p. 50
  10. Gilbert, Lynch, 2002, In an asynchronous model, when no clocks are available, the impossibility result is fairly strong: it is impossible to provide consistent data, even allowing stale data to be returned when messages are lost. However in partially synchronous models it is possible to achieve a practical compromise between consistency and availability, p. 59
  11. Grigorik, 2010, Problem is, the CAP theorem proposed by Eric Brewer and later proved by Seth Gilbert and Nancy Lynch, shows that together, these three requirements are impossible to achieve at the same time
  12. Carter, 2011, Some CA systems include: single site databases, cluster databases and LDAP
  13. Демидов, 2010, CP (отказы обслуживания) – это подход с наличием дублирования, строгой ACID непротиворечивостью и синхронной репликацией изменений с применением метода пессимистических блокировок
  14. Carter, 2011, Some AP Systems include: Web caching systems and the Domain Name System (DNS)
  15. Carter, 2010, Eventual consistency – performing a read operation may give stale data to the client, but all writes will eventually propagate through the entire system
  16. Grigorik, 2010, CAP Implies Weak Consistency
  17. Pritchett, 2008, If ACID provides the consistency choice for partitioned databases, then how do you achieve availability instead? One answer is BASE (basically available, soft state, eventually consistent). BASE is diametrically opposed to ACID
  18. Pritchett, 2008, The availability of BASE is achieved through supporting partial failures without total system failure. Here is a simple example: if users are partitioned across five database servers, BASE design encourages crafting operations in such a way that a user database failure impacts only the 20 percent of the users on that particular host
  19. Стоунбрейкер, 2010
  20. Vogels, 2008

Литература[править | править вики-текст]