Задача розподіленої координації

Цю задачу формулюють так: чи можливо надійно скоординувати дії на двох різних комп'ютерах (наприклад, виконання деякого коду в один і той самий час, вико­нання дії тільки один раз, атомарну зміну стану на двох різних машинах тощо)?

До дій, що вимагають такої синхронізації, належать, наприклад:

♦ атомарне переміщення файла із сервера S_{ на сервер S<i,

♦ атомарне переміщення суми грошей із рахунку в одному банку на рахунок в іншому.

Головна проблема, що виникає при цьому, пов'язана з тим, що мережа, яка зв'язує ці комп'ютери, є ненадійною:

♦ повідомлення можуть бути втрачені;

♦ комп'ютери можуть бути вимкнені або вийти з ладу.

З урахуванням ненадійності мережі можна уточнити формулювання цієї задачі.

Чи можна використати обмін повідомленнями через ненадійну мережу для надійної синхронізації двох комп'ютерів (щоб вони гарантовано могли виконува­ти ту саму операцію одночасно)?

Відповідь на це запитання є однозначно негативною навіть тоді, коли всі пові­домлення будуть доставлені й жоден комп'ютер не вийде з ладу.

Цю проблему звичайно ілюструють парадоксом візантійських генералів. При­пустимо, що два генерали на чолі армій перебувають на деякій відстані один від одного, тому вони можуть обмінюватися повідомленнями тільки через посиль­них, причому під час доставлення повідомлення посильних можуть полонити. Задачею є погодити час одночасної атаки на ворога (спільних сил достатньо для перемоги, сил кожної армії окремо - ні). Розглянемо протокол обміну повідом­леннями, який можна використати в даному випадку.

1. Генерал G_A відсилає повідомлення М_м із точним часом атаки.

2. Генерал G_B отримує М_АІ, відсилає своє повідомлення М_ВІ із висловленням зго­ди і починає очікувати підтвердження отримання М_ВІ.

3. Генерал G_A отримує М_ВІ, відсилає підтвердження його отримання (М_А2) і по­чинає очікувати підтвердження отримання М_А2.

Подібний обмін повідомленнями може тривати нескінченно. Очевидно, що погодити час атаки генералам не вдасться (останнє повідомлення увесь час зали­шатиметься непідтвердженим). Доведено, що розв'язків ця задача не має.

Далі в цьому пункті розглянемо протоколи розподіленої координації, що не потребують одночасного виконання операцій різними сторонами.

 

Протокол запиту-квітування

Проаналізуємо особливості обміну повідомленнями в мережі за наявності поми­лок. Припустимо, що трапляються тільки помилки передавання даних (втрати повідомлень), учасники протоколу не виходять із ладу.

Для обміну повідомленнями за таких умов із гарантією одноразового достав­лення призначений протокол запиту-квітування (request/acknowledge protocol).

1. Відправник пересилає одержувачеві повідомлення і встановлює таймер.

2. Одержувач отримує повідомлення і відсилає підтвердження отримання.

3. Відправник отримує підтвердження і скидає значення таймера.

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

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

умови, що учасники не виходять із ладу. При цьому одержувач може отримати повідомлення кілька разів (у разі втрати підтвердження). Щоб мати можливість відкидати дублікати, повідомлення можна супроводжувати унікальними номерами.

Протокол запиту-квітування мало пристосований до роботи за умов виходу з ладу його учасників. Наприклад, у разі краху відправника після відновлення він не може отримати інформацію про те, отримав одержувач повідомлення чи ні (підтвердження до нього дійти не зможе). У разі краху одержувача значно усклад­нюється робота із дублікатами.

Для координації взаємодії ненадійних учасників потрібні більш складні про­токоли. Одним із них є протокол двофазового підтвердження.

 

Двофазове підтвердження

Оскільки одночасного виконання дій на віддалених комп'ютерах відповідно до парадоксу генералів домогтися неможливо, для розподіленої координації дій ви­користовують методи, у яких допустиме виконання дій у різний час. Розглянемо один із них - двофазове підтвердження (two-phase commit, 2РС) [4].

У цьому разі дві сторони виконують дії, оформлені у вигляді транзакцій -атомарних операцій, які виконуються повністю (підтверджуються, commit) або не виконуються зовсім (відкочуються, rollback).

Прикладом розподіленої транзакції може бути перенесення файла із сервера Si на сервер S₂. Якщо виконання цієї дії переривається, за відсутності атомарності може виявитися, що файл був вилучений із сервера 5_Ь але при цьому не був пере­несений на сервер S₂.

Для виконання протоколу двофазового підтвердження необхідно на кожному комп'ютері підтримувати журнал транзакцій (transaction log), у якому відстежу-вати, відбулося підтвердження чи ні. Крім того, один із вузлів мережі має відігра­вати роль координатора транзакцій. Основним завданням такого координатора є збереження атомарності кожної транзакції у розподіленій системі.

Першим етапом протоколу є етап запитів координатора.

1. Координатор відсилає всім учасникам запит. Він містить опис дії, яка має ви­конуватися, наприклад «вилучити файл a.txt із кореневого каталогу». Перед відсиланням запиту інформацію про нього зберігають у журналі транзакцій координатора.

2. Учасники отримують запит і виконують транзакцію локально (наприклад, на­магаються вилучити файл). Інформацію про результат цієї дії відображають у вигляді повідомлення (М_ок - успіх, М_АВ0КГ - невдача), яке зберігають у жур­налі транзакцій кожного учасника і відсилають координаторові. Цей етап за­вершений, коли координатор отримає повідомлення від всіх учасників (або мине максимальний час очікування). Зазначимо, що для жодної транзакції в конкретний момент ще не було виконано ні підтвердження, ні відкату (на­приклад, інформацію про вилучення файла зберігають лише у пам'яті). Другим етапом є етап ухвалення рішення координатором.

3. Спочатку координатор ухвалює рішення щодо підтвердження або відкату роз­поділеної транзакції. На цьому кроці можуть виникнути дві ситуації:

♦ координатор отримує повідомлення M_AB0RT хоча б від одного учасника. Після цього він створює повідомлення M_GL0BAL rollback зберігає його в жур­налі та відсилає всім учасникам;

♦ координатор отримує повідомлення М_ок від кожного учасника. Після цьо­го він створює повідомлення M_GL0BALC0MMIT, зберігає його в журналі та відсилає всім учасникам.

4. Після отримання повідомлення від координатора кожен учасник зберігає його у своєму журналі та виконує відкат або підтвердження транзакції залежно від типу повідомлення. Для цього прикладу відкат може зводитися до повного скасування операції вилучення файла, підтвердження - до вилучення файла з диска.

Розглянемо виконання цього протоколу за умов мережних помилок. Спочат­ку зупинимося на випадках виходу з ладу учасників протоколу.

♦ Якщо учасник вийде з ладу на кроці 2 (під час виконання транзакції), коорди­натор не отримає повідомлення про завершення транзакції упродовж макси­мального часу очікування і відкотить транзакцію, відіславши учасникам пові­домлення M_{GL0BAL_R0LLBACK} -

♦ Якщо координатор вийде з ладу на кроці 3, після відновлення він має зверну­тися до свого журналу транзакцій. Коли в ньому немає жодного повідомлення Mglobal_xxx або є повідомлення M_{GL0BAL_ rollback}, то всім учасникам відсила­ють повідомлення про відкат. Коли в журналі є M_{GL0BAL_commit}, учасникам відсилають повідомлення про підтвердження.

♦ У разі виходу учасника з ладу на кроці 4 після відновлення він має звернутися до координатора за інформацією і виконати відповідно підтвердження або відкат.

До недоліків протоколу 2РС належать високі вимоги до надійності координа­тора. Якщо він вийде з ладу на кроці 3 і не відновить свою роботу, всі учасники можуть бути заблоковані.

Це, однак, відбувається не завжди. У разі отримання деякими учасниками по­відомлення від координатора на кроці 4, а деякими — ні, часом є можливість за­вершити транзакцію, звернувшись за інформацією до інших учасників.

♦ Коли хоча б один із учасників отримав Mglobal_xxx, необхідно виконати дію, що відповідає цьому повідомленню.

♦Коли хоча б один із учасників відіслав M_AB0RT, транзакцію необхідно відкотити.

Якщо ж всі учасники відіслали М_ок, але ніхто з них не отримав Mglobal _xxx, рішення не може бути прийнято, оскільки координатор міг зберегти в журналі (але не встиг відіслати) Mglobal_ rollback через свою внутрішню помилку. Така ситуація і спричиняє блокування всіх уч асників. Під час реалізації 2РС потрібно завжди враховувати можливість такого блокування.

 

Розподілені файлові системи

Розподілена файлова система (РФС) дає можливість застосуванням звертатися до файлів, що перебувають на диску віддаленого комп'ютера. Загалом до таких систем можна віднести будь-які засоби доступу до віддалених файлів; наприклад, HTTP фактично можна розглядати як базовий протокол для реалізації РФС.

У цьому розділі обмежимося розглядом РФС, які володіють властивістю про­зорості доступу. Під час роботи із такою системою з усіма файлами (локальні во­ни чи віддалені) працюють однаково, особливості реалізації віддаленого доступу обробляють на рівні файлової системи. Фактично розподілена файлова система із прозорістю доступу приховує від користувача наявність мережі.