ProHoster > Blog > Stjórnsýsla > Dreifð læsing með Redis

Dreifð læsing með Redis

Hæ Habr!

Í dag vekjum við athygli þína á þýðingu á flókinni grein um innleiðingu dreifðrar læsingar með Redis og bjóðum þér að tala um horfur Redis sem efni. Greining á umræddu Redlock algrími frá Martin Kleppmann, höfundi bókarinnar "Mikil álagsforrit“, gefið hér.

Dreifð læsing er mjög gagnleg frumstæða sem notuð er í mörgum umhverfi þar sem mismunandi ferlar verða að vinna á sameiginlegum auðlindum á gagnkvæman hátt.

Það eru til nokkur bókasöfn og færslur þarna úti sem lýsa því hvernig á að innleiða DLM (Dreifða læsingarstjóra) með Redis, en hvert bókasafn tekur aðra nálgun og ábyrgðirnar sem þau veita eru frekar veikar miðað við það sem er hægt að ná með aðeins flóknari hönnun.

Í þessari grein munum við reyna að lýsa skilyrtu kanónísku reikniriti sem sýnir hvernig á að útfæra dreifða læsingu með Redis. Við munum tala um reiknirit sem kallast Redlock, það útfærir dreifðan lásstjóra og að okkar mati er þetta reiknirit öruggara en venjuleg einstaks nálgun. Við vonum að samfélagið muni greina það, veita endurgjöf og nota það sem upphafspunkt fyrir flóknari eða önnur verkefni.

Framkvæmd

Áður en farið er yfir í lýsinguna á reikniritinu gefum við nokkra tengla á tilbúnar útfærslur. Þeir geta verið notaðir til viðmiðunar.

Öryggi og aðgengisábyrgð

Við ætlum að móta hönnun okkar með aðeins þremur eiginleikum sem við teljum veita lágmarksábyrgð sem þarf til að nota dreifða læsingu á áhrifaríkan hátt.

  1. Öryggiseign: Gagnkvæm útilokun. Á hverjum tíma getur aðeins einn viðskiptavinur haldið læsingunni.
  2. Framboð Eign A: Engin stöðvun. Það er alltaf hægt að eignast læsingu á endanum, jafnvel þótt biðlarinn sem læsti tilfanginu bili eða lendi á öðrum diskhluta.
  3. Framboð Eign B: Bilunarþol. Svo lengi sem meirihluti Redis hnúta er í gangi geta viðskiptavinir eignast og losað lása.

Hvers vegna innleiðing byggð á bilunarbata er ekki nóg í þessu tilfelli
Til að skilja hvað við ætlum að bæta, skulum við greina núverandi stöðu mála með flestum dreifðu læsingarsöfnum sem byggjast á Redis.

Einfaldasta leiðin til að læsa auðlind með Redis er að búa til lykil í tilvikinu. Venjulega er lykill búinn til með takmarkaðan líftíma, þetta er náð með því að nota rennur út í Redis, svo fyrr eða síðar losnar þessi lykill (eign 2 á listanum okkar). Þegar viðskiptavinurinn þarf að losa auðlindina eyðir hann lyklinum.

Við fyrstu sýn virkar þessi lausn nokkuð vel, en það er vandamál: arkitektúr okkar skapar einn bilunarpunkt. Hvað gerist ef Host Redis tilvikið mistekst? Við skulum þá bæta þræli við! Og við munum nota það ef kynnirinn er ekki tiltækur. Því miður er þessi valkostur ekki raunhæfur. Með því að gera þetta munum við ekki geta innleitt almennilega gagnkvæma útilokunareiginleikann sem við þurfum til að tryggja öryggi, vegna þess að afritun í Redis er ósamstillt.

Augljóslega, í slíku líkani á sér stað keppnisástand:

  1. Viðskiptavinur A eignast lás á skipstjóra.
  2. Skipstjórinn mistekst áður en lykilinn er fluttur til þrælsins.
  3. Fylgismaðurinn er gerður að leiðtoga.
  4. Viðskiptavinur B eignast lás á sömu auðlind og A hefur þegar læst. ÖRYGGISBROT!

Stundum er fullkomlega eðlilegt að við sérstakar aðstæður, svo sem bilun, geti margir viðskiptavinir haldið læsingunni á sama tíma. Í slíkum tilfellum er hægt að nota afritunarlausn. Annars mælum við með lausninni sem lýst er í þessari grein.

Rétt útfærsla með einu tilviki

Áður en reynt er að sigrast á göllunum á einstökum uppsetningu sem lýst er hér að ofan, skulum við skilja hvernig á að meðhöndla þetta einfalda mál á réttan hátt, þar sem þessi lausn er í raun gild í forritum þar sem keppnisástand er ásættanlegt af og til, og einnig vegna þess að blokkun á a. stakt tilvik þjónar sem grunnur sem er notaður í dreifða reikniritinu sem lýst er hér.

Til að eignast lás, gerðu þetta:

SET resource_name my_random_value NX PX 30000

Þessi skipun setur lykil aðeins upp ef hann er ekki þegar til (NX valkostur), með gildistíma upp á 30000 millisekúndur (PX valkostur). Lykillinn er stilltur á "myrandomvalue" Þetta gildi verður að vera einstakt fyrir alla viðskiptavini og allar læsingarbeiðnir.
Í grundvallaratriðum er tilviljunarkennt gildi notað til að losa lásinn á öruggan hátt, með handriti sem segir Redis: fjarlægðu lykilinn aðeins ef hann er til og gildið sem er geymt í honum er nákvæmlega það sem búist var við. Þetta er náð með því að nota eftirfarandi Lua handrit:

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

Þetta er mikilvægt til að koma í veg fyrir að læsing í eigu annars viðskiptavinar sé fjarlægður. Til dæmis gæti viðskiptavinur eignast lás, læst síðan í einhverri aðgerð sem endist lengur en fyrsti lásinn (svo að lykillinn hafi tíma til að renna út) og fjarlægi síðar lásinn sem einhver annar viðskiptavinur hafði sett.
Að nota einfalt DEL er óöruggt vegna þess að viðskiptavinur getur fjarlægt lás sem annar viðskiptavinur hefur. Aftur á móti, þegar ofangreint handrit er notað, er hver lás „undirritaður“ með handahófskenndum streng, þannig að aðeins viðskiptavinurinn sem áður setti hann getur fjarlægt hann.

Hvað ætti þessi handahófi strengur að vera? Ég giska á að það ætti að vera 20 bæti frá /dev/urandom, en þú getur fundið ódýrari leiðir til að gera strenginn nógu einstaka fyrir tilgang þinn. Til dæmis væri fínt að fræja RC4 með /dev/urandom og búa svo til gervi-handahófskenndan straum úr því. Einfaldari lausn felur í sér blöndu af unix tíma í míkrósekúnduupplausn ásamt auðkenni viðskiptavinarins; það er ekki eins öruggt, en það er sennilega upp við verkefnið í flestum samhengi.

Tíminn sem við notum sem mælikvarða á líftíma lykilsins er kallaður „líftími læsingar“. Þetta gildi er bæði tíminn áður en læsingunni er sleppt sjálfkrafa og sá tími sem viðskiptavinur hefur til að ljúka aðgerð áður en annar viðskiptavinur getur aftur læst þeirri auðlind, án þess að brjóta gegn gagnkvæmum útilokunartryggingum. Þessi ábyrgð er aðeins takmörkuð við ákveðinn tíma, sem hefst frá því augnabliki sem lásinn er keyptur.

Þannig að við höfum rætt góða leið til að eignast og losa lás. Kerfið (ef við erum að tala um ódreift kerfi sem samanstendur af einu og alltaf tiltæku tilviki) er öruggt. Við skulum útvíkka þetta hugtak til dreifðs kerfis, þar sem við höfum engar slíkar tryggingar.

Redlock reiknirit

Dreifða útgáfan af reikniritinu gerir ráð fyrir að við höfum N Redis meistara. Þessir hnútar eru algjörlega óháðir hver öðrum, þannig að við notum ekki afritun eða annað óbeint samhæfingarkerfi. Við höfum þegar fjallað um hvernig á að eignast og losa lás á öruggan hátt á einu tilviki. Við teljum það sjálfsagt að reikniritið, þegar unnið er með eitt tilvik, mun nota nákvæmlega þessa aðferð. Í dæmunum okkar settum við N á 5, sem er sanngjarnt gildi. Þannig þurfum við að nota 5 Redis meistara á mismunandi tölvur eða sýndarvélar til að tryggja að þeir virki að mestu óháðir hver öðrum.

Til að eignast lás framkvæmir viðskiptavinurinn eftirfarandi aðgerðir:

  1. Fær núverandi tíma í millisekúndum.
  2. Reynir í röð til að fá læsingu á öllum N tilfellum, með því að nota sama lykilheiti og tilviljunarkennd gildi í öllum tilvikum. Á stigi 2, þegar viðskiptavinurinn setur upp lás á tilviksgrundvelli, notar viðskiptavinurinn töf til að eignast hann sem er nógu stutt miðað við tímann sem lásinn er sjálfkrafa laus. Til dæmis, ef lokunartíminn er 10 sekúndur, þá gæti seinkunin verið á bilinu ~5-50 millisekúndur. Þetta útilokar aðstæður þar sem viðskiptavinurinn gæti verið lokaður í langan tíma við að reyna að ná í misheppnaðan Redis hnút: ef tilvikið er ekki tiltækt, þá reynum við að tengjast öðru tilviki eins fljótt og auðið er.
  3. Til að taka læsingu reiknar viðskiptavinurinn út hversu langur tími hefur liðið; Til að gera þetta dregur það frá raunverulegu tímagildi tímastimpilinn sem fékkst í skrefi 1. Ef og aðeins ef viðskiptavinurinn gat fengið læsinguna á meirihluta tilvika (að minnsta kosti 3) og heildartímann sem það tók að fá læsinguna, minna en læsingartíminn, telst læsingin hafa verið fengin.
  4. Ef lás hefur verið aflað er lástíminn talinn vera upphafleg láslenging að frádregnum liðnum tíma sem reiknaður var í skrefi 3.
  5. Ef viðskiptavinurinn nær ekki læsingunni af einhverjum ástæðum (annaðhvort tókst honum ekki að læsa N/2+1 tilvikum eða læsingartíminn var neikvæður), þá mun hann reyna að opna öll tilvikin (jafnvel þau sem hann hélt að hann gæti ekki lokað ).

Er reikniritið ósamstillt?

Þetta reiknirit er byggt á þeirri forsendu að þrátt fyrir að engin samstillt klukka sé til sem öll ferli myndu virka á, þá flæðir staðartími í hverju ferli samt á um það bil sama hraða og villan er lítil miðað við heildartímann sem læsingin er liðin frá. sjálfkrafa sleppt. Þessi forsenda er mjög svipuð því ástandi sem er dæmigert fyrir venjulegar tölvur: hver tölva hefur staðbundna klukku og við getum yfirleitt treyst á þá staðreynd að tímamunur milli mismunandi tölva er lítill.

Á þessum tímapunkti verðum við að móta regluna okkar um gagnkvæma útilokun betur: gagnkvæm útilokun er aðeins tryggð ef viðskiptavinurinn sem heldur á læsingunni fer út á þeim tíma sem læsingin er í gildi (þetta gildi fæst í skrefi 3), að frádregnum lengri tíma (samtals nokkrir millisekúndur til að jafna upp tímamun á milli ferla).

Eftirfarandi áhugaverð grein segir meira um slík kerfi sem krefjast samræmingar á millibili: Leigusamningar: skilvirkt bilunarþolið fyrirkomulag fyrir samkvæmni í dreifðri skyndiminni.

Reyndu aftur við bilun

Þegar viðskiptavinur nær ekki að eignast læsingu verður hann að reyna aftur eftir handahófskennda töf; þetta er gert til að afsamstilla marga viðskiptavini sem reyna að eignast læsingu á sömu auðlind á sama tíma (sem getur leitt til "klofinn heila" ástand þar sem engir sigurvegarar eru). Að auki, því hraðar sem viðskiptavinur reynir að ná læsingu á meirihluta Redis-tilvika, því þrengri er glugginn þar sem skipting heila getur átt sér stað (og því minni þörf fyrir endurtilraunir). Þess vegna ætti viðskiptavinurinn helst að reyna að senda SET skipanir til N tilvika samtímis með því að nota margföldun.

Rétt er að undirstrika hér hversu mikilvægt það er fyrir viðskiptavini sem ná ekki að eignast meirihluta læsa að losa (að hluta) keypta læsa, svo að þeir þurfi ekki að bíða eftir að lykillinn rennur út áður en hægt er að ná í læsinguna á auðlindinni aftur. (þó að ef netsrof á sér stað og viðskiptavinurinn missir samband við Redis tilvikin, þá þarftu að borga sekt á meðan þú bíður eftir að lykillinn rennur út).

Losar lásinn

Að losa lás er einföld aðgerð sem einfaldlega krefst þess að opna öll tilvik, óháð því hvort viðskiptavinurinn virðist hafa læst tilteknu tilviki.

Öryggissjónarmið

Er reikniritið öruggt? Við skulum reyna að ímynda okkur hvað gerist við mismunandi aðstæður.

Til að byrja með skulum við gera ráð fyrir að viðskiptavinurinn hafi getað fengið læsingu á meirihluta tilvika. Hvert tilvik mun innihalda lykil með sama líftíma fyrir alla. Hins vegar var hver þessara lykla settur upp á öðrum tíma, þannig að þeir munu renna út á mismunandi tímum. En ef fyrsti lykillinn var settur upp í einu ekki verri en T1 (tíminn sem við veljum áður en við höfum samband við fyrsta netþjóninn) og síðasti lykillinn var settur upp í einu ekki verri en T2 (tíminn sem svarið barst frá síðasta netþjóni), þá erum við fullviss um að fyrsti lykillinn í settinu sem rennur út lifi a.m.k. MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Allir aðrir lyklar munu renna út síðar, þannig að við getum verið viss um að allir lyklar verði samtímis í gildi í að minnsta kosti þennan tíma.

Á þeim tíma sem flestir lyklar eru í gildi mun annar viðskiptavinur ekki geta fengið lásinn, þar sem N/2+1 SET NX aðgerðir geta ekki gengið upp ef N/2+1 lyklar eru þegar til. Því þegar lás hefur verið keyptur er ómögulegt að eignast hann aftur á sama augnabliki (þetta myndi brjóta í bága við gagnkvæma útilokun).
Hins vegar viljum við tryggja að margir viðskiptavinir sem reyna að eignast lás á sama tíma geti ekki náð árangri á sama tíma.

Ef viðskiptavinurinn hefur læst meirihluta tilvika í um eða lengur en hámarkslæsingartímann mun hann telja læsinguna ógilda og opna tilvikin. Þess vegna verðum við aðeins að taka tillit til þess tilviks þar sem viðskiptavinurinn náði að loka á meirihluta tilvika á skemmri tíma en fyrningardagsetningu. Í þessu tilviki, varðandi ofangreind rök, á tímabilinu MIN_VALIDITY enginn viðskiptavinur ætti að geta fengið lásinn aftur. Þess vegna munu margir viðskiptavinir geta læst N/2+1 tilvikum á sama tíma (sem lýkur í lok 2. stigs) aðeins þegar tíminn til að læsa meirihlutanum var lengri en TTL tíminn, sem gerir læsinguna ógilda.

Geturðu lagt fram formlega sönnun fyrir öryggi, gefið til kynna svipaða reiknirit sem fyrir eru eða fundið villu í ofangreindu?

Aðgengissjónarmið

Kerfisframboð fer eftir þremur megineinkennum:

  1. Slepptu læsingum sjálfkrafa (þegar lyklar renna út): Lyklar verða að lokum tiltækir aftur til að nota fyrir læsingar.
  2. Sú staðreynd að viðskiptavinir hjálpa venjulega hver öðrum með því að fjarlægja lása þegar viðkomandi lás hefur ekki verið aflað, eða hefur verið aflað og verkinu er lokið; þannig að það er líklegt að við þurfum ekki að bíða eftir að lyklarnir renni út til að fá aftur læsinguna.
  3. Sú staðreynd að þegar viðskiptavinur þarf að reyna aftur að eignast læsingu bíður hann í tiltölulega lengri tíma en sá tími sem þarf til að eignast flesta læsa. Þetta dregur úr líkum á að upp komi klofningur í heila þegar keppt er um auðlindir.

Hins vegar er framboðsrefsing jöfn TTL nethlutanna, þannig að ef það eru samliggjandi hlutar gæti refsingin verið ótímabundin. Þetta gerist þegar viðskiptavinur eignast lás og rífur síðan í annan hluta áður en hann getur losað hann.

Í grundvallaratriðum, miðað við óendanlega samfellda nethluti, getur kerfi verið óaðgengilegt í óendanlegan tíma.

Afköst, bilun og fsync

Margir nota Redis vegna þess að þeir þurfa mikla afköst lásþjóns með tilliti til leyndarinnar sem þarf til að afla og losa lása og fjölda kaupa/útgáfu sem hægt er að ljúka á sekúndu. Til að mæta þessari kröfu er stefna til að hafa samskipti við N Redis netþjóna til að draga úr leynd. Þetta er margföldunaraðferð (eða "fátæks margföldun", þar sem falsinn er settur í óblokkandi stillingu, sendir allar skipanir og les skipanirnar síðar, að því gefnu að tíminn fram og til baka milli viðskiptavinarins og hvers tilviks sé svipaður) .

Hins vegar verðum við líka að taka tillit til þess sem tengist langtímagagnageymslu ef við reynum að búa til líkan með áreiðanlega endurheimt frá bilunum.

Í grundvallaratriðum, til að skýra málið, skulum við gera ráð fyrir að við stillum Redis með enga langtímagagnageymslu yfirleitt. Viðskiptavinurinn nær að loka fyrir 3 af 5 tilvikum. Eitt af tilvikunum sem viðskiptavinurinn náði að loka er endurræst og á þessu augnabliki eru aftur 3 tilvik fyrir sama tilfang, sem við getum lokað á, og annar viðskiptavinur getur aftur á móti lokað á endurræst tilvikið og brýtur í bága við öryggiseiginleikann sem gerir ráð fyrir einkarétt á læsingum.

Ef þú virkjar gögn framundan (AOF) mun ástandið batna aðeins. Til dæmis geturðu kynnt miðlara með því að senda SHUTDOWN skipunina og endurræsa hana. Þar sem fyrningaraðgerðir í Redis eru merkingarlega útfærðar á þann hátt að tíminn heldur áfram að flæða jafnvel þegar slökkt er á þjóninum eru allar kröfur okkar í lagi. Þetta er eðlilegt svo framarlega sem eðlileg stöðvun er tryggð. Hvað á að gera ef rafmagnsleysi verður? Ef Redis er sjálfgefið stillt, með fsync samstillingu á disknum á hverri sekúndu, þá er mögulegt að eftir endurræsingu munum við ekki hafa lykilinn okkar. Fræðilega séð, ef við viljum tryggja læsingaröryggi við endurræsingu, ættum við að virkja fsync=always í stillingum fyrir langtíma gagnageymslu. Þetta mun algjörlega drepa afköst, niður á stigi CP kerfa sem venjulega eru notuð til að innleiða dreifða læsa á öruggan hátt.

En ástandið er betra en það virðist við fyrstu sýn. Í grundvallaratriðum er öryggi reikniritsins varðveitt vegna þess að þegar tilvikið er endurræst eftir bilun tekur það ekki lengur þátt í neinum lás sem er virkur.

Til að tryggja þetta þurfum við bara að tryggja að eftir bilun sé tilvikið ótiltækt í einhvern tíma sem er aðeins umfram hámarks TTL sem við notum. Þannig bíðum við þar til fyrningardagsetning og sjálfvirk losun allra lykla sem voru virkir þegar bilun varð.

Með því að nota seinkaða endurræsingu er í grundvallaratriðum mögulegt að ná öryggi jafnvel þótt engin langtímaviðhald sé í Redis. Athugið þó að þetta getur varðað sekt fyrir brot á aðgengi. Til dæmis, ef meirihluti tilvika mistakast, verður kerfið ekki tiltækt á heimsvísu fyrir TTL (og ekki er hægt að loka fyrir neina auðlind á þessum tíma).

Við aukum aðgengi reikniritsins: við framlengjum lokunina

Ef vinnan sem framkvæmt er af viðskiptavinum samanstendur af litlum skrefum er hægt að draga úr sjálfgefna læsingartímanum og innleiða kerfi til að lengja læsingar. Í grundvallaratriðum, ef viðskiptavinurinn er upptekinn við tölvuvinnslu og lás fyrningargildið er hættulega lágt, geturðu sent Lua skriftu til allra tilvika sem framlengir TTL lykilsins ef lykillinn er enn til og gildi hans er enn tilviljunarkennt gildi sem fæst þegar lás var keyptur.

Viðskiptavinur ætti aðeins að líta á lás sem endurheimtan ef honum hefur tekist að læsa meirihluta tilvika innan gildistímans.

Að vísu breytist tæknilega reikniritið ekki, þannig að hámarksfjöldi endurtekinna tilrauna til að eignast læsingar verður að takmarka, annars verður brotið gegn aðgengiseiginleikum.

Heimild: www.habr.com

Bæta við athugasemd