ProHoster > Blog > Uprava > Porazdeljeno zaklepanje z uporabo Redisa

Porazdeljeno zaklepanje z uporabo Redisa

Pozdravljeni, Habr!

Danes vam predstavljamo prevod zapletenega članka o implementaciji porazdeljenega zaklepanja z uporabo Redisa in vas vabimo, da spregovorite o možnostih Redisa kot teme. Analiza zadevnega algoritma Redlock Martina Kleppmanna, avtorja knjige "Aplikacije z visoko obremenitvijo", dano tukaj.

Porazdeljeno zaklepanje je zelo uporaben primitiv, ki se uporablja v mnogih okoljih, kjer morajo različni procesi delovati na skupnih virih na medsebojno izključujoč način.

Obstajajo številne knjižnice in objave, ki opisujejo, kako implementirati DLM (Distributed Lock Manager) z uporabo Redisa, vendar ima vsaka knjižnica drugačen pristop in jamstva, ki jih ponujajo, so precej šibka v primerjavi s tem, kar je mogoče doseči z nekoliko bolj prefinjeno zasnovo.

V tem članku bomo poskušali opisati pogojni kanonični algoritem, ki prikazuje, kako implementirati porazdeljeno zaklepanje z uporabo Redisa. Govorili bomo o algoritmu, imenovanem redlock, izvaja upravljalnik porazdeljenega zaklepanja in po našem mnenju je ta algoritem varnejši od običajnega pristopa z eno instanco. Upamo, da ga bo skupnost analizirala, zagotovila povratne informacije in ga uporabila kot izhodišče za bolj zapletene ali alternativne projekte.

Izvajanje

Preden preidemo na opis algoritma, nudimo več povezav do že pripravljenih izvedb. Uporabljajo se lahko za referenco.

Garancije za varnost in razpoložljivost

Našo zasnovo bomo modelirali s samo tremi lastnostmi, za katere menimo, da zagotavljajo minimalna jamstva, potrebna za učinkovito uporabo porazdeljenega zaklepanja.

  1. Varnostna lastnost: Medsebojna izključitev. V danem trenutku lahko samo ena stranka drži ključavnico.
  2. Lastnost razpoložljivosti A: Brez zastojev. Vedno je mogoče na koncu pridobiti zaklepanje, tudi če odjemalec, ki je zaklenil vir, odpove ali pristane na drugem segmentu diska.
  3. Lastnost razpoložljivosti B: Toleranca napak. Dokler večina vozlišč Redis deluje, lahko odjemalci pridobijo in sprostijo zapore.

Zakaj implementacija, ki temelji na obnovitvi napake, v tem primeru ni dovolj
Da bi razumeli, kaj bomo izboljšali, analizirajmo trenutno stanje z večino porazdeljenih knjižnic za zaklepanje, ki temeljijo na Redisu.

Najenostavnejši način za zaklepanje vira z uporabo Redisa je ustvarjanje ključa v primerku. Običajno je ključ ustvarjen z omejeno življenjsko dobo, to se doseže s funkcijo poteka, ki je na voljo v Redisu, zato se ta ključ prej ali slej sprosti (lastnost 2 na našem seznamu). Ko mora odjemalec sprostiti vir, izbriše ključ.

Na prvi pogled ta rešitev deluje precej dobro, vendar obstaja težava: naša arhitektura ustvarja eno samo točko odpovedi. Kaj se zgodi, če gostiteljski primerek Redis odpove? Dodajmo torej sužnja! Uporabili ga bomo, če voditelj ne bo dosegljiv. Na žalost ta možnost ni izvedljiva. S tem ne bomo mogli pravilno implementirati lastnosti vzajemne izključitve, ki jo potrebujemo za zagotavljanje varnosti, ker je podvajanje v Redisu asinhrono.

Očitno se v takem modelu pojavi stanje dirke:

  1. Odjemalec A pridobi zaklepanje nadrejenega.
  2. Glavni odpove, preden se vnos ključa prenese na podrejeno.
  3. Sledilec je napredovan v vodjo.
  4. Odjemalec B pridobi zaklepanje istega vira, ki ga je A že zaklenil. KRŠITEV VARNOSTI!

Včasih je povsem normalno, da lahko v posebnih okoliščinah, kot je okvara, več strank zadrži ključavnico hkrati. V takih primerih je mogoče uporabiti rešitev, ki temelji na podvajanju. V nasprotnem primeru priporočamo rešitev, opisano v tem članku.

Pravilna izvedba z enim samim primerkom

Preden poskušamo premagati pomanjkljivosti zgoraj opisane konfiguracije z enim primerkom, poglejmo, kako pravilno ravnati s tem preprostim primerom, saj je ta rešitev dejansko veljavna v aplikacijah, kjer je stanje tekmovanja občasno sprejemljivo, in tudi zato, ker blokiranje na posamezen primerek služi kot osnova, ki se uporablja v tukaj opisanem porazdeljenem algoritmu.

Če želite pridobiti ključavnico, naredite to:

SET resource_name my_random_value NX PX 30000

Ta ukaz namesti ključ le, če še ne obstaja (možnost NX), z obdobjem veljavnosti 30000 milisekund (možnost PX). Ključ je nastavljen na "myrandomvalue" Ta vrednost mora biti edinstvena za vse odjemalce in vse zahteve za zaklepanje.
V bistvu se za varno sprostitev ključavnice uporablja naključna vrednost, s skriptom, ki Redisu pove: odstranite ključ samo, če obstaja in je vrednost, shranjena v njem, natanko pričakovana. To se doseže z naslednjim skriptom Lua:

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

To je pomembno, da preprečite odstranitev ključavnice, ki jo ima drug odjemalec. Odjemalec lahko na primer pridobi ključavnico, nato postane zaklenjen v neki operaciji, ki traja dlje kot prvo zaklepanje (tako da ima ključ čas, da poteče), in pozneje odstrani ključavnico, ki jo je namestil drug odjemalec.
Uporaba preprostega DELa ni varna, ker lahko odjemalec odstrani zaklepanje, ki ga ima drug odjemalec. Nasprotno pa je pri uporabi zgornjega skripta vsaka ključavnica "podpisana" z naključnim nizom, tako da jo lahko odstrani samo odjemalec, ki jo je predhodno postavil.

Kakšen naj bo ta naključni niz? Predvidevam, da bi moral biti 20 bajtov iz /dev/urandom, vendar lahko najdete cenejše načine, da naredite niz dovolj edinstven za svoje namene. Na primer, v redu bi bilo, če bi RC4 zasegli z /dev/urandom in nato iz njega ustvarili psevdonaključni tok. Enostavnejša rešitev vključuje kombinacijo časa Unix v mikrosekundni ločljivosti in ID-ja odjemalca; ni tako varen, vendar je verjetno kos nalogi v večini kontekstov.

Čas, ki ga uporabljamo kot merilo življenjske dobe ključa, se imenuje "življenjska doba ključavnice". Ta vrednost je čas, preden se zaklepanje samodejno sprosti, in čas, ki ga mora odjemalec dokončati, preden lahko drug odjemalec zaklene ta vir, ne da bi dejansko kršil jamstva za medsebojno izključitev. Ta garancija je omejena le na določeno časovno obdobje, ki začne teči od trenutka nakupa ključavnice.

Tako smo razpravljali o dobrem načinu pridobitve in sprostitve ključavnice. Sistem (če govorimo o nedistribuiranem sistemu, sestavljenem iz ene in vedno razpoložljive instance) je varen. Razširimo ta koncept na porazdeljen sistem, kjer nimamo takih garancij.

Redlock algoritem

Porazdeljena različica algoritma predpostavlja, da imamo N Redis mojstrov. Ta vozlišča so popolnoma neodvisna druga od druge, zato ne uporabljamo replikacije ali katerega koli drugega implicitnega koordinacijskega sistema. Pokrili smo že, kako varno pridobiti in sprostiti zaklepanje na enem primeru. Za samoumevno se nam zdi, da bo algoritem pri delu z eno samo instanco uporabil točno to metodo. V naših primerih smo N nastavili na 5, kar je razumna vrednost. Tako bomo morali uporabiti 5 mojstrov Redis na različnih računalnikih ali virtualnih strojih, da zagotovimo, da delujejo v veliki meri neodvisno drug od drugega.

Za pridobitev ključavnice odjemalec izvede naslednje operacije:

  1. Pridobi trenutni čas v milisekundah.
  2. Zaporedoma poskuša pridobiti zaklepanje na vseh N primerkih z uporabo istega imena ključa in naključnih vrednosti v vseh primerih. Na 2. stopnji, ko odjemalec nastavi zaklepanje za vsak primerek, odjemalec za pridobitev uporabi zakasnitev, ki je dovolj kratka v primerjavi s časom, po katerem se zaklepanje samodejno sprosti. Na primer, če je trajanje blokade 10 sekund, je lahko zakasnitev v območju ~5–50 milisekund. To odpravlja situacijo, v kateri bi lahko odjemalec dolgo časa ostal blokiran, ko poskuša doseči neuspelo vozlišče Redis: če primerek ni na voljo, se poskušamo čim prej povezati z drugim primerkom.
  3. Za zaklepanje stranka izračuna, koliko časa je preteklo; Da bi to naredil, od dejanske časovne vrednosti odšteje časovni žig, ki je bil pridobljen v 1. koraku. Če in samo če je odjemalec uspel pridobiti zaklepanje večine primerkov (vsaj 3) in skupni čas, potreben za pridobi zaklepanje, manj kot je trajanje zaklepanja, se šteje, da je zaklepanje pridobljeno.
  4. Če je bilo zaklepanje pridobljeno, je trajanje zaklepanja enako izvirnemu trajanju zaklepanja minus pretečeni čas, izračunan v 3. koraku.
  5. Če odjemalec iz nekega razloga ne pridobi zaklepanja (bodisi ni mogel zakleniti N/2+1 primerkov ali pa je bilo trajanje zaklepanja negativno), bo poskusil odkleniti vse primerke (tudi tiste, za katere je mislil, da jih ne more blokirati ).

Ali je algoritem asinhron?

Ta algoritem temelji na predpostavki, da čeprav ni sinhronizirane ure, po kateri bi delovali vsi procesi, lokalni čas v vsakem procesu še vedno teče s približno enako hitrostjo in je napaka majhna v primerjavi s skupnim časom, po katerem je zaklepanje samodejno sproščeno. Ta predpostavka je zelo podobna situaciji, značilni za običajne računalnike: vsak računalnik ima lokalno uro in običajno lahko računamo na dejstvo, da je časovna razlika med različnimi računalniki majhna.

Na tej točki moramo natančneje oblikovati naše pravilo medsebojne izključitve: medsebojna izključitev je zagotovljena samo, če stranka, ki drži ključavnico, izstopi v času, ko je ključavnica veljavna (ta vrednost, pridobljena v 3. koraku), minus še nekaj časa (skupaj nekaj milisekund za kompenzacijo časovne razlike med procesi).

Več o sistemih, ki zahtevajo usklajevanje časovnih intervalov, pove naslednji zanimiv članek: Zakupi: učinkovit mehanizem, odporen na napake, za konsistentnost porazdeljenega predpomnilnika datotek.

Ob neuspehu poskusi znova

Ko odjemalec ne pridobi zaklepanja, mora poskusiti znova po naključnem zamiku; to se naredi za desinhronizacijo več odjemalcev, ki poskušajo pridobiti zaklepanje istega vira hkrati (kar lahko privede do situacije "razcepljenih možganov", v kateri ni zmagovalcev). Poleg tega, hitreje ko odjemalec poskuša pridobiti zaklepanje večine primerkov Redisa, ožje je okno, v katerem lahko pride do situacije z razdeljenimi možgani (in manjša je potreba po ponovnih poskusih). Zato bi moral odjemalec v idealnem primeru poskusiti poslati ukaze SET na N primerkov hkrati z uporabo multipleksiranja.

Tu je vredno poudariti, kako pomembno je za stranke, ki ne uspejo pridobiti večine zaklepanj, da sprostijo (delno) pridobljena zaklepanja, tako da jim ni treba čakati, da ključ poteče, preden je mogoče znova pridobiti zaklepanje vira. (čeprav pride do razdrobljenosti omrežja in odjemalec izgubi stik z instancami Redis, potem morate plačati kazen za razpoložljivost, medtem ko čakate, da ključ poteče).

Sprostite ključavnico

Sprostitev zaklepanja je preprosta operacija, ki preprosto zahteva odklepanje vseh primerkov, ne glede na to, ali se zdi, da je odjemalec uspešno zaklenil določen primerek.

Varnostni vidiki

Ali je algoritem varen? Poskusimo si predstavljati, kaj se zgodi v različnih scenarijih.

Za začetek predpostavimo, da je odjemalec lahko pridobil zaklepanje večine primerkov. Vsak primerek bo vseboval ključ z enako življenjsko dobo za vse. Vendar je bil vsak od teh ključev nameščen ob drugem času, zato bodo potekli ob različnih časih. Vendar, če je bil prvi ključ nameščen v času, ki ni slabši od T1 (čas, ki ga izberemo pred vzpostavitvijo stika s prvim strežnikom), in zadnji ključ nameščen v času, ki ni slabši od T2 (čas, ko je bil prejet odgovor z zadnjega strežnika), potem smo prepričani, da bo prvi ključ v nizu, ki poteče, preživel vsaj MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Vsi ostali ključi bodo potekli kasneje, zato smo lahko prepričani, da bodo vsi ključi istočasno veljavni vsaj ta čas.

V času, ko večina ključev ostane veljavnih, drug odjemalec ne bo mogel pridobiti ključavnice, ker N/2+1 SET NX operacij ne more uspeti, če N/2+1 ključev že obstaja. Torej, ko je zaklepanje enkrat pridobljeno, ga ni mogoče ponovno pridobiti v istem trenutku (to bi kršilo lastnost medsebojne izključitve).
Vendar želimo zagotoviti, da več odjemalcev, ki poskušajo pridobiti ključavnico hkrati, ne more uspeti hkrati.

Če je odjemalec zaklenil večino primerkov za približno ali več kot je največje trajanje zaklepanja, bo zaklepanje obravnaval kot neveljavno in odklenil primerke. Zato moramo upoštevati le primer, ko je stranki uspelo blokirati večino instanc v času, krajšem od datuma poteka. V tem primeru glede zgornjo trditev med časom MIN_VALIDITY nobena stranka ne bi smela znova pridobiti zaklepanja. Zato bo veliko odjemalcev lahko zaklenilo N/2+1 primerkov v istem času (ki se konča na koncu 2. stopnje) le, če je bil čas za zaklepanje večine večji od časa TTL, zaradi česar je zaklepanje neveljavno.

Ali lahko predložite formalni dokaz o varnosti, navedete obstoječe podobne algoritme ali najdete napako v zgornjem?

Premisleki glede dostopnosti

Razpoložljivost sistema je odvisna od treh glavnih značilnosti:

  1. Samodejno sprosti ključavnice (ko ključi potečejo): ključi bodo sčasoma spet na voljo za uporabo za ključavnice.
  2. Dejstvo, da si stranke običajno pomagajo z odstranjevanjem ključavnic, ko želena ključavnica ni pridobljena ali pa je pridobljena in je delo opravljeno; zato je verjetno, da nam ne bo treba čakati, da ključi potečejo, da ponovno pridobimo ključavnico.
  3. Dejstvo, da ko mora odjemalec znova poskusiti pridobiti zaklepanje, čaka sorazmerno dlje od obdobja, potrebnega za pridobitev večine zaklepanj. To zmanjša verjetnost, da bi med tekmovanjem za vire prišlo do situacije z razdeljenimi možgani.

Vendar obstaja kazen glede razpoložljivosti, ki je enaka TTL segmentov omrežja, tako da je lahko kazen, če obstajajo sosednji segmenti, neomejena. To se zgodi vsakič, ko odjemalec pridobi ključavnico in nato odtrga drug segment, preden jo lahko sprosti.

Načeloma lahko sistem zaradi neskončnih sosednjih segmentov omrežja ostane nedosegljiv neskončno dolgo obdobje.

Zmogljivost, samodejni preklop in fsync

Veliko ljudi uporablja Redis, ker potrebujejo visoko zmogljivost strežnika za zaklepanje v smislu zakasnitve, potrebne za pridobitev in sprostitev zaklepanja, ter števila pridobitev/sprostitev, ki jih je mogoče izvesti na sekundo. Da bi izpolnili to zahtevo, obstaja strategija za komunikacijo s strežniki N Redis za zmanjšanje zakasnitve. To je strategija multipleksiranja (ali "multipleksiranje revežev", kjer je vtičnica prestavljena v način brez blokiranja, pošlje vse ukaze in prebere ukaze pozneje, ob predpostavki, da je čas povratnega potovanja med odjemalcem in vsakim primerkom podoben) .

Vendar pa moramo upoštevati tudi premislek, povezan z dolgoročnim shranjevanjem podatkov, če želimo ustvariti model z zanesljivim okrevanjem po okvarah.

V bistvu, da razjasnimo težavo, predpostavimo, da konfiguriramo Redis brez dolgoročnega shranjevanja podatkov. Stranki uspe blokirati 3 od 5 primerkov. Eden od primerkov, ki jih je odjemalec uspel blokirati, se znova zažene in v tem trenutku so spet 3 primerki za isti vir, ki jih lahko blokiramo, drug odjemalec pa lahko blokira znova zagnani primerek in s tem krši varnostno lastnost, ki predvideva ekskluzivnost ključavnic.

Če omogočite podatke vnaprej (AOF), se bo stanje nekoliko izboljšalo. Na primer, lahko promovirate strežnik tako, da pošljete ukaz SHUTDOWN in ga znova zaženete. Ker so operacije poteka v Redisu semantično implementirane na tak način, da čas še naprej teče, tudi ko je strežnik izklopljen, so vse naše zahteve v redu. To je normalno, dokler je zagotovljen normalen izklop. Kaj storiti v primeru izpada elektrike? Če je Redis privzeto konfiguriran tako, da se fsync sinhronizira na disku vsako sekundo, potem je možno, da po ponovnem zagonu ne bomo imeli svojega ključa. Teoretično bi morali omogočiti, če želimo zagotoviti varnost zaklepanja med ponovnim zagonom primerka fsync=always v nastavitvah za dolgoročno shranjevanje podatkov. To bo popolnoma uničilo zmogljivost, vse do ravni sistemov CP, ki se tradicionalno uporabljajo za varno implementacijo porazdeljenih ključavnic.

A stanje je boljše, kot se zdi na prvi pogled. Načeloma je varnost algoritma ohranjena, ker ob ponovnem zagonu primerka po napaki ne sodeluje več pri nobenem trenutno aktivnem zaklepanju.

Da bi to zagotovili, moramo le zagotoviti, da po napaki primerek ostane nedosegljiv za obdobje, ki nekoliko presega najvišji TTL, ki ga uporabljamo. Tako bomo počakali do datuma poteka in samodejne sprostitve vseh ključev, ki so bili aktivni v času okvare.

Z uporabo odloženih ponovnih zagonov je načeloma mogoče doseči varnost tudi v odsotnosti kakršnega koli dolgotrajnega vztrajanja v Redisu. Upoštevajte pa, da lahko to povzroči globo za kršitev dostopnosti. Na primer, če večina primerkov ne uspe, bo sistem postal globalno nedosegljiv za TTL (in v tem času ni mogoče blokirati nobenega vira).

Povečamo razpoložljivost algoritma: razširimo blokado

Če je delo, ki ga izvajajo stranke, sestavljeno iz majhnih korakov, je mogoče zmanjšati privzeto trajanje zaklepanja in implementirati mehanizem za podaljšanje zaklepanja. Načeloma, če je odjemalec zaposlen z računalništvom in je vrednost poteka zaklepanja nevarno nizka, lahko vsem primerkom pošljete skript Lua, ki razširi TTL ključa, če ključ še vedno obstaja in je njegova vrednost še vedno naključna vrednost, pridobljena, ko ključavnica je bila pridobljena.

Odjemalec naj ponovno pridobi zaklepanje le, če mu je uspelo zakleniti večino primerkov v obdobju veljavnosti.

Res je, tehnično se algoritem ne spremeni, zato mora biti največje število ponovljenih poskusov pridobitve ključavnic omejeno, sicer bodo kršene lastnosti dostopnosti.

Vir: www.habr.com

Dodaj komentar