Розробники програмують машини, щоб ті робили те, що ми, їх творці, бажаємо. Це приємне відчуття, коли ти пишеш код і потім цей код робить для тебе саме таку каву, як ти хочеш, чи генерує тобі 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)