Interested Article - Теорема CAP

ashanti
  • 2020-04-07
  • 1

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

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

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

Принцип был предложен профессором Калифорнийского университета в Беркли в июле 2000 года и впоследствии получил широкую популярность и признание в среде специалистов по распределённым вычислениям . Концепция NoSQL , в рамках которой создаются распределённые нетранзакционные системы управления базами данных , зачастую использует этот принцип в качестве обоснования неизбежности отказа от согласованности данных . Однако многими учёными и практиками теорема CAP критикуется за вольность трактовки и даже недостоверность в том смысле, в котором она распространена в сообществе.

Обоснования

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

Следствия

С точки зрения теоремы CAP, распределённые системы вычислений в зависимости от пары практически поддерживаемых свойств из трёх возможных распадаются на три класса — CA, CP, AP (при этом в рамках одной программной системы могут быть реализованы стратегии обработки различных запросов с использованием различных систем вычислений).

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

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

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

BASE-архитектура

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

Примечания

  1. .
  2. , 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. ↑ (англ.) ( PDF ). genedb.com (17 апреля 2011). Дата обращения: 7 июня 2011. Архивировано из 28 июня 2011 года.
  4. ↑ Browne, Julian (англ.) (11 января 2009). Дата обращения: 7 июня 2011. 1 августа 2012 года.
  5. ↑ , 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. , This conjecture is now commonly known as the CAP theorem and is one of the main arguments why traditional relational database techniques that provide strong ACID guarantees (atomic transactions, transactional consistency and isolation, and data durability) cannot provide both the partition tolerance and availability required by large-scale distributed applications, p. 49.
  7. , Более серьёзным “теоретическим” основанием NoSQL-разработок, в которых общепринятые полезные свойства систем управления данными приносятся в жертву доступности этих систем, является так называемая “теорема CAP”, впервые сформулированная Эриком Брювером, с. 191.
  8. , я заключаю слово теорема в кавычки, поскольку утверждение, названное Брювером теоремой, таковым я признать не могу из-за отсутствия какой-либо чёткой и хотя бы немного формальной постановки задачи … но широко распространено мнение, что она означает невозможность поддержки в одной распределенной системе управления данных свойств согласованности данных (Consistency), доступности (Availability) и устойчивости к разделению сети (Partitioning), с. 191—192.
  9. , 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. , 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. , 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. , Some CA systems include: single site databases, cluster databases and LDAP.
  13. , CP (отказы обслуживания) – это подход с наличием дублирования, строгой ACID непротиворечивостью и синхронной репликацией изменений с применением метода пессимистических блокировок.
  14. , Some AP Systems include: Web caching systems and the Domain Name System (DNS).
  15. , Eventual consistency – performing a read operation may give stale data to the client, but all writes will eventually propagate through the entire system.
  16. , CAP Implies Weak Consistency.
  17. , 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. , 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. .
  20. .

Литература

Источник —

ashanti
  • 2020-04-07
  • 1
  • Tags:

Same as Теорема CAP

The title for the last searches