ИИтог

Гибридные логические часы: как совместить причинность и физическое время в распределённых базах данных

исследованияРедакция ИИтогHacker News🔥33Рейтинг ИИтог · значимость 33 · 8 баллов · 1 коммент.

Технический отчёт «Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases» (авторы: Sandeep Kulkarni, Murat Demirbas, Deepak Madeppa, Bharadwaj Avva, Marcelo Leone; Michigan State University и University at Buffalo, SUNY) разбирает давний разрыв между теорией распределённых систем и её практикой в вопросе времени. Теория со времён работы Лэмпорта 1978 года использует логические часы (LC), они дают строгий причинно-следственный порядок событий (happened-before), но никак не привязаны к реальному времени и требуют, чтобы все взаимодействия шли через обмен сообщениями. Практика же полагается на физические часы, синхронизированные по протоколу NTP: они дают привязку к реальному времени, но страдают от неустранимой погрешности синхронизации (обычно десятки миллисекунд в интернете, около миллисекунды в локальной сети) и от «сбоев» вроде високосных секунд и немонотонных корректировок времени, из-за которых метки могут идти назад. Google для Spanner предложил TrueTime (TT), аппаратное решение на GPS- и атомных часах с явным интервалом неопределённости; чтобы гарантировать корректный порядок транзакций, Spanner вынужден «ждать» (commit-wait), пока интервал неопределённости не пройдёт, что снижает пропускную способность на запись и требует специального оборудования, недоступного на арендованных облачных машинах.

Авторы предлагают Hybrid Logical Clocks (HLC), метку времени из двух компонентов: l (близко к максимальному увиденному физическому времени) и c (счётчик, растущий только когда l не меняется, чтобы упорядочить события внутри одного и того же физического «тика»). Наивная версия алгоритма (l := max(l+1, pt)) на практике даёт неограниченный дрейф между l и физическими часами, авторы показывают контрпример на 4 узлах с циклом обмена сообщениями, где разница l−pt растёт бесконечно. Корректный алгоритм разделяет l и c и добавляет правило сброса c при обновлении l, что и позволяет доказать (4 теоремы и 4 следствия) три свойства: (1) HLC сохраняет причинность так же строго, как логические часы Лэмпорта; (2) отклонение l от физического времени ограничено величиной ε (примерно удвоенным NTP-офсетом); (3) счётчик c остаётся ограниченным (в худшем теоретическом случае, O(N·(ε+1)), на практике, единицы). HLC укладывается в стандартный 64-битный формат NTP-метки: 48 бит отводится под l (округлённое до микросекунды физическое время), 16 бит, под c (счётчик до 65536). Важное свойство, HLC работает как надстройка над NTP: только читает физические часы узла, но никогда их не меняет, поэтому не мешает другим процессам, зависящим от NTP, и одинаково хорошо работает как peer-to-peer в WAN-развёртывании, так и в клиент-серверной модели, причём разные узлы могут использовать разные NTP-серверы.

Авторы реализовали HLC и провели эксперименты на AWS (инстансы xlarge, Ubuntu 14.04, синхронизация с публичным stratum-2 NTP-сервером 0.ubuntu.pool.ntp.org), прогнав от 75 000 до 425 000 сообщений между узлами. В одном дата-центре с 4 узлами при офсете NTP 5 мс счётчик c не превышал 4 почти в 84% событий, максимальная разница l−pt составила 21,7 мс; с 8 узлами при офсете 9 мс максимальный разброс достиг 107,9 мс; с 16 узлами при офсете 16 мс, 90,5 мс. В WAN-развёртывании на 4 узлах в разных регионах AWS (Ирландия, US East, US West, Токио) при офсете NTP около 3 мс счётчик c был равен 0 в 95% случаев и 1 в оставшихся 5%, а разброс l−pt не превышал 0,02 мс, заметно ниже, чем в одном дата-центре, потому что задержки сообщений через WAN сами по себе больше, чем погрешность синхронизации ε. В стресс-тестах в симуляции (частота событий, 1 в миллисекунду, дрейф часов 10, 100 мс) счётчик c оставался ≤4 более чем в 99% случаев независимо от числа узлов. Отдельно проверили устойчивость к «отстающему» узлу (постоянно держащемуся у границы допустимого дрейфа или превышающему её в 5 раз, счётчик c у него самого мог доходить до 514, но на другие узлы это не распространялось) и к «спешащему» узлу (максимальный c в этих экспериментах, 8, при доле событий с c>3 менее 1%).

Главное практическое применение, согласованные снимки состояния (consistent snapshots) в многоверсионных распределённых базах данных: чтобы получить согласованный снимок на момент времени t, достаточно прочитать состояние на каждом узле в момент, когда его l равно t (с c=0), существование такого события гарантируется благодаря концепции «виртуальных фиктивных событий», введённой авторами. В отличие от TrueTime/Spanner, здесь не нужно ждать, пока пройдёт интервал неопределённости, HLC фиксирует причинно-следственные связи внутри самого интервала неопределённости за счёт правил обновления. Алгоритм также самостабилизируется: если физические часы узла временно испортились (в том числе из-за произвольной порчи переменных l и c), после восстановления NTP-синхронизации HLC автоматически возвращается в корректное состояние, а при выходе l−pt за заданный предел Δ срабатывает защитный механизм сброса и игнорирования подозрительных сообщений с журналированием инцидента.

Ключевые факты

  • HLC, гибрид логических часов Лэмпорта и физических NTP-часов: метка из пары (l, c), где l держится близко к физическому времени, а c, счётчик для упорядочивания событий внутри одного и того же физического момента.
  • Метка умещается в стандартный 64-битный формат NTP (48 бит под l, 16 бит под c) и только читает физические часы узла, не изменяя их, работает поверх NTP без вмешательства в другие процессы.
  • Позволяет снимать согласованные снимки распределённой БД без ожидания «окна неопределённости», в отличие от TrueTime в Google Spanner, которому для этого нужны атомные/GPS-часы и задержки commit-wait.
  • Эксперименты на AWS (4, 16 узлов, один дата-центр и WAN на 4 регионах, Ирландия, US East, US West, Токио) показали: счётчик c почти всегда меньше 4, разброс между логическим и физическим временем, единицы-десятки миллисекунд в одном дата-центре и около 0,02 мс в WAN.
  • Алгоритм самостабилизируется и устойчив к произвольной порче переменных часов; отдельно проверена устойчивость к «отстающим» и «спешащим» узлам.

Почему это важно

Теория распределённых систем и их практика десятилетиями расходились в вопросе времени. Логические часы Лэмпорта (1978) дают строгий причинно-следственный порядок событий, но не привязаны к реальному времени и требуют, чтобы все взаимодействия шли через явный обмен сообщениями. Физические часы, синхронизированные по NTP, дают привязку к реальному времени, но подвержены погрешности синхронизации и сбоям вроде немонотонных корректировок времени. Google для Spanner решил эту проблему аппаратно, часами TrueTime на GPS и атомных часах, но это требует специального оборудования, недоступного на обычных облачных инстансах, и вынуждает транзакции «ждать» интервал неопределённости перед подтверждением (commit-wait), что снижает пропускную способность на запись. HLC предлагает программное решение той же задачи без этих издержек.

Кому это важно

Работа адресована разработчикам распределённых баз данных и многоверсионных хранилищ ключ-значение, которым нужны согласованные снимки состояния между узлами, а также авторам протоколов причинного логирования сообщений, byzantine fault-tolerance протоколов, распределённых файловых систем и распределённых транзакций, то есть всей инфраструктуре, где важно упорядочить события в разных частях системы без выделенного аппаратного обеспечения (GPS, атомные часы), которого нет на обычных арендованных облачных узлах.

Как это применить

HLC хранит метку из двух компонентов: l, приближение к физическому времени (максимум из собственных часов узла и всех меток времени, полученных в сообщениях), и c, счётчик, увеличивающийся только тогда, когда l не меняется, чтобы разрешить порядок событий внутри одного и того же физического момента. Метка укладывается в стандартный 64-битный формат NTP: 48 бит на l с округлением до микросекунды, 16 бит на c (счётчик до 65536). HLC работает как надстройка над NTP, только читает физические часы, никогда их не меняет, поэтому не мешает другим процессам и работает как peer-to-peer в WAN, так и в клиент-серверной модели, причём разные узлы вправе использовать разные NTP-серверы. Для согласованного снимка на момент t достаточно прочитать состояние каждого узла в момент, когда его l равно t (с c=0), такое событие гарантированно существует благодаря введённой авторами концепции «виртуальных фиктивных событий». Реализация авторов выложена в открытый доступ на GitHub (в анонимизированном для рецензирования виде, под именем AugmentedTimeProject).

Можно ли доверять

Заявленные свойства HLC подкреплены формальными доказательствами (4 теоремы и 4 следствия): сохранение причинности не хуже, чем у логических часов Лэмпорта, ограниченность отклонения от физического времени величиной ε и ограниченность счётчика c. Помимо теории, авторы провели эксперименты на AWS: кластеры из 4, 8 и 16 узлов в одном дата-центре и в WAN-развёртывании на 4 регионах (Ирландия, US East, US West, Токио), с прогоном от 75 000 до 425 000 сообщений. Во всех сценариях счётчик c оставался низким (в стресс-тестах, ≤4 более чем в 99% событий), а отклонение от физического времени укладывалось в единицы-десятки миллисекунд в одном дата-центре и было пренебрежимо малым в WAN. Отдельно проверена устойчивость к «отстающему» и «спешащему» узлам, система оставалась ограниченной и не распространяла аномалии на остальные узлы.

Риски и подводные камни

«Отстающий» узел (чьи часы значительно отклонились от общего темпа) может резко раздуть собственный счётчик c, в одном из симуляционных тестов до 514 при отклонении в 5ε, хотя это не сказывалось на других узлах системы. Работоспособность HLC по-прежнему зависит от качества NTP-синхронизации: при выходе разницы l−pt за установленный предел Δ срабатывает защитный механизм сброса и игнорирования подозрительных сообщений, то есть система деградирует к поведению обычных физических часов. Это технический отчёт 2014 года с бенчмарками на инфраструктуре AWS того периода (Ubuntu 14.04, инстансы xlarge), реальные production-нагрузки и сетевые условия в 2026 году могут отличаться от протестированных сценариев.

«Любую проблему в информатике можно решить, добавив ещё один уровень косвенности.»

— Дэвид Уилер, эпиграф к разделу об алгоритме HLC