Використання динамічного кворуму у процесі вибору лідера алгоритму Raft для прийняття консенсусу у розподілених системах



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

Ключові слова--розподілені системи, алгоритм, консенсус, кластер, вузли, розподілений лог.

Вступ

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

Аналіз існуючих методів

Алгоритми Raft [1] і Paxos [2] – це алгоритми прийняття консенсусу у розподілених системах. Обидва вони засновані на підході лідерства: спочатку обирається лідер, що є відповідальним за управління розподіленим логом. Лідер приймає запити від клієнтів і реплікує їх на інші сервери в кластері. Основна відмінність у роботі алгоритмів Raft і Paxos це процес вибору лідера. Алгоритм Paxos сам розподіляє терміни між серверами. Raft же дозволяє будь-якому серверу стати лідером у будь-який термін. Якщо фоловер не отримуватиме жодних повідомлень деякий час, він збільшує на 1 свій номер терміну T, переходить у стан «кандидат», голосує сам за себе і розсилає запит на голосування всім іншим серверам. Коли лідер обраний, він бере на себе управління розподіленим логом. Лідер записує в свій лог новий запис, що містить клієнтську команду, а потім надсилає запит на запис всім фоловерам, для того щоб вони реплікували запис у свій лог. Коли запис буде успішно репліковано на більшості серверів, лідер вважає запис остаточно збереженим і надсилає клієнту інформацію про успішно виконану операцію [3].

Введення динамічного протоколу голосування

Основною причиною високої ресурсоємності алгоритму Raft є використання консенсусного голосування більшості для визначення кворуму Q запису і кворуму Q виборів. Оскільки ці кворуми повинні містити більшість серверів кластера, кластер Raft повинен містити щонайменше $2n+1$ сервери, щоб мати можливість сприймати $n$ збоїв серверів. Ефективнішим рішенням є зробити кворуми динамічними та вимагати, щоб вони містили більшість активних серверів даного кластера. Таким чином протокол динамічного голосування вимагає $n+2$ сервери на кластер, щоб мати змогу сприймати $n$ збоїв. Реалізація цієї властивості у алгоритмі Raft, призводить до 25\% зменшення ресурсоємності Raft. Для зберігання додаткових метаданих про стан вузлів пропонується використовувати когортні набори [4].

Порівняння реалізацій

Розглянемо кластер, що складається із чотирьох вузлів, який вимагає як два сервера, щоб підтримувати нові оновлення даних. У якості показника ефективності було обрано доступність сервера, тобто відрізок часу, коли він буде спроможний обробляти запити клієнта. Для того, аби вивести значення доступності, необхідно зробити деякі припущення щодо роботи кластера. Нехай кожен вузол працює незалежно один від одного і так само незалежно може відмовити. Кожного разу, коли вузол падає, система автоматично запускає процес його відновлення. Ми припускаємо, що падіння серверів це незалежні випадкові події розподілені за експоненціальним законом з середнім $\lambda$. За аналогією, час відновлення роботи вузла має експоненційний розподіл з середнім $\mu$. Обидві гіпотези необхідні для того, аби представити систему у вигляді процесу Маркова з кінцевою кількістю можливих станів. Ми також припускаємо, що лідери можуть швидко визначати відмову вузлів з допомогою періодичних фіктивних запитів. На рис.1 зображена схема переходів між станами кластера.

Рис. 1 Схема зміни станів кластера

Кластер має 9 можливих станів. Стан 4 - це початковий стан системи, коли усі вузли працюють коректно. Відмова будь-якого із вузлів переводить систему у стан 3 і кворум складатиметься з двох вузлів із трьох можливих. Падіння ще одного вузла переведе систему у стан 2, кворум складатиметься з двох вузлів із двох можливих.

Умови рівноваги для такого кластеру:

\begin{eqnarray} 4\lambda p_4=\mu(p_3+p_{3^\prime}) \nonumber \ (3\lambda+\mu)p_3=4\lambda p_4+2\mu p_2+\mu p_{2^\prime}\nonumber\ (3\lambda+\mu)p_{3^\prime}=\mu p_{2^\prime}+2\mu p_{2^{\prime\prime}}\nonumber\ (2\lambda+2\mu)p_2=3\lambda p_3+\mu p_{1^\prime}\nonumber\ (2\lambda+2\mu)p_{2^\prime}=2\lambda p_{3^\prime}+2\mu{(p}_{1^\prime}+p_{1^{\prime\prime}})\nonumber\ (2\lambda+2\mu)p_{2^{\prime\prime}}=\lambda p_{3^\prime}+\mu p_{1^{\prime\prime}}\nonumber\ (\lambda+3\mu)p_{1^\prime}=2\lambda p_2+\lambda p_{2^\prime}+2\mu p_{0^{\prime\prime}}\nonumber\ (\lambda+3\mu)p_{1^{\prime\prime}}=\lambda p_{2^\prime}+2\lambda p_{2^{\prime\prime}}+2\mu p_{0^{\prime\prime}}\nonumber\ 4\mu p_{0^{\prime\prime}}=\lambda(p_{1^\prime}+p_{1^{\prime\prime}}),\nonumber \end{eqnarray} де $p_i$ це ймовірність перебування кластера у стані i з додатковою умовою, що $\sum_{i} p_i=1$.

Розв'яжемо систему лінійних рівнянь і замінимо відношення $\frac{\lambda}{\mu}=\rho$. Отримаємо наступну формулу доступності кластера: \begin{eqnarray} A_{4R}(\rho)=p_4+p_3+p_2=\nonumber\ =\frac{3\rho^6+23\rho^5+\ 68\rho^4+97\rho^3+21\rho+3}{{(\rho+1)}^5(3\rho^3+8\rho^2+6\rho+3)}. \nonumber \end{eqnarray}

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

\begin{eqnarray} A=\frac{1}{\rho+1}, A_3(\rho)=A^3+3A^2(1-A)=\frac{3\rho+1}{{(\rho+1)}^3},\nonumber\ A_5(\rho)=A^5+5A^4(1-A)+{10A}^3{(1-A)}^2=\nonumber\ =\frac{10\rho^2+5\rho+1}{{(\rho+1)}^5}.\nonumber \end{eqnarray}

Побудуємо графіки на основі отриманих формул. На рис.2 зображено графік доступності кластера при трьох конфігураціях: динамічне голосування, класична конфігурація алгоритму Raft з трьома та п'ятьма вузлами. Доступність кластера тут залежить від відношення частоти відмов вузлів до частоти їх відновлення - , що належить проміжку від 0 до 0,20. Нульова відмітка означає те, що кластер ніколи не відмовить, а відмітка 0,20 - те, що кластер буде відповідати на запити клієнта 83,3 відсотки часу.

Рис. 2 Графік порівняння доступності кластера

Як бачимо, динамічний протокол показує практично такі ж показники доступності як і конвенційний Raft на 5-ти вузлах і значно кращі показники, ніж Raft на 3-ох вузлах.

Висновки

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

Література

{1} Ongaro D. In Search of an Understandable Consensus Algorithm / D. Ongaro, J. Ousterhoud. // USENIX Annual Technical Conference. – 2014.

{2} Lamport, L., et al.: Paxos made simple. ACM SIGACT News 32(4), 18–25 (2001).

{3} Howard H. Analysis of Raft Consensus / Heidi Howard. // Cambridge Computer Laboratory. – 2014. – №857.

{4} 4. Jehan-François P. Pirogue, a lighter dynamic version of the Raft distributed consensus algorithm / P. Jehan-François, L. Darrell D. E. // IEEE. – 2015.

Рецензент: доцент кафедри інформаційних систем та технологій КПІ ім. Ігоря Сікорського к.т.н. доцент Сперкач Майя

Dec 5, 2021