Разпределени заключвания с използване на 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).
• Redisson (реализация за 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) минус още известно време (всичко на всичко няколко милисекунди, за да компенсираме разликата във времето между процесите).

Повече за подобни системи, които изискват координиране на разликата във времето, разказва следващата интересна статия: Наемане: ефективен механизъм за устойчивост на грешки за разпределена последователност на файловото кеширане.

Повторна опит при отказ

Когато клиентът не успее да получи блокировката, той трябва да опита отново, из耐ждайки случайно забавяне; това се прави с цел да се разсинхронизира множество клиенти, които едновременно се опитват да придобият блокировката на един и същ ресурс (което може да доведе до ситуация на "разделен мозък", в която няма победители). Освен това, колкото по-бързо клиентът се опитва да придобие блокировката на повечето инстанции на 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