ProHoster > Блог > адміністрування > Розподілені блокування із застосуванням Redis

Розподілені блокування із застосуванням Redis

Привіт, Хабре!

Сьогодні ми пропонуємо до вашої уваги переклад складної статті про реалізацію розподілених блокувань засобами Redis та пропонуємо поговорити про перспективність Redis як теми. Аналіз аналізованого алгоритму Redlock від Мартіна Клеппмана, автора книгиВисоконавантажені програми", наведено тут.

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

Існує ряд бібліотек і постів, що описують, як реалізувати DLM (менеджер розподілених блокувань) за допомогою Redis, але в кожній бібліотеці використовується власний підхід, і гарантії, що надаються при цьому, досить слабкі в порівнянні з тим, що можна досягти за допомогою трохи складнішого проектування.

У цій статті ми спробуємо описати умовно канонічний алгоритм, який демонструє, як реалізувати розподілені блокування за допомогою Redis. Ми поговоримо про алгоритм під назвою redlock, він реалізує менеджер розподілених блокувань і, з погляду, цей алгоритм безпечніше, ніж звичайний підхід із єдиним інстансом. Сподіваємося, що співтовариство його проаналізує, дасть зворотний зв'язок і використовуватиме як відправну точку для реалізації більш складних або альтернативних проектів.

реалізації

Перш, ніж перейти до опису алгоритму, наведемо кілька посилань на готові реалізації. Ними можна скористатися для довідки.

  • Redlock-rb (Реалізація для Ruby). Також існує вилка Redlock-rb, що додає пакет (gem) для зручності розподілу і не тільки для цього.
  • Redlock-py (Реалізація для Python).
  • Aioredlock (Реалізація для Asyncio Python).
  • Redlock-php (Реалізація для PHP).
  • PHPRedisMutex (ще одна реалізація для PHP)
  • cheprasov/php-redis-lock (PHP-бібліотека для блокувань)
  • Redsync (Реалізація для Go).
  • Редіссон (Реалізація для Java).
  • Redis::DistLock (Реалізація для Perl).
  • Redlock-cpp (Реалізація для C++).
  • Redlock-cs (Реалізація для C # /. NET).
  • RedLock.net (Реалізація для C # /. NET). За допомогою розширень async і lock.
  • ScarletLock (Реалізація для C# .NET з конфігурованим сховищем даних)
  • Redlock4Net (Реалізація для C # .NET)
  • node-redlock (Реалізація для NodeJS). Включає підтримку продовження блокування.

Гарантії безпеки та доступності

Ми збираємося змоделювати наш проект лише з трьома властивостями, які, на наш погляд, дають мінімальні гарантії, необхідні для ефективного використання розподілених блокувань.

  1. Властивість безпеки: Взаємний виняток. У будь-який час лише один клієнт може утримувати блокування.
  2. Властивість доступності A: Відсутність взаємних блокувань. Зрештою, завжди можна отримати блокування, навіть якщо клієнт, що заблокував ресурс, відмовить або потрапить в інший сегмент диска.
  3. Властивість доступності B: стійкість до відмов. Поки більшість вузлів Redis працює, клієнти здатні купувати та вивільняти блокування.

Чому реалізації, заснованої на відновленні після відмови, у цьому випадку недостатньо
Щоб зрозуміти, що ж ми збираємося покращувати, проаналізуємо поточний стан справ, що склався з більшістю бібліотек для розподілених блокувань, заснованих на Redis.

Найпростіший спосіб блокувати ресурс за допомогою Redis – створити ключ в інстансі. Зазвичай ключ створюється з обмеженим часом життя, це досягається за допомогою передбаченої Redis можливості expires, тому рано чи пізно цей ключ вивільняється (властивість 2 в нашому списку). Коли клієнту потрібно звільнити ресурс, він видаляє ключ.

На перший погляд, це рішення цілком працює, але є проблема: у нашій архітектурі виникає єдина точка відмови. Що станеться, якщо відмовить провідний інстанс Redis? Давайте тоді додамо відомий! І будемо ним користуватися, якщо ведучий недоступний. На жаль, такий варіант нежиттєздатний. Зробивши так, ми не зможемо правильно реалізувати якість взаємного виключення, потрібну нам для забезпечення безпеки, адже реплікація в Redis асинхронна.

Очевидно, що у такій моделі виникає стан гонки:

  1. Клієнт A набуває блокування на провідному.
  2. Ведучий відмовляє до того, як запис у ключ буде передано веденому.
  3. Ведений підвищується до ведучого.
  4. Клієнт B набуває блокування того самого ресурсу, який вже заблокований A. ПОРУШЕННЯ БЕЗПЕКИ!

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

Правильна реалізація з єдиним інстансом

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

Щоб придбати блокування, зробимо так:

SET resource_name my_random_value NX PX 30000

Ця команда встановлює ключ тільки якщо він ще не існує (опція NX), з терміном дії 30000 мілісекунд (опція PX). Для ключа задається значення “myrandomvalue”. Це значення має бути унікальним у межах усіх клієнтів та всіх запитів на блокування.
В принципі, випадкове значення використовується для безпечного вивільнення блокування за допомогою скрипта, що повідомляє Redis: видаляй ключ, тільки якщо він існує, і значення, збережене в ньому - саме те, що очікувалося. Це досягається за допомогою наступного скрипту Lua:

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

Це важливо, щоб не допустити зняття блокування, зробленого іншим клієнтом. Наприклад, клієнт може придбати блокування, потім заблокуватися в ході якоїсь операції, яка триває довше, ніж термін дії першого блокування (так що термін дії ключа встигне закінчитися), і пізніше видалити блокування, яке поставив якийсь інший клієнт.
Скористайтеся простим DEL небезпечно, оскільки клієнт може видалити блокування, поставлене іншим клієнтом. Навпаки, при використанні вищенаведеного скрипту, кожне блокування «підписано» випадковим рядком, тому видалити його зможе лише той клієнт, який раніше його поставив.

Яким має бути цей випадковий рядок? Вважаю, це має бути 20 байт з /dev/urandom, але можна знайти і менш витратні способи зробити рядок досить унікальним для тих цілей, що перед вами стоять. Наприклад, нормально посіяти RC4 з /dev/urandom, а потім згенерувати на його основі псевдовипадковий потік. Простіше рішення пов'язане з комбінацією часу unix в мікросекундному дозволі плюс ID клієнта; воно не настільки безпечне, але, мабуть, відповідає рівню завдань у більшості контекстів.

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

Отже, ми обговорили хороший спосіб придбання та вивільнення блокування. Система (якщо йдеться про нерозподілену систему, що складається з єдиного і завжди доступного інстансу) безпечна. Давайте розширимо цю концепцію до розподіленої системи, у якій таких гарантій ми не маємо.

Алгоритм Redlock

У розподіленій версії алгоритму передбачається, що ми маємо N провідних Redis. Ці вузли є повністю незалежними один від одного, тому ми не використовуємо реплікацію або будь-яку іншу неявну систему координації. Ми вже розповіли, як безпечно купувати та звільняти блокування на єдиній інстансі. Ми сприймаємо як даність, що алгоритм при роботі з єдиним інстансом використовуватиме саме цей метод. У прикладах ми встановлюємо N рівним 5, це цілком розумне значення. Таким чином, нам потрібно буде використовувати 5 провідних Redis на різних комп'ютерах або віртуальних машинах, щоб гарантувати, що вони будуть діяти в основному незалежно один від одного.

Щоб придбати блокування, клієнт виконує такі операції:

  1. Отримує поточний час у мілісекундах.
  2. Послідовно намагається отримати блокування на всі N інстансів, використовуючи у всіх випадках одне й те саме ім'я ключа та випадкові значення. На етапі 2, встановлюючи блокування для кожного інстансу, клієнт, щоб отримати його, використовує затримку, яка досить коротка в порівнянні з тим часом, після якого блокування автоматично знімається. Наприклад, якщо тривалість блокування становить 10 секунд, то затримка може бути в діапазоні ~5-50 мілісекунд. Таким чином виключається ситуація, в якій клієнт міг би довго залишатися заблокованим, намагаючись достукатися до вузла Redis, що відмовив: якщо інстанс недоступний, то ми якнайшвидше намагаємося з'єднатися з іншою інстансом.
  3. Щоб взяти блокування, клієнт обчислює, скільки часу закінчилося; для цього він віднімає з актуального значення часу ту мітку часу, яка була отримана в кроці 1. Тоді і тільки тоді, коли клієнт зміг отримати блокування на більшості інстансів (як мінімум 3), і загальний час, який знадобився на те, щоб отримати блокування, менше часу дії блокування вважається, що отримання блокування відбулося.
  4. Якщо блокування було отримано, то за термін її дії приймається вихідне значення тривалості блокування мінус час, що минув, обчислений у кроці 3.
  5. Якщо клієнту з якоїсь причини не вдалося отримати блокування (або він не зміг заблокувати N/2+1 інстансів, або час дії блокування виявився негативним), він спробує розблокувати всі інстанси (навіть ті, що, як вважалося, він не міг заблокувати).

Чи є алгоритм асинхронним?

Даний алгоритм ґрунтується на припущенні, що, хоча і немає синхронізованих годин, за якими працювали б усі процеси, локальний час у кожному процесі все одно тече приблизно в одному темпі, і похибка невелика порівняно із загальним часом, після якого блокування автоматично знімається. Це припущення дуже нагадує ситуацію, властиву звичайних комп'ютерів: кожному комп'ютері є локальні годинник, і ми можемо розраховувати те що, що розбіжність у часі різних комп'ютерах невелика.

На даному етапі ми повинні ретельніше сформулювати наше правило взаємного виключення: взаємний виняток гарантований лише за умови, що клієнт, який утримує блокування, завершить роботу за час, протягом якого блокування дійсне (це значення отримано в кроці 3), мінус ще деякий час (всього кілька мілісекунд, щоб компенсувати розбіжність у часі між процесами).

Докладніше про подібні системи, що потребують узгодження розбіжності за часом, розповідає така цікава стаття: Leases: efficient fault-tolerant mechanism for distributed file cache consistency.

Повторна спроба відмовити

Коли клієнту не вдалося отримати блокування, він повинен спробувати це знову зробити, витримавши випадкову затримку; це робиться з метою розсинхронізувати безліч клієнтів, які одночасно намагаються придбати блокування одного і того ж ресурсу (що може призвести до ситуації «розділеного мозку», в якій переможців не буває). Крім того, чим швидше клієнт намагається придбати блокування більшості інстансів Redis, тим вже вікно, в яке може виникнути ситуація розділеного мозку (і тим менша необхідність у повторних спробах). Тому в ідеалі клієнт повинен спробувати одночасно надіслати команди SET до N інстансів за допомогою мультиплексування.

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

Вивільнення блокування

Вивільнення блокування - проста операція, що вимагає просто розблокувати всі інстанси, незалежно від того, чи клієнту здається, що він зміг успішно заблокувати конкретний інстанс.

Міркування щодо безпеки

Чи безпечний алгоритм? Давайте спробуємо уявити, що відбувається у різних сценаріях.

Для початку припустимо, що клієнт зміг отримати блокування над більшістю інстансів. Кожен із інстансів міститиме ключ з одним і тим же часом життя у всіх. Однак, кожен із цих ключів встановлювався у свій момент, тому і термін дії у них закінчиться у різний час. Але, якщо перший ключ був встановлений в момент не гірше T1 (час, який ми вибираємо перед контактом з першим сервером), а останній ключ був встановлений в момент не гірше T2 (час, коли було отримано відгук від останнього сервера), то ми впевнені, що перший ключ у множині, у якого закінчиться термін дії, проіснує як мінімум MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Всі інші ключі закінчаться пізніше, тому ми можемо бути впевнені, що всі ключі будуть одночасно дійсні протягом як мінімум цього часу.

Протягом часу, коли більшість ключів залишаються дійсними, інший клієнт не зможе придбати блокування, оскільки N/2+1 SET NX операцій не може закінчитися успіхом, якщо вже існує N/2+1 ключів. Тому якщо блокування було придбано, то повторно придбати його в той же момент неможливо (це порушувало б властивість взаємного виключення).
Щоправда, ми хочемо переконатися, що багато клієнтів, які одночасно намагаються придбати блокування, не зможуть одночасно в цьому досягти успіху.

Якщо клієнт заблокував більшість інстансів, витративши на цей час близько або більше, ніж максимальний час тривалості блокування, то вважає блокування недійсним і розблокує інстанси. Тому нам доводиться врахувати лише той випадок, у якому клієнту вдалося заблокувати більшість інстансів за час, менший за термін дії. В даному випадку, що стосується вищевикладеного аргументу, за час MIN_VALIDITY жоден клієнт не повинен мати можливість повторно отримати блокування. Тому безліч клієнтів зможуть заблокувати N/2+1 екземплярів за один і той же час (який закінчується в момент завершення етапу 2), тільки коли час для блокування більшості був більшим, ніж час TTL, що перетворює блокування на недійсне.

А ви зможете навести формальний доказ безпеки, вказати наявні схожі алгоритми, чи знайти баг у викладеному?

Міркування щодо доступності

Доступність системи залежить від трьох основних характеристик:

  1. Автоматичне зняття блокування (оскільки термін дії ключів закінчується): зрештою ключі будуть доступні знову, щоб використовуватися для блокування.
  2. Той факт, що клієнти зазвичай допомагають один одному, видаляючи блокування, коли потрібне блокування не було придбано або було придбано, а робота завершилася; тому цілком імовірно, що нам не доведеться чекати закінчення ключів, щоб повторно придбати блокування.
  3. Той факт, що коли клієнту необхідно повторно спробувати отримати блокування, він вичікує протягом порівняно довшого часу, ніж період, який потрібний для придбання більшості блокувань. Так знижується можливість виникнення ситуації розділеного мозку при конкуренції за ресурси.

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

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

Продуктивність, відновлення після відмови та fsync

Багато хто використовує Redis, оскільки потрібно забезпечити високу продуктивність сервера блокувань, на рівні затримок, необхідних для придбання та вивільнення блокувань, а також кількості таких операцій придбання/вивільнення, які вдається виконати в секунду. Для відповідності цій вимогі існує стратегія комунікації з серверами N Redis, щоб знизити затримку. Це стратегія мультиплексування (або «мультиплексування бідняка», при якому сокет ставиться в неблокуючий режим, відправляє всі команди, а зчитує команди пізніше, припускаючи, що час обороту між клієнтом і кожним з інстансів є схожим).

Щоправда, доводиться враховувати ще й міркування, пов'язані з довгостроковим зберіганням даних, якщо ми прагнемо створити модель із впевненим відновленням після відмов.

У принципі, щоб прояснити проблему, припустимо, що конфігуруємо Redis взагалі без тривалого зберігання даних. Клієнт встигає заблокувати 3 із 5 інстансів. Один із інстансів, який клієнту вдалося заблокувати, перезапускається, і в цей момент знову виникає 3 інстанси для одного і того ж ресурсу, який ми можемо заблокувати, і інший клієнт може, у свою чергу, заблокувати перезапущений інстанс, порушуючи якість безпеки, яка передбачає винятковість блокувань.

Якщо увімкнути випереджувальне збереження даних (AOF), ситуація трохи покращиться. Наприклад, можна підвищити сервер, відправивши команду SHUTDOWN та перезапустивши його. Оскільки операції закінчення в Redis семантично реалізовані таким чином, що час продовжує текти, також коли сервер вимкнений, з усіма вимогами все нормально. Нормально доти, доки забезпечується штатне відключення. А що робити при перебоях із харчуванням? Якщо Redis налаштовано за замовчуванням, із синхронізацією fsync на диску кожну секунду, то можливо, що після перезапуску ми не дорахуємося нашого ключа. Теоретично, якщо ми хочемо гарантувати безпеку блокувань при будь-якому перезапуску інстансу, то маємо включити fsync=always у налаштуваннях довгострокового збереження даних. Це повністю вб'є продуктивність до рівня таких CP-систем, які традиційно застосовуються для безпечної реалізації розподілених блокувань.

Але ситуація краща, ніж здається на перший погляд. В принципі, безпека алгоритму зберігається, оскільки, коли інстанс перезапускається після відмови, він більше не бере участі в жодному блокуванні, активному зараз.

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

Використовуючи відкладені перезапуски, в принципі можна досягти безпеки і за відсутності будь-якої довготривалої зберігання в Redis. Зазначимо, що це може вилитися в штраф за порушення доступності. Наприклад, при відмові більшості інстансів система стане глобально недоступна на час TTL (і жоден ресурс заблокувати в цей час буде не можна).

Підвищуємо доступність алгоритму: продовжуємо блокування

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

Клієнт повинен вважати блокування повторно придбаним лише у випадку, коли йому вдалося заблокувати більшість інстансів протягом часу дії.

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

Джерело: habr.com

Додати коментар або відгук