ProHoster > Blog > podávání > Distribuované zamykání pomocí Redis

Distribuované zamykání pomocí Redis

Čau Habr!

Dnes vám dáváme do pozornosti překlad komplexního článku o implementaci distribuovaného zamykání pomocí Redis a zveme vás k rozhovoru o perspektivách Redis jako tématu. Analýza příslušného algoritmu Redlock od Martina Kleppmanna, autora knihy "Aplikace s vysokým zatížením“, dáno zde.

Distribuované zamykání je velmi užitečné primitivum používané v mnoha prostředích, kde různé procesy musí fungovat na sdílených zdrojích vzájemně se vylučujícím způsobem.

Existuje řada knihoven a příspěvků, které popisují, jak implementovat DLM (Distributed Lock Manager) pomocí Redis, ale každá knihovna používá jiný přístup a záruky, které poskytují, jsou dost slabé ve srovnání s tím, co je dosažitelné s trochu sofistikovanějším designem.

V tomto článku se pokusíme popsat podmíněný kanonický algoritmus, který demonstruje, jak implementovat distribuované zamykání pomocí Redis. Budeme mluvit o algoritmu zvaném Redlock, implementuje distribuovaného správce zámků a podle našeho názoru je tento algoritmus bezpečnější než běžný jednoinstanční přístup. Doufáme, že ji komunita analyzuje, poskytne zpětnou vazbu a použije ji jako výchozí bod pro složitější nebo alternativní projekty.

Implementace

Než přejdeme k popisu algoritmu, poskytneme několik odkazů na hotové implementace. Mohou být použity jako reference.

Záruky bezpečnosti a dostupnosti

Náš návrh budeme modelovat pouze se třemi vlastnostmi, o kterých si myslíme, že poskytují minimální záruky potřebné pro efektivní využití distribuovaného zamykání.

  1. Bezpečnostní vlastnost: Vzájemné vyloučení. V každém okamžiku může zámek držet pouze jeden klient.
  2. Dostupnost Vlastnost A: Žádná uváznutí. Vždy je možné nakonec získat zámek, i když klient, který zamkl prostředek, selže nebo přistane na jiném segmentu disku.
  3. Availability Property B: Fault Tolerance. Dokud běží většina uzlů Redis, mohou klienti získávat a uvolňovat zámky.

Proč implementace založená na obnově selhání v tomto případě nestačí
Abychom pochopili, co se chystáme zlepšit, pojďme analyzovat současný stav s většinou distribuovaných zamykacích knihoven založených na Redis.

Nejjednodušší způsob, jak uzamknout prostředek pomocí Redis, je vytvořit klíč v instanci. Obvykle je klíč vytvořen s omezenou životností, toho je dosaženo pomocí funkce expirace poskytované v Redis, takže dříve nebo později je tento klíč uvolněn (vlastnost 2 v našem seznamu). Když klient potřebuje uvolnit prostředek, odstraní klíč.

Na první pohled toto řešení funguje docela dobře, ale je tu problém: naše architektura vytváří jediný bod selhání. Co se stane, když hostitelská instance Redis selže? Tak přidáme otroka! A použijeme ho, pokud je prezentér nedostupný. Bohužel tato možnost není schůdná. Tímto způsobem nebudeme schopni správně implementovat vlastnost vzájemného vyloučení, kterou potřebujeme k zajištění bezpečnosti, protože replikace v Redis je asynchronní.

Je zřejmé, že v takovém modelu nastává podmínka závodu:

  1. Klient A získá zámek na masteru.
  2. Master selže dříve, než je zadání klíče přeneseno na podřízené.
  3. Následovník je povýšen na vůdce.
  4. Klient B získá zámek na stejném prostředku, který A již uzamkl. PORUŠENÍ BEZPEČNOSTI!

Někdy je zcela normální, že za zvláštních okolností, jako je porucha, může zámek podržet mnoho klientů současně. V takových případech lze použít řešení založené na replikaci. V opačném případě doporučujeme řešení popsané v tomto článku.

Správná implementace s jedinou instancí

Než se pokusíme překonat nedostatky konfigurace jedné instance popsané výše, pochopme, jak správně zacházet s tímto jednoduchým případem, protože toto řešení je ve skutečnosti platné v aplikacích, kde je čas od času přijatelný spor, a také proto, že blokování na jediná instance slouží jako základ, který se používá v zde popsaném distribuovaném algoritmu.

Chcete-li získat zámek, postupujte takto:

SET resource_name my_random_value NX PX 30000

Tento příkaz nainstaluje klíč pouze v případě, že ještě neexistuje (volba NX), s dobou platnosti 30000 XNUMX milisekund (volba PX). Klíč je nastaven na „myrandomvalue" Tato hodnota musí být jedinečná pro všechny klienty a všechny požadavky na zámek.
V zásadě se k bezpečnému uvolnění zámku používá náhodná hodnota se skriptem, který říká Redis: klíč odstraňte, pouze pokud existuje a hodnota v něm uložená je přesně to, co se očekávalo. Toho je dosaženo pomocí následujícího skriptu Lua:

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

To je důležité, aby se zabránilo odstranění zámku drženého jiným klientem. Klient může například získat zámek, pak se zamknout při nějaké operaci, která trvá déle než první zámek (takže klíč má čas vypršet), a později odstranit zámek, který umístil nějaký jiný klient.
Použití jednoduchého DEL není bezpečné, protože klient může odstranit zámek držený jiným klientem. Naproti tomu při použití výše uvedeného skriptu je každý zámek „podepsán“ náhodným řetězcem, takže jej může odstranit pouze klient, který jej dříve umístil.

Jaký by měl být tento náhodný řetězec? Hádám, že by to mělo být 20 bajtů z /dev/urandom, ale můžete najít levnější způsoby, jak vytvořit řetězec dostatečně jedinečný pro vaše účely. Například by bylo v pořádku nasít RC4 pomocí /dev/urandom a poté z něj vygenerovat pseudonáhodný stream. Jednodušší řešení zahrnuje kombinaci unixového času v mikrosekundovém rozlišení plus ID klienta; není to tak bezpečné, ale ve většině kontextů to pravděpodobně odpovídá danému úkolu.

Doba, kterou používáme jako měřítko životnosti klíče, se nazývá „životnost zámku“. Tato hodnota je jak množství času před automatickým uvolněním zámku, tak množství času, který má klient na dokončení operace, než může jiný klient zase uzamknout daný zdroj, aniž by skutečně porušil záruky vzájemného vyloučení. Tato záruka je omezena pouze na určité časové okno, které začíná okamžikem zakoupení zámku.

Takže jsme probrali dobrý způsob, jak získat a uvolnit zámek. Systém (pokud mluvíme o nedistribuovaném systému skládajícím se z jediné a vždy dostupné instance) je bezpečný. Rozšiřme tento koncept na distribuovaný systém, kde žádné takové záruky nemáme.

Redlock algoritmus

Distribuovaná verze algoritmu předpokládá, že máme N Redis masters. Tyto uzly jsou na sobě zcela nezávislé, proto nepoužíváme replikaci ani žádný jiný implicitní koordinační systém. Jak bezpečně získat a uvolnit zámek na jedné instanci jsme již probrali. Považujeme za samozřejmé, že algoritmus při práci s jedinou instancí bude používat přesně tuto metodu. V našich příkladech nastavíme N na 5, což je rozumná hodnota. Budeme tedy muset použít 5 masterů Redis na různých počítačích nebo virtuálních strojích, abychom zajistili, že budou fungovat do značné míry nezávisle na sobě.

Chcete-li získat zámek, klient provede následující operace:

  1. Získá aktuální čas v milisekundách.
  2. Postupně se pokusí získat zámek na všech N instancích pomocí stejného názvu klíče a náhodných hodnot ve všech případech. Ve fázi 2, kdy klient nastavuje zámek pro každou instanci, klient používá k jeho získání zpoždění, které je dostatečně krátké v porovnání s časem, po kterém se zámek automaticky uvolní. Pokud je například doba blokování 10 sekund, může být zpoždění v rozsahu ~5-50 milisekund. To eliminuje situaci, kdy by klient mohl zůstat blokován po dlouhou dobu při pokusu o dosažení neúspěšného uzlu Redis: pokud je instance nedostupná, snažíme se co nejdříve připojit k jiné instanci.
  3. Chcete-li provést zámek, klient vypočítá, kolik času uplynulo; Za tímto účelem odečte od skutečné časové hodnoty časové razítko, které bylo získáno v kroku 1. Pokud a pouze v případě, že klient byl schopen získat zámek na většině instancí (alespoň 3), a celkový čas, který trvalo získat zámek, kratší než doba trvání zámku, zámek se považuje za získaný.
  4. Pokud byl získán zámek, doba trvání zámku se považuje za původní dobu trvání zámku mínus uplynulý čas vypočítaný v kroku 3.
  5. Pokud klient z nějakého důvodu nezíská zámek (buď nebyl schopen uzamknout N/2+1 instancí, nebo byla doba trvání zámku záporná), pokusí se odemknout všechny instance (i ty, o kterých si myslel, že je nemůže zablokovat ).

Je algoritmus asynchronní?

Tento algoritmus je založen na předpokladu, že ačkoli neexistují žádné synchronizované hodiny, na kterých by všechny procesy fungovaly, místní čas v každém procesu stále plyne přibližně stejným tempem a chyba je malá ve srovnání s celkovým časem, po kterém je zámek automaticky uvolněna. Tento předpoklad je velmi podobný situaci typické pro běžné počítače: každý počítač má lokální hodiny a většinou můžeme počítat s tím, že časový rozdíl mezi různými počítači je malý.

V tomto bodě musíme pečlivěji formulovat naše pravidlo vzájemného vyloučení: vzájemné vyloučení je zaručeno pouze v případě, že klient, který drží zámek, odejde během doby platnosti zámku (tato hodnota se získá v kroku 3), mínus nějaký další čas (celkem několik milisekundy pro kompenzaci časového rozdílu mezi procesy).

Následující zajímavý článek říká více o takových systémech, které vyžadují koordinaci časových intervalů: Pronájmy: účinný mechanismus odolný proti chybám pro konzistenci distribuované mezipaměti souborů.

Zkuste to znovu při selhání

Když se klientovi nepodaří získat zámek, musí to zkusit znovu po náhodném zpoždění; to se provádí za účelem desynchronizace více klientů, kteří se snaží získat zámek na stejném zdroji ve stejnou dobu (což může vést k situaci „rozděleného mozku“, ve které nejsou žádní vítězové). Navíc čím rychleji se klient pokusí získat zámek na většině instancí Redis, tím užší je okno, ve kterém může dojít k situaci rozděleného mozku (a tím menší je potřeba opakování). V ideálním případě by se tedy klient měl pokusit odeslat příkazy SET N instancím současně pomocí multiplexování.

Zde je vhodné zdůraznit, jak důležité je, aby klienti, kterým se nepodaří získat většinu zámků, uvolnili (částečně) získané zámky, aby nemuseli čekat na vypršení platnosti klíče, než bude možné zámek na zdroji znovu získat. (i když pokud dojde k fragmentaci sítě a klient ztratí kontakt s instancemi Redis, musíte během čekání na vypršení platnosti klíče zaplatit pokutu za dostupnost).

Uvolněte zámek

Uvolnění zámku je jednoduchá operace, která jednoduše vyžaduje odemknutí všech instancí bez ohledu na to, zda se zdá, že klient úspěšně uzamkl konkrétní instanci.

Bezpečnostní aspekty

Je algoritmus bezpečný? Zkusme si představit, co se děje v různých scénářích.

Pro začátek předpokládejme, že klient byl schopen získat zámek na většině instancí. Každá instance bude obsahovat klíč se stejnou životností pro všechny. Každý z těchto klíčů byl však nainstalován v jinou dobu, takže jejich platnost vyprší v jinou dobu. Pokud však byl první klíč nainstalován v době ne horší než T1 (čas, který zvolíme před kontaktováním prvního serveru) a poslední klíč byl nainstalován v době ne horší než T2 (čas, kdy byla přijata odpověď z posledního serveru), pak jsme si jisti, že první klíč v sadě, který vyprší, přežije minimálně MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Platnost všech ostatních klíčů vyprší později, takže si můžeme být jisti, že všechny klíče budou současně platné alespoň po tuto dobu.

Během doby, kdy zůstává většina klíčů v platnosti, nebude moci zámek získat jiný klient, protože operace N/2+1 SET NX nemohou být úspěšné, pokud již N/2+1 klíčů existuje. Jakmile je tedy zámek pořízen, není možné jej znovu nabýt ve stejném okamžiku (to by porušilo vlastnost vzájemného vyloučení).
Chceme však zajistit, aby více klientů pokoušejících se získat zámek současně nemohlo uspět ve stejnou dobu.

Pokud klient uzamkl většinu instancí na dobu přibližně nebo déle, než je maximální doba trvání zámku, bude považovat zámek za neplatný a instance odemkne. Musíme tedy vzít v úvahu pouze případ, kdy se klientovi podařilo zablokovat většinu instancí v době kratší, než je datum expirace. V tomto případě, pokud jde o výše uvedený argument, během doby MIN_VALIDITY žádný klient by neměl být schopen znovu získat zámek. Mnoho klientů tedy bude moci uzamknout instance N/2+1 ve stejnou dobu (která končí na konci fáze 2) pouze v případě, že čas k uzamčení většiny byl větší než čas TTL, což způsobí, že zámek bude neplatný.

Můžete poskytnout formální důkaz zabezpečení, uvést existující podobné algoritmy nebo najít chybu ve výše uvedeném?

Úvahy o přístupnosti

Dostupnost systému závisí na třech hlavních charakteristikách:

  1. Automaticky uvolnit zámky (po vypršení platnosti klíčů): Klíče budou nakonec znovu k dispozici pro použití pro zámky.
  2. Skutečnost, že klienti si obvykle pomáhají odstraněním zámků, když požadovaný zámek nebyl získán nebo byl získán a úloha byla dokončena; takže je pravděpodobné, že nebudeme muset čekat na vypršení platnosti klíčů, abychom znovu získali zámek.
  3. Skutečnost, že když se klient potřebuje znovu pokusit získat zámek, čeká srovnatelně delší dobu, než je doba potřebná k získání většiny zámků. To snižuje pravděpodobnost, že při soupeření o zdroje nastane situace rozděleného mozku.

Existuje však penalizace za dostupnost rovnající se TTL segmentů sítě, takže pokud existují souvislé segmenty, může být penalizace neomezená. K tomu dochází, kdykoli klient získá zámek a poté se odtrhne od jiného segmentu, než jej může uvolnit.

V zásadě, vzhledem k nekonečným souvislým segmentům sítě, může systém zůstat nedostupný po nekonečně dlouhou dobu.

Výkon, převzetí služeb při selhání a fsync

Mnoho lidí používá Redis, protože potřebují vysoký výkon zámkového serveru, pokud jde o latenci potřebnou k získání a uvolnění zámků a počet akvizic/uvolnění, které lze dokončit za sekundu. Ke splnění tohoto požadavku existuje strategie komunikace se servery N Redis za účelem snížení latence. Toto je strategie multiplexování (neboli „multiplexování chudáka“, kdy je soket uveden do neblokovacího režimu, odesílá všechny příkazy a čte příkazy později, za předpokladu, že doba oběhu mezi klientem a každou instancí je podobná) .

Musíme však také vzít v úvahu úvahy spojené s dlouhodobým ukládáním dat, pokud se snažíme vytvořit model se spolehlivou obnovou po selhání.

V zásadě, abychom problém objasnili, předpokládejme, že nakonfigurujeme Redis bez dlouhodobého ukládání dat. Klient zvládne zablokovat 3 z 5 instancí. Jedna z instancí, které se klientovi podařilo zablokovat, se restartuje a v tuto chvíli existují opět 3 instance pro stejný prostředek, které můžeme zablokovat, a další klient může zase zablokovat restartovanou instanci, čímž poruší bezpečnostní vlastnost, která předpokládá exkluzivitu zámků.

Pokud povolíte data dopředu (AOF), situace se mírně zlepší. Můžete například povýšit server odesláním příkazu SHUTDOWN a jeho restartováním. Vzhledem k tomu, že operace s vypršením platnosti jsou v Redis sémanticky implementovány tak, že čas plynule pokračuje, i když je server vypnutý, jsou všechny naše požadavky v pořádku. To je normální, pokud je zajištěno normální vypnutí. Co dělat v případě výpadku proudu? Pokud je Redis ve výchozím nastavení nakonfigurován s fsync synchronizací na disku každou sekundu, pak je možné, že po restartu nebudeme mít náš klíč. Teoreticky, pokud chceme zaručit zabezpečení zámku během restartu jakékoli instance, měli bychom povolit fsync=always v nastavení pro dlouhodobé ukládání dat. To zcela zabije výkon až na úroveň systémů CP, které se tradičně používají k bezpečné implementaci distribuovaných zámků.

Situace je ale lepší, než se na první pohled zdá. V zásadě je bezpečnost algoritmu zachována, protože při restartu instance po selhání se již neúčastní žádného aktuálně aktivního zámku.

Abychom to zajistili, musíme pouze zajistit, aby po selhání instance zůstala nedostupná po dobu mírně přesahující maximální TTL, které používáme. Takto počkáme na datum expirace a automatické uvolnění všech klíčů, které byly v době poruchy aktivní.

Pomocí zpožděných restartů je v zásadě možné dosáhnout bezpečnosti i při absenci jakékoli dlouhodobé perzistence v Redis. Upozorňujeme však, že to může mít za následek pokutu za porušení přístupnosti. Pokud například selže většina instancí, systém se stane globálně nedostupným pro TTL (a během této doby nelze zablokovat žádný zdroj).

Zvyšujeme dostupnost algoritmu: rozšiřujeme blokování

Pokud se práce prováděná klienty skládá z malých kroků, je možné zkrátit výchozí dobu trvání zámku a implementovat mechanismus pro prodloužení zámků. V zásadě platí, že pokud je klient zaneprázdněn počítačem a hodnota vypršení platnosti zámku je nebezpečně nízká, můžete všem instancím poslat skript Lua, který prodlouží TTL klíče, pokud klíč stále existuje a jeho hodnota je stále náhodná hodnota získaná při zámek byl získán.

Klient by měl uvažovat o opětovném získání zámku pouze v případě, že se mu podařilo uzamknout většinu instancí během doby platnosti.

Je pravda, že technicky se algoritmus nemění, takže maximální počet opakovaných pokusů o získání zámků musí být omezen, jinak budou narušeny vlastnosti přístupnosti.

Zdroj: www.habr.com

Přidat komentář