ProHoster > blog > administratie > Gedistribueerde vergrendeling met Redis

Gedistribueerde vergrendeling met Redis

Hé Habr!

Vandaag brengen we een vertaling van een complex artikel over de implementatie van gedistribueerde vergrendeling met Redis onder uw aandacht en nodigen we u uit om te praten over de vooruitzichten van Redis als onderwerp. Analyse van het betreffende Redlock-algoritme van Martin Kleppmann, auteur van het boek "Toepassingen met hoge belasting", gegeven hier.

Gedistribueerde vergrendeling is een zeer nuttige primitief die wordt gebruikt in veel omgevingen waar verschillende processen op een elkaar uitsluitende manier moeten werken op gedeelde bronnen.

Er zijn een aantal bibliotheken en berichten die beschrijven hoe je DLM (Distributed Lock Manager) kunt implementeren met Redis, maar elke bibliotheek hanteert een andere aanpak en de garanties die ze bieden zijn vrij zwak vergeleken met wat haalbaar is met een iets geavanceerder ontwerp.

In dit artikel zullen we proberen een voorwaardelijk canoniek algoritme te beschrijven dat laat zien hoe u gedistribueerde vergrendeling kunt implementeren met Redis. We zullen het hebben over een algoritme genaamd Roodslot, het implementeert een gedistribueerde lock-manager en naar onze mening is dit algoritme veiliger dan de gebruikelijke aanpak met één exemplaar. We hopen dat de gemeenschap het zal analyseren, feedback zal geven en het zal gebruiken als startpunt voor complexere of alternatieve projecten.

Implementatie

Voordat we verder gaan met de beschrijving van het algoritme, bieden we verschillende links naar kant-en-klare implementaties. Ze kunnen ter referentie worden gebruikt.

Beveiligings- en beschikbaarheidsgaranties

We gaan ons ontwerp modelleren met slechts drie eigenschappen waarvan we denken dat ze de minimale garanties bieden die nodig zijn om effectief gebruik te maken van gedistribueerde vergrendeling.

  1. Beveiligingseigenschap: wederzijdse uitsluiting. Op elk moment kan slechts één klant het slot vasthouden.
  2. Beschikbaarheid Eigenschap A: Geen impasses. Het is altijd mogelijk om uiteindelijk een vergrendeling te verkrijgen, zelfs als de client die de bron heeft vergrendeld mislukt of op een ander schijfsegment terechtkomt.
  3. Beschikbaarheid Eigenschap B: Fouttolerantie. Zolang het merendeel van de Redis-knooppunten actief is, kunnen clients vergrendelingen verkrijgen en vrijgeven.

Waarom implementatie op basis van foutherstel in dit geval niet voldoende is
Om te begrijpen wat we gaan verbeteren, analyseren we de huidige stand van zaken met de meeste gedistribueerde sluitbibliotheken op basis van Redis.

De eenvoudigste manier om een ​​bron te vergrendelen met Redis is door een sleutel in de instantie te maken. Normaal gesproken wordt een sleutel gemaakt met een beperkte levensduur. Dit wordt bereikt met behulp van de vervalfunctie in Redis, dus vroeg of laat wordt deze sleutel vrijgegeven (eigenschap 2 in onze lijst). Wanneer de client de bron moet vrijgeven, wordt de sleutel verwijderd.

Op het eerste gezicht werkt deze oplossing best goed, maar er is een probleem: onze architectuur creëert een single point offailure. Wat gebeurt er als het Redis-hostexemplaar mislukt? Laten we dan een slaaf toevoegen! En we zullen het gebruiken als de presentator niet beschikbaar is. Helaas is deze optie niet haalbaar. Door dit te doen, kunnen we de wederzijdse uitsluitingseigenschap die we nodig hebben om de veiligheid te garanderen niet correct implementeren, omdat replicatie in Redis asynchroon is.

Het is duidelijk dat in zo’n model een race condition optreedt:

  1. Klant A verkrijgt een slot op de master.
  2. De master faalt voordat de sleutelinvoer naar de slave wordt overgedragen.
  3. De volger wordt gepromoveerd tot leider.
  4. Klant B verkrijgt een vergrendeling op dezelfde bron die A al heeft vergrendeld. VEILIGHEIDSOVERTREDING!

Soms is het volkomen normaal dat bij bijzondere omstandigheden, zoals een storing, meerdere klanten tegelijk het slot vast kunnen houden. In dergelijke gevallen kan een op replicatie gebaseerde oplossing worden toegepast. Anders raden we de oplossing aan die in dit artikel wordt beschreven.

Correcte implementatie met één exemplaar

Voordat we proberen de tekortkomingen van de hierboven beschreven configuratie met één exemplaar te overwinnen, moeten we eerst begrijpen hoe we dit eenvoudige geval op de juiste manier kunnen aanpakken, aangezien deze oplossing feitelijk geldig is in toepassingen waar een race condition van tijd tot tijd acceptabel is, en ook omdat het blokkeren van een enkele instantie dient als basis die wordt gebruikt in het hier beschreven gedistribueerde algoritme.

Ga als volgt te werk om een ​​slot te verkrijgen:

SET resource_name my_random_value NX PX 30000

Met dit commando wordt alleen een sleutel geïnstalleerd als deze nog niet bestaat (NX-optie), met een geldigheidsperiode van 30000 milliseconden (PX-optie). De sleutel is ingesteld op “myrandomvalue" Deze waarde moet uniek zijn voor alle clients en alle vergrendelingsverzoeken.
In principe wordt een willekeurige waarde gebruikt om het slot veilig vrij te geven, waarbij een script tegen Redis zegt: verwijder alleen de sleutel als deze bestaat en de daarin opgeslagen waarde precies is wat werd verwacht. Dit wordt bereikt met behulp van het volgende Lua-script:

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

Dit is belangrijk om te voorkomen dat een slot van een andere klant wordt verwijderd. Een cliënt kan bijvoorbeeld een slot verwerven, vervolgens vast komen te zitten in een handeling die langer duurt dan het eerste slot (zodat de sleutel tijd heeft om te verlopen) en later het slot verwijderen dat een andere cliënt had geplaatst.
Het gebruik van een eenvoudige DEL is onveilig omdat een client een slot van een andere client kan verwijderen. Wanneer u daarentegen het bovenstaande script gebruikt, wordt elk slot “ondertekend” met een willekeurige reeks, zodat alleen de klant die het eerder heeft geplaatst het kan verwijderen.

Wat moet deze willekeurige string zijn? Ik vermoed dat het 20 bytes uit /dev/urandom moet zijn, maar je kunt goedkopere manieren vinden om de string uniek genoeg te maken voor jouw doeleinden. Het zou bijvoorbeeld prima zijn om RC4 te seeden met /dev/urandom en er vervolgens een pseudo-willekeurige stream van te genereren. Een eenvoudiger oplossing omvat een combinatie van Unix-tijd in microseconderesolutie plus de client-ID; het is niet zo veilig, maar in de meeste contexten is het waarschijnlijk voldoende.

De tijd die we gebruiken als maatstaf voor de levensduur van de sleutel wordt de ‘slotlevensduur’ genoemd. Deze waarde is zowel de hoeveelheid tijd voordat de vergrendeling automatisch wordt vrijgegeven als de hoeveelheid tijd die een client heeft om een ​​bewerking te voltooien voordat een andere client op zijn beurt die bron kan vergrendelen, zonder daadwerkelijk de wederzijdse uitsluitingsgaranties te schenden. Deze garantie is slechts beperkt tot een bepaalde periode, die begint vanaf het moment van aankoop van het slot.

We hebben dus een goede manier besproken om een ​​slot te verkrijgen en vrij te geven. Het systeem (als we het hebben over een niet-gedistribueerd systeem dat uit één enkel en altijd beschikbaar exemplaar bestaat) is veilig. Laten we dit concept uitbreiden naar een gedistribueerd systeem, waar we dergelijke garanties niet hebben.

Redlock-algoritme

De gedistribueerde versie van het algoritme gaat ervan uit dat we N Redis-masters hebben. Deze knooppunten zijn volledig onafhankelijk van elkaar, dus we gebruiken geen replicatie of enig ander impliciet coördinatiesysteem. We hebben al besproken hoe u veilig een vergrendeling op één exemplaar kunt verkrijgen en vrijgeven. We gaan ervan uit dat het algoritme, wanneer het met een enkele instantie werkt, precies deze methode zal gebruiken. In onze voorbeelden stellen we N in op 5, wat een redelijke waarde is. We zullen dus vijf Redis-masters op verschillende computers of virtuele machines moeten gebruiken om ervoor te zorgen dat ze grotendeels onafhankelijk van elkaar werken.

Om een ​​slot te verkrijgen, voert de client de volgende handelingen uit:

  1. Krijgt de huidige tijd in milliseconden.
  2. Probeert opeenvolgend een vergrendeling te verkrijgen op alle N exemplaren, waarbij in alle gevallen dezelfde sleutelnaam en willekeurige waarden worden gebruikt. In fase 2, wanneer de klant een vergrendeling per exemplaar instelt, gebruikt de klant een vertraging om deze te verwerven die kort genoeg is in vergelijking met de tijd waarna de vergrendeling automatisch wordt vrijgegeven. Als de blokkeerduur bijvoorbeeld 10 seconden is, kan de vertraging tussen de 5 en 50 milliseconden liggen. Dit elimineert de situatie waarin de client lange tijd geblokkeerd zou kunnen blijven bij het bereiken van een mislukt Redis-knooppunt: als de instantie niet beschikbaar is, proberen we zo snel mogelijk verbinding te maken met een andere instantie.
  3. Om een ​​slot te nemen, berekent de klant hoeveel tijd er is verstreken; Om dit te doen, wordt van de werkelijke tijdswaarde de tijdstempel afgetrokken die in stap 1 is verkregen. Als en alleen als de client in staat was de vergrendeling van de meerderheid van de instanties (ten minste 3) te verkrijgen, en de totale tijd die nodig was om het verkrijgen van de blokkering, korter dan de blokkeringsduur, wordt de blokkering geacht te zijn verkregen.
  4. Als er een blokkering is verkregen, wordt als blokkeringsduur de oorspronkelijke blokkeringsduur minus de in stap 3 berekende verstreken tijd genomen.
  5. Als de client er om wat voor reden dan ook niet in slaagt de vergrendeling te verkrijgen (het was niet in staat om N/2+1 instances te vergrendelen, of de vergrendelingsduur was negatief), dan zal het proberen alle instances te ontgrendelen (zelfs de instances waarvan hij dacht dat hij deze niet kon blokkeren). ).

Is het algoritme asynchroon?

Dit algoritme is gebaseerd op de veronderstelling dat, hoewel er geen gesynchroniseerde klok is waarop alle processen zouden werken, de lokale tijd in elk proces nog steeds met ongeveer hetzelfde tempo loopt, en dat de fout klein is vergeleken met de totale tijd waarna het slot wordt uitgeschakeld. automatisch vrijgegeven. Deze aanname lijkt sterk op de situatie die typisch is voor gewone computers: elke computer heeft een lokale klok, en we kunnen er meestal op rekenen dat het tijdsverschil tussen verschillende computers klein is.

Op dit punt moeten we onze wederzijdse uitsluitingsregel zorgvuldiger formuleren: wederzijdse uitsluiting is alleen gegarandeerd als de cliënt die het slot vasthoudt naar buiten gaat gedurende de tijd dat het slot geldig is (deze waarde verkregen in stap 3), min nog wat tijd (in totaal enkele milliseconden om het tijdsverschil tussen processen te compenseren).

Het volgende interessante artikel vertelt meer over dergelijke systemen die coördinatie van tijdsintervallen vereisen: Leases: een efficiënt fouttolerant mechanisme voor consistentie van de gedistribueerde bestandscache.

Opnieuw proberen bij mislukking

Wanneer een client er niet in slaagt een slot te verkrijgen, moet hij het na een willekeurige vertraging opnieuw proberen; dit wordt gedaan om meerdere clients te desynchroniseren die tegelijkertijd proberen een slot op dezelfde bron te verkrijgen (wat kan leiden tot een "split-brain" -situatie waarin er geen winnaars zijn). Bovendien geldt dat hoe sneller een client een vergrendeling probeert te verkrijgen op de meeste Redis-instanties, hoe smaller het venster waarin een split-brain-situatie kan optreden (en hoe kleiner de noodzaak voor nieuwe pogingen). Idealiter zou de client daarom moeten proberen SET-opdrachten tegelijkertijd naar N instanties te verzenden met behulp van multiplexing.

Het is de moeite waard om hier te benadrukken hoe belangrijk het is voor klanten die er niet in slagen de meerderheid van de sloten te verwerven, om de (gedeeltelijk) verkregen sloten vrij te geven, zodat ze niet hoeven te wachten tot de sleutel verloopt voordat de vergrendeling op de bron opnieuw kan worden verkregen. (Als er echter netwerkfragmentatie optreedt en de client het contact met de Redis-instanties verliest, moet u een beschikbaarheidsboete betalen terwijl u wacht tot de sleutel verloopt).

Maak het slot los

Het vrijgeven van een vergrendeling is een eenvoudige handeling waarbij eenvoudigweg alle exemplaren moeten worden ontgrendeld, ongeacht of de client een bepaalde instantie met succes heeft vergrendeld.

Beveiligingsoverwegingen

Is het algoritme veilig? Laten we ons proberen voor te stellen wat er in verschillende scenario's gebeurt.

Laten we om te beginnen aannemen dat de client op de meeste instances een lock heeft kunnen verkrijgen. Elke instantie bevat een sleutel met dezelfde levensduur. Elk van deze sleutels is echter op een ander tijdstip geïnstalleerd, waardoor ze op verschillende tijdstippen verlopen. Maar als de eerste sleutel is geïnstalleerd op een tijdstip dat niet slechter is dan T1 (het tijdstip dat we kiezen voordat we contact opnemen met de eerste server), en de laatste sleutel is geïnstalleerd op een tijdstip dat niet slechter is dan T2 (het tijdstip waarop het antwoord is ontvangen van de laatste server), dan hebben we er vertrouwen in dat de eerste sleutel in de set die vervalt, in ieder geval zal overleven MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Alle andere sleutels verlopen later, dus we kunnen er zeker van zijn dat alle sleutels in ieder geval deze tijd tegelijkertijd geldig zijn.

Gedurende de tijd dat de meeste sleutels geldig blijven, zal een andere client het slot niet kunnen verkrijgen, omdat N/2+1 SET NX-bewerkingen niet kunnen slagen als er al N/2+1 sleutels bestaan. Daarom is het, zodra een slot is aangeschaft, onmogelijk om het op hetzelfde moment opnieuw te verkrijgen (dit zou in strijd zijn met de eigenschap van wederzijdse uitsluiting).
Wij willen er echter voor zorgen dat meerdere klanten die tegelijkertijd een slot proberen te bemachtigen, niet tegelijkertijd kunnen slagen.

Als de client het merendeel van de exemplaren voor ongeveer of langer dan de maximale vergrendelingsduur heeft vergrendeld, wordt de vergrendeling als ongeldig beschouwd en worden de exemplaren ontgrendeld. Daarom hoeven we alleen rekening te houden met het geval waarin de klant erin slaagde de meerderheid van de instanties te blokkeren in een tijd die korter is dan de vervaldatum. In dit geval, met betrekking tot het bovenstaande argument, gedurende de tijd MIN_VALIDITY geen enkele klant mag het slot opnieuw kunnen bemachtigen. Daarom kunnen veel clients N/2+1-instanties in dezelfde tijd (die eindigt aan het einde van fase 2) alleen vergrendelen als de tijd om het merendeel te vergrendelen groter was dan de TTL-tijd, waardoor de vergrendeling ongeldig wordt.

Kunt u een formeel beveiligingsbewijs leveren, bestaande soortgelijke algoritmen aangeven of een bug in het bovenstaande vinden?

Toegankelijkheidsoverwegingen

De systeembeschikbaarheid is afhankelijk van drie hoofdkenmerken:

  1. Sloten automatisch vrijgeven (als sleutels verlopen): Sleutels zullen uiteindelijk weer beschikbaar zijn om te gebruiken voor sloten.
  2. Het feit dat opdrachtgevers elkaar doorgaans helpen door sloten te verwijderen wanneer het gewenste slot nog niet is verkregen, of wel is verworven en de klus is geklaard; het is dus waarschijnlijk dat we niet hoeven te wachten tot de sleutels verlopen zijn voordat we het slot opnieuw kunnen verkrijgen.
  3. Het feit dat wanneer een klant opnieuw moet proberen een slot te verkrijgen, hij relatief langer wacht dan de periode die nodig is om de meeste sloten te verkrijgen. Dit verkleint de kans op een gespleten situatie bij het strijden om hulpbronnen.

Er is echter een beschikbaarheidsboete die gelijk is aan de TTL van de netwerksegmenten, dus als er aangrenzende segmenten zijn, kan de boete onbepaald zijn. Dit gebeurt wanneer een klant een slot verkrijgt en vervolgens naar een ander segment gaat voordat deze het kan vrijgeven.

In principe kan een systeem, gegeven oneindige aaneengesloten netwerksegmenten, voor een oneindige periode onbeschikbaar blijven.

Prestaties, failover en fsync

Veel mensen gebruiken Redis omdat ze hoge serverprestaties nodig hebben in termen van de latentie die nodig is om vergrendelingen te verwerven en vrij te geven, en het aantal acquisities/releases dat per seconde kan worden voltooid. Om aan deze vereiste te voldoen, is er een strategie om met N Redis-servers te communiceren om de latentie te verminderen. Dit is een multiplexstrategie (of "poor man's multiplexing", waarbij de socket in niet-blokkerende modus wordt gezet, alle opdrachten verzendt en de opdrachten later leest, ervan uitgaande dat de retourtijd tussen de client en elke instantie vergelijkbaar is) .

We moeten echter ook rekening houden met de overwegingen die gepaard gaan met gegevensopslag op de lange termijn als we ernaar streven een model te creëren met betrouwbaar herstel na storingen.

Laten we, om het probleem te verduidelijken, aannemen dat we Redis configureren zonder gegevensopslag op de lange termijn. De client slaagt erin om 3 van de 5 instanties te blokkeren. Eén van de instances die de client heeft weten te blokkeren is opnieuw gestart, en op dit moment zijn er weer drie instances voor dezelfde bron, die we kunnen blokkeren, en een andere client kan op zijn beurt de opnieuw gestarte instance blokkeren, waardoor de beveiligingseigenschap wordt geschonden die veronderstelt exclusiviteit van sloten.

Als u data ahead (AOF) inschakelt, verbetert de situatie enigszins. U kunt bijvoorbeeld een server promoten door de opdracht SHUTDOWN te verzenden en deze opnieuw op te starten. Omdat vervalbewerkingen in Redis semantisch zo zijn geïmplementeerd dat de tijd blijft stromen, zelfs als de server is uitgeschakeld, zijn al onze vereisten prima. Dit is normaal zolang een normale uitschakeling gewaarborgd is. Wat te doen bij stroomuitval? Als Redis standaard is geconfigureerd, waarbij fsync elke seconde op schijf wordt gesynchroniseerd, is het mogelijk dat we na een herstart onze sleutel niet meer hebben. Theoretisch gezien zouden we dit moeten inschakelen als we de vergrendelingsbeveiliging willen garanderen tijdens het opnieuw opstarten van een instantie fsync=always in de instellingen voor langdurige gegevensopslag. Dit zal de prestaties volledig ondermijnen, tot op het niveau van CP-systemen die traditioneel worden gebruikt om gedistribueerde sloten veilig te implementeren.

Maar de situatie is beter dan het op het eerste gezicht lijkt. In principe blijft de veiligheid van het algoritme behouden, omdat wanneer de instance na een storing opnieuw wordt opgestart, deze niet langer deelneemt aan een vergrendeling die momenteel actief is.

Om dit te garanderen, hoeven we er alleen maar voor te zorgen dat de instance na een fout niet beschikbaar blijft gedurende een periode die iets groter is dan de maximale TTL die we gebruiken. Op deze manier wachten we tot de vervaldatum en automatische vrijgave van alle sleutels die actief waren op het moment van de storing.

Door een vertraagde herstart te gebruiken, is het in principe mogelijk om veiligheid te bereiken, zelfs als er geen sprake is van langdurige persistentie in Redis. Houd er echter rekening mee dat dit een boete kan opleveren voor het schenden van de toegankelijkheid. Als bijvoorbeeld de meerderheid van de instanties faalt, zal het systeem wereldwijd niet meer beschikbaar zijn voor de TTL (en gedurende deze tijd kan geen enkele bron worden geblokkeerd).

We vergroten de beschikbaarheid van het algoritme: we breiden de blokkering uit

Als het werk van klanten uit kleine stappen bestaat, is het mogelijk om de standaard vergrendelingsduur te verkorten en een mechanisme te implementeren voor het verlengen van sloten. Als de client bezig is met computergebruik en de vervalwaarde van het slot gevaarlijk laag is, kunt u in principe een Lua-script naar alle instanties sturen dat de TTL van de sleutel verlengt als de sleutel nog steeds bestaat en de waarde ervan nog steeds een willekeurige waarde is die wordt verkregen toen de sleutel werd uitgevoerd. slot aangeschaft.

Een klant mag alleen overwegen dat een vergrendeling opnieuw wordt verkregen als hij erin is geslaagd de meerderheid van de instanties binnen de geldigheidsperiode te vergrendelen.

Het is waar dat het algoritme technisch gezien niet verandert, dus het maximale aantal herhaalde pogingen om sloten te verkrijgen moet beperkt zijn, anders worden de toegankelijkheidseigenschappen geschonden.

Bron: www.habr.com

Voeg een reactie