Разпределено заключване с помощта на Redis

Хей Хабр!

Днес предлагаме на вашето внимание превод на сложна статия за внедряването на разпределено заключване с помощта на Redis и ви каним да говорите за перспективите на Redis като тема. Анализ на въпросния алгоритъм Redlock от Мартин Клепман, автор на книгата "Приложения с голямо натоварване“, дадено тук.

Разпределеното заключване е много полезен примитив, използван в много среди, където различни процеси трябва да работят върху споделени ресурси по взаимно изключващ се начин.

Има редица библиотеки и публикации, които описват как да внедрите DLM (Distributed Lock Manager) с помощта на 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). С поддръжка за асинхронни и заключващи разширения.
• ScarletLock (имплементация за C# .NET с конфигурируемо хранилище на данни)
• Redlock4Net (имплементация за C# .NET)
• възел-redlock (имплементация за NodeJS). Включва поддръжка за разширяване на брави.

Гаранции за сигурност и наличност

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

1. Защитно свойство: Взаимно изключване. Във всеки един момент само един клиент може да държи ключалката.
2. Свойство на наличност A: Няма блокирания. Винаги е възможно в крайна сметка да се получи заключване, дори ако клиентът, който е заключил ресурса, се провали или се приземи на различен дисков сегмент.
3. Свойство на наличност B: Толерантност към грешки. Докато по-голямата част от възлите на Redis работят, клиентите могат да придобиват и освобождават ключалки.

Защо изпълнението, базирано на възстановяване при повреда, не е достатъчно в този случай
За да разберем какво ще подобрим, нека анализираме текущото състояние на повечето разпределени заключващи библиотеки, базирани на Redis.

Най-лесният начин да заключите ресурс с помощта на Redis е да създадете ключ в екземпляра. Обикновено се създава ключ с ограничен живот, това се постига с помощта на функцията за изтичане, предоставена в Redis, така че рано или късно този ключ се освобождава (свойство 2 в нашия списък). Когато клиентът трябва да освободи ресурса, той изтрива ключа.

На пръв поглед това решение работи доста добре, но има проблем: нашата архитектура създава една единствена точка на повреда. Какво се случва, ако екземплярът на хост Redis се провали? Тогава да добавим роб! И ние ще го използваме, ако водещият е недостъпен. За съжаление тази опция не е жизнеспособна. Правейки това, няма да можем да приложим правилно свойството за взаимно изключване, което ни е необходимо, за да гарантираме сигурността, тъй като репликацията в Redis е асинхронна.

Очевидно в такъв модел възниква състояние на състезание:

1. Клиент A получава заключване на главния.
2. Главният се проваля, преди въвеждането на ключ да бъде прехвърлено към подчинения.
3. Последователят се повишава до лидер.
4. Клиент B получава заключване на същия ресурс, който A вече е заключил. НАРУШЕНИЕ НА СИГУРНОСТТА!

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

Правилно изпълнение с един екземпляр

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

За да получите заключване, направете следното:

SET resource_name my_random_value NX PX 30000

Тази команда инсталира ключ само ако вече не съществува (NX опция), с период на валидност от 30000 XNUMX милисекунди (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 време в разделителна способност от микросекунди плюс идентификатора на клиента; не е толкова сигурен, но вероятно се справя със задачата в повечето контексти.

Времето, което използваме като мярка за живота на ключа, се нарича "живот на ключалката". Тази стойност е както времето, преди заключването да бъде автоматично освободено, така и времето, което клиентът трябва да завърши операция, преди друг клиент да може на свой ред да заключи този ресурс, без всъщност да нарушава гаранции за взаимно изключване. Тази гаранция е ограничена само до определен период от време, който започва от момента на закупуване на ключалката.

Така че обсъдихме добър начин за получаване и освобождаване на заключване. Системата (ако говорим за неразпределена система, състояща се от един единствен и винаги достъпен екземпляр) е защитена. Нека разширим тази концепция към разпределена система, където нямаме такива гаранции.

Алгоритъм на Redlock

Разпространената версия на алгоритъма предполага, че имаме N Redis masters. Тези възли са напълно независими един от друг, така че не използваме репликация или друга имплицитна система за координация. Вече разгледахме как сигурно да придобием и освободим заключване на един екземпляр. Приемаме за даденост, че алгоритъмът, когато работи с един екземпляр, ще използва точно този метод. В нашите примери задаваме 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 на ключа, ако ключът все още съществува и стойността му все още е произволна стойност, получена, когато заключване беше придобито.

Клиентът трябва да обмисли повторно придобиване на заключване само ако е успял да заключи повечето екземпляри в рамките на периода на валидност.

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

Източник: www.habr.com