Розробники програмують машини, щоб ті робили те, що ми, їх творці, бажаємо. Це приємне відчуття, коли ти пишеш код і потім цей код робить для тебе саме таку каву, як ти хочеш, чи генерує тобі lofi.

В роботі з машинами, так само, як і в роботі с людьми, є певні проблеми організації.

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

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

Алгоритми досягнення згоди зʼявились, як напрямок в компʼютерних науках, щоб вирішити проблеми самоорганізації групи машин. Ці алгоритми ставлять для себе за мету "пояснити" чи "навчити" машини, як вони можуть колективно дійти до згоди і приймати рішення, не очікуючи на людину.

Є декілька всесвітньо відомих, ефективних алгоритмів досягнення згоди і в цьому пості я буду говорити про RAFT.

Спільнота машин і ролі

Те, що в людей називається "спільнота", для машин ми будемо називати "кластер". "Кластер" – це декілька машин, які мають мережевий звʼязок одна з одною.

Зазвичай, щоб організувати кластер, потрібно не менше 3 машин, щоб, в разі пошкодження одної в нас все ще були 2 машини, які будуть мати 2 різні ролі. Є також засоби "симулювання" "кластера" на одній машині. Наприклад, minikube для кубернетесу.

Машини в кластері не обовʼязково повинні бути фізично окремими машинами. Часто використовують віртуальні машині, чи контейнери.

Далі ми позначимо машину, яка буде грати якусь роль в нашому кластері, як "нода". "Нода" з англійською перекладається, як "вузол". Це термін, який має свої коріння в теорії графів. Якщо ви зацікавлений читач, то ви можете згадати, що графи мають вузли (nodes) і ланки (edges).

Ноди в кластері поділяються на дві ролі: лідер і послідовники.

Лідер приймає всі важливі рішення, але якщо його "вивести з гри", то послідовники оголошують "вибори" і обирають нового "лідера". Таким чином в кластері з трьох нод, в нас буде один лідер і два послідовники. Якщо лідер опинеться поза зоною досягнення, один з послідовників стане лідером, і в нього залишеться один послідовник.

Поняття "стану" і лог

В компʼютерних науках система може називатися "маючою" стан (stateful), якщо ця система зберігає (запамʼятовує) якусь інформацію.

Наш кластер буде мати "стан" тому, що машини в ньому будуть "запамʼятовувати" все, що відбувається в кластері. На даному прикладі ми можемо сказати, що "стан" кластера – це те, що з ним відбувається зараз: хто лідер і хто послідовники. Якщо відбувається процес обрання нового лідера – ця інформація теж вважається частиною "стана" кластера, одже нам важливо запамʼятати хто як голосує.

Стан записується нодами, які обʼєднані в кластер, до сховища. Важливо відмітити, що якщо одна з нод вийде з ладу, це сховище не буде очищене.

В концепції алгоритма ми будемо називати місце, де зберігається наш стан, логом.

Час лідерства

Лідер зберігає "лідерство" в кластері до поки не вийде з ладу. Для того, щоб визначити, чи лідер присутній, використовується heartbeat – "серцебиття" – це термін, якій обозначає регулярні мережеві виклики від лідера до всіх своїх фолловерів, щоб позначити свою присутність.

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

Один період лідерства використовується, як позначка логічного часу в кластері.

Комунікації

Якщо в кластер надходить команда, за її виконання відповідальний лідер. Лідер також розповсюджує повідомлення про те, яка команда надійшла, до всіх своїх фоловерів.

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

Крім вишеназначеного, лідер відповідальний за те, щоб вести лог і здійснювати транзакцію лога (сommit).

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

Всі комунікації в кластері здійснюються за допомогою RPC – remote procedure calls. Незважаючи на те, що в нас велика кількість коунікацій, на практиці (в коді) нам вистачає двух структур, щоб позначити їх: gitHub gist.

Команда AppendEntry використовується лідером і зберігає останні команди, які ним були здійснені. Ця команда водночас служить, як "серцебиття".

Команда RequestVote (github gist) використовується послідовником, якщо він протягом якогось часу (це має налаштувати розробник) не отримує повідомлень від лідера. В цей момент послідовник пропонує себе, як лідера, і просить інші ноди в кластері проголосувати за нього. Інші послідовники мають вибір чи віддати йому свій голос чи ні. Коли досягається більшість (majority), вибори оголошують завершеними, послідовник стає лідером і всі інші кандидати теж конвертуються в послідовників.

Стани в кластері

• Тільки-но нода опиняється в кластері чи стає доступною, вона стає послідовником. Це стосується і лідерів також.
• Якщо послідовник не отримує від лідера серцебиття протягом певного часу, він одразу ж пропонує себе, як наступного кандидата в лідери.
• Як тільки послідовник-кандидат набирає більшість голосів, він стає лідером поки не вийде з стану.
• Коли ноди проводять вибори, це називають кворум. Ми говоримо, щоб для того, щоб стати лідером, потрібно набрати більшість в кворумі.
• Якщо послідовник-кандидат отримує повідомлення від послідовника-кандидата, який запропонував себе пізніше, ніж він, цей послідовник знімає себе з кандидатства і стає знову послідовником-частиною кворума, який голосує.
• Якщо послідовник не набирає більшість і лідер ще не обраний, він автоматично пропонує себе ще раз через деякий час.
• Як тільки лідер отримує повідомлення, що обрано нового лідера, він переходить в стан послідовника і визнає нового лідера.

Імплементація алгоритма

В імплементації алгоритма можна виділити декілька частин:

• створення кластеру
• голосування
• збір голосів
• розсилка повідомлень від лідера
• отримання повідомлень послідовниками
• оновлення лога для послідовників
• транзація (коміт) лога лідером
• валідація лога лідера послідовниками

Декілька прикладів реалізації Рафта на різних мовах програмування:

• Raft (Golang)
• Raft (Rust)
• Raft (Scala) (currently not stable)

Список джерел, що використовувався для подготовки матеріала

• In Search of an Understandable Consensus Algorithm (original paper)
• лекція Мартина Клеппмана
• Raft Algorithm, Explained (Zixuan Zhang)