Курс «Распределённые системы». Глава 2. Время и порядок

Цели главы. Разобраться, почему физическим часам в распределённой системе нельзя доверять упорядочение событий, и построить работающую замену: отношение «произошло раньше», часы Лэмпорта, векторные часы. В конце — две конструкции, доводящие идеи до практики: алгоритм согласованного снимка Чанди–Лэмпорта и гибридные логические часы, на которых стоят современные распределённые СУБД. Это самая «математическая» глава части I — и одновременно источник самых частых производственных ошибок (все они начинаются со слов «возьмём метку времени»).

2.1. Почему физические часы не годятся

Кварцевый генератор дрейфует — типично на десятки миллионных долей, то есть на миллисекунды в минуту и секунды в сутки. Синхронизация по NTP возвращает часы к истине с точностью от единиц до десятков миллисекунд в хорошей сети — и произвольно плохо при сетевых проблемах; более того, коррекция NTP может перевести часы назад, так что даже на одной машине последовательные вызовы «который час» могут убывать (поэтому для измерения длительностей существуют монотонные часы — они не для календаря, но хотя бы не идут вспять). Виртуализация добавляет паузы гипервизора, миграции — скачки.

Следствие для распределённой системы: если события на двух узлах помечены физическим временем с разницей меньше погрешности синхронизации (миллисекунды — а под них попадает практически вся конкурентная нагрузка), их порядок по меткам — фикция. Канонический производственный ущерб — репликация «последняя запись побеждает» (LWW): узел с часами, спешащими на 30 мс, систематически выигрывает конфликты у честного соседа, молча затирая его свежие записи; заметить это без специального аудита почти невозможно. Отсюда программа главы: заменить вопрос «когда произошло?» вопросом «что от чего зависело?».

2.2. Отношение «произошло раньше»

Лэмпорт (1978) определил на событиях системы (в модели главы 1) отношение произошло-раньше, обозначаемое a → b, как наименьшее транзитивное отношение, такое что:

1. если a и b — события одного процесса и a предшествует b локально, то a → b;
2. если a — отправка сообщения, а b — его получение, то a → b;
3. если a → b и b → c, то a → c.

Содержательно a → b означает: информация о событии a могла достичь точки события b — a лежит в причинном прошлом b. Если ни a → b, ни b → a, события называются конкурентными (a ∥ b): никакая из сторон не могла знать о другой, и любой их взаимный порядок — вопрос соглашения, а не факта. Это точный смысл слова «одновременно» в распределённой системе: не «в один момент по часам» (бессмысленно — см. 2.1), а «причинно независимо». Всё дальнейшее содержание главы — способы вычислять отношение → эффективно.

2.3. Часы Лэмпорта

Простейший механизм — скалярные часы Лэмпорта: каждый процесс держит целочисленный счётчик L.

• Перед каждым локальным событием: L := L + 1.
• В каждое сообщение вкладывается текущий L отправителя.
• При получении сообщения с меткой t: L := max(L, t) + 1.

Свойство (доказывается индукцией по определению →, упражнение 2): если a → b, то L(a) < L(b). Причинный порядок никогда не нарушается номерами. Обратное неверно: из L(a) < L(b) не следует a → b — конкурентные события тоже получают какие-то, вообще говоря различные, номера. Часы Лэмпорта упорядочивают причинность, но не умеют распознавать конкурентность.

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

2.4. Векторные часы

Чтобы распознавать конкурентность, счётчик заменяют вектором: процесс p_i в системе из n процессов держит вектор V из n счётчиков, где V[j] — «сколько событий процесса p_j лежит в моём причинном прошлом».

• Локальное событие у p_i: V[i] := V[i] + 1.
• Сообщение несёт весь вектор отправителя.
• Получение с вектором W: V := поэлементный max(V, W); затем V[i] := V[i] + 1.

Сравнение векторов: V ≤ W, если V[k] ≤ W[k] по всем k; V < W, если вдобавок хоть где-то строго. Точная характеристика (в отличие от лэмпортовских): a → b тогда и только тогда, когда V(a) < V(b); несравнимые векторы = конкурентные события. Векторные часы — полный детектор причинности; цена — O(n) на каждое сообщение и головная боль при динамическом множестве участников.

Практика: версионные векторы (близкий родственник) в Dynamo-подобных хранилищах отличают «новая версия перекрывает старую» от «версии конкурентны — конфликт, требуется слияние» (вспомните лестницу разрешения конфликтов из статьи о надёжности: честные варианты стоят именно на этом механизме). Там, где участников слишком много, платят точностью: усечённые векторы дают ложные конфликты, LWW — молчаливые потери; инженерный выбор между ними должен быть осознанным.

2.5. Согласованные снимки: алгоритм Чанди–Лэмпорта

Применим накопленное к практической задаче: снять глобальное состояние работающей системы — всех процессов и всех сообщений в пути — не останавливая её. Наивное «каждый снимет себя в полночь» разбивается об 2.1: полуночи, единой для всех, не существует, и снимок получится физически противоречивым (деньги, списанные в снимке A и ещё не зачисленные в снимке B, «исчезли»). Правильное требование к снимку — не одновременность, а согласованность: если событие b попало в снимок и a → b, то a тоже попало (снимок замкнут относительно причинного прошлого — «разрез» истории, который не пересекает ни одной стрелки причинности справа налево).

Алгоритм Чанди–Лэмпорта (1985), в предположении надёжных FIFO-каналов:

1. Инициатор фиксирует своё состояние и посылает во все исходящие каналы специальное сообщение-маркер.
2. Процесс, впервые получивший маркер (по каналу c): фиксирует своё состояние, объявляет канал c пустым в снимке и рассылает маркер во все свои исходящие каналы.
3. Процесс, уже зафиксировавшийся, при получении маркера по каналу c′: записывает в снимок как «содержимое канала c′» все обычные сообщения, пришедшие по c′ между его фиксацией и этим маркером.

Маркеры, распространяясь волной, «разрезают» историю согласованным образом: FIFO гарантирует, что сообщения, отправленные до фиксации отправителя, не проскочат мимо учёта. Алгоритм красив сам по себе, но включён в курс за живучесть идеи: согласованные контрольные точки Apache Flink используют родственную схему с барьерами в потоках. Детали отличаются: выровненные checkpoints задерживают обработку за быстрыми барьерами, а невыровненные дополнительно фиксируют данные в каналах. Согласованные бэкапы шардированных систем решают ту же общую задачу.

Рис. 2.1. Согласованный разрез включает локальные состояния процессов и сообщения, находившиеся в каналах.

2.6. Гибридные логические часы

Инженерам хочется невозможного: чтобы метка была и причинно корректной (как Лэмпорт), и близкой к физическому времени (читаемой человеком, пригодной для TTL и диапазонных запросов). Компромисс — гибридные логические часы (HLC, 2014): метка (pt, l), где pt учитывает локальное физическое время и виденные метки, а логическая часть l разводит события с одинаковой физической компонентой. При корректном распространении меток HLC сохраняют причинный порядок и остаются близки к физическим часам; предел близости зависит от принятых ограничений на рассинхронизацию. HLC использует, например, CockroachDB. Другие СУБД решают задачу иначе: TiDB получает метки от TSO, YDB использует логическое время координаторов, а Spanner применяет TrueTime с атомными часами и GPS и отвечает о фиксации только после commit-wait. Эти конструкции встретятся нам в главе 9.

Итоги главы

• Физические часы дрейфуют, прыгают и не доказывают порядок; LWW по физическим меткам молча теряет данные.
• Правильный вопрос — не «когда», а «что от чего зависело»: отношение a → b (произошло-раньше) и конкурентность a ∥ b.
• Часы Лэмпорта: a → b ⇒ L(a) < L(b); дёшево, дают тотальный порядок с tie-break, но не распознают конкурентность.
• Векторные часы: a → b ⇔ V(a) < V(b) — полный детектор причинности ценой O(n) на сообщение; основа честного обнаружения конфликтов версий.
• Согласованный снимок — разрез, замкнутый по причинности; алгоритм Чанди–Лэмпорта строит его маркерами на лету, а потоковые системы используют родственные барьерные снимки.
• HLC, централизованные TSO, координаторное логическое время и TrueTime — разные инженерные способы получить порядок транзакций в распределённых SQL-СУБД.

Упражнения

1. Три процесса, события: P1: a (отправка m1 к P2), затем b; P2: c (получение m1), d (отправка m2 к P3); P3: e (получение m2), f. Выпишите все пары x → y и все конкурентные пары. Проставьте лэмпортовские метки (старт с 0) и векторные.
2. Докажите индукцией свойство часов Лэмпорта: a → b ⇒ L(a) < L(b). Разберите три случая из определения отношения →.
3. Постройте на диаграмме из упражнения 1 (или своей) пример пары событий с L(a) < L(b), но a ∥ b — и убедитесь, что их векторные метки несравнимы.
4. Реплики используют LWW по физическим часам; часы реплики B спешат на 30 мс. Клиент записал x=1 на A, через 10 мс (реального времени) другой клиент записал x=2 на B, репликация сошлась. Какое значение победит? А если второй записью была x=2 на A, а первой — на B? Сформулируйте, какие потери LWW делает систематическими.
5. В алгоритме Чанди–Лэмпорта уберите требование FIFO: постройте исполнение с несогласованным снимком (сообщение учтено у получателя, но отправлено после фиксации отправителя — «стрелка из будущего в прошлое»).
6. Банковская система: счёт A на узле 1, счёт B на узле 2, перевод — «списать на 1, послать сообщение, зачислить на 2». Покажите на разрезах, какой снимок «теряет» деньги в пути и почему согласованный снимок Чанди–Лэмпорта суммы сохраняет (деньги окажутся в состоянии канала).
7. Векторные часы для системы с тысячами короткоживущих клиентов непрактичны. Перечислите компромиссы (векторы по серверам-репликам вместо клиентов; усечение по размеру/возрасту; dotted version vectors — по одному на изучение) и цену каждого в терминах «ложные конфликты / потерянные конфликты».

Ответы и указания. 1: причинные рёбра порождают цепочки a→c→d→e→f и a→b; b конкурентно с c, d, e и f. Метки Лэмпорта: a=1, b=2, c=2, d=3, e=4, f=5. Векторы: a=(1,0,0), b=(2,0,0), c=(1,1,0), d=(1,2,0), e=(1,2,1), f=(1,2,2). 2: для локального порядка счётчик строго увеличивается; при отправке метка сообщения равна метке события отправки, а получение берёт максимум с ней и добавляет один; транзитивность сохраняет неравенство по цепочке. Это покрывает три порождающих случая определения →. 3: b и e имеют L(b)=2 < L(e)=4, но b ∥ e; векторы (2,0,0) и (1,2,1) несравнимы. 4: в обоих сценариях побеждает запись на B: во втором случае более ранняя реальная запись получает большую метку и стирает более позднюю. LWW систематически отдаёт преимущество спешащим часам. 5: процесс P фиксирует состояние, отправляет маркер M, а затем обычное сообщение x. В не-FIFO-канале x обгоняет M. Процесс Q сначала получает и применяет x, а при последующем получении M фиксирует уже изменённое локальное состояние. Снимок P не содержит отправку x, произошедшую после его фиксации, тогда как снимок Q содержит её следствие: разрез получился несогласованным. 6: несогласованный разрез фиксирует узел 1 после списания, узел 2 до зачисления и не учитывает канал; согласованный снимок помещает перевод в состояние канала и сохраняет сумму. 7: вектор только по долговечным репликам уменьшает размер, но теряет точную причинность клиентов; усечение превращает забытые зависимости в ложную конкурентность или, при неосторожном слиянии, скрывает конфликт; dotted version vectors компактно отделяют одно новое событие от контекста, но требуют аккуратного управления идентификаторами и контекстом причинности.

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

1. L. Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System," CACM 21(7), 1978 — обязательное чтение первоисточника.
2. C. Fidge, "Timestamps in Message-Passing Systems," 1988; F. Mattern, "Virtual Time and Global States of Distributed Systems," 1989 — векторные часы.
3. K. M. Chandy, L. Lamport, "Distributed Snapshots: Determining Global States of Distributed Systems," ACM TOCS 3(1), 1985.
4. S. Kulkarni et al., "Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases (HLC)," 2014.
5. M. Kleppmann, "Designing Data-Intensive Applications," O'Reilly, 2017 — гл. 8 (ненадёжные часы), гл. 5 (обнаружение конкурентных записей).

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