Кажется, что время — это просто. Но мы, инженеры, теряем сон из-за такой простой задачи, как синхронизация часов.
Причина этого в том, что не существует каких-то глобальных часов. У нас есть тысячи машин, распределённых по дата-центрам, континентам и часовым поясам; каждая из них работает независимо от других, поэтому ответ на простой вопрос «сколько сейчас времени?» оказывается на удивление сложным.
Синхронизация часов становится основой самых сложных задач в распределённых системах, она влияет на всё, от согласованности баз данных и отладки до финансовых транзакций.
Иллюзия точного времени
У каждого компьютера есть внутренние часы, обычно управляемые кварцевым резонатором. При подаче напряжения на эти резонаторы они колеблются на определённой частоте. Для большинства компьютерных часов стандартом выбрана частота 32768 Гц, потому что она является степенью двойки и упрощает подсчёт с точностью до одной секунды.
Однако проблема в том, что кварцевые кристаллы неидеальны. Эта частота колебаний зависит от множества факторов.
Самый важный — это температура. У стандартных кварцевых кристаллов дрейф частот при изменении температуры может составлять до десятков частей на миллион. Изменение температуры примерно на 10 градусов Цельсия может вызывать дрейф, эквивалентный примерно 110 секундам в год. В зависимости от температуры окружающей среды кристалл колеблется быстрее или медленнее, а окружающая среда в дата-центрах контролируется неидеально.
Ещё один фактор — различия при производстве. Невозможно найти двух идентичных кристаллов. Кристаллы даже из одной производственной партии будут иметь немного различающиеся характеристики. Усугубляет эту проблему старение, потому что свойства кристаллов со временем меняются.
В результате этого у двух компьютеров, включённых одновременно, но не обменивающиеся информацией друг с другом, неизбежно возникнет дрейф. Спустя всего один день показания их часов могут различаться на сотни миллисекунд. Спустя месяц разница будет измеряться в секундах.
Почему рассинхронизация часов приводит к поломкам
Рассинхронизация — это разница во времени двух часов в конкретный момент времени. Дрейф — это скорость, с которой показания часов расходятся со временем. Оба этих фактора вызывают серьёзные проблемы в распределённых системах.
Рассмотрим простой пример с распределённой системой make. Вы редактируете файл исходников на своей клиентской машине, часы которой слегка отстают от часов сервера, где находятся скомпилированные объектные файлы. При выполнении make она сравнивает временные метки. Если часы сервера опережают часы клиента, то кажется, что объектный файл новее, чем отредактированный вами файл исходников, и make не выполнит повторную компиляцию. Ваши изменения незаметно пропадут из сборки.
Сценарий: make UNIX с рассинхронизованными часами
Часы на клиентской машине: 10:00:00 (отстают)
Часы на сервере: 10:00:05 (опережают)
1. Редактируем util.c во время клиента 10:00:00
2. util.o на сервере имеет временную метку 10:00:03
3. Make выполняет сравнение: util.o (10:00:03) и util.c (10:00:00)
4. Вывод: util.o новее, повторная компиляция не выполняется
5. Результат: ваши изменения игнорируютсяСистемы баз данных сталкиваются с ещё более критичными проблемами временных меток. Когда на разных узлах примерно в одно и то же время происходят две транзакции, база данных должна определить, какая произошла первой. Если часы рассинхронизированы, база данных может упорядочить их неправильно, нарушая гарантии согласованности.
Представьте банковскую систему, в которой клиент кладёт деньги на депозит в одном отделении (Узел A) и мгновенно снимает их в другом (Узел Б). Если часы Узла Б отстают от часов Узла A, транзакция снятия может получить временную метку раньше, чем транзакция депозита. Снэпшот, сделанный в неподходящее время, может отразить только снятие, но не депозит, из-за чего может показаться, что клиент снял деньги, которых у него не было.
При рассинхронизации часов практически невозможными становятся логгинг и отладка. В распределённых трассировках для воссоздания событий сервисов применяются временные метки. При рассинхронизации часов в трассировках будут отображаться невозможные последовательности, в которых причины и следствия поменялись местами.
Физическая синхронизация часов
Простейшее решение для синхронизации часов заключается в периодической отправке запросов надёжному серверу времени и соответствующей настройке локальных часов. Давайте рассмотрим различные алгоритмы и решения, основанные на нём.
Алгоритм Кристиана
Предложенный в 1989 году алгоритм Кристиана работает с централизованным сервером времени, который считается источником точного времени. Клиент запрашивает время, сервер отправляет ему ответ с текущим временем, и клиент настраивает свои часы.
Сложность заключается в сетевых задержках. Ко времени прибытия ответа время сервера устареет. В алгоритме Кристиана задержка в одну сторону принимается равной половине времени передачи данных туда-обратно.
# Алгоритм Кристиана
def synchronize_clock():
t0 = local_time() # Записываем время перед запросом
server_time = request_time_from_server()
t1 = local_time() # Записываем время после запроса
round_trip = t1 - t0
one_way_delay = round_trip / 2
# Меняем показания локальных часов
new_time = server_time + one_way_delay
set_local_clock(new_time)
# Пределы погрешности: +/- (t1 - t0) / 2Когда сетевые задержки симметричны (то есть когда для запроса и ответа требуется одинаковое время), такая система работает относительно неплохо. Однако на практике задержки часто бывают асимметричными из-за разных путей маршрутизации, варьирующейся загруженности сети и задержек при обработке.
Алгоритм Беркли
В этом алгоритме используется другой подход, в котором предполагается, что ни на одной машине нет точного времени. Вместо него используется консенсус среди множества машин.
Специальный демон времени периодически опрашивает значения часов у всех машин. Он вычисляет среднее, отсекает выбросы и сообщает каждой машине, на сколько ей нужно исправить показания. Вместо того, чтобы посылать абсолютные значения времени, на которые могут влиять сетевые задержки, он передаёт относительные изменения.
Этапы алгоритма Беркли:
1. Демон времени опрашивает машины: "Сколько у вас сейчас времени?"
2. Ответы: Машина A: 10:00:05, Машина Б: 10:00:02, Машина В: 10:00:08
3. Показания часов демона времени: 10:00:04
4. Среднее: (5 + 2 + 8 + 4) / 4 = 4.75 → 10:00:05
5. Отправляемые исправления:
- Машина A: замедлись на 0 с (уже имеет нужное время)
- Машина Б: ускорься на 3 с
- Машина В: замедлись на 3 с
- Демон: ускорься на 1 сОчень важная деталь: компьютеры никогда не должны переводить свои часы назад скачком. Это нарушило бы допущение о монотонном времени, от которого зависят многие алгоритмы. Для синхронизации алгоритм Беркли вместо перемотки постепенно замедляет часы.
Network Time Protocol
В NTP используется иерархическая модель серверов времени, упорядоченных в страты.
Устройства страты 0 — это высокопрецизионные источники времени, например, атомные часы и GPS-приёмники. Серверы страты 1 соединены непосредственно с источниками страты 0. Каждая более низкая страта синхронизируется с уровнем выше; страт может быть до пятнадцати.
В публичном Интернете NTP обычно поддерживает точность времени в пределах десятков миллисекунд, а в локальных сетях может достигать погрешности меньше миллисекунды. Однако его точность ограничивает множество факторов.
Пределы точности NTP:
- Публичный Интернет: обычно 10-100 мс
- LAN с хорошими условиями: 100-500 мкс
- Асимметрия сети: может вызывать погрешности до 100+ мс
- Переменные задержки: добавляют неустойчивость
- Задержки операционных систем: временные метки ПО добавляют микросекундыОсобенно проблематична асимметрия сети. Если путь от клиента до сервера отличается от пути от сервера до клиента, то нарушается допущение о том, что односторонняя задержка равна половине времени пути туда-обратно. Классический пример этого — спутниковая связь, при которой восходящий и нисходящий каналы имеют разные задержки.
Оверхед операционных систем добавляет неопределённость. При поступлении пакета NTP он проходит через сетевой стек, получает временную метку ядра, а затем достигает демона NTP. Каждый этап добавляет задержки переменной величины в микросекундах.
Миллисекунд недостаточно
Для многих сфер применения точности NTP достаточно. Веб-серверы, файловые системы и большинство бизнес-приложений вполне допускают различия в десятки миллисекунд. Однако в некоторых сферах требуется более чёткая синхронизация.
В финансовых трейдинговых системах задержки измеряются в микросекундах. Транзакция, временная метка которой неверна всего на несколько миллисекунд, может иметь существенные юридические и финансовые последствия. Для стратегий высокочастотного трейдинга важно знать точный порядок событий.
Телекоммуникационным системам синхронизация требуется для TDM (Time Division Multiplexing), при котором разные пользователи по очереди занимают общий канал. В случае дрейфа таймингов происходит конфликт передач от разных пользователей.
В научных экспериментах, особенно в физических, для корреляции измерений между инструментами требуется наносекундная точность.
Precision Time Protocol
PTP, определённый в IEEE 1588, достигает точности меньше микросекунды благодаря аппаратному добавлению временных меток. Вместо того, чтобы время прибытия пакета записывала операционная система, специализированный сетевой интерфейс ставит временные метки на пакеты при получении, устраняя программные задержки.
Сравнение точности PTP и NTP:
- NTP: миллисекунды (программные временные метки)
- PTP: наносекунды (аппаратные временные метки)
Основные преимущества PTP:
- Аппаратные временные метки на уровне NIC
- Граничные часы в коммутаторах, поддерживающие точность
- Двухсторонний обмен сообщениями вычисляет асимметричные задержкиPTP требует поддержки на всём сетевом пути. Коммутаторы должны знать о PTP и использоваться в качестве граничных часов, поддерживающих синхронизацию между сетевыми сегментами.
В 2022 году компания Meta*объявила о миграции с NTP на PTP в своих дата-центрах. Инвестиции в инфраструктуру PTP оправдали себя снижением погрешностей и расширением возможностей отладки.
Логические часы и причинно-следственные связи
Исходя из простого наблюдения, Лесли Лэмпорт предложил концепцию логических часов: если два события связаны, как причина и следствие, то мы можем их упорядочить. Если событие А отправляет сообщение, получаемое событием Б, то А произошло до Б. Если оба события происходят в одном процессе, более раннее происходит до более позднего.
События, не объединённые причинно-следственной связью, считаются конкурентными. Они могли произойти в любом порядке, и, с точки зрения системы, его невозможно определить.
Временные метки Лэмпорта
Это наблюдение реализовано в простом алгоритме временных меток Лэмпорта. Каждый процесс имеет свой счётчик. Перед любым событием он увеличивает значение счётчика. При отправке сообщения в него включается значение счётчика. При получении сообщения счётчик устанавливается на максимальное значение из текущего и полученного, а затем выполняется инкремент.
class LamportClock:
def __init__(self):
self.time = 0
def local_event(self):
self.time += 1
return self.time
def send_event(self):
self.time += 1
return self.time # Включается в сообщение
def receive_event(self, received_time):
self.time = max(self.time, received_time) + 1
return self.timeЕсли временная метка Лэмпорта у события А меньше, чем у события Б, это значит одно из двух: или А произошло до Б, или они конкурентны. Обратное гарантировано: если A произошло до Б, То временная метка А меньше, чем у Б.
Процесс P1: [0] ---(1)---> отправка m ---(2)---> локальное событие
|
v
Процесс P2: [0] --------> получение m ---(2)---> локальное событие ---(3)
События P1: (1, 2)
События P2: (2, 3)
Получение на P2 происходит после отправки на P1 (причинно-следственная связь сохранена)Ограничение заключается в том, что временные метки Лэмпорта не могут сообщить нам, конкурентны ли два события. События с временными метками 5 и 7 могут иметь причинно-следственную связь или произойти независимо в разных процессах без коммуникации между ними.
Векторные часы
Векторные часы дополняют временные метки Лэмпорта, позволяя записывать всю информацию о причинно-следственных связях. Вместо одного счётчика каждый процесс хранит вектор с записями всех процессов системы.
class VectorClock:
def __init__(self, process_id, num_processes):
self.id = process_id
self.clock = [0] * num_processes
def local_event(self):
self.clock[self.id] += 1
return self.clock.copy()
def send_event(self):
self.clock[self.id] += 1
return self.clock.copy()
def receive_event(self, received_clock):
for i in range(len(self.clock)):
self.clock[i] = max(self.clock[i], received_clock[i])
self.clock[self.id] += 1
return self.clock.copy()
@staticmethod
def compare(vc1, vc2):
less = any(vc1[i] < vc2[i] for i in range(len(vc1)))
greater = any(vc1[i] > vc2[i] for i in range(len(vc1)))
if less and not greater:
return "vc1 happened before vc2"
elif greater and not less:
return "vc2 happened before vc1"
elif not less and not greater:
return "equal"
else:
return "concurrent"Сравнение двух векторных часов точно сообщает нам, произошло ли одно событие до другого или конкурентны ли они. Если каждая запись в VC1 меньше или равна соответствующей записи в VC2, и хотя бы одна строго меньше, то VC1 произошло до VC2.
Пример векторных часов (3 процесса: P1, P2, P3):
P1: [1,0,0] ---> [2,0,0] ---отправка m---> [3,0,0]
|
P2: [0,1,0] ---------> [0,2,0] ---получение m---> [3,3,0]
P3: [0,0,1] ---> [0,0,2]
Сравниваем [2,0,0] и [0,0,2]:
- 2 > 0 (первый элемент)
- 0 < 2 (третий элемент)
Результат: КОНКУРЕНТНОСТЬ (причинно-следственная связь отсутствует)
Сравниваем [2,0,0] и [3,3,0]:
- 2 < 3 (первый элемент)
- 0 < 3 (второй элемент)
Результат: [2,0,0] произошло до [3,3,0]Недостаток векторных часов — оверхед занимаемого места. При N процессах каждая временная метка требует O(N) пространства. В случае больших распределённых систем с тысячами узлов такая система перестаёт быть практичной. Существуют различные её оптимизации, в том числе сжатые векторные часы и часы деревьев интервалов, однако фундаментальная проблема масштабирования никуда не пропадает.
Google Spanner и TrueTime
В беспрецедентных масштабах с проблемой синхронизации часов Google столкнулась при работе с глобальной распределённой базой данных Spanner. Компании требовались надёжные гарантии согласованности между дата-центрами на разных континентах, для чего необходимо было знать порядок транзакций.
Я объяснял это в своём видео.
Решением компании стала TrueTime — глобальная распределённая инфраструктура часов, сообщающая время с ограниченной неопределённостью.
Для каждого дата-центра TrueTime использует два типа источников времени. GPS-приёмники получают время непосредственно со спутников. Атомные часы обеспечивают резервирование и перекрёстную валидацию. Использование обоих типов обеспечивает надёжность, поскольку они имеют независимые режимы отказа. Сбой GPS может быть вызван проблемами с антеннами или помехами сигнала. У атомных часов может возникать дрейф, но на них не влияют те же проблемы.
Ключевой инновацией стало то, что TrueTime возвращает не одну временную метку, а интервал, гарантированно содержащий истинное время.
- TT.now() возвращает [earliest, latest]
- Истинное время гарантированно будет находиться внутри этого интервала
- Ширина интервала - это предел неопределённости ε
- TT.after(t) возвращает true, если t точно находилось в прошлом
- TT.before(t) возвращает true, если t точно находится в будущем
Типичная степень неопределённости: 1-7 миллисекундПри коммите транзакции Spanner она получает временную метку. Перед тем, как сообщить о коммите клиенту, Spanner ждёт, пока TT.after(commit_timestamp) не вернёт true. Это «ожидание коммита» гарантирует, что любая последующая транзакция, начавшаяся после ожидания, получит более позднюю временную метку.
Ожидание коммита Spanner:
1. Транзакция T1 подготавливается к коммиту
2. T1 получает временную метку коммита ts = TT.now().latest
3. T1 ждёт, пока TT.after(ts) не вернёт true
4. T1 сообщает о коммите клиенту
Почему это работает:
- После ожидания мы точно знаем, что ts произошла в прошлом
- Любая транзакция T2, начинающаяся после этой точки,
получит временную метку > ts
- Следовательно: коммит T1 выполнен до начала T2 → ts(T1) < ts(T2)
- Внешняя согласованность сохраненаВ худшем случае период ожидания обычно примерно равен 7 миллисекундам. Кажется, что это существенное повышение задержек, но на самом деле оно накладывается на обработку других коммитов, а высокая степень согласованности в случае Spanner оправдывает затраты.
Гибридные логические часы
Не у всех есть ресурсы Google, позволяющие установить атомные часы в каждом дата-центре. CockroachDB, вдохновлённая Spanner, но предназначенная для работы на обычном оборудовании, использует гибридные логические часы (hybrid logical clock, HLC).
У меня был подкаст с ведущим архитектором CockroachDB Беном Дарнеллом, где мы подробно обсудили эту тему.
HLC комбинирует физическое время с логическим компонентом. Физическая часть остаётся близкой к тому, что показывают физические часы. Логическая часть обрабатывает случаи, когда множественные события происходят в пределах одного такта физических часов или когда рассинхронизация часов вызывает проблемы.
class HybridLogicalClock:
def __init__(self):
self.physical = 0 # Физическое время
self.logical = 0 # Логический счётчик
def now(self, wall_time):
if wall_time > self.physical:
self.physical = wall_time
self.logical = 0
else:
self.logical += 1
return (self.physical, self.logical)
def receive(self, wall_time, received_physical, received_logical):
if wall_time > self.physical and wall_time > received_physical:
self.physical = wall_time
self.logical = 0
elif received_physical > self.physical:
self.physical = received_physical
self.logical = received_logical + 1
elif self.physical > received_physical:
self.logical += 1
else: # Равные показания физического времени
self.logical = max(self.logical, received_logical) + 1
return (self.physical, self.logical)HLC обладает свойством близости временных меток к физическому времени, что упрощает отладку. Взглянув на временную метку HLC, можно приблизительно понять, когда произошло событие. Логический компонент гарантирует всегда правильный порядок событий, находящихся в причинно-следственной связи, даже в случае рассинхронизации физических часов.
Физические часы Узла А: 100
Физические часы Узла Б: 98 (немного отстают)
Событие Узла А: HLC = (100, 0)
Узел А отправляет сообщение Узлу Б
Узел Б получает его в своё физическое время 99:
- Полученное HLC = (100, 0)
- Локальное физическое время = 99
- Так как 100 > 99: новое HLC = (100, 1)
Событие Узла Б корректно располагается после события Узла А, несмотря на отставание
физических часов Узла Б.CockroachDB применяет HLC с конфигурируемым максимальным смещением часов; обычно в локальном окружении оно равно 500 миллисекундам. Если узел обнаруживает, что его часы слишком далеки от остальных, то он удаляет себя из кластера вместо того, чтобы рисковать нарушением согласованности.
YugabyteDB тоже использует HLC и недавно интегрировалась с AWS Time Sync Service для более плотной синхронизации. Бенчмарки разработчиков показали снижение задержек вплоть до троекратного при транзакциях с использованием прецизионных источников времени, потому что благодаря малым границам неопределённости время ожидания при транзакциях снижается.
Как выбрать подходящую систему
Выбор детализированности синхронизации
Какой уровень синхронизации нужен вам на самом деле? Многим системам вполне подходит NTP, обеспечивающий миллисекундную точность. Если ваши транзакции и так требуют десятки миллисекунд, рассинхронизация часов на менее чем миллисекунду не важна.
Если вам нужны строгие гарантии упорядочивания, то задумайтесь о том, достаточно ли будет логических часов. Временные метки Лэмпорта просты в реализации и имеют нулевой оверхед занимаемого пространства: достаточно лишь одного integer на сообщение.
В случае баз данных, требующих внешней согласованности, или систем, для которых важно физическое время (логи аудитов, финансовые записи), следует инвестировать в улучшение инфраструктуры синхронизации. Оборудование PTP, выделенные серверы времени и продуманная сетевая архитектура могут обеспечить точность в пределах микросекунд.
Работа с аномалиями часов
Часы могут перепрыгивать назад. NTP может внезапно исправить часы, дрейф которых был слишком большим. Миграции виртуальных машин могут вызвать разрывы в показаниях часов. Баги операционных систем могут приводить к скачкам времени.
Устойчивые системы распознают подобные аномалии. Они отслеживают частоту изменений часов и сообщают о внезапных скачках. Никогда не следует использовать сырое системное время для критичных случаев упорядочивания; применяйте абстракцию часов, способную обрабатывать аномалии.
class SafeClock:
def __init__(self):
self.last_time = 0
self.offset = 0
def now(self):
system_time = get_system_time()
if system_time < self.last_time:
# Часы скакнули назад!
# Регулируем смещение для обеспечения монотонности
self.offset += (self.last_time - system_time) + 1
log_warning("Clock jumped backward")
result = system_time + self.offset
self.last_time = result
return resultРабота с високосной секундой
Иногда в течение времени вставляются високосные (корректировочные) секунды для согласования UTC с вращением Земли. Минута с високосной секундой содержит 61 секунду. Многие системы плохо справляются с такой ситуацией.
Високосная секунда: 2016-12-31 23:59:60 UTC
Сценарии возникновения проблем:
- Вылет систем, предполагающих, что в минутах всегда по 60 секунд
- При планировании на основе времени создаются дубликаты событий
- В логах появляются невозможные временные метки
Решение:
- Размазывание високосной секунды: постепенное регулирование в течение нескольких часов (Google, AWS)
- Пошаговая регулировка: изменение часов скачком (традиционный NTP)
- Игнорирование: применение TAI вместо UTC (в специализированных системах)Google и AWS используют «размазывание високосной секунды», при котором эта секунда распределяется на долгий период времени, из-за его каждая секунда становится немного длиннее или короче. Это позволяет избежать разрывов, но часы в период размазывания не будут точно соответствовать UTC.
Радостная новость заключается в том, что Международное бюро мер и весов решило к 2035 году перестать добавлять високосные секунды, что позволяет устранить эту проблему в системах будущего.
Фундаментальный компромисс
Синхронизация часов в распределённых системах всегда требует компромисса между точностью, задержками и сложностью.
Плотная синхронизация требует или качественного оборудования (атомных часов, GPS, коммутаторов с поддержкой PTP), или дополнительного оверхеда коммуникаций (частых сообщений синхронизации, протоколов обеспечения консенсуса). За оба эти решения приходится расплачиваться.
Мягкая синхронизация дешевле, но временные метки при ней будут менее надёжными. Придётся или встраивать в алгоритмы расширенные пределы безопасности, или смириться с пониженными гарантиями упорядоченности.
Логические часы полностью обходятся без физического времени, но требуют передачи информации о часах в каждом сообщении и не могут сообщить, когда на самом деле произошло событие.
Какого-то единого правильного решения нет, оно зависит от ваших требований, бюджета и допустимой сложности.
Заключение
Синхронизация часов — интересная и сложная задача, решения которой находятся в спектре от простого NTP до инфраструктуры атомных часов Google для глобальных баз данных.
Важно осознать, что идеальная синхронизация невозможна, а потому при выборе системы необходимо выбирать подходящие границы и компромиссы.