ProHoster > Blog > Administrácia > Distribuované uzamykanie pomocou Redis

Distribuované uzamykanie pomocou Redis

Čau Habr!

Dnes vám dávame do pozornosti preklad komplexného článku o implementácii distribuovaného uzamykania pomocou Redis a pozývame vás, aby ste hovorili o perspektívach Redis ako o téme. Analýza predmetného algoritmu Redlock od Martina Kleppmanna, autora knihy "Aplikácie s vysokým zaťažením“, dané tu.

Distribuované uzamykanie je veľmi užitočné primitívum používané v mnohých prostrediach, kde rôzne procesy musia fungovať na zdieľaných zdrojoch vzájomne sa vylučujúcim spôsobom.

Existuje množstvo knižníc a príspevkov, ktoré popisujú, ako implementovať DLM (Distributed Lock Manager) pomocou Redis, ale každá knižnica má iný prístup a záruky, ktoré poskytujú, sú dosť slabé v porovnaní s tým, čo sa dá dosiahnuť o niečo sofistikovanejším dizajnom.

V tomto článku sa pokúsime opísať podmienený kanonický algoritmus, ktorý demonštruje, ako implementovať distribuované uzamykanie pomocou Redis. Budeme hovoriť o algoritme tzv redlock, implementuje distribuovaného správcu zámkov a podľa nášho názoru je tento algoritmus bezpečnejší ako bežný jednoinštančný prístup. Dúfame, že ju komunita analyzuje, poskytne spätnú väzbu a použije ju ako východiskový bod pre komplexnejšie alebo alternatívne projekty.

Implementácia

Predtým, ako prejdeme k popisu algoritmu, poskytujeme niekoľko odkazov na hotové implementácie. Môžu byť použité ako referencia.

Záruky bezpečnosti a dostupnosti

Náš dizajn budeme modelovať len s tromi vlastnosťami, o ktorých si myslíme, že poskytujú minimálne záruky potrebné na efektívne využitie distribuovaného uzamykania.

  1. Zabezpečenie: Vzájomné vylúčenie. V každom danom čase môže zámok držať iba jeden klient.
  2. Dostupnosť Vlastnosť A: Žiadne uviaznutia. Vždy je možné nakoniec získať zámok, aj keď klient, ktorý uzamkol prostriedok, zlyhá alebo pristane na inom segmente disku.
  3. Dostupnosť Vlastnosť B: Odolnosť voči chybám. Pokiaľ je spustená väčšina uzlov Redis, klienti môžu získavať a uvoľňovať zámky.

Prečo implementácia založená na obnove zlyhania v tomto prípade nestačí
Aby sme pochopili, čo sa chystáme zlepšiť, analyzujme súčasný stav s väčšinou distribuovaných uzamykacích knižníc založených na Redis.

Najjednoduchším spôsobom uzamknutia prostriedku pomocou Redis je vytvorenie kľúča v inštancii. Kľúč sa zvyčajne vytvára s obmedzenou životnosťou, čo sa dosahuje pomocou funkcie expirácie poskytovanej v Redis, takže skôr či neskôr sa tento kľúč uvoľní (vlastnosť 2 v našom zozname). Keď klient potrebuje uvoľniť prostriedok, vymaže kľúč.

Na prvý pohľad toto riešenie funguje celkom dobre, no je tu problém: naša architektúra vytvára jediný bod zlyhania. Čo sa stane, ak hostiteľská inštancia Redis zlyhá? Pridajme teda otroka! A použijeme ho, ak je prezentér nedostupný. Bohužiaľ, táto možnosť nie je realizovateľná. Týmto spôsobom nebudeme môcť správne implementovať vlastnosť vzájomného vylúčenia, ktorú potrebujeme na zaistenie bezpečnosti, pretože replikácia v Redis je asynchrónna.

Je zrejmé, že v takomto modeli nastáva rasový stav:

  1. Klient A získa zámok na master.
  2. Master zlyhá skôr, ako sa zadanie kľúča prenesie na podriadený.
  3. Nasledovník je povýšený na vodcu.
  4. Klient B získa zámok na rovnakom zdroji, ktorý už A uzamkol. PORUŠENIE BEZPEČNOSTI!

Niekedy je úplne normálne, že za zvláštnych okolností, napríklad pri poruche, môže zámok podržať viacero klientov súčasne. V takýchto prípadoch možno použiť riešenie založené na replikácii. V opačnom prípade odporúčame riešenie opísané v tomto článku.

Správna implementácia s jedinou inštanciou

Predtým, ako sa pokúsime prekonať nedostatky konfigurácie s jednou inštanciou opísanú vyššie, pochopme, ako správne zvládnuť tento jednoduchý prípad, pretože toto riešenie je v skutočnosti platné v aplikáciách, kde je čas od času prijateľná podmienka pretekov, a tiež preto, že blokovanie na jediná inštancia slúži ako základ, ktorý sa používa v tu opísanom distribuovanom algoritme.

Ak chcete získať zámok, postupujte takto:

SET resource_name my_random_value NX PX 30000

Tento príkaz nainštaluje kľúč, iba ak ešte neexistuje (možnosť NX), s dobou platnosti 30000 XNUMX milisekúnd (možnosť PX). Kľúč je nastavený na „myrandomvalue" Táto hodnota musí byť jedinečná pre všetkých klientov a všetky požiadavky na uzamknutie.
V zásade sa na bezpečné uvoľnenie zámku používa náhodná hodnota, pričom skript hovorí Redis: kľúč odstráňte iba vtedy, ak existuje a hodnota v ňom uložená je presne taká, ako sa očakávalo. To sa dosiahne pomocou nasledujúceho skriptu Lua:

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

Je to dôležité, aby sa zabránilo odstráneniu zámku držaného iným klientom. Klient môže napríklad získať zámok, potom sa zamknúť pri nejakej operácii, ktorá trvá dlhšie ako prvý zámok (takže kľúč má čas vypršať) a neskôr odstrániť zámok, ktorý umiestnil iný klient.
Použitie jednoduchého DEL nie je bezpečné, pretože klient môže odstrániť zámok, ktorý drží iný klient. Naproti tomu pri použití vyššie uvedeného skriptu je každý zámok „podpísaný“ náhodným reťazcom, takže ho môže odstrániť iba klient, ktorý ho predtým umiestnil.

Aký by mal byť tento náhodný reťazec? Hádam by to malo byť 20 bajtov z /dev/urandom, ale môžete nájsť lacnejšie spôsoby, ako urobiť reťazec dostatočne jedinečným pre vaše účely. Napríklad by bolo v poriadku nasadiť RC4 pomocou /dev/urandom a potom z neho vygenerovať pseudonáhodný stream. Jednoduchšie riešenie zahŕňa kombináciu unixového času v mikrosekundovom rozlíšení plus ID klienta; nie je to také bezpečné, ale vo väčšine kontextov to pravdepodobne vyhovuje.

Čas, ktorý používame ako meradlo životnosti kľúča, sa nazýva „životnosť zámku“. Táto hodnota predstavuje čas pred automatickým uvoľnením zámku a čas, ktorý má klient na dokončenie operácie, kým iný klient môže zamknúť daný zdroj bez toho, aby skutočne porušil záruky vzájomného vylúčenia. Táto záruka je obmedzená len na určité časové okno, ktoré začína od momentu zakúpenia zámku.

Takže sme diskutovali o dobrom spôsobe získania a uvoľnenia zámku. Systém (ak hovoríme o nedistribuovanom systéme pozostávajúcom z jedinej a vždy dostupnej inštancie) je bezpečný. Rozšírme tento koncept na distribuovaný systém, kde takéto záruky nemáme.

Algoritmus redlock

Distribuovaná verzia algoritmu predpokladá, že máme N Redis masters. Tieto uzly sú na sebe úplne nezávislé, preto nepoužívame replikáciu ani iný implicitný koordinačný systém. Ako bezpečne získať a uvoľniť zámok na jednej inštancii sme už prebrali. Považujeme za samozrejmé, že algoritmus pri práci s jednou inštanciou bude používať presne túto metódu. V našich príkladoch sme N nastavili na 5, čo je primeraná hodnota. Preto budeme musieť použiť 5 masterov Redis na rôznych počítačoch alebo virtuálnych strojoch, aby sme zaistili, že budú fungovať do značnej miery nezávisle od seba.

Na získanie zámku klient vykoná nasledujúce operácie:

  1. Získa aktuálny čas v milisekundách.
  2. Postupne sa pokúsi získať zámok na všetkých N inštanciách pomocou rovnakého názvu kľúča a náhodných hodnôt vo všetkých prípadoch. V 2. fáze, keď klient nastaví zámok pre jednotlivé inštancie, klient použije oneskorenie na jeho získanie, ktoré je dostatočne krátke v porovnaní s časom, po ktorom sa zámok automaticky uvoľní. Napríklad, ak je trvanie blokovania 10 sekúnd, oneskorenie môže byť v rozsahu ~5-50 milisekúnd. Tým sa eliminuje situácia, v ktorej by klient mohol zostať zablokovaný po dlhú dobu pri pokuse o dosiahnutie neúspešného uzla Redis: ak je inštancia nedostupná, pokúsime sa čo najskôr pripojiť k inej inštancii.
  3. Na vykonanie zámku klient vypočíta, koľko času uplynulo; Za týmto účelom odpočíta od skutočnej časovej hodnoty časovú pečiatku získanú v kroku 1. Ak a len vtedy, ak klient dokázal získať zámok vo väčšine prípadov (aspoň 3), a celkový čas, ktorý trvalo získať zámok, kratší ako je trvanie uzamknutia, zámok sa považuje za získaný.
  4. Ak bol zámok získaný, trvanie uzamknutia sa považuje za pôvodné trvanie uzamknutia mínus uplynutý čas vypočítaný v kroku 3.
  5. Ak sa klientovi z nejakého dôvodu nepodarí získať zámok (buď nebol schopný uzamknúť N/2+1 inštancií, alebo trvanie uzamknutia bolo záporné), pokúsi sa odomknúť všetky inštancie (aj tie, o ktorých si myslel, že ich nemôže zablokovať ).

Je algoritmus asynchrónny?

Tento algoritmus je založený na predpoklade, že aj keď neexistujú žiadne synchronizované hodiny, na ktorých by fungovali všetky procesy, miestny čas v každom procese stále plynie približne rovnakým tempom a chyba je malá v porovnaní s celkovým časom, po ktorom je blokovanie automaticky uvoľnené. Tento predpoklad je veľmi podobný situácii typickej pre bežné počítače: každý počítač má lokálne hodiny a väčšinou môžeme počítať s tým, že časový rozdiel medzi rôznymi počítačmi je malý.

V tomto bode musíme dôkladnejšie formulovať naše pravidlo vzájomného vylúčenia: vzájomné vylúčenie je zaručené iba vtedy, ak klient, ktorý drží zámok, odíde počas doby platnosti zámku (táto hodnota sa získa v kroku 3), mínus nejaký ďalší čas (celkom niekoľko milisekúnd na kompenzáciu časového rozdielu medzi procesmi).

Nasledujúci zaujímavý článok hovorí viac o takýchto systémoch, ktoré vyžadujú koordináciu časových intervalov: Prenájom: efektívny mechanizmus odolný voči chybám pre konzistenciu distribuovanej vyrovnávacej pamäte súborov.

Skúste to znova pri zlyhaní

Keď sa klientovi nepodarí získať zámok, musí to skúsiť znova po náhodnom oneskorení; toto sa robí na desynchronizáciu viacerých klientov, ktorí sa pokúšajú získať zámok na rovnakom zdroji v rovnakom čase (čo môže viesť k situácii „rozštiepeného mozgu“, v ktorej nie sú žiadni víťazi). Navyše, čím rýchlejšie sa klient pokúsi získať zámok na väčšine inštancií Redis, tým užšie je okno, v ktorom môže nastať situácia rozštiepeného mozgu (a tým menšia je potreba opakovania). V ideálnom prípade by sa preto klient mal pokúsiť odoslať príkazy SET N inštanciám súčasne pomocou multiplexovania.

Tu je potrebné zdôrazniť, aké dôležité je, aby klienti, ktorým sa nepodarí získať väčšinu zámkov, uvoľnili (čiastočne) získané zámky, aby nemuseli čakať na vypršanie platnosti kľúča, kým bude možné zámok na zdroji znova získať. (aj keď ak dôjde k fragmentácii siete a klient stratí kontakt s inštanciami Redis, musíte zaplatiť pokutu za dostupnosť počas čakania na vypršanie platnosti kľúča).

Uvoľnite zámok

Uvoľnenie zámku je jednoduchá operácia, ktorá jednoducho vyžaduje odomknutie všetkých inštancií bez ohľadu na to, či sa zdá, že klient úspešne uzamkol konkrétnu inštanciu.

Úvahy o bezpečnosti

Je algoritmus bezpečný? Skúsme si predstaviť, čo sa deje v rôznych scenároch.

Na začiatok predpokladajme, že klient bol schopný získať zámok na väčšine inštancií. Každá inštancia bude obsahovať kľúč s rovnakou životnosťou pre všetky. Každý z týchto kľúčov bol však nainštalovaný v inom čase, takže ich platnosť vyprší v rôznych časoch. Ak však bol prvý kľúč nainštalovaný v čase, ktorý nie je horší ako T1 (čas, ktorý si zvolíme pred kontaktovaním prvého servera) a posledný kľúč bol nainštalovaný v čase, ktorý nie je horší ako T2 (čas, v ktorom bola prijatá odpoveď z posledného servera), potom sme si istí, že prežije aspoň prvý kľúč v súprave, ktorému vyprší platnosť MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Platnosť všetkých ostatných kľúčov vyprší neskôr, takže si môžeme byť istí, že všetky kľúče budú súčasne platné minimálne tento čas.

Počas doby, počas ktorej zostáva väčšina kľúčov v platnosti, iný klient nebude môcť získať zámok, pretože operácie N/2+1 SET NX nemôžu byť úspešné, ak už existujú kľúče N/2+1. Po nadobudnutí zámku preto nie je možné ho znova nadobudnúť v tom istom okamihu (tým by došlo k porušeniu vlastnosti vzájomného vylúčenia).
Chceme sa však uistiť, že viacerí klienti, ktorí sa snažia získať zámok súčasne, nemôžu súčasne uspieť.

Ak klient uzamkol väčšinu inštancií na približne alebo viac ako maximálne trvanie uzamknutia, bude považovať zámok za neplatný a inštancie odomkne. Do úvahy teda musíme brať len prípad, kedy sa klientovi podarilo zablokovať väčšinu inštancií v čase kratšom, ako je dátum vypršania platnosti. V tomto prípade, čo sa týka vyššie uvedeného argumentu, počas doby MIN_VALIDITY žiadny klient by nemal byť schopný znova získať zámok. Preto mnohí klienti budú môcť uzamknúť inštancie N/2+1 v rovnakom čase (ktorý sa končí na konci fázy 2) iba vtedy, keď čas na uzamknutie väčšiny bol väčší ako čas TTL, čo robí zámok neplatným.

Môžete poskytnúť formálny dôkaz o bezpečnosti, uviesť existujúce podobné algoritmy alebo nájsť chybu vo vyššie uvedenom?

Úvahy o dostupnosti

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

  1. Automaticky uvoľniť zámky (keď sa skončí platnosť kľúčov): Kľúče budú nakoniec opäť k dispozícii na použitie na zámky.
  2. Skutočnosť, že klienti si zvyčajne navzájom pomáhajú odstránením zámkov, keď požadovaný zámok nebol získaný alebo bol získaný a práca bola dokončená; takže je pravdepodobné, že nebudeme musieť čakať na vypršanie platnosti kľúčov, aby sme znova získali zámok.
  3. Skutočnosť, že keď sa klient potrebuje znova pokúsiť získať zámok, čaká porovnateľne dlhší čas, než je obdobie potrebné na získanie väčšiny zámkov. Znižuje sa tým pravdepodobnosť, že pri súperení o zdroje nastane rozštiepený mozog.

Existuje však penalizácia za dostupnosť rovnajúca sa TTL segmentov siete, takže ak existujú susediace segmenty, penalizácia môže byť neobmedzená. K tomu dochádza vždy, keď klient získa zámok a potom sa odtrhne od iného segmentu skôr, ako ho môže uvoľniť.

V zásade, vzhľadom na nekonečné súvislé segmenty siete, systém môže zostať nedostupný počas nekonečného časového obdobia.

Výkon, failover a fsync

Mnoho ľudí používa Redis, pretože potrebujú vysoký výkon servera zámkov z hľadiska latencie potrebnej na získanie a uvoľnenie zámkov a počtu akvizícií/uvoľnení, ktoré je možné dokončiť za sekundu. Na splnenie tejto požiadavky existuje stratégia komunikácie so servermi N Redis na zníženie latencie. Toto je stratégia multiplexovania (alebo „multiplexovanie chudáka“, kde je zásuvka uvedená do neblokovacieho režimu, odosiela všetky príkazy a číta príkazy neskôr, za predpokladu, že doba obehu medzi klientom a každou inštanciou je podobná) .

Musíme však brať do úvahy aj úvahy spojené s dlhodobým ukladaním dát, ak sa snažíme vytvoriť model so spoľahlivou obnovou po zlyhaní.

V zásade, aby sme problém objasnili, predpokladajme, že nakonfigurujeme Redis bez dlhodobého ukladania údajov. Klientovi sa podarí zablokovať 3 z 5 inštancií. Jedna z inštancií, ktoré sa klientovi podarilo zablokovať, sa reštartuje a v tomto momente existujú opäť 3 inštancie pre ten istý zdroj, ktoré môžeme zablokovať, a ďalší klient zase môže zablokovať reštartovanú inštanciu, čím poruší bezpečnostnú vlastnosť, ktorá predpokladá exkluzivitu zámkov.

Ak povolíte dáta dopredu (AOF), situácia sa mierne zlepší. Server môžete povýšiť napríklad odoslaním príkazu SHUTDOWN a jeho reštartovaním. Keďže operácie vypršania platnosti v Redis sú sémanticky implementované tak, že čas plynie aj vtedy, keď je server vypnutý, všetky naše požiadavky sú v poriadku. To je normálne, pokiaľ je zabezpečené normálne vypnutie. Čo robiť v prípade výpadku prúdu? Ak je Redis predvolene nakonfigurovaný, pričom fsync sa synchronizuje na disku každú sekundu, potom je možné, že po reštarte nebudeme mať náš kľúč. Teoreticky, ak chceme zaručiť bezpečnosť zámku počas reštartu akejkoľvek inštancie, mali by sme povoliť fsync=always v nastaveniach pre dlhodobé ukladanie dát. Toto úplne zabije výkon až na úroveň systémov CP, ktoré sa tradične používajú na bezpečnú implementáciu distribuovaných zámkov.

Situácia je však lepšia, ako sa na prvý pohľad zdá. V zásade je bezpečnosť algoritmu zachovaná, pretože pri reštartovaní inštancie po zlyhaní sa už nezúčastňuje žiadneho aktuálne aktívneho zámku.

Aby sme to zaistili, musíme sa uistiť, že po zlyhaní zostane inštancia nedostupná po dobu mierne presahujúcu maximálne TTL, ktoré používame. Takto počkáme do dátumu expirácie a automatického uvoľnenia všetkých kľúčov, ktoré boli v čase poruchy aktívne.

Pomocou oneskorených reštartov je v zásade možné dosiahnuť bezpečnosť aj pri absencii akéhokoľvek dlhodobého pretrvávania v Redis. Upozorňujeme však, že to môže viesť k pokute za porušenie prístupnosti. Napríklad, ak väčšina inštancií zlyhá, systém sa stane globálne nedostupným pre TTL (a počas tejto doby nemôže byť zablokovaný žiadny zdroj).

Zvyšujeme dostupnosť algoritmu: rozširujeme blokovanie

Ak práca vykonávaná klientmi pozostáva z malých krokov, je možné skrátiť predvolené trvanie zámku a implementovať mechanizmus na predĺženie zámkov. V zásade platí, že ak je klient zaneprázdnený výpočtom a hodnota uplynutia platnosti zámku je nebezpečne nízka, môžete všetkým inštanciám poslať Lua skript, ktorý predĺži TTL kľúča, ak kľúč stále existuje a jeho hodnota je stále náhodná hodnota získaná pri zámok bol získaný.

Klient by mal zvážiť opätovné získanie zámku iba vtedy, ak sa mu podarilo uzamknúť väčšinu inštancií počas doby platnosti.

Je pravda, že technicky sa algoritmus nemení, takže maximálny počet opakovaných pokusov o získanie zámkov musí byť obmedzený, inak budú narušené vlastnosti prístupnosti.

Zdroj: hab.com

Pridať komentár