Gedecentraliseerde locks met Redis

Hallo, Habr!

Vandaag bieden we u een vertaling aan van een complex artikel over de implementatie van gedistribueerde locks met Redis en willen we het hebben over de potentie van Redis als onderwerp. De analyse van het besproken algoritme Redlock door Martin Kleppmann, auteur van het boek "Hoogbelaste applicaties", is gegeven hier.

Gedistribueerde locks zijn een zeer nuttige primitive die in veel omgevingen wordt toegepast waar verschillende processen moeten werken met gedeelde resources op basis van wederzijds uitsluiten.

Er zijn verschillende bibliotheken en artikelen die beschrijven hoe DLM (Distributed Lock Manager) te implementeren met behulp van Redis, maar elke bibliotheek hanteert zijn eigen aanpak, en de garanties die daarbij worden geboden zijn over het algemeen vrij zwak in vergelijking met wat haalbaar is met een iets geavanceerdere architectuur.

In dit artikel zullen we proberen een min of meer canoniek algoritme te beschrijven dat aantoont hoe gedistribueerde locks met Redis kunnen worden geïmplementeerd. We zullen het hebben over het algoritme genaamd Redlock, dat een gedistribueerde lockmanager implementeert en naar onze mening veiliger is dan de gebruikelijke aanpak met een enkele instantie. We hopen dat de gemeenschap het zal analyseren, feedback zal geven en het zal gebruiken als uitgangspunt voor de implementatie van complexere of alternatieve projecten.

Implementaties

Voordat we overgaan naar de beschrijving van het algoritme, geven we enkele links naar al bestaande implementaties. Deze kunnen als referentie worden gebruikt.

• Redlock-rb (implementatie voor Ruby). Er is ook fork Redlock-rb, dat een package (gem) toevoegt voor gebruiksgemak in distributie, en niet alleen daarvoor.
• Redlock-py (implementatie voor Python).
• Aioredlock (implementatie voor Asyncio Python).
• Redlock-php (implementatie voor PHP).
• PHPRedisMutex (nog een implementatie voor PHP)
• cheprasov/php-redis-lock (PHP-bibliotheek voor locks)
• Redsync (implementatie voor Go).
• Redisson (implementatie voor Java).
• Redis::DistLock (implementatie voor Perl).
• Redlock-cpp (implementatie voor C++).
• Redlock-cs (implementatie voor C#/.NET).
• RedLock.net (implementatie voor C#/.NET). Met ondersteuning voor async en lock extensies.
• ScarletLock (implementatie voor C# .NET met configureerbare dataopslag)
• Redlock4Net (implementatie voor C# .NET)
• node-redlock (implementatie voor NodeJS). Inclusief ondersteuning voor het verlengen van locks.

Veiligheids- en beschikbaarheidsgaranties

We gaan ons project modelleren met slechts drie eigenschappen die, naar onze mening, de minimale garanties bieden die nodig zijn voor een effectieve benutting van gedistribueerde locks.

1. Beveiligingseigenschap: Wederzijds exclusie. Op elk moment kan slechts één cliënt de lock vasthouden.
2. Toegankelijkheidseigenschap A: Afwezigheid van wederzijdse blokkades. Uiteindelijk kan de lock altijd verkregen worden, zelfs als de cliënt die de bron heeft geblokkeerd, uitvalt of in een ander schijfsegment komt.
3. Toegankelijkheidseigenschap B: Fouttolerantie. Zolang de meeste Redis-knooppunten werken, zijn cliënten in staat om locks te verwerven en vrij te geven.

Waarom is een implementatie die is gebaseerd op herstel na een storing in dit geval onvoldoende?
Om te begrijpen wat we willen verbeteren, laten we de huidige stand van zaken analyseren met de meeste bibliotheken voor gedistribueerde locks die op Redis zijn gebaseerd.

De eenvoudigste manier om een bron te blokkeren met Redis is door een sleutel in de instantie te creëren. Gewoonlijk wordt de sleutel met een beperkte levensduur aangemaakt, dit wordt bereikt met de expires mogelijkheid in Redis, dus vroeg of laat wordt deze sleutel vrijgegeven (eigenschap 2 op onze lijst). Wanneer de cliënt de bron moet vrijgeven, verwijdert hij de sleutel.

Op het eerste gezicht werkt deze oplossing prima, maar er is een probleem: onze architectuur creëert een enkele foutpunt. Wat gebeurt er als de primaire Redis-instantie uitvalt? Laten we dan een secundaire toevoegen! En deze gebruiken als de primaire niet beschikbaar is. Helaas is deze optie niet levensvatbaar. Door dit te doen, kunnen we de wederzijdse uitsluiting, die we nodig hebben voor beveiliging, niet correct implementeren, omdat replicatie in Redis asynchroon is.

Het is duidelijk dat in dit model een race-voorwaarde ontstaat:

1. Cliënt A verwerft de lock op de primaire.
2. De primaire valt uit voordat de registratie in de sleutel aan de secundaire is doorgegeven.
3. De secundaire wordt gepromoveerd tot primaire.
4. Cliënt B verwerft de lock van dezelfde bron, die al door A is geblokkeerd. VEILIGHEIDSSCHENDING!

Soms is het volkomen normaal dat in speciale omstandigheden, bijvoorbeeld bij een storing, veel klanten tegelijkertijd een vergrendeling kunnen vasthouden. In dergelijke gevallen kan een oplossing op basis van replicatie worden toegepast. In andere gevallen raden we de oplossing aan die in dit artikel wordt beschreven.

Juiste implementatie met een enkele instantie

Voordat we proberen de tekortkomingen van de bovengenoemde configuratie met een enkele instantie te omzeilen, laten we kijken hoe we correct moeten handelen in dit eenvoudige geval, aangezien een dergelijke oplossing eigenlijk acceptabel is in toepassingen waar een raceconditie af en toe is toegestaan, en ook omdat de vergrendeling op een enkele instantie de basis vormt voor het gedistribueerde algoritme dat hier wordt beschreven.

Om de vergrendeling te verkrijgen, doen we het volgende:

SET resource_name my_random_value NX PX 30000

Dit commando stelt een sleutel in, alleen als deze nog niet bestaat (optie NX), met een vervaldatum van 30000 milliseconden (optie PX). Voor de sleutel wordt de waarde “myrandomvalue”. Deze waarde moet uniek zijn binnen alle klanten en alle vergrendelingsverzoeken.
In principe wordt een willekeurige waarde gebruikt voor een veilige vrijgave van de vergrendeling, met behulp van een script dat Redis vertelt: verwijder de sleutel alleen als deze bestaat en de waarde die erin is opgeslagen, is precies 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

Het is belangrijk om te voorkomen dat een vergrendeling wordt opgeheven door een andere klant. Bijvoorbeeld, een klant kan een vergrendeling verwerven, vervolgens vastlopen tijdens een operatie die langer duurt dan de looptijd van de eerste vergrendeling (waardoor de vervaldatum van de sleutel is verstreken) en later de vergrendeling verwijderen die door een andere klant is ingesteld.
Het gebruik van een eenvoudige DEL is onveilig, omdat een klant de vergrendeling kan verwijderen die door een andere klant is ingesteld. Daarentegen, bij gebruik van het bovenstaande script, is elke vergrendeling "ondertekend" met een willekeurige tekenreeks, zodat alleen de klant die deze eerder heeft ingesteld, deze kan verwijderen.

Wat zou deze willekeurige string moeten zijn? Ik denk dat het 20 bytes uit /dev/urandom moet zijn, maar er zijn ook goedkopere manieren om een string voldoende uniek te maken voor de doelen die voor je liggen. Bijvoorbeeld, het zou prima zijn om RC4 met /dev/urandom te zaaien en vervolgens op basis daarvan een pseudo-willekeurige stroom te genereren. Een eenvoudigere oplossing is de combinatie van Unix-tijd in microseconden plus de klant-ID; het is niet zo veilig, maar voldoet waarschijnlijk aan het niveau van de taken in de meeste contexten.

De tijd die we gebruiken als indicator voor de levensduur van de sleutel, wordt "vergrendelingsperiode" genoemd. Deze waarde is tegelijkertijd de termijn waarna de vergrendeling automatisch wordt vrijgegeven en de tijd die de klant heeft om de operatie uit te voeren, voordat een andere klant deze hulpbron kan vergrendelen, zonder daadwerkelijk de waarborgen van externe uitsluiting te schenden. Deze garantie is beperkt tot een bepaald tijdsvenster, dat begint vanaf het moment dat de vergrendeling wordt verkregen.

Dus hebben we een goede manier besproken om vergrendelingen te verwerven en vrij te geven. Het systeem (wanneer het gaat om een niet-gedistribueerd systeem, bestaande uit een enkele en altijd beschikbare instantie) is veilig. Laten we dit concept uitbreiden naar een gedistribueerd systeem, waarin we deze garanties niet hebben.

Het Redlock-algoritme

In de gedistribueerde versie van het algoritme veronderstellen we dat we N primaire Redis-servers hebben. Deze knooppunten zijn volledig onafhankelijk van elkaar, daarom gebruiken we geen replicatie of een andere impliciete coördinatiesysteem. We hebben al besproken hoe we veilig een vergrendeling kunnen verkrijgen en vrijgeven op een enkele instantie. We nemen als uitgangspunt dat het algoritme bij het werken met een enkele instantie deze methode zal gebruiken. In onze voorbeelden stellen we N gelijk aan 5, wat een redelijk getal is. We moeten dus 5 primaire Redis-servers op verschillende computers of virtuele machines gebruiken om te garanderen dat ze voornamelijk onafhankelijk van elkaar handelen.

Om een vergrendeling te verkrijgen, voert de klant de volgende bewerkingen uit:

1. Haal de huidige tijd in milliseconden op.
2. Het probeert consequent een lock te krijgen op alle N-instanties, waarbij in alle gevallen dezelfde sleutelnaam en willekeurige waarden worden gebruikt. In stap 2, bij het instellen van de lock voor elke instantie, gebruikt de cliënt een vertraging die kort genoeg is in vergelijking met de tijd waarna de lock automatisch wordt opgeheven. Bijvoorbeeld, als de duur van de lock 10 seconden is, dan kan de vertraging variëren van ~ 5-50 milliseconden. Op deze manier wordt de situatie uitgesloten waarin de cliënt lange tijd geblokkeerd zou blijven terwijl hij probeert contact te leggen met een falende Redis-node: als de instantie niet beschikbaar is, proberen we zo snel mogelijk verbinding te maken met een andere instantie.
3. Om de lock te verkrijgen, berekent de cliënt hoeveel tijd er verstreken is; daarvoor trekt hij de actuele tijd af van de tijdstempel die in stap 1 is verkregen. Pas wanneer de cliënt erin slaagt om de lock op de meeste instanties te krijgen (ten minste 3) en de totale tijd die nodig is om de lock te verkrijgen minder is dan de looptijd van de lock, wordt het verkrijgen van de lock als geslaagd beschouwd.
4. Als de lock is verkregen, wordt de looptijd ervan bepaald als de oorspronkelijke waarde van de lockduur minus de verstreken tijd, berekend in stap 3.
5. Als de cliënt om een of andere reden de lock niet kon verkrijgen (of hij heeft niet N/2+1 instanties kunnen blokkeren, of de looptijd van de lock bleek negatief te zijn), dan zal hij proberen alle instanties te ontgrendelen (zelfs die waarvan werd aangenomen dat hij ze niet kon blokkeren).

Is het algoritme asynchroon?

Dit algoritme is gebaseerd op de aanname dat, hoewel er geen gesynchroniseerde klokken zijn waarop alle processen werken, de lokale tijd in elk proces toch ongeveer in hetzelfde tempo verloopt, en de afwijking klein is in vergelijking met de totale tijd waarna de lock automatisch wordt opgeheven. Deze aanname komt sterk overeen met de situatie die gebruikelijk is voor gewone computers: elke computer heeft lokale klokken, en doorgaans kunnen we rekenen op het feit dat de tijdsafwijking tussen verschillende computers klein is.

Op dit moment moeten we onze regel van wederzijds uitsluiten nauwkeuriger formuleren: wederzijds uitsluiten is slechts gegarandeerd op voorwaarde dat de cliënt die de blokkade vasthoudt, zijn werk beëindigt binnen de tijd waarin de blokkade geldig is (deze waarde is verkregen in stap 3), minus nog een korte tijd (slechts enkele milliseconden, om de tijdsafwijking tussen processen te compenseren).

Meer over dergelijke systemen, die afwijking in tijdsynchronisatie vereisen, staat in het volgende interessante artikel: Leases: een efficiënt fouttolerant mechanisme voor consistente distributie van bestandscache.

Herhaal poging bij mislukking

Wanneer de cliënt er niet in slaagt de blokkade te verkrijgen, moet hij opnieuw proberen dit te doen, met een willekeurige vertraging; dit is gedaan om de synchronisatie tussen meerdere cliënten die tegelijkertijd proberen dezelfde resource te blokkeren te verstoren (wat kan leiden tot een situatie van 'split-brain', waarin er geen winnaars zijn). Bovendien, hoe sneller de cliënt probeert de blokkade van de meeste Redis-instanties te verkrijgen, hoe kleiner het venster waarin een 'split-brain'-situatie kan ontstaan (en hoe minder herhaalpogingen nodig zijn). Daarom moet de cliënt in het ideale geval proberen tegelijkertijd SET-opdrachten naar N instanties te verzenden met behulp van multiplexing.

Het is belangrijk te benadrukken hoe cruciaal het is dat cliënten die er niet in slagen de meeste blokkades te verkrijgen, (deels) verworven blokkades vrijgeven, zodat er niet gewacht hoeft te worden op het verlopen van de sleutel voordat de blokkade op de resource opnieuw kan worden verkregen (eigenlijk, als er netwerkaftakking optreedt en de cliënt verbinding verliest met de Redis-instanties, dan moet hij een prijs betalen voor het schenden van de beschikbaarheid terwijl hij wacht op het verlopen van de sleutel).

Blokkade vrijgeven

Blokkade vrijgeven is een eenvoudige operatie die alleen vereist dat alle instanties worden ontgrendeld, ongeacht of de cliënt denkt dat hij succesvol een specifieke instantie heeft geblokkeerd.

Veiligheidsoverwegingen

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

Laten we voor het begin aannemen dat de klant een blokkering over de meeste instanties heeft verkregen. Elke instantie bevat een sleutel met dezelfde levensduur voor allemaal. Echter, elke sleutel is op een ander moment ingesteld, waardoor hun vervaldatums op verschillende tijden verlopen. Maar als de eerste sleutel is ingesteld op een moment niet slechter dan T1 (de tijd die we kiezen vóór het contact met de eerste server), en de laatste sleutel is ingesteld op een moment niet slechter dan T2 (de tijd waarop we antwoord kregen van de laatste server), dan zijn we er zeker van dat de eerste sleutel in de set die zal vervallen, ten minste zal bestaan. MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Alle andere sleutels vervallen later, dus we kunnen er zeker van zijn dat alle sleutels tegelijkertijd geldig zullen zijn gedurende ten minste deze tijd.

Gedurende de tijd dat de meeste sleutels geldig blijven, kan een andere klant geen blokkering verwerven, omdat N/2+1 SET NX-actie niet succesvol kan eindigen als er al N/2+1 sleutels bestaan. Daarom, als de blokkering is verkregen, kan deze niet op hetzelfde moment opnieuw worden verkregen (dit zou de eigenschap van exclusiviteit schenden).
Echter, we willen ervoor zorgen dat meerdere klanten die tegelijkertijd proberen een blokkering te verkrijgen, niet allemaal succesvol kunnen zijn.

Als een klant de meeste instanties heeft geblokkeerd, waarbij hij daar ongeveer of meer tijd aan heeft besteed dan de maximale duur van de blokkering, zal hij de blokkering ongeldig verklaren en de instanties ontsluiten. Daarom moeten we alleen rekening houden met de gevallen waarin het de klant gelukt is om de meeste instanties te blokkeren in een tijd die korter is dan de vervaltijd. In dit geval, wat betreft het bovenstaande argument, gedurende de tijd. MIN_VALIDITY mag geen enkele klant in staat zijn om opnieuw een blokkering te verkrijgen. Daarom kunnen meerdere klanten N/2+1 instanties blokkeren in dezelfde tijd (die eindigt op het moment dat fase 2 is voltooid), alleen wanneer de tijd voor het blokkeren van de meerderheid langer is dan de TTL-tijd, waardoor de blokkering ongeldig wordt.

Kunt u een formeel bewijs van veiligheid geven, vergelijkbare algoritmen aanwijzen, of een bug in het bovenstaande vinden?

Overwegingen over beschikbaarheid

De beschikbaarheid van het systeem hangt af van drie hoofdeigenschappen:

1. Automatisch ontgrendelen (aangezien de sleutels verlopen): uiteindelijk zullen de sleutels weer beschikbaar zijn om te worden gebruikt voor ontgrendelingen.
2. Het feit dat klanten elkaar meestal helpen bij het ontgrendelen wanneer de benodigde ontgrendeling niet is aangeschaft, of wanneer deze wel is aangeschaft maar het werk is voltooid; daarom is het heel goed mogelijk dat we niet hoeven te wachten op het verstrijken van de sleutels om de ontgrendeling opnieuw aan te schaffen.
3. Het feit dat, wanneer een klant opnieuw een poging moet doen om een ontgrendeling te krijgen, hij relatief langer wacht dan de tijd die nodig is om de meeste ontgrendelingen aan te schaffen. Dit vermindert de kans op een opdeling in de besluitvorming bij concurrentie om middelen.

Echter, er is een straf voor de verminderde beschikbaarheid, gelijk aan de tijd TTL in de netwerksegmenten, dus als er continue segmenten zijn, kan deze straf een onbepaalde omvang aannemen. Dit gebeurt elke keer wanneer een klant een ontgrendeling verwerft en vervolgens in een ander segment wordt afgesneden voordat hij deze kan vrijgeven.

In principe, met onbeperkte continue netwerken, kan het systeem voor een oneindige periode niet beschikbaar zijn.

Prestaties, herstel na falen en fsync

Veel mensen gebruiken Redis omdat het vereist is om hoge serverprestaties voor ontgrendelingen te waarborgen, op het niveau van latencies die nodig zijn om ontgrendelingen te verkrijgen en vrij te geven, evenals het aantal van dergelijke verkrijgings/vrijgaven dat per seconde kan worden uitgevoerd. Om aan deze vereiste te voldoen, is er een communicatiestrategie met N Redis-servers om de latentie te verlagen. Dit is een multiplexingstrategie (of 'arme man's multiplexing', waarbij de socket in niet-blokkerende modus wordt gezet, alle commando's verzendt en commando's later leest, ervan uitgaande dat de omlooptijd tussen de cliënt en elk van de instanties vergelijkbaar is).

Het is echter ook belangrijk om rekening te houden met de overweging van langdurige gegevensopslag, als we een model willen creëren met gegarandeerd herstel na falen.

Laten we om de kwestie te verduidelijken aannemen dat we Redis configureren zonder langdurige gegevensopslag. De klant weet 3 van de 5 instanties te blokkeren. Een van de instanties die de klant kon blokkeren, wordt herstart en op dat moment ontstaan er opnieuw 3 instanties voor dezelfde bron die we kunnen blokkeren, en een andere klant kan op zijn beurt de herstartte instantie blokkeren, waardoor het beveiligingskenmerk van exclusiviteit van de blokkeringen in gevaar komt.

Als we de vooruitlopende gegevensopslag (AOF) inschakelen, verbetert de situatie enigszins. We kunnen bijvoorbeeld de server verhogen door het commando SHUTDOWN te verzenden en deze opnieuw te starten. Aangezien tijd in Redis semantisch zodanig is geïmplementeerd dat het doorgaat te verstrijken, ook wanneer de server is uitgeschakeld, zijn al onze vereisten in orde. Dit is in orde zolang een nette uitschakeling wordt gegarandeerd. Maar wat te doen bij stroomstoringen? Als Redis standaard is geconfigureerd met fsync-synchronisatie op de schijf elke seconde, is het mogelijk dat we onze sleutel na herstarten niet kunnen vinden. In theorie, als we de zekerheid van blokkades bij elke herstart van de instantie willen garanderen, moeten we fsync=always in de instellingen voor langdurige gegevensopslag. Dit zal de prestaties volledig verlammen, tot het niveau van dergelijke CP-systemen die traditioneel worden gebruikt voor de veilige implementatie van gedistribueerde blokkades.

Maar de situatie is beter dan het op het eerste gezicht lijkt. In principe blijft de veiligheid van het algoritme intact, aangezien wanneer een instantie opnieuw wordt opgestart na een fout, deze niet meer deelneemt aan een van de momenteel actieve blokkades.

Om dit te garanderen, hoeven we alleen maar ervoor te zorgen dat na een fout de instantie onbeschikbaar blijft gedurende een tijdsperiode die net iets langer is dan de maximale TTL die we gebruiken. Op deze manier wachten we tot de vervaldatum en de automatische vrijgave van alle sleutels die actief waren op het moment van de fout.

Met uitgestelde herstarts is het in principe mogelijk om veiligheid te bereiken, zelfs zonder enige langdurige opslag in Redis. We moeten echter opmerken dat dit kan resulteren in een boete wegens onbeschikbaarheid. Bijvoorbeeld, bij falen van de meeste instanties, zal het systeem wereldwijd onbeschikbaar zijn gedurende de TTL (en geen enkele bron kan in die tijd worden geblokkeerd).

Verhoog de beschikbaarheid van het algoritme: verleng de blokkade

Als het werk dat door klanten wordt uitgevoerd uit kleine stappen bestaat, is het mogelijk om de standaard geldigheidsduur van de blokkade te verkorten en een mechanisme voor het verlengen van blokkades te implementeren. In principe, als de klant bezig is met berekeningen en de waarde van de geldigheidsduur van de blokkade gevaarlijk laag wordt, kan hij alle instanties een Lua-script sturen dat de TTL van de sleutel verlengt, mits de sleutel nog steeds bestaat en de waarde nog steeds willekeurig is, verkregen tijdens het verwerven van de blokkade.

De klant moet de blokkade slechts als herwonnen beschouwen als het hem is gelukt om de meeste instanties te blokkeren binnen de geldigheidsduur.

Technisch gezien verandert het algoritme echter niet, dus het maximale aantal herhaalde pogingen om blokkades te verwerven moet beperkt zijn, anders zullen de eigenschappen van beschikbaarheid in het geding komen.

Bron: habr.com