ProHoster > Blog > Administrazioa > Banatutako blokeoa Redis erabiliz

Banatutako blokeoa Redis erabiliz

Aupa Habr!

Gaur Redis erabiliz blokeo banatua ezartzeari buruzko artikulu konplexu baten itzulpena ekarriko dizugu eta Redis-en aukerak gai gisa hitz egitera gonbidatzen zaitugu. Martin Kleppmann liburuaren egileak egindako Redlock algoritmoaren azterketa.Karga Handiko Aplikazioak", emana Hemen.

Blokeo banatua ingurune askotan erabiltzen den primitibo oso erabilgarria da, non prozesu ezberdinek partekatutako baliabideetan modu esklusiboan lan egin behar duten.

Hainbat liburutegi eta argitalpen daude Redis erabiliz DLM (Distributed Lock Manager) nola inplementatu deskribatzen dutenak, baina liburutegi bakoitzak ikuspegi desberdina hartzen du eta eskaintzen dituzten bermeak nahiko ahulak dira diseinu apur bat sofistikatuagoarekin lor daitekeenarekin alderatuta.

Artikulu honetan Redis erabiliz blokeo banatua nola inplementatu erakusten duen algoritmo kanoniko baldintzatua deskribatzen saiatuko gara. izeneko algoritmo bati buruz hitz egingo dugu Redlock, banatutako blokeoen kudeatzailea ezartzen du eta, gure ustez, algoritmo hau instantzia bakarreko ohiko ikuspegia baino seguruagoa da. Espero dugu komunitateak aztertzea, iritzia ematea eta proiektu konplexuago edo alternatiboetarako abiapuntu gisa erabiltzea.

Ezarpena

Algoritmoaren deskribapenari ekin aurretik, prest dauden inplementazioetarako hainbat esteka eskaintzen ditugu. Erreferentziarako erabil daitezke.

Segurtasun eta Eskuragarritasun Bermeak

Gure diseinua hiru propietaterekin modelatuko dugu, gure ustez blokeo banatua modu eraginkorrean erabiltzeko behar diren gutxieneko bermeak ematen dituztela.

  1. Segurtasun ondasunak: Elkarrekiko bazterketa. Une bakoitzean, bezero bakarrak eduki dezake blokeoa.
  2. Erabilgarritasuna A jabetza: blokeorik ez. Beti posible da azkenean blokeoa eskuratzea, nahiz eta baliabidea blokeatu duen bezeroak huts egin edo beste disko-segmentu batean lurreratu.
  3. Erabilgarritasuna B propietatea: akatsen tolerantzia. Redis nodo gehienak exekutatzen ari diren bitartean, bezeroek blokeoak eskuratu eta askatu ditzakete.

Zergatik hutsegiteen berreskurapenean oinarritutako inplementazioa ez da nahikoa kasu honetan
Zer hobetuko dugun ulertzeko, aztertu dezagun Redis-en oinarritutako blokeo-liburutegi banatuenen egungo egoera.

Redis erabiliz baliabide bat blokeatzeko modurik errazena instantzian gako bat sortzea da. Normalean, bizitza-iraupen mugatuko gako bat sortzen da, hau Redis-en emandako iraungitze funtzioa erabiliz lortzen da, beraz, lehenago edo beranduago, gako hau askatzen da (gure zerrendako 2. jabetza). Bezeroak baliabidea askatu behar duenean, gakoa ezabatzen du.

Lehen begiratuan, irtenbide honek nahiko ondo funtzionatzen du, baina arazo bat dago: gure arkitekturak huts-puntu bakarra sortzen du. Zer gertatzen da ostalariaren Redis instantzia huts egiten badu? Gehi dezagun esklabo bat orduan! Eta aurkezlea erabilgarri ez badago erabiliko dugu. Zoritxarrez, aukera hau ez da bideragarria. Hori eginez gero, ezingo dugu behar bezala inplementatu segurtasuna bermatzeko behar dugun elkarrekiko bazterketa propietatea, Redis-en erreplikazioa asinkronoa delako.

Jakina, eredu horretan lasterketa-baldintza bat gertatzen da:

  1. A bezeroak blokeoa eskuratzen du maisuan.
  2. Maisuak huts egiten du gako-sarrera esklaboari transferitu aurretik.
  3. Jarraitzailea liderra igotzen da.
  4. B bezeroak blokeo bat eskuratzen du A dagoeneko blokeatu duen baliabide berean. SEGURTASUN URRATZEA!

Batzuetan guztiz normala da egoera berezietan, hala nola hutsegite batean, bezero askok blokeoa aldi berean edukitzea. Kasu horietan, errepliketan oinarritutako irtenbide bat aplika daiteke. Bestela, artikulu honetan deskribatutako irtenbidea gomendatzen dugu.

Inplementazio zuzena instantzia bakar batekin

Goian deskribatutako instantzia bakarreko konfigurazioaren gabeziak gainditzen saiatu aurretik, uler dezagun kasu sinple hau behar bezala nola kudeatu, izan ere, soluzio hau baliozkoa baita noizean behin lasterketa-baldintza bat onargarria den aplikazioetan, eta baita batean blokeatzea ere. instantzia bakarra hemen deskribatutako algoritmo banatuan erabiltzen den oinarri gisa balio du.

Blokeo bat eskuratzeko, egin hau:

SET resource_name my_random_value NX PX 30000

Komando honek gako bat lehendik existitzen ez bada bakarrik instalatzen du (NX aukera), 30000 milisegundoko balio-epearekin (PX aukera). Gakoa "n ezarrita dagomyrandomvalue" Balio honek bakarra izan behar du bezero guztietan eta blokeo-eskaera guztietan.
Funtsean, ausazko balio bat erabiltzen da blokeoa segurtasunez askatzeko, script batek Redis-i esaten diona: kendu gakoa bakarrik badago eta bertan gordetako balioa espero zena bada. Hau Lua script hau erabiliz lortzen da:

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

Garrantzitsua da beste bezero batek duen blokeoa kentzea saihesteko. Adibidez, bezero batek sarraila bat eskura dezake, gero lehen blokeoa baino gehiago irauten duen eragiketa batean blokeatu (gakoak iraungitzeko denbora izan dezan) eta gero beste bezeroren batek jarritako blokeoa kendu.
DEL sinple bat erabiltzea ez da segurua, bezero batek beste bezero batek duen blokeoa kendu dezakeelako. Aitzitik, goiko script-a erabiltzean, blokeo bakoitza ausazko kate batekin "sinatzen" da, beraz, aurretik jarri zuen bezeroak bakarrik kendu dezake.

Zein izan behar du ausazko kate honek? Uste dut /dev/urandom-etik 20 byte izan beharko lukeela, baina modu merkeagoak aurki ditzakezu katea zure helburuetarako nahikoa bakarra izan dadin. Esate baterako, ondo legoke RC4 /dev/urandom-ekin hastea eta, ondoren, sasi-ausazko korronte bat sortzea. Irtenbide sinpleago batek unix denbora mikrosegundoko bereizmenean gehi bezeroaren IDaren konbinazioa dakar; ez da hain segurua, baina ziurrenik testuinguru gehienetan egitekoa da.

Giltzaren bizitzaren neurtzeko erabiltzen dugun denborari "blokeoaren bizitza" deitzen zaio. Balio hau blokeoa automatikoki askatu aurretik dagoen denbora eta bezero batek eragiketa bat burutzeko behar duen denbora da, beste bezero batek, berriz, baliabide hori blokeatu baino lehen, elkarrekiko bazterketa bermeak benetan urratu gabe. Berme hau denbora-leiho jakin batera mugatzen da, sarraila erosten den unetik hasten dena.

Beraz, blokeoa eskuratzeko eta askatzeko modu on bat eztabaidatu dugu. Sistema (banatu gabeko sistema batez ari bagara instantzia bakar batez eta beti eskuragarri dagoena) segurua da. Zabal dezagun kontzeptu hau sistema banatu batera, non horrelako bermerik ez dugun.

Redlock algoritmoa

Algoritmoaren bertsio banatuak N Redis maisuak ditugula suposatzen du. Nodo hauek elkarrengandik guztiz independenteak dira, beraz, ez dugu erreplika edo beste koordinazio sistema inpliziturik erabiltzen. Dagoeneko azaldu dugu instantzia bakarrean blokeo bat modu seguruan eskuratu eta askatu. Algoritmoak, instantzia bakar batekin lan egiten duenean, metodo hau zehatz-mehatz erabiliko duela uste dugu. Gure adibideetan N 5 ezarri dugu, hau da, arrazoizko balio bat. Horrela, 5 Redis maisu erabili beharko ditugu ordenagailu edo makina birtualetan ezberdinetan, neurri handi batean elkarrengandik independentean jokatzen dutela ziurtatzeko.

Blokeo bat eskuratzeko, bezeroak eragiketa hauek egiten ditu:

  1. Uneko ordua milisegundotan lortzen du.
  2. N instantzia guztietan blokeoa lortzen saiatzen da sekuentzialki, kasu guztietan gako-izen bera eta ausazko balioak erabiliz. 2. fasean, bezeroak blokeo bat konfiguratzen duenean instantzia bakoitzeko, bezeroak atzerapen bat erabiltzen du hura eskuratzeko, blokeoa automatikoki askatzen den denboraren aldean nahikoa laburra den. Adibidez, blokeoaren iraupena 10 segundokoa bada, atzerapena ~ 5-50 milisegundo artekoa izan daiteke. Horrek ezabatzen du bezeroa denbora luzez blokeatuta egon daitekeen egoera, huts egin duen Redis nodo batera iritsi nahian: instantzia erabilgarri ez badago, beste instantzia batera konektatzen saiatzen gara ahalik eta azkarren.
  3. Sarraila bat hartzeko, bezeroak zenbat denbora igaro den kalkulatzen du; Horretarako, benetako denbora-balioari 1. urratsean lortutako denbora-zigilua kentzen dio. Baldin eta bezeroak instantzia gehienetan blokeoa lortzeko gai izan bada (gutxienez 3), eta behar izan duen denbora osoa. blokeoa lortu, blokeoaren iraupena baino txikiagoa, blokeoa lortutzat jotzen da.
  4. Blokeo bat eskuratu bada, blokeoaren iraupena jatorrizko blokeoaren iraupena izango da, 3. urratsean kalkulatutako igarotako denbora kenduta.
  5. Bezeroak arrazoiren batengatik blokeoa lortzen ez badu (ezin izan zituen N/2+1 instantzia blokeatu edo blokeoaren iraupena negatiboa izan zen), instantzia guztiak desblokeatzen saiatuko da (baita blokeatu ezin zituela uste zuenak ere. ).

Algoritmoa asinkronoa al da?

Algoritmo hau, prozesu guztiek funtzionatuko luketen erloju sinkronizaturik ez dagoen arren, prozesu bakoitzean tokiko orduak oraindik ere erritmo berdinean doa, eta errorea txikia da blokeoa igarotako denbora osoaren aldean. automatikoki askatuta. Suposizio hau ordenagailu arrunten ohiko egoeraren oso antzekoa da: ordenagailu bakoitzak erloju lokal bat du, eta normalean ordenagailu ezberdinen arteko denbora-aldea txikia dela zenbatu dezakegu.

Puntu honetan, arreta handiagoz formulatu behar dugu gure elkarrekiko bazterketa-araua: elkarrekiko bazterketa bermatzen da sarraila duen bezeroa sarraila balio duen denboran irteten bada (balio hori 3. urratsean lortutakoa), denbora gehiago kenduta (guztira gutxi batzuk). milisegundoak prozesuen arteko denbora-aldea konpentsatzeko).

Ondorengo artikulu interesgarriak denbora-tarteen koordinazioa behar duten sistemei buruz gehiago kontatzen du: Errentamenduak: akatsekiko tolerantzia duen mekanismo eraginkorra, banatutako fitxategien cachearen koherentziarako.

Saiatu berriro huts egiten bada

Bezero batek blokeoa eskuratzen ez duenean, berriro saiatu behar du ausazko atzerapen baten ondoren; hau aldi berean baliabide bereko blokeoa eskuratzen saiatzen diren hainbat bezero dessinkronizatzeko egiten da (horrek irabazlerik ez dagoen "burmuin zatitu" egoerara eraman dezake). Gainera, bezero bat zenbat eta azkarrago saiatzen den blokeoa lortzen Redis-en instantzia gehienetan, orduan eta estuagoa izango da zatitutako garunaren egoera gerta daitekeen leihoa (eta txikiagoa da berriro saiakeraren beharra). Hori dela eta, hoberena, bezeroak SET komandoak bidaltzen saiatu beharko luke N instantziari aldi berean multiplexazioa erabiliz.

Hemen azpimarratzea merezi du zein garrantzitsua den sarraila gehienak eskuratzen ez dituzten bezeroek eskuratutako sarrailak (partzialki) askatzea, baliabidearen blokeoa berriro eskuratu ahal izateko giltza iraungi arte itxaron beharrik izan ez dezaten. (nahiz eta sarearen zatiketa gertatzen bada eta bezeroak Redis instantziekin kontaktua galtzen badu, erabilgarritasun-zigorra ordaindu beharko duzu gakoa iraungiko den bitartean).

Askatu sarraila

Blokeo bat askatzea instantzia guztiak desblokeatzea besterik gabe eskatzen duen eragiketa sinplea da, bezeroak instantzia jakin bat behar bezala blokeatu duela dirudien ala ez kontuan hartu gabe.

Segurtasun-gogoetak

Seguru al da algoritmoa? Saia gaitezen agertoki ezberdinetan gertatzen dena imajinatzen.

Hasteko, demagun bezeroak instantzia gehienetan blokeoa lortzeko gai izan zela. Instantzia bakoitzak gako bat edukiko du guztientzat bizitza berdina duena. Hala ere, gako horietako bakoitza une ezberdin batean instalatu zen, beraz, une desberdinetan iraungiko dira. Baina, lehen gakoa T1 baino okerrago ez den une batean instalatu bada (lehen zerbitzariarekin harremanetan jarri aurretik aukeratzen dugun ordua) eta azken gakoa T2 baino okerrago batean instalatu bada (erantzuna jaso den unean). azken zerbitzaritik), orduan ziur gaude iraungitzen den multzoko lehen gakoak gutxienez iraungo duela MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Gainerako gako guztiak geroago iraungiko dira, beraz, ziur egon gaitezke gako guztiak aldi berean balioko dutela gutxienez denbora honetan.

Gako gehienek balio duten bitartean, beste bezero batek ezin izango du blokeoa eskuratu, izan ere, N/2+1 SET NX eragiketak ezin dira arrakastarik izan N/2+1 gakoak dagoeneko badaude. Hortaz, behin sarraila eskuratuta, ezinezkoa da momentu berean berriro eskuratzea (horrek elkarrekiko bazterketa jabetza urratuko luke).
Hala ere, ziurtatu nahi dugu aldi berean blokeoa eskuratzen saiatzen diren hainbat bezerok ezin dutela arrakasta izan aldi berean.

Bezeroak instantzia gehienak blokeatu baditu gehienez blokeoaren iraupena baino gehiagotan, blokeoa baliogabetzat joko du eta instantzia desblokeatuko du. Beraz, bezeroak iraungitze-data baino denbora gutxiagoan instantzia gehienak blokeatzea lortu duen kasua baino ez dugu kontuan hartu. Kasu honetan, goiko argudioari dagokionez, denboran zehar MIN_VALIDITY bezero batek ezin du blokeoa berriro eskuratu. Hori dela eta, bezero askok N/2+1 instantzia blokeatu ahal izango dituzte aldi berean (2. etaparen amaieran amaitzen dena) gehiengoa blokeatzeko denbora TTL denbora baino handiagoa denean soilik, eta horrek blokeoa baliogabe bihurtzen du.

Segurtasun-froga formal bat eman, lehendik dauden antzeko algoritmoak adierazi edo goiko honetan akatsen bat aurki dezakezu?

Irisgarritasunari buruzko gogoetak

Sistemaren erabilgarritasuna hiru ezaugarri nagusiren araberakoa da:

  1. Askatu automatikoki blokeoak (giltzak iraungi ahala): azkenean giltzak berriro erabilgarri egongo dira sarrailetarako erabiltzeko.
  2. Bezeroek normalean elkarri laguntzen dioten sarrailak kenduz nahi den blokeoa eskuratu ez denean, edo eskuratu eta lana amaitu denean; beraz, litekeena da giltzak iraungi arte itxaron behar ez izatea sarraila berriro eskuratzeko.
  3. Izan ere, bezero batek sarraila bat eskuratzen berriro saiatu behar duenean, blokeo gehienak eskuratzeko behar den epea baino denbora luzeagoan itxaroten duela. Horrek baliabideak lortzeko lehian garuneko zatiketa gertatzeko probabilitatea murrizten du.

Hala ere, sareko segmentuen TTLren berdina den erabilgarritasun-zigorra dago, beraz, ondoko segmentuak badaude, zigorra mugagabea izan daiteke. Hau bezero batek blokeoa eskuratzen duen bakoitzean eta, ondoren, beste segmentu batera erauzitzen du askatu aurretik.

Printzipioz, ondoko sare-segmentu infinituak emanda, sistema bat erabilgarri egon daiteke denbora infinitu batean.

Errendimendua, hutsegitea eta fsync

Jende askok Redis erabiltzen du blokeo-zerbitzariaren errendimendu handia behar duelako blokeoak eskuratzeko eta askatzeko behar den latentziari dagokionez, eta segundoko osa daitezkeen eskuratze/argitalpen kopuruari dagokionez. Baldintza hori betetzeko, N Redis zerbitzariekin komunikatzeko estrategia bat dago latentzia murrizteko. Hau multiplexazio estrategia bat da (edo "pobre man's multiplexing", non socket-a blokeorik gabeko moduan jartzen den, komando guztiak bidaltzen dituen eta komandoak geroago irakurtzen dituen, bezeroaren eta instantzia bakoitzaren arteko joan-etorriko denbora antzekoa dela suposatuz) .

Dena den, epe luzerako datuen biltegiratzearekin lotutako kontua ere kontuan hartu behar dugu, hutsegiteen berreskurapen fidagarria duen eredu bat sortzen saiatzen bagara.

Funtsean, arazoa argitzeko, demagun Redis epe luzerako datu biltegiratzerik gabe konfiguratzen dugula. Bezeroak 3 instantziatik 5 blokeatzea lortzen du. Bezeroak blokeatzea lortu zuen instantzia bat berrabiarazi egiten da, eta momentu honetan 3 instantzia daude berriro baliabide bererako, guk blokeatu ditzakegunak, eta beste bezero batek, berriz, berrabiarazitako instantzia blokeatu dezake, segurtasun-propietatea urratuz. sarrailen esklusibotasuna hartzen du.

Aurretik datuak (AOF) gaitzen badituzu, egoera apur bat hobetuko da. Adibidez, zerbitzari bat sustatu dezakezu SHUTDOWN komandoa bidaliz eta berrabiaraziz. Redis-en iraungitze-eragiketak semantikoki inplementatzen direnez, zerbitzaria itzalita egon arren denborak igarotzen jarraitzen duen moduan, gure eskakizun guztiak ondo daude. Hau normala da, beti ere, itzalaldi normal bat ziurtatuta dagoen bitartean. Zer egin argindar etenaldietan? Redis lehenespenez konfiguratuta badago, fsync diskoan segundoro sinkronizatzen delarik, baliteke berrabiarazi ondoren gure gakoa ez izatea. Teorian, edozein instantzia berrabiarazi bitartean blokeoen segurtasuna bermatu nahi badugu, gaitu beharko genuke fsync=always Datuak epe luzerako biltegiratzeko ezarpenetan. Horrek erabat hilko du errendimendua, tradizionalki banatutako blokeoak modu seguruan ezartzeko erabiltzen diren CP sistemen mailaraino.

Baina egoera lehen begiratuan dirudiena baino hobea da. Printzipioz, algoritmoaren segurtasuna mantentzen da, instantzia hutsegite baten ondoren berrabiarazten denean ez duelako parte hartzen une honetan aktibo dagoen blokeo batean.

Hori ziurtatzeko, hutsegite baten ondoren instantzia erabilgarri egongo dela ziurtatu behar dugu erabiltzen dugun TTL maximoa apur bat gainditzen duen denbora-tarte batean. Horrela, hutsegite unean aktibo zeuden gako guztien iraungitze-datara arte itxarongo dugu.

Berrabiarazi atzeratuak erabiliz, printzipioz posible da segurtasuna lortzea Redis-en epe luzerako iraunkortasunik egon ez arren. Kontuan izan, hala ere, horrek isuna ekar dezakeela irisgarritasuna hausteagatik. Adibidez, instantzia gehienek huts egiten badute, sistema orokorrean ez dago erabilgarri TTLrako (eta ezingo da baliabiderik blokeatu denbora horretan).

Algoritmoaren erabilgarritasuna handitzen dugu: blokeoa luzatzen dugu

Bezeroek egiten duten lana urrats txikiz osatuta badago, posible da blokeo lehenetsiaren iraupena murriztea eta blokeoak zabaltzeko mekanismo bat ezartzea. Printzipioz, bezeroa konputatzen lanpetuta badago eta blokeoaren iraungitze-balioa arriskutsuki baxua bada, gakoaren TTL hedatzen duten instantzia guztietara bidal diezaiekezu Lua script bat gakoa oraindik existitzen bada eta bere balioa oraindik ausazko balio bat bada. sarraila eskuratu zen.

Bezero batek blokeo bat berriro eskuratu behar dela kontuan hartu behar du, indarrean dagoen epean instantzia gehienak blokeatzea lortu badu.

Egia da, teknikoki algoritmoa ez da aldatzen, beraz, blokeoak eskuratzeko behin eta berriz saiakeraren gehienezko kopurua mugatu behar da, bestela irisgarritasun-propietateak urratu egingo dira.

Iturria: www.habr.com

Gehitu iruzkin berria