Теорема CAP и модели согласованности

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

Definition

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

Scope

Эта тема охватывает теорему CAP и ее формализацию, практическое понимание того, что реальный компромисс возникает только во время сетевых разделений, и вытекающее из этого уточнение PACELC. Она охватывает спектр моделей согласованности — от строгой (линеаризуемой) согласованности через причинную согласованность до итоговой согласованности — и стиль BASE, который контрастирует с ACID. В ней рассматривается, как эти модели направляют проектирование реплицированных хранилищ данных. Она исключает протоколы консенсуса и фиксации, используемые для реализации строгой согласованности, которые рассматриваются в разделе распределенных баз данных.

Core questions

• Что именно означают согласованность, доступность и устойчивость к разделению в CAP?
• Почему реальный выбор между согласованностью и доступностью вынужден только во время разделения?
• Чем строгая, причинная и итоговая согласованность отличаются по своим гарантиям?
• Что обещает итоговая согласованность, а что нет?
• Как философия BASE контрастирует с ACID?

Key concepts

• согласованность, доступность, устойчивость к разделению
• сетевое разделение
• линеаризуемость / строгая согласованность
• причинная согласованность
• итоговая согласованность
• PACELC
• BASE против ACID
• разрешение конфликтов

Key theories

Теорема CAP

Формализованная Гилбертом и Линчем, CAP показывает, что при сетевом разделении реплицированное хранилище должно выбирать между возвратом, возможно, устаревших данных (доступность) и отказом в обслуживании для сохранения единого согласованного значения (согласованность); устойчивость к разделению не является необязательной в реальных сетях.

Спектр согласованности

Модели согласованности варьируются от строгой (линеаризуемой) согласованности, где операции чтения всегда видят последнюю запись, через причинную согласованность, которая сохраняет причинно-следственный порядок, до итоговой согласованности, где реплики сходятся со временем при отсутствии новых записей.

BASE против ACID

Высокодоступные системы часто используют стиль BASE — базовая доступность, мягкое состояние, итоговая согласованность (basically available, soft state, eventually consistent) — намеренно ослабляя строгие гарантии ACID, чтобы оставаться отзывчивыми при разделениях и в масштабе.

Clinical relevance

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

History

Эрик Брюэр выдвинул гипотезу о компромиссе CAP примерно в 2000 году; Гилберт и Линч формально доказали ее в 2002 году. Amazon Dynamo (2007) и эссе Фогельса 2009 года популяризировали итоговую согласованность на практике. Ретроспектива Брюэра 2012 года уточнила, что CAP запрещает идеальную согласованность и доступность только во время разделений, а формулировка PACELC позже добавила компромисс между задержкой и согласованностью в случае отсутствия разделений.

Debates

Насколько фундаментален компромисс между согласованностью и доступностью

Ранние интерпретации рассматривали CAP как принуждение к постоянному выбору между согласованностью и доступностью; более поздние анализы, включая ретроспективу Брюэра, утверждают, что компромисс проявляется только во время разделений и что системы могут быть в значительной степени согласованными и доступными в противном случае, переосмысливая, насколько строго CAP ограничивает дизайн.

Key figures

• Eric Brewer
• Seth Gilbert
• Nancy Lynch
• Werner Vogels

Seminal works

• gilbert2002
• brewer2012
• vogels2009

Frequently asked questions

Означает ли CAP, что я могу иметь только два из трех свойств?

Популярная формулировка «выбери два» вводит в заблуждение. Устойчивость к разделению на самом деле не является необязательной в распределенной системе, поэтому подлинный выбор стоит между согласованностью и доступностью, и этот выбор приходится делать только тогда, когда происходит разделение. Когда сеть здорова, система может обеспечивать как согласованность, так и доступность.

Что на самом деле гарантирует итоговая согласованность?

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