Distribuerade lås med Redis

Hej, Habr!

Idag erbjuder vi er en översättning av en komplex artikel om implementering av distribuerade lås med hjälp av Redis och vi föreslår att diskutera Redis framtid som ämne. Analysen av den diskuterade algoritmen Redlock av Martin Kleppmann, författare till boken "Högbelastade applikationer", presenteras här.

Distribuerade lås är en mycket användbar primitiv, som tillämpas i många miljöer där olika processer måste arbeta med delade resurser på grundval av ömsesidig uteslutning.

Det finns flera bibliotek och inlägg som beskriver hur man implementerar DLM (manager för distribuerade lås) med hjälp av Redis, men varje bibliotek använder sig av sin egen metod, och de garantier som erbjuds är ganska svaga jämfört med vad som kan åstadkommas med en något mer komplex design.

I denna artikel ska vi försöka beskriva en så kallad kanonisk algoritm som demonstrerar hur man implementerar distribuerade lås med hjälp av Redis. Vi kommer att prata om algoritmen som kallas Redlock, som implementerar en manager för distribuerade lås och, enligt vår åsikt, är denna algoritm säkrare än den vanliga metoden med en enda instans. Vi hoppas att gemenskapen kommer att analysera den, ge feedback och börja använda den som en utgångspunkt för att implementera mer komplexa eller alternativa projekt.

Implementeringar

Innan vi går vidare till beskrivningen av algoritmen, låt oss ge några länkar till redan färdiga implementeringar. De kan användas som referens.

• Redlock-rb (implementering för Ruby). Det finns också fork Redlock-rb, som lägger till ett paket (gem) för att underlätta distributionen, och inte bara för detta.
• Redlock-py (implementering för Python).
• Aioredlock (implementering för Asyncio Python).
• Redlock-php (implementering för PHP).
• PHPRedisMutex (ännu en implementering för PHP)
• cheprasov/php-redis-lock (PHP-bibliotek för låsning)
• 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 async- och lock-tillägg.
• ScarletLock (implementering för C# .NET med konfigurerbart datalager)
• Redlock4Net (implementering för C# .NET)
• node-redlock (implementering för NodeJS). Inkluderar stöd för förlängning av lås.

Säkerhets- och tillgänglighetsgarantier

Vi planerar att modellera vårt projekt med bara tre egenskaper som vi anser ger de minimi garantier som krävs för effektiv användning av distribuerade lås.

1. Säkerhetsegenskap: Ömsesidigt uteslutande. Vid varje given tid kan endast en klient hålla ett lås.
2. Tillgänglighetsegenskap A: Frånvaro av dödlägen. I slutändan kan ett lås alltid förvärvas, även om klienten som låste resursen avbryter eller går in i ett annat disksegment.
3. Tillgänglighetsegenskap B: Felresilens. Så länge majoriteten av Redis-noderna är i drift, kan kunder förvärva och frigöra lås.

Varför är implementeringar baserade på återhämtning efter fel otillräckliga i detta fall?
För att förstå vad vi ska förbättra, låt oss analysera den nuvarande situationen kring de flesta biblioteken för distribuerade lås som är baserade på Redis.

Det enklaste sättet att låsa en resurs med Redis är att skapa en nyckel i instansen. Nyckeln skapas vanligtvis med en begränsad livslängd, vilket åstadkoms med Redis-funktionen expires, så småningom frigörs denna nyckel (egenskap 2 på vår lista). När kunden behöver frigöra resursen raderar de nyckeln.

Vid första anblick kan denna lösning tyckas fungera, men det finns ett problem: i vår arkitektur uppstår en enskild felpunkt. Vad händer om den ledande Redis-instansen går ner? Låt oss då lägga till en följdinstans! Och använda den om den ledande inte är tillgänglig. Tyvärr är detta alternativohållbart. Om vi gör så kan vi inte korrekt implementera den ömsesidiga uteslutningen, som vi behöver för att säkerställa säkerheten, eftersom replikationen i Redis är asynkron.

Det är uppenbart att en kapplöpningstillstånd uppstår i en sådan modell:

1. Klient A förvärvar låset på den ledande.
2. Den ledande går ner innan skrivningen av nyckeln överförs till följdinstansen.
3. Följdinstansen uppgraderas till ledande.
4. Klient B förvärvar låset på samma resurs som redan är låst av A. SÄKERHETSÖVERTRÄDELS!

Ibland är det helt okej att flera kunder kan hålla en lås samtidigt under speciella omständigheter, som vid ett fel. I sådana fall kan en lösning baserad på replikering tillämpas. I andra fall rekommenderar vi den lösning som beskrivs i denna artikel.

Korrekt implementering med en enda instans

Innan vi försöker övervinna begränsningarna av konfigurationen med en enda instans som beskrivits ovan, låt oss klargöra hur man agerar korrekt i detta enkla fall, eftersom en sådan lösning faktiskt är acceptabel i applikationer där race conditions ibland är tillåtna, och även eftersom låsningen på en enda instans är den grund som används i den distribuerade algoritm som beskrivs här.

För att erhålla en lås, gör följande:

SET resource_name my_random_value NX PX 30000

Detta kommando sätter nyckeln, endast om den än så länge inte existerar (NX-alternativet), med en livslängd på 30000 millisekunder (PX-alternativet). För nyckeln sätts värdet “myrandomvalue”. Detta värde måste vara unikt bland alla kunder och alla låsförfrågningar.
I princip används ett slumpmässigt värde för att säkert frigöra låsen, genom ett skript som meddelar Redis: ta bort nyckeln endast om den existerar, och värdet som sparats i den är precis det som förväntades. Detta uppnås via 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 låsningen tas bort av en annan kund. Till exempel kan en kund få en lås, sedan blockeras under en operation som tar längre tid än livslängden på den första låsningen (så att livslängden för nyckeln hinner löpa ut), och senare ta bort låsningen som en annan kund har ställt.
Att använda en enkel DEL är osäkert, eftersom en kund kan ta bort en lås som ställts av en annan kund. Däremot, vid användning av ovanstående skript, är varje lås "undertecknad" med en slumpmässig sträng, vilket gör att endast den kund som tidigare har ställt låset kan ta bort det.

Hur ska denna slumpmässiga sträng se ut? Jag tror att den borde bestå av 20 byte från /dev/urandom, men det finns också mindre kostsamma sätt att göra strängen tillräckligt unik för de syften ni har. Till exempel skulle det vara okej att säkra RC4 med /dev/urandom och sedan generera en pseudorandomström baserat på det. En enklare lösning är att kombinera unix-tid i mikrosekundsupplösning med kund-ID; det är inte lika säkert men kanske tillräckligt för de flesta sammanhang.

Tiden som vi använder som indikator på nyckelns livslängd kallas "låsets giltighetstid". Detta värde är både tidsgränsen efter vilken låset automatiskt kommer att frigöras, och tiden som kunden har på sig att genomföra operationen innan en annan kund kan blockera denna resurs utan att faktiskt bryta garantin för ömsesidig uteslutning. Sådan garanti är begränsad till ett visst tidsspann som börjar från det ögonblick låset erhålls.

Så vi har diskuterat ett bra sätt att förvärva och frigöra lås. Systemet (om vi talar om ett icke-distribuerat system med en enda och alltid tillgänglig instans) är säkert. Låt oss utvidga detta koncept till ett distribuerat system, där vi inte har sådana garantier.

Redlock-algoritmen

I den distribuerade versionen av algoritmen förutsätter vi att vi har N primära Redis. Dessa noder är helt oberoende av varandra, så vi använder inte replikering eller något annat underförstått koordineringssystem. Vi har redan förklarat hur man säkert kan förvärva och frigöra lås på en enda instans. Vi utgår från att algoritmen kommer att använda just denna metod när den arbetar med en enda instans. I våra exempel sätter vi N till 5, vilket är ett rimligt värde. Således behöver vi använda 5 primära Redis på olika datorer eller virtuella maskiner för att säkerställa att de fungerar i huvudsak oberoende av varandra.

För att förvärva ett lås utför kunden följande operationer:

1. Får den aktuella tiden i millisekunder.
2. Sekventiellt försöker klienten att erhålla låset på alla N-instansar, och använder samma nyckelnamn och slumpmässiga värden i alla fall. Vid steg 2, när låset sätts för varje instans, använder klienten en fördröjning som är ganska kort i förhållande till den tid efter vilken låset automatiskt tas bort. Till exempel, om låsets varaktighet är 10 sekunder, kan fördröjningen ligga i intervallet ~ 5-50 millisekunder. På så sätt undviks situationen där klienten kan förbli låst under en lång tid medan den försöker nå den misslyckade Redis-noden: om instansen inte är tillgänglig, försöker vi så snabbt som möjligt att ansluta till en annan instans.
3. För att ta låset beräknar klienten hur mycket tid som har gått; för detta subtraherar den den aktuella tidsstämpeln från den tidsstämpel som erhölls i steg 1. Låset anses vara erhållet först när klienten har fått låset på merparten av instanserna (minst 3) och den totala tid som det tog att få låset är mindre än låsets livslängd.
4. Om låset har erhållits, anses lånets varaktighet vara det ursprungliga lånets tidsvärde minus den tid som har passerat, beräknad i steg 3.
5. Om klienten av någon anledning inte lyckas få låset (antingen för att den inte kunde låsa N/2+1 instanser eller för att lånets livslängd visade sig vara negativ), kommer den att försöka låsa upp alla instanser (även de som den antogs inte kunna låsa).

Är algoritmen asynkron?

Denna algoritm baseras på antagandet att, även om det inte finns några synkroniserade klockor, som alla processer arbetar med, så flyter den lokala tiden i varje process ungefär i samma takt, och felmarginalen är liten i förhållande till den totala tiden efter vilken låset automatiskt tas bort. Detta antagande liknar situationen hos vanliga datorer: varje dator har lokala klockor och vanligtvis kan vi räkna med att tidsavvikelsen mellan olika datorer är liten.

I detta skede måste vi formulera vår regel om ömsesidig uteslutning mer noggrant: ömsesidig uteslutning garanteras endast om klienten som håller låset avslutar sitt arbete inom den tid som låset är giltigt (detta värde erhölls i steg 3), minus lite extra tid (bara några millisekunder för att kompensera för tidsavvikelsen mellan processerna).

Mer information om sådana system som kräver samordning av tidsavvikelser finns i följande intressanta artikel: Leases: a efficient fault-tolerant mechanism for distributed file cache consistency.

Återförsök vid fel

När klienten inte lyckas få ett lås bör den försöka igen efter att ha avvaktat en slumpmässig fördröjning; detta görs för att desynkronisera flera klienter som samtidigt försöker få låset på samma resurs (vilket kan leda till en situation med "split brain" där det inte finns några vinnare). Dessutom, ju snabbare klienten försöker att få lås på den största delen av Redis-instansarna, desto smalare blir fönstret där en situation med split brain kan uppstå (och desto mindre behov av återförsök). Därför bör klienten idealt försöka skicka SET-kommandon till N instanser samtidigt genom multiplexering.

Det är värt att betona hur viktigt det är att klienter som inte lyckats få de flesta låsen frigör (delvis) de lås de har fått, så att det inte behöver vänta på att nyckelns utgångstid ska gå ut innan låset på resursen åter kan erhållas (visserligen, om nätverket fragmenteras och klienten förlorar kontakten med Redis-instanserna, måste man betala ett pris för brott mot tillgängligheten medan man väntar på att nyckelns utgångstid ska gå ut).

Frigörande av lås

Frigörande av lås är en enkel operation som bara kräver att låset avlägsnas från alla instanser, oavsett om klienten anser att den har 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.

Låt oss först anta att klienten har lyckats få ett lås över de flesta instanser. Varje instans kommer att innehålla en nyckel med samma livstid för alla. Men varje nyckel ställdes in vid olika tidpunkter, så giltighetstiden för dem kommer att gå ut vid olika tillfällen. Men om den första nyckeln ställdes in vid en tidpunkt som inte är senare än T1 (tiden vi väljer före kontakten med den första servern), och den sista nyckeln ställdes in vid en tidpunkt som inte är senare än T2 (tiden då svaret från den senaste servern mottogs), så är vi säkra på att den första nyckeln i mängden som ska gå ut kommer att existera i minst MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Alla andra nycklar kommer att gå ut senare, så vi kan vara säkra på att alla nycklar kommer att vara giltiga samtidigt under åtminstone denna tid.

Under den tid då de flesta nycklar förblir giltiga kan en annan klient inte få ett lås, eftersom N/2+1 SET NX-operationer inte kan avslutas med framgång om det redan finns N/2+1 nycklar. Därför, om låset har förvärvats, är det omöjligt att återfå det vid samma tidpunkt (detta skulle bryta egenskapen av ömsesidig uteslutning).
Visserligen vill vi se till att en mängd klienter som samtidigt försöker få ett lås inte kan lyckas samtidigt.

Om klienten har låst de flesta instanser och lagt tid som är ungefär eller mer än den maximala låstillståndets varaktighet, så anser den låset ogiltigt och låser upp instanserna. Så vi måste ta hänsyn till det fall där klienten lyckades låsa de flesta instanser på en tid som är kortare än giltighetstiden. I det här fallet, avseende det ovanstående argumentet, under tiden MIN_VALIDITY bör ingen klient ha möjlighet att återfå ett lås. Så en mängd klienter kan låsa N/2+1 instanser på samma tid (vilken avslutas vid slutet av steg 2), endast när tiden för att låsa de flesta var längre än TTL-tiden, vilket gör låset ogiltigt.

Kan du ge ett formellt bevis på säkerhet, ange befintliga liknande algoritmer, eller hitta en bugg i det som har presenterats?

Tillgänglighet Överväganden

Systemets tillgänglighet beror på tre grundläggande egenskaper:

1. Automatisk avblockering (eftersom nycklarna går ut): i slutändan kommer nycklarna återigen att vara tillgängliga för att användas för blockeringar.
2. Det faktum att kunder vanligtvis hjälper varandra genom att ta bort blockeringar när den nödvändiga blockeringen inte har köpts, eller har köpts men arbetet har avslutats; därför är det mycket troligt att vi inte behöver vänta på att nycklarna ska gå ut för att återigen kunna köpa en blockering.
3. Det faktum att när en kund behöver försöka igen för att få en blockering, kan de behöva vänta en jämförelsevis längre tid än den tid som krävs för att köpa de flesta blockeringarna. Detta minskar risken för en delad hjärnsituation vid tävling om resurser.

Men det finns en straff för den minskade tillgängligheten, motsvarande TTL-tiden i nätverkssegment, så om det finns kontinuerliga segment, kan denna straff bli av obestämd storlek. Detta händer varje gång en kund köper en blockering, men sedan kopplas bort i ett annat segment innan de hinner frigöra den.

Principiellt, med ett oändligt antal kontinuerliga nätverkssegment, kan systemet förbli otillgängligt under en oändlig tidsperiod.

Prestanda, återhämtning från misslyckanden och fsync

Många använder Redis eftersom det krävs för att säkerställa hög prestanda för blockeringstjänser, på nivå med de latenser som krävs för att förvärva och frigöra blockeringar, samt antalet operationer för sådana förvärv/frigörningar som kan genomföras per sekund. För att uppfylla detta krav finns det en kommunikationsstrategi med N Redis-servrar för att minska latensen. Detta är en multiplexeringsstrategi (eller 'fattigmans multiplexering', där socket sätts i icke-blockerande läge, skickar alla kommandon och läser kommandona senare, under antagande att svarstiden mellan klienten och varje instans är liknande).

Sanningen är att man också måste beakta fråga om långsiktig datalagring om vi syftar på att skapa en modell med pålitlig återhämtning efter systemfel.

I princip, för att klargöra problemet, låt oss anta att vi konfigurerar Redis utan långsiktig datalagring. Klienten lyckas låsa 3 av 5 instanser. En av instanserna som klienten lyckats låsa startas om, och då uppstår återigen 3 instanser för samma resurs som vi kan låsa, och en annan klient kan i sin tur låsa den omstartade instansen, vilket bryter mot säkerhetsegenskapen som innebär exklusivitet i låsningen.

Om vi aktiverar förhandsbesparande av data (AOF) förbättras situationen något. Till exempel kan vi återstarta servern genom att skicka kommandot SHUTDOWN och sedan starta om den. Eftersom timeout-operatörer i Redis semantiskt implementeras på så sätt att tiden fortsätter att gå även när servern är avstängd, är allt okej med våra krav. Allt är okej så länge som en ordentlig avstängning sker. Men vad ska vi göra vid strömavbrott? Om Redis är konfigurerad som standard, med synkronisering av fsync på disken varje sekund, kan det hända att vi inte hittar vår nyckel efter omstart. Teoretiskt sett, om vi vill garantera säkerheten för lås vid varje omstart av instansen, måste vi aktivera fsync=always i inställningarna för långvarig datalagring. Detta kommer helt att döda prestandan, ner till nivån av sådana CP-system som traditionellt används för säker implementering av distribuerade lås.

Men situationen är bättre än den verkar vid första ögonkastet. I princip kvarstår säkerheten i algoritmen, eftersom när en instans startas om efter ett fel, deltar den inte längre i några lås som är aktiva för tillfället.

För att garantera detta behövs bara säkerställas att instansen förblir otillgänglig under en tid som något överstiger max TTL som vi använder. Då kommer vi att vänta på att tidsgränsen ska löpa ut och att alla nycklar som var aktiva vid tidpunkten för felet automatiskt ska frigöras.

Genom att använda fördröjda omstarter är det möjligt att uppnå säkerhet även utan någon långvarig lagring i Redis. Det bör dock noteras att detta kan leda till böter för otillgänglighet. Till exempel, när majoriteten av instanserna misslyckas, blir systemet globalt otillgängligt under TTL (och inga resurser kan låsas under denna tid).

Öka tillgängligheten för algoritmen: förläng låsningen

Om arbetet som utförs av kunderna består av små steg är det möjligt att korta ned den standardinställda låsningstiden och implementera en mekanism för förlängning av låsningar. I princip, om kunden är upptagen med beräkningar och låsningens giltighetstid riskerar att sänkas, kan ett Lua-skript skickas till alla instanser för att förlänga TTL för nyckeln, om nyckeln fortfarande existerar och dess värde fortfarande är slumpmässigt, vilket erhölls när låsningen förvärvades.

Kunden bör anse att låsningen har återförvärvats endast om hen har lyckats låsa majoriteten av instanserna under giltighetstiden.

Tekniskt sett förblir dock algoritmen oförändrad, så det maximala antalet försök att få låsningar bör begränsas, annars kommer tillgänglighetskraven att brytas.

Källa: habr.com