Distribuerad låsning med Redis

Hej Habr!

Idag uppmärksammar vi en översättning av en komplex artikel om implementeringen av distribuerad låsning med Redis och inbjuder dig att prata om utsikterna för Redis som ett ämne. Analys av Redlock-algoritmen i fråga från Martin Kleppmann, författare till boken "Högbelastningsapplikationer", givet här.

Distribuerad låsning är en mycket användbar primitiv som används i många miljöer där olika processer måste arbeta på delade resurser på ett ömsesidigt uteslutande sätt.

Det finns ett antal bibliotek och inlägg där ute som beskriver hur man implementerar DLM (Distributed Lock Manager) med Redis, men varje bibliotek har olika tillvägagångssätt och garantierna de ger är ganska svaga jämfört med vad som är möjligt med lite mer sofistikerad design.

I den här artikeln kommer vi att försöka beskriva en villkorad kanonisk algoritm som visar hur man implementerar distribuerad låsning med Redis. Vi ska prata om en algoritm som heter redlock, implementerar den en distribuerad låshanterare och, enligt vår åsikt, är denna algoritm säkrare än den vanliga engångsmetoden. Vi hoppas att samhället kommer att analysera det, ge feedback och använda det som utgångspunkt för mer komplexa eller alternativa projekt.

Genomförande

Innan vi går vidare till beskrivningen av algoritmen tillhandahåller vi flera länkar till färdiga implementeringar. De kan användas som referens.

• Redlock-rb (implementering för Ruby). Det finns också gaffel Redlock-rb, som lägger till ett paket (pärla) för enkel distribution, och inte bara för det.
• Redlock-py (Python-implementering).
• Aioredlock (implementering för Asyncio Python).
• Redlock-php (implementering för PHP).
• PHPRedisMutex (en annan implementering för PHP)
• cheprasov/php-redis-lock (PHP-bibliotek för lås)
• Redsync (implementering för Go).
• Redisson (implementering för Java).
• Redis::DistLock (implementering för Perl).
• Redlock-cpp (implementering för C++).
• Redlock-cs (implementering för C#/.NET).
• RedLock.net (implementering för C#/.NET). Med stöd för asynkron- och låstillägg.
• ScarletLock (implementering för C# .NET med konfigurerbart datalager)
• Redlock4Net (implementering för C# .NET)
• nod-redlock (implementering för NodeJS). Inkluderar stöd för förlängning av lås.

Säkerhet och tillgänglighetsgarantier

Vi kommer att modellera vår design med bara tre egenskaper som vi tror ger de minsta garantier som krävs för att effektivt använda distribuerad låsning.

1. Säkerhetsegendom: Ömsesidig uteslutning. Vid varje given tidpunkt kan endast en klient hålla låset.
2. Tillgänglighet Egenskap A: Inga låsningar. Det är alltid möjligt att så småningom skaffa ett lås, även om klienten som låste resursen misslyckas eller landar på ett annat disksegment.
3. Tillgänglighet Egenskap B: Feltolerans. Så länge som majoriteten av Redis-noderna är igång kan klienter skaffa och släppa lås.

Varför implementering baserat på felåterställning inte räcker i det här fallet
För att förstå vad vi ska förbättra, låt oss analysera det aktuella läget med de flesta distribuerade låsbibliotek baserade på Redis.

Det enklaste sättet att låsa en resurs med Redis är att skapa en nyckel i instansen. Vanligtvis skapas en nyckel med en begränsad livslängd, detta uppnås med hjälp av expires-funktionen i Redis, så förr eller senare släpps denna nyckel (egenskap 2 i vår lista). När klienten behöver släppa resursen tar den bort nyckeln.

Vid första anblicken fungerar den här lösningen ganska bra, men det finns ett problem: vår arkitektur skapar en enda punkt av misslyckande. Vad händer om värdens Redis-instans misslyckas? Låt oss lägga till en slav då! Och vi kommer att använda den om presentatören inte är tillgänglig. Tyvärr är det här alternativet inte genomförbart. Genom att göra detta kommer vi inte att kunna implementera den ömsesidiga uteslutningsegenskapen som vi behöver för att säkerställa säkerheten, eftersom replikering i Redis är asynkron.

Uppenbarligen uppstår ett rastillstånd i en sådan modell:

1. Klient A skaffar ett lås på mastern.
2. Mastern misslyckas innan nyckelinmatningen överförs till slaven.
3. Följaren befordras till ledare.
4. Klient B skaffar ett lås på samma resurs som A redan har låst. SÄKERHETSKROTT!

Ibland är det helt normalt att många klienter kan hålla i låset samtidigt under speciella omständigheter, till exempel ett fel. I sådana fall kan en replikeringsbaserad lösning användas. Annars rekommenderar vi lösningen som beskrivs i den här artikeln.

Korrekt implementering med en enda instans

Innan vi försöker övervinna bristerna med konfigurationen för en instans som beskrivs ovan, låt oss förstå hur man korrekt hanterar detta enkla fall, eftersom den här lösningen faktiskt är giltig i applikationer där ett tävlingstillstånd är acceptabelt från tid till annan, och även eftersom blockering på en enskild instans fungerar som basen som används i den distribuerade algoritmen som beskrivs här.

För att skaffa ett lås, gör så här:

SET resource_name my_random_value NX PX 30000

Detta kommando installerar en nyckel endast om den inte redan finns (NX-alternativ), med en giltighetstid på 30000 XNUMX millisekunder (PX-alternativ). Nyckeln är inställd på "myrandomvalue" Detta värde måste vara unikt för alla klienter och alla låsförfrågningar.
I grund och botten används ett slumpmässigt värde för att säkert frigöra låset, med ett skript som säger till Redis: ta bara bort nyckeln om den finns och värdet som lagras i det är exakt vad som förväntades. Detta uppnås med hjälp av följande Lua-skript:

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

Detta är viktigt för att förhindra att ett lås som innehas av en annan klient tas bort. Till exempel kan en klient skaffa ett lås, sedan bli låst i någon operation som varar längre än det första låset (så att nyckeln hinner gå ut) och senare ta bort låset som någon annan klient hade placerat.
Att använda en enkel DEL är osäker eftersom en klient kan ta bort ett lås som innehas av en annan klient. Däremot, när du använder skriptet ovan, "signeras" varje lås med en slumpmässig sträng, så bara klienten som tidigare placerat det kan ta bort det.

Vad ska denna slumpmässiga sträng vara? Jag antar att det borde vara 20 byte från /dev/urandom, men du kan hitta billigare sätt att göra strängen tillräckligt unik för dina syften. Till exempel skulle det vara bra att seed RC4 med /dev/urandom och sedan generera en pseudoslumpmässig ström från den. En enklare lösning innebär en kombination av unix-tid i mikrosekundsupplösning plus klient-ID; det är inte lika säkert, men det är nog upp till uppgiften i de flesta sammanhang.

Den tid vi använder som mått på nyckelns livslängd kallas "låsets livslängd". Detta värde är både hur lång tid innan låset släpps automatiskt och hur lång tid en klient har på sig att slutföra en operation innan en annan klient i sin tur kan låsa den resursen, utan att faktiskt bryta mot ömsesidiga uteslutningsgarantier. Denna garanti är begränsad endast till en viss tidsperiod, som börjar från det ögonblick som låset köps.

Så vi har diskuterat ett bra sätt att skaffa och släppa ett lås. Systemet (om vi pratar om ett icke-distribuerat system som består av en enda och alltid tillgänglig instans) är säkert. Låt oss utöka detta koncept till ett distribuerat system, där vi inte har några sådana garantier.

Redlock-algoritm

Den distribuerade versionen av algoritmen antar att vi har N Redis-mästare. Dessa noder är helt oberoende av varandra, så vi använder inte replikering eller något annat implicit koordinationssystem. Vi har redan tagit upp hur man säkert skaffar och frigör ett lås på en enskild instans. Vi tar för givet att algoritmen, när man arbetar med en enda instans, kommer att använda exakt denna metod. I våra exempel sätter vi N till 5, vilket är ett rimligt värde. Således kommer vi att behöva använda 5 Redis-masters på olika datorer eller virtuella maskiner för att säkerställa att de agerar i stort sett oberoende av varandra.

För att skaffa ett lås utför klienten följande operationer:

1. Hämtar aktuell tid i millisekunder.
2. Försöker sekventiellt att få ett lås på alla N instanser, med samma nyckelnamn och slumpmässiga värden i alla fall. I steg 2, när klienten sätter upp ett lås per instans, använder klienten en fördröjning för att skaffa det som är tillräckligt kort jämfört med den tid efter vilken låset automatiskt släpps. Till exempel, om blockeringens varaktighet är 10 sekunder, kan fördröjningen vara i intervallet ~5-50 millisekunder. Detta eliminerar situationen där klienten kan förbli blockerad under lång tid när han försöker nå en misslyckad Redis-nod: om instansen inte är tillgänglig försöker vi ansluta till en annan instans så snart som möjligt.
3. För att ta ett lås räknar klienten ut hur lång tid som har förflutit; För att göra detta subtraherar den från det faktiska tidsvärdet tidsstämpeln som erhölls i steg 1. Om och endast om klienten kunde erhålla låset på de flesta instanser (minst 3), och den totala tiden det tog att skaffa låset, mindre än låstiden, anses låset ha erhållits.
4. Om ett lås har förvärvats, anses låstiden vara den ursprungliga låstiden minus den förflutna tiden som beräknats i steg 3.
5. Om klienten misslyckas med att få låset av någon anledning (antingen kunde den inte låsa N/2+1-instanser eller låstiden var negativ), kommer den att försöka låsa upp alla instanser (även de som den trodde att den inte kunde blockera) ).

Är algoritmen asynkron?

Denna algoritm är baserad på antagandet att även om det inte finns någon synkroniserad klocka på vilken alla processer skulle fungera, flyter lokal tid i varje process fortfarande i ungefär samma takt, och felet är litet jämfört med den totala tiden efter vilken låset är släpps automatiskt. Detta antagande är mycket likt den situation som är typisk för vanliga datorer: varje dator har en lokal klocka, och vi kan vanligtvis räkna med att tidsskillnaden mellan olika datorer är liten.

Vid denna tidpunkt måste vi formulera vår ömsesidiga uteslutningsregel noggrannare: ömsesidig uteslutning garanteras endast om klienten som håller låset går ut under tiden som låset är giltigt (detta värde erhållits i steg 3), minus ytterligare tid (totalt några få millisekunder för att kompensera för tidsskillnaden mellan processer).

Följande intressanta artikel berättar mer om sådana system som kräver samordning av tidsintervall: Leasingavtal: en effektiv feltolerant mekanism för distribuerad filcachekonsistens.

Försök igen vid misslyckande

När en klient inte lyckas skaffa ett lås måste den försöka igen efter en slumpmässig fördröjning; detta görs för att avsynkronisera flera klienter som försöker skaffa ett lås på samma resurs samtidigt (vilket kan leda till en "split-brain"-situation där det inte finns några vinnare). Dessutom, ju snabbare en klient försöker få ett lås på en majoritet av Redis-instanserna, desto snävare fönster där en split-brain-situation kan uppstå (och desto mindre blir behovet av återförsök). Därför bör klienten helst försöka skicka SET-kommandon till N instanser samtidigt med multiplexering.

Det är värt att betona här hur viktigt det är för kunder som misslyckas med att skaffa majoriteten av låsen att frigöra de (delvis) förvärvade låsen, så att de inte behöver vänta på att nyckeln ska löpa ut innan låset på resursen kan skaffas igen (men om nätverksfragmentering inträffar och klienten förlorar kontakten med Redis-instanserna, måste du betala en tillgänglighetsstraff medan du väntar på att nyckeln ska upphöra att gälla).

Släpp låset

Att släppa ett lås är en enkel operation som helt enkelt kräver att alla instanser låses upp, oavsett om klienten verkar ha lyckats låsa en viss instans.

Säkerhetsöverväganden

Är algoritmen säker? Låt oss försöka föreställa oss vad som händer i olika scenarier.

Till att börja med, låt oss anta att klienten kunde få ett lås på de flesta fall. Varje instans kommer att innehålla en nyckel med samma livslängd för alla. Men var och en av dessa nycklar installerades vid olika tidpunkter, så de kommer att förfalla vid olika tidpunkter. Men om den första nyckeln installerades vid en tidpunkt som inte var sämre än T1 (den tid som vi väljer innan vi kontaktar den första servern), och den sista nyckeln installerades vid en tidpunkt som inte var sämre än T2 (den tidpunkt då svaret togs emot från den sista servern), så är vi säkra på att den första nyckeln i setet som löper ut kommer att överleva åtminstone MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Alla andra nycklar kommer att upphöra att gälla senare, så vi kan vara säkra på att alla nycklar kommer att vara giltiga samtidigt under åtminstone denna tid.

Under den tid som de flesta nycklar är giltiga kommer en annan klient inte att kunna förvärva låset, eftersom N/2+1 SET NX-operationer inte kan lyckas om N/2+1-nycklar redan finns. Därför, när ett lås har förvärvats, är det omöjligt att förvärva det igen i samma ögonblick (detta skulle bryta mot den ömsesidiga uteslutningsegenskapen).
Vi vill dock se till att flera klienter som försöker skaffa ett lås samtidigt inte kan lyckas samtidigt.

Om klienten har låst majoriteten av instanserna i ungefär eller mer än den maximala låstiden, kommer den att betrakta låset som ogiltigt och låsa upp instanserna. Därför behöver vi bara ta hänsyn till det fall där klienten lyckats blockera flertalet instanser på en kortare tid än utgångsdatumet. I det här fallet, angående ovanstående argument, under tiden MIN_VALIDITY ingen klient ska kunna återanskaffa låset. Därför kommer många klienter att kunna låsa N/2+1-instanser samtidigt (som slutar i slutet av steg 2) endast när tiden för att låsa majoriteten var längre än TTL-tiden, vilket gör låset ogiltigt.

Kan du tillhandahålla ett formellt säkerhetsbevis, ange befintliga liknande algoritmer eller hitta en bugg i ovanstående?

Tillgänglighetsöverväganden

Systemtillgänglighet beror på tre huvudegenskaper:

1. Frigör lås automatiskt (när nycklar upphör): Nycklar kommer så småningom att vara tillgängliga igen för att användas för lås.
2. Det faktum att klienter brukar hjälpa varandra genom att ta bort lås när det önskade låset inte har skaffats, eller har införskaffats och jobbet är klart; så det är troligt att vi inte behöver vänta på att nycklarna ska ta slut för att få tillbaka låset.
3. Det faktum att när en klient behöver försöka igen för att skaffa ett lås, väntar den i jämförelsevis längre tid än den tid som krävs för att skaffa de flesta lås. Detta minskar sannolikheten för att en split-brain-situation uppstår när man konkurrerar om resurser.

Det finns dock en tillgänglighetsstraff som är lika med TTL för nätverkssegmenten, så om det finns sammanhängande segment kan straffavgiften vara obestämd. Detta inträffar närhelst en klient skaffar ett lås och sedan river till ett annat segment innan det kan släppa det.

I princip, givet oändliga angränsande nätverkssegment, kan ett system förbli otillgängligt under en oändlig tidsperiod.

Prestanda, failover och fsync

Många använder Redis för att de behöver hög låsserverprestanda vad gäller den latens som krävs för att förvärva och släppa lås, och antalet förvärv/släpp som kan genomföras per sekund. För att möta detta krav finns det en strategi för att kommunicera med N Redis-servrar för att minska latensen. Detta är en multiplexeringsstrategi (eller "fattigmansmultiplexering", där socket sätts i icke-blockerande läge, skickar alla kommandon och läser kommandona senare, förutsatt att tiden för tur och retur mellan klienten och varje instans är liknande) .

Men vi måste också ta hänsyn till den hänsyn som är förknippad med långsiktig datalagring om vi strävar efter att skapa en modell med tillförlitlig återhämtning från fel.

I grund och botten, för att klargöra problemet, låt oss anta att vi konfigurerar Redis utan någon långvarig datalagring alls. Klienten lyckas blockera 3 av 5 instanser. En av instanserna som klienten lyckades blockera startas om, och i detta ögonblick finns det 3 instanser igen för samma resurs, som vi kan blockera, och en annan klient kan i sin tur blockera den omstartade instansen, vilket bryter mot säkerhetsegenskapen som förutsätter exklusivitet för lås.

Om du aktiverar data framåt (AOF) kommer situationen att förbättras något. Du kan till exempel marknadsföra en server genom att skicka kommandot SHUTDOWN och starta om den. Eftersom utgångsoperationer i Redis är semantiskt implementerade på ett sådant sätt att tiden fortsätter att flyta även när servern är avstängd, är alla våra krav bra. Detta är normalt så länge som en normal avstängning säkerställs. Vad ska man göra vid strömavbrott? Om Redis är konfigurerat som standard, med fsync som synkroniserar på disken varje sekund, är det möjligt att vi inte kommer att ha vår nyckel efter en omstart. Teoretiskt, om vi vill garantera låssäkerhet under en omstart av en instans, bör vi aktivera fsync=always i inställningarna för långtidslagring av data. Detta kommer att helt döda prestandan, ner till nivån för CP-system som traditionellt används för att säkert implementera distribuerade lås.

Men läget är bättre än det verkar vid första anblicken. I princip är säkerheten för algoritmen bevarad eftersom när instansen startas om efter ett misslyckande deltar den inte längre i något lås som för närvarande är aktivt.

För att säkerställa detta behöver vi bara se till att instansen efter ett misslyckande förblir otillgänglig under en tidsperiod som något överskrider den maximala TTL som vi använder. På så sätt kommer vi att vänta tills utgångsdatumet och automatiskt frisläppande av alla nycklar som var aktiva vid tidpunkten för felet.

Genom att använda fördröjda omstarter är det i princip möjligt att uppnå säkerhet även om det inte finns någon långvarig beständighet i Redis. Observera dock att detta kan ge böter för brott mot tillgängligheten. Till exempel, om majoriteten av instanserna misslyckas, kommer systemet att bli globalt otillgängligt för TTL (och ingen resurs kan blockeras under denna tid).

Vi ökar tillgängligheten för algoritmen: vi utökar blockeringen

Om arbetet som utförs av klienter består av små steg, är det möjligt att minska standardlåsets varaktighet och implementera en mekanism för att förlänga lås. I princip, om klienten är upptagen med datoranvändning och låsets utgångsvärde är farligt lågt, kan du skicka ett Lua-skript till alla instanser som utökar nyckelns TTL om nyckeln fortfarande finns och dess värde fortfarande är ett slumpmässigt värde som erhålls när lås införskaffades.

En klient bör endast överväga att ett lås ska återanskaffas om den har lyckats låsa de flesta instanser inom giltighetstiden.

Det är sant, tekniskt sett förändras inte algoritmen, så det maximala antalet upprepade försök att skaffa lås måste begränsas, annars kommer tillgänglighetsegenskaperna att kränkas.

Källa: will.com