🥇Bllokime të shpërndara me përdorimin e Redis

Përshëndetje, Habr!

Sot tema më poshtë është një përkthim i një artikulli të ndërlikuar mbi implementimin e bllokimeve të shpërndara duke përdorur Redis dhe do të flasim për potencialin e Redis si temë. Analiza e algoritmit të shqyrtuar Redlock nga Martin Kleppmann, autori i librit "Aplikacione me ngarkesë të lartë", i paraqitur këtu.

Bllokimet e shpërndara janë një primitiv shumë i dobishëm, i përdorur në mjedise të shumta ku procese të ndryshme duhet të punojnë mbi burime të përbashkëta në një parim të përjashtimit mutuat.

Ekziston një sërë bibliotekash dhe postimesh që përshkruajnë se si të implementoni DLM (menaxherin e bllokimeve të shpërndara) duke përdorur Redis, por çdo bibliotekë përdor një qasje të vetën dhe garancitë që ofrohen janë relativisht të dobëta krahasuar me ato që mund të arrihen me një projektim pak më të ndërlikuar.

Në këtë artikull ne do të përpiqemi të përshkruajmë një algoritëm ndoshta kanonik, duke demonstruar se si të implementoni bllokimet e shpërndara duke përdorur Redis. Do të flasim për algoritmin e quajtur Redlock, i cili implementon një menaxher bllokimesh të shpërndara dhe, sipas mendimit tonë, ky algoritëm është më i sigurt se qasja e zakonshme me një instancë të vetme. Shpresojmë që komuniteti ta analizojë atë, të japë reagime dhe ta përdorë si një pikë fillimi për realizimin e projekteve më të ndërlikuara ose alternative.

Implementimet

Para se të kalojmë në përshkrimin e algoritmit, le të japim disa lidhje me implementime tashmë të gatshme. Ato mund të shërbejnë si referencë.

Redlock-rb (implementim për Ruby). Ekziston gjithashtu fork Redlock-rb, që shton një paketë (gem) për lehtësimin e shpërndarjes, dhe jo vetëm për këtë.
Redlock-py (implementim për Python).
Aioredlock (implementim për Asyncio Python).
Redlock-php (implementim për PHP).
PHPRedisMutex (një implementim tjetër për PHP)
cheprasov/php-redis-lock (bibliotekë PHP për bllokime)
Redsync (implementim për Go).
Redisson (implementim për Java).
Redis::DistLock (implementim për Perl).
Redlock-cpp (implementim për C++).
Redlock-cs (implementim për C#/.NET).
RedLock.net (implementim për C#/.NET). Me mbështetje për zgjerime asinkrone dhe bllokim.
ScarletLock (implementim për C# .NET me një sistem të amësus që mund të konfigurohet)
Redlock4Net (implementim për C# .NET)
node-redlock (implementim për NodeJS). Përfshin mbështetje për zgjerimin e bllokimeve.

Garancitë e sigurisë dhe disponueshmërisë

Ne do të simulojmë projektin tonë me vetëm tri pronësi, të cilat, sipas mendimit tonë, ofrojnë garancitë minimale të nevojshme për përdorimin efektiv të bllokimeve të shpërndara.

Pronësia e sigurisë: Përjashtim i ndërsjellë. Në çdo moment, vetëm një klient mund të mbajë një bllokim.
Pronësia e disponueshmërisë A: Mungesa e bllokimeve të ndërsjella. Në fund të fundit, gjithmonë mund të merrni një bllokim, edhe nëse klienti që bllokoi burimin dështon ose kalon në një segment tjetër të diskut.
Pronësia e disponueshmërisë B: Qëndrueshmëria ndaj dështimit. Pavarësisht se shumica e nyjeve Redis funksionojnë, klientët janë në gjendje të fitojnë dhe të çlirojnë bllokime.

Pse implementimet që mbështeten në rikuperimin nga dështimi nuk janë të mjaftueshme në këtë rast
Për të kuptuar se çfarë do të përmirësojmë, le të analizojmë situatën aktuale që ekziston me shumicën e biblioteka për bllokime të shpërndara të bazuara në Redis.

Mënyra më e thjeshtë për të bllokuar një burim me anë të Redis është të krijoni një çelës në instancën e tij. Zakonisht, çelësi krijohet me një kohë të kufizuar jetese, e cila arrihet përmes mundësisë 'expires' në Redis, prandaj për një kohë të caktuar ky çelës lirohet (pronësia 2 në listën tonë). Kur klienti ka nevojë të lirojë burimin, ai fshin çelësin.

Në pamje të parë, kjo zgjidhje duket se funksionon mirë, por ka një problem: në arkitekturën tonë, krijohet një pikë e vetme dështimi. Çfarë ndodh nëse instanca kryesore e Redis dështon? Le të shtojmë një skllav! Dhe do ta përdorim atë nëse kryesori nuk është i disponueshëm. Fatkeqësisht, një mundësi e tillë është e papranueshme. Duke bërë kështu, ne nuk do të jemi në gjendje të realizojmë siç duhet pronësinë e përjashtimit të ndërsjellë, që na nevojitet për të siguruar sigurinë, pasi replikimi në Redis është asinkron.

Është evidente se në një model të tillë krijohet një gjendje garuese:

Klienti A fiton një bllokim në kryesoren.
Kryesori dështon para se regjistrimi në çelës të dërgohet te skllavi.
Skllavi ngrihet në kryesor.
Klienti B fiton një bllokim të të njëjtit burim, i cili tashmë është bllokuar nga A. SHKELJE E SIGURISË!

Ndonjëherë është plotësisht e natyrshme që në rrethana të veçanta, siç është dështimi, shumë klientë mund të mbajnë bllokimin në të njëjtën kohë. Në raste të tilla, mund të zbatoni një zgjidhje të bazuar në replikim. Në raste të tjera, rekomandojmë zgjidhjen e përshkruar në këtë artikull.

Zbatimi i duhur me një instancë të vetme

Para se të përpiqemi të kapërcejmë disavantazhet e konfigurimit me një instancë të vetme, le të shqyrtojmë si të veprojmë siç duhet në këtë rast të thjeshtë, pasi një zgjidhje e tillë është në të vërtetë e pranueshme në aplikacione ku gjendja e garës është herë pas here e pranueshme, si dhe sepse bllokimi me një instancë të vetme shërben si baza që përdoret në algoritmin e shpërndarë të përshkruar këtu.

Për të marrë bllokimin, do të veprojmë kështu:

SET resource_name my_random_value NX PX 30000

Ky komandë vendos çelësin, vetëm nëse ai ende nuk ekziston (opsioni NX), me një afat kohor prej 30000 milisekondash (opsioni PX). Për çelësin, vendoset vlera “myrandomvalue”. Kjo vlerë duhet të jetë unike për të gjithë klientët dhe të gjitha kërkesat për bllokim.
Në parim, një vlerë e rastësishme përdoret për të liruar në mënyrë të sigurt bllokimin, përmes një skenari që informon Redis: fshi çelësin, vetëm nëse ai ekziston, dhe vlera e ruajtur në të është pikërisht ajo që pritej. Kjo arrihet përmes skenarit të mëposhtëm në Lua:

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

Është e rëndësishme të mos lejohet lirimi i bllokimit të bërë nga një klient tjetër. Për shembull, një klient mund të marrë bllokimin, pastaj të bllokohet gjatë një operacioni, që zgjat më shumë se afati i parë të bllokimit (në mënyrë që afati i çelësit të skadojë), dhe më vonë të fshijë bllokimin që ka vendosur ndonjë klient tjetër.
Përdorimi i thjeshtë DEL nuk është i sigurt, pasi klienti mund të fshijë bllokimin që është vendosur nga një klient tjetër. Në të kundërt, duke përdorur skenarin e përmendur më sipër, çdo bllokim "nënshkruhet" me një varg rastësor, prandaj vetëm klienti që e ka vendosur atë mund ta fshijë.

Çfarë duhet të jetë ky varg rastësor? Mendoj se duhet të jetë 20 byte nga /dev/urandom, por ka edhe mënyra më të lira për të krijuar një varg mjaft unik për qëllimet që keni para. Për shembull, do të ishte në rregull të mbjellnim RC4 me /dev/urandom dhe pastaj të gjeneronim një rrjedhë pseudo-rastësore mbi të. Një zgjidhje më e thjeshtë është e lidhur me kombinimin e kohës Unix në një rezolutë mikrosekondash plus ID-në e klientit; nuk është aq e sigurt, por ndoshta i përshtatet nivelit të detyrave në shumicën e konteksteve.

Koha që ne e përdorim si tregues të periudhës së jetës së çelësit quhet «koha e skadimit të bllokimit». Ky vlerë është njëherësh afati, pas së cilës bllokimi do të lirohet automatikisht, dhe koha që ka klienti për të kryer operacionin para se një klient tjetër të jetë në gjendje, gjithashtu, të bllokojë këtë burim, pa e shkelur në fakt garancitë e ekskluzivitetit. Kjo garanci është e kufizuar vetëm në një dritare të caktuar kohore, e cila fillon nga momenti i marrjes së bllokimit.

Pra, ne kemi diskutuar një mënyrë të mirë për të marrë dhe liruar bllokimin. Sistemi (nëse flasim për një sistem të pandarë, përbërë nga një instancë të vetme dhe gjithmonë të arritshme) është në siguri. Le të zgjerim këtë koncept në një sistem të shpërndarë, në të cilin ato garanci nuk i kemi.

Algoritmi Redlock

Në versionin e shpërndarë të algoritmit supozojmë se kemi N Redis të kryesorë. Këta node janë krejtësisht të pavarur nga njëri-tjetri, ndaj nuk përdorim replikimin ose ndonjë sistem tjetër implicit koordinimi. Ne tashmë e kemi shpjeguar se si të marrim dhe të lirojmë sigurt bllokimin në një instancë të vetme. E pranojmë si të dhënë se algoritmi kur punon me një instancë të vetme do të përdorë këtë metodë. Në shembujt tanë, ne vendosim N të barabartë me 5, kjo është një vlerë mjaft e arsyeshme. Kështu, do të na nevojitet të përdorim 5 Redis të kryesorë në kompjuterë ose maune virtuale të ndryshme, për të garantuar se ato do të veprojnë kryesisht pavarësisht nga njëra-tjetra.

Për të marrë bllokimin, klienti kryen operacionet e mëposhtme:

Merr kohën aktuale në milisekonda.
Ai mundësi të provoni të merrni një bllokim në të gjitha N instancat, duke përdorur të njëjtin emër çelësi dhe vlera rastësore në të gjitha rastet. Në hapin 2, gjatë vendosjes së bllokimit për çdo instancë, klienti për të marrë atë përdor një vonesë, që është mjaft e shkurtër në krahasim me kohën pas së cilës bllokimi hiqet automatikisht. Për shembull, nëse koha e bllokimit është 10 sekonda, vonesa mund të jetë në intervalin ~ 5-50 milisekonda. Kështu që përjashtohet situata kur klienti mund të mbetet për një kohë të gjatë i bllokuar, duke u përpjekur të arrijë në një nodë Redis që ka dështuar: nëse instanca nuk është e arritshme, atëherë ne përpiqemi sa më shpejt të lidhim me një instancë tjetër.
Për të marrë bllokimin, klienti llogarit se sa kohë ka kaluar; për këtë, ai mbetet nga vlera aktuale e kohës stampën e marrë në hapin 1. Atëherë dhe vetëm atëherë, kur klienti arrin të marrë bllokimin në shumicën e instancave (të paktën 3), dhe koha totale e nevojshme për të marrë bllokimin është më e vogël se koha e veprimit të bllokimit, merret si e arritur marrëveshja e bllokimit.
Nëse është marrë bllokimi, atëherë koha e vlefshmërisë së tij llogaritet si vlera fillestare e kohës së bllokimit minus koha e kaluar, e llogaritur në hapin 3.
Nëse për ndonjë arsye klienti nuk kishte mundësi të merrte bllokimin (ose ai nuk arriti të bllokonte N/2 + 1 instanca, ose koha e veprimit të bllokimit doli negative), ai do të përpiqet të çbllokojë të gjitha instancat (edhe ata që besohej se nuk mund të bllokoheshin).

A është algoritmi asinkron?

Ky algoritëm bazohet në supozimin se, megjithëse nuk ka orë të sinkronizuara me të cilat punojnë të gjitha proceset, koha lokale në çdo proces ende kalon në një ritëm afërsisht të njëjtë, dhe gabimi është i vogël krahasuar me kohën totale, pas së cilës bllokimi hiqet automatikisht. Ky supozim i ngjan shumë situatës që i përket kompjuterëve të zakonshëm: në çdo kompjuter ka orë lokale, dhe zakonisht mund të mendojmë se diferenca në kohë midis kompjuterëve të ndryshëm është e vogël.

Në këtë fazë, duhet të formulojmë më me kujdes rregullin tonë të përjashtimit mutua: përjashtimi i ndërsjellë garantizohet vetëm nëse klienti që mban bllokimin përfundon punën brenda kohës kur bllokimi është aktiv (kjo vlerë është marrë në hapin 3), minus një kohë shtesë (për disa milisekonda, për të kompensuar dallimin e kohës midis proceseve).

Më shumë rreth sistemeve të ngjashme, që kërkojnë akordim të dallimeve të kohës, flet artikulli interesante në vijim: Lejet: një mekanizëm efikas dhe i qëndrueshëm për koherencën e caches së skedarëve të shpërndarë.

Përsëritja në rast dështimi

Kur klienti nuk arrin të marrë bllokimin, ai duhet të përpiqet përsëri, duke pritur një vonesë rastësore; kjo bëhet me qëllim që të asinkronizohen shumë klientë që përpiqen njëkohësisht të blejnë një bllokim të të njëjtit burim (çka mund të çojë në një situatë të 'trurit të ndarë', ku nuk ka fitues). Për më tepër, sa më shpejt të përpiqet klienti të bëjë bllokimin e shumicës së instancave Redis, aq më e ngushtë është dritarja, në të cilën mund të krijohet situata e trurit të ndarë (dhe aq më pak nevojë për përpjekje të përsëritura). Prandaj, në mënyrë ideale, klienti duhet të përpiqet të dërgojë komandat SET në N instance përmes shumëzimit.

Këtu duhet theksuar se sa e rëndësishme është që klientët që nuk arritën të marrin shumicën e bllokimeve, të shpërndajnë (pjesërisht) bllokimet e marra, në mënyrë që të mos duhej të pritej skadimi i çelësit, përpara se bllokimi mbi burimin të mund të marrë përsëri (nëse ndodh fragmentimi i rrjetit dhe klienti humbet lidhjen me instancat Redis, atëherë duhet të paguhet një ndëshkim për shkeljen e disponueshmërisë, derisa të pritet skadimi i çelësit).

Çlirimi i bllokimit

Çlirimi i bllokimit është një operacion i thjeshtë, që kërkon vetëm të çbzllokusni të gjitha instancat, pavarësisht nëse klienti mendon se ka arritur me sukses të bllokojë një instancë të caktuar.

Konsiderata mbi sigurinë

A është algoritmi i sigurt? Le të përpiqemi të paraqesim se çfarë ndodh në skenarë të ndryshëm.

Së pari, le të supozojmë se klienti ka arritur të fitojë bllokimin mbi shumicën e instancave. Çdo instancë do të përmbajë një çelës me një jetëgjatësi të njëjtë për të gjithë. Megjithatë, çdo njëri nga këto çelësa është vendosur në momentin e tij, kështu që afati i skadencës për ta do të skadojë në kohë të ndryshme. Por, nëse çelësi i parë është vendosur në momentin jo më të keq se T1 (koha që ne zgjedhim para kontaktit me serverin e parë), dhe çelësi i fundit është vendosur në momentin jo më të keq se T2 (koha kur është marrë përgjigjja nga serveri i fundit), atëherë ne jemi të sigurt se çelësi i parë në shumë, i cili do të skadojë, do të ekzistojë për të paktën MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Të gjithë çelësat e tjerë do të skadojnë më vonë, prandaj ne mund të jemi të sigurt se të gjithë çelësat do të jenë të vlefshëm në të njëjtën kohë për të paktën këtë kohë.

Gjatë kohës që shumica e çelësave mbeten të vlefshëm, një klient tjetër nuk do të mund të marrë bllokimin, sepse operacionet N/2+1 SET NX nuk mund të krijojnë sukses nëse tashmë ekzistojnë N/2+1 çelësa. Prandaj, nëse bllokimi është fituar, atëherë e rimarrja në të njëjtën kohë është e pamundur (kjo do të shkelte pronësinë e përjashtimit të ndërsjellë).
Është e vërtetë, ne duam të sigurohemi se një grup klientësh, që përpiqen njëkohësisht të fitojnë bllokimin, nuk do të mund të kenë sukses njëkohësisht.

Nëse klienti ka bllokuar shumicën e instancave, duke kaluar për të, koha mbi ose më shumë se maksimalja e kohëzgjatjes së bllokimit, atëherë do të konsiderojë bllokimin si të pavlefshëm dhe do të çbllokojë instancat. Pra, ne duhet të merremi vetëm me rastin kur klienti ka arritur të bllokojë shumicën e instancave brenda një kohe më të shkurtër se afati i vlefshmërisë. Në këtë rast, për sa i përket argumentit të mësipërm, brenda kohës MIN_VALIDITY asnjë klient nuk duhet të jetë në gjendje të marrë përsëri bllokimin. Pra, një grup klientësh do të jenë në gjendje të bllokojnë N/2+1 instanca në të njëjtën kohë (e cila përfundon në momentin e përfundimit të fazës 2), vetëm kur koha për bllokimin e shumicës ishte më e madhe se koha TTL, e cila e bën bllokimin të pavlefshëm.

A do të jeni në gjendje të ofroni një provë formale të sigurisë, të cili tregon algoritme të ngjashme ekzistuese, ose të gjeni një gabim në të përshkruar?

Konsideratat mbi disponueshmërinë

Disponueshmëria e sistemit varet nga tri karakteristika kryesore:

Heqja automatike e bllokadës (pasi periudha e vlefshmërisë së çelësave skadon): në fund, çelësat do të jenë përsëri të disponueshëm për t'u përdorur për bllokadat.
Fakti që klientët zakonisht ndihmojnë njëri-tjetrin duke hequr bllokadat, kur bllokada e nevojshme nuk është blerë, ose është blerë, dhe puna është përfunduar; prandaj është krejtësisht e mundshme që ne mos të presim skadimin e çelësave për të blerë përsëri një bllokadë.
Fakti është se, kur klienti nevojitet të provojë përsëri për të marrë një bllokadë, ai prit më gjatë se periudha e nevojshme për të blerë shumicën e bllokadave. Kështu, mundësia e krijimit të një situate të mendjes së ndarë gjatë konkurencës për burimet zvogëlohet.

Megjithatë, është e nevojshme të paguani një ndëshkim për uljen e disponueshmërisë, të barabartë me kohën TTL në segmentet e rrjetit, prandaj, nëse ka segmente të vazhdueshme, ky ndëshkim mund të marrë një madhësi të pasigurt. Kjo ndodh sa herë që një klient blen një bllokadë dhe pastaj ndalon në një segment tjetër para se të arrijë ta lirojë atë.

Në thelb, me segmente të pafundme të vazhdueshme rrjeti, sistemi mund të mbetet i padisponueshëm për një periudhë të pafundme kohe.

Performanca, rikuperimi pas dështimit dhe fsync

Shumë përdorin Redis, pasi nevojitet të sigurohet një performancë e lartë e serverit të bllokadave, në nivelin e vonesave të nevojshme për të blerë dhe liruar bllokadat, si dhe sasisë së operacioneve të tillë blerjeje/lirimi që arrijnë të realizohen në sekondë. Për të përmbushur këtë kërkesë, ekziston një strategji komunikimi me N serverë Redis, për të reduktuar vonesën. Kjo është një strategji shumëfishimi (ose "multiplakimi i varfërit", ku soketi vendoset në modalitet jo bllokues, dërgon të gjitha komandat, dhe lexon komandat më vonë, duke supozuar që koha e kthimit midis klientit dhe secilit nga instancat është e ngjashme).

E vërteta është se duhet marrë parasysh gjithashtu një aspekt që lidhet me ruajtjen afatgjatë të të dhënave, nëse po përpiqemi të krijojmë një model me rikuperim të sigurta pas dështimeve.

Në parim, për të sqaruar problemin, le të supozojmë se po konfigurojmë Redis pa asnjë ruajtje afatgjatë të të dhënave. Klienti arrin të bllokojë 3 nga 5 instancat. Një nga instancat që klienti arriti ta bllokojë riçelhet, dhe në atë moment përsëri shfaqen 3 instanca për të njëjtin burim që mund ta bllokojmë, dhe një klient tjetër mund, nga ana e tij, të bllokojë instancën e riçelur, duke shpërfillur pronën e sigurisë që parashikon ekskluzivitetin e bllokimeve.

Nëse aktivizojmë ruajtjen e parakohshme të të dhënave (AOF), situata përmirësohet pak. Për shembull, mund të përmirësojmë serverin duke dërguar urdhërin SHUTDOWN dhe riçeljen e tij. Të gjitha operacionet janë të realizuara në mënyrë semantike në Redis në mënyrë që koha vazhdon të kalojë gjithashtu kur serveri është i fikur, ndaj çdo kërkesë është në rregull. Në rregull deri sa të sigurohet një shkëputje standarde. Çfarë të bëjmë në rast të ndodhjeve të energjisë? Nëse Redis është konfiguruar me parametrat standardë, me sinkronizim fsync në disk çdo sekondë, mund të ndodhë që pas riçeljes të humbasim çelësin tonë. Teorikisht, nëse duam të garantojmë sigurinë e bllokimeve gjatë çdo riçelje të instancës, duhet të aktivizojmë fsync=always në parametrat e ruajtjes afatgjatë të të dhënave. Kjo do të shkatërrojë krejtësisht performancën, deri në nivelet e sistemeve CP që përdoren tradicionalisht për implementimin e sigurt të bllokimeve të shpërndara.

Por situata është më e mirë se si duket në shikimin e parë. Në parim, siguria e algoritmit ruhet, pasi kur instanca riçelhet pas një dështimi, ajo nuk merr pjesë më në asnjë bllokim që është aktiv në atë moment.

Për të garantuar këtë, është e nevojshme thjesht të sigurojmë që pas një dështimi instanca të mbetet e paaksesueshme për një periudhë që tejkalon maksimumin TTL që përdorim. Në atë mënyrë ne do të presim skadimin dhe çlirimin automatik të të gjitha çelëve që ishin aktivë në momentin e dështimit.

Duke përdorimi i rindërprerjeve të vonuara, parimisht është e mundur të arrihet siguria dhe në mungesë të ruajtjes afatgjatë në Redis. Megjithatë, duhet të theksojmë se kjo mund të çojë në ndëshkime për shkeljen e disponueshmërisë. Për shembull, në rastin e dështimit të shumicës së instancave, sistemi do të bëhet globalisht i paqasshëm për një periudhë TTL (dhe asnjë burim nuk do të mund të bllokohet gjatë kësaj kohe).

Rritim i disponueshmërisë së algoritmit: zgjatja e bllokimit

Nëse puna që klientët realizojnë përbëhet nga hapa të vegjël, është e mundur të shkurtohet koha e veprimit të bllokimit të vendosur nga e drejta dhe të zbatohet një mekanizëm për zgjatjen e bllokimeve. Parimisht, nëse klienti është i angazhuar në llogaritje, dhe vlera e afatit të veprimit të bllokimit zvogëlohet rrezikshëm, mund të dërgohet një skenar në Lua në të gjitha instancat, që zgjat TTL e çelësit, nëse çelësi ende ekziston dhe vlera e tij vazhdon të jetë e rastësishme, e marrë kur u sigurua bllokimi.

Klienti duhet ta konsiderojë bllokimin si të risiguruar vetëm në rastin kur arriti të bllokojë shumicën e instancave brenda periudhës së veprimit.

Megjithatë, teknikisht algoritmi nuk ndryshon, prandaj numri maksimal i përpjekjeve për të risiguruar bllokimet duhet të jetë i kufizuar, përndryshe do të shqetësohen pronat e disponueshmërisë.

Burimi: habr.com