ProHoster > Блог > Administracija > Distribuirano zaključavanje pomoću Redis-a

Distribuirano zaključavanje pomoću Redis-a

Hej Habr!

Danas vam predstavljamo prijevod složenog članka o implementaciji distribuiranog zaključavanja pomoću Redis-a i pozivamo vas da razgovarate o perspektivama Redisa kao teme. Analiza dotičnog Redlock algoritma od Martina Kleppmanna, autora knjige "Aplikacije sa velikim opterećenjem“, dato ovdje.

Distribuirano zaključavanje je vrlo koristan primitiv koji se koristi u mnogim okruženjima gdje različiti procesi moraju raditi na zajedničkim resursima na međusobno isključiv način.

Postoji veliki broj biblioteka i postova koji opisuju kako implementirati DLM (Distributed Lock Manager) koristeći Redis, ali svaka biblioteka ima drugačiji pristup i garancije koje pružaju su prilično slabe u poređenju sa onim što je moguće postići sa malo sofisticiranijim dizajnom.

U ovom članku pokušat ćemo opisati uvjetni kanonski algoritam koji pokazuje kako implementirati distribuirano zaključavanje koristeći Redis. Pričaćemo o algoritmu pod nazivom Redlock, implementira distribuirani menadžer zaključavanja i, po našem mišljenju, ovaj algoritam je sigurniji od uobičajenog pristupa sa jednom instancom. Nadamo se da će ga zajednica analizirati, dati povratne informacije i koristiti ga kao polaznu tačku za složenije ili alternativne projekte.

Implementacija

Prije nego što pređemo na opis algoritma, pružamo nekoliko veza do gotovih implementacija. Mogu se koristiti za referencu.

Garancije sigurnosti i dostupnosti

Naš dizajn ćemo modelirati sa samo tri svojstva za koja mislimo da pružaju minimalne garancije potrebne za efikasno korištenje distribuiranog zaključavanja.

  1. Sigurnosna imovina: Međusobno isključenje. U bilo kom trenutku, samo jedan klijent može zadržati bravu.
  2. Svojstvo dostupnosti A: Nema zastoja. Uvijek je moguće na kraju dobiti zaključavanje, čak i ako klijent koji je zaključao resurs ne uspije ili dođe na drugi segment diska.
  3. Svojstvo dostupnosti B: Tolerancija grešaka. Sve dok je većina Redis čvorova pokrenuta, klijenti su u mogućnosti da prihvate i otpuste zaključavanja.

Zašto implementacija zasnovana na oporavku od kvara nije dovoljna u ovom slučaju
Da bismo razumjeli šta ćemo poboljšati, analizirajmo trenutno stanje s većinom distribuiranih biblioteka zaključavanja zasnovanih na Redis-u.

Najjednostavniji način zaključavanja resursa pomoću Redis-a je kreiranje ključa u instanci. Tipično, ključ se kreira s ograničenim životnim vijekom, to se postiže korištenjem značajke isteka koja je dostupna u Redis-u, tako da prije ili kasnije ovaj ključ se oslobađa (svojstvo 2 na našoj listi). Kada klijent treba da oslobodi resurs, briše ključ.

Na prvi pogled ovo rješenje funkcionira prilično dobro, ali postoji problem: naša arhitektura stvara jednu tačku kvara. Šta se dešava ako host Redis instanca ne uspije? Onda dodajmo roba! I mi ćemo ga koristiti ako prezenter nije dostupan. Nažalost, ova opcija nije održiva. Radeći ovo, nećemo moći pravilno implementirati svojstvo međusobnog isključivanja koje nam je potrebno da osiguramo sigurnost, jer je replikacija u Redis-u asinhrona.

Očigledno, u takvom modelu dolazi do stanja trke:

  1. Klijent A preuzima bravu na masteru.
  2. Master ne radi prije nego što se unos ključa prenese na slave.
  3. Sljedbenik se unapređuje u lidera.
  4. Klijent B preuzima zaključavanje na istom resursu koji je A već zaključao. KRŠENJE SIGURNOSTI!

Ponekad je sasvim normalno da u posebnim okolnostima, kao što je kvar, mnogi klijenti mogu držati bravu u isto vrijeme. U takvim slučajevima može se primijeniti rješenje zasnovano na replikaciji. U suprotnom, preporučujemo rješenje opisano u ovom članku.

Ispravna implementacija sa jednom instancom

Prije nego pokušamo prevladati nedostatke gore opisane konfiguracije jedne instance, hajde da shvatimo kako pravilno postupati s ovim jednostavnim slučajem, budući da je ovo rješenje zapravo važeće u aplikacijama u kojima je uvjet trke prihvatljiv s vremena na vrijeme, kao i zbog blokiranja na pojedinačna instanca služi kao osnova koja se koristi u distribuiranom algoritmu opisanom ovdje.

Da dobijete bravu, uradite ovo:

SET resource_name my_random_value NX PX 30000

Ova komanda instalira ključ samo ako već ne postoji (NX opcija), s periodom valjanosti od 30000 milisekundi (PX opcija). Ključ je postavljen na “myrandomvalue" Ova vrijednost mora biti jedinstvena za sve klijente i sve zahtjeve za zaključavanje.
U osnovi, nasumična vrijednost se koristi za sigurno otpuštanje brave, sa skriptom koja govori Redis-u: uklonite ključ samo ako postoji i vrijednost pohranjena u njemu je upravo ono što se očekivalo. Ovo se postiže korištenjem sljedeće Lua skripte:

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

Ovo je važno kako bi se spriječilo uklanjanje brave koju drži drugi klijent. Na primjer, klijent može dobiti bravu, zatim se zaključati u nekoj operaciji koja traje duže od prve brave (tako da ključ ima vremena da istekne), a kasnije ukloni bravu koju je neki drugi klijent postavio.
Korištenje jednostavnog DEL-a nije sigurno jer klijent može ukloniti zaključavanje koje drži drugi klijent. Nasuprot tome, kada koristite gornju skriptu, svaka brava je “potpisana” nasumičnim nizom, tako da samo klijent koji ju je prethodno postavio može ukloniti.

Šta bi trebao biti ovaj nasumični niz? Pretpostavljam da bi trebalo biti 20 bajtova iz /dev/urandom, ali možete pronaći jeftinije načine da string učinite dovoljno jedinstvenim za vaše potrebe. Na primjer, bilo bi u redu zasjeti RC4 sa /dev/urandom i zatim generirati pseudo-slučajni stream iz njega. Jednostavnije rješenje uključuje kombinaciju unix vremena u mikrosekundnoj rezoluciji plus ID klijenta; nije tako siguran, ali je vjerovatno dorastao zadatku u većini konteksta.

Vrijeme koje koristimo kao mjera životnog vijeka ključa naziva se "životni vijek brave". Ova vrijednost je i količina vremena prije nego što se zaključavanje automatski otpusti i količina vremena koje klijent mora dovršiti operaciju prije nego što drugi klijent može zauzvrat zaključati taj resurs, bez stvarnog kršenja garancija međusobnog isključivanja. Ova garancija je ograničena samo na određeni vremenski period, koji počinje od trenutka kupovine brave.

Dakle, razgovarali smo o dobrom načinu za preuzimanje i otpuštanje brave. Sistem (ako govorimo o nedistribuiranom sistemu koji se sastoji od jedne i uvijek dostupne instance) je siguran. Proširimo ovaj koncept na distribuirani sistem, gdje nemamo takve garancije.

Redlock algoritam

Distribuirana verzija algoritma pretpostavlja da imamo N Redis mastera. Ovi čvorovi su potpuno nezavisni jedan od drugog, tako da ne koristimo replikaciju ili bilo koji drugi sistem implicitne koordinacije. Već smo pokrili kako sigurno dobiti i otpustiti zaključavanje na jednoj instanci. Uzimamo zdravo za gotovo da će algoritam, kada radi sa jednom instancom, koristiti upravo ovu metodu. U našim primjerima postavili smo N na 5, što je razumna vrijednost. Stoga ćemo morati da koristimo 5 Redis mastera na različitim računarima ili virtuelnim mašinama kako bismo osigurali da deluju uglavnom nezavisno jedan od drugog.

Da bi stekao bravu, klijent izvodi sljedeće operacije:

  1. Dobiva trenutno vrijeme u milisekundama.
  2. Uzastopno pokušava dobiti zaključavanje na svih N instanci, koristeći isto ime ključa i nasumične vrijednosti u svim slučajevima. U fazi 2, kada klijent postavlja zaključavanje za svaku instancu, klijent koristi odgodu da je dobije dovoljno kratko u usporedbi s vremenom nakon kojeg se zaključavanje automatski oslobađa. Na primjer, ako je trajanje blokiranja 10 sekundi, onda kašnjenje može biti u rasponu od ~5-50 milisekundi. Ovo eliminira situaciju u kojoj bi klijent mogao ostati blokiran duže vrijeme pokušavajući doći do neuspjelog Redis čvora: ako je instanca nedostupna, pokušavamo se povezati s drugom instancom što je prije moguće.
  3. Da bi preuzeo bravu, klijent izračunava koliko je vremena prošlo; Da bi to uradio, oduzima od stvarne vremenske vrednosti vremensku oznaku koja je dobijena u koraku 1. Ako i samo ako je klijent uspeo da dobije zaključavanje na većini instanci (najmanje 3), i ukupno vreme potrebno za dobijanje zaključavanja, manje od trajanja zaključavanja, zaključavanje se smatra postignutim.
  4. Ako je zaključavanje postignuto, trajanje zaključavanja se uzima kao originalno trajanje zaključavanja minus proteklo vrijeme izračunato u koraku 3.
  5. Ako klijent iz nekog razloga ne uspije dobiti zaključavanje (ili nije mogao zaključati N/2+1 instance, ili je trajanje zaključavanja bilo negativno), tada će pokušati otključati sve instance (čak i one za koje je mislio da ne može blokirati ).

Da li je algoritam asinhroni?

Ovaj algoritam se temelji na pretpostavci da, iako ne postoji sinkronizirani sat na kojem bi svi procesi radili, lokalno vrijeme u svakom procesu i dalje teče približno istim tempom, a greška je mala u odnosu na ukupno vrijeme nakon kojeg se zaključava automatski otpušten. Ova pretpostavka je vrlo slična situaciji tipičnoj za obične računare: svaki računar ima lokalni sat, a obično možemo računati na činjenicu da je vremenska razlika između različitih računara mala.

U ovom trenutku moramo pažljivije formulirati naše pravilo međusobnog isključenja: uzajamno isključenje je zagarantovano samo ako klijent koji drži bravu izađe za vrijeme dok je zaključavanje važeće (ova vrijednost dobijena u koraku 3), minus još neko vrijeme (ukupno nekoliko milisekundi za kompenzaciju vremenske razlike između procesa).

Sljedeći zanimljiv članak govori više o takvim sistemima koji zahtijevaju koordinaciju vremenskih intervala: Iznajmljivanje: efikasan mehanizam otporan na greške za konzistentnost distribuirane keš memorije datoteka.

Pokušajte ponovo u slučaju neuspjeha

Kada klijent ne uspije dobiti zaključavanje, mora pokušati ponovo nakon nasumične odgode; ovo se radi kako bi se desinhroniziralo više klijenata koji pokušavaju da steknu zaključavanje istog resursa u isto vrijeme (što može dovesti do situacije "podijeljenog mozga" u kojoj nema pobjednika). Osim toga, što brže klijent pokušava da zaključa većinu Redis instanci, to je uži prozor u kojem može doći do situacije podijeljenog mozga (i manja je potreba za ponovnim pokušajima). Stoga, u idealnom slučaju, klijent bi trebao pokušati poslati SET komande na N instanci istovremeno koristeći multipleksiranje.

Ovdje je vrijedno naglasiti koliko je važno da klijenti koji ne uspiju steći većinu brava otpuste (djelomično) stečene brave, kako ne bi morali čekati da ključ istekne prije nego što se brava na resursu može ponovo nabaviti (iako ako dođe do fragmentacije mreže, a klijent izgubi kontakt sa Redis instancama, tada morate platiti kaznu dostupnosti dok čekate da ključ istekne).

Otpustite bravu

Otključavanje je jednostavna operacija koja jednostavno zahtijeva otključavanje svih instanci, bez obzira na to da li se čini da je klijent uspješno zaključao određenu instancu.

Sigurnosna razmatranja

Da li je algoritam bezbedan? Pokušajmo zamisliti šta se dešava u različitim scenarijima.

Za početak, pretpostavimo da je klijent uspio dobiti zaključavanje na većini instanci. Svaka instanca će sadržavati ključ s istim vijekom trajanja za sve. Međutim, svaki od ovih ključeva je instaliran u različito vrijeme, tako da će isteći u različito vrijeme. Ali, ako je prvi ključ instaliran u vrijeme koje nije gore od T1 (vrijeme koje biramo prije kontaktiranja prvog servera), a posljednji ključ instaliran u vrijeme koje nije gore od T2 (vrijeme u kojem je primljen odgovor sa posljednjeg servera), onda smo uvjereni da će prvi ključ u setu koji ističe preživjeti barem MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Svi ostali ključevi će isteći kasnije, tako da možemo biti sigurni da će svi ključevi istovremeno važiti barem ovaj put.

Za vrijeme dok većina ključeva ostane važeća, drugi klijent neće moći preuzeti bravu, jer N/2+1 SET NX operacije ne mogu uspjeti ako već postoji N/2+1 ključeva. Stoga, kada je brava jednom stečena, nemoguće je ponovo je steći u istom trenutku (ovo bi narušilo svojstvo međusobnog isključivanja).
Međutim, želimo da budemo sigurni da više klijenata koji pokušavaju da zaključaju u isto vreme ne mogu da uspeju u isto vreme.

Ako je klijent zaključao većinu instanci otprilike ili duže od maksimalnog trajanja zaključavanja, smatrat će zaključavanje nevažećim i otključati instance. Stoga moramo uzeti u obzir samo slučaj u kojem je klijent uspio blokirati većinu instanci u vremenu kraćem od isteka roka. U ovom slučaju, u vezi sa gornjim argumentom, tokom vremena MIN_VALIDITY nijedan klijent ne bi trebao biti u mogućnosti da ponovo preuzme bravu. Stoga će mnogi klijenti moći zaključati N/2+1 instance u isto vrijeme (koje se završava na kraju faze 2) samo kada je vrijeme za zaključavanje većine bilo veće od TTL vremena, što zaključavanje čini nevažećim.

Možete li pružiti formalni dokaz sigurnosti, naznačiti postojeće slične algoritme ili pronaći grešku u gore navedenom?

Razmatranja pristupačnosti

Dostupnost sistema zavisi od tri glavne karakteristike:

  1. Automatsko otpuštanje brava (kako ključevi ističu): ključevi će na kraju ponovo biti dostupni za korištenje za brave.
  2. Činjenica da klijenti obično pomažu jedni drugima uklanjanjem brave kada željena brava nije stečena, ili je stečena, a posao je završen; tako da je vjerovatno da nećemo morati čekati da ključevi isteknu da bismo ponovo preuzeli bravu.
  3. Činjenica da kada klijent treba ponovo da pokuša da preuzme zaključavanje, on čeka relativno duže vreme od perioda potrebnog za preuzimanje većine brava. Ovo smanjuje vjerovatnoću da dođe do situacije podijeljenog mozga kada se nadmeće za resurse.

Međutim, postoji kazna dostupnosti jednaka TTL-u mrežnih segmenata, tako da ako postoje susjedni segmenti, kazna može biti neograničena. Ovo se dešava kad god klijent stekne bravu, a zatim pređe na drugi segment prije nego što ga otpusti.

U principu, s obzirom na beskonačno susedne mrežne segmente, sistem može ostati nedostupan beskonačan vremenski period.

Performanse, prelazak na grešku i fsync

Mnogi ljudi koriste Redis jer su im potrebne visoke performanse servera zaključavanja u smislu kašnjenja potrebnog za preuzimanje i otpuštanje zaključavanja i broja preuzimanja/otpuštanja koji se mogu završiti u sekundi. Da bi se ispunio ovaj zahtjev, postoji strategija za komunikaciju sa N Redis serverima radi smanjenja kašnjenja. Ovo je strategija multipleksiranja (ili "multipleksiranje siromaha", gdje se utičnica stavlja u neblokirajući način, šalje sve komande i čita komande kasnije, pod pretpostavkom da je vrijeme povratnog putovanja između klijenta i svake instance slično) .

Međutim, također moramo uzeti u obzir razmatranje povezano s dugoročnim pohranjivanjem podataka ako težimo kreiranju modela s pouzdanim oporavkom od kvarova.

U suštini, da razjasnimo problem, pretpostavimo da smo konfigurisali Redis bez dugotrajnog skladištenja podataka. Klijent uspijeva blokirati 3 od 5 instanci. Jedna od instanci koju je klijent uspio blokirati se ponovo pokreće i u ovom trenutku postoje ponovo 3 instance za isti resurs, koje možemo blokirati, a drugi klijent može zauzvrat blokirati ponovo pokrenutu instancu, kršeći sigurnosno svojstvo koje pretpostavlja ekskluzivnost brava.

Ako omogućite podatke unaprijed (AOF), situacija će se malo poboljšati. Na primjer, možete promovirati server slanjem naredbe SHUTDOWN i ponovnim pokretanjem. Budući da su operacije isteka u Redis-u semantički implementirane na način da vrijeme nastavlja teći čak i kada je server isključen, svi naši zahtjevi su u redu. Ovo je normalno sve dok je osigurano normalno gašenje. Šta učiniti u slučaju nestanka struje? Ako je Redis konfiguriran po defaultu, sa fsync sinhronizacijom na disku svake sekunde, onda je moguće da nakon ponovnog pokretanja nećemo imati svoj ključ. Teoretski, ako želimo da garantujemo sigurnost zaključavanja tokom ponovnog pokretanja bilo koje instance, trebalo bi da omogućimo fsync=always u postavkama za dugotrajno skladištenje podataka. Ovo će potpuno ubiti performanse, sve do nivoa CP sistema koji se tradicionalno koriste za sigurnu implementaciju distribuiranih brava.

Ali situacija je bolja nego što se čini na prvi pogled. U principu, sigurnost algoritma je očuvana jer kada se instanca ponovo pokrene nakon kvara, ona više ne učestvuje ni u jednom zaključavanju koje je trenutno aktivno.

Da bismo to osigurali, samo trebamo osigurati da nakon kvara instanca ostane nedostupna neko vrijeme koje neznatno premašuje maksimalni TTL koji koristimo. Na ovaj način ćemo čekati do isteka roka trajanja i automatskog otpuštanja svih ključeva koji su bili aktivni u trenutku kvara.

Korištenjem odgođenih ponovnih pokretanja, u principu je moguće postići sigurnost čak i u odsustvu dugoročne postojanosti u Redis-u. Imajte na umu, međutim, da to može rezultirati novčanom kaznom za kršenje pristupačnosti. Na primjer, ako većina instanci ne uspije, sistem će postati globalno nedostupan za TTL (i nijedan resurs ne može biti blokiran za to vrijeme).

Povećavamo dostupnost algoritma: proširujemo blokiranje

Ako se posao koji obavljaju klijenti sastoji od malih koraka, moguće je smanjiti zadano trajanje zaključavanja i implementirati mehanizam za proširenje zaključavanja. U principu, ako je klijent zauzet računanjem i vrijednost isteka zaključavanja je opasno niska, možete poslati Lua skriptu svim instancama koja proširuje TTL ključa ako ključ još uvijek postoji i njegova vrijednost je i dalje nasumična vrijednost dobivena kada brava je nabavljena.

Klijent bi trebao uzeti u obzir da se zaključavanje ponovo preuzima samo ako je uspio zaključati većinu instanci unutar perioda važenja.

Istina, tehnički se algoritam ne mijenja, tako da maksimalan broj ponovljenih pokušaja stjecanja zaključavanja mora biti ograničen, inače će svojstva pristupačnosti biti narušena.

izvor: www.habr.com

Dodajte komentar