Курс «Распределённые системы». Глава 4. Модели согласованности

Цели главы. Превратить слово «согласованность» из маркетингового эпитета в точный инструмент: определить линеаризуемость (и научиться проверять её по истории операций), спуститься по лестнице ослаблений — последовательная, причинная, итоговая — и разобрать сессионные гарантии, которыми ослабленные модели делают пригодными для жизни. Глава отвечает на вопрос «что именно система обещает клиенту»; главы 5–6 — на вопрос «какой механикой обещание выполняется».

4.1. Постановка: что мы вообще определяем

Модель данных для всей главы — простейшая: регистр с операциями write(x) и read()→x, реплицированный на несколько узлов. Клиенты обращаются к системе конкурентно; каждая операция занимает интервал времени от вызова до ответа. Историей назовём набор всех операций с их интервалами и результатами. Модель согласованности — это предикат над историями: контракт, отделяющий допустимые поведения системы от запрещённых. Чем сильнее модель, тем меньше историй она допускает, тем проще рассуждать клиенту — и тем дороже реализация (глава 3 объяснила, почему цена неустранима: координация, задержки, недоступность при разделении).

4.2. Линеаризуемость

Определение. История линеаризуема, если каждой операции можно назначить точку линеаризации — момент внутри её интервала, — так что результаты всех операций совпадают с последовательным исполнением в порядке этих точек. Неформально: система ведёт себя как один регистр в одном месте, а каждая операция срабатывает мгновенно где-то между вызовом и ответом. Два практических следствия определения: если операция A завершилась до начала операции B (по реальному времени!), A обязана быть видна B; конкурентные (перекрывающиеся) операции могут упорядочиться как угодно — но одинаково для всех наблюдателей.

Пример. Клиент 1 исполняет write(1) на интервале [0, 3]; клиент 2 — read()→1 на [1, 2]; клиент 3 — read()→0 на [4, 5]. Линеаризуема ли история? Нет: чтение клиента 3 началось после завершения write(1) и обязано видеть 1 (или более позднюю запись). А если бы интервал клиента 3 был [2, 5]? Всё равно нет, но теперь это надо доказывать. read₂→1 требует, чтобы его точка стояла после точки записи; read₃→0 — чтобы его точка стояла до неё; итого необходим порядок точек read₃ < write < read₂. Но точка read₂ лежит в его интервале, то есть не превосходит 2, а точка read₃ — не меньше 2; цепочка read₃ < write < read₂ ≤ 2 ≤ read₃ замыкается в противоречие — история нелинеаризуема при любом выборе точек. Замените результат третьего чтения на 1 — и точки находятся (например, write=1.5, read₂=1.7, read₃=2.5): история линеаризуема. Такой перебор ограничений алгоритмизуется. В Jepsen для него применяется Knossos; Porcupine — самостоятельная библиотека проверки линеаризуемости на Go (глава 11).

Где линеаризуемость обязательна: выбор лидера, блокировки, сравнение-и-замена, выделение уникального имени. Для денежных остатков и других инвариантов одного линеаризуемого регистра обычно мало: нужна ещё транзакционная изоляция операций над несколькими объектами (глава 9). Цена: каждая сильная операция координируется (кворум/лидер — глава 6), платя round-trip задержки (PACELC!), а при разделении линеаризуемый сервис обязан отказывать той части, которая не может собрать кворум (CAP). Отсюда правило зрелых систем: сильные гарантии — точечно, по операциям, где они куплены не зря.

4.3. Последовательная согласованность

Ослабим требование реального времени: история последовательно согласованна, если существует единый порядок всех операций, согласованный с программным порядком каждого клиента (но не обязательно с реальным временем между клиентами), дающий те же результаты. Разница с линеаризуемостью тонкая, но содержательная: последовательная модель разрешает клиенту 3 из примера выше прочитать 0 после чужой завершившейся записи — «его чтение поставили в общем порядке раньше». Модель пришла из многопроцессорных архитектур (Лэмпорт, 1979) и в распределённых хранилищах встречается реже линеаризуемости и причинности; включаем её ради точности словаря — и потому, что «sequential consistency» регулярно путают с линеаризуемостью в документации продуктов. Тест на различие: линеаризуемость = последовательная + уважение реального времени.

4.4. Причинная согласованность

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

Каноническая аномалия, которую причинность запрещает, а итоговая согласованность (4.5) допускает: пользователь A пишет «Куда пропал кот?», пользователь B отвечает «Нашёлся под диваном»; на третьей реплике ответ материализуется раньше вопроса — диалог для читателя бессмыслен. В стандартной модели всегда доступного хранилища причинная согласованность является сильнейшей широко применимой моделью, совместимой с доступностью при разделении: причинное прошлое можно переносить вместе с данными без глобального тотального порядка. Реализация — метки причинности на записях (векторы главы 2) и задержка применения записи, пока не применено её причинное прошлое.

4.5. Итоговая согласованность

Самое слабое из употребимых обещаний: если записи прекратятся, все реплики когда-нибудь сойдутся к одному значению. О текущем моменте — ничего: чтение может вернуть сколь угодно старое значение, разные реплики — разное, повторное чтение — «откатиться» назад. Это не карикатура, а точный контракт DNS, многих кэшей и Dynamo-наследников при слабых кворумах. Amazon S3 с 2020 года даёт сильную согласованность операций с объектами и списков, поэтому автоматически относить весь «S3-класс» к итогово-согласованным системам нельзя: гарантии конкретной реализации нужно читать отдельно. Два обязательных дополнения слабой модели, без которых контракт бессодержателен: механизм сходимости (анти-энтропия, read repair — глава 5) и стратегия конфликтов (LWW с его потерями, версии с ручным слиянием, CRDT — глава 5).

4.6. Сессионные гарантии

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

• Читай-свои-записи: клиент видит собственные записи. Реализации: читать с лидера первые N секунд после своей записи; либо клиент хранит версию своей последней записи и реплика отвечает не раньше, чем догонит её.
• Монотонные чтения: время не идёт вспять — прочитав версию v, клиент не увидит более старую. Реализация: привязка сессии к реплике либо версия-водяной знак в сессии.
• Монотонные записи: записи одного клиента применяются всюду в его порядке.
• Записи-после-чтений: запись, сделанная после чтения версии v, упорядочивается после v (ответ — после вопроса: строительный блок причинности).

Все четыре вместе дают сессии причинно согласованный взгляд на данные при условии, что клиент переносит контекст между обращениями. Это ещё не означает глобальной причинной согласованности между независимыми сессиями: для неё причинный контекст должны распространять и реплики. Практический компромисс остаётся полезным: глобально система может быть итогово согласованна, а отдельный пользователь не видит наиболее грубых откатов собственного мира.

4.7. Как выбирать: сводка

Данные / операция                  Разумная модель                Почему
─────────────────────────────      ────────────────────────────   ─────────────────────────
Лидерство, блокировки, инварианты  линеаризуемость                иначе split brain /
уникальности, остатки и лимиты                                    двойное исполнение
Лента, профиль, комментарии        причинная / сессионные          аномалия «ответ раньше
                                   гарантии                       вопроса» недопустима
Счётчики просмотров, лайки, кэши   итоговая (+CRDT для счётчиков) устаревание безобидно
Конфигурация, метаданные кластера  линеаризуемость (etcd/ZooKeeper) редко пишется, критично
Аналитика, метрики                 итоговая                        точность момента не нужна

Предостережение о словаре: модели согласованности реплик (эта глава) и уровни изоляции транзакций (read committed, snapshot, serializable) — родственные, но разные оси: первая — про один объект на многих репликах, вторая — про много объектов в одной транзакции. Они встретятся и переплетутся в главе 9; до тех пор не позволяйте документации продуктов смешивать их в одно слово consistency.

Итоги главы

• Модель согласованности — предикат над историями операций: точный контракт «что обещано клиенту».
• Линеаризуемость: система как один регистр, операции мгновенны внутри своих интервалов; проверяемо алгоритмически; обязательна для «ровно один»; оплачивается задержкой и недоступностью меньшинства.
• Последовательная = линеаризуемость минус реальное время; причинная = согласован лишь порядок причинно связанных операций — максимум, достижимый без координации.
• Итоговая согласованность — честный контракт «сойдёмся потом» при обязательных анти-энтропии и стратегии конфликтов.
• Сессионные гарантии (читай-свои-записи, монотонные чтения/записи, записи-после-чтений) делают слабые модели пригодными для пользователя; вместе = причинность в сессии.
• Выбор модели — по классам данных и операций, а не один на систему.

Упражнения

1. Проверьте линеаризуемость истории: клиент 1: write(1) [0,4]; клиент 2: read()→1 [1,2] и позже read()→1 [5,6]; клиент 3: write(2) [1,3]. Найдите точки линеаризации или докажите их отсутствие. Подсказка: подумайте, в каком порядке обязаны стоять точки двух записей, чтобы оба чтения вернули 1.
2. История: клиент A: write(1) [0,2], write(2) [3,5]; клиент B: read()→2 [4,6], read()→1 [7,9]. Линеаризуема ли? Последовательно согласованна? Какая сессионная гарантия нарушена у B?
3. Постройте историю, последовательно согласованную, но не линеаризуемую (подсказка: завершившаяся запись, «не увиденная» более поздним по реальному времени чтением другого клиента).
4. Форум реплицирован итогово-согласованно. Разыграйте аномалию «ответ раньше вопроса» на трёх репликах с конкретными порядками доставки; затем покажите, как метки причинности (векторные часы на сообщениях + задержка применения) её устраняют.
5. Спроектируйте «читай-свои-записи» для системы «лидер + асинхронные реплики» тремя способами (чтение с лидера по таймеру; версия в сессии; липкая реплика) и сравните: поведение при отказе реплики, при нескольких устройствах одного пользователя, стоимость.
6. Продукт обещает в документации strong consistency для чтений «по умолчанию», мелким шрифтом — «с реплик возможны stale reads». Сформулируйте два вопроса к вендору, отделяющие линеаризуемость от сессионных гарантий, и тест (последовательность операций двух клиентов), различающий их экспериментально.

Ответы и указания. 1: история линеаризуема при порядке write(2) < write(1) < оба read; например, точки 1,2; 1,5; 1,7; 5,5 попадают в интервалы. 2: история не линеаризуема и не последовательно согласованна: программный порядок A требует write(1) перед write(2), а программный порядок B — read(2) перед read(1), что нельзя совместить в одном последовательном регистре; у B нарушены монотонные чтения. 3: A завершает write(1), после этого B читает 0. Реальное время запрещает поставить чтение раньше записи, поэтому линеаризуемости нет; последовательная модель такой порядок допускает, потому что между клиентами программной зависимости нет. 4: R1 получает вопрос Q, R2 получает Q и затем ответ A, R3 получает A раньше Q — аномалия. Если A несёт зависимость от Q, R3 откладывает применение A, пока не получит версию Q. 5: чтение с лидера после записи просто, но повышает нагрузку и требует маршрутизации при failover; версия в сессии позволяет выбрать реплику, догнавшую нужную позицию, но токен надо переносить между устройствами; липкая реплика дешева, однако её отказ теряет привязку и сам по себе не гарантирует догон реплики. 6: спросить надо, какие именно операции линеаризуемы и сохраняется ли гарантия при чтении с реплики, а также какие гарантии действуют между разными сессиями. Тест: A завершает write(x=1), затем B в другой сессии читает x; линеаризуемость требует 1, а одни сессионные гарантии этого не обещают.

Литература к главе

1. M. Herlihy, J. Wing, "Linearizability: A Correctness Condition for Concurrent Objects," ACM TOPLAS 12(3), 1990.
2. L. Lamport, "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs," IEEE ToC, 1979 — последовательная согласованность.
3. D. Terry et al., "Session Guarantees for Weakly Consistent Replicated Data," PDIS, 1994.
4. M. Kleppmann, "Designing Data-Intensive Applications," O'Reilly, 2017 — гл. 5, 9.
5. K. Kingsbury, обзор моделей согласованности проекта Jepsen. jepsen.io/consistency

Предыдущая глава || Содержание курса || Следующая глава