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

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

Definition

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

Scope

Эта тема охватывает формальные модели согласованности — линеаризуемость, последовательную согласованность, причинную согласованность и итоговую согласованность — и их упорядочение по силе; теорему CAP, ее точную формулировку и доказательство; а также уточнения, такие как PACELC, которые также учитывают компромисс между задержкой и согласованностью в отсутствие разделов. Она предоставляет словарь для спецификации и сравнения гарантий реплицированных систем.

Core questions

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

Key theories

Линеаризуемость и последовательная согласованность

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

Теорема CAP

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

Уточнение PACELC

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

Clinical relevance

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

History

Лампорт определил последовательную согласованность в 1979 году, а Херлихи и Винг формализовали линеаризуемость в 1990 году; Брюэр выдвинул гипотезу о компромиссе CAP в 2000 году, Гилберт и Линч доказали ее в 2002 году, а переосмысление PACELC Абади в 2012 году прояснило, что задержка, а не только разделы, определяет выбор согласованности.

Debates

Часто ли CAP неверно истолковывается?

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

Key figures

• Eric Brewer
• Seth Gilbert
• Nancy Lynch
• Maurice Herlihy
• Jeannette Wing
• Leslie Lamport

Seminal works

• gilbert2002
• herlihy1990
• lamport1979

Frequently asked questions

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

Не совсем. Разделы — это факт сетей, а не выбор дизайна, поэтому реальное решение заключается в том, что делать во время раздела: пожертвовать строгой согласованностью, чтобы оставаться доступным, или пожертвовать доступностью, чтобы оставаться согласованным. Когда раздела нет, система может быть как согласованной, так и доступной.