Fordelte låsninger ved hjælp af Redis

Hello, Habr!

I dag præsenterer vi en oversættelse af en kompleks artikel om implementeringen af fordelte låsninger med Redis og vil diskutere Redis' potentiale som emne. Analysen af den betragtede Redlock-algoritme af Martin Kleppmann, forfatteren af bogen "Højtydende applikationer", er givet her.

Fordelte låsninger er en meget nyttig primitive, der anvendes i mange miljøer, hvor forskellige processer skal arbejde med delte ressourcer baseret på principperne for gensidig eksklusion.

Der findes en række biblioteker og indlæg, der beskriver, hvordan man implementerer en DLM (fordelt låsemanager) ved hjælp af Redis, men hver biblioteksmetode har sin egen tilgang, og de garantier, der gives, er ganske svage i forhold til, hvad der kan opnås med et lidt mere komplekst design.

I denne artikel vil vi forsøge at beskrive en betinget kanonisk algoritme, der viser, hvordan man implementerer fordelte låsninger ved hjælp af Redis. Vi vil tale om algoritmen kaldet Redlock, som implementerer en fordelt låsemanager, og efter vores mening er denne algoritme mere sikker end den almindelige tilgang med en enkelt instans. Vi håber, at samfundet vil analysere den, give feedback og bruge den som et udgangspunkt for implementering af mere komplekse eller alternative projekter.

Implementeringer

Før vi går videre til beskrivelsen af algoritmen, vil vi give nogle links til allerede færdige implementeringer. De kan bruges til reference.

• Redlock-rb (implementering for Ruby). Der findes også en fork Redlock-rb, der tilføjer en pakke (gem) for nem distribution, og ikke kun til dette.
• Redlock-py (implementering for Python).
• Aioredlock (implementering for Asyncio Python).
• Redlock-php (implementering for PHP).
• PHPRedisMutex (endnu en implementering for PHP)
• cheprasov/php-redis-lock (PHP-bibliotek til låsninger)
• Redsync (implementering for Go).
• Redisson (implementering for Java).
• Redis::DistLock (implementering for Perl).
• Redlock-cpp (implementering for C++).
• Redlock-cs (implementering for C#/.NET).
• RedLock.net (implementering for C#/.NET). Med støtte til async og lock udvidelser.
• ScarletLock (implementering for C# .NET med konfigurerbar datalagring)
• Redlock4Net (implementering for C# .NET)
• node-redlock (implementering for NodeJS). Inkluderer støtte til forlængelse af låsninger.

Sikkerheds- og tilgængelighedsgarantier

Vi planlægger at modellere vores projekt med kun tre egenskaber, som vi mener giver de minimumsgarantier, der er nødvendige for effektiv brug af distribuerede låse.

1. Sikkerhedsegenskab: Mutuelt eksklusion. På ethvert tidspunkt kan kun én klient holde låsen.
2. Tilgængelighedsegenskab A: Ingen døde låse. I sidste ende kan man altid få låsen, selv hvis klienten, der har låst ressourcen, fejler eller går ind i et andet disksegment.
3. Tilgængelighedsegenskab B: Fejltolerance. Så længe flertallet af Redis noder fungerer, kan klienterne erhverve og frigive låse.

Hvorfor en implementering baseret på genopretning efter fejl ikke er tilstrækkelig i dette tilfælde
For at forstå, hvad vi skal forbedre, lad os analysere den nuværende tilstand, der eksisterer med de fleste biblioteker til distribuerede låse baseret på Redis.

Den nemmeste måde at låse en ressource ved hjælp af Redis er at oprette en nøgle i instansen. Normalt oprettes nøglen med en begrænset levetid, hvilket opnås ved hjælp af Redis' indbyggede expires-funktion, så denne nøgle vil før eller senere blive frigivet (egenskab 2 på vores liste). Når klienten skal frigive ressourcen, sletter den nøglen.

Ved første øjekast fungerer denne løsning fint, men der er et problem: der opstår et enkelt punkt for fejl i vores arkitektur. Hvad sker der, hvis den primære Redis instans fejler? Lad os så tilføje en sekundær! Og vi vil bruge den, hvis den primære ikke er tilgængelig. Desværre er denne mulighed ikke levedygtig. Ved at gøre det kan vi ikke korrekt implementere den nødvendige egenskab ved mutuel eksklusion for at sikre sikkerheden, da replikationen i Redis er asynkron.

Det er tydeligt, at der i en sådan model opstår en kapløbsstilstand:

1. Klient A erhverver låsen på den primære.
2. Den primære fejler, før adgang til nøglen er overført til den sekundære.
3. Den sekundære opgraderes til primær.
4. Klient B erhverver låsen på den samme ressource, som allerede er låst af A. SIKKERHEDSVIOLATION!

Det er nogle gange helt i orden, at i særlige omstændigheder, som f.eks. ved et nedbrud, kan mange kunder samtidig holde en lås. I sådanne tilfælde kan en løsning baseret på replikering anvendes. I andre tilfælde anbefaler vi den løsning, der er beskrevet i denne artikel.

Korrekt implementering med en enkelt instans

Før vi forsøger at overvinde begrænsningerne ved konfigurationen med en enkelt instans, som beskrevet ovenfor, lad os overveje, hvordan man korrekt handler i dette enkle tilfælde, da en sådan løsning faktisk er acceptabel i de applikationer, hvor race-condition fra tid til anden er acceptabel, samt fordi låsen på den enkelte instans fungerer som det grundlag, der anvendes i den distribuerede algoritme, der er beskrevet her.

For at erhverve en lås, gør vi følgende:

SET resource_name my_random_value NX PX 30000

Denne kommando sætter nøglen, kun hvis den ikke allerede eksisterer (NX-option), med en udløbstid på 30000 millisekunder (PX-option). For nøglen sættes værdien til “myrandomvalue”. Denne værdi skal være unik på tværs af alle kunder og alle låseanmodninger.
Generelt bruges en tilfældig værdi til sikkert at frigive låsen ved hjælp af et script, der informerer Redis: slet nøglen, kun hvis den eksisterer, og værdien, der er gemt i den, er præcis den, der blev 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

Det er vigtigt at forhindre, at låsen frigives af en anden client. For eksempel kan en client erhverve en lås, derefter låse sig fast under en operation, der tager længere tid end den oprindelige låses udløbstid (så nøglen når at udløbe), og senere fjerne låsen, som blev sat af en anden client.
At bruge en simpel DEL er usikkert, da en client kan fjerne en lås sat af en anden client. I modsætning hertil, ved brug af ovenstående script, er hver lås "underskrevet" med en tilfældig streng, så kun den client, der tidligere har sat den, kan fjerne den.

Hvad skal denne tilfældige streng være? Jeg antager, at det bør være 20 byte fra /dev/random, men der findes mindre omkostningskrævende måder at lave en streng, der er tilstrækkelig unik til de formål, du står overfor. For eksempel ville det være okay at så RC4 med /dev/random og derefter generere en pseudo-tilfældig strøm baseret på det. En enklere løsning involverer en kombination af unix-tid i mikrosekundopløsning plus klient-ID; det er ikke så sikkert, men det vil sandsynligvis opfylde niveauet af opgaver i de fleste kontekster.

Den tid, vi bruger som et mål for nøglelivsspand, kaldes "blokeringens gyldighedstid". Denne værdi er samtidig den periode, hvorefter blokeringen automatisk vil blive frigivet, og den tid, som klienten har til at udføre operationen, inden en anden klient kan blokere denne ressource uden faktisk at bryde garantierne for gensidig udelukkelse. Denne garanti er begrænset til et bestemt tidsvindue, der starter fra det øjeblik, blokeringen erhverves.

Så vi har diskuteret en god måde at erhverve og frigive en blokering på. 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 disse garantier.

Redlock-algoritmen

I den distribuerede version af algoritmen antages det, at vi har N ledende Redis-instanser. Disse noder er helt uafhængige af hinanden, så vi bruger ikke replikering eller noget andet implicit koordinationssystem. Vi har allerede forklaret, hvordan man sikkert erhverver og frigiver en blokering på en enkelt instans. Vi tager som en given, at algoritmen ved arbejde med en enkelt instans vil anvende denne metode. I vores eksempler sætter vi N lig med 5, hvilket er et rimeligt tal. Vi skal derfor bruge 5 ledende Redis-instanser på forskellige computere eller virtuelle maskiner for at sikre, at de kan fungere for det meste uafhængigt af hinanden.

For at erhverve en blokering udfører klienten følgende operationer:

1. Henter den aktuelle tid i millisekunder.
2. Klienten forsøger sekventielt at opnå låsning af alle N-instanser ved at bruge det samme nøgleord og tilfældige værdier i alle tilfælde. I trin 2, når låsningen etableres for hver instans, anvender klienten for at få den en forsinkelse, der er kort sammenlignet med den tid, låsningen automatisk ophæves. For eksempel, hvis låsetidens længde er 10 sekunder, kan forsinkelsen være i området ~ 5-50 millisekunder. På den måde undgår man, at klienten kan være låst i lang tid, mens han forsøger at nå den fejlslagne Redis-node: hvis instansen ikke er tilgængelig, forsøger vi så hurtigt som muligt at oprette forbindelse til en anden instans.
3. For at opnå låsningen beregner klienten, hvor lang tid der er gået; for dette trækker han tidsstemplet, der blev opnået i trin 1, fra den aktuelle tid. Først når klienten har fået låsningen på de fleste instanser (mindst 3), og den samlede tid, der er taget for at få låsningen, er mindre end låsningens varighed, betragtes det som, at låsen er blevet opnået.
4. Hvis låsningen er blevet opnået, betragtes låsens gyldighedsperiode som den oprindelige længde af låsningen minus den forløbne tid, beregnet i trin 3.
5. Hvis klienten af en eller anden grund ikke kunne opnå låsningen (enten kunne han ikke låse N/2+1 instanser, eller låsens varighed viste sig at være negativ), vil han forsøge at låse op for alle instanser (selv dem, som man mente, han ikke kunne låse).

Er algoritmen asynkron?

Denne algoritme er baseret på antagelsen om, at selvom der ikke er synkroniserede ure, som alle processer arbejder efter, så går den lokale tid i hver proces stadig i omtrent samme tempo, og forskellen er lille sammenlignet med den samlede tid, det tager for låsningen at ophæves automatisk. Denne antagelse minder meget om situationen i almindelige computere: på hver computer er der lokale ure, og generelt kan vi regne med, at tidsforskellen mellem forskellige computere er lille.

På dette stadie skal vi formulere vores gensidige udelukkelsesregel mere omhyggeligt: Gensidig udelukkelse er kun garanteret, hvis klienten, der holder låsen, afslutter arbejdet inden for den periode, hvor låsen er gyldig (denne værdi er opnået i trin 3), minus en yderligere tidsperiode (kun nogle millisekunder for at kompensere for tidsforskydningen mellem processerne).

Yderligere information om sådanne systemer, der kræver præcisering af tidsforskydningen, findes i den følgende interessante artikel: Leases: en effektiv fejltolerant mekanisme til distribution af filcachekonsistens.

Genforsøg ved fejl

Når klienten ikke var i stand til at få låsen, skal de forsøge at gøre det igen efter en tilfældig forsinkelse; dette gøres for at desynkronisere mange klienter, der forsøger at erhverve låsen for den samme ressource samtidig (hvilket kan føre til en 'split brain'-situation, hvor der ikke er nogen vindere). Desuden, jo hurtigere klienten forsøger at erhverve låsen for de fleste Redis-instanser, jo smallere bliver vinduet, hvor split brain-situationen kan opstå (og jo mindre behov er der for genforsøg). Derfor bør klienten ideelt set forsøge at sende SET-kommandoer til N instanser samtidig ved hjælp af multiplexering.

Her er det vigtigt at understrege, hvor kritisk det er, at klienter, der ikke kunne erhverve de fleste låse, frigiver (delvist) erhvervede låse, så man ikke skal vente på udløbet af nøglen, før låsen på ressourcen igen kan erhverves (dog, hvis der opstår netværksfragmentering, og klienten mister forbindelsen til Redis-instanserne, skal der betales en straf for brud på tilgængeligheden, mens man venter på, at nøglen udløber).

Frigivelse af lås

Frigivelse af lås er en simpel operation, der blot kræver, at man låser alle instanser op, uanset om klienten mener, at de har været i stand til at låse en bestemt instans.

Overvejelser om sikkerhed

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

Lad os antage, at klienten har formået at opnå lås på det meste af instanserne. Hver af instanserne vil indeholde en nøgle med den samme livstid for alle. Men hver af disse nøgler blev sat på et tidspunkt, så deres udløbstid vil være forskellig. Hvis den første nøgle blev sat i et øjeblik, der er mindst T1 (det tidspunkt, vi vælger før kontakten med den første server), og den sidste nøgle blev sat i et øjeblik, der er mindst T2 (det tidspunkt, hvor svaret fra den sidste server blev modtaget), så er vi sikre på, at den første nøgle i mængden, der vil udløbe, vil eksistere mindst MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Alle andre nøgler vil udløbe 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 opnå lås, da N/2+1 SET NX-operationer ikke kan lykkes, hvis der allerede eksisterer N/2+1 nøgler. Derfor, hvis låsen er blevet opnået, kan den ikke opnås igen på samme tidspunkt (det ville bryde egenskaben om gensidig udelukkelse).
Det er sandt, at vi vil sikre os, at mængden af klienter, der forsøger at opnå lås samtidigt, ikke kan have succes samtidigt.

Hvis klienten har låst størstedelen af instanserne og har brugt tid svarende til eller mere end den maksimale låsetid, vil den betragte låsen som ugyldig og låse instanserne op. Derfor må vi kun tage hensyn til det tilfælde, hvor klienten har været i stand til at låse størstedelen af instanserne på kortere tid end gyldigheden. I det tilfælde, angående det ovenstående argument, inden for tiden MIN_VALIDITY bør ingen klient være i stand til at få låsen igen. Derfor kan flere klienter låse N/2+1 instanser på samme tid (som slutter, når trin 2 er afsluttet), kun når tiden for at låse størstedelen var længere end TTL-tiden, hvilket gør låsen ugyldig.

Kan du give et formelt bevis for sikkerhed, pege på eksisterende lignende algoritmer, eller finde en fejl i det beskrevne?

Overvejelser om tilgængelighed

Systemets tilgængelighed afhænger af tre hovedkarakteristika:

1. Automatisk ophævelse af blokering (da nøgleudløbsdatoer udløber): til sidst vil nøglerne blive tilgængelige igen for at blive brugt til blokeringer.
2. Det faktum, at kunder typisk hjælper hinanden ved at fjerne blokeringer, når den nødvendige blokering ikke er blevet erhvervet, eller når den er blevet erhvervet, men arbejdet er færdigt; derfor er det meget sandsynligt, at vi ikke skal vente på, at nøglerne udløber, for at genindkøbe en blokering.
3. Det faktum, at når en kunde skal forsøge at få en blokering igen, venter han relativt længere end den tid, der kræves for at erhverve de fleste blokeringer. Dette mindsker sandsynligheden for en splittet hjerne-situation ved konkurrence om ressourcer.

Men man må betale en straf for reduktionen i tilgængeligheden svarende til TTL-tiden i netværkssegmenterne, så hvis der er kontinuerlige segmenter, kan denne straf blive ubegribelig stor. Dette sker hver gang, en kunde erhverver en blokering og derefter bliver afskåret i et andet segment, før han har haft tid til at frigive den.

I princippet, hvis der er uendelige kontinuerlige netværkssegmenter, kan systemet være utilgængeligt i uendelig tid.

Ydelse, fejlgendannelse og fsync

Mange bruger Redis, da det er nødvendigt at sikre høj ydeevne af låseserveren, på niveau med de forsinkelser, der er nødvendige for at erhverve og frigive blokeringer, samt det antal operationer, der kan gennemføres pr. sekund af sådanne erhvervelser/frigivelser. For at imødekomme dette krav er der en kommunikationsstrategi med N Redis-servere for at reducere latenstiden. Dette er en multiplexeringsstrategi (eller 'fattigmandsmultiplexering', hvor soklen sættes i ikke-blokerende tilstand, sender alle kommandoer og læser kommandoer senere, idet man antager, at drejningstiden mellem klienten og hver af instanserne er ens).

Sandt, man må også tage højde for en overvejelse relateret til langtidsholdbar lagring af data, hvis vi ønsker at skabe en model med sikker fejlgendannelse.

For clarity, let's assume we configure Redis without any persistent data storage at all. The client manages to lock 3 out of 5 instances. One of the instances that the client was able to lock restarts, and at that moment, 3 instances for the same resource that we can lock arise again, and another client can, in turn, lock the restarted instance, violating the security property that stipulates the exclusivity of locks.

If we enable ahead-of-time data saving (AOF), the situation improves somewhat. For example, one can raise the server by sending the SHUTDOWN command and restarting it. Since expiration operations in Redis are semantically implemented in such a way that time continues to flow even when the server is down, all our requirements are fine. Fine as long as a proper shutdown is ensured. But what about power outages? If Redis is configured by default, with fsync synchronization on disk every second, it is possible that after a restart we might miss our key. Theoretically, if we want to guarantee the safety of locks during any instance restart, we must enable fsync=always in the persistent data storage settings. This will completely kill performance, down to levels of such CP systems that are traditionally used for safe implementation of distributed locks.

But the situation is better than it seems at first glance. In principle, the algorithm's security is maintained because when an instance restarts after a failure, it no longer participates in any locks that are currently active.

To ensure this, it is only necessary to ensure that after a failure, the instance remains unavailable for a time slightly exceeding the maximum TTL that we use. This way, we will wait for the expiration and automatic release of all keys that were active at the time of the failure.

Ved at bruge udsatte genstarter er det i princippet muligt at opnå sikkerhed selv uden nogen langvarig vedholdenhed i Redis. Det skal dog bemærkes, at dette kan føre til en straf for overtrædelse af tilgængelighed. For eksempel, ved en svigt af de fleste instanser, vil systemet blive globalt utilgængeligt i TTL-perioden (og ingen ressourcer kan blokeres i mellemtiden).

Øger algoritmens tilgængelighed: forlænge blokeringen

Hvis det arbejde, der udføres af kunderne, består af små faser, er det muligt at forkorte den standard angivne blokeringstid og implementere et mekanisme til forlængelse af blokeringer. I princippet, hvis kunden er optaget af beregninger, og værdien af blokeringens varighed faretruende falder, kan vi sende et Lua-script til alle instanser, som forlænges TTL for nøglen, hvis nøglen stadig eksisterer, og dens værdi stadig er tilfældig, som blev erhvervet, da blokeringen blev opnået.

Kunden skal kun betragte blokeringen som genvundet, hvis det lykkedes dem at blokere flertallet af instanser inden for varigheden.

Det skal dog bemærkes, at algoritmen teknisk set ikke ændres, så det maksimale antal genforsøg for at opnå blokeringer skal være begrænset, ellers vil tilgængelighedsegenskaberne blive overtrådt.

Kilde: habr.com