Helló, Habr!
Ma ma egy olyan bonyolult cikk fordítását kínáljuk figyelmükbe, amely a Redis-alkalmazás alapján megvalósított elosztott zárolásokkal foglalkozik, és a Redis témakörének ígéretes jövőjéről beszélünk. Elemzésre kerül a Martin Kleppmann által írt Redlock algoritmus, a "", amely bemutatja .
Az elosztott zárolások rendkívül hasznos primitívek, amelyeket számos környezetben használnak, ahol különböző folyamatoknak kölcsönös kizárás elve alapján kell megosztott erőforrásokon dolgozniuk.
Számos könyvtár és bejegyzés található, amelyek leírják, hogyan lehet DLM-t (elosztott zároláskezelőt) megvalósítani Redis segítségével, de minden könyvtár a saját megközelítését alkalmazza, és a biztosított garanciák meglehetősen gyengék ahhoz képest, amit kissé bonyolultabb tervezéssel elérhetünk.
Ebben a cikkben megpróbáljuk leírni a feltételesen kanonikus algoritmust, amely bemutatja, hogyan lehet elosztott zárolásokat megvalósítani Redis segítségével. Beszélni fogunk egy algoritmusról, amelynek neve Redlock, amely megvalósítja az elosztott zároláskezelőt, és véleményünk szerint ez az algoritmus biztonságosabb, mint a hagyományos megközelítés egyetlen példányával. Reméljük, hogy a közösség elemezni fogja, visszajelzést ad, és kiindulási pontként használja majd bonyolultabb vagy alternatív projektek megvalósításához.
Megvalósítások
Mielőtt rátérnénk az algoritmus leírására, néhány linket szeretnénk bemutatni a már elkészült megvalósításokhoz. Ezeket referenciaként használhatják.
- (Ruby alapú megvalósítás). Létezik egy Redlock-rb, amely kényelmesen telepíthető csomagot (gem) biztosít, és nem csak emiatt.
- (Python alapú megvalósítás).
- (Asyncio Python alapú megvalósítás).
- (PHP alapú megvalósítás).
- (még egy PHP alapú megvalósítás)
- (PHP záráskezelő könyvtár)
- (Go alapú megvalósítás).
- (Java alapú megvalósítás).
- (Perl alapú megvalósítás).
- (C++ alapú megvalósítás).
- (C#/.NET alapú megvalósítás).
- (C#/.NET alapú megvalósítás), async és lock kiterjesztések támogatásával.
- (C# .NET alapú megvalósítás konfigurálható adattárolással)
- (C# .NET alapú megvalósítás)
- (NodeJS alapú megvalósítás). Tartalmazza a zárolások meghosszabbításának támogatását.
Biztonsági és rendelkezésre állási garanciák
A projektünket három tulajdonsággal fogjuk modellezni, amelyek véleményünk szerint biztosítják a szükséges minimális garanciákat a hatékony elosztott zárak használatához.
- Biztonsági tulajdonság: Kölcsönös kizárás. Bármely pillanatban csak egy kliens tarthatja a zárat.
- A hozzáférhetőségi A tulajdonság: Kölcsönös zárak hiánya. Végül mindig meg lehet kapni a zárat, még akkor is, ha az erőforrást lezáró kliens lemond vagy másik lemezszegmensbe kerül.
- A hozzáférhetőségi B tulajdonság: Hibatűrés. Amíg a Redis csomópontok nagy része működik, a kliens képes zárakat megszerezni és felszabadítani.
Miért elégtelen ebben az esetben a hibahelyreállításon alapuló megvalósítás?
Azzal, hogy megértjük, mit kívánunk javítani, elemezzük a Redis alapú elosztott zárak többségi könyvtárainak jelenlegi állapotát.
A legegyszerűbb módja annak, hogy erőforrást zárjunk a Redis segítségével, egy kulcs létrehozása az példányban. A kulcs általában korlátozott élettartammal rendelkezik, amelyet a Redis expires funkciójával érhetünk el, így előbb-utóbb a kulcs feloldódik (a második tulajdonságunk). Amikor a kliensnek felszabadítani kell az erőforrást, egyszerűen eltávolítja a kulcsot.
Első pillantásra ez a megoldás jól működik, de van egy probléma: az architektúránkban egyetlen hibapont keletkezik. Mi történik, ha a Redis vezető példány meghibásodik? Akkor adjunk hozzá egy követőt! És használjuk, ha a vezető nem érhető el. Sajnos ez a megoldás életképtelen. Ezzel nem tudjuk megfelelően megvalósítani a szükséges kölcsönös kizárás tulajdonságát a biztonságunk érdekében, mivel a Redis replikáció aszinkron.
Nyilvánvaló, hogy egy ilyen modellben versenyhelyzet alakul ki:
- A kliens A megszerzi a zárat a vezetőn.
- A vezető meghibásodik, mielőtt a kulcsba való írás átkerülne a követőhöz.
- A követő vezetővé emelkedik.
- A kliens B megszerzi ugyanannak az erőforrásnak a zárát, amelyet már A lezárt. BIZTONSÁGI HIBÁS!
Néha teljesen normális, hogy különleges körülmények között, például hiba esetén, sok ügyfél egyszerre blokkolhat. Ilyen esetekben replikáción alapuló megoldás alkalmazható. Más esetekben a cikkben leírt megoldás javasolt.
A helyes megvalósítás egyetlen példányban
Mielőtt megpróbálnánk leküzdeni az egyetlen példányú konfiguráció hátrányait, nézzük meg, hogyan kell helyesen cselekedni ebben az egyszerű esetben, mivel ez a megoldás tényleg elfogadható az olyan alkalmazások esetében, ahol a versenyhelyzet időnként megengedett, és azért is, mert az egyetlen példányú blokkolás szolgál alapként a leírt elosztott algoritmushoz.
A blokk megszerzéséhez tegyük a következőket:
SET resource_name my_random_value NX PX 30000
Ez a parancs beállít egy kulcsot, csak akkor, ha még nem létezik (NX opció), 30000 milliszekundumos érvényességi idővel (PX opció). A kulcshoz a következő érték tartozik: “myrandomvalue”. Ennek az értéknek egyedinek kell lennie az összes ügyfél és az összes blokkérési kérés között.
Alapvetően a véletlenszerű érték használata biztonságos módot biztosít a blokk felszabadítására egy olyan szkripttel, amely a Redisnek jelzi: töröld a kulcsot, csak ha az létezik, és az abban tárolt érték éppen az, amire számítottunk. Ezt a következő Lua szkripttel érjük el:
if redis.call("get",KEYS[1]) == ARGV[1] then
return redis.call("del",KEYS[1])
else
return 0
endFontos, hogy elkerüljük a blokk eltávolítását, amelyet egy másik ügyfél végzett. Például egy ügyfél megszerezheti a blokkolást, majd elakadhat egy olyan művelet közben, amely tovább tart, mint az első blokk érvényességi ideje (így a kulcs érvényessége lejár), és később eltávolíthatja a blokkot, amelyet egy másik ügyfél állított be.
A sima DEL használata nem biztonságos, mivel az ügyfél eltávolíthatja egy másik ügyfél által beállított blokkot. Ezzel szemben a fent leírt szkript használatával minden blokk 'aláírásra' kerül egy véletlenszerű karakterlánccal, ezért csak az az ügyfél tudja eltávolítani, aki korábban azt beállította.
Milyennek kell lennie ennek a véletlenszerű sztringnek? Azt hiszem, ennek 20 bájt hosszúnak kellene lennie a /dev/urandom-ból, de léteznek olcsóbb módszerek is arra, hogy a céljaidhoz elég egyedi sztringet készíts. Például rendben van az RC4-et a /dev/urandom-ból maghoz ültetni, majd ezen alapuló ál-véletlenszerű folyamatot generálni. Egy egyszerűbb megoldás a unix idő mikroszekundumos felbontású kombinációja és a kliens azonosító; ez nem annyira biztonságos, de valószínűleg megfelel a feladat szintjének a legtöbb kontextusban.
Az az idő, amit a kulcs élettartamának mutatójaként használunk, az úgynevezett „zárolási idő”. Ez az érték egyszerre határidő, amely után a zárolás automatikusan feloldódik, és az idő, amennyi a kliensnek van az operáció végrehajtására, mielőtt egy másik kliens zárolhatja ezt az erőforrást anélkül, hogy ténylegesen megsértené a kölcsönös kizárás garanciáit. Ez a garancia egy meghatározott időablakra korlátozódik, amely a zárolás megszerzésével kezdődik.
Tehát beszéltünk egy jó módszerről a zárolás megszerzésére és feloldására. A rendszer (ha nem elosztott rendszerről van szó, amely egyetlen és mindig elérhető példányból áll) biztonságos. Terjesszük ki ezt a koncepciót egy elosztott rendszerre, amelyben nincsenek ilyen garanciáink.
Redlock algoritmus
Az algoritmus elosztott verziójában azt feltételezzük, hogy van N vezető Redis. Ezek a csomópontok teljesen függetlenek egymástól, ezért nem használunk replikációt vagy bármilyen más implicit koordinációs rendszert. Már beszéltünk arról, hogyan lehet biztonságosan megszerezni és feloldani a zárolást egyetlen példányon. Feltételezzük, hogy az algoritmus egy példánnyal dolgozva ezt a módszert használja. A példáinkban N-t 5-re állítjuk be, ez egy teljesen ésszerű érték. Így szükségünk lesz 5 vezető Redis-re különböző számítógépeken vagy virtuális gépeken, hogy garantáljuk, hogy alapvetően egymástól függetlenül működjenek.
A zárolás megszerzéséhez a kliens a következő műveleteket hajtja végre:
- Megkapja a jelenlegi időt milliszekundumban.
- A kliens újra és újra megpróbálja megszerezni a zárolást az összes N példányra, minden esetben ugyanazt a kulcsnevet és véletlenszerű értékeket használva. A 2. lépésben, amikor minden példányhoz zárolást állít be, a kliens egy késleltetést alkalmaz, amely viszonylag rövid ahhoz képest, hogy mennyi idő alatt szűnik meg automatikusan a zárolás. Például, ha a zárolás időtartama 10 másodperc, a késleltetés ~ 5-50 milliszekundum között mozoghat. Ezzel elkerülhető, hogy a kliens hosszú ideig zárolva maradjon, miközben a hibás Redis csomópontot próbálja elérni: ha a példány elérhetetlen, akkor igyekszünk minél előbb kapcsolódni egy másik példányhoz.
- A kliens a zárolás megszerzésének időtartamát úgy számolja ki, hogy kivonja a 1. lépésben kapott időbélyeget az aktuális időből. Csak akkor tekinthető a zárolás megszerzésének, ha a kliens a többségi példányon (legalább 3-on) sikeresen megszerezte a zárolást, és a zárolás megszerzéséhez szükséges teljes idő kevesebb, mint a zárolás időtartama.
- Ha a zárolást megszerezték, akkor a zárolás időtartama az alapértelmezett zárolási idő mínusz a 3. lépésben számított eltelt idő.
- Ha a kliens valamilyen okból nem tudta megszerezni a zárolást (vagy nem tudott N/2+1 példányt zárolni, vagy a zárolás időtartama negatív lett), megpróbálja feloldani az összes példány zárolását (még azokat is, amelyekről úgy vélték, hogy nem tudta zárolni).
Aszinkron algoritmusnak számít?
Ez az algoritmus azon a feltételezésen alapul, hogy bár nincsenek szinkronizált órák, amelyek szerint az összes folyamat működik, minden folyamat helyi ideje körülbelül ugyanolyanképpen telik, és a hiba kicsi ahhoz képest, hogy mennyi idő alatt szűnik meg automatikusan a zárolás. Ez a feltételezés nagyon hasonlít a szokásos számítógépek helyzetéhez: minden számítógépnek vannak helyi órái, és általában számíthatunk arra, hogy különböző számítógépeken a pontos időbeli eltérés kicsi.
Ezen a ponton alaposabban meg kell fogalmaznunk a kölcsönös kizárás szabályát: a kölcsönös kizárás csak abban az esetben garantált, ha az a kliens, aki a zárolást megtartja, a zárolás érvényességi ideje alatt befejezi a munkáját (ez az érték a 3. lépésben lett meghatározva), levonva egy kis időt (csupán néhány milliszekundum a folyamatok közötti időeltolódás kompenzálására).
További részletek az időeltolódást egyeztető hasonló rendszerekről a következő érdekes cikkben találhatók: .
Újrapróbálkozás hiba esetén
Ha a kliens nem tudta megszerezni a zárolást, akkor meg kell próbálnia újra, véletlenszerű késleltetéssel; ez azért szükséges, hogy szinkronizálatlanul próbálkozzanak a különböző kliensek, akik egyszerre próbálják megszerezni egy ugyanazon erőforrás zárolását (ami „megosszabott agy” helyzethez vezethet, ahol nincs győztes). Ezen kívül, minél gyorsabban próbálja a kliens megszerezni a zárolást a legtöbb Redis példánytól, annál szűkebb az az időintervallum, ahol a megosszabott agy helyzete előfordulhat (és annál kevesebb újrapróbálkozás válik szükségessé). Ezért ideális esetben a kliensnek párhuzamosan kellene SET parancsokat küldenie N példányhoz multiplexálás segítségével.
Fontos hangsúlyozni, hogy azoknak a klienseknek, akik nem tudtak megszerezni a többségi zárolásokat, fel kellene szabadítaniuk (részben) a megszerzett zárolásokat, hogy ne kelljen a kulcs lejárati idejére várni, mielőtt a zárolás újra megszerezhetővé válik az erőforrásra (azonban ha hálózati fragmentáció történik, és a kliens elveszíti a kapcsolatot a Redis példányokkal, akkor büntetést kell fizetni a hozzáférhetőség megsértéséért, amíg várakozik a kulcs lejárati idejére).
Zárolás felszabadítása
A zárolás felszabadítása egy egyszerű művelet, amely csupán a minden példányt fel kell szabadítani, függetlenül attól, hogy a kliensnek úgy tűnik-e, hogy sikeresen zárolta az adott példányt.
Biztonsági megfontolások
Mennyire biztonságos az algoritmus? Próbáljuk meg elképzelni, hogy különböző forgatókönyvekben mi történik.
Kezdetben tegyük fel, hogy az ügyfél képes volt megszerezni a zárat a legtöbb példány felett. Minden példány rendelkezni fog egy kulccsal, amelynek élettartama azonos lesz mindegyiknél. Azonban ezek a kulcsok különböző pillanatokban kerültek beállításra, így eltérő időpontokban fognak lejárni. De ha az első kulcs a T1 pillanatban lett beállítva (az időpont, amit a legelső szerverrel való kapcsolatfelvétel előtt választunk), és az utolsó kulcs a T2 pillanatban (az időpont, amikor az utolsó szervertől választ kaptunk), akkor biztosak lehetünk abban, hogy az első kulcs az érvényességi időszakot túllépő halmazban legalább MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Minden más kulcs később fog lejárni, így biztosak lehetünk abban, hogy minden kulcs egyidejűleg érvényes marad legalább ennyi ideig.
Azokban az időszakokban, amikor a legtöbb kulcs érvényes, egy másik ügyfél nem tud zárat szerezni, mivel az N/2+1 SET NX műveletek nem lehetnek sikeresek, ha már létezik N/2+1 kulcs. Ezért, ha a zárat megszerezték, akkor azt ugyanabban a pillanatban nem lehet újra megszerezni (ez megsértené a kölcsönös kizárás tulajdonságát).
Bár biztosak akarunk lenni abban, hogy a zárat egyidejűleg megszerezni próbáló ügyfelek nem fognak egyszerre sikerrel járni.
Ha az ügyfél blokkolta a legtöbb példányt, és ez időt vett igénybe, ami körülbelül vagy meghaladja a blokkolás maximális időtartamát, akkor a zárat érvénytelennek tekinti és feloldja a példányokat. Ezért csak azt az esetet kell figyelembe vennünk, amelyben az ügyfél sikerült blokkolnia a legtöbb példányt egy időtartamon belül, ami kevesebb, mint az érvényességi idő. Ebben az esetben, ami a fenti érvet illeti, az idő MIN_VALIDITY egyik ügyfél sem kell, hogy újra megszerezze a zárat. Ezért több ügyfél is képes lesz egyszerre N/2+1 példányt blokkolni ugyanazon idő alatt (ami a 2-es szakasz befejezésének pillanatában ér véget), csak akkor, ha a többség blokkolását igénylő idő hosszabb volt, mint a TTL idő, ami a zárat érvényteleníti.
Tudná adni a biztonság formális bizonyítékát, megjelölni a létező hasonló algoritmusokat, vagy találni hibát az előterjesztettben?
Elérhetőséggel kapcsolatos megfontolások
A rendszer elérhetősége három fő jellemzőtől függ:
- Automatikus akadálymentesítés (mivel a kulcsok érvényességi ideje lejár): végül a kulcsok újra elérhetővé válnak, hogy használják az akadályok megszüntetésére.
- Az a tény, hogy az ügyfelek általában segítenek egymásnak az akadályok eltávolításában, amikor a szükséges akadályt nem vásárolták meg, vagy megvásárolták, de a munka befejeződött; ezért valószínű, hogy nem kell megvárnunk a kulcsok lejáratát, hogy újra megszerezzük az akadályt.
- Az a tény, hogy amikor az ügyfélnek meg kell próbálnia újra megszerezni az akadályt, viszonylag hosszabb ideig várakozik, mint a legtöbb akadály megszerzéséhez szükséges idő. Ez csökkenti a megosztott memória helyzet kialakulásának valószínűségét az erőforrásokért folytatott versengés során.
Ugyanakkor a csökkent elérhetőségért büntetést kell fizetni, ami megegyezik a TTL idővel a hálózati szegmensekben, ezért ha folyamatos szegmensek állnak rendelkezésre, akkor ez a büntetés határtalan méretet ölthet. Ez minden alkalommal megtörténik, amikor az ügyfél megszerzi az akadályt, majd leválik egy másik szegmensre, mielőtt sikerülne azt felszabadítani.
Elméletileg, ha végtelen folyamatos hálózati szegmensek állnak rendelkezésre, a rendszer végtelen ideig elérhetetlen maradhat.
Teljesítmény, helyreállítási képesség és fsync
Sokan használják a Redist, mivel biztosítani kell a zárolási szerver magas teljesítményét, a zárolások megszerzéséhez és felszabadításához szükséges késleltetés szintjén, valamint azon műveletek számát, amelyeket másodpercenként sikerül végrehajtani. E követelménynek való megfelelés érdekében létezik egy N Redis szerverrel való kommunikációs stratégia a késleltetés csökkentésére. Ez a multiplexálási stratégia (vagy „szegények multiplexálása”, ahol a socket nem blokkoló módban működik, elküldi az összes parancsot, és később olvassa be a parancsokat, feltételezve, hogy az ügyfél és az egyes példányok közötti fordulási idő hasonló).
Igaz, figyelembe kell venni egy másik szempontot is, amely a hosszú távú adatok tárolásával kapcsolatos, ha egy megbízható hibahelyreállítási modellt kívánunk létrehozni.
Elvileg, hogy tisztázzuk a problémát, tegyük fel, hogy a Redis-t úgy konfiguráljuk, hogy egyáltalán ne tároljon adatokat tartósan. Az ügyfél sikerült blokkolnia 5 példány közül 3-at. Az egyik példány, amelyet az ügyfél blokkolt, újraindul, és ekkor újra 3 példány jelenik meg ugyanarra az erőforrásra, amelyet blokkolhatunk, és egy másik ügyfél, viszont blokkolhatja az újraindított példányt, megsértve ezzel a blokkolás egyediségére vonatkozó biztonsági jellemzőt.
Ha engedélyezzük az adatok előzetes tárolását (AOF), a helyzet kicsit javul. Például emelhetjük a szervert, ha kiadunk egy SHUTDOWN parancsot, majd újraindítjuk. Mivel a Redis-ben a lejárati műveletek olyan módon valósulnak meg, hogy az idő továbbra is halad, amikor a szerver ki van kapcsolva, minden követelménnyel rendben vagyunk. Rendben van, amíg a szokásos leállítás biztosított. Mi a helyzet áramkimaradások esetén? Ha a Redis alapértelmezés szerint van konfigurálva, és az fsync-t minden másodpercben a lemezre szinkronizálja, akkor előfordulhat, hogy az újraindítás után nem találjuk meg a kulcsunkat. Elméletileg, ha garantálni akarjuk a blokkolások biztonságát bármilyen újraindításkor, akkor be kell kapcsolnunk fsync=always a tartós adatmentés beállításaiban. Ez teljesen megölni a teljesítményt, olyan szintre, mint a hagyományosan használt CP-rendszerek, amelyek biztonságosan valósítják meg a elosztott blokkolásokat.
De a helyzet jobb, mint amilyennek elsőre tűnik. Elvileg az algoritmus biztonsága megmarad, mivel, amikor a példány újraindul a hiba után, már nem vesz részt egyetlen aktív blokkolásban sem.
Annak biztosításához, hogy ez így legyen, csupán annyit kell tenni, hogy a hiba után a példány elérhetetlen marad egy olyan időintervallumban, amely kissé meghaladja a maximális TTL-t, amelyet használunk. Így megvárjuk a kulcsok lejáratát és automatikus felszabadítását, amelyek aktívak voltak a hiba pillanatában.
Felhalmozott újraindítások alkalmazásával elvileg lehetséges a biztonság elérése a Redis hosszú távú megőrzése nélkül. Igaz, hogy ez elérheti a rendelkezésre állás megsértésének büntetését. Például, ha a legtöbb példány leáll, a rendszer globálisan elérhetetlenné válik a TTL időtartamára (és ezen idő alatt egy erőforrást sem lehet letiltani).
Növeljük az algoritmus elérhetőségét: meghosszabbítjuk a zárolást
Ha az ügyfelek által végzett munka apró lépésekből áll, akkor lehetőség van a lehetséges alapértelmezett zárolási idő csökkentésére, és a zárolások meghosszabbításának mechanizmusának megvalósítására. Elvileg, ha az ügyfél számításokat végez, és a zárolás időtartamának értéke veszélyesen csökkent, akkor minden példány számára lehet egy Lua szkriptet küldeni, amely meghosszabbítja a kulcs TTL-jét, ha a kulcs még létezik, és értéke továbbra is véletlenszerű, amelyet a zárolás megszerzésekor nyert.
Az ügyfél csak akkor tekintheti a zárolást újból megkapottnak, ha az időtartama alatt sikerült a legtöbb példányt zárolnia.
Igaz, hogy technikailag az algoritmus nem változik, ezért a zárolások megszerzésére tett maximális újrapróbálkozások számát korlátozni kell, különben megsérülnek a rendelkezésre állási tulajdonságok.
Forrás: habr.com
