ProHoster > Blog > administratë > Kyçja e shpërndarë duke përdorur Redis

Kyçja e shpërndarë duke përdorur Redis

Hej Habr!

Sot sjellim në vëmendjen tuaj një përkthim të një artikulli kompleks në lidhje me zbatimin e mbylljes së shpërndarë duke përdorur Redis dhe ju ftojmë të flisni për perspektivat e Redis si temë. Analiza e algoritmit Redlock në fjalë nga Martin Kleppmann, autor i librit "Aplikacione me ngarkesë të lartë", dhënë këtu.

Bllokimi i shpërndarë është një primitiv shumë i dobishëm që përdoret në shumë mjedise ku procese të ndryshme duhet të punojnë në burime të përbashkëta në një mënyrë reciproke ekskluzive.

Ka një numër bibliotekash dhe postimesh atje që përshkruajnë se si të zbatohet DLM (Distributed Lock Manager) duke përdorur Redis, por secila bibliotekë ka një qasje të ndryshme dhe garancitë që ato ofrojnë janë mjaft të dobëta në krahasim me atë që mund të arrihet me dizajn pak më të sofistikuar.

Në këtë artikull do të përpiqemi të përshkruajmë një algoritëm kanonik të kushtëzuar që tregon se si të zbatohet mbyllja e shpërndarë duke përdorur Redis. Ne do të flasim për një algoritëm të quajtur Redlock, ai zbaton një menaxher të bllokimit të shpërndarë 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ë komente dhe ta përdorë atë si pikënisje për projekte më komplekse ose alternative.

Zbatimi

Para se të kalojmë në përshkrimin e algoritmit, ne ofrojmë disa lidhje me implementimet e gatshme. Ato mund të përdoren për referencë.

Garancitë e sigurisë dhe disponueshmërisë

Ne do të modelojmë dizajnin tonë me vetëm tre veti që mendojmë se ofrojnë garancitë minimale të nevojshme për të përdorur në mënyrë efektive mbylljen e shpërndarë.

  1. Pasuria e sigurisë: Përjashtimi i ndërsjellë. Në çdo moment, vetëm një klient mund ta mbajë bllokimin.
  2. Disponueshmëria Prona A: Nuk ka bllokime. Është gjithmonë e mundur që përfundimisht të fitohet një bllokim, edhe nëse klienti që bllokoi burimin dështon ose zbret në një segment tjetër të diskut.
  3. Vetia e disponueshmërisë B: Toleranca ndaj gabimeve. Për sa kohë që shumica e nyjeve Redis po funksionojnë, klientët janë në gjendje të marrin dhe lëshojnë bravë.

Pse zbatimi i bazuar në rikuperimin e dështimit nuk është i mjaftueshëm në këtë rast
Për të kuptuar se çfarë do të përmirësojmë, le të analizojmë gjendjen aktuale të punëve me shumicën e bibliotekave mbyllëse të shpërndara bazuar në Redis.

Mënyra më e thjeshtë për të kyçur një burim duke përdorur Redis është krijimi i një çelësi në shembull. Në mënyrë tipike, një çelës krijohet me jetëgjatësi të kufizuar, kjo arrihet duke përdorur funksionin e skadimit të dhënë në Redis, kështu që herët a vonë ky çelës lëshohet (vetia 2 në listën tonë). Kur klienti duhet të lëshojë burimin, ai fshin çelësin.

Në pamje të parë, kjo zgjidhje funksionon mjaft mirë, por ka një problem: arkitektura jonë krijon një pikë të vetme dështimi. Çfarë ndodh nëse shembulli i hostit Redis dështon? Le të shtojmë një skllav atëherë! Dhe ne do ta përdorim nëse prezantuesi nuk është i disponueshëm. Fatkeqësisht, ky opsion nuk është i zbatueshëm. Duke bërë këtë, ne nuk do të jemi në gjendje të zbatojmë siç duhet veçorinë e përjashtimit të ndërsjellë që na nevojitet për të garantuar sigurinë, sepse përsëritja në Redis është asinkron.

Natyrisht, në një model të tillë ndodh një gjendje gare:

  1. Klienti A merr një bravë mbi master.
  2. Masteri dështon përpara se hyrja kryesore të transferohet te skllavi.
  3. Ndjekësi promovohet në lider.
  4. Klienti B merr një bllokim në të njëjtin burim që A e ka mbyllur tashmë. SHKELJE E SIGURISË!

Ndonjëherë është krejtësisht normale që në rrethana të veçanta, të tilla si një dështim, shumë klientë mund të mbajnë bllokimin në të njëjtën kohë. Në raste të tilla, mund të aplikohet një zgjidhje e bazuar në përsëritje. Përndryshe, ne rekomandojmë zgjidhjen e përshkruar në këtë artikull.

Zbatimi i saktë me një shembull të vetëm

Përpara se të përpiqemi të kapërcejmë mangësitë e konfigurimit me një instancë të përshkruar më sipër, le të kuptojmë se si ta trajtojmë siç duhet këtë rast të thjeshtë, pasi kjo zgjidhje është në të vërtetë e vlefshme në aplikacionet ku një kusht gare është i pranueshëm herë pas here, dhe gjithashtu sepse bllokimi në një një shembull i vetëm shërben si bazë që përdoret në algoritmin e shpërndarë të përshkruar këtu.

Për të marrë një bllokues, bëni këtë:

SET resource_name my_random_value NX PX 30000

Kjo komandë instalon një çelës vetëm nëse ai nuk ekziston tashmë (opsioni NX), me një periudhë vlefshmërie prej 30000 milisekonda (opsioni PX). Çelësi është vendosur në "myrandomvalue" Kjo vlerë duhet të jetë unike për të gjithë klientët dhe për të gjitha kërkesat e bllokimit.
Në thelb, një vlerë e rastësishme përdoret për të liruar në mënyrë të sigurt bllokimin, me një skript që i thotë Redis: hiqeni çelësin vetëm nëse ekziston dhe vlera e ruajtur në të është pikërisht ajo që pritej. Kjo arrihet duke përdorur skriptin e mëposhtëm 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 një bllokimi të mbajtur nga një klient tjetër. Për shembull, një klient mund të marrë një bllokim, pastaj të bllokohet në një operacion që zgjat më shumë se kyçi i parë (në mënyrë që çelësi të ketë kohë të skadojë) dhe më vonë të heqë bllokimin që kishte vendosur një klient tjetër.
Përdorimi i një DEL të thjeshtë është i pasigurt sepse një klient mund të heqë një bllokues të mbajtur nga një klient tjetër. Në të kundërt, kur përdorni skriptin e mësipërm, çdo kyç "nënshkruhet" me një varg të rastësishëm, kështu që vetëm klienti që e ka vendosur më parë mund ta heqë atë.

Cili duhet të jetë ky varg i rastësishëm? Unë mendoj se duhet të jetë 20 bajt nga /dev/urandom, por mund të gjeni mënyra më pak të shtrenjta për ta bërë vargun mjaft unik për qëllimet tuaja. Për shembull, do të ishte mirë të vendosni RC4 me /dev/urandom dhe më pas të krijoni një rrjedhë pseudo të rastësishme prej tij. Një zgjidhje më e thjeshtë përfshin një kombinim të kohës unix në rezolucionin mikrosekondë plus ID-në e klientit; nuk është aq i sigurt, por ndoshta është në detyrë në shumicën e konteksteve.

Koha që ne përdorim si masë e jetëgjatësisë së çelësit quhet "jeta e bllokimit". Kjo vlerë është edhe sasia e kohës përpara se bllokimi të lëshohet automatikisht dhe sasia e kohës që një klient duhet të përfundojë një operacion përpara se një klient tjetër të mund ta bllokojë atë burim, pa shkelur në fakt garancitë e përjashtimit të ndërsjellë. Kjo garanci është e kufizuar vetëm në një periudhë të caktuar kohe, e cila fillon nga momenti i blerjes së bllokimit.

Pra, ne kemi diskutuar një mënyrë të mirë për të marrë dhe liruar një bllokues. Sistemi (nëse po flasim për një sistem jo të shpërndarë që përbëhet nga një shembull i vetëm dhe gjithmonë i disponueshëm) është i sigurt. Le ta zgjerojmë këtë koncept në një sistem të shpërndarë, ku nuk kemi garanci të tilla.

Algoritmi Redlock

Versioni i shpërndarë i algoritmit supozon se kemi N mjeshtra Redis. Këto nyje janë plotësisht të pavarura nga njëra-tjetra, kështu që ne nuk përdorim replikimin ose ndonjë sistem tjetër të nënkuptuar të koordinimit. Ne kemi trajtuar tashmë se si të blini dhe lironi në mënyrë të sigurt një bllokues në një shembull të vetëm. Ne e marrim të mirëqenë që algoritmi, kur punon me një shembull të vetëm, do të përdorë pikërisht këtë metodë. Në shembujt tanë kemi vendosur N në 5, që është një vlerë e arsyeshme. Kështu, do të na duhet të përdorim 5 mjeshtra Redis në kompjuterë të ndryshëm ose makina virtuale për t'u siguruar që ato veprojnë kryesisht në mënyrë të pavarur nga njëri-tjetri.

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

  1. Merr kohën aktuale në milisekonda.
  2. Në mënyrë sekuenciale përpiqet të marrë një bllokim në të gjitha N rastet, duke përdorur të njëjtin emër kyç dhe vlera të rastësishme në të gjitha rastet. Në Fazën 2, kur klienti vendos një bllokim në bazë të rastit, klienti përdor një vonesë për ta marrë atë që është mjaft e shkurtër në krahasim me kohën pas së cilës bllokimi lëshohet automatikisht. Për shembull, nëse kohëzgjatja e bllokimit është 10 sekonda, atëherë vonesa mund të jetë në intervalin ~ 5-50 milisekonda. Kjo eliminon situatën në të cilën klienti mund të qëndrojë i bllokuar për një kohë të gjatë duke u përpjekur të arrijë një nyje Redis të dështuar: nëse shembulli nuk është i disponueshëm, atëherë ne përpiqemi të lidhemi me një shembull tjetër sa më shpejt të jetë e mundur.
  3. Për të marrë një bllokim, klienti llogarit sa kohë ka kaluar; Për ta bërë këtë, ai zbret nga vlera aktuale kohore vulën kohore që u mor në hapin 1. Nëse dhe vetëm nëse klienti ishte në gjendje të merrte bllokimin në shumicën e rasteve (të paktën 3) dhe kohën totale që iu desh për të merrni bllokimin, më pak se kohëzgjatja e bllokimit, bllokimi konsiderohet se është marrë.
  4. Nëse është marrë një bllokim, kohëzgjatja e bllokimit merret si kohëzgjatja fillestare e bllokimit minus kohën e kaluar e llogaritur në hapin 3.
  5. Nëse klienti nuk arrin të marrë bllokimin për ndonjë arsye (ose nuk ishte në gjendje të bllokonte shembuj N/2+1, ose kohëzgjatja e bllokimit ishte negative), atëherë ai do të përpiqet të zhbllokojë të gjitha instancat (edhe ato që mendonte se nuk mund t'i bllokonte ).

A është algoritmi asinkron?

Ky algoritëm bazohet në supozimin se, megjithëse nuk ka orë të sinkronizuar në të cilën do të funksiononin të gjitha proceset, ora lokale në secilin proces ende rrjedh afërsisht me të njëjtin ritëm dhe gabimi është i vogël në krahasim me kohën totale pas së cilës bllokohet lëshuar automatikisht. Ky supozim është shumë i ngjashëm me situatën tipike për kompjuterët e zakonshëm: çdo kompjuter ka një orë lokale dhe zakonisht mund të mbështetemi në faktin se diferenca kohore midis kompjuterëve të ndryshëm është e vogël.

Në këtë pikë, ne duhet të formulojmë më me kujdes rregullin tonë të përjashtimit të ndërsjellë: përjashtimi i ndërsjellë garantohet vetëm nëse klienti që mban bllokimin del gjatë kohës që bllokimi është i vlefshëm (kjo vlerë është marrë në hapin 3), minus pak kohë më shumë (gjithsej disa milisekonda për të kompensuar diferencën kohore ndërmjet proceseve).

Artikulli i mëposhtëm interesant tregon më shumë për sisteme të tilla që kërkojnë koordinim të intervaleve kohore: Qiratë: një mekanizëm efikas tolerant ndaj gabimeve për konsistencën e cache të skedarëve të shpërndarë.

Riprovoni dështimin

Kur një klient nuk arrin të marrë një bllokim, ai duhet të provojë përsëri pas një vonese të rastësishme; kjo është bërë për të çsinkronizuar shumë klientë që përpiqen të marrin një bllokim në të njëjtin burim në të njëjtën kohë (gjë që mund të çojë në një situatë "truri të ndarë" në të cilën nuk ka fitues). Për më tepër, sa më shpejt një klient të përpiqet të marrë një bllokim në shumicën e rasteve të Redis, aq më e ngushtë është dritarja në të cilën mund të ndodhë një situatë e ndarjes së trurit (dhe aq më e vogël është nevoja për riprovime). Prandaj, në mënyrë ideale, klienti duhet të përpiqet të dërgojë komanda SET në N instanca në të njëjtën kohë duke përdorur multipleksimin.

Këtu vlen të theksohet se sa e rëndësishme është që klientët të cilët nuk arrijnë të blejnë pjesën më të madhe të bravave të lëshojnë bravat e fituara (pjesërisht), në mënyrë që të mos kenë nevojë të presin që çelësi të skadojë përpara se bllokimi në burim të mund të merret përsëri. (megjithëse nëse ndodh fragmentimi i rrjetit dhe klienti humbet kontaktin me instancat Redis, atëherë duhet të paguani një gjobë për disponueshmërinë ndërsa prisni që çelësi të skadojë).

Lëshojeni bllokimin

Lëshimi i një bllokimi është një operacion i thjeshtë që kërkon thjesht zhbllokimin e të gjitha rasteve, pavarësisht nëse klienti duket se ka bllokuar me sukses një shembull të caktuar.

Konsideratat e Sigurisë

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

Për të filluar, le të supozojmë se klienti ishte në gjendje të merrte një bllokim në shumicën e rasteve. Çdo shembull do të përmbajë një çelës me të njëjtën jetëgjatësi për të gjithë. Megjithatë, secili prej këtyre çelësave është instaluar në një kohë të ndryshme, kështu që ata do të skadojnë në kohë të ndryshme. Por, nëse çelësi i parë është instaluar në një kohë jo më të keqe se T1 (koha që ne zgjedhim përpara se të kontaktojmë serverin e parë), dhe çelësi i fundit është instaluar në një kohë jo më të keqe se T2 (koha në të cilën është marrë përgjigja nga serveri i fundit), atëherë kemi besim se çelësi i parë në grup që skadon do të mbijetojë të paktën MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Të gjithë çelësat e tjerë do të skadojnë më vonë, kështu që mund të jemi të sigurt se të gjithë çelësat do të jenë njëkohësisht të vlefshëm për të paktën këtë herë.

Gjatë kohës që shumica e çelësave mbeten të vlefshëm, një klient tjetër nuk do të jetë në gjendje të marrë bllokimin, pasi operacionet N/2+1 SET NX nuk mund të kenë sukses nëse çelësat N/2+1 ekzistojnë tashmë. Prandaj, pasi të jetë blerë një bravë, është e pamundur ta blini atë përsëri në të njëjtin moment (kjo do të cenonte pronën e përjashtimit të ndërsjellë).
Megjithatë, ne duam të sigurohemi që shumë klientë që përpiqen të blejnë një bllokim në të njëjtën kohë nuk mund të kenë sukses në të njëjtën kohë.

Nëse klienti ka kyçur shumicën e rasteve për rreth ose më shumë se kohëzgjatja maksimale e bllokimit, ai do ta konsiderojë kyçin të pavlefshëm dhe do t'i zhbllokojë instancat. Prandaj, duhet të kemi parasysh vetëm rastin në të cilin klienti ka arritur të bllokojë shumicën e rasteve në një kohë më të vogël se data e skadencës. Në këtë rast, lidhur me argumentin e mësipërm, gjatë kohës MIN_VALIDITY asnjë klient nuk duhet të jetë në gjendje të rimarrë bllokimin. Prandaj, shumë klientë do të jenë në gjendje të kyçin instancat N/2+1 në të njëjtën kohë (e cila përfundon në fund të fazës 2) vetëm kur koha për të kyçur shumicën ishte më e madhe se koha TTL, gjë që e bën bllokimin të pavlefshëm.

A mund të jepni një provë zyrtare sigurie, të tregoni algoritme të ngjashme ekzistuese ose të gjeni një gabim në sa më sipër?

Konsideratat e aksesueshmërisë

Disponueshmëria e sistemit varet nga tre karakteristika kryesore:

  1. Lëshoni automatikisht kyçet (pasi skadojnë çelësat): Çelësat përfundimisht do të jenë sërish të disponueshëm për t'u përdorur për bravë.
  2. Fakti që klientët zakonisht ndihmojnë njëri-tjetrin duke hequr bravat kur bllokimi i dëshiruar nuk është marrë, ose është marrë dhe puna ka përfunduar; kështu që ka të ngjarë që nuk do të duhet të presim që të skadojnë çelësat për të rimarrë bllokimin.
  3. Fakti që kur një klient duhet të provojë përsëri për të blerë një bravë, ai pret për një kohë relativisht më të gjatë se periudha e kërkuar për të blerë shumicën e bravave. Kjo zvogëlon mundësinë e një situate të ndarjes së trurit kur konkurroni për burime.

Megjithatë, ekziston një dënim për disponueshmërinë e barabartë me TTL-në e segmenteve të rrjetit, kështu që nëse ka segmente të lidhura, dënimi mund të jetë i pacaktuar. Kjo ndodh sa herë që një klient merr një bllokim dhe më pas shkëputet në një segment tjetër përpara se të mund ta lëshojë atë.

Në parim, duke pasur parasysh segmentet e pafundme të rrjetit, një sistem mund të mbetet i padisponueshëm për një periudhë të pafundme kohe.

Performanca, dështimi dhe fsync

Shumë njerëz përdorin Redis sepse kanë nevojë për performancë të lartë të serverit me kyçje për sa i përket vonesës së kërkuar për të marrë dhe lëshuar bllokime, si dhe numrin e blerjeve/lëshimeve që mund të kryhen për sekondë. Për të përmbushur këtë kërkesë, ekziston një strategji për të komunikuar me serverët N Redis për të reduktuar vonesën. Kjo është një strategji multipleksimi (ose "multipleksimi i të varfërve", ku priza vendoset në modalitetin jo-bllokues, dërgon të gjitha komandat dhe lexon komandat më vonë, duke supozuar se koha e vajtje-ardhjes midis klientit dhe çdo shembulli është e ngjashme) .

Sidoqoftë, duhet të marrim parasysh gjithashtu konsideratën që lidhet me ruajtjen afatgjatë të të dhënave nëse përpiqemi të krijojmë një model me rikuperim të besueshëm nga dështimet.

Në thelb, për të sqaruar çështjen, le të supozojmë se ne konfigurojmë Redis pa ruajtje afatgjatë të të dhënave. Klienti arrin të bllokojë 3 nga 5 raste. Një nga rastet që klienti arriti të bllokojë riniset dhe në këtë moment ka përsëri 3 raste për të njëjtin burim, të cilat ne mund t'i bllokojmë dhe një klient tjetër mund të bllokojë shembullin e rifilluar, duke shkelur vetinë e sigurisë që supozon ekskluzivitetin e bravave.

Nëse aktivizoni të dhënat përpara (AOF), situata do të përmirësohet pak. Për shembull, mund të promovoni një server duke dërguar komandën SHUTDOWN dhe duke e rifilluar atë. Meqenëse operacionet e skadimit në Redis zbatohen semantikisht në atë mënyrë që koha të vazhdojë të rrjedhë edhe kur serveri është i fikur, të gjitha kërkesat tona janë në rregull. Kjo është normale për sa kohë që sigurohet një mbyllje normale. Çfarë duhet bërë në rast të ndërprerjes së energjisë? Nëse Redis është konfiguruar si parazgjedhje, me sinkronizimin e fsync në disk çdo sekondë, atëherë është e mundur që pas një rifillimi të mos kemi çelësin tonë. Teorikisht, nëse duam të garantojmë sigurinë e bllokimit gjatë çdo rinisjeje, duhet ta aktivizojmë fsync=always në cilësimet për ruajtjen afatgjatë të të dhënave. Kjo do të shkatërrojë plotësisht performancën, deri në nivelin e sistemeve CP që përdoren tradicionalisht për të zbatuar në mënyrë të sigurt bravat e shpërndara.

Por situata është më e mirë se sa duket në shikim të parë. Në parim, siguria e algoritmit ruhet sepse kur shembulli riniset pas një dështimi, ai nuk merr më pjesë në asnjë bllokim që është aktualisht aktiv.

Për ta siguruar këtë, ne vetëm duhet të sigurohemi që pas një dështimi shembulli të mbetet i padisponueshëm për një periudhë kohore që tejkalon pak TTL-në maksimale që përdorim. Në këtë mënyrë do të presim deri në datën e skadencës dhe lëshimin automatik të të gjithë çelësave që ishin aktivë në momentin e dështimit.

Duke përdorur rinisjet e vonuara, në parim është e mundur të arrihet siguria edhe në mungesë të ndonjë qëndrueshmërie afatgjatë në Redis. Vini re, megjithatë, se kjo mund të rezultojë në një gjobë për shkeljen e aksesit. Për shembull, nëse shumica e rasteve dështojnë, sistemi do të bëhet i padisponueshëm globalisht për TTL (dhe asnjë burim nuk mund të bllokohet gjatë kësaj kohe).

Ne rrisim disponueshmërinë e algoritmit: zgjerojmë bllokimin

Nëse puna e kryer nga klientët përbëhet nga hapa të vegjël, është e mundur të zvogëlohet kohëzgjatja e parazgjedhur e bllokimit dhe të zbatohet një mekanizëm për zgjatjen e bravave. Në parim, nëse klienti është i zënë duke llogaritur dhe vlera e skadimit të bllokimit është jashtëzakonisht e ulët, ju mund të dërgoni një skript Lua në të gjitha rastet që zgjeron TTL-në e çelësit nëse çelësi ende ekziston dhe vlera e tij është ende një vlerë e rastësishme e marrë kur u fitua bllokimi.

Një klient duhet të marrë në konsideratë një bllokim për t'u rimarrë vetëm nëse ka arritur të bllokojë shumicën e rasteve brenda periudhës së vlefshmërisë.

Vërtetë, teknikisht algoritmi nuk ndryshon, kështu që numri maksimal i përpjekjeve të përsëritura për të marrë bravë duhet të jetë i kufizuar, përndryshe vetitë e aksesueshmërisë do të shkelen.

Burimi: www.habr.com

Shto një koment