Логические и физические часы

Логические часы упорядочивают события по причинно-следственной связи без привязки к реальному времени, в то время как синхронизация физических часов поддерживает реальное время отдельных машин близким друг к другу, несмотря на дрейф.

Definition

Логические часы присваивают каждому событию целочисленную метку времени, которая монотонна в каждом процессе и увеличивается при обмене сообщениями, фиксируя причинно-следственный порядок; синхронизация физических часов — это процесс настройки аппаратных часов машин таким образом, чтобы они показывали приблизительно одно и то же реальное время.

Scope

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

Core questions

• Как можно присваивать метки времени таким образом, чтобы они соответствовали причинно-следственному отношению «произошло до»?
• Как строится согласованный полный порядок событий на основе логических часов?
• Насколько точно можно синхронизировать физические часы при переменной задержке сети и дрейфе?

Key theories

Логические часы Лэмпорта

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

Вероятностная синхронизация и синхронизация по времени кругового обхода

Метод Кристиана оценивает удаленные часы путем измерения времени кругового обхода и предположения о симметричной задержке, обеспечивая вероятностные границы ошибки синхронизации, достижимой по сети.

Протокол сетевого времени (NTP)

NTP организует серверы времени в стратифицированную иерархию и использует статистическую фильтрацию повторных измерений смещения для синхронизации часов по всему Интернету с точностью до миллисекунд.

Clinical relevance

Логические часы упорядочивают операции в реплицированных хранилищах и очередях сообщений, не доверяя показаниям реального времени, в то время как физическая синхронизация лежит в основе баз данных, упорядоченных по меткам времени, распределенной трассировки и протоколов безопасности, которые зависят от ограниченной ошибки часов.

History

Статья Лэмпорта 1978 года о логических часах переосмыслила время в распределенных системах как причинное, а не физическое понятие; параллельно Кристиан и другие разработали вероятностную синхронизацию, а NTP Миллса стал стандартным механизмом для выравнивания интернет-часов.

Debates

Логическое против физического времени для упорядочивания операций

Логические часы гарантируют причинную корректность без доверия к аппаратным часам, но не могут связывать события с реальным временем; физические часы позволяют рассуждать в реальном времени с риском неправильного упорядочивания, когда дрейф превышает задержку сообщения, что мотивирует гибридные подходы.

Key figures

• Leslie Lamport
• Flaviu Cristian
• David Mills

Seminal works

• lamport1978
• mills1991
• cristian1989

Frequently asked questions

Если метка времени Лэмпорта для события «a» меньше, чем для события «b», означает ли это, что «a» произошло до «b»?

Не обязательно — меньшая метка времени согласуется с отношением «произошло до», но не подразумевает его, потому что одновременные события могут получать упорядоченные метки времени. Чтобы точно определить причинность, нужны векторные часы, а не скалярные логические часы.