ProHoster > Blog > administration > Distribueret låsning ved hjælp af Redis

Distribueret låsning ved hjælp af Redis

Hej Habr!

I dag gør vi dig opmærksom på en oversættelse af en kompleks artikel om implementering af distribueret låsning ved hjælp af Redis og inviterer dig til at tale om udsigterne for Redis som et emne. Analyse af den pågældende Redlock-algoritme fra Martin Kleppmann, forfatter til bogen "Applikationer med høj belastning", givet her.

Distribueret låsning er en meget nyttig primitiv, der bruges i mange miljøer, hvor forskellige processer skal arbejde på delte ressourcer på en gensidigt udelukkende måde.

Der er en række biblioteker og indlæg derude, der beskriver, hvordan man implementerer DLM (Distributed Lock Manager) ved hjælp af Redis, men hvert bibliotek har en anden tilgang, og de garantier, de giver, er ret svage i forhold til, hvad der er muligt med lidt mere sofistikeret design.

I denne artikel vil vi forsøge at beskrive en betinget kanonisk algoritme, der demonstrerer, hvordan man implementerer distribueret låsning ved hjælp af Redis. Vi vil tale om en algoritme kaldet Redlock, implementerer den en distribueret låsemanager, og efter vores mening er denne algoritme sikrere end den sædvanlige enkelt-instans tilgang. Vi håber, at fællesskabet vil analysere det, give feedback og bruge det som udgangspunkt for mere komplekse eller alternative projekter.

Implementeringer

Inden vi går videre til beskrivelsen af ​​algoritmen, giver vi flere links til færdige implementeringer. De kan bruges som reference.

Sikkerheds- og tilgængelighedsgarantier

Vi vil modellere vores design med kun tre egenskaber, som vi mener giver de minimumsgarantier, der er nødvendige for effektivt at bruge distribueret låsning.

  1. Sikkerhedsejendom: Gensidig udelukkelse. På ethvert givet tidspunkt kan kun én klient holde låsen.
  2. Tilgængelighed Ejendom A: Ingen dødvande. Det er altid muligt i sidste ende at erhverve en lås, selvom klienten, der låste ressourcen, fejler eller lander på et andet disksegment.
  3. Tilgængelighed Egenskab B: Fejltolerance. Så længe størstedelen af ​​Redis-noder kører, er klienter i stand til at erhverve og frigive låse.

Hvorfor implementering baseret på fejlgendannelse ikke er nok i dette tilfælde
For at forstå, hvad vi skal forbedre, lad os analysere den aktuelle situation med de fleste distribuerede låsebiblioteker baseret på Redis.

Den enkleste måde at låse en ressource på ved hjælp af Redis er at oprette en nøgle i instansen. Typisk oprettes en nøgle med en begrænset levetid, dette opnås ved hjælp af udløbsfunktionen i Redis, så før eller siden frigives denne nøgle (egenskab 2 på vores liste). Når klienten skal frigive ressourcen, sletter den nøglen.

Ved første øjekast fungerer denne løsning ganske godt, men der er et problem: Vores arkitektur skaber et enkelt fejlpunkt. Hvad sker der, hvis værtens Redis-forekomst fejler? Lad os så tilføje en slave! Og vi vil bruge det, hvis oplægsholderen ikke er tilgængelig. Desværre er denne mulighed ikke levedygtig. Ved at gøre dette vil vi ikke være i stand til korrekt at implementere den gensidige udelukkelsesegenskab, som vi har brug for for at sikre sikkerheden, fordi replikering i Redis er asynkron.

I en sådan model opstår naturligvis en racetilstand:

  1. Klient A anskaffer en lås på masteren.
  2. Masteren fejler, før nøgleindtastningen er overført til slaven.
  3. Følgeren forfremmes til leder.
  4. Klient B anskaffer en lås på den samme ressource, som A allerede har låst. SIKKERHEDSKRIDTELSE!

Nogle gange er det helt normalt, at mange klienter under særlige omstændigheder, såsom en fejl, kan holde låsen på samme tid. I sådanne tilfælde kan en replikationsbaseret løsning anvendes. Ellers anbefaler vi løsningen beskrevet i denne artikel.

Korrekt implementering med en enkelt instans

Før vi forsøger at overvinde manglerne ved enkeltinstanskonfigurationen beskrevet ovenfor, lad os forstå, hvordan man korrekt håndterer denne simple sag, da denne løsning faktisk er gyldig i applikationer, hvor en race-tilstand er acceptabel fra tid til anden, og også fordi blokering på en enkelt forekomst tjener som grundlaget, der bruges i den distribuerede algoritme beskrevet her.

For at anskaffe en lås skal du gøre dette:

SET resource_name my_random_value NX PX 30000

Denne kommando installerer kun en nøgle, hvis den ikke allerede eksisterer (NX option), med en gyldighedsperiode på 30000 millisekunder (PX option). Nøglen er sat til "myrandomvalue" Denne værdi skal være unik på tværs af alle klienter og alle låseanmodninger.
Grundlæggende bruges en tilfældig værdi til sikkert at frigive låsen, med et script, der fortæller Redis: Fjern kun nøglen, hvis den findes, og værdien gemt i den er nøjagtigt, hvad der var forventet. Dette opnås ved hjælp af følgende Lua-script:

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

Dette er vigtigt for at forhindre, at en lås, som en anden klient holder, fjernes. For eksempel kan en klient anskaffe sig en lås, derefter blive låst i en operation, der varer længere end den første lås (så nøglen når at udløbe), og senere fjerne den lås, som en anden klient havde placeret.
Det er usikkert at bruge en simpel DEL, fordi en klient kan fjerne en lås, som en anden klient har. I modsætning hertil, når du bruger ovenstående script, er hver lås "signeret" med en tilfældig streng, så kun den klient, der tidligere har placeret den, kan fjerne den.

Hvad skal denne tilfældige streng være? Jeg gætter på, at det burde være 20 bytes fra /dev/urandom, men du kan finde billigere måder at gøre strengen unik nok til dine formål. For eksempel ville det være fint at seede RC4 med /dev/urandom og derefter generere en pseudo-tilfældig strøm fra den. En enklere løsning involverer en kombination af unix-tid i mikrosekundsopløsning plus klient-id'et; det er ikke så sikkert, men det er nok op til opgaven i de fleste sammenhænge.

Den tid vi bruger som et mål for nøglens levetid kaldes "låsens levetid". Denne værdi er både mængden af ​​tid, før låsen automatisk udløses, og mængden af ​​tid, en klient har til at gennemføre en operation, før en anden klient igen kan låse den ressource, uden faktisk at overtræde gensidige udelukkelsesgarantier. Denne garanti er kun begrænset til et bestemt tidsrum, som begynder fra det øjeblik, låsen er købt.

Så vi har diskuteret en god måde at anskaffe og frigive en lås. Systemet (hvis vi taler om et ikke-distribueret system bestående af en enkelt og altid tilgængelig instans) er sikkert. Lad os udvide dette koncept til et distribueret system, hvor vi ikke har sådanne garantier.

Redlock algoritme

Den distribuerede version af algoritmen antager, at vi har N Redis-mastere. Disse noder er fuldstændig uafhængige af hinanden, så vi bruger ikke replikering eller noget andet implicit koordinationssystem. Vi har allerede dækket, hvordan du sikkert erhverver og frigiver en lås på en enkelt instans. Vi tager det for givet, at algoritmen, når man arbejder med en enkelt instans, vil bruge præcis denne metode. I vores eksempler sætter vi N til 5, hvilket er en rimelig værdi. Vi bliver således nødt til at bruge 5 Redis-mastere på forskellige computere eller virtuelle maskiner for at sikre, at de fungerer stort set uafhængigt af hinanden.

For at erhverve en lås udfører klienten følgende handlinger:

  1. Henter den aktuelle tid i millisekunder.
  2. Forsøg sekventielt at opnå en lås på alle N forekomster ved at bruge det samme nøglenavn og tilfældige værdier i alle tilfælde. I trin 2, når klienten sætter en lås op på en per-instans basis, bruger klienten en forsinkelse til at erhverve den, der er kort nok i forhold til den tid, hvorefter låsen automatisk udløses. For eksempel, hvis blokeringsvarigheden er 10 sekunder, kan forsinkelsen være i intervallet ~5-50 millisekunder. Dette eliminerer den situation, hvor klienten kan forblive blokeret i lang tid ved at forsøge at nå en mislykket Redis-knude: hvis instansen ikke er tilgængelig, så forsøger vi at oprette forbindelse til en anden instans så hurtigt som muligt.
  3. For at tage en lås beregner klienten, hvor lang tid der er gået; For at gøre dette trækker den tidsstemplet, der blev opnået i trin 1 fra den faktiske tidsværdi. Hvis og kun hvis klienten var i stand til at opnå låsen på de fleste instanser (mindst 3), og den samlede tid det tog at få låsen, mindre end låsens varighed, anses låsen for at være opnået.
  4. Hvis der er erhvervet en lås, anses låsevarigheden for at være den oprindelige låsevarighed minus den forløbne tid beregnet i trin 3.
  5. Hvis klienten ikke kan få låsen af ​​en eller anden grund (enten var den ikke i stand til at låse N/2+1 forekomster, eller låsevarigheden var negativ), så vil den forsøge at låse alle forekomster op (selv dem, den troede, den ikke kunne blokere ).

Er algoritmen asynkron?

Denne algoritme er baseret på den antagelse, at selvom der ikke er noget synkroniseret ur, som alle processer ville arbejde på, så flyder lokal tid i hver proces stadig med omtrent samme hastighed, og fejlen er lille sammenlignet med den samlede tid, hvorefter låsen er automatisk frigivet. Denne antagelse minder meget om den situation, der er typisk for almindelige computere: hver computer har et lokalt ur, og vi kan normalt regne med, at tidsforskellen mellem forskellige computere er lille.

På dette tidspunkt skal vi formulere vores gensidige udelukkelsesregel mere omhyggeligt: ​​gensidig udelukkelse er kun garanteret, hvis klienten, der holder låsen, går ud i løbet af den tid, låsen er gyldig (denne værdi opnået i trin 3), minus noget mere tid (i alt nogle få millisekunder for at kompensere for tidsforskellen mellem processer).

Den følgende interessante artikel fortæller mere om sådanne systemer, der kræver koordinering af tidsintervaller: Leasing: en effektiv fejltolerant mekanisme til distribueret filcache-konsistens.

Prøv igen ved fejl

Når en klient ikke får en lås, skal den prøve igen efter en tilfældig forsinkelse; dette gøres for at de-synkronisere flere klienter, der forsøger at erhverve en lås på den samme ressource på samme tid (hvilket kan føre til en "split-brain" situation, hvor der ikke er nogen vindere). Derudover, jo hurtigere en klient forsøger at opnå en lås på et flertal af Redis-forekomster, jo snævrere er vinduet, hvor en split-hjerne-situation kan opstå (og jo mindre er behovet for genforsøg). Derfor skal klienten ideelt set forsøge at sende SET-kommandoer til N instanser samtidigt ved hjælp af multipleksing.

Det er værd at understrege her, hvor vigtigt det er for klienter, der undlader at anskaffe de fleste låse, at frigøre de (delvist) erhvervede låse, så de ikke skal vente på, at nøglen udløber, før låsen på ressourcen kan anskaffes igen. (men hvis netværksfragmentering opstår, og klienten mister kontakten med Redis-forekomsterne, så skal du betale en tilgængelighedsbøde, mens du venter på, at nøglen udløber).

Slip låsen

Frigivelse af en lås er en simpel handling, der blot kræver, at alle instanser låses op, uanset om klienten ser ud til at have låst en bestemt instans med succes.

Sikkerhedshensyn

Er algoritmen sikker? Lad os prøve at forestille os, hvad der sker i forskellige scenarier.

Til at begynde med, lad os antage, at klienten var i stand til at få en lås på de fleste tilfælde. Hver instans vil indeholde en nøgle med samme levetid for alle. Men hver af disse nøgler blev installeret på et andet tidspunkt, så de udløber på forskellige tidspunkter. Men hvis den første nøgle blev installeret på et tidspunkt, der ikke var værre end T1 (det tidspunkt, vi vælger, før vi kontakter den første server), og den sidste nøgle blev installeret på et tidspunkt, der ikke var værre end T2 (det tidspunkt, hvor svaret blev modtaget fra den sidste server), så er vi sikre på, at den første nøgle i sættet, der udløber, vil overleve mindst MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Alle andre nøgler udløber senere, så vi kan være sikre på, at alle nøgler vil være gyldige samtidigt i mindst denne tid.

I den tid, hvor de fleste nøgler forbliver gyldige, vil en anden klient ikke være i stand til at erhverve låsen, da N/2+1 SET NX-operationer ikke kan lykkes, hvis N/2+1-nøgler allerede eksisterer. Derfor, når først en lås er erhvervet, er det umuligt at erhverve den igen i samme øjeblik (dette ville krænke den gensidige udelukkelse).
Vi ønsker dog at sikre, at flere klienter, der forsøger at anskaffe en lås på samme tid, ikke kan lykkes på samme tid.

Hvis klienten har låst de fleste instanser i omkring eller mere end den maksimale låsevarighed, vil den betragte låsen som ugyldig og låse instanserne op. Derfor skal vi kun tage højde for det tilfælde, hvor klienten formåede at blokere de fleste tilfælde på en kortere tid end udløbsdatoen. I dette tilfælde, vedrørende ovenstående argument, i løbet af tiden MIN_VALIDITY ingen klient bør være i stand til at erhverve låsen igen. Derfor vil mange klienter kun kunne låse N/2+1-instanser på samme tid (som slutter i slutningen af ​​trin 2), når tiden til at låse flertallet var større end TTL-tiden, hvilket gør låsen ugyldig.

Kan du fremlægge et formelt sikkerhedsbevis, angive eksisterende lignende algoritmer eller finde en fejl i ovenstående?

Overvejelser om tilgængelighed

Systemtilgængelighed afhænger af tre hovedkarakteristika:

  1. Slip automatisk låse (efterhånden som nøgler udløber): Nøgler vil med tiden være tilgængelige igen til brug til låse.
  2. Det faktum, at klienter normalt hjælper hinanden ved at fjerne låse, når den ønskede lås ikke er anskaffet, eller er anskaffet og arbejdet er udført; så det er sandsynligt, at vi ikke skal vente på, at nøglerne udløber for at få låsen igen.
  3. Det faktum, at når en klient skal forsøge at anskaffe en lås igen, venter den i forholdsvis længere tid end den periode, der kræves for at anskaffe de fleste låse. Dette reducerer sandsynligheden for, at en split-hjerne-situation opstår, når der konkurreres om ressourcer.

Der er dog en tilgængelighedsstraf svarende til TTL for netværkssegmenterne, så hvis der er sammenhængende segmenter, kan straffen være ubestemt. Dette sker, når en klient anskaffer en lås og derefter ripper til et andet segment, før den kan frigive den.

I princippet, givet uendelige sammenhængende netværkssegmenter, kan et system forblive utilgængeligt i en uendelig periode.

Ydelse, failover og fsync

Mange mennesker bruger Redis, fordi de har brug for høj låseserverydelse i forhold til den forsinkelse, der kræves for at erhverve og frigive låse, og antallet af opkøb/udgivelser, der kan gennemføres pr. sekund. For at opfylde dette krav er der en strategi for at kommunikere med N Redis-servere for at reducere latens. Dette er en multipleksing-strategi (eller "fattigmands multiplexing", hvor stikket sættes i ikke-blokerende tilstand, sender alle kommandoer og læser kommandoerne senere, forudsat at rundturstiden mellem klienten og hver instans er ens) .

Men vi er også nødt til at tage hensyn til den langsigtede datalagring, hvis vi stræber efter at skabe en model med pålidelig retablering fra fejl.

Grundlæggende, for at afklare problemet, lad os antage, at vi konfigurerer Redis uden nogen langvarig datalagring overhovedet. Klienten formår at blokere 3 ud af 5 tilfælde. Et af de tilfælde, som klienten formåede at blokere, genstartes, og i øjeblikket er der 3 forekomster igen for den samme ressource, som vi kan blokere, og en anden klient kan til gengæld blokere den genstartede forekomst, hvilket krænker sikkerhedsegenskaben, der forudsætter eksklusivitet af låse.

Hvis du aktiverer data ahead (AOF), vil situationen forbedres en smule. For eksempel kan du promovere en server ved at sende SHUTDOWN-kommandoen og genstarte den. Da udløbsoperationer i Redis er semantisk implementeret på en sådan måde, at tiden fortsætter med at flyde, selv når serveren er slukket, er alle vores krav i orden. Dette er normalt, så længe en normal nedlukning er sikret. Hvad skal man gøre i tilfælde af strømafbrydelser? Hvis Redis er konfigureret som standard, med fsync-synkronisering på disk hvert sekund, så er det muligt, at vi efter en genstart ikke har vores nøgle. Teoretisk set, hvis vi ønsker at garantere låsesikkerhed under genstart af en instans, bør vi aktivere fsync=always i indstillingerne for langtidslagring af data. Dette vil fuldstændig dræbe ydeevnen, ned til niveauet for CP-systemer, der traditionelt bruges til at implementere distribuerede låse sikkert.

Men situationen er bedre, end den ser ud ved første øjekast. I princippet er algoritmens sikkerhed bevaret, fordi når instansen genstartes efter en fejl, deltager den ikke længere i nogen lås, der i øjeblikket er aktiv.

For at sikre dette skal vi blot sikre, at instansen efter en fejl forbliver utilgængelig i en periode, der lidt overstiger den maksimale TTL, som vi bruger. På denne måde vil vi vente til udløbsdatoen og automatisk frigivelse af alle nøgler, der var aktive på tidspunktet for fejlen.

Ved at bruge forsinket genstart er det i princippet muligt at opnå sikkerhed, selv i mangel af nogen langvarig vedholdenhed i Redis. Bemærk dog, at dette kan medføre en bøde for krænkelse af tilgængeligheden. For eksempel, hvis de fleste instanser mislykkes, vil systemet blive globalt utilgængeligt for TTL (og ingen ressource kan blokeres i løbet af denne tid).

Vi øger tilgængeligheden af ​​algoritmen: vi udvider blokeringen

Hvis arbejdet udført af klienter består af små trin, er det muligt at reducere standardlåsens varighed og implementere en mekanisme til at forlænge låse. I princippet, hvis klienten har travlt med at computere, og låseudløbsværdien er farlig lav, kan du sende et Lua-script til alle forekomster, der udvider nøglens TTL, hvis nøglen stadig eksisterer, og dens værdi stadig er en tilfældig værdi, der opnås, når lås blev anskaffet.

En klient bør kun overveje, at en lås skal genanskaffes, hvis den har formået at låse de fleste instanser inden for gyldighedsperioden.

Det er sandt, teknisk set ændres algoritmen ikke, så det maksimale antal gentagne forsøg på at erhverve låse skal begrænses, ellers vil tilgængelighedsegenskaberne blive overtrådt.

Kilde: www.habr.com

Tilføj en kommentar