ProHoster > Blog > uprava > Distribuirano zaključavanje pomoću Redisa

Distribuirano zaključavanje pomoću Redisa

Hej Habr!

Danas vam predstavljamo prijevod složenog članka o implementaciji distribuiranog zaključavanja pomoću Redisa i pozivamo vas da razgovarate o izgledima Redisa kao teme. Analiza dotičnog algoritma Redlock od Martina Kleppmanna, autora knjige "Prijave s velikim opterećenjem", dano здесь.

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

Postoje brojne knjižnice i postovi koji opisuju kako implementirati DLM (Distributed Lock Manager) pomoću Redisa, ali svaka knjižnica ima drugačiji pristup, a jamstva koja pružaju prilično su slaba u usporedbi s onim što je moguće postići s malo sofisticiranijim dizajnom.

U ovom ćemo članku pokušati opisati uvjetni kanonski algoritam koji pokazuje kako implementirati distribuirano zaključavanje pomoću Redisa. Govorit ćemo o algoritmu tzv Redlock, implementira distribuirani upravitelj zaključavanja i, po našem mišljenju, ovaj je algoritam sigurniji od uobičajenog pristupa s jednom instancom. Nadamo se da će ga zajednica analizirati, dati povratne informacije i koristiti kao polazište za složenije ili alternativne projekte.

Implementacija

Prije nego prijeđemo na opis algoritma, nudimo nekoliko poveznica na gotove implementacije. Mogu se koristiti kao referenca.

Jamstva sigurnosti i dostupnosti

Modelirat ćemo naš dizajn sa samo tri svojstva za koja mislimo da pružaju minimalna jamstva potrebna za učinkovito korištenje distribuiranog zaključavanja.

  1. Sigurnosno svojstvo: Uzajamno isključivanje. U bilo kojem trenutku samo jedan klijent može drž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 sleti na drugi segment diska.
  3. Svojstvo dostupnosti B: Tolerancija greške. Sve dok većina Redis čvorova radi, klijenti mogu nabaviti i otpustiti zaključavanja.

Zašto implementacija temeljena na oporavku od kvara nije dovoljna u ovom slučaju
Da bismo razumjeli što ćemo poboljšati, analizirajmo trenutno stanje s većinom distribuiranih biblioteka za zaključavanje temeljenih na Redisu.

Najjednostavniji način za zaključavanje resursa pomoću Redisa je stvaranje ključa u instanci. Tipično, ključ se stvara s ograničenim vijekom trajanja, to se postiže korištenjem značajke isteka koja je dostupna u Redisu, tako da se prije ili kasnije ovaj ključ izda (svojstvo 2 na našem popisu). Kada klijent treba osloboditi resurs, on briše ključ.

Na prvi pogled, ovo rješenje radi prilično dobro, ali postoji problem: naša arhitektura stvara jednu točku kvara. Što se događa ako host Redis instanca ne uspije? Dodajmo onda roba! I koristit ćemo ga ako prezenter nije dostupan. Nažalost, ova opcija nije održiva. Čineći to, nećemo moći ispravno implementirati svojstvo međusobnog isključivanja koje nam je potrebno za osiguranje sigurnosti, jer je replikacija u Redisu asinkrona.

Očito, u takvom modelu dolazi do stanja utrke:

  1. Klijent A stječe zaključavanje nadređenog.
  2. Glavni otkaže prije nego što se unos ključa prenese na podređeni.
  3. Sljedbenik se promiče u vođu.
  4. Klijent B stječe zaključavanje istog resursa koji je A već zaključao. KRŠENJE SIGURNOSTI!

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

Ispravna implementacija s jednom instancom

Prije nego što pokušamo prevladati nedostatke gore opisane konfiguracije s jednom instancom, shvatimo kako pravilno postupati s ovim jednostavnim slučajem, budući da je ovo rješenje zapravo važeće u aplikacijama gdje je stanje utrke prihvatljivo s vremena na vrijeme, a također i zato što blokiranje na jedna instanca služi kao osnova koja se koristi u ovdje opisanom distribuiranom algoritmu.

Da biste dobili zaključavanje, učinite sljedeće:

SET resource_name my_random_value NX PX 30000

Ova naredba instalira ključ samo ako već ne postoji (NX opcija), s rokom 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 otključavanje, sa skriptom koja govori Redisu: uklonite ključ samo ako postoji i ako je vrijednost pohranjena u njemu točno ono što se očekivalo. To se postiže pomoću 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 zaključavanje, zatim postati zaključan u nekoj operaciji koja traje dulje od prvog zaključavanja (tako da ključ ima vremena da istekne), a kasnije ukloniti zaključavanje koje je postavio neki drugi klijent.
Korištenje jednostavnog DEL-a nije sigurno jer klijent može ukloniti zaključavanje drugog klijenta. Nasuprot tome, kada koristite gornju skriptu, svaka brava je "potpisana" nasumičnim nizom, tako da je samo klijent koji ju je prethodno postavio može ukloniti.

Što bi trebao biti ovaj slučajni niz? Pretpostavljam da bi trebao biti 20 bajtova iz /dev/urandom, ali možete pronaći jeftinije načine da niz učinite dovoljno jedinstvenim za svoje potrebe. Na primjer, bilo bi dobro zasijati RC4 s /dev/urandom i zatim iz njega generirati pseudo-nasumični tok. Jednostavnije rješenje uključuje kombinaciju unix vremena u mikrosekundnoj rezoluciji plus ID klijenta; nije toliko siguran, ali je vjerojatno dorastao zadatku u većini konteksta.

Vrijeme koje koristimo kao mjeru ž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 koju klijent mora dovršiti operaciju prije nego što drugi klijent može zauzvrat zaključati taj resurs, bez stvarnog kršenja jamstava međusobnog isključivanja. Ovo jamstvo je ograničeno samo na određeni vremenski okvir, koji počinje od trenutka kupnje brave.

Dakle, razgovarali smo o dobrom načinu za dobivanje i otpuštanje brave. Sustav (ako govorimo o nedistribuiranom sustavu koji se sastoji od jedne i uvijek dostupne instance) je siguran. Proširimo ovaj koncept na distribuirani sustav, gdje nemamo takva jamstva.

Redlock algoritam

Distribuirana verzija algoritma pretpostavlja da imamo N Redis mastera. Ovi su čvorovi potpuno neovisni jedni o drugima, tako da ne koristimo replikaciju ili bilo koji drugi implicitni sustav koordinacije. Već smo pokrili kako sigurno nabaviti i otpustiti zaključavanje na jednoj instanci. Uzimamo zdravo za gotovo da će algoritam, kada radi s jednom instancom, koristiti upravo ovu metodu. U našim smo primjerima postavili N na 5, što je razumna vrijednost. Stoga ćemo trebati koristiti 5 Redis mastera na različitim računalima ili virtualnim strojevima kako bismo osigurali da djeluju uglavnom neovisno jedan o drugom.

Za dobivanje zaključavanja, klijent izvodi sljedeće operacije:

  1. Dobiva trenutno vrijeme u milisekundama.
  2. Sekvencijalno pokušava dobiti zaključavanje na svih N instanci, koristeći isti naziv ključa i nasumične vrijednosti u svim slučajevima. U fazi 2, kada klijent postavlja zaključavanje za svaku instancu, klijent koristi odgodu za dobivanje koja je dovoljno kratka u usporedbi s vremenom nakon kojeg se zaključavanje automatski otpušta. Na primjer, ako je trajanje blokiranja 10 sekundi, tada bi kašnjenje moglo biti u rasponu od ~5-50 milisekundi. Ovo eliminira situaciju u kojoj bi klijent mogao ostati blokiran dulje 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 učinio, od stvarne vremenske vrijednosti oduzima vremensku oznaku koja je dobivena u koraku 1. Ako i samo ako je klijent uspio dobiti zaključavanje na većini instanci (najmanje 3) i ukupno vrijeme koje je bilo potrebno za dobiti zaključavanje, manje od trajanja zaključavanja, smatra se da je zaključavanje dobiveno.
  4. Ako je zaključavanje stečeno, trajanje zaključavanja se uzima kao izvorno 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 ).

Je li algoritam asinkroni?

Ovaj se algoritam 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 pogreška je mala u usporedbi s ukupnim vremenom nakon kojeg je zaključavanje automatski pušten. Ova pretpostavka je vrlo slična situaciji tipičnoj za obična računala: svako računalo ima lokalni sat, a obično možemo računati na činjenicu da je vremenska razlika između različitih računala mala.

U ovom trenutku moramo pažljivije formulirati naše pravilo uzajamnog isključivanja: uzajamno isključivanje je zajamčeno samo ako klijent koji drži zaključavanje izađe tijekom vremena koje je zaključavanje važeće (ova vrijednost dobivena 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 sustavima koji zahtijevaju koordinaciju vremenskih intervala: Najam: učinkovit mehanizam otporan na pogreške za dosljednost distribuirane predmemorije datoteka.

Pokušaj ponovno u slučaju neuspjeha

Kada klijent ne uspije dobiti zaključavanje, mora pokušati ponovno nakon nasumičnog kašnjenja; ovo se radi kako bi se de-sinkroniziralo više klijenata koji pokušavaju dobiti zaključavanje na istom resursu u isto vrijeme (što može dovesti do situacije "podijeljenog mozga" u kojoj nema pobjednika). Osim toga, što brže klijent pokuša zaključati većinu instanci Redisa, to je uži prozor u kojem se može dogoditi situacija podijeljenog mozga (i manja je potreba za ponovnim pokušajima). Stoga bi u idealnom slučaju klijent trebao pokušati poslati naredbe SET na N instanci istovremeno koristeći multipleksiranje.

Ovdje vrijedi naglasiti koliko je važno da klijenti koji ne uspiju steći većinu zaključavanja oslobode (djelomično) stečena zaključavanja, tako da ne moraju čekati da ključ istekne prije nego što se zaključavanje resursa može ponovno steći. (iako dođe do fragmentacije mreže i klijent izgubi kontakt s instancama Redisa, 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 čini li se da je klijent uspješno zaključao određenu instancu.

Sigurnosna razmatranja

Je li algoritam siguran? Pokušajmo zamisliti što se događa u različitim scenarijima.

Za početak, pretpostavimo da je klijent uspio dobiti zaključavanje većine instanci. Svaka će instanca sadržavati ključ s istim vijekom trajanja za sve. Međutim, svaki od ovih ključeva instaliran je u različito vrijeme, pa će isteći u različito vrijeme. Ali, ako je prvi ključ instaliran u vrijeme koje nije gore od T1 (vrijeme koje smo odabrali prije kontaktiranja prvog poslužitelja), a zadnji ključ je instaliran u vrijeme koje nije gore od T2 (vrijeme u kojem je primljen odgovor od posljednjeg poslužitelja), tada smo uvjereni da će prvi ključ u skupu koji istekne preživjeti barem MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Svi ostali ključevi istječu kasnije, tako da možemo biti sigurni da će svi ključevi istovremeno biti valjani barem ovo vrijeme.

Tijekom vremena dok većina ključeva ostaje valjana, drugi klijent neće moći preuzeti zaključavanje, budući da N/2+1 SET NX operacija ne može uspjeti ako N/2+1 ključeva već postoji. Stoga, jednom kad je zaključavanje stečeno, nemoguće ga je ponovno steći u istom trenutku (ovo bi prekršilo svojstvo međusobnog isključivanja).
Međutim, želimo biti sigurni da više klijenata koji pokušavaju dobiti zaključavanje u isto vrijeme ne može uspjeti u isto vrijeme.

Ako je klijent zaključao većinu instanci na približno ili dulje 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 datuma isteka. U ovom slučaju, s obzirom na gornji argument, tijekom vremena MIN_VALIDITY niti jedan klijent ne bi trebao moći ponovno preuzeti zaključavanje. Stoga će mnogi klijenti moći zaključati N/2+1 instanci u isto vrijeme (koje 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 službeni dokaz sigurnosti, naznačiti postojeće slične algoritme ili pronaći grešku u gore navedenom?

Razmatranja pristupačnosti

Dostupnost sustava ovisi o tri glavne karakteristike:

  1. Automatski otključaj brave (kako ključevi isteknu): ključevi će na kraju opet biti dostupni za korištenje za zaključavanje.
  2. Činjenica da klijenti obično pomažu jedni drugima skidanjem brava kada željena brava nije dobivena ili je nabavljena i posao je završen; pa je vjerojatno da nećemo morati čekati da ključevi isteknu kako bismo ponovno preuzeli bravu.
  3. Činjenica da kada klijent treba ponovno pokušati dobiti zaključavanje, čeka relativno dulje vrijeme od razdoblja potrebnog za preuzimanje većine zaključavanja. To smanjuje vjerojatnost pojave situacije podijeljenog mozga kada se natječu 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. To se događa svaki put kada klijent dobije zaključavanje i zatim otkida na drugi segment prije nego što ga može otpustiti.

U načelu, s obzirom na beskonačne kontinualne mrežne segmente, sustav može ostati nedostupan beskonačno dugo.

Performanse, failover i fsync

Mnogi ljudi koriste Redis jer im je potrebna visoka izvedba poslužitelja za zaključavanje u smislu latencije potrebne za dobivanje i otpuštanje zaključavanja, te broj preuzimanja/otpuštanja koji se mogu izvršiti u sekundi. Kako bi se ispunio ovaj zahtjev, postoji strategija za komunikaciju s N Redis poslužiteljima kako bi se smanjila latencija. Ovo je strategija multipleksiranja (ili "multipleksiranje jadnika", gdje se utičnica stavlja u način rada bez blokiranja, šalje sve naredbe i čita naredbe 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 dugotrajnom pohranom podataka ako nastojimo stvoriti model s pouzdanim oporavkom od kvarova.

Uglavnom, da razjasnimo problem, pretpostavimo da konfiguriramo Redis bez ikakve dugoročne pohrane podataka. Klijent uspijeva blokirati 3 od 5 instanci. Jedna od instanci koju je klijent uspio blokirati ponovno se pokreće, au ovom trenutku ponovno postoje 3 instance za isti resurs, koje možemo blokirati, a drugi klijent može zauzvrat blokirati ponovno pokrenutu instancu, kršeći sigurnosno svojstvo koje pretpostavlja ekskluzivnost brava.

Ako omogućite podatke unaprijed (AOF), situacija će se malo popraviti. Na primjer, možete promovirati poslužitelj slanjem naredbe SHUTDOWN i ponovnim pokretanjem. Budući da su operacije isteka u Redisu semantički implementirane na takav način da vrijeme nastavlja teći čak i kada je poslužitelj isključen, svi naši zahtjevi su u redu. To je normalno sve dok je osigurano normalno isključivanje. Što učiniti u slučaju nestanka struje? Ako je Redis konfiguriran prema zadanim postavkama, s fsync-om koji se svake sekunde sinkronizira na disku, tada je moguće da nakon ponovnog pokretanja nećemo imati svoj ključ. Teoretski, ako želimo jamčiti sigurnost zaključavanja tijekom bilo kojeg ponovnog pokretanja instance, trebali bismo omogućiti fsync=always u postavkama za dugotrajnu pohranu podataka. To će u potpunosti uništiti performanse, sve do razine CP sustava koji se tradicionalno koriste za sigurnu implementaciju distribuiranih zaključavanja.

Ali situacija je bolja nego što se na prvi pogled čini. U načelu, sigurnost algoritma je očuvana jer kada se instanca ponovno pokrene nakon kvara, više ne sudjeluje 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 malo premašuje maksimalni TTL koji koristimo. Na taj način ćemo pričekati do datuma isteka i automatskog oslobađanja svih ključeva koji su bili aktivni u trenutku kvara.

Korištenjem odgođenih ponovnih pokretanja načelno je moguće postići sigurnost čak i u odsutnosti bilo kakve dugotrajne postojanosti u Redisu. Međutim, imajte na umu da to može rezultirati novčanom kaznom za kršenje pristupačnosti. Na primjer, ako većina instanci ne uspije, sustav će postati globalno nedostupan za TTL (i niti jedan resurs se ne može blokirati tijekom tog vremena).

Povećavamo dostupnost algoritma: produljujemo blokadu

Ako se posao koji obavljaju klijenti sastoji od malih koraka, moguće je smanjiti zadano trajanje zaključavanja i implementirati mehanizam za produljenje zaključavanja. U načelu, 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 još uvijek nasumična vrijednost dobivena kada brava je nabavljena.

Klijent bi trebao uzeti u obzir ponovno preuzimanje zaključavanja samo ako je uspio zaključati većinu instanci unutar razdoblja valjanosti.

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

Izvor: www.habr.com

Dodajte komentar