Распределённые системы
Vector Clocks: точный порядок событий
Цели урока
- Понимать ограничение Lamport Timestamps: частичный порядок без обнаружения конкурентности
- Знать три правила Vector Clock: tick, send, receive
- Уметь сравнивать векторы и определять причинность vs конкурентность
- Различать Vector Clocks, HLC и TrueTime по применению
Предварительные знания
- Lamport Timestamps и отношение happened-before
- Понимание репликации и eventual consistency
- Базовые структуры данных (Map, массив)
Каждый раз когда добавляешь товар в корзину Amazon с телефона и компьютера одновременно - Vector Clock решает, не потерян ли ни один из товаров.
- **Amazon Dynamo (2007)** - Vector Clocks для обнаружения конфликтов при репликации корзин покупателей
- **Riak** - Dotted Version Vectors (эволюция Vector Clocks) для кластеров с тысячами клиентов
- **CockroachDB / YugabyteDB** - HLC для globally consistent SQL транзакций без атомных часов
- **Apache Cassandra** - LWW как упрощённая альтернатива, цена: возможная потеря данных при конфликтах
- **Google Spanner** - TrueTime как альтернатива Vector Clocks через атомные часы и GPS приёмники
Colin Fidge и Friedemann Mattern: параллельное открытие 1988
В 1988 году два исследователя независимо опубликовали одну и ту же идею: Colin Fidge в январе (университет Квинсленда) и Friedemann Mattern в сентябре (Дармштадт). Fidge в статье "Timestamps in Message-Passing Systems That Preserve the Partial Ordering", Mattern в "Virtual Time and Global States of Distributed Systems". Оба ссылались на Lamport 1978 как отправную точку. Сегодня структуру называют Vector Clocks или Fidge/Mattern timestamps.
Почему Lamport Timestamps не достаточно
**Amazon S3, 2006 год. Первый запуск. Инженеры обнаруживают: две реплики одного объекта хранят разные версии - обе с меткой времени 14:32:00.412. NTP давал точность 100 мс. Кто записал данные первым - система не знает.** Так появился запрос на Vector Clocks в Amazon Dynamo - инструмент, который сегодня хранит содержимое корзин 200 млн покупателей.
Lamport Timestamps (1978) дают частичный порядок: если L(a) < L(b), то событие a могло произойти до b. Но обратное неверно: L(a) < L(b) не означает, что a случилось раньше b. Два независимых события на разных узлах могут получить одинаковую метку.
| Свойство | Lamport Timestamps | Vector Clocks |
|---|---|---|
| Размер данных | 1 число | N чисел (по одному на узел) |
| a causally before b? | L(a) < L(b) - необходимо, но не достаточно | VC(a) < VC(b) - точный критерий |
| Обнаружение конкурентности | Нет - невозможно отличить от причинности | Да - a || b если VC(a) несравнимы с VC(b) |
| Применение | Тотальный порядок событий (с доп. правилами) | Определение конфликтов и причинности |
Знак отношения Lamport: если a causally before b, то L(a) < L(b). Но если L(a) < L(b) - это ещё не значит причинную связь. Vector Clocks дают двустороннее отношение: a -> b тогда и только тогда, когда VC(a) < VC(b).
Lamport Timestamps однозначно упорядочивают все события в распределённой системе
Lamport Timestamps дают только частичный порядок: если a -> b то L(a) < L(b), но не наоборот
Счётчик Lamport монотонно растёт при получении сообщений, но два независимых узла могут достичь одинакового значения без всякой причинной связи. Vector Clocks хранят вектор из N счётчиков и дают точный двусторонний критерий.
На двух узлах события имеют Lamport Timestamps L=7. Что можно утверждать?
Как работает Vector Clock
**Идея Colin Fidge и Friedemann Mattern (1988, независимо друг от друга): каждый узел хранит вектор счётчиков - по одному на каждый узел в системе. Инкрементируй свой счётчик при каждом событии, передавай весь вектор в сообщениях, при получении бери максимум по каждой позиции.** Три правила, которые дают полную информацию о причинности.
Три узла, три события
P1=[1,0,0] отправляет msg -> P2. P2=[0,1,0] получает: merge([1,0,0],[0,1,0])=[1,1,0], инкремент -> P2=[1,2,0]. P3=[0,0,1] делает локальное событие -> P3=[0,0,2]. Теперь: P2=[1,2,0] и P3=[0,0,2] несравнимы - события конкурентны. P1=[1,0,0] и P2=[1,2,0]: P1 causally before P2 (1<=1, 0<=2, 0<=0 и хоть одно строго меньше).
Размер Vector Clock = O(N), где N - количество узлов. В Amazon Dynamo N=9 (стандартное кольцо). Для систем с тысячами узлов используют Dotted Version Vectors или другие компактные структуры.
Узел P2 получает сообщение с VC=[3,0,2]. У P2 сейчас VC=[1,4,1]. Каким будет VC у P2 после получения?
Сравнение векторов и обнаружение конфликтов
**Amazon DynamoDB 2007: при добавлении товара в корзину на двух устройствах одновременно - какую версию сохранить? DynamoDB использует Vector Clocks для точного ответа: если векторы конкурентны - оба варианта передаются клиенту для ручного merge. Именно так работает "добавление в корзину" на Amazon.com.**
| VC(a) | VC(b) | Результат | Интерпретация |
|---|---|---|---|
| [1,0,0] | [2,1,0] | before (a->b) | a causally before b, b видело событие a |
| [2,1,0] | [1,0,0] | after (b->a) | b causally after a |
| [1,2,0] | [1,0,3] | concurrent (||) | конфликт - оба варианта нужно merge |
| [2,1,3] | [2,1,3] | equal | одинаковое состояние на обоих узлах |
Конфликт в корзине Amazon
Пользователь на мобильном добавляет книгу: VC=[mobile:1, web:0]. Одновременно на веб-версии добавляет наушники: VC=[mobile:0, web:1]. Сервер получает обе версии. compareVC([1,0],[0,1]) = 'concurrent'. Dynamo не выбирает победителя - возвращает оба варианта клиенту с пометкой 'conflict'. Shopping cart service делает union: корзина содержит и книгу, и наушники. Результирующий VC=[mobile:1, web:2].
Last-Write-Wins (LWW) проще, чем Vector Clocks - берём версию с большим timestamp. Но LWW молча теряет данные при конкурентных записях. Vector Clocks обнаруживают конфликт и сохраняют все версии для merge. Cassandra использует LWW по умолчанию. Riak и Dynamo - Vector Clocks.
Vector Clocks автоматически разрешают конфликты при конкурентных записях
Vector Clocks только обнаруживают конфликт и сохраняют все версии - разрешение остаётся на уровне приложения или CRDT
Vector Clocks - это инструмент детектирования причинности, не conflict resolution. После обнаружения конкурентных версий система должна либо вернуть обе клиенту (Dynamo), либо использовать CRDT для автоматического слияния (Riak с CRDT типами), либо применить LWW как fallback.
Сервер видит две версии объекта: VC1=[3,1,0] и VC2=[2,0,2]. Что должна сделать система?
Hybrid Logical Clocks и практика
**CockroachDB, 2015. Цель: глобально распределённая SQL-база с serializable isolation. Проблема: Vector Clocks плохо масштабируются на SQL (нужны глобальные транзакции), а физические часы дают 100-500 мс дрейф. Решение: Hybrid Logical Clocks (HLC) - физическое время как база, логический счётчик для разрешения коллизий. CockroachDB использует HLC в каждой транзакции с 2015 года.**
| Механизм | Размер | Точность | Применение |
|---|---|---|---|
| Lamport Clock | 1 int | Частичный порядок (однонаправленный) | Тотальный порядок событий (с tie-breaking) |
| Vector Clock | N ints | Точная причинность + конкурентность | Conflict detection (Dynamo, Riak, Voldemort) |
| HLC | 2 ints | Причинность + близость к физическому времени | Глобальные транзакции (CockroachDB, YugabyteDB) |
| TrueTime (Spanner) | Интервал [earliest, latest] | Сильная согласованность глобально | Google Spanner (атомные часы + GPS) |
Версии Dotted Version Vectors решают проблему роста Vector Clocks при большом числе клиентов: вместо счётчика на каждый узел хранится пара (узел, счётчик) только для последней записи. Riak 2.0 перешёл на DVV в 2014 году, сократив размер метаданных в 10 раз на больших кластерах.
Зачем CockroachDB использует HLC вместо чистых Vector Clocks?
Вопросы для размышления
- Система хранит данные на 100 узлах. Vector Clock размером 100 чисел на каждый объект - приемлемо ли это? При каком количестве узлов Vector Clocks становятся практически неудобными, и какие альтернативы рассмотреть?
Связанные уроки
- dist-05-vector-clocks — Builds on basic vector clocks
- dist-11-replication — Version vectors enable multi-master conflict detection
- ds-10-crdts — Dotted version vectors track CRDT state precisely
- alg-18-topological