SYS Системы и большие данные Алгоритм
Часы Лэмпорта и векторные часы
Также: Lamport clocks · vector clocks · логические часы · logical clocks · отношение «случилось раньше» · happened-before · версионные векторы · version vectors · гибридные логические часы · hybrid logical clocks · номер поколения · generation number
Когда у системы нет общих часов, «раньше» значит одно: о событии успели узнать. Часы Лэмпорта — одно число на событие — никогда не противоречат этому порядку, но не умеют сказать «параллельно». Векторные часы умеют, ценой числа на каждый процесс. На истории git этого сайта видно и то и другое — и то, что сам git держит в каждом коммите часы Лэмпорта.
Этот сайт пишется параллельно: игра «Форпост» в одной ветке, аэродинамическая труба в другой, каталог алгоритмов в третьей, и время от времени ветки вливаются в основную. В истории git 1258 коммитов на тридцати линиях работы. Какие правки сделаны раньше каких, а какие — параллельно, ничего не зная друг о друге? Сцена открылась на последних коммитах «Форпоста» и трубы. Нажимайте на коммиты и двигайте окно по истории.
Последний коммит ветки outpost и последний коммит ветки wind-tunnel параллельны: ни один не знает о другом. Это видно по их векторам — по числу на каждую линию работы. В 27 линиях из 30 векторы совпадают: обе ветки знают одну и ту же раннюю историю. А в трёх расходятся: outpost знает 85 коммитов своей ветки, а wind-tunnel — только 79, зато wind-tunnel знает 905 коммитов основной ветки против 897 и все 23 своих, о которых outpost не знает ничего. У каждого есть линия, где он знает больше, — значит, ни один не раньше другого. Числа Лэмпорта у них 1021 и 1037, и по ним этого не скажешь.
Идея
В распределённой системе «раньше» определяется не временем на часах, а знанием: событие a случилось раньше b, если сведения об a могли дойти до b — по цепочке событий одного процесса и сообщений между процессами. Часы Лэмпорта дают каждому событию число, которое растёт вдоль любой такой цепочки: раньше — значит меньше. Векторные часы дают каждому событию счётчик на каждый процесс: сколько его событий известно. Тогда «раньше» — это «вектор нигде не больше», а «параллельно» — «у каждого есть позиция, где он больше».
Почему не обычные часы? Часы разных машин расходятся, и сообщение, отправленное «в 12:00:00,005», может прийти на машину, где уже «12:00:00,003». По таким отметкам ответ выглядит пришедшим раньше вопроса. Как это видно на острове законодателей, рассказывает глава курса о распределённых системах; здесь — как логические часы устроены и что они стоят в настоящих системах.
В git отношение «раньше» видно прямо: коммит a раньше b, если a — предок b. Процессы — линии работы: основная ветка и каждая влитая ветка; событие — коммит; сообщение — слияние, которое приносит в одну линию всё, что знал коммит другой.
Часы Лэмпорта
Правило одно: число события на единицу больше наибольшего из чисел событий, о которых оно знает напрямую, — предыдущего события своего процесса и отправителей полученных сообщений. В git это число называется топологическим уровнем: у первого коммита 1, у остальных — на единицу больше, чем у старшего из родителей.
Если a случилось раньше b, то число Лэмпорта a меньше числа b.
Если a раньше b, есть цепочка a = e0, e1, …, ek = b, где каждое следующее событие знает предыдущее напрямую — как следующее событие процесса или как получатель сообщения. По правилу число каждого звена больше числа предыдущего хотя бы на единицу, и по цепочке L(a) < L(b).
Обратное неверно, и это главное ограничение. В сцене у параллельных коммитов числа 1021 и 1037: меньшее число не значит «раньше». По числам Лэмпорта можно упорядочить все события так, чтобы порядок не противоречил «случилось раньше», — для этого Лэмпорт их и придумал: например, чтобы все процессы одинаково решали, чей запрос на общий ресурс был первым. А вот отличить «раньше» от «параллельно» по ним нельзя.
Но и одно число полезно — git это доказывает. Чтобы узнать, предок ли коммит a коммита b, git идёт по истории назад от b. Если на пути встретился коммит с уровнем меньше уровня a, дальше от него идти бесполезно: все его предки ещё ниже, и a среди них быть не может. Переключите сцену на «обход графа»: на 500 случайных парах коммитов нашей истории обход без часов просматривает в среднем 412 коммитов, а с отсечением по уровням — 124.
Номера поколений git хранит в файле commit-graph. Первая их версия — ровно часы Лэмпорта. Вторая — «исправленная дата коммита»: время коммита, но не меньше даты любого родителя плюс единица. Это та же идея, что у гибридных логических часов, о которых ниже: число растёт вдоль истории, как часы Лэмпорта, но остаётся близко к настоящему времени. Её ввели, потому что для некоторых запросов уровни отсекали хуже, чем обычные даты: при поиске общего предка двух версий ядра Linux обход по уровням просматривал 635 579 коммитов, а по датам — 167 468. Голые даты при этом нельзя использовать для точных ответов: часы машины, где сделан коммит, могут отставать, и тогда ребёнок окажется «старше» родителя. В нашей истории таких коммитов нет — все сделаны на одной машине, — поэтому исправленные даты здесь совпадают с обычными и отсекают так же, как уровни: 125 коммитов на вопрос.
Векторные часы
Пусть процессов n. Каждое событие несёт вектор из n чисел: в позиции q — сколько событий процесса q оно знает. Новое событие процесса p берёт покомпонентный максимум векторов того, что оно знает напрямую, и увеличивает свою позицию p на единицу. Сообщение несёт вектор отправителя.
Событие a случилось раньше события b тогда и только тогда, когда вектор a ни в одной позиции не больше вектора b и a ≠ b. Более того, если a — i-е событие процесса p, то a раньше b ровно тогда, когда в векторе b в позиции p стоит не меньше i.
Индукцией по событиям: позиция q вектора события x равна числу событий процесса q, которые раньше x или совпадают с ним. Для первого события процесса это верно. Новое событие знает всё, что знает каждое событие, о котором ему известно напрямую, и ничего сверх того плюс себя; события процесса q идут цепочкой, и знать j-е из них — значит знать первые j. Поэтому максимум по позиции q и есть число известных событий q, а своя позиция растёт на одно — на само новое событие.
Теперь, если a раньше b, то b знает всё, что знает a, и вектор a нигде не больше. Наоборот: если a — i-е событие процесса p и в векторе b в позиции p стоит не меньше i, то b знает первые i событий p, в том числе a, — значит, a раньше b или это одно событие. Условие «вектор нигде не больше» включает это частное.
Вторая часть теоремы делает проверку быстрой: не нужно сравнивать векторы целиком, достаточно одной ячейки. Это первая задача статьи. Вторая — сосчитать все параллельные пары, не перебирая их: в нашей истории их 31 873 из 790 653, около 4 %. Ветки сайта живут недолго и вливаются часто, поэтому параллельного в истории немного.
Код
Листинг строит по истории git все три часов — уровни Лэмпорта, исправленные даты и векторы по тридцати линиям, — сравнивает последние коммиты «Форпоста» и трубы и на 500 случайных парах проверяет, что векторы отвечают так же, как обход графа, и сколько коммитов обходу нужно с часами и без.
Сколько это стоит
| Часы | На событие | В сообщении | Что умеют |
|---|---|---|---|
| Лэмпорта | одно число, O(1) | одно число | согласованы с «раньше»; «параллельно» не видят |
| векторные | n чисел, O(n) | n чисел | «раньше», «позже», «параллельно» — точно |
| гибридные | время и счётчик, O(1) | то же | как Лэмпорта, и близки к настоящему времени |
Цена векторных часов — длина вектора, и обойти её нельзя. Бернадетт Шарон-Бо в 1991 году доказала, что для n процессов отличать «раньше» от «параллельно» по отметкам событий в общем случае можно только с векторами не короче n. Тридцать чисел на коммит — пустяк. У репозитория ядра Linux веток тысячи, и git векторов не хранит: ему хватает одного числа поколения и обхода, который это число обрезает.
Версионные векторы
В реплицированных хранилищах та же идея стоит на каждом значении: у каждой копии счётчик, и вектор при значении говорит, какие записи оно учитывает. Если две копии приняли записи одного ключа, не зная друг о друге, их векторы несравнимы — это параллельные записи, и хранилище сохраняет обе, чтобы приложение решило, как их объединить, а не выбрасывает одну молча. Так делало хранилище Dynamo, описанное в 2007 году; чтобы векторы не росли бесконечно с числом узлов, оно отбрасывало самые старые пары, когда их становилось больше порога, — и признавало, что тогда «раньше» иногда не отличить от «параллельно». Riak пошёл дальше: точечные версионные векторы отделяют саму запись — «точку», пару «копия, номер» — от знания о прошлом, и их размер ограничен числом копий, а не клиентов. С ними хранилище не плодит лишних параллельных версий, когда через одну копию пишут много клиентов.
Если же векторы слишком дороги, берут гибридные логические часы, предложенные в 2014 году: отметка — пара «физическое время, счётчик», и при получении сообщения время берётся как максимум своего, пришедшего и физического, а счётчик различает события с одинаковым временем. Такие часы, как часы Лэмпорта, не противоречат порядку «раньше» и при этом почти совпадают с настоящим временем — ровно то, что git делает исправленными датами. На них работают CockroachDB и MongoDB.
История
Лесли Лэмпорт определил отношение «случилось раньше» и логические часы в статье 1978 года «Time, Clocks, and the Ordering of Events in a Distributed System». Векторные часы в начале 1980-х появлялись у нескольких авторов, а имя и теорию дали в 1988 году независимо друг от друга Колин Фидж и Фридеман Маттерн. Версионные векторы для копий файлов описали ещё в 1983 году. Git с 2018 года хранит граф коммитов в отдельном файле вместе с номерами поколений, а позже перешёл на исправленные даты.
Задачи
Первая — векторные отметки и ответы «раньше, позже, параллельно» за одно обращение к памяти. Вторая — сколько всего параллельных пар в журнале, без перебора пар.
Векторные отметки Параллельные парыДанные: Граф коммитов legost.in (git, до 16.10.2026)