Еј Хабр!
Денес ви пренесуваме превод на сложена статија за имплементација на дистрибуирано заклучување со користење на Redis и ве покануваме да разговарате за изгледите на Redis како тема. Анализа на предметниот алгоритам Редлок од Мартин Клепман, автор на книгата „“, дадено .
Дистрибуираното заклучување е многу корисен примитив кој се користи во многу средини каде што различни процеси мора да работат на споделени ресурси на заемно исклучувачки начин.
Има голем број библиотеки и објави кои опишуваат како да се имплементира DLM (Дистрибуиран менаџер за заклучување) со користење на Redis, но секоја библиотека има различен пристап и гаранциите што ги обезбедуваат се прилично слаби во споредба со она што е остварливо со малку пософистициран дизајн.
Во оваа статија ќе се обидеме да опишеме условен канонски алгоритам кој покажува како да се имплементира дистрибуираното заклучување користејќи Redis. Ќе зборуваме за алгоритам наречен Редлок, имплементира дистрибуиран менаџер за заклучување и, според наше мислење, овој алгоритам е побезбеден од вообичаениот пристап со еден примерок. Се надеваме дека заедницата ќе го анализира, ќе даде повратни информации и ќе го користи како почетна точка за посложени или алтернативни проекти.
Имплементација
Пред да преминеме на описот на алгоритмот, даваме неколку врски до готови имплементации. Тие можат да се користат како референца.
- (имплементација за Руби). Исто така постои Redlock-rb, кој додава пакет (дијамант) за леснотија на дистрибуција, и не само за тоа.
- (Имплементација на Python).
- (имплементација за Asyncio Python).
- (имплементација за PHP).
- (друга имплементација за PHP)
- (PHP библиотека за брави)
- (имплементација за Go).
- (имплементација за Java).
- (имплементација за Perl).
- (имплементација за C++).
- (имплементација за C#/.NET).
- (имплементација за C#/.NET). Со поддршка за асинхронизирани и заклучувачки екстензии.
- (имплементација за C# .NET со конфигурабилна продавница за податоци)
- (имплементација за C# .NET)
- (имплементација за NodeJS). Вклучува поддршка за продолжување на бравите.
Гаранции за безбедност и достапност
Ќе го моделираме нашиот дизајн со само три својства за кои мислиме дека ги обезбедуваат минималните гаранции потребни за ефикасно користење на дистрибуираното заклучување.
- Безбедносна сопственост: меѓусебно исклучување. Во секое време, само еден клиент може да ја држи бравата.
- Достапност Својство А: Нема ќор-сокак. Секогаш е можно на крајот да се стекне заклучување, дури и ако клиентот што го заклучил ресурсот не успее или слета на друг сегмент на дискот.
- Достапност Својство Б: Толеранција на грешки. Сè додека работат поголемиот дел од јазлите на Редис, клиентите можат да ги добијат и ослободат бравите.
Зошто имплементацијата заснована на враќање на неуспехот не е доволна во овој случај
За да разбереме што ќе подобриме, ајде да ја анализираме моменталната состојба на работите со повеќето дистрибуирани библиотеки со заклучување базирани на Redis.
Наједноставниот начин да се заклучи ресурс користејќи Redis е да се создаде клуч во примерот. Вообичаено, клучот се креира со ограничен животен век, тоа се постигнува со користење на функцијата за истекување дадена во Redis, па порано или подоцна овој клуч се ослободува (својство 2 во нашата листа). Кога клиентот треба да го ослободи ресурсот, тој го брише клучот.
На прв поглед, ова решение функционира доста добро, но има проблем: нашата архитектура создава единствена точка на неуспех. Што се случува ако инстанцата на домаќинот Redis не успее? Ајде тогаш да додадеме роб! И ние ќе го користиме ако презентерот е недостапен. За жал, оваа опција не е остварлива. Со ова, нема да можеме правилно да го имплементираме својството за меѓусебно исклучување што ни е потребно за да обезбедиме безбедност, бидејќи репликацијата во Redis е асинхрона.
Очигледно, во таков модел се јавува состојба на трка:
- Клиентот А добива брава на господарот.
- Господарот не успее пред внесувањето на клучот да се пренесе на робот.
- Следбеникот се промовира во лидер.
- Клиентот Б добива брава на истиот ресурс што А веќе го има заклучено. ПОВРЕДА НА БЕЗБЕДНОСТА!
Понекогаш е сосема нормално дека во посебни околности, како што е дефект, многу клиенти можат да ја држат бравата во исто време. Во такви случаи, може да се примени решение засновано на репликација. Во спротивно, го препорачуваме решението опишано во оваа статија.
Правилна имплементација со еден примерок
Пред да се обидеме да ги надминеме недостатоците на конфигурацијата со еден примерок опишана погоре, ајде да разбереме како правилно да се справиме со овој едноставен случај, бидејќи ова решение е всушност валидно во апликации каде што условот за трка е прифатлив од време на време, а исто така и поради блокирањето на единечна инстанца служи како основа што се користи во дистрибуираниот алгоритам опишан овде.
За да добиете брава, направете го ова:
SET resource_name my_random_value NX PX 30000
Оваа команда инсталира клуч само ако веќе не постои (опција NX), со период на важност од 30000 милисекунди (опција PX). Клучот е поставен на „myrandomvalue" Оваа вредност мора да биде единствена кај сите клиенти и сите барања за заклучување.
Во основа, се користи случајна вредност за безбедно ослободување на бравата, со скрипта која му кажува на Редис: отстранете го клучот само ако постои и вредноста зачувана во него е токму она што се очекуваше. Ова се постигнува со користење на следнава скрипта Луа:
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; не е толку безбеден, но веројатно е на висина на задачата во повеќето контексти.
Времето што го користиме како мерка за животниот век на клучот се нарекува „живот на бравата“. Оваа вредност е и износот на времето пред автоматското ослободување на заклучувањето и времето кое клиентот треба да го заврши пред друг клиент да го заклучи тој ресурс, без всушност да ги прекрши меѓусебните гаранции за исклучување. Оваа гаранција е ограничена само на одреден временски период, кој започнува од моментот на купување на бравата.
Значи, разговаравме за добар начин за стекнување и ослободување на бравата. Системот (ако зборуваме за недистрибуиран систем кој се состои од единствена и секогаш достапна инстанца) е безбеден. Да го прошириме овој концепт на дистрибуиран систем, каде што немаме такви гаранции.
Редлок алгоритам
Дистрибуираната верзија на алгоритмот претпоставува дека имаме N Redis мајстори. Овие јазли се целосно независни еден од друг, така што не користиме репликација или кој било друг имплицитен систем за координација. Веќе опфативме како безбедно да стекнете и ослободите брава на еден примерок. Земаме здраво за готово дека алгоритмот, кога работи со една инстанца, ќе го користи токму овој метод. Во нашите примери го поставивме N на 5, што е разумна вредност. Така, ќе треба да користиме 5 мајстори на Redis на различни компјутери или виртуелни машини за да се осигураме дека тие дејствуваат главно независно еден од друг.
За да стекне брава, клиентот ги извршува следните операции:
- Го добива моменталното време во милисекунди.
- Секвенцијално се обидува да добие заклучување на сите N примероци, користејќи го истото име на клучот и случајните вредности во сите случаи. Во Фаза 2, кога клиентот поставува брава по пример, клиентот користи доцнење за да го добие што е доволно кратко во споредба со времето по кое бравата автоматски се ослободува. На пример, ако времетраењето на блокирањето е 10 секунди, тогаш доцнењето може да биде во опсег од ~ 5-50 милисекунди. Ова ја елиминира ситуацијата во која клиентот може да остане блокиран долго време обидувајќи се да стигне до неуспешен јазол Redis: ако примерот е недостапен, тогаш се обидуваме да се поврземе со друг пример што е можно поскоро.
- За да земе брава, клиентот пресметува колку време поминало; За да го направите ова, го одзема од вистинската временска вредност временскиот печат што беше добиен во чекор 1. Ако и само ако клиентот можеше да го добие заклучувањето на повеќето примероци (најмалку 3), и вкупното време потребно за добие бравата, помалку од времетраењето на бравата, се смета дека бравата е добиена.
- Ако е купена брава, времетраењето на заклучувањето се зема како првобитно времетраење на заклучувањето минус изминатото време пресметано во чекор 3.
- Ако клиентот не успее да ја добие бравата поради некоја причина (или не можеше да заклучи 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, што го прави заклучувањето неважечко.
Можете ли да обезбедите формален доказ за безбедност, да наведете постоечки слични алгоритми или да најдете грешка во горенаведеното?
Размислувања за пристапност
Достапноста на системот зависи од три главни карактеристики:
- Автоматско ослободување на бравите (поради истекување на клучевите): клучевите на крајот ќе бидат повторно достапни за да се користат за брави.
- Фактот дека клиентите обично си помагаат едни на други со отстранување на бравите кога саканата брава не е стекната, или е стекната и работата е завршена; па веројатно нема да треба да чекаме да истечат клучевите за повторно да ја добиеме бравата.
- Фактот дека кога клиентот треба повторно да се обиде да купи брава, тој чека релативно подолго време од периодот потребен за стекнување на повеќето брави. Ова ја намалува веројатноста за појава на ситуација со поделен мозок кога се натпреваруваат за ресурси.
Сепак, постои казна за достапност еднаква на 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