Алгоритм «Хендікат»: Вибір лідера в розподіленій системі за найбільшим ID

Налаштування: Кілька Номеруваних Процесів

Уявіть набір процесів або вузлів, розподілених по мережі, кожен з яких має унікальний ідентифікатор – зазвичай просто ціле число. Ці процеси повинні завжди узгоджуватись щодо одного члена серед них, який є координатором, іноді називаним лідером. Координатор може відповідати за послідовну обробку оновлень, призначення роботи або діяти як єдине джерело правди для деякого спільного ресурсу. Правило, яке визначає Алгоритм «Булли», є хитрим: серед процесів, які зараз активні та доступні, той з найвищим ID завжди стає лідером. Немає голосування, жодних переговорів і немає поняття справедливості – ранг є долею. Це означає, що вся задача алгоритму полягає в одне питання після відмови: враховуючи процеси, які зараз активні, хто має найвищий ID? Припускається, що кожен процес у системі знає повний список членів і ID кожного іншого процесу заздалегідь, хоча не обов’язково знає, хто зараз активний. Ця проміжна діра між знанням списку та знанням того, хто реально доступний, є точно тим, що вирішує протокол вибору. Це простий ментальний опис, який є причиною того, що Алгоритм «Булли» залишається основою курсів з розподілених систем навіть десятиліття після того, як Raft і Paxos стали промисловим стандартом.

Вибори та повідомлення координатора: Повний процес

Протокол розпочинається, коли певний процес помічає, що поточний лідер більше не реагує, зазвичай через те, що серцебиття або запит завершилися з часом. Цей процес, який називається P, ініціює вибори, надсилаючи повідомлення про вибір до кожного іншого процесу з ID вищим за його власний. Потім він чекає протягом певного часу, щоб побачити, чи відповістиме хтось із цих процесів із вищим ID. Якщо жоден з цих процесів із вищим ID не відповідає вчасно, P робить висновок, що це має бути найвищий ID процес, який все ще живий, оголошує себе переможцем і надсилає повідомлення координатора кожному процесу з нижчим ID, оголошуючи нове лідерство. Але якщо хоч один із процесів із вищим ID все ще живий, він відповідатиме на повідомлення про вибір P двома речами: він не стане переможцем і повинен відмовитися та просто чекати оголошення координатора. У той час як процес із вищим ID, який відповідав, не просто без діла – отримання повідомлення про вибір зобов’язує його розпочати власні вибори серед процесів над його власним ID, повторюючи цей процес рекурсивно. Цей ланцюг триває до тих пір, поки певний процес не знаходить жодного процесу з вищим ID, щоб відповісти, в цьому випадку цей процес заявляє про перемогу, а повідомлення координатора поширюється вниз до всіх. В результаті це самоорганізована послідовність перекриваючихся виборів, яка завжди сходиться на єдиний найвищий живий ID.

Чому його назвали "Буллі" (Čomu yohō nazvaly "Bully")

Назва цього алгоритма ідеально передає його характер. Коли процес з вищим ID отримує повідомлення про вибір лідера від процесу з нижчим ID, йому не потрібно роздумувати, збирати докази або чекати на консенсус – він вже знає за визначенням, що має вищий рейтинг. Тому він негайно бере контроль, надсилаючи повідомлення про активність та перехоплюючи вибір, фактично відштовхуючи первинного ініціатора. У цьому немає місця для аргументів чи подальшого внеску з боку нижчого процесу; його роль полягала лише в тому, щоб помітити, що лідер відсутній, та запустити процес. Це точно відповідає шкільному динамічному зображенню, яке викликає назва: найсильніша дитина у класі не потребує дозволу для захоплення влади – вона просто заявляє про домінування, як тільки чує виклик. Це свідомо грубий, ієрархічний спосіб координації, що контрастує з більш рівноправними консенсусними протоколами, де голос кожного вузла справді має значення. Така поведінка "булінгу" також робить алгоритм передбачуваним: за умови унікальності та статики ID, результат будь-якого вибору визначається ще до початку, що є перевагою для простоти, і, як ми побачимо, джерелом реальних слабкостей.

Реальні слабкості: Потоки повідомлень та ігнорування поділів

Простота алгоритму ‘Bully’ має свою ціну. По-перше, розглянемо складність обміну повідомленнями. У найгіршому випадку, коли процес з найнижчим ID виявляє відмову, майже всі процеси з вищим ID запускають власні вкладені вибори, кожен із яких надсилає повідомлення усім процесам вище за нього. Це призводить до спалаху повідомлень, який масштабується приблизно як квадрат кількості процесів – O(n²) патерн, що може перевантажувати мережу трафіком виборів саме тоді, коли система вже перебуває під тиском через відмову. У великих кластерах цей оверхід стає справжньою проблемою масштабованості, а не просто теоретичною ноткою. По-друге, і значно серйозніше, алгоритм припускає, що безвідповідальність завжди означає аварійний збій процесу, але реальні мережі виявляються більш хаотичними. Якщо мережа розпадається на поділи – дві групи процесів, які можуть спілкуватися між собою внутрішньо, але не між ними – обидві сторони незалежно та правильно запускають алгоритм ‘Bully’ і кожен обирає для себе процеси з найвищим ID як лідера. В результаті працюють два координатори одночасно, кожен вважаючи себе єдиним авторитетом – класична ситуація «розділяй та володарюй», яка може пошкодити спільний стан або дублювати роботу. Алгоритм ‘Bully’ не має вбудованого поняття більшості кворуму для запобігання цьому, оскільки він був розроблений з урахуванням припущення про відмови вузлів, а не про поділи мережі.

Як це порівнюється з Raft

Сучасні системи консенсусу, такі як Raft, розроблені десятиліття після алгоритму Bully, безпосередньо усувають ці недоліки. Замість того, щоб покладатися на фіксовані числові ID та детерміноване правило «найвищий виграє», вузли Raft використовують випадкові тайм-аути виборів: коли фолловера не отримує інформації від лідера, він чекає випадковий проміжок часу перед тим, як стати кандидатом і попросити голоси, що природним чином зменшує ймовірність одночасного запуску виборів багатьох вузлів та уникнення штормів повідомлень, які часто трапляються в алгоритмі Bully у найгіршому випадку. Більше того, Raft організовує час у вигляді монотонно зростаючих термів і вимагає від кандидата отримати голоси від чіткої більшості кластеру перед тим, як стати лідером. Це вимоги більшості є ключовою структурною відмінністю: в разі мережевого розриву лише сторона з справжньою більшістю вузлів може обрати лідера, тоді як меншість залишається без лідера замість того, щоб обирати другого, конфліктуючого координатора. Це робить Raft значно стійкішим до сценаріїв «розділеного мозку» (split-brain) ніж алгоритм Bully, але це досягається за рахунок додаткової складності щодо реплікації логів та ведення обліку термів. Коротко кажучи, Bully оптимізований для концептуальної простоти і добре працює в невеликих середовищах лише з відмовами, тоді як Raft обмінюється цією простотою на гарантії правильності, які витримують більш хаотичні відмови розриву, що часто зустрічаються в реальних мережевих системах.

Frequently asked questions

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

Усе, що вище, працює прямо у вашому браузері — відкрийте The Bully Algorithm: Electing a Leader in a Distributed System by Highest ID і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.