Алгоритм розподіленого знімка Chandy-Lamport

Проблема: Зйомка моменту в системі без годинника

Розподілена система складається з процесів, які спілкуються лише шляхом надсилання повідомлень по каналах зв’язку, при цьому кожен процес не знає про поточний стан інших процесів, крім як через ці повідомлення. Немає глобального годинника та жодного моменту, коли всі машини могли б одночасно призупинити свою роботу, оскільки саме акт їхнього повідомлення потребує часу та надходить у різні моменти. Це створює реальну складність: якщо попросити кожного процесу повідомити про свій стан, щойно він отримує ваш запит, звіти відображатимуть дуже різні, неузгоджені моменти, і деякі навіть описуватимуть стан, який ніколи справді не існував одночасно. Наприклад, один процес може повідомити, що вже отримав повідомлення, яке, згідно з звітом іншого процесу, ще не було відправлено. Таке зображення моменту часу буде невідповідним і може ввести в оману будь-який алгоритм, який на ньому покладається, наприклад, перевірку, чи має система достатньо ресурсів або заблокувалася. Замість цього потрібно досягти узгодженого глобального стану, який іноді називають узгодженим розрізом: колекція локальних станів, один на процес, плюс набір повідомлень, що перебувають в процесі передачі по кожному каналу зв’язку, щоб ця колекція могла правдоподібно існувати в певний момент відповідно до часової послідовності подій. Важливо, що це не вимагає реального синхронізації в режимі реального часу. Потрібно лише забезпечити, щоб зафіксовані стани поважали причинно-наслідкові зв’язки: якщо знімок записує отримання повідомлення, він також повинен записувати відправку того самого повідомлення. Алгоритм Чанді-Лампорта був розроблений спеціально для створення такого розрізу ефективно, використовуючи лише повідомлення, які надсилаються системою, плюс один новий вид повідомлень – маркер, і припускає надійність каналів зв’язку та доставку повідомлень в порядку їх надсилання (FIFO), що є ключовим для того, як алгоритм міркує про те, що він вже бачив, а що ні.

Як працює алгоритм: маркери, запис та поширення

Алгоритм починається тоді, коли будь-який окремий процес вирішує ініціювати зняття образу. Цей ініційований процес спочатку записує свій власний локальний стан, захоплюючи будь-які внутрішні змінні, що мають значення для застосування, і негайно надсилає спеціальне повідомлення-маркер по всіх каналах, на яких він здійснює вихід, перш ніж робити щось інше. Цей маркер не містить жодних даних застосування; його єдиний спосіб дії – сигналізувати про межу зняття образу. Від цього моменту ініціатор також починає записувати будь-яке повідомлення застосування, яке він отримує на кожному з його вхідних каналів, розглядаючи ці повідомлення як стан переміщення того каналу, доки не прийде маркер туди. Тепер розглянемо будь-який інший процес у системі. Коли він вперше отримує маркер на якомусь вхідному каналі, він негайно виконує дві дії: записує свій власний локальний стан, який існує в цей момент, і записує стан каналу, на який прийшов маркер, як порожній, оскільки маркер у FIFO-каналі означає, що раніше повідомлення застосування не враховані на цьому з’єднанні. Він потім поширює зняття образу, надсилаючи маркер по всіх своїх вихідних каналах, так само, як і ініціатор, і починає записувати вхідні повідомлення на кожному іншому каналі, на якому він ще не бачив маркера. Якщо процес пізніше отримує маркер на одному з цих інших каналів, він припиняє запис цього каналу та завершує свій записаний список поточних повідомлень для нього, що є точним набором повідомлень, які він отримав на цьому каналі після запису свого стану, але до того, як прийшов маркер. Якщо процес отримує другий або наступний маркер на каналі, на якому він вже бачив маркер, він просто закриває запис цього каналу, оскільки дублікат маркера на тому ж каналі сигналізує про відсутність нової інформації. Алгоритм завершується тоді, коли кожен процес отримує маркер на кожному з своїх вхідних каналів, після чого локальний стан і стан каналу записуються, і повний глобальний знімок може бути зібраний, зазвичай шляхом того, що кожен процес передає свій записаний стан координатору.”]} звучало б більш природно як: {

paragraphs

Чому знімок є послідовним: Аргумент про розріз

Серце доказу правильності алгоритму Чанді-Лампорта полягає в тому, що набір записаних станів утворює справжній послідовний розріз, тобто для будь-якого повідомлення, яке знімок відмічає як отримане певним процесом, це саме повідомлення також враховується як записане в попередньому стані відправника, відправлене та захоплене як частина стану польоту каналу, або іншим чином послідовно розміщене. Ключовий момент – жорсткий порядок, що забезпечується маркерами, поєднаний із властивістю FIFO (першим прийшов – першим обслуговується) каналів. Коли процес P записує свій стан і потім надсилає маркери на всі вихідні канали, кожне додаткове повідомлення, яке P відправляє після цього, надсилається після маркера на тому ж самому каналі, оскільки процес ніколи не переставляє свої вихідні повідомлення відносно моменту, коли він вирішив зробити знімок. Таким чином, будь-який процес Q, який пізніше отримує цей маркер на каналі від P, знає, за властивістю FIFO, що всі додаткові повідомлення, які надходять на цей канал до маркера, були відправлені P перед його знімком, і все, що надходить після, належить до пост-знімкового майбутнього та правильно виключено з запису про польоти. Це гарантує важливу властивість: жодне повідомлення не може бути записане як отримане в знімку без відображення його відправлення, або вже відбулося, або у записаних польотах певного каналу. Іншими словами, алгоритм ніколи не захоплює ефект без його причини. Це має величезне значення для будь-якого алгоритму, який споживає знімок, оскільки це означає, що зафіксований глобальний стан, хоча його частини фізично спостерігалися в різні моменти реального часу по мережі, відповідає стану, який система могла дійсно пройти у валідній схемі виконання відповідно до фактичного порядку подій (його причинного, або

що сталося раніше

). Ця гарантія, а не буквальна одночасність, робить знімок надійним та корисним для роздумів про глобальні властивості.

Практичне застосування: Контрольні точки та виявлення застрягання,

Найбільш пряме застосування знімків Chandy-Lamport – це створення контрольних точок для забезпечення стійкості до несправностей. У тривалих розподілених обчисленнях, таких як великі наукові симуляції або системи обробки транзакцій, періодичне збереження узгодженого глобального стану дозволяє всьому системі відновитися після збою, перейшовши назад до останньої контрольної точки замість того, щоб починати все спочатку. Оскільки знімок гарантовано узгоджений, відновлення з нього ніколи не ставить систему в неможливе положення, коли процес отримує повідомлення, яке, за відновленим станом, ніколи не надсилалося; вміст каналу просто відтворюється як нещодавно отриманий. Друке значне застосування – виявлення застрягання в розподілених системах. У системах, де процеси утримують ресурси та чекають один на одного, наприклад, у розподілених базах даних, що домовляються про блокування, застрявання відповідає циклу в графі очікування, але жоден окремий процес не може безпосередньо бачити цей граф, оскільки кожен знає лише свої власні локальні залежності. Взявши узгоджений знімок місцевого стану ресурсів та стану очікування кожного процесу, алгоритм моніторингу може точно відтворити повний граф очікування і шукати в ньому цикли, а оскільки знімок доведено, що він узгоджений, виявлений цикл там відповідає реальному застряганню, а не артефакту порівняння несумісних моментів часу. Цей алгоритм також вплинув на більш широкі методи виявлення стабільних властивостей, тобто властивостей, які, якщо вони були правдивими, залишаються правдивими, таких як виявлення завершення або збирання сміття в розподілених об'єктних системах, оскільки узгоджений знімок є точно інструментом, необхідним для безпечної оцінки того, чи поточна властивість дійсно існує в системі без зупинення її.

Припущення, обмеження та компроміси проєктування

Елегантність алгоритму Чанді-Лампортта ґрунтується на певному наборі припущень, які важливо розуміти. Він вимагає, щоб канали були надійними, тобто жодні повідомлення не втрачалися, дублювалися або пошкоджувалися, і що вони були FIFO – доставляли повідомлення в точному порядку надсилання, оскільки аргумент щодо правильності повністю залежить від маркера, який діє як надійна межа всередині упорядкованого потоку. Також припускається, що основна мережа сильно зв’язана, щоб маркери, ініційовані будь-де, могли в кінцевому підсумку досягти кожного процесу, і що кожен процес, отримавши маркер, правильно слідує за протоколом без збою посередині самого процесу створення знімка. Якщо канали можуть перемішувати або втрачати повідомлення, гарантії базового алгоритму руйнуються, і потрібні більш складні варіанти з номерами послідовностей або підтвердженнями. Алгоритм також мовчить про те, що відбувається між моментом, коли він виявляє глобальну властивість, і моментом, коли будь-які дії виконуються на цій інформації; оскільки система продовжує працювати протягом усього часу, знімок описує стан, який вже є минулим, коли він повністю зібраний, тому його висновки повинні стосуватися стабільних властивостей або використовуватися для відновлення, а не для прийняття миттєвих рішень в режимі реального часу. Ще одна тонкість – це накладні витрати: кількість повідомлень-маркерів зростає з кількістю каналів, і кожен процес тимчасово буферизує вхідні повідомлення на невпорядкованих каналах, що коштує пам’ять пропорційно швидкості поширення маркерів. Незважаючи на ці обмеження, основний внесок алгоритму – відокремлення поняття змістовного глобального знімка від неможливої вимоги буквальної одночасности – залишається одним із фундаментальних ідей в теорії розподілених систем, і його спадники зустрічаються у багатьох сучасних фреймворках обробки потоків та протоколах контрольних точок розподілених баз даних.

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

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

Усе, що вище, працює прямо у вашому браузері — відкрийте The Chandy-Lamport Distributed Snapshot Algorithm і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.