Гібридні логічні годинники Лабораторія

Чому фізичні чи логічні годинники недостатньо

Фізичні годинники на окремих машинах ніколи не збігаються абсолютно. Навіть із протоколами синхронізації часу в мережі, неминучі невеликі відхилення та дрейф. Тому дві машини можуть розходитися на кілька мілісекунд або більше в будь-який момент. Якщо система просто маркує кожну подію локальним фізичним годинником і припускає, що ці часові мітки можна порівнювати для визначення порядку, вона іноді може помилитися: подія, яка відбулася причинно раніше іншої, може мати більшу фізичну часову мітку просто тому, що годинник на її машині працював трохи швидше. Це не косметична проблема, а серйозний недолік правильності, оскільки бази даних і розподілені журнали часто покладаються на порядок часових міток для визначення того, яке запис виграє або який читання є свіжим. Логічні годинники, представлені Лампортом, вирішують проблему порядку, повністю відкидаючи фізичний час. Кожен вузол підтримує лічильник, який збільшується з кожною локальною подією, і коли отримує повідомлення, перескакує на одиницю більше за максимальне значення локального лічильника та лічильника, що передається в повідомленні. Це гарантує, що причинно-наслідковий порядок завжди відображається правильно: якщо подія A відбулася до події B, лічильник Лампорта для події A гарантовано буде меншим за лічильник для події B. Однак є одна

підводна каменість

- лічильник є чистою абстракцією. У нього немає зв'язку з реальним плином часу, тому вузол, який отримує багато повідомлень поспіль, може побачити свій лічильник стрибнути далеко вперед від того, що показує годинник стін. А вузол, який бере участь у невеликій кількості взаємодій, може відставати значно. Порівняння Лампортової часової мітки з моментом часу, наприклад, щоб вирішити, чи є запис старшим за п'ять хвилин, безглуздо. Hібридні логічні годинники існують саме для заповнення цієї прогалини. Вони підтримують часові мітки, прив’язані до фізичного часу в нормальних умовах, тому у поширеному випадку, коли годинники збігаються та події відбуваються не надто щільно, часова мітка HLC просто є локальним числовим значенням годинника стін. Тільки коли фізичний час не забезпечує достатньої роздільної здатності або коли це вимагають причини, логічна складова втручається і збільшується, точно відтворюючи ситуації, коли чистий фізичний годинник сам по собі дасть неправильне уявлення про порядок.

Структура міток часу HLC

Мітка часу HLC — це пара значень, зазвичай записана як (фізичний час, логічний лічильник), іноді скорочено як (pt, l). Компонент фізичного часу береться з годинника локального вузла та є найкращим поточним оцінкою алгоритмом реального часу, коригується вгору кожного разу, коли потрібно залишатися попереду часових міток, які було спостережено. Компонент логічного лічильника — це невелике ціле число, яке розв’язує зв’язки та фіксує інформацію про порядок, яку не можна виразити лише за допомогою фізичного часу, наприклад, коли кілька подій відбуваються в одному тику годинника або коли час отриманого повідомлення перевищує локальний фізичний годинник. Порівняння двох міток часу HLC проводиться лексикографічно: спочатку порівнюються компоненти фізичного часу, і лише якщо вони рівні, порівнюються компоненти логічного лічильника. Це означає, що мітка часу HLC поводиться майже точно як фізична мітка часу з точки зору інтерпретації людиною та запитів за діапазоном. Логічний лічильник зазвичай невеликий, часто одного разу, оскільки він накопичується лише тоді, коли кілька причинно пов’язаних подій упаковуються в один і той же фізичний тик, і він скидається до нуля, коли компонент фізичного часу справді просувається вперед після своєї попередньої вартості. Це дизайн дає HLC дві властивості одночасно, яких жоден з чисто фізичних чи чисто логічних годинників не має окремо. По-перше, компонент фізичного часу завжди близький до справжнього часу годинника, обмежений максимальною відхиленням та затримкою повідомлень, які спостерігаються в системі, тому мітку часу HLC можна використовувати майже безпосередньо як звичайну мітку часу для перевірок терміну дії, вікон прибирання сміття або людських журналів. По-друге, пара в цілому зберігає гарантію причинного порядку: коли одна подія причинно відбулася раніше за іншу, лексикографічне порівняння їхніх міток часу HLC завжди правильно повідомляє про цей порядок, точно так само як і Lamport clock.

Оновлення: Покроково

Алгоритм HLC визначає дві правила оновлення: одне для повністю локальних подій та інше для отримання повідомлення, яке містить віддалений часовий штамп HLC. Обидва правила слідують одному основному принципу: ніколи не дозволяйте часовому штампу йти назад і завжди включайте найновішу доступну інформацію. Під час локальної події вузол читає свій фізичний годинник, назвемо це значення pt_now. Потім він обчислює нову фізичну компоненту часу як максимум між pt_now та попередньою фізичною компонентою часу цього вузла. Якщо цей максимум дорівнює попередній фізичній компоненті часу, тобто фізичний годинник не зростав з моменту останнього оновлення, логічний лічильник збільшується на одиницю. Якщо цей максимум строго більший за попередню фізичну компоненту часу, тобто реальний час пішов вперед, логічний лічильник скидається до нуля. Це точно аналогічно правилу збільшення Lamport-годинника «збільшувати при кожній події», крім того, що збільшення потрібне лише тоді, коли сам фізичний час не забезпечує свіжої розв’язаності. Під час отримання повідомлення, яке містить віддалений часовий штамп (pt_remote, l_remote), вузол знову читає свій локальний фізичний годинник pt_now і обчислює нову фізичну компоненту часу як максимум між трьома величинами: pt_now, попередньою фізичною компонентою часу цього вузла та pt_remote. Якась із цих трьох величин, що стала найбільшою, стає новою фізичною компонентою. Потім логічний лічильник встановлюється на основі того, яка з цих трьох величин досягла максимуму: якщо максимум досягнуто лише локальним фізичним читнням, логічний лічильник скидається до нуля; якщо нова фізична компонента співпадає з попередньою локальною та/або віддаленою фізичною компонентою, логічний лічильник стає на одиницю більшим за максимальне значення відповідних попередніх логічних лічильників, збільшуючи його для розв’язання зв’язки. У будь-якому випадку лічильник ніколи не зменшується, що гарантує, що об'єднаний часовий штамп буде більшим за часовий штамп відправника та власну попередню часову мітку отримувача, що точно забезпечує збереження гарантії причинно-наслідкового порядку при обміні повідомленнями.

Як HLC зберігає причинність без втрати фізичного змісту

Аргумент про правильність для HLC відображає класичний доказ для годинників Лампорта, з доданим обмеженням за фізичним часом. Оскільки кожне правило оновлення приймає максимальне значення всіх відповідних попередніх міток часу та, якщо необхідно, строго збільшує логічний лічильник, то час відмітку будь-якої події гарантовано завжди більший за часи відмітку всіх подій, що викликають її. Це така ж умова годинника, як і для чистих логічних годинників: якщо подія А відбулася до події Б, незалежно від порядку виконання програми на одному вузлі або через ланцюг надсилань та отримань повідомлень між вузлами, то HLC(А) гарантовано буде меншим за HLC(Б) відповідно до раніше описаного лінгвістичного порівняння. Крім того, HLC додає до цієї гарантії доведене обмеження, що пов'язує фізичний компонент із справжнім часом годинника. При розумних припущеннях, таких як обмежена розбіжність часу між вузлами та обмежений час передачі повідомлень, фізичний компонент будь-якого часу відмітку HLC залишається в межах невеликої, обмеженої відстані від фактичного фізичного часу, коли відбулася подія. Це обмеження робить часи відмітку HLC корисними для практичних цілей: порівняння часу відмітку HLC з терміном виконання годинника, обчислення приблизної тривалості між двома подіями на різних вузлах або відображення запису в зручному для людини форматі – все це залишається змістовним, що було б неможливим із чисто логічними лічильниками. Важливо бути точним щодо того, чого не дає HLC. Він не надає точного порядку у реальному часі, як ідеально синхронізований глобальний годинник, і не замінює більш потужних структур відстеження причинності, коли системі потрібно знати повну історію причинності всіх подій, а не лише повний порядок, який відповідає причинності. HLC надає скалярне значення для кожної події, яке легко зберігати, порівнювати та індексувати, на шкоду лише приблизному відображенню справжньої одночасність і лише захопленню причинного передування, а не повної інформації про залежність від причинності.

Практичне застосування: CockroachDB, MongoDB та інші

Гібридні логічні годинники набули популярності в розподілених базах даних для виробництва, оскільки вони вирішують конкретну інженерну проблему: ці системи потребують міток часу, які можна використовувати як для забезпечення правильності, узгодження транзакцій у кластері, так і для операційних цілей, таких як спливання застарілих даних, збір непотрібних версій зберігання або повідомлення про межі запитів у часі, що нагадують звичайний календарний час. CockroachDB використовує HLC як основу для порядку транзакцій і контролю багатоверсійного конфлікту. Кожен вузол підтримує HLC, і кожне читання та запис мічаться за допомогою нього. Оскільки фізичний компонент тісно відстежує реальний час, CockroachDB може обмежити, наскільки вузол може відхилитися від часу інших вузлів кластера, і використовувати це обмеження для забезпечення узгодженості транзакцій, а логічний лічильник гарантує, що навіть операції, які відбуваються в межах одного фізичногоtick або прибувають поза фізичним часом через затримку мережі, все ще впорядковуються таким чином, щоб відповідати причинно-наслідковим зв'язкам. MongoDB прийняла подібний механізм, який внутрішньо позначається як час кластера, який слідує тому ж гібридному принципу для порядку операцій у репліках та шардах у причинно-відносних сесіях. Коли клієнт виконує причинно-відносний читання після запису, драйвер розповсюджує гібрильний міток часу, щоб наступні операції на будь-якому вузлі кластера гарантовано бачили дані принаймні так само нещодавно, знову ж таки покладаючись на той самий правило максимального та збільшення оновлення для об'єднання фізичного часу та логічного порядку. Крім цих двох систем, ця ідея зустрічається скрізь, де інженерам потрібні мітки часу, які також виконують роль механізму впорядкування та інформаційного джерела для операційних цілей, включаючи різні розподілені фреймворки логування та зберігання подій, деякі реалізації консенсусу та реплікації, а також академічні дослідження, які розширюють базову ідею HLC більш жорсткими обмеженнями або додатковою інформацією.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Hybrid Logical Clocks Lab і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.