Пошук уроків, статей та іншого контенту
Розглянемо алгоритми leader election, терміни дії лідерства, split-brain та відновлення після відмови лідера.
Leader election — це процедура, під час якої група вузлів обирає один вузол координатором. Лідер може:
приймати записи та зміни стану;
призначати порядок операцій;
координувати фонові задачі;
видавати унікальні токени або версії;
повідомляти іншим вузлам актуальний стан.
Вибір лідера потрібен, коли одночасно виконувати певну дію має лише один вузол. Наприклад:
запускати планувальник періодичної задачі;
обробляти чергу в режимі single consumer;
виконувати міграцію даних;
приймати записи до реплікованого журналу;
керувати розподіленим ресурсом.
Важливо розділяти дві властивості:
Safety — одночасно не повинно існувати двох дійсних лідерів у межах одного кворуму.
Liveness — якщо система працює та між вузлами є зв’язок, з часом має з’явитися лідер.
На практиці неможливо гарантувати обидві властивості без компромісів у мережі. Система часто надає перевагу safety: краще тимчасово не мати лідера, ніж дозволити двом вузлам одночасно змінювати стан.
У простому алгоритмі кожен вузол має пріоритет або ідентифікатор. Якщо лідер недоступний, вузол із найбільшим пріоритетом оголошує себе лідером і повідомляє про це інші вузли.
Такий підхід називають bully algorithm.
Типовий сценарій:
Вузол помічає, що лідер не відповідає.
Він надсилає повідомлення вузлам із вищим пріоритетом.
Якщо жоден із них не відповідає, він стає лідером.
Якщо відповідає вузол із вищим пріоритетом, вибори продовжуються вже там.
Новий лідер повідомляє всю групу про свій статус.
Переваги:
проста модель;
легко реалізувати в невеликій групі;
не потрібен складний журнал операцій.
Недоліки:
багато повідомлень під час одночасних виборів;
потрібна узгоджена інформація про доступність вузлів;
мережеве розділення може створити кількох «лідерів»;
сам факт перемоги вузла не гарантує, що він має актуальний стан даних.
У ring election вузли логічно утворюють кільце. Повідомлення про вибори передається від вузла до вузла, а кожен додає до нього свій ідентифікатор.
Після проходження кільця обирається, наприклад, вузол із найбільшим ідентифікатором. Потім інше повідомлення поширює інформацію про нового лідера.
Цей алгоритм передбачуваний, але вимагає:
знати наступний вузол у кільці;
відновлювати кільце після відмов;
коректно обробляти одночасні вибори.
Для сучасних систем із реплікованим станом частіше використовують алгоритми на основі кворуму та консенсусу.
Алгоритми Raft і Paxos вирішують не лише питання «хто лідер», а й питання узгодженого стану групи.
У спрощеній моделі Raft вузол має один із трьох станів:
Follower — очікує повідомлення від лідера;
Candidate — бере участь у виборах;
Leader — координує реплікацію.
Вибори в Raft відбуваються за термами (terms):
Follower не отримує heartbeat протягом election timeout.
Він збільшує номер терму.
Переходить у стан Candidate.
Голосує за себе.
Надсилає запити на голосування іншим вузлам.
Стає лідером після отримання більшості голосів.
Регулярно надсилає heartbeat.
Якщо отримує повідомлення з більшим term, переходить у стан Follower.
Для кластера з N вузлів кворум зазвичай дорівнює:
floor(N / 2) + 1Тому:
кластер із 3 вузлів переживає відмову 1 вузла;
кластер із 5 вузлів переживає відмову 2 вузлів;
кластер із 4 вузлів також переживає лише 1 відмову, хоча містить більше вузлів.
Непарна кількість вузлів зазвичай ефективніша для кворумних систем.
Терм — це монотонно зростаючий номер епохи лідерства.
Він потрібен, щоб відрізняти:
старого лідера від нового;
актуальне рішення від застарілого;
повідомлення з попереднього запуску виборів;
delayed message від поточного повідомлення.
Наприклад:
term 7: лідер A
term 8: лідер B
term 9: лідер CЯкщо вузол отримує повідомлення з term = 9, перебуваючи в term = 7, він має визнати свою інформацію застарілою та оновити term до 9.
Якщо вузол із term = 7 пізніше знову з’явиться в мережі, його повідомлення не повинні мати сили проти вузлів із term 9.
Це різні поняття:
Term — логічна версія або епоха лідерства.
Lease — обмежене в часі право вважати вузол лідером.
Fencing token — монотонний токен, який захищає ресурс від застарілих лідерів.
Один term може тривати довго, якщо лідер стабільно працює. Lease обов’язково має час завершення. Fencing token потрібен, коли старий лідер може продовжувати виконання операцій після втрати лідерства.
Лідерство не повинно бути безстроковим без механізму перевірки. Вузол може вийти з ладу, зависнути або втратити зв’язок із групою.
Лідер регулярно надсилає heartbeat:
Leader A → Follower B: heartbeat, term=12
Leader A → Follower C: heartbeat, term=12Якщо follower не отримує heartbeat протягом election timeout, він може почати нові вибори.
Параметри мають бути узгоджені:
heartbeat interval має бути значно меншим за election timeout;
election timeout повинен враховувати затримки мережі та паузи runtime;
timeout кандидатів часто рандомізують, щоб усі вузли не почали вибори одночасно.
Наприклад:
heartbeat interval: 100 мс
election timeout: випадкове значення між 500 і 900 мсЦе не універсальні значення. Їх потрібно підбирати за виміряними характеристиками системи.
Lease — це право, яке дійсне до певного моменту часу. Лідер повинен періодично продовжувати lease.
Спрощена логіка:
lease_valid = current_time < lease_expirationЯкщо продовжити lease не вдалося, вузол має припинити лідерські операції.
Однак перевірка локального часу небезпечна у розподіленій системі. Годинники вузлів можуть:
відрізнятися;
коригуватися;
мати різну точність;
зупинятися під час пауз процесу.
Тому lease часто підтверджують через зовнішній узгоджений сервіс або кворум. Навіть тоді потрібно враховувати затримку між моментом втрати lease та моментом, коли старий лідер це усвідомить.
Інший варіант — прив’язати лідерство до сесії або ephemeral-запису в координаційному сервісі.
Якщо клієнт втрачає сесію, його запис видаляється, а інші вузли можуть почати вибори. Такий механізм спрощує виявлення відмов, але не скасовує проблему уже запущених операцій старого лідера.
Split-brain — це ситуація, у якій різні частини кластера вважають лідерами різні вузли.
Наприклад, кластер із чотирьох вузлів розділився на дві частини:
Група A: вузли 1, 2
Група B: вузли 3, 4Якщо алгоритм дозволяє лідеру обиратися без кворуму, обидві групи можуть продовжити роботу. Тоді:
обидва лідери приймають записи;
клієнти бачать різні результати;
записи можуть конфліктувати;
після відновлення мережі потрібне складне злиття станів.
Припустімо, вузол A не отримує відповіді від кластера. Це може означати:
кластер справді недоступний;
зламався канал між A та кластером;
A завис;
відповіді затримуються;
A ізольований, але інші вузли продовжують роботу.
Локальний timeout не дає змоги визначити, який саме сценарій відбувається. Тому правило «якщо немає відповіді — стати лідером» небезпечне.
Щоб уникнути split-brain, новий лідер повинен отримати більшість голосів.
У кластері з п’яти вузлів група з двох вузлів не може обрати легітимного лідера. Для цього потрібні щонайменше три голоси.
Це дає важливу властивість: дві різні більшості в одному кластері обов’язково перетинаються хоча б одним вузлом. Вузол не може коректно проголосувати за двох різних кандидатів в одному term.
Кворум не завжди достатній. Старий лідер може втратити зв’язок із кластером, але продовжити виконувати операції над зовнішнім ресурсом.
Наприклад:
Вузол A був лідером і отримав доступ до сховища.
Мережевий канал між A та кластером зламався.
Кластер обрав вузол B.
A не знає про це та продовжує записувати у сховище.
B також починає записувати.
Fencing змушує старого лідера втратити можливість змінювати ресурс. Це може бути:
завершення або ізоляція старого процесу;
відкликання доступу;
блокування старої сесії;
використання монотонного fencing token на кожній операції.
Приклад із токенами:
A отримав token 41
B отримав token 42Сховище приймає операцію лише тоді, коли її token не старший за допустимий:
if operation.token < latest_token:
reject operationТоді запізніла операція A із token 41 буде відхилена після того, як B отримав token 42.
Fencing token має перевіряти саме ресурс, до якого звертається лідер. Просте зберігання токена лише в пам’яті лідера не захищає від старих операцій.
Наступний приклад демонструє важливу ідею: вузол може втратити lease, але вже запущена операція не повинна змінити ресурс після отримання нового токена.
Це навчальна симуляція одного процесу, а не реалізація розподіленого протоколу.
class ProtectedResource {
constructor() {
this.latestToken = 0;
this.value = 0;
}
issueToken() {
this.latestToken += 1;
return this.latestToken;
}
write(token, value) {
if (token < this.latestToken) {
throw new Error(
`Операцію відхилено: token ${token} застарілий, ` +
`актуальний token ${this.latestToken}`
);
}
this.value = value;
console.log(`Ресурс оновлено до ${value} токеном ${token}`);
}
}
class Leader {
constructor(name, resource, leaseDurationMs) {
this.name = name;
this.resource = resource;
this.leaseDurationMs = leaseDurationMs;
this.leaseExpiresAt = 0;
this.token = 0;
}
acquireLeadership(now) {
this.token = this.resource.issueToken();
this.leaseExpiresAt = now + this.leaseDurationMs;
console.log(
`${this.name} став лідером: token=${this.token}, ` +
`lease до ${this.leaseExpiresAt}`
);
}
renewLease(now) {
if (now >= this.leaseExpiresAt) {
console.log(`${this.name} не може продовжити прострочений lease`);
return false;
}
this.leaseExpiresAt = now + this.leaseDurationMs;
console.log(`${this.name} продовжив lease до ${this.leaseExpiresAt}`);
return true;
}
write(now, value) {
if (now >= this.leaseExpiresAt) {
throw new Error(`${this.name} втратив lease і не може писати`);
}
this.resource.write(this.token, value);
}
}
const resource = new ProtectedResource();
const oldLeader = new Leader("A", resource, 1000);
const newLeader = new Leader("B", resource, 1000);
oldLeader.acquireLeadership(0);
oldLeader.write(100, 10);
// A втрачає зв'язок і не знає, що його lease завершився.
// Кластер обирає B, який отримує новий fencing token.
newLeader.acquireLeadership(1500);
newLeader.write(1600, 20);
// Запізніла операція A не повинна змінити ресурс.
try {
oldLeader.write(1700, 30);
} catch (error) {
console.log(error.message);
}
console.log(`Фінальне значення ресурсу: ${resource.value}`);Очікуваний результат містить відхилення операції старого лідера:
A став лідером: token=1, lease до 1000
Ресурс оновлено до 10 токеном 1
B став лідером: token=2, lease до 2500
Ресурс оновлено до 20 токеном 2
A втратив lease і не може писати
Фінальне значення ресурсу: 20У реальній системі перевірка lease та видача токена повинні виконуватися через спільний узгоджений компонент або протокол. Локальний JavaScript-об’єкт не забезпечує розподілену гарантію.
Відмова лідера може бути різною:
процес завершився;
вузол втратив мережу;
вузол завис, але операційна система ще вважає його живим;
вузол перевантажений і не встигає надсилати heartbeat;
вузол бачить лише частину кластера.
Після підозри на відмову вузли не повинні одразу призначати нового лідера без перевірки кворуму.
Типовий процес відновлення:
Follower перестає отримувати heartbeat.
Чекає до завершення election timeout.
Збільшує term.
Переходить у Candidate.
Надсилає запити на голосування.
Вузли порівнюють term і стан журналу кандидата.
Кандидат із більшістю голосів стає лідером.
Новий лідер надсилає heartbeat.
Репліки синхронізують відсутні записи.
Старий лідер після повернення бачить більший term і переходить у Follower.
У системі з реплікованим журналом не можна обирати лідером лише вузол із найменшим network latency або найбільшим пріоритетом. Новий лідер має мати достатньо актуальний стан.
Інакше можливий сценарій:
Вузол A отримав записи, але вони ще не були підтверджені більшістю.
A відмовив.
Вузол B став лідером зі старішим журналом.
Непідтверджені записи A були видалені або замінені.
Це нормальна поведінка для непідтверджених записів. Тому клієнт не повинен вважати запис надійно збереженим лише тому, що один лідер відповів «успішно».
У Raft кандидат має отримати голоси від вузлів, якщо його журнал не менш актуальний за журнал голосуючого вузла. Для цього порівнюють:
term останнього запису;
індекс останнього запису.
Під час переходу між лідерами потрібно визначити, які операції вважаються підтвердженими.
Корисне розділення:
прийнята лідером — лідер отримав запит;
записана локально — операція потрапила до журналу одного вузла;
реплікована — операція є на кількох вузлах;
committed — операція підтверджена кворумом і не повинна бути скасована;
застосована — операція змінює стан прикладного сервісу.
Після відмови лідера:
committed-записи мають зберегтися;
записи, які не отримали кворуму, можуть бути видалені;
новий лідер повинен відновити однаковий порядок committed-записів;
клієнти можуть повторно надіслати невизначені запити.
Клієнт може отримати timeout після того, як лідер уже застосував операцію. Повторне надсилання може створити дубль.
Тому операціям часто надають унікальний ідентифікатор:
request_id = "payment-8f31..."Лідер або прикладний стан зберігає інформацію про вже оброблені request_id. Повторний запит повертає попередній результат замість повторного виконання.
Це особливо важливо під час повторного підключення після виборів.
Мережа може доставити повідомлення із затримкою. Тому кожне лідерське повідомлення має містити достатню інформацію для перевірки актуальності:
leader_id
term
log_index
request_id
fencing_tokenОтримувач має:
відхилити повідомлення з меншим term;
оновити свій term після повідомлення з більшим term;
перевірити, чи має відправник право виконувати операцію;
перевірити fencing token на захищеному ресурсі;
не покладатися лише на поле leader_id.
Саме ім’я вузла не доводить, що він досі є лідером.
Під час проєктування потрібно визначити:
кількість вузлів;
розмір кворуму;
heartbeat interval;
election timeout;
максимальну затримку мережі;
допустимий час відновлення;
поведінку під час втрати кворуму;
механізм fencing;
спосіб зберігання term і токенів;
правила для невизначених клієнтських запитів.
Занадто короткий election timeout спричиняє зайві вибори під час тимчасових затримок. Занадто довгий timeout збільшує час відновлення після справжньої відмови.
Потрібно враховувати не лише середню затримку, а й хвости розподілу: рідкісні, але великі затримки, паузи збирача сміття, перевантаження CPU та затримки диска.
Розглянемо кластер із трьох вузлів:
A — лідер, term 10
B — follower, term 10
C — follower, term 10A перестає надсилати heartbeat.
B очікує до завершення свого election timeout.
B збільшує term до 11.
B голосує за себе.
C голосує за B.
B отримує 2 із 3 голосів.
B стає лідером term 11.
B надсилає heartbeat до C.
B продовжує реплікацію журналу.
A знову підключається.
A надсилає повідомлення з term 10.
B відповідає або надсилає повідомлення з term 11.
A бачить більший term.
A переходить у Follower.
A синхронізує стан із B.
A не може продовжувати лідерські операції лише тому, що його процес не завершувався.
Якщо будь-яка ізольована група може обрати лідера, split-brain стає очікуваною поведінкою.
Правильно: вимагати кворум і відмовлятися від змін стану без нього.
Timeout доводить лише те, що повідомлення не було отримано вчасно. Він не доводить, що інший вузол вимкнений.
Правильно: поєднувати timeout із кворумом, term і fencing.
Прострочений запис у координаційному сховищі не гарантує, що старий лідер уже припинив роботу.
Правильно: додавати fencing token або інший механізм блокування старих операцій.
Порівнювати час різних вузлів без урахування похибки небезпечно.
Правильно: використовувати узгоджений механізм продовження lease та запас на clock drift.
Після перезапуску вузол може забути, у якому term він голосував, і порушити правило «один голос за term».
Правильно: критичний стан протоколу зберігати на надійному носії до підтвердження відповіді.
Локальна відповідь лідера не означає, що операція отримала кворум.
Правильно: чітко розрізняти локальний запис, реплікацію та commit.
Після failover клієнт може повторити запит, результат якого він не отримав.
Правильно: використовувати request_id і зберігати результат обробленої операції.
Старий процес може бути живим довше, ніж його lease.
Правильно: перевіряти fencing token на стороні ресурсу, а не лише всередині лідера.
Leader election обирає координатора серед кількох вузлів.
Safety означає відсутність двох дійсних лідерів, а liveness — можливість знову обрати лідера.
Алгоритми bully та ring простіші, але потребують особливої уваги до split-brain.
Консенсусні алгоритми використовують кворум, терми та перевірку актуальності журналу.
Term — це логічна епоха, lease — обмежене в часі право, а fencing token — захист ресурсу від старого лідера.
Heartbeat виявляє відсутність зв’язку, але сам по собі не запобігає split-brain.
Для виборів потрібен кворум: без більшості кластер має припинити операції, що змінюють стан.
Після повернення старий лідер повинен побачити більший term і перейти у Follower.
Непідтверджені записи можуть бути втрачені під час зміни лідера, а committed-записи мають зберегтися.
Клієнтські операції мають бути ідемпотентними, оскільки після відмови можливі повторні запити.