ProHoster > Log > administrasjon > Distribuert låsing ved hjelp av Redis

Distribuert låsing ved hjelp av Redis

Hei Habr!

I dag bringer vi til deg en oversettelse av en kompleks artikkel om implementering av distribuert låsing ved hjelp av Redis og inviterer deg til å snakke om utsiktene til Redis som et emne. Analyse av den aktuelle Redlock-algoritmen fra Martin Kleppmann, forfatter av boken "Høybelastningsapplikasjoner", gitt her.

Distribuert låsing er en svært nyttig primitiv som brukes i mange miljøer der ulike prosesser må arbeide på delte ressurser på en gjensidig utelukkende måte.

Det finnes en rekke biblioteker og innlegg der ute som beskriver hvordan man implementerer DLM (Distributed Lock Manager) ved hjelp av Redis, men hvert bibliotek har en annen tilnærming og garantiene de gir er ganske svake sammenlignet med hva som er oppnåelig med litt mer sofistikert design.

I denne artikkelen vil vi prøve å beskrive en betinget kanonisk algoritme som demonstrerer hvordan man implementerer distribuert låsing ved hjelp av Redis. Vi skal snakke om en algoritme kalt redlock, implementerer den en distribuert låsemanager, og etter vår mening er denne algoritmen sikrere enn den vanlige tilnærmingen med én forekomst. Vi håper fellesskapet vil analysere det, gi tilbakemeldinger og bruke det som utgangspunkt for mer komplekse eller alternative prosjekter.

Gjennomføring

Før vi går videre til beskrivelsen av algoritmen, gir vi flere lenker til ferdige implementeringer. De kan brukes som referanse.

Sikkerhet og tilgjengelighetsgarantier

Vi skal modellere designet vårt med bare tre egenskaper som vi tror gir minimumsgarantiene som trengs for effektivt å bruke distribuert låsing.

  1. Sikkerhetseiendom: Gjensidig utelukkelse. Til enhver tid kan kun én klient holde låsen.
  2. Tilgjengelighet Eiendom A: Ingen vranglås. Det er alltid mulig å til slutt skaffe en lås, selv om klienten som låste ressursen mislykkes eller lander på et annet disksegment.
  3. Tilgjengelighet Egenskap B: Feiltoleranse. Så lenge de fleste Redis-nodene kjører, er klienter i stand til å skaffe og frigjøre låser.

Hvorfor implementering basert på feilgjenoppretting er ikke nok i dette tilfellet
For å forstå hva vi skal forbedre, la oss analysere den nåværende situasjonen med de fleste distribuerte låsebiblioteker basert på Redis.

Den enkleste måten å låse en ressurs ved å bruke Redis er å lage en nøkkel i instansen. Vanligvis opprettes en nøkkel med begrenset levetid, dette oppnås ved å bruke utløpsfunksjonen i Redis, så før eller siden frigis denne nøkkelen (egenskap 2 i listen vår). Når klienten trenger å frigjøre ressursen, sletter den nøkkelen.

Ved første øyekast fungerer denne løsningen ganske bra, men det er et problem: arkitekturen vår skaper et enkelt feilpunkt. Hva skjer hvis vertens Redis-forekomst mislykkes? La oss legge til en slave da! Og vi vil bruke den hvis presentatøren er utilgjengelig. Dessverre er dette alternativet ikke levedyktig. Ved å gjøre dette vil vi ikke være i stand til å implementere den gjensidige eksklusjonsegenskapen som vi trenger for å sikre sikkerhet på riktig måte, fordi replikering i Redis er asynkron.

Åpenbart, i en slik modell oppstår en rasetilstand:

  1. Klient A skaffer seg en lås på masteren.
  2. Masteren mislykkes før nøkkelinntastingen overføres til slaven.
  3. Følgeren forfremmes til leder.
  4. Klient B anskaffer en lås på den samme ressursen som A allerede har låst. SIKKERHETSBRUDD!

Noen ganger er det helt normalt at under spesielle omstendigheter, som for eksempel feil, kan mange klienter holde låsen samtidig. I slike tilfeller kan en replikeringsbasert løsning brukes. Ellers anbefaler vi løsningen beskrevet i denne artikkelen.

Riktig implementering med en enkelt instans

Før vi forsøker å overvinne manglene ved enkeltforekomstkonfigurasjonen beskrevet ovenfor, la oss forstå hvordan vi skal håndtere dette enkle tilfellet på riktig måte, siden denne løsningen faktisk er gyldig i applikasjoner der en rasetilstand er akseptabel fra tid til annen, og også fordi blokkering på en enkelt forekomst fungerer som grunnlaget som brukes i den distribuerte algoritmen beskrevet her.

For å skaffe en lås, gjør dette:

SET resource_name my_random_value NX PX 30000

Denne kommandoen installerer en nøkkel bare hvis den ikke allerede eksisterer (NX-alternativ), med en gyldighetsperiode på 30000 XNUMX millisekunder (PX-alternativ). Nøkkelen er satt til "myrandomvalue" Denne verdien må være unik for alle klienter og alle låseforespørsler.
I utgangspunktet brukes en tilfeldig verdi for å frigjøre låsen på en sikker måte, med et skript som forteller Redis: fjern nøkkelen bare hvis den finnes og verdien som er lagret i den er nøyaktig det som var forventet. Dette oppnås ved å bruke følgende Lua-skript:

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

Dette er viktig for å forhindre at en lås som holdes av en annen klient fjernes. For eksempel kan en klient anskaffe en lås, for så å bli låst i en operasjon som varer lenger enn den første låsen (slik at nøkkelen har tid til å utløpe), og senere fjerne låsen som en annen klient hadde plassert.
Å bruke en enkel DEL er usikker fordi en klient kan fjerne en lås som holdes av en annen klient. I motsetning til dette, når du bruker skriptet ovenfor, er hver lås "signert" med en tilfeldig streng, slik at bare klienten som tidligere har plassert den kan fjerne den.

Hva skal denne tilfeldige strengen være? Jeg tipper det bør være 20 byte fra /dev/urandom, men du kan finne rimeligere måter å gjøre strengen unik nok for dine formål. For eksempel ville det være greit å seed RC4 med /dev/urandom og deretter generere en pseudo-tilfeldig strøm fra den. En enklere løsning innebærer en kombinasjon av unix-tid i mikrosekunders oppløsning pluss klient-ID; det er ikke like sikkert, men det er nok opp til oppgaven i de fleste sammenhenger.

Tiden vi bruker som et mål på nøkkelens levetid kalles "låslevetiden". Denne verdien er både hvor lang tid før låsen frigjøres automatisk og hvor lang tid en klient har på å fullføre en operasjon før en annen klient igjen kan låse den ressursen, uten å faktisk bryte gjensidige eksklusjonsgarantier. Denne garantien er bare begrenset til et visst tidsvindu, som begynner fra det øyeblikket låsen er kjøpt.

Så vi har diskutert en god måte å anskaffe og frigjøre en lås. Systemet (hvis vi snakker om et ikke-distribuert system som består av en enkelt og alltid tilgjengelig instans) er sikkert. La oss utvide dette konseptet til et distribuert system, hvor vi ikke har slike garantier.

Redlock-algoritme

Den distribuerte versjonen av algoritmen forutsetter at vi har N Redis-mastere. Disse nodene er helt uavhengige av hverandre, så vi bruker ikke replikering eller noe annet implisitt koordineringssystem. Vi har allerede dekket hvordan du sikkert anskaffer og frigjør en lås på en enkelt forekomst. Vi tar det for gitt at algoritmen, når du arbeider med en enkelt instans, vil bruke akkurat denne metoden. I våre eksempler setter vi N til 5, som er en rimelig verdi. Dermed må vi bruke 5 Redis-mastere på forskjellige datamaskiner eller virtuelle maskiner for å sikre at de fungerer stort sett uavhengig av hverandre.

For å skaffe en lås, utfører klienten følgende operasjoner:

  1. Henter gjeldende tid i millisekunder.
  2. Forsøker sekvensielt å få en lås på alle N forekomster, ved å bruke samme nøkkelnavn og tilfeldige verdier i alle tilfeller. I trinn 2, når klienten setter opp en lås på en per-instans basis, bruker klienten en forsinkelse for å skaffe den som er kort nok sammenlignet med tiden etter at låsen automatisk frigjøres. Hvis for eksempel blokkeringsvarigheten er 10 sekunder, kan forsinkelsen være i området ~5-50 millisekunder. Dette eliminerer situasjonen der klienten kan forbli blokkert i lang tid ved å prøve å nå en mislykket Redis-node: hvis forekomsten er utilgjengelig, prøver vi å koble til en annen forekomst så snart som mulig.
  3. For å ta en lås, beregner klienten hvor lang tid som har gått; For å gjøre dette trekker den fra den faktiske tidsverdien tidsstemplet som ble oppnådd i trinn 1. Hvis og bare hvis klienten var i stand til å få låsen på de fleste instanser (minst 3), og den totale tiden det tok å skaffe låsen, mindre enn låsens varighet, anses låsen å være oppnådd.
  4. Hvis en lås er anskaffet, regnes låsevarigheten til å være den opprinnelige låsevarigheten minus den forløpte tiden beregnet i trinn 3.
  5. Hvis klienten ikke klarer å få tak i låsen av en eller annen grunn (enten var den ikke i stand til å låse N/2+1-forekomster, eller låsevarigheten var negativ), vil den forsøke å låse opp alle forekomster (selv de den trodde den ikke kunne blokkere) ).

Er algoritmen asynkron?

Denne algoritmen er basert på antakelsen om at selv om det ikke er noen synkronisert klokke som alle prosesser vil fungere på, flyter lokal tid i hver prosess fortsatt i omtrent samme tempo, og feilen er liten sammenlignet med den totale tiden etter at låsen er automatisk utløst. Denne antakelsen er veldig lik situasjonen som er typisk for vanlige datamaskiner: hver datamaskin har en lokal klokke, og vi kan vanligvis regne med at tidsforskjellen mellom forskjellige datamaskiner er liten.

På dette tidspunktet må vi formulere vår gjensidige eksklusjonsregel mer nøye: gjensidig utestenging er garantert bare hvis klienten som holder låsen går ut i løpet av tiden låsen er gyldig (denne verdien oppnådd i trinn 3), minus noe mer tid (totalt noen få millisekunder for å kompensere for tidsforskjellen mellom prosesser).

Den følgende interessante artikkelen forteller mer om slike systemer som krever koordinering av tidsintervaller: Leieavtaler: en effektiv feiltolerant mekanisme for distribuert filbufferkonsistens.

Prøv igjen ved feil

Når en klient ikke klarer å skaffe en lås, må den prøve igjen etter en tilfeldig forsinkelse; dette gjøres for å de-synkronisere flere klienter som prøver å skaffe en lås på samme ressurs samtidig (noe som kan føre til en "split-brain"-situasjon der det ikke er noen vinnere). I tillegg, jo raskere en klient prøver å få en lås på et flertall av Redis-forekomster, desto smalere er vinduet der en splitt-hjerne-situasjon kan oppstå (og jo mindre er behovet for gjenforsøk). Derfor, ideelt sett, bør klienten prøve å sende SET-kommandoer til N instanser samtidig ved hjelp av multipleksing.

Det er verdt å understreke her hvor viktig det er for klienter som ikke klarer å anskaffe de fleste låser å frigjøre de (delvis) anskaffede låsene, slik at de slipper å vente på at nøkkelen utløper før låsen på ressursen kan anskaffes igjen (men hvis nettverksfragmentering oppstår og klienten mister kontakten med Redis-forekomstene, må du betale en tilgjengelighetsstraff mens du venter på at nøkkelen skal utløpe).

Slipp låsen

Å frigjøre en lås er en enkel operasjon som ganske enkelt krever å låse opp alle forekomster, uavhengig av om klienten ser ut til å ha låst en bestemt forekomst.

Sikkerhetshensyn

Er algoritmen trygg? La oss prøve å forestille oss hva som skjer i forskjellige scenarier.

Til å begynne med, la oss anta at klienten var i stand til å få en lås på de fleste tilfeller. Hver forekomst vil inneholde en nøkkel med samme levetid for alle. Hver av disse nøklene ble imidlertid installert på et annet tidspunkt, så de vil utløpe til forskjellige tider. Men hvis den første nøkkelen ble installert på et tidspunkt som ikke var dårligere enn T1 (tiden vi velger før vi kontakter den første serveren), og den siste nøkkelen ble installert på et tidspunkt som ikke var dårligere enn T2 (tidspunktet da svaret ble mottatt fra den siste serveren), så er vi sikre på at den første nøkkelen i settet som utløper vil overleve minst MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Alle andre nøkler vil utløpe senere, så vi kan være sikre på at alle nøkler vil være gyldige samtidig i minst denne tiden.

I løpet av tiden som de fleste nøkler forblir gyldige, vil ikke en annen klient kunne skaffe seg låsen, siden N/2+1 SET NX-operasjoner ikke kan lykkes hvis N/2+1-nøkler allerede eksisterer. Derfor, når en lås har blitt anskaffet, er det umulig å anskaffe den igjen i samme øyeblikk (dette vil krenke den gjensidige eksklusjonsegenskapen).
Vi vil imidlertid sørge for at flere klienter som prøver å skaffe seg en lås samtidig, ikke kan lykkes samtidig.

Hvis klienten har låst de fleste forekomstene i omtrent eller mer enn maksimal låsetid, vil den vurdere låsen som ugyldig og låse opp forekomstene. Derfor trenger vi kun å ta hensyn til tilfellet der klienten klarte å blokkere de fleste tilfellene på kortere tid enn utløpsdatoen. I dette tilfellet, angående argumentet ovenfor, i løpet av tiden MIN_VALIDITY ingen klient skal kunne få tilbake låsen. Derfor vil mange klienter kunne låse N/2+1-forekomster på samme tid (som slutter ved slutten av trinn 2) bare når tiden for å låse majoriteten var større enn TTL-tiden, noe som gjør låsen ugyldig.

Kan du gi et formelt bevis på sikkerhet, indikere eksisterende lignende algoritmer, eller finne en feil i ovenstående?

Tilgjengelighetshensyn

Systemtilgjengelighet avhenger av tre hovedegenskaper:

  1. Slipp låser automatisk (ettersom nøkler utløper): Nøkler vil etter hvert være tilgjengelige igjen for å brukes til låser.
  2. Det faktum at klienter vanligvis hjelper hverandre ved å fjerne låser når ønsket lås ikke er anskaffet, eller er anskaffet og jobben er fullført; så det er sannsynlig at vi ikke trenger å vente på at nøklene utløper for å få tilbake låsen.
  3. Det faktum at når en klient må prøve på nytt for å anskaffe en lås, venter den i relativt lengre tid enn perioden som kreves for å anskaffe de fleste låser. Dette reduserer sannsynligheten for at en splittet hjernesituasjon oppstår når man konkurrerer om ressurser.

Imidlertid er det en tilgjengelighetsstraff lik TTL for nettverkssegmentene, så hvis det er sammenhengende segmenter, kan straffen være ubestemt. Dette skjer når en klient anskaffer en lås og deretter river av til et annet segment før den kan frigjøre den.

I prinsippet, gitt uendelige sammenhengende nettverkssegmenter, kan et system forbli utilgjengelig i en uendelig periode.

Ytelse, failover og fsync

Mange bruker Redis fordi de trenger høy låseserverytelse når det gjelder ventetiden som kreves for å skaffe og frigjøre låser, og antall anskaffelser/utgivelser som kan fullføres per sekund. For å møte dette kravet er det en strategi for å kommunisere med N Redis-servere for å redusere ventetiden. Dette er en multiplekseringsstrategi (eller "fattigmannsmultipleksing", der kontakten settes i ikke-blokkerende modus, sender alle kommandoer og leser kommandoene senere, forutsatt at rundturstiden mellom klienten og hver instans er lik) .

Vi må imidlertid også ta hensynet knyttet til langsiktig datalagring hvis vi streber etter å lage en modell med pålitelig gjenoppretting fra feil.

I utgangspunktet, for å avklare problemet, la oss anta at vi konfigurerer Redis uten langsiktig datalagring i det hele tatt. Klienten klarer å blokkere 3 av 5 instanser. En av forekomstene som klienten klarte å blokkere, startes på nytt, og i dette øyeblikk er det 3 forekomster igjen for den samme ressursen, som vi kan blokkere, og en annen klient kan på sin side blokkere den omstartede forekomsten, og bryter med sikkerhetsegenskapen som forutsetter eksklusivitet av låser.

Hvis du aktiverer data fremover (AOF), vil situasjonen bedre seg litt. Du kan for eksempel promotere en server ved å sende SHUTDOWN-kommandoen og starte den på nytt. Siden utløpsoperasjoner i Redis er semantisk implementert på en slik måte at tiden fortsetter å flyte selv når serveren er slått av, er alle våre krav i orden. Dette er normalt så lenge en normal avstengning er sikret. Hva skal man gjøre ved strømbrudd? Hvis Redis er konfigurert som standard, med fsync-synkronisering på disk hvert sekund, så er det mulig at vi etter en omstart ikke vil ha nøkkelen vår. Teoretisk sett, hvis vi ønsker å garantere låsesikkerhet under omstart av en forekomst, bør vi aktivere fsync=always i innstillingene for langtidslagring av data. Dette vil fullstendig drepe ytelsen, ned til nivået til CP-systemer som tradisjonelt brukes til å implementere distribuerte låser på en sikker måte.

Men situasjonen er bedre enn den ser ut ved første øyekast. I prinsippet er sikkerheten til algoritmen bevart fordi når forekomsten startes på nytt etter en feil, deltar den ikke lenger i noen lås som for øyeblikket er aktiv.

For å sikre dette trenger vi bare å sørge for at forekomsten etter en feil forblir utilgjengelig i en periode som overskrider den maksimale TTL som vi bruker. På denne måten vil vi vente til utløpsdatoen og automatisk utgivelse av alle nøkler som var aktive på feiltidspunktet.

Ved å bruke forsinket omstart er det i prinsippet mulig å oppnå sikkerhet selv i fravær av langvarig utholdenhet i Redis. Vær imidlertid oppmerksom på at dette kan gi bot for brudd på tilgjengeligheten. For eksempel, hvis flertallet av forekomster mislykkes, vil systemet bli globalt utilgjengelig for TTL (og ingen ressurs kan blokkeres i løpet av denne tiden).

Vi øker tilgjengeligheten til algoritmen: vi utvider blokkeringen

Hvis arbeidet utført av klienter består av små trinn, er det mulig å redusere standard låsevarighet og implementere en mekanisme for å forlenge låser. I prinsippet, hvis klienten er opptatt med databehandling og låseutløpsverdien er farlig lav, kan du sende et Lua-skript til alle forekomster som utvider TTL-en til nøkkelen hvis nøkkelen fortsatt eksisterer og verdien fortsatt er en tilfeldig verdi oppnådd når lås ble anskaffet.

En klient bør kun vurdere en lås som gjenanskaffet dersom den har klart å låse de fleste instanser innenfor gyldighetsperioden.

Riktignok endres ikke algoritmen teknisk, så det maksimale antallet gjentatte forsøk på å skaffe låser må begrenses, ellers vil tilgjengelighetsegenskapene bli krenket.

Kilde: www.habr.com

Legg til en kommentar