🥇Bllokimet e shpërndara me përdorimin e Redis

Përshëndetje, Habr!

Sot do t'ju paraqesim një përkthim të një artikulli të ndërlikuar mbi zbatimin e bllokimeve të shpërndara përmes Redis dhe do të flasim për perspektivën e Redis si një temë. Analiza e algoritmit Redlock nga Martin Kleppmang, autori i librit "Aplikacione me ngarkesë të lartë", është shpjeguar këtu.

Bllokimet e shpërndara janë një primitiv shumë i dobishëm, i përdorur në shumë ambiente ku procese të ndryshme duhet të punojnë mbi burime të ndara sipas parimit të përjashtimit të ndërsjellë.

Ekzistojnë disa biblioteka dhe postime që përshkruajnë si të zbatohet DLM (menaxheri i bllokimeve të shpërndara) duke përdorur Redis, por çdo bibliotekë përdor një qasje të vetë dhe garancitë që ofrohen janë mjaft të dobëta krahasuar me atë që arrihet përmes një dizajni pak më kompleks.

Në këtë artikull do të përpiqemi të përshkruajmë një algoritëm që mund të quhet kanonik, i cili demonstrohet se si të implementohen bllokimet e shpërndara me anë të Redis. Do të flasim për algoritmin e quajtur Redlock, i cili zbaton një menaxher bllokimesh të shpërndara dhe, sipas mendimit tonë, ky algoritëm është më i sigurt se qasja tradicionale me një instancë të vetme. Shpresojmë që komuniteti të analizojë, të ofrojë ktheerje dhe ta përdorë si një pikënisje për zbatimin e projekteve më të komplikuara ose alternativë.

Zbatime

Para se të kalojmë në përshkrimin e algoritmit, do të paraqesim disa lidhje për zbatime të gatshme. Mund t'i përdorni ato si referencë.

Redlock-rb (zbatohet për Ruby). Po ashtu ekziston fork Redlock-rb, i cili shton një paketë (gem) për lehtësinë e shpërndarjes, dhe jo vetëm për këtë.
Redlock-py (zbatohet për Python).
Aioredlock (zbatohet për Asyncio Python).
Redlock-php (zbatohet për PHP).
PHPRedisMutex (një tjetër zbatim për PHP)
cheprasov/php-redis-lock (bibliotekë PHP për bllokime)
Redsync (zbatohet për Go).
Redisson (zbatohet për Java).
Redis::DistLock (zbatohet për Perl).
Redlock-cpp (zbatohet për C++).
Redlock-cs (zbatohet për C#/.NET).
RedLock.net (zbatohet për C#/.NET). Me mbështetje për zgjerime async dhe lock.
ScarletLock (zbatohet për C# .NET me ndihmën e një depoje të konfiguruar)
Redlock4Net (zbatohet për C# .NET)
node-redlock (zbatohet për NodeJS). Përfshin mbështetje për zgjatjen e bllokimeve.

Garancitë e sigurisë dhe disponueshmërisë

Ne do të modelojmë projektin tonë vetëm me tre karakteristika që, sipas mendimit tonë, ofrojnë garancitë minimale të nevojshme për përdorimin efektiv të bllokimeve të shpërndara.

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

Pse zbatimi i bazuar në rikuperimin nga dështimi nuk është i mjaftueshëm në këtë rast
Për të kuptuar se çfarë do të përmirësojmë, le të analizojmë situatën aktuale të shumicës së biblioteka për bllokime të shpërndara, të bazuara në Redis.

Mënyra më e thjeshtë për të bllokuar një burim duke përdorur Redis është të krijosh një çelës në instancën. Zakonisht çelësi krijohet me një kohë të kufizuar jetese, kjo arrihet përmes mundësisë që Redis ofron për skadon, kështu që ngadalë ose shpejt ky çelës lirohet (karakteristika 2 në listën tonë). Kur klientit i nevojitet të lirojë burimin, ai fshin çelësin.

Në pamje të parë, kjo zgjidhje funksionon mjaft mirë, por ka një problem: në arkitekturën tonë krijohet një pikë e vetme dështimi. Çfarë do ndodhë nëse instanca kryesore e Redis dështon? Le të shtojmë një kopje! Dhe do ta përdorim atë nëse kryesori nuk është i aksesueshëm. Fatkeqësisht, ky variant nuk është i qëndrueshëm. Duke vepruar kështu, ne nuk mund të realizojmë siç duhet karakteristikën e përjashtimit ndërsjellë që na nevojitet për të siguruar sigurinë, për shkak se replikimi në Redis është asinkron.

Është e qartë se në këtë model krijohet një gjendje garuese:

Klienti A merr bllokimin në instancën kryesore.
Kryesori dështon para se të regjistrohet çelësi te kopja.
Kopja ngrihet në kryesor.
Klienti B merr bllokimin për të njëjtin burim, i cili tashmë është bllokuar nga A. SHKELJE E SIGURISË!

Ndonjëherë është plotësisht normale që në rrethana të veçanta, për shembull gjatë një dështimi, shumë klientë të mbajnë bllokimin në mënyrë të njëkohshme. Në këto raste, mund të përdoret një zgjidhje e bazuar në replikim. Në raste të tjera, ne rekomandojmë zgjidhjen e përshkruar në këtë artikull.

Implementimi i saktë me një instancë të vetme

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

Për të fituar 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ë kohëzgjatje prej 30000 milisekondash (opsioni PX). Për çelësin caktohet vlera “myrandomvalue”. Kjo vlerë duhet të jetë unike brenda të gjithë klientëve dhe të gjitha kërkesave për bllokim.
Në parim, një vlerë e rastit përdoret për të liruar në siguri bllokimin, me një skenar që i komunikon Redis: hiqe çelësin, vetëm nëse ai ekziston, dhe vlera e ruajtur në të është pikërisht ajo që pritej. Kjo arrihet me ndihmën e 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

Kjo është e rëndësishme për të parandaluar heqjen e bllokimit që është bërë nga një klient tjetër. Për shembull, një klient mund të fitojë një bllokim, pastaj të bllokohet gjatë një operacioni, që zgjat më shumë se koha e vlefshme e bllokimit të parë (në mënyrë që koha e vlefshme e çelësit të skadojë), dhe më vonë të heqë bllokimin që e vendosi një klient tjetër.
Të përdorësh DEL të thjeshtë nuk është e sigurt, pasi klienti mund të heqë bllokimin e vendosur nga një klient tjetër. Në anën tjetër, duke përdorur skenarin e mëposhtëm, çdo bllokim ‘nënshkruhet’ me një varg të rastësishëm, prandaj mund ta heqë atë vetëm klienti që e vendosi më parë.

Cila duhet të jetë kjo varg e rastësishme? Mendoj se duhet të jetë 20 bajta nga /dev/urandom, por mund të gjejmë mënyra më të lira për të krijuar një varg mjaft unik për qëllimet që keni. Për shembull, do të ishte në rregull të mbjellësh RC4 me /dev/urandom dhe pastaj të gjenerosh një rrjedhë pseudo-rastësore mbi të. Një zgjidhje më e thjeshtë lidhet me kombinimin e kohës unix në mikrosekonda plus ID e klientit; kjo nuk është aq e sigurt, por ndoshta përputhet me nivelin e detyrave në shumicën e konteksteve.

Koha që përdorim si tregues të jetëgjatësisë së çelësit quhet ‘koha e veprimit të bllokimit’. Ky vlerë është njëkohësisht koha, pas së cilës bllokimi do të lirohet automatikisht, dhe koha që ka klienti për të realizuar operacionin para se një klient tjetër të mund të bllokojë këtë burim, pa cenuar në fakt garancitë e ekskluzivitetit. Kjo garanci është e kufizuar vetëm në një dritare të caktuar kohe, që fillon nga momenti i fitimit të bllokimit.

Pra, kemi diskutuar një mënyrë të mirë për të fituar dhe liruar bllokimin. Sistemi (nëse flasim për një sistem të pacaktuar, që përbëhet nga një instancë të vetme dhe gjithmonë të disponueshme) është i sigurt. Le të zgjeron këtë koncept në një sistem të shpërndarë, në të cilin nuk kemi këto garanci.

Algoritmi Redlock

Në versionin e shpërndarë të algoritmit supozohet se kemi N Redis të udhëhequr. Këta nyje janë plotësisht të pavarur nga njëri-tjetri, prandaj ne nuk përdorim replikimin apo ndonjë sistem koordinimi implicit. Ne tashmë kemi përmendur se si të fitojmë dhe të lirojmë bllokimin në një instancë të vetme në mënyrë të sigurt. Ne 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ë vendosim N të jetë 5, një vlerë mëse e arsyeshme. Në këtë mënyrë, na nevojitet të përdorim 5 Redis të udhëhequr në kompjuterë ose makina virtuale të ndryshme, për të siguruar që ata të veprojnë kryesisht pavarur nga njëri-tjetri.

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

Merr kohën aktuale në milisekonda.
Klienti përpiqet vazhdimisht të marrë bllokimin në të gjithë N instancat, duke përdorur në të gjitha rastet të njëjtin emër çelësi dhe vlera të rastit. Në hapin 2, duke vendosur bllokimin për secilën 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 zgjedhja e bllokimit është 10 sekonda, vonesa mund të jetë në диапазонin ~ 5-50 milisekonda. Kështu eliminohet situata në të cilën klienti do të mbetej i bllokuar për një kohë të gjatë duke u përpjekur të arrijë një nod Redis që ka dështuar: nëse instanca nuk është e disponueshme, ne sa më shpejt që të jetë e mundur përpiqemi të lidhim një instancë tjetër.
Për të marrë bllokimin, klienti llogarit se sa kohë ka kaluar; për këtë, ai zbrit nga vlera aktuale e kohës atë markim kohor që u mor në hapat 1. Vetëm atëherë kur klienti është në gjendje të marrë bllokimin në shumicën e instancave (të paktën 3), dhe koha totale që nevojitet për të marrë bllokimin është më e vogël se kohëzgjatja e bllokimit, merr parasysh se bllokimi është marrë.
Nëse bllokimi është marrë, atëherë periudha e tij e vlefshmërisë pranohet si vlera fillestare e kohëzgjatjes së bllokimit minus koha e kaluar e llogaritur në hapin 3.
Nëse klienti për ndonjë arsye nuk arrin të marrë bllokimin (ose nuk mund të bllokojë N/2+1 instanca, ose koha e vlefshmërisë së bllokimit rezulton negative), ai do të provojë të çbllokojë të gjitha instancat (edhe ato që, siç u mendua, ai nuk mundi t'i bllokojë).

A është algoritmi asinkron?

Ky algoritëm bazohet në supozimin se, megjithëse nuk ka orë të sinkronizuara me të cilat funksionojnë të gjitha proceset, koha lokale në çdo proces ende kalon përafërsisht në të njëjtin ritëm, dhe devijimi është i vogël në krahasim me kohën totale, pas së cilës bllokimi hiqet automatikisht. Ky supozim është shumë i ngjashëm me situatën që ndodh në kompjuterët e zakonshëm: në çdo kompjuter ka orë lokale, dhe zakonisht mund të llogarisim se devijimi i kohës në kompjuterë të ndryshëm është i vogël.

Në këtë fazë, ne duhet ta formulojmë më saktë rregullin tonë të përjashtimit të ndërsjellë: përjashtimi i ndërsjellë garanton vetëm nëse klienti që mban bllokimin përfundon punën brenda kohës gjatë së cilës bllokimi është i vlefshëm (kjo vlerë është marrë në hapin 3), minus një kohë shtesë (thjesht disa milisekonda, për të kompensuar devijimin e kohës midis proceseve).

Më shumë rreth sistemeve të tilla që kërkojnë pajtimin e devijimeve të kohës flet artikulli interesant që vjen pas: Leases: një mekanizëm efikas pa dështim për konsistencën e caches të skedarëve të shpërndarë.

Përsëritja në rast dështimi

Kur klientit nuk i arrin të marrë bllokimin, ai duhet të përpiqet ta bëjë atë përsëri, duke ruajtur një vonesë të rastit; kjo bëhet për të asinkronizuar shumë klientë që përpiqen në të njëjtën kohë të marrin bllokimin e të njëjtit burim (çka mund të çojë në një situatë 'truri të ndarë', në të cilën nuk ka fitues). Për më tepër, sa më shpejt të përpiqet klienti të marrë bllokimin e shumicës së instancave Redis, aq më e vogël është dritarja, ku mund të ndodhë 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ë komanda SET në N instanca nëpërmjet shumë përçueshmërisë.

Këtu është e rëndësishme të theksohet se sa e rëndësishme është që klientët që nuk arritën të marrin shumicën e bllokimeve të lironi (pjesërisht) bllokimet e marra, në mënyrë që të mos presin për skadimin e çelësit, para se bllokimi mbi burimin të mund të merret përsëri (pavarësisht se, nëse ndodhin fraktura të rrjetit, dhe klienti humb lidhjen me instancat e Redis, atëherë ka një ndëshkim të disponueshmërisë, derisa të pritet skadimi i çelësit).

Çlirimi i bllokimit

Çlirimi i bllokimit është një operacion i thjeshtë, që kërkon thjesht të çbllokoni të gjitha instancat, pavarësisht se klienti mendon se ai ndoshta ka arritur të bllokojë një instancë specifike.

Konsideratat për sigurinë

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

Fillimisht, le të supozojmë se klienti arriti të fitojë një bllokim mbi shumicën e instancave. Çdo instancë do të ketë një çelës me të njëjtën kohë jetëshkurtë. Megjithatë, çdo njëri nga këta çelësa është vendosur në momentin e tij, kështu që afati i tyre do të skadojë në kohë të ndryshme. Por, nëse çelësi i parë u vendos në një moment të paktën T1 (koha që ne zgjedhim para kontaktit me serverin e parë), dhe çelësi i fundit u vendos në një moment të paktën T2 (koha kur u mor përgjigja nga serveri i fundit), atëherë jemi të sigurt se çelësi i parë në grupin, që do të skadojë, do të jetë aktiv për të paktën MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Çelësat e tjerë do të skadojnë më vonë, prandaj mund të jemi të sigurt se të gjithë çelësat do të jenë të vlefshëm njëkohësisht për të paktën këtë kohë.

Në kohën kur shumica e çelësave mbeten të vlefshëm, një klient tjetër nuk do të mund të fitojë bllokimin, pasi operacionet N/2+1 SET NX nuk mund të përfundojnë me sukses, nëse tashmë ekzistojnë N/2+1 çelësa. Prandaj, nëse bllokimi është fituar, nuk është e mundur ta fitojmë atë përsëri në të njëjtën kohë (kjo do të shkelte pronësinë e përjashtimit të ndërsjellë).
E vërteta është, ne duam të sigurohemi se një grup klientësh që përpiqen të fitojnë bllokimin njëkohësisht nuk do të mund të përfundojnë të gjithë me sukses.

Nëse një klient bllokoi shumicën e instancave, duke kaluar një kohë rreth ose më shumë se koha maksimale e zgjatjes së bllokimit, atëherë do ta konsiderojë bllokimin të pavlefshëm dhe do të shkëputë instancat. Prandaj, na mbetet të marrim parasysh vetëm rastin kur klienti arriti të bllokojë shumicën e instancave brenda një kohe më të shkurtër se afati i vlefshmërisë. Në këtë rast, sa i përket argumentit të mësipërm, brenda kohës MIN_VALIDITY asnjë klient nuk duhet të jetë në gjendje të ripërfitojë bllokimin. Prandaj, një grup klientësh mund të bllokojnë N/2+1 instanca në të njëjtën kohë (e cila përfundohet 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, duke e bërë bllokimin të pavlefshëm.

A mund të ofroni një provë formale të sigurisë, të përmendi algoritmet e ngjashëm që ekzistojnë, apo të gjeni ndonjë defekt në atë që është paraqitur?

Konsiderata për disponueshmërinë

Disponueshmëria e sistemit varet nga tre karakteristika kryesore:

Automatizimi i heqjes së bllokimit (meqë çelësat skadojnë): në fund të fundit, çelësat do të jenë sërish të disponueshëm për t'u përdorur për bllokime.
Fakti që klientët zakonisht ndihmojnë njëri-tjetrin, duke hequr bllokimet kur bllokimi i kërkuar nuk është fituar, ose është fituar dhe puna ka përfunduar; prandaj, është shumë e mundur që të mos na nevojitet të presim skadimin e çelësave për të ripërfituar bllokimin.
Fakti që, kur klienti ka nevojë të përpiqet përsëri të fitojë bllokimin, ai pret për një kohë relativisht më të gjatë se periudha e nevojshme për të fituar shumicën e bllokimeve. Kështu, zvogëlohet probabiliteti i shfaqjes së situatës së ndarjes së mendjes në konkurrencën për burime.

Megjithatë, duhet të paguhet një gjobë për uljen e disponueshmërisë, e barabartë me kohën TTL në segmentet e rrjetit, prandaj, nëse ka segmente të vazhdueshme, kjo gjobë mund të ketë një madhësi të papërcaktuar. Kjo ndodh çdo herë kur klienti fiton bllokimin dhe pastaj preket në një segment tjetër para se të mund ta lirojë.

Në parim, me segmente të pafundme të vazhdueshme në rrjet, sistemi mund të mbetet i padisponueshëm për një periudhë të pafund.

Kryerja, rikuperimi nga dështimi dhe fsync

Shumë përdorin Redis, pasi është e nevojshme të sigurohet një performancë e lartë e serverit të bllokimit, në nivelin e vonesave të nevojshme për të fituar dhe liruar bllokime, si dhe sasisë së operacioneve të tilla të fitimit/lirimit që mund të realizohet për sekondë. Për të përmbushur këtë kërkesë ekziston një strategji komunikimi me N servera Redis, për të ulur vonesën. Kjo është një strategji e shumëfisheve (ose “shumëfishimi i varfër”, ku soketi vihet në modalitet jo bllokues, dërgon të gjitha komandat dhe lexon komandat më vonë, duke supozuar se koha e kthimit midis klientit dhe secilës instancë është e ngjashme).

Megjithatë, duhet të merret parasysh edhe një konsideratë e lidhur me ruajtjen afatgjatë të të dhënave, nëse ne synojmë të krijojmë një model me rikuperim të sigurt nga dështimet.

Në thelb, për të sqaruar problemin, le të supozojmë se po konfigurojmë Redis pa asnjë ruajtje të gjatë të të dhënave. Klienti arrin të bllokojë 3 nga 5 instancat. Një nga instancat, që klienti arriti ta bllokojë, ribluhet, dhe në atë moment krijohen përsëri 3 instanca për të njëjtin burim, të cilin ne mund ta bllokojmë, dhe klienti tjetër mund, për rrjedhojë, të bllokojë instancën e ribluar, duke shkelur pronën e sigurisë që implicon ekskluzivitetin e bllokimeve.

Nëse aktivizohet ruajtja e parashpejtuar të të dhënave (AOF), situata përmirësohet pak. Për shembull, mund të rrisim serverin duke dërguar komandën SHUTDOWN dhe duke e ribluar atë. Duke qenë se operacionet e skadimit në Redis janë realizuar semantikisht në mënyrë që koha të vazhdojë të kalojë edhe kur serveri është i fikur, gjithçka me kërkesat tona është në rregull. Është në rregull deri sa të sigurohet një ndarje standarde. Por çfarë të bëjmë në rast të ndërprerjes së energjisë? Nëse Redis është i konfiguruar siç është ndryshe, me sinkronizimin fsync në disk çdo sekondë, është e mundur që pas ribllimit të mos na ketë mbetur çelësi ynë. Teorikisht, nëse duam të sigurojmë sigurinë e bllokimeve gjatë çdo ribllimi të instancës, duhet të aktivizojmë fsync=always në cilësimet e ruajtjes së gjatë të të dhënave. Kjo do të shkatërrojë plotësisht performancën, deri në nivelin e sistemeve CP, që tradicionalisht përdoren për realizimin e sigurt të bllokimeve të shpërndara.

Por situata është më e mirë se sa duket në shikim të parë. Në thelb, siguria e algoritmit ruhet, pasi kur një instancë ribllohet pas një dështimi, ajo nuk merr pjesë më në asnjë bllokim aktiv aktualisht.

Për të garantuar këtë, ne thjesht duhet të sigurojmë që pas dështimit instanca të mbetet e paarritshme për një periudhë që paksa tejkalon maksimumin e TTL që ne përdorim. Në këtë mënyrë, do të presim që të skadojë koha dhe të lirohen automatikisht të gjitha çelësat që ishin aktivë në momentin e dështimit.

Duke përdorur ribllime të vonuara, në thelb është e mundur të arrihet siguria edhe në mungesë të ndonjë ruajtjeje të gjatë në Redis. Megjithatë, duhet theksuar se kjo mund të rezultojë në një ndëshkim për shkeljen e disponueshmërisë. Për shembull, në rast të dështimit të shumicës së instancave, sistemi do të bëhet globalisht i paarritshëm për një periudhë TTL (dhe asnjë burim nuk do të mund të bllokohet në këtë kohë).

Rritja e disponueshmërisë së algoritmit: zgjasja e bllokimit

Nëse puna e kryer nga klientët përbëhet nga etapa të vogla, është e mundur të shkurtohet koha e vlefshmërisë së bllokimit të caktuar si parazgjedhje dhe të realizohet një mekanizëm për zgjatjen e bllokimeve. Në thelb, nëse klienti është i angazhuar në llogaritje dhe vlera e afatit të bllokimit po bie me rrezik, mund të dërgohet një skript në Lua në të gjitha instancat për të zgjeruar TTL e çelësit, nëse çelësi ende ekziston dhe vlera e tij vazhdon të jetë një rastësor që është siguruar kur është bllokuar.

Klienti duhet ta konsiderojë bllokimin si të ricikluar vetëm në rast se ka arritur të bllokojë shumicën e instancave brenda periudhës së vlefshmërisë.

Në fakt, në aspektin teknik algoritmi nuk ndryshon, prandaj numri maksimal i përpjekjeve për të riakorduar bllokimet duhet të jetë i kufizuar, përndryshe do të shkelin pronat e disponueshmërisë.

Burimi: habr.com

Bllokimet e shpërndara duke përdorur Redis