Останнє оновлення: 21 December, 2022
Розробники програмують машини, щоб ті робили те, що ми, їх творці, бажаємо. Це приємне відчуття, коли ти пишеш код і потім цей код робить для тебе саме таку каву, як ти хочеш, чи генерує тобі lofi.
В роботі з машинами, так само, як і в роботі с людьми, є певні проблеми організації.
Якщо ви стаєте менеджером чи супервізором для команди людей, ви напевно знаєте, що постійно наказувати кожній людині що їй робити – це доволі складна робота. Якщо ви комусь щось забудете сказати, то ця людина не зробить нічого з того, що вам треба, і ваша команда не досягне тих результатів, яких вам би хотілося.
Такі самі проблеми організації існують і з машинами. Машини не знають як працювати в команді з іншими машинами чи людьми і не проактивні (тобто, якщо ви їм не пояснете що їм потрібно робити, то машини нічого не роблять).
Алгоритми досягнення згоди зʼявились, як напрямок в компʼютерних науках, щоб вирішити проблеми самоорганізації групи машин. Ці алгоритми ставлять для себе за мету "пояснити" чи "навчити" машини, як вони можуть колективно дійти до згоди і приймати рішення, не очікуючи на людину.
Є декілька всесвітньо відомих, ефективних алгоритмів досягнення згоди і в цьому пості я буду говорити про RAFT.
Те, що в людей називається "спільнота", для машин ми будемо називати "кластер". "Кластер" – це декілька машин, які мають мережевий звʼязок одна з одною.
Зазвичай, щоб організувати кластер, потрібно не менше 3 машин, щоб, в разі пошкодження одної в нас все ще були 2 машини, які будуть мати 2 різні ролі. Є також засоби "симулювання" "кластера" на одній машині. Наприклад, minikube
для кубернетесу.
Машини в кластері не обовʼязково повинні бути фізично окремими машинами. Часто використовують віртуальні машині, чи контейнери.
Далі ми позначимо машину, яка буде грати якусь роль в нашому кластері, як "нода". "Нода" з англійською перекладається, як "вузол". Це термін, який має свої коріння в теорії графів. Якщо ви зацікавлений читач, то ви можете згадати, що графи мають вузли (nodes) і ланки (edges).
Ноди в кластері поділяються на дві ролі: лідер і послідовники.
Лідер приймає всі важливі рішення, але якщо його "вивести з гри", то послідовники оголошують "вибори" і обирають нового "лідера". Таким чином в кластері з трьох нод, в нас буде один лідер і два послідовники. Якщо лідер опинеться поза зоною досягнення, один з послідовників стане лідером, і в нього залишеться один послідовник.
В компʼютерних науках система може називатися "маючою" стан (stateful), якщо ця система зберігає (запамʼятовує) якусь інформацію.
Наш кластер буде мати "стан" тому, що машини в ньому будуть "запамʼятовувати" все, що відбувається в кластері. На даному прикладі ми можемо сказати, що "стан" кластера – це те, що з ним відбувається зараз: хто лідер і хто послідовники. Якщо відбувається процес обрання нового лідера – ця інформація теж вважається частиною "стана" кластера, одже нам важливо запамʼятати хто як голосує.
Стан записується нодами, які обʼєднані в кластер, до сховища. Важливо відмітити, що якщо одна з нод вийде з ладу, це сховище не буде очищене.
В концепції алгоритма ми будемо називати місце, де зберігається наш стан, логом.
Лідер зберігає "лідерство" в кластері до поки не вийде з ладу. Для того, щоб визначити, чи лідер присутній, використовується heartbeat – "серцебиття" – це термін, якій обозначає регулярні мережеві виклики від лідера до всіх своїх фолловерів, щоб позначити свою присутність.
Якщо нода-фолловер не отримує позначки від лідера деякий час, фолловер розсилає пропозицію в кластер щодо перевизначення лідера. Після цього проводяться вибори, на яких ноди обирають нового лідера в кластері.
Один період лідерства використовується, як позначка логічного часу в кластері.
Якщо в кластер надходить команда, за її виконання відповідальний лідер. Лідер також розповсюджує повідомлення про те, яка команда надійшла, до всіх своїх фоловерів.
Лідер також, як я вже зазначив, регулярно розповсюджує повідомлення про те, що він присутній. Вони називаються "серцебиття".
Крім вишеназначеного, лідер відповідальний за те, щоб вести лог і здійснювати транзакцію лога (сommit).
Коли починаються вибори, ноди спілкуються між собою, щоб визначити наступного лідера.
Всі комунікації в кластері здійснюються за допомогою RPC – remote procedure calls. Незважаючи на те, що в нас велика кількість коунікацій, на практиці (в коді) нам вистачає двух структур, щоб позначити їх: gitHub gist.
Команда AppendEntry використовується лідером і зберігає останні команди, які ним були здійснені. Ця команда водночас служить, як "серцебиття".
Команда RequestVote (github gist) використовується послідовником, якщо він протягом якогось часу (це має налаштувати розробник) не отримує повідомлень від лідера. В цей момент послідовник пропонує себе, як лідера, і просить інші ноди в кластері проголосувати за нього. Інші послідовники мають вибір чи віддати йому свій голос чи ні. Коли досягається більшість (majority), вибори оголошують завершеними, послідовник стає лідером і всі інші кандидати теж конвертуються в послідовників.
В імплементації алгоритма можна виділити декілька частин:
Декілька прикладів реалізації Рафта на різних мовах програмування: