ProHoster > Blog > Administrácia > Distribuované zámky s použitím Redis

Distribuované zámky s použitím Redis

Ahoj, Habr!

Dnes vám predstavujeme preklad zložitého článku o implementácii distribuovaných zámkov pomocou Redis a ponúkame diskusiu o perspektívach Redis ako témy. Analýza uvažovaného algoritmu Redlock od Martína Kleppmanna, autora knihy "Vysokonáročné aplikácie", je uvedená tu.

Distribuované zámky sú veľmi užitočný primitív, ktorý sa využíva v mnohých prostrediach, kde rôzne procesy musia pracovať so zdieľanými zdrojmi na princípe vzájomného vylúčenia.

Existuje niekoľko knižníc a článkov, ktoré popisujú, ako implementovať DLM (manažér distribuovaných zámkov) pomocou Redis, ale každá knižnica používa svoj vlastný prístup a poskytované záruky sú pomerne slabé v porovnaní s tým, čo je dosiahnuteľné pomocou o niečo zložitejšieho návrhu.

V tomto článku sa pokúsime opísať podmienečne kanonický algoritmus, ktorý demonštruje, ako implementovať distribuované zámky pomocou Redis. Budeme hovoriť o algoritme s názvom Redlock, ktorý implementuje manažér distribuovaných zámkov a preto je tento algoritmus podľa nášho názoru bezpečnejší ako bežný prístup s jedným inštancom. Dúfame, že ho komunita analyzuje, poskytne spätnú väzbu a stane sa východiskovým bodom pre implementáciu zložitejších alebo alternatívnych projektov.

Implementácie

Predtým, než prejdeme k opisu algoritmu, uvádzame niekoľko odkazov na už hotové implementácie. Tieto sa dajú použiť ako referencia.

Záruky bezpečnosti a dostupnosti

Chceme modelovať náš projekt s iba tromi vlastnosťami, ktoré podľa nás poskytujú minimálne záruky potrebné na efektívne využívanie distribuovaných zámkov.

  1. Vlastnosť bezpečnosti: Vzájomné vylúčenie. V danom okamihu môže iba jeden klient držať zámok.
  2. Vlastnosť dostupnosti A: Žiadne vzájomné zablokovanie. Nakoniec je možné vždy získať zámok, aj keď klient, ktorý zablokoval zdroj, zlyhá alebo sa dostane do iného segmentu disku.
  3. Vlastnosť dostupnosti B: Odolnosť voči zlyhaniu. Pokiaľ väčšina uzlov Redis funguje, klienti môžu získavať a uvoľňovať zámky.

Prečo implementácia založená na obnovení po zlyhaní nie je v tomto prípade dostatočná.
Aby sme pochopili, čo chceme zlepšiť, analyzujme súčasnú situáciu väčšiny knižníc pre distribuované zámky založené na Redis.

Najjednoduchší spôsob, ako zablokovať zdroj pomocou Redis, je vytvoriť kľúč v inštancii. Kľúč sa zvyčajne vytvára s obmedzenou životnosťou, čo sa dosahuje pomocou funkcie expires v Redis, takže tento kľúč sa skôr alebo neskôr uvoľní (vlastnosť 2 v našom zozname). Keď klient potrebuje uvoľniť zdroj, odstráni kľúč.

Na prvý pohľad toto riešenie celkom funguje, ale existuje problém: v našej architektúre vzniká jediný bod zlyhania. Čo sa stane, ak zlyhá hlavná inštancia Redis? Potom pridajme záložnú! A budeme ju používať, ak je hlavná nedostupná. Bohužiaľ, táto možnosť je neudržateľná. Týmto spôsobom nebudeme schopní správne implementovať vlastnosť vzájomného vylúčenia, ktorú potrebujeme na zabezpečenie, keďže replikácia v Redis je asynchrónna.

Je zrejmé, že v takejto modelovej situácii vzniká pretek.

  1. Klient A získava zámok na hlavnej.
  2. Hlavná zlyhá skôr, ako bude zápis do kľúča prenesený na záložnú.
  3. Záložná sa povyšuje na hlavnú.
  4. Klient B získava zámok toho istého zdroja, ktorý je už zablokovaný A. PORUŠENIE BEZPEČNOSTI!

Niekedy je úplne v poriadku, že v špeciálnych okolnostiach, ako je napríklad zlyhanie, môže množstvo klientov naraz získať zámok. V takýchto prípadoch je možné aplikovať riešenie založené na replikácii. V iných prípadoch odporúčame riešenie popísané v tomto článku.

Správna realizácia s jedným inštancom

Predtým, než sa pokúsime prekonať nevýhody konfigurácie s jedným inštancom, ako je uvedené vyššie, poďme si objasniť, ako správne postupovať v tomto jednoduchom prípade, pretože takéto riešenie je v skutočnosti prípustné v tých aplikáciách, kde sú závody občas prípustné, a tiež preto, že zámok na jednom inštanci slúži ako základ, ktorý sa používa v opísanom rozdelenom algoritme.

Aby sme získali zámok, postupujme takto:

SET resource_name my_random_value NX PX 30000

Tento príkaz nastaví kľúč, iba ak ešte neexistuje (možnosť NX), s dobou platnosti 30000 milisekúnd (možnosť PX). Pre kľúč je nastavená hodnota "myrandomvalue". Táto hodnota musí byť jedinečná v rámci všetkých klientov a všetkých požiadaviek na zámok.
V zásade sa náhodná hodnota používa na bezpečné uvoľnenie zámku pomocou skriptu, ktorý oznámi Redis: zmaž kľúč, iba ak existuje, a hodnota, ktorá je v ňom uložená – je skutočne tou, ktorú sme očakávali. To dosiahneme pomocou nasledujúceho skriptu v Lua:

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

Je dôležité, aby nedošlo k zrušeniu zámku, ktorý urobil iný klient. Napríklad klient môže získať zámok, potom sa zablokovať počas nejakého procesu, ktorý trvá dlhšie, ako je doba platnosti prvého zámku (tak, aby došlo k vypršaniu platnosti kľúča), a neskôr zrušiť zámok, ktorý nastavil nejaký iný klient.
Použiť jednoduché DEL nie je bezpečné, pretože klient môže odstrániť zámok, ktorý nastavil iný klient. Naopak, pri použití vyššie uvedeného skriptu je každý zámok „podpísaný“ náhodným reťazcom, preto ho môže zrušiť iba ten klient, ktorý ho predtým nastavil.

Aká by mala byť táto náhodná reťazec? Predpokladám, že by to malo byť 20 bajtov z /dev/urandom, ale môžeme nájsť aj menej nákladné spôsoby, ako vytvoriť reťazec dostatočne jedinečný na účely, ktoré pred vami stoja. Napríklad by bolo v poriadku posiať RC4 z /dev/urandom a potom na jeho základe vygenerovať pseudonáhodný tok. Jednoduchšie riešenie je spojené s kombináciou unixového času v mikrosekundovom rozlíšení plus ID klienta; nie je tak bezpečné, ale pravdepodobne zodpovedá úrovni úloh v väčšine kontextov.

Čas, ktorý používame ako ukazovateľ časovej platnosti kľúča, sa nazýva „časová platnosť blokovania“. Táto hodnota je zároveň termínom, po uplynutí ktorého sa blokovanie automaticky uvoľní, a časom, ktorý má klient na vykonanie operácie, skôr ako iný klient bude môcť blokovať tento zdroj, bez skutočného porušenia záruk vzájomného vylúčenia. Takáto záruka je obmedzená len na určené časové okno, ktoré začína od momentu získania blokovania.

Takže sme prediskutovali dobrý spôsob získania a uvoľnenia blokovania. Systém (ak hovoríme o nerestredenej sústave pozostávajúcej z jedného a vždy dostupného inštancie) je bezpečný. Poďme túto koncepciu rozšíriť na distribuovaný systém, kde takéto záruky nemáme.

Algoritmus Redlock

V distribuovanej verzii algoritmu sa predpokladá, že máme N vedúcich Redis. Tieto uzly sú úplne nezávislé od seba, preto nepoužívame replikáciu ani akýkoľvek iný implicitný systém koordinácie. Už sme vysvetlili, ako bezpečne získať a uvoľniť blokovanie na jedinom inštancii. Predpokladáme, že algoritmus pri práci s jednou inštanciou použije presne túto metódu. V našich príkladoch nastavujeme N na 5, čo je celkom rozumná hodnota. Takže potrebujeme použiť 5 vedúcich Redis na rôznych počítačoch alebo virtuálnych strojoch, aby sme zabezpečili, že budú fungovať väčšinou nezávisle od seba.

Aby získal blokovanie, klient vykoná nasledujúce operácie:

  1. Získa aktuálny čas v milisekundách.
  2. Postupne sa pokúša získať zámok na všetkých N inštanciách, pričom vo všetkých prípadoch používa rovnaké meno kľúča a náhodné hodnoty. V etape 2, pri nastavovaní zámku pre každú inštanciu, klient na jeho získanie používa oneskorenie, ktoré je dostatočne krátke v porovnaní s časom, po uplynutí ktorého sa zámok automaticky odoberie. Napríklad, ak trvanie zámku je 10 sekúnd, oneskorenie môže byť v rozsahu ~ 5-50 milisekúnd. Týmto sa vylučuje situácia, v ktorej by klient mohol dlho zostať zamknutý, pokúšajúc sa pripojiť k nefunkčnému uzlu Redis: ak je inštancia nedostupná, snažíme sa čo najskôr pripojiť k inej inštancii.
  3. Aby získal zámok, klient vypočíta, koľko času uplynulo; na to od aktuálneho časového hodnotenia odčíta časovú pečiatku, ktorú získal v kroku 1. Až keď sa klientovi podarí získať zámok na väčšine inštancií (minimálne 3) a celkový čas potrebný na získanie zámku je kratší ako čas trvania zámku, považuje sa to za úspešné získanie zámku.
  4. Ak bol zámok získaný, ako trvanie jeho platnosti sa považuje počiatočná hodnota trvania zámku mínus uplynulý čas, vypočítaný v kroku 3.
  5. Ak sa klientovi z nejakého dôvodu nepodarilo získať zámok (buď sa mu nepodarilo zamknúť N/2+1 inštancií, alebo čas trvania zámku sa ukázal ako záporný), pokúsi sa odblokovať všetky inštancie (aj tie, za ktoré sa predpokladalo, že ich nemôže zamknúť).

Je algoritmus asynchrónny?

Tento algoritmus vychádza z predpokladu, že hoci neexistujú synchronizované hodiny, podľa ktorých by všetky procesy pracovaly, miestny čas v každom procese stále plynie zhruba rovnakým tempom, a odchýlka je malá v porovnaní s celkovým časom, po ktorom sa zámok automaticky odoberie. Tento predpoklad veľmi pripomína situáciu typickú pre bežné počítače: na každom počítači sú lokálne hodiny a zvyčajne môžeme počítať s tým, že rozptyl času na rôznych počítačoch je malý.

V tejto fáze musíme presnejšie formulovať naše pravidlo vzájomného vylúčenia: vzájomné vylúčenie je zaručené iba za podmienky, že klient, ktorý drží zámok, ukončí svoju činnosť v čase, v ktorom zámok platí (táto hodnota bola získaná v kroku 3), mínus ešte nejaký čas (len niekoľko milisekúnd, aby kompenzoval časovú odchýlku medzi procesmi).

Podrobnejšie informácie o podobných systémoch, ktoré vyžadujú zladenie časových odchýlok, uvádza nasledujúci zaujímavý článok: Leases: efektívny mechanizmus odolný voči chybám pre konzistenciu distribuovanej cache súborov.

Opätovný pokus pri zlyhaní

Keď sa klientovi nepodarí získať zámok, mal by sa pokúsiť znova, pričom si počká náhodné oneskorenie; to sa robí s cieľom rozosynchronizovať množstvo klientov, ktorí sa zároveň pokúšajú získať zámok na rovnaký zdroj (čo môže viesť k situácii 'rozdeleného mozgu', v ktorej nie sú víťazi). Okrem toho, čím rýchlejšie sa klient pokúša získať zámok väčšiny inštancií Redis, tým menšie je okno, v ktorom môže vzniknúť situácia rozdeleného mozgu (a tým menej je potrebné opakovať pokusy). Preto by sa v ideálnom prípade mal klient pokúsiť súčasne poslať príkazy SET k N inštanciám použitím multiplexovania.

Je dôležité zdôrazniť, ako zásadné je, aby klienti, ktorí sa nedokázali získať väčšinu zámkov, uvoľnili (čiastočne) získané zámky, aby nemuseli čakať na vypršanie platnosti kľúča, skôr než sa zámok nad zdrojom opäť môže získať (pravda, ak dôjde k fragmentácii siete a klient stratí spojenie s inštanciami Redis, musí zaplatiť pokutu za porušenie dostupnosti, kým čaká na vypršanie platnosti kľúča).

Uvoľnenie zámku

Uvoľnenie zámku je jednoduchá operácia, ktorá si vyžaduje len odblokovať všetky inštancie, bez ohľadu na to, či sa klientovi zdá, že sa mu podarilo úspešne zablokovať konkrétnu inštanciu.

Bezpečnostné úvahy

Je algoritmus bezpečný? Poďme sa pokúsiť predstaviť, čo sa deje v rôznych scénarijoch.

Na začiatok predpokladajme, že klient dokázal získať blokáciu nad väčšinou inštancií. Každá z inštancií bude obsahovať kľúč s rovnakou dobou životnosti pre všetky. Avšak každý z týchto kľúčov bol nastavený v rôznom momente, a preto aj ich platnosť vyprší v rôznom čase. Ale, ak prvý kľúč bol nastavený v čase nie horšom ako T1 (čas, ktorý volíme pred kontaktovaním prvého servera), a posledný kľúč bol nastavený v čase nie horšom ako T2 (čas, kedy sme dostali odpoveď od posledného servera), môžeme si byť istí, že prvý kľúč v množine, ktorého platnosť vyprší, prežije minimálne MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Všetky ostatné kľúče vypršia neskôr, takže si môžeme byť istí, že všetky kľúče budú súčasne platné aspoň po toto časové obdobie.

Počas času, keď väčšina kľúčov zostáva platná, iný klient nebude schopný získať blokáciu, pretože N/2+1 operácií SET NX nemôže skončiť úspechom, ak už existuje N/2+1 kľúčov. Preto, ak bola blokácia získaná, nie je možné ju získať znovu v tom istom momente (to by porušilo vlastnosť vzájomného vylúčenia).
Pravda je, že chceme zabezpečiť, aby množstvo klientov, ktorí sa snažia získať blokáciu súčasne, nemohlo naraz uspieť.

Ak klient zablokoval väčšinu inštancií a strávil na tom čas približne alebo viac, ako maximálna doba trvania blokácie, považoval by blokáciu za neplatnú a odblokoval by inštancie. Preto musíme zohľadniť len ten prípad, v ktorom sa klientovi podarilo zablokovať väčšinu inštancií za čas, ktorý je kratší ako doba platnosti. V tomto prípade, pokiaľ ide o vyššie uvedený argument, za čas MIN_VALIDITY žiadny klient by nemal byť schopný znovu získať blokáciu. Preto množstvo klientov môže zablokovať N/2+1 inštancií v rovnakom čase (ktoré končí v momente dokončenia fázy 2), iba ak čas pre blokovanie väčšiny bol dlhší, ako čas TTL, čo mení blokáciu na neplatnú.

Môžete poskytnúť formálne dôkazy o bezpečnosti, uviesť existujúce podobné algoritmy alebo nájsť chybu v uvedenom?

Úvahy o dostupnosti

Dostupnosť systému závisí od troch hlavných charakteristík:

  1. Automatické uvoľnenie blokovania (keďže platnosť kľúčov vyprší): v konečnom dôsledku budú kľúče znovu dostupné na použitie pre blokovania.
  2. Skutočnosť, že zákazníci si zvyčajne navzájom pomáhajú odstraňovaním blokád, ak nebolo zakúpené požadované blokovanie, alebo ak bolo zakúpené a práca sa ukončila; preto sa zdá pravdepodobné, že nebudeme musieť čakať na vypršanie kľúčov, aby sme si znovu zakúpili blokovanie.
  3. Skutočnosť, že keď zákazník potrebuje opäť skúsiť získať blokovanie, čaká relatívne dlhšie ako doba potrebná na získanie väčšiny blokovaní. To znižuje pravdepodobnosť vzniku situácie rozdeleného mozgu pri súťažení o zdroje.

Musíme však zaplatiť pokutu za zníženú dostupnosť, rovnakú ako čas TTL v segmentoch siete, a preto, ak existujú nepretržité segmenty, môže sa táto pokuta stať nejakou nepredvídateľnou veľkosťou. K tomu dochádza zakaždým, keď si zákazník zakúpi blokovanie a potom je odpojený do iného segmentu skôr, ako ho stihne uvoľniť.

V princípe, pri neobmedzených nepretržitých segmentoch siete môže systém zostať nedostupný počas neobmedzeného časového obdobia.

Výkon, obnova po zlyhaní a fsync

Mnohí používajú Redis, keďže je potrebné zabezpečiť vysoký výkon servera blokovaní na úrovni latencií potrebných na získavanie a uvoľňovanie blokovaní, ako aj množstva operácií takéhoto získavania/uvoľňovania, ktoré sa podarí vykonať za sekundu. Na splnenie tejto požiadavky existuje stratégia komunikácie s N servermi Redis na zníženie latencie. Ide o stratégiu multiplexovania (alebo „multiplexovanie chudobných“, pri ktorej sa socket nastaví do neblokujúceho režimu, odošle všetky príkazy a číta príkazy neskôr, pričom predpokladá, že obratový čas medzi klientom a každým z inštancií je podobný).

Pravdou je, že treba zohľadniť aj úvahu o dlhodobom uchovávaní údajov, ak sa snažíme vytvoriť model s istou obnovou po zlyhaní.

Aby sme problém objasnili, predpokladajme, že konfigujeme Redis bez trvalého ukladania dát. Klient dokáže uzamknúť 3 z 5 inštancií. Jedna z inštancií, ktorú sa klientovi podarilo uzamknúť, sa reštartuje, a v tomto momente vzniknú znova 3 inštancie pre jeden a ten istý zdroj, ktorý môžeme uzamknúť, a iný klient môže zase uzamknúť reštartovanú inštanciu, čím porušuje bezpečnostný vlastnosť, ktorá predpokladá exkluzivitu uzamknutí.

Ak zapneme predbežné ukladanie dát (AOF), situácia sa mierne zlepší. Napríklad, môžeme zvýšiť server, keď vydáme príkaz SHUTDOWN a reštartujeme ho. Keďže operácie vypršania v Redis sú semanticky implementované tak, že čas pokračuje aj počas vypnutia servera, s našimi požiadavkami je všetko v poriadku. Je to v poriadku, pokiaľ je zabezpečené riadne vypnutie. Ale čo robiť pri výpadkoch napájania? Ak je Redis nakonfigurovaný predvolene, so synchronizáciou fsync na disku každú sekundu, je možné, že po reštarte sa nebudeme môcť spoľahnúť na náš kľúč. Teoreticky, ak chceme zaručiť bezpečnosť uzamknutí pri každom reštarte inštancie, mali by sme zapnúť fsync=always v nastaveniach trvalého ukladania dát. To úplne zabije výkon, na úroveň takých CP systémov, ktoré sa tradične používajú na bezpečnú implementáciu distribuovaných uzamknutí.

Ale situácia je lepšia, než sa na prvý pohľad zdá. V podstate, bezpečnosť algoritmu zostáva zachovaná, pretože keď sa inštancia reštartuje po zlyhaní, už sa nezúčastňuje žiadneho uzamknutia, ktoré je práve aktívne.

Aby sme to zabezpečili, stačí zabezpečiť, aby po zlyhaní inštancia zostala nedostupná po dobu, ktorá mierne presahuje maximum TTL, ktoré používame. Takto vyčkáme na uplynutie platnosti a automatické uvoľnenie všetkých kľúčov, ktoré boli aktívne v momente zlyhania.

Používaním oneskorených reštartov je v zásade možné dosiahnuť bezpečnosť aj pri absencii akéhokoľvek dlhodobého uchovania v Redis. Treba však poznamenať, že to môže viesť k pokute za porušenie dostupnosti. Napríklad, pri zlyhaní väčšiny inštancií sa systém stane globálne nedostupným na čas TTL (a žiaden prostriedok nebude možné v tomto čase zablokovať).

Zvyšujeme dostupnosť algoritmu: predlžujeme blokáciu

Ak práca vykonávaná klientmi pozostáva z malých etáp, je možné skrátiť predvolené časové obdobie blokácie a realizovať mechanizmus predlžovania blokácií. V zásade, ak je klient zaneprázdnený výpočtami a hodnota doby platnosti blokácie nebezpečne klesá, je možné poslať všetkým inštanciám skript v Lua, ktorý predlžuje TTL kľúča, pokiaľ kľúč ešte existuje a jeho hodnota je naďalej náhodná, získaná pri nadobudnutí blokácie.

Klient by mal považovať blokáciu za opätovne nadobudnutú iba v prípade, že sa mu podarilo zablokovať väčšinu inštancií počas doby platnosti.

Pravda, technicky sa algoritmus pritom nemení, preto maximálny počet opakovaných pokusov o nadobudnutie blokácií by mal byť obmedzený, inak budú narušené vlastnosti dostupnosti.

Zdroj: habr.com

Kúpte si spoľahlivý hosting pre webové stránky s ochranou proti DDoS, VPS VDS servery 🔥 Kúpte si spoľahlivý hosting pre webové stránky s ochranou proti DDoS, VPS VDS servery | ProHoster