Дистрибуирано закључавање помоћу Редис-а

Хеј Хабр!

Данас вам представљамо превод сложеног чланка о имплементацији дистрибуираног закључавања помоћу Редис-а и позивамо вас да разговарате о перспективама Редиса као теме. Анализа дотичног Редлоцк алгоритма од Мартина Клеппмана, аутора књиге "Апликације са великим оптерећењем", дато овде.

Дистрибуирано закључавање је веома користан примитив који се користи у многим окружењима где различити процеси морају да раде на заједничким ресурсима на међусобно искључив начин.

Постоји велики број библиотека и постова који описују како имплементирати ДЛМ (Дистрибутед Лоцк Манагер) користећи Редис, али свака библиотека има другачији приступ и гаранције које пружају су прилично слабе у поређењу са оним што је могуће постићи са мало софистициранијим дизајном.

У овом чланку ћемо покушати да опишемо условни канонски алгоритам који показује како имплементирати дистрибуирано закључавање користећи Редис. Причаћемо о алгоритму тзв Редлоцк, имплементира дистрибуирани менаџер закључавања и, по нашем мишљењу, овај алгоритам је сигурнији од уобичајеног приступа са једном инстанцом. Надамо се да ће га заједница анализирати, дати повратне информације и користити га као полазну тачку за сложеније или алтернативне пројекте.

Имплементација

Пре него што пређемо на опис алгоритма, дајемо неколико веза ка готовим имплементацијама. Могу се користити за референцу.

• Редлоцк-рб (имплементација за Руби). Постоји и виљушка Редлоцк-рб, који додаје пакет (гем) ради лакше дистрибуције, и не само због тога.
• Редлоцк-пи (Питхон имплементација).
• Аиоредлоцк (имплементација за Асинцио Питхон).
• Редлоцк-пхп (имплементација за ПХП).
• ПХПРедисМутек (друга имплементација за ПХП)
• цхепрасов/пхп-редис-лоцк (ПХП библиотека за браве)
• Редсинц (имплементација за Го).
• Редиссон (имплементација за Јаву).
• Редис::ДистЛоцк (имплементација за Перл).
• Редлоцк-цпп (имплементација за Ц++).
• Редлоцк-цс (имплементација за Ц#/.НЕТ).
• РедЛоцк.нет (имплементација за Ц#/.НЕТ). Са подршком за асинхронизована и закључана проширења.
• СцарлетЛоцк (имплементација за Ц# .НЕТ са конфигурабилним складиштем података)
• Редлоцк4Нет (имплементација за Ц# .НЕТ)
• ноде-редлоцк (имплементација за НодеЈС). Укључује подршку за проширење брава.

Гаранције сигурности и доступности

Моделираћемо наш дизајн са само три својства за која мислимо да пружају минималне гаранције потребне за ефикасно коришћење дистрибуираног закључавања.

1. Сигурносна имовина: Међусобно искључење. У било ком тренутку, само један клијент може да држи браву.
2. Својство доступности А: Нема застоја. Увек је могуће на крају добити закључавање, чак и ако клијент који је закључао ресурс не успе или дође на други сегмент диска.
3. Својство доступности Б: Толеранција грешака. Све док већина Редис чворова ради, клијенти су у могућности да прибаве и отпусте браве.

Зашто имплементација заснована на опоравку од квара није довољна у овом случају
Да бисмо разумели шта ћемо да побољшамо, хајде да анализирамо тренутно стање са већином дистрибуираних библиотека закључавања заснованих на Редис-у.

Најједноставнији начин да закључате ресурс користећи Редис је креирање кључа у инстанци. Типично, кључ се креира са ограниченим животним веком, то се постиже коришћењем функције истека обезбеђене у Редис-у, тако да се пре или касније овај кључ ослобађа (својство 2 на нашој листи). Када клијент треба да ослободи ресурс, брише кључ.

На први поглед, ово решење функционише прилично добро, али постоји проблем: наша архитектура ствара једну тачку квара. Шта се дешава ако хост Редис инстанца не успе? Хајде онда да додамо роба! И користићемо га ако презентер није доступан. Нажалост, ова опција није одржива. На тај начин нећемо моћи правилно да применимо својство међусобног искључивања које нам је потребно да бисмо обезбедили безбедност, јер је репликација у Редис-у асинхрона.

Очигледно, у таквом моделу долази до стања трке:

1. Клијент А закључава мастер.
2. Мастер не успе пре него што се унос кључа пренесе на славе.
3. Следбеник се унапређује у лидера.
4. Клијент Б добија закључавање на истом ресурсу који је А већ закључао. КРШЕЊЕ БЕЗБЕДНОСТИ!

Понекад је сасвим нормално да у посебним околностима, као што је квар, многи клијенти могу истовремено да држе браву. У таквим случајевима може се применити решење засновано на репликацији. У супротном, препоручујемо решење описано у овом чланку.

Исправна имплементација са једном инстанцом

Пре него што покушамо да превазиђемо недостатке горе описане конфигурације са једном инстанцом, хајде да разумемо како да правилно поступамо са овим једноставним случајем, пошто је ово решење заправо важеће у апликацијама где је услов трке прихватљив с времена на време, а такође и због блокирања на појединачна инстанца служи као основа која се користи у овде описаном дистрибуираном алгоритму.

Да бисте добили браву, урадите ово:

SET resource_name my_random_value NX PX 30000

Ова команда инсталира кључ само ако већ не постоји (НКС опција), са периодом важења од 30000 милисекунди (опција ПКС). Кључ је постављен на „myrandomvalue" Ова вредност мора бити јединствена за све клијенте и све захтеве за закључавање.
У основи, насумична вредност се користи за безбедно отпуштање браве, са скриптом која говори Редис-у: уклоните кључ само ако постоји и вредност сачувана у њему је управо оно што се очекивало. Ово се постиже коришћењем следеће Луа скрипте:

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

Ово је важно како би се спречило уклањање браве коју држи други клијент. На пример, клијент може да стекне браву, затим да се закључа у некој операцији која траје дуже од прве браве (тако да кључ има времена да истекне), а касније уклони браву коју је неки други клијент поставио.
Коришћење једноставног ДЕЛ-а није безбедно јер клијент може да уклони браву коју држи други клијент. Насупрот томе, када користите горњу скрипту, свака брава је „потписана“ насумичним низом, тако да само клијент који ју је претходно поставио може да је уклони.

Шта би требало да буде овај насумични низ? Претпостављам да би требало да буде 20 бајтова из /дев/урандом, али можете пронаћи јефтиније начине да стринг учините довољно јединственим за ваше потребе. На пример, било би у реду да се РЦ4 зачини са /дев/урандом и затим генерише псеудо-случајни ток из њега. Једноставније решење укључује комбинацију уникс времена у резолуцији у микросекундама плус ИД клијента; није тако безбедно, али вероватно одговара задатку у већини контекста.

Време које користимо као меру животног века кључа назива се „век трајања браве“. Ова вредност је и количина времена пре него што се закључавање аутоматски отпусти и време које клијент мора да заврши операцију пре него што други клијент може заузврат да закључа тај ресурс, а да заправо не крши гаранције међусобног искључивања. Ова гаранција је ограничена само на одређени временски период, који почиње од тренутка куповине браве.

Дакле, разговарали смо о добром начину за стицање и отпуштање браве. Систем (ако говоримо о недистрибуираном систему који се састоји од једне и увек доступне инстанце) је безбедан. Хајде да проширимо овај концепт на дистрибуирани систем, где немамо такве гаранције.

Редлоцк алгоритам

Дистрибуирана верзија алгоритма претпоставља да имамо Н Редис мастера. Ови чворови су потпуно независни један од другог, тако да не користимо репликацију или било који други имплицитни систем координације. Већ смо покрили како да безбедно набавите и отпустите закључавање на једној инстанци. Узимамо здраво за готово да ће алгоритам, када ради са једном инстанцом, користити управо овај метод. У нашим примерима поставили смо Н на 5, што је разумна вредност. Стога ћемо морати да користимо 5 Редис мастера на различитим рачунарима или виртуелним машинама како бисмо осигурали да делују углавном независно један од другог.

Да би стекао браву, клијент обавља следеће операције:

1. Добија тренутно време у милисекундама.
2. Узастопно покушава да добије закључавање на свих Н инстанци, користећи исто име кључа и насумичне вредности у свим случајевима. У фази 2, када клијент поставља закључавање за сваку инстанцу, клијент користи одлагање да га преузме које је довољно кратко у поређењу са временом након којег се закључавање аутоматски ослобађа. На пример, ако је трајање блокирања 10 секунди, онда кашњење може бити у опсегу од ~5-50 милисекунди. Ово елиминише ситуацију у којој би клијент могао остати блокиран дуже време покушавајући да дође до неуспелог Редис чвора: ако је инстанца недоступна, покушавамо да се повежемо са другом инстанцом што је пре могуће.
3. Да би преузео браву, клијент израчунава колико је времена прошло; Да би то урадио, одузима од стварне временске вредности временску ознаку која је добијена у кораку 1. Ако и само ако је клијент успео да добије закључавање на већини инстанци (најмање 3), и укупно време потребно за добијање закључавања, мање од трајања закључавања, закључавање се сматра добијеним.
4. Ако је закључавање стечено, трајање закључавања се узима као првобитно трајање закључавања минус протекло време израчунато у кораку 3.
5. Ако клијент не успе да добије закључавање из неког разлога (или није могао да закључа Н/2+1 инстанце, или је трајање закључавања било негативно), онда ће покушати да откључа све инстанце (чак и оне за које је мислио да не може да блокира ).

Да ли је алгоритам асинхрони?

Овај алгоритам се заснива на претпоставци да, иако не постоји синхронизовани сат на којем би сви процеси радили, локално време у сваком процесу и даље тече приближно истим темпом, а грешка је мала у поређењу са укупним временом након којег је закључавање аутоматски пуштен. Ова претпоставка је веома слична ситуацији типичној за обичне рачунаре: сваки рачунар има локални сат, а обично можемо рачунати на чињеницу да је временска разлика између различитих рачунара мала.

У овом тренутку, морамо пажљивије формулисати наше правило међусобног искључења: узајамно искључење је загарантовано само ако клијент који држи браву изађе током времена када је закључавање важеће (ова вредност добијена у кораку 3), минус још неко време (укупно неколико милисекунди да се надокнади временска разлика између процеса).

Следећи занимљив чланак говори више о таквим системима који захтевају координацију временских интервала: Изнајмљивање: ефикасан механизам отпоран на грешке за доследност дистрибуиране кеш меморије датотека.

Покушајте поново у случају неуспеха

Када клијент не успе да добије закључавање, мора да покуша поново након случајног одлагања; ово се ради да би се де-синхронизовали више клијената који покушавају да стекну закључавање истог ресурса у исто време (што може довести до ситуације „раздвојеног мозга“ у којој нема победника). Поред тога, што брже клијент покушава да закључа већину Редис инстанци, то је ужи прозор у коме може доћи до ситуације подељеног мозга (и мања је потреба за поновним покушајима). Стога, у идеалном случају, клијент треба да покуша да пошаље СЕТ команде на Н инстанци истовремено користећи мултиплексирање.

Овде је вредно нагласити колико је важно да клијенти који не успеју да стекну већину брава отпусте (делимично) стечене браве, тако да не морају да чекају да кључ истекне пре него што се брава на ресурсу може поново набавити (мада ако дође до фрагментације мреже и клијент изгуби контакт са Редис инстанцама, онда морате да платите казну доступности док чекате да кључ истекне).

Отпуштање браве

Откључавање закључавања је једноставна операција која једноставно захтева откључавање свих инстанци, без обзира на то да ли се чини да је клијент успешно закључао одређену инстанцу.

Безбедносна разматрања

Да ли је алгоритам безбедан? Покушајмо да замислимо шта се дешава у различитим сценаријима.

За почетак, претпоставимо да је клијент успео да закључа већину инстанци. Свака инстанца ће садржати кључ са истим животним веком за све. Међутим, сваки од ових кључева је инсталиран у различито време, тако да ће истећи у различито време. Али, ако је први кључ инсталиран у време које није горе од Т1 (време које бирамо пре него што контактирамо први сервер), а последњи кључ је инсталиран у време које није горе од Т2 (време када је примљен одговор са последњег сервера), онда смо уверени да ће први кључ у сету који истиче преживети барем MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Сви остали кључеви ће истећи касније, тако да можемо бити сигурни да ће сви кључеви истовремено важити бар овај пут.

Током времена док већина кључева остаје важећа, други клијент неће моћи да преузме браву, пошто Н/2+1 СЕТ НКС операције не могу успети ако већ постоји Н/2+1 кључева. Дакле, када је брава стечена, немогуће је поново је стећи у истом тренутку (ово би нарушило својство међусобног искључивања).
Међутим, желимо да будемо сигурни да више клијената који покушавају да закључају у исто време не могу да успеју у исто време.

Ако је клијент закључао већину инстанци отприлике или дуже од максималног трајања закључавања, сматраће закључавање неважећим и откључати инстанце. Дакле, морамо само да узмемо у обзир случај у којем је клијент успео да блокира већину инстанци у времену краћем од истека рока. У овом случају, у вези са горњим аргументом, током времена MIN_VALIDITY ниједан клијент не би требало да буде у могућности да поново преузме браву. Због тога ће многи клијенти моћи да закључају Н/2+1 инстанце у исто време (које се завршава на крају фазе 2) само када је време за закључавање већине било веће од ТТЛ времена, што закључавање чини неважећим.

Можете ли да пружите формални доказ безбедности, назначите постојеће сличне алгоритме или пронађете грешку у горе наведеном?

Разматрања приступачности

Доступност система зависи од три главне карактеристике:

1. Аутоматско отпуштање брава (како кључеви истичу): кључеви ће на крају поново бити доступни за употребу за браве.
2. Чињеница да клијенти обично помажу једни другима уклањањем браве када жељена брава није набављена, или је стечена, а посао је завршен; тако да је вероватно да нећемо морати да чекамо да кључеви истеку да бисмо поново преузели браву.
3. Чињеница да када клијент треба поново да покуша да преузме браву, он чека релативно дуже време од периода потребног за преузимање већине брава. Ово смањује вероватноћу да дође до ситуације подељеног мозга када се надмеће за ресурсе.

Међутим, постоји казна доступности једнака ТТЛ-у мрежних сегмената, тако да ако постоје суседни сегменти, казна може бити неограничена. Ово се дешава кад год клијент стекне браву, а затим пређе на други сегмент пре него што га отпусти.

У принципу, с обзиром на бесконачно суседне сегменте мреже, систем може остати недоступан бесконачан временски период.

Перформансе, прелазак на грешку и фсинц

Многи људи користе Редис јер су им потребне високе перформансе сервера за закључавање у смислу кашњења потребног за преузимање и отпуштање закључавања и броја преузимања/отпуштања који се могу завршити у секунди. Да би се испунио овај захтев, постоји стратегија за комуникацију са Н Редис серверима ради смањења кашњења. Ово је стратегија мултиплексирања (или „мултиплексирање сиромаха“, где се сокет ставља у неблокирајући режим, шаље све команде и чита команде касније, под претпоставком да је време повратног пута између клијента и сваке инстанце слично) .

Међутим, такође морамо узети у обзир разматрање везано за дуготрајно складиштење података ако тежимо да креирамо модел са поузданим опоравком од кварова.

У суштини, да бисмо разјаснили проблем, претпоставимо да смо конфигурисали Редис без дуготрајног складиштења података. Клијент успева да блокира 3 од 5 инстанци. Једна од инстанци коју је клијент успео да блокира се поново покреће и у овом тренутку постоје поново 3 инстанце за исти ресурс, које можемо блокирати, а други клијент може, заузврат, да блокира поново покренуту инстанцу, нарушавајући безбедносно својство које претпоставља искључивост брава.

Ако омогућите податке унапред (АОФ), ситуација ће се мало побољшати. На пример, можете да унапредите сервер тако што ћете послати команду СХУТДОВН и поново га покренути. Пошто су операције истека у Редис-у семантички имплементиране на такав начин да време наставља да тече чак и када је сервер искључен, сви наши захтеви су у реду. Ово је нормално све док је обезбеђено нормално гашење. Шта учинити у случају нестанка струје? Ако је Редис подразумевано конфигурисан, са фсинц синхронизацијом на диску сваке секунде, онда је могуће да после поновног покретања нећемо имати наш кључ. Теоретски, ако желимо да гарантујемо сигурност закључавања током поновног покретања било које инстанце, требало би да омогућимо fsync=always у подешавањима за дуготрајно складиштење података. Ово ће потпуно убити перформансе, све до нивоа ЦП система који се традиционално користе за безбедну имплементацију дистрибуираних брава.

Али ситуација је боља него што се чини на први поглед. У принципу, безбедност алгоритма је очувана јер када се инстанца поново покрене након грешке, она више не учествује ни у једном закључавању које је тренутно активно.

Да бисмо то осигурали, само треба да обезбедимо да након квара инстанца остане недоступна неко време које незнатно прелази максимални ТТЛ који користимо. На овај начин ћемо сачекати до истека рока и аутоматског отпуштања свих кључева који су били активни у тренутку квара.

Коришћењем одложеног поновног покретања, у принципу је могуће постићи сигурност чак и у одсуству дугорочне истрајности у Редис-у. Имајте на уму, међутим, да то може довести до новчане казне за кршење приступачности. На пример, ако већина инстанци не успе, систем ће постати глобално недоступан за ТТЛ (и ниједан ресурс не може бити блокиран за то време).

Повећавамо доступност алгоритма: проширујемо блокирање

Ако се посао који обављају клијенти састоји од малих корака, могуће је смањити подразумевано трајање закључавања и имплементирати механизам за продужење брава. У принципу, ако је клијент заузет рачунаром и вредност истека закључавања је опасно ниска, можете послати Луа скрипту свим инстанцама која проширује ТТЛ кључа ако кључ још увек постоји и његова вредност је и даље насумична вредност добијена када брава је набављена.

Клијент треба да сматра да се закључавање поново преузима само ако је успео да закључа већину инстанци у периоду важења.

Истина, технички се алгоритам не мења, тако да максималан број поновљених покушаја стицања брава мора бити ограничен, иначе ће својства приступачности бити нарушена.

Извор: ввв.хабр.цом