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

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

Ahoj, Habr!

Dnes vám nabízíme překlad složitého článku o implementaci distribuovaných zámků pomocí Redis a nabízíme diskusi o perspektivnosti Redis jako tématu. Analýza zvažovaného algoritmu Redlock od Martina Kleppmanna, autora knihy "Vysoce zatížené aplikace", je uvedena zde.

Distribuované zámky jsou velmi užitečný primitiv, který se používá v mnoha prostředích, kde různé procesy musí pracovat se sdílenými zdroji na principu vzájemného vyloučení.

Existuje řada knihoven a příspěvků, které popisují, jak implementovat DLM (správce distribuovaných zámků) pomocí Redis, ale každá knihovna používá vlastní přístup a poskytované záruky jsou poměrně slabé v porovnání s tím, co je dosažitelné pomocí trochu složitějšího návrhu.

V tomto článku se pokusíme popsat podmíněně kanonický algoritmus, který demonstruje, jak implementovat distribuované zámky pomocí Redis. Při tom se budeme věnovat algoritmu s názvem Redlock, který implementuje správce distribuovaných zámků a podle našeho názoru je tento algoritmus bezpečnější než obvyklý přístup s jediným instancí. Doufáme, že komunitu zanalizuje, poskytne zpětnou vazbu a stane se výchozím bodem pro implementaci složitějších nebo alternativních projektů.

Implementace

Než přejdeme k popisu algoritmu, uvedeme několik odkazů na již hotové implementace. Je možné je použít pro referenci.

Záruky bezpečnosti a dostupnosti

Chystáme se modelovat náš projekt pouze se třemi vlastnostmi, které podle našeho názoru poskytují minimální záruky potřebné pro efektivní používání distribuovaných zámků.

  1. Bezpečnostní vlastnost: Vzájemné vyloučení. V každém okamžiku může jeden klient držet zámek.
  2. Vlastnost dostupnosti A: Nepřítomnost vzájemných blokací. Nakonec je vždy možné získat zámek, i když klient, který blokuje prostředek, selže nebo se přesune do jiného disku.
  3. Vlastnost dostupnosti B: Odolnost proti selhání. Dokud většina uzlů Redis funguje, klienti mohou zámky získávat a uvolňovat.

Proč realizace založená na obnovení po selhání v tomto případě není dostatečná.
Abychom pochopili, co chceme zlepšit, podívejme se na aktuální stav většiny knihoven pro distribuované zámky založených na Redis.

Nejjednodušší způsob, jak zablokovat prostředek pomocí Redis, je vytvořit klíč v instanci. Klíč se obvykle vytváří s omezenou životností, což je dosaženo pomocí funkce expires v Redis, a proto tento klíč dříve nebo později bude uvolněn (vlastnost 2 v našem seznamu). Když klient potřebuje uvolnit prostředek, odstraní klíč.

Na první pohled toto řešení funguje, ale problém je v tom, že v naší architektuře se vytváří jediný bod selhání. Co se stane, pokud selže vedoucí instance Redis? Přidejme tedy následníka! A použijeme ho, pokud vedoucí nebude dostupný. Bohužel tento přístup není životaschopný. Uděláním toho nebudeme schopni správně implementovat vlastnost vzájemného vyloučení, kterou potřebujeme pro zajištění bezpečnosti, protože replikace v Redis je asynchronní.

Je zřejmé, že v takovém modelu dochází k závodu:

  1. Klient A získává zámek na vedoucím.
  2. Vedoucí selže, než je záznam o klíči předán následníkovi.
  3. Následník se zvedne na vedoucího.
  4. Klient B získává zámek na stejný prostředek, který již blokuje A. PORUŠENÍ BEZPEČNOSTI!

Někdy je zcela normální, že v určitých okolnostech, například při selhání, může mnoho klientů současně držet zámek. V takových případech lze použít řešení založené na replikaci. V ostatních případech doporučujeme řešení popsané v tomto článku.

Správná implementace s jediným instancí

Než se pokusíme překonat nedostatky konfigurace s jediným instancí, jak bylo uvedeno výše, podívejme se, jak správně jednat v tomto jednoduchém případě, protože takové řešení je skutečně přijatelné v těch aplikacích, kde je závodní stav příležitostně povolen, a také proto, že zámek na jediném instancí slouží jako základ pro zde popsaný distribuovaný algoritmus.

Abychom získali zámek, postupujme takto:

SET resource_name my_random_value NX PX 30000

Tento příkaz nastaví klíč, pouze pokud ještě neexistuje (možnost NX), s platností 30000 milisekund (možnost PX). Pro klíč se nastavuje hodnota "myrandomvalue". Tato hodnota by měla být jedinečná mezi všemi klienty a všemi žádostmi o zámek.
Obecně platí, že náhodná hodnota se používá k bezpečnému uvolnění zámku pomocí skriptu, který říká Redis: maž klíč, pouze pokud existuje, a hodnota, která je v něm uložena, je přesně to, co se očekávalo. Toho se dosahuje pomocí následujícího Lua skriptu:

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

Je důležité předejít uvolnění zámku provedeného jiným klientem. Například klient může získat zámek, pak se zablokovat během nějaké operace, která trvá déle, než je platnost prvního zámku (takže platnost klíče může vypršet) a později uvolnit zámek, který stanovil jiný klient.
Použití jednoduchého DEL není bezpečné, protože klient může odstranit zámek, který stanovil jiný klient. Naopak, při použití výše uvedeného skriptu je každý zámek "podepsán" náhodným řetězcem, a proto ho může odstranit pouze ten klient, který ho dříve stanovil.

Jaký by měl být tento náhodný řetězec? Předpokládám, že to má být 20 bytů z /dev/urandom, ale existují i méně nákladné způsoby, jak vytvořit řetězec dostatečně jedinečný pro vaše cíle. Například by bylo v pořádku použít RC4 z /dev/urandom a poté na jeho základě generovat pseudonáhodný tok. Jednodušší řešení by bylo spojení unixového času s mikroskopickou přesností a ID klienta; není to tak bezpečné, ale pravděpodobně to odpovídá úrovni úkolů v většině kontextů.

Čas, který používáme jako ukazatel životnosti klíče, se nazývá „čas vypršení zámku“. Tato hodnota je zároveň termínem, po jehož uplynutí se zámek automaticky uvolní, a doba, kterou má klient na provedení operace, než jiný klient bude moci tento zdroj zablokovat, aniž by skutečně porušil záruky vzájemného vyloučení. Tato záruka je omezena pouze určitou časovou oknem, které začíná od okamžiku získání zámku.

Tedy jsme prodiskutovali dobrý způsob, jak získat a uvolnit zámek. Systém (pokud se jedná o distribuovaný systém, který se skládá z jediného a neustále dostupného instance) je bezpečný. Pojďme rozšířit tento koncept na distribuovaný systém, ve kterém tyto záruky nemáme.

Redlock algoritmus

V distribuované verzi algoritmu předpokládáme, že máme N hlavních Redis. Tyto uzly jsou plně nezávislé na sobě, takže nepoužíváme replikaci ani žádný jiný implicitní koordinační systém. Již jsme vysvětlili, jak bezpečně získat a uvolnit zámek na jediném instanci. Předpokládáme, že algoritmus při práci s jediným instancí použije právě tuto metodu. V našich příkladech nastavujeme N na 5, což je zcela rozumná hodnota. Takže budeme potřebovat použít 5 hlavních Redis na různých počítačích nebo virtuálních strojích, abychom zajistili, že budou fungovat především nezávisle na sobě.

Aby klient získal zámek, provede následující operace:

  1. Získá aktuální čas v milisekundách.
  2. Snaží se postupně získat zámek na všech N instancích, přičemž ve všech případech používá stejné jméno klíče a náhodné hodnoty. Ve fázi 2, při nastavování zámku pro každou instanci, klient využívá zpoždění, které je dostatečně krátké ve srovnání s dobou, po které se zámek automaticky uvolňuje. Například pokud trvání zámku je 10 sekund, zpoždění může být v rozmezí přibližně 5-50 milisekund. Tím se vylučuje situace, kdy by klient mohl být dlouho zamčen, zatímco by se snažil připojit k nefunkčnímu uzlu Redis: pokud je instance nedostupná, snažíme se co nejdříve připojit k jiné instanci.
  3. Aby získal zámek, klient vypočítá, kolik času uplynulo; k tomu odečte aktuální čas od časové značky, kterou získal v kroku 1. Teprve poté, co se klientovi podaří získat zámek na většině instancí (alespoň 3) a celkový čas potřebný k získání zámku je kratší než doba platnosti zámku, se považuje, že získání zámku proběhlo úspěšně.
  4. Pokud byl zámek získán, za dobu jeho platnosti se považuje původní hodnota trvání zámku minus uplynulý čas vypočítaný ve kroku 3.
  5. Pokud se klientovi z nějakého důvodu nepodařilo získat zámek (buď se mu nepodařilo uzamknout N/2+1 instancí, nebo doba platnosti zámku byla záporná), pokusí se uvolnit všechny instance (i ty, o kterých se domníval, že je nemohl zamknout).

Je algoritmus asynchronní?

Tento algoritmus vychází z předpokladu, že ačkoli neexistují synchronizované hodiny, podle kterých by pracovaly všechny procesy, lokální čas v každém procesu plyne přibližně stejným tempem a chyba je malá v porovnání s celkovým časem, po kterém se zámek automaticky uvolňuje. Tento předpoklad velmi připomíná situaci, která je typická pro běžné počítače: na každém počítači jsou lokální hodiny a obvykle můžeme očekávat, že časová odchylka mezi různými počítači je malá.

V této fázi musíme důkladněji formulovat naše pravidlo vzájemného vyloučení: vzájemné vyloučení je zaručeno pouze za předpokladu, že klient, který drží zámek, ukončí svou práci v čase, kdy je zámek platný (tato hodnota byla získána v kroku 3), minus další čas (celkově několik milisekund, aby se kompenzovalo časové zpoždění mezi procesy).

Více o podobných systémech, které vyžadují vyrovnání časových odchylek, popisuje následující zajímavý článek: Leases: efektivní mechanismus tolerující chyby pro konzistenci distribuovaných souborových cache.

Opakování pokusu při selhání

Když se klientovi nepodaří získat zámek, měl by se pokusit o to znovu s náhodným zpožděním; to se provádí s cílem rozštěpit více klientů, kteří se zároveň snaží získat zámek jednoho a téhož zdroje (což může vést k situaci "roztrženého mozku", kde nejsou vítězové). Dále, čím rychleji se klient snaží získat zámek pro většinu instancí Redis, tím menší je okno, ve kterém může nastat situace roztrženého mozku (a tím menší je potřeba opakovaných pokusů). Ideálně by se klient měl snažit současně poslat příkazy SET k N instancím pomocí multiplexování.

Zde je třeba zdůraznit, jak důležité je, aby klienti, kteří se nepodařilo získat většinu zámků, uvolnili (částečně) již získané zámky, aby nemuseli čekat na vypršení platnosti klíče, než bude zámek nad zdrojem znovu možné získat (pravda, pokud dojde k fragmentaci sítě a klient ztratí spojení s instancemi Redis, je třeba zaplatit pokutu za porušení dostupnosti, dokud se nečeká na vypršení platnosti klíče).

Uvolnění zámku

Uvolnění zámku je jednoduchá operace, kterou stačí odblokovat všechny instance, bez ohledu na to, zda se klientovi zdá, že se mu podařilo úspěšně zablokovat konkrétní instanci.

Bezpečnostní úvahy

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

Nejprve si představme, že klient byl schopen získat zámek nad většinou instancí. Každá z instancí bude obsahovat klíč se stejnou dobou platnosti pro všechny. Nicméně každý z těchto klíčů byl nastaven v jiném okamžiku, a proto jejich platnost vyprší v různých časech. Pokud byl první klíč nastaven ve chvíli, která je alespoň T1 (čas, který vybíráme před kontaktem s prvním serverem), a poslední klíč byl nastaven ve chvíli, která je alespoň T2 (čas, kdy byla obdržena odpověď od posledního serveru), pak si jsme jisti, že první klíč ve skupině, jehož platnost vyprší, zůstane platný minimálně MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Všechny ostatní klíče vyprší později, a proto si můžeme být jisti, že všechny klíče budou zároveň platné po minimální dobu.

Během doby, kdy většina klíčů zůstává platná, další klient nebude schopen získat zámek, protože operace N/2+1 SET NX nemohou skončit úspěšně, pokud již existuje N/2+1 klíčů. Proto, pokud byl zámek získán, není možné jej znovu získat ve stejném okamžiku (to by narušovalo vlastnost vzájemného vyloučení).
Opravdu chceme zajistit, že skupina klientů, kteří se současně snaží získat zámek, nebude schopna uspět ve stejnou chvíli.

Pokud klient zablokoval většinu instancí a zabral na to čas přibližně nebo více než maximální dobu trvání zámku, považuje zámek za neplatný a odblokuje instance. Proto musíme vzít v úvahu pouze ten případ, kdy se klientovi podařilo zablokovat většinu instancí za čas kratší než doba platnosti. V tomto případě, co se týče výše uvedeného argumentu, za čas MIN_VALIDITY žádný klient by neměl být schopen znovu získat zámek. Takže skupina klientů může zablokovat N/2+1 instancí ve stejném čase (který končí na konci fáze 2), pouze když doba pro zablokování většiny byla delší než doba TTL, což činí zámek neplatným.

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

Úvahy o dostupnosti

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

  1. Automatické odblokování (protože platnost klíčů vyprší): nakonec budou klíče opět dostupné pro použití k odblokování.
  2. Skutečnost, že si klienti obvykle navzájem pomáhají tím, že odblokovávají, když potřebná blokace nebyla zakoupena, nebo byla zakoupena a práce skončila; proto je velmi pravděpodobné, že nebudeme muset čekat na vypršení klíčů, abychom znovu zakoupili blokaci.
  3. Skutečnost, že když klient potřebuje znovu zkusit získat blokaci, čeká relativně delší dobu, než je čas potřebný k zakoupení většiny blokací. Tím se snižuje pravděpodobnost vzniku situace rozdělené mysli při soutěži o zdroje.

Musíme však zaplatit pokutu za sníženou dostupnost, což odpovídá času TTL v segmentech sítě, takže pokud jsou nepřetržité segmenty, může tato pokuta nabýt neurčité velikosti. K tomu dochází pokaždé, když klient získá blokaci a pak je odříznut v jiném segmentu dříve, než ji stihne uvolnit.

V zásadě, pokud existují nekonečné nepřetržité segmenty sítě, může být systém nedostupný po nekonečně dlouhou dobu.

Výkon, zotavení po selhání a fsync

Mnoho lidí používá Redis, protože je třeba zajistit vysoký výkon serveru blokací na úrovni latencí potřebných pro získání a uvolnění blokací, stejně jako množství operací takového získání/uvolnění, které se podaří provést za sekundu. K tomu existuje strategie komunikace s N servery Redis, aby se snížila latence. Tato strategie je multiplexování (nebo 'chudé multiplexování', kdy je socket nastaven do neblokujícího režimu, posílá všechny příkazy a později čte příkazy, předpokládajíc, že doba obratu mezi klientem a každým z instancí je podobná).

Je pravda, že musíme také vzít v úvahu úvahu o dlouhodobém uchovávání dat, pokud se snažíme vytvořit model s spolehlivým zotavením po selhání.

Aby objasnili problém, předpokládejme, že konfigurujeme Redis bez trvalého ukládání dat. Klient úspěšně zablokuje 3 z 5 instancí. Jedna z instancí, kterou se klientovi podařilo zablokovat, se restartuje, a v tu chvíli vznikají znovu 3 instance pro stejný zdroj, které můžeme zablokovat, a jiný klient může zablokovat restartovanou instanci, čímž porušuje bezpečnostní vlastnost vyžadující exkluzivitu blokací.

Pokud aktivujeme předběžné ukládání dat (AOF), situace se mírně zlepší. Například můžeme zvýšit server, když pošleme příkaz SHUTDOWN a restartujeme ho. Protože operace vypršení v Redis jsou semanticky implementovány tak, že čas pokračuje, i když je server vypnutý, je vše s našimi požadavky v pořádku. V pořádku, dokud je zajištěno standardní vypnutí. Co dělat při výpadku napájení? Pokud je Redis výchozím způsobem nakonfigurován s fsync na disku každou sekundu, je možné, že po restartu nenajdeme naši klíč. Teoreticky, pokud chceme zajistit bezpečnost blokací při každém restartu instance, musíme povolit fsync=always v nastavení trvalého ukládání dat. To zcela zničí výkon, na úroveň těch CP systémů, které se tradičně používají pro bezpečnou realizaci distribuovaných blokací.

Ale situace je lepší, než se na první pohled zdá. V zásadě je bezpečnost algoritmu zachována, protože když se instance restartuje po selhání, již se nezúčastňuje žádné aktivní blokace.

Abychom to zajistili, stačí zajistit, aby byla instance po selhání nedostupná po dobu, která mírně přesahuje maximální TTL, který používáme. Tak počkáme na vypršení platnosti a automatické uvolnění všech klíčů, které byly aktivní v době selhání.

Použitím odložených restartů je v zásadě možné dosáhnout bezpečnosti i za absence jakékoliv dlouhodobé udržitelnosti v Redis. Je však pravda, že to může vést k pokutě za porušení dostupnosti. Například, pokud dojde k selhání většiny instancí, systém se stane globálně nedostupným na dobu TTL (a v tomto čase nebude možné zablokovat žádný zdroj).

Zvyšujeme dostupnost algoritmu: prodlužujeme zámek

Pokud se práce prováděná klienty skládá z menších etap, je možné zkrátit výchozí dobu trvání zámku a realizovat mechanismus prodlužování zámků. V zásadě, pokud je klient zaměstnán výpočty a hodnota doby trvání zámku nebezpečně klesá, lze všem instancím poslat skript v Lua, který prodlouží TTL klíče, pokud klíč stále existuje a jeho hodnota je nadále náhodná, získaná při zakoupení zámku.

Klient by měl považovat zámek za znovu získaný pouze v případě, kdy se mu podařilo zablokovat většinu instancí během doby trvání.

Technicky se však algoritmus nemění, a proto by maximální počet opakovaných pokusů o získání zámků měl být omezen; jinak budou porušeny vlastnosti dostupnosti.

Zdroj: habr.com

Koupit spolehlivý hosting pro webové stránky s ochranou proti DDoS, VPS VDS servery 🔥 Koupit spolehlivý hosting pro webové stránky s ochranou proti DDoS, VPS VDS servery | ProHoster