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