Jaotatud lukud Redis'e rakendamisega

Tere, Habr!

Täna pakume teie tähelepanu keerulise artikli tõlget jaotatud lukustuste rakendamisest Redis abil ning arutame Redis'e perspektiivikust teemana. Analüüsime Redlock algoritmi Martin Kleppmann'i poolt, kes on raamatu autor "Kohandatud rakendused", on esitatud siin.

Jaotatud lukustused on väga kasulik primitiiv, mida kasutatakse paljudes keskkondades, kus erinevad protsessid peavad töötama jagatud ressursside kallal vastavalt vastastikuse välistamise põhimõttele.

On olemas mitmeid teeke ja postitusi, mis kirjeldavad, kuidas rakendada DLM-i (jaotatud lukustuste haldurit) Redis abil, kuid igas teegis kasutatakse oma lähenemist ning antud garantiid on võrreldes keerukama projekteerimisega üsna nõrgad.

Selles artiklis püüame kirjeldada tinglikult kanonilist algoritmi, mis demonstreerib, kuidas rakendada jaotatud lukustusi Redis'i abil. Räägime algoritmist nimega Redlock, mis rakendab jaotatud lukustuste haldurit ning meie arvates on see algoritm turvalisem kui traditsiooniline lähenemine, kus on ainult üks instants. Loodame, et kogukond analüüsib seda, annab tagasisidet ja hakkab seda kasutama keerukamate või alternatiivsete projektide teostamise lähtepunktina.

Rakendused

Enne algoritmi kirjelduse juurde minekut toome välja mõned lingid juba valminud rakendustele. Neid saab kasutada viitamiseks.

• Redlock-rb (Ruby rakendus). Samuti on olemas fork Redlock-rb, lisades paketi (gem) mugavuse jaoks ja mitte ainult selleks.
• Redlock-py (Python rakendus).
• Aioredlock (Asyncio Python rakendus).
• Redlock-php (PHP rakendus).
• PHPRedisMutex (veel üks PHP rakendus)
• cheprasov/php-redis-lock (PHP teek lukustuste jaoks)
• Redsync (Go rakendus).
• Redisson (Java rakendus).
• Redis::DistLock (Perl rakendus).
• Redlock-cpp (C++ rakendus).
• Redlock-cs (C#/.NET rakendus).
• RedLock.net (C#/.NET rakendus). Toetab asünkroonset ja lukustamise laiendust.
• ScarletLock (C# .NET rakendus konfigureeritava andmete salvestusega)
• Redlock4Net (C# .NET rakendus)
• node-redlock (NodeJS rakendus). Sisaldab lukustuste pikendamise tuge.

Turvalisuse ja kättesaadavuse garantiid

Me kavatseme modelleerida meie projekti ainult kolme omaduse abil, mis meie arvates pakuvad vähemalt minimaalset garantiid, mis on vajalikud jaotatud lukustuste tõhusaks kasutamiseks.

1. Turvaomadus: Vastastikune välistamine. Igal hetkel võib lukustust hoida vaid üks klient.
2. Kättesaadavuse omadus A: Vastastikuste lukustuste puudumine. Lõppkokkuvõttes on alati võimalik lukustus saada, isegi kui ressurssi lukustav klient keeldub või satub teisele kettasegmentile.
3. Kättesaadavuse omadus B: Rikete taluvus. Niikaua kui enamus Redis'e sõlmedest töötab, saavad kliendid lukustusi omandada ja vabastada.

Miks on taastumisele keskenduvad rakendused antud juhul ebapiisavad
Kuna mõistame, mida me soovime parandada, vaatame hetkeolukorda, mis enamiku Redis'e põhiste jaotatud lukustuste raamatukogude puhul on tekkinud.

Lihtsaim viis ressurssi Redis'e abil lukustada on luua key instantsis. Üldiselt luuakse key piiratud elueaga, mida saavutatakse Redis'e võimalusega expires, seega varem või hiljem vabastatakse see key (omadus 2 meie nimekirjas). Kui kliendil on vajalik ressurss vabastada, delete'ib ta key.

Esmapilgul töötab see lahendus küllalt hästi, kuid on probleem: meie arhitektuuris tekib ühtne tõrkepunkt. Mis juhtub, kui päästiku Redis'e instants ebaõnnestub? Lisame alluva! Ja kasutame seda, kui päästik on mitteaktiivne. Kahjuks on see võimalus elujõuetu. Nii tehes ei suuda me õigesti rakendada vastastikuse välistamise omadust, mis on turvalisuse tagamiseks vajalik, kuna replikeerimine Redis's on asünkroonsete.

Ilmselgelt tekib sellises mudelis võidujooksu olek:

1. Klient A omandab lukustuse päästikus.
2. Päästik ebaõnnestub, enne kui kirje key'sse kantakse alluvale.
3. Alluv tõuseb päästikuks.
4. Klient B omandab lukustuse samale ressursele, mis on juba A poolt lukustatud. TURVALISUSE RIKKUMINE!

Mõnikord on täiesti normaalne, et erilistes olukordades, näiteks rikke puhul, võivad mitmed kliendid korraga lukustuse hoida. Sellistel juhtudel saab rakendada replikatsioonipõhist lahendust. Teistes olukordades soovitame artiklis kirjeldatud lahendust.

Õige teostus ühe instantsiga

Enne kui proovime ületada üheaastase konfiguratsiooni puudusi, mis on eespool kirjeldatud, vaatame, kuidas õigesti tegutseda selles lihtsas olukorras, kuna selline lahendus on tegelikult lubatav rakendustes, kus võidusõidud on aeg-ajalt lubatud, samuti seetõttu, et ühekordne lukustus teenib aluseks, mida kasutatakse siin kirjeldatud jaotatud algoritmis.

Lukustuse saamiseks teeme järgmist:

SET resource_name my_random_value NX PX 30000

See käsk seadistab võtme ainult siis, kui see ei eksisteeri (valik NX), kehtivusajaga 30000 millisekundit (valik PX). Võtmele määratakse väärtus “myrandomvalue”. See väärtus peab olema ainulaadne kõigi klientide ja lukustuse taotluste seas.
Põhimõtteliselt kasutatakse juhuslikku väärtust lukustuse ohutuks vabastamiseks skripti abil, mis teatab Redis'ile: kustuta võti, ainult kui see eksisteerib, ja väärtus, mis seal on, on see, mida oodati. See saavutatakse järgmise Lua skripti abil:

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

See on oluline, et vältida lukustuse eemaldamist, mille on teinud teine klient. Näiteks võib klient omada lukustust ja seejärel lukustuda operatsiooni käigus, mis kestab kauem kui esimese lukustuse kehtivusaeg (n nii, et võtme aegumise aeg on möödas), ja hiljem eemaldada lukustuse, mille pani mõni teine klient.
Lihtsa DEL kasutamine ei ole ohutu, kuna klient võib eemaldada lukustuse, mille on seadnud teine klient. Vastupidi, kasutades ülaltoodud skripti, on iga lukustus „allkirjastatud“ juhusliku stringiga, seega suudab selle eemaldada vaid see klient, kes selle varem seadistatud lukustuse kehtestanud.

Mis peab see juhuslik tekst olema? Arvan, et see peaks olema 20 baiti /dev/urandom'ist, kuid on olemas ka odavamaid viise, et luua tekst, mis on piisavalt ainulaadne teie esitatud eesmärkide jaoks. Näiteks võib olla sobiv alustada RC4'ga /dev/urandom'ist ja seejärel luua selle põhjal pseudojuhuslik voog. Lihtsam lahendus on kombineerida unix-i aega mikroskogustes pluss kliendi ID; see ei ole nii turvaline, kuid tõenäoliselt vastab see ülesannete tasemele enamikes kontekstides.

Aeg, mida kasutame võtme eluea näitajana, nimetatakse „lukustamise kehtivuse ajaks“. See väärtus on samaaegselt periood, mille möödumisel lukustus automaatselt vabastatakse, ja aeg, mille jooksul kliendil on võimalus operatsioon läbi viia, enne kui teine klient saab omakorda selle ressursi lukustada, rikkuvat aga tegelikult vastastikuse välistamise garantiisid. Selline garantii on piiratud ainult kindla ajavahemikuga, mis algab lukustuse omandamise hetkest.

Nii siis, oleme arutanud head viisi lukustuse omandamiseks ja vabastamiseks. Süsteem (kui räägime mittejaotatud süsteemist, mis koosneb ainsast ja alati kergesti ligipääsetavast instantsist) on turvaline. Laiendame seda kontseptsiooni jaotatud süsteemile, kus selliseid garantiisid meil ei ole.

Redlock'i algoritm

Jaotatud versioonis algoritmist eeldatakse, et meil on N juhtivat Redis'i. Need sõlmed on täielikult sõltumatud üksteisest, seega ei kasuta me replikatsiooni ega ühtegi muud kaudset koordineerimissüsteemi. Oleme juba rääkinud, kuidas turvaliselt omandada ja vabastada lukustust ühes ainsas instantsis. Eeldame, et algoritm ühes instantsis töötab just selle meetodiga. Meie näidetes seadistame N-ks 5, mis on täiesti mõistlik väärtus. Seega, peame kasutama 5 juhtivat Redis'i erinevates arvutites või virtuaalmasinates, et tagada nende peamine sõltumatus üksteisest.

Lukustuse omandamiseks peab klient teostama järgmised toimingud:

1. Saama praeguse aja millisekundites.
2. Järjestelmällisesti yritetään hankkia lukitus kaikilta N-instanssilta käyttäen kaikissa tapauksissa samaa avaimen nimeä ja satunnaisia arvoja. Vaiheessa 2, asettaen lukituksen jokaiselle instanssille, asiakas käyttää viivettä, joka on riittävän lyhyt verrattuna aikaan, jonka kuluttua lukitus poistuu automaattisesti. Esimerkiksi, jos lukituksen kesto on 10 sekuntia, viive voi olla alueella ~ 5-50 millisekuntia. Tällä tavoin vältetään tilanne, jossa asiakas voisi jäädä pitkäksi aikaa lukituksi yrittäessään ottaa yhteyttä epäonnistuneeseen Redis-solmuun: jos instanssi ei ole käytettävissä, yritämme mahdollisimman pian yhdistää toiseen instanssiin.
3. Lukituksen ottamiseksi asiakas laskee, kuinka kauan aikaa on kulunut; hän vähentää nykyisestä aikavälistä sen aikaleiman, joka saatiin vaiheessa 1. Vasta silloin, kun asiakas on onnistunut saamaan lukituksen useimmista instansseista (vähintään 3), ja kokonaisaika, joka tarvittiin lukituksen saamiseen, on lyhyempi kuin lukituksen voimassaoloaika, katsotaan, että lukituksen saaminen on onnistunut.
4. Jos lukitus saatiin, lukituksen voimassaoloaikaa lasketaan alkuperäisestä lukituksen kestosta vähentämällä vaiheessa 3 laskettu kulunut aika.
5. Jos asiakas ei jostain syystä onnistunut saamaan lukitusta (tai hän ei saanut lukittua N/2+1 instanssia, tai lukituksen voimassaoloaika oli negatiivinen), hän yrittää avata lukituksen kaikilta instansseilta (myös niiltä, joita hän luuli, ettei hän voinut lukita).

Onko algoritmi asynkroninen?

Tämä algoritmi perustuu oletukseen, että vaikka ei ole synkronoituja kelloja, joiden mukaan kaikki prosessit toimisivat, jokaisen prosessin paikallinen aika kulkee silti suurin piirtein samaa tahtia, ja virhe on pieni verrattuna kokonaisaikaan, jonka kuluttua lukitus poistuu automaattisesti. Tämä oletus muistuttaa paljon tilannetta, joka on tyypillinen tavallisille tietokoneille: jokaisessa tietokoneessa on paikalliset kellot, ja yleensä voimme laskea, että aikahäiriö eri tietokoneilla on pieni.

Selle etapi juures peame selgemalt sõnastama meie vastastikuse välistamise reegli: vastastikune välistamine on garanteeritud ainult siis, kui klient, kes hoiab lukku, lõpetab oma tegevuse ajavahemikus, mil lukustus on kehtiv (see väärtus on saadud 3. sammust), miinus veel mõni hetk (mitu millisekundit, et kompenseerida protsesside vahelisi ajavahemikke).

Rohkem sarnastest süsteemidest, mis nõuavad ajavahemike kooskõlastamist, räägib järgmine huvitav artikkel: Leased: tõhus veakindel mehanism jaotatud failivahendite järjepidevuse tagamiseks.

Uuesti proovimine peale ebaõnnestumist

Kui kliendil ei õnnestu lukku saada, peab ta proovima seda uuesti, tehes juhusliku viivituse; seda tehakse, et desünkroniseerida mitmed kliendid, kes üritavad sama ressursi lukku samaaegselt osta (mis võib viia olukorra «jagatud aju» tekkimiseni, kus võitjaid ei ole). Lisaks, mida kiiremini klient üritab enamikku Redis'i instantsidest lukku saada, seda kitsam on aken, kus «jagatud aju» olukord võib tekkida (ja seda vähem on uuesti proovimise vajadust). Seega peaks klient ideaaljuhul üritama samal ajal saata SET käsklusi N instantsile mitmekesistamise abil.

Siinkohal on oluline rõhutada, kui tähtis on, et kliendid, kes ei suutnud enamikke lukustusi saada, vabastaksid (osaliselt) saadud lukustusi, et ei peaks ootama võtme aegumise lõppu, enne kui ressursi lukku saab uuesti saada (tegelikult, kui toimub võrgu killustumine ja klient kaotab ühenduse Redis'i instantsidega, tuleb maksta tasu saadavuse rikkumise eest, kuni võtme aegumisel ootamine kestab).

Luku vabastamine

Luku vabastamine on lihtne operatsioon, mis nõuab lihtsalt kõigi instantside vabastamist, olenemata sellest, kas klient arvab, et ta suutis konkreetse instantsi edukalt lukustada.

Turvakaalutlused

Kas algoritm on turvaline? Proovime kujutada, mis juhtub erinevates stsenaariumides.

Alustuseks eeldame, et klient suutis saada lukustuse enamusinstantside üle. Igal instantsil on sama eluiga, kuid iga selle võtme kehtivus algas eri ajal, mistõttu nende aegumine toimub erinevatel hetkedel. Kui esimene võtme seati mitte hiljem kui T1 (aeg, mille me valime enne ühenduse loomist esimesse serverisse), ja viimane võtme seati mitte hiljem kui T2 (aeg, mil saadi vastus viimase serveri poolt), siis saame olla kindlad, et esimene võtme, millel aegumine toimub, kehtib vähemalt MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Kõik ülejäänud võtmed aeguvad hiljem, seega saame kindlad olla, et kõik võtmed kehtivad vähemalt selle aja jooksul.

Kuna enamus võtmeid on kehtivad, ei saa teine klient lukustust osta, kuna N/2+1 SET NX operatsioon ei saa lõpetuda edukalt, kui juba on olemas N/2+1 võtmeid. Seega, kui lukustus on juba omandatud, ei saa seda samal hetkel uuesti omandada (see rikuks vastastikuse tõrjumise omadust).
Tõsi, me tahame olla kindlad, et hulk kliente, kes üritavad samal ajal lukustust omandada, ei õnnestu sellega samaaegselt.

Kui klient lukustab enamusinstantsidest, kulutades sellele aega, mis on võrdne või pikem kui maksimaalne lukustuse kestus, siis peab ta lukustuse kehtetuks ja vabastab instantsid. Seega peame arvesse võtma ainult olukorda, kus kliendil õnnestus lukustada enamus instantsidest ajavahemikus, mis on lühem kui kehtivusaeg. Sel juhul, seoses eelpooltoodud argumendiga, ajavahemiku MIN_VALIDITY kui ükski klient ei peaks olema suuteline lukustust uuesti saama. Seega saavad paljud kliendid lukustada N/2+1 instantsi samal hetkel (mis lõppeb etapp 2 lõppemise hetkel), ainult siis, kui enamus lukustuse aeg oli pikem kui TTL aeg, muutes lukustuse kehtetuks.

Kas sa saaksid esitada formaalse turvalisuse tõendi, viidata olemasolevatele sarnastele algoritmidele või leida tõrke eeltoodud tekstis?

Kergusega seotud kaalutlused

Süsteemi kergus sõltub kolmest põhijoonest:

1. Automaatne lukustuse lõpetamine (kuna võtmete kehtivusaeg lõpeb): lõpuks on võtmed taas kergesti kättesaadavad, et kasutada lukustuse jaoks.
2. Tegelikkus on see, et kliendid aitavad tavaliselt üksteist lukustusi eemaldades, kui vajalik lukustus pole soetatud, või kui see on soetatud ja töö on lõpetatud; seega on tõenäoline, et me ei pea ootama võtmete kehtivuse lõppemist, et lukustust uuesti soetada.
3. Tegelikkus on see, et kui kliendil on vaja lukustuse uuesti soetamist, oodatakse tavaliselt tunduvalt pikemat aega kui enamik lukustuste soetamiseks vajalik aeg. See vähendab tõenäosust, et tekib olukord, kus kokkulepitud ressursid on jagatud.

Siiski tuleb kerguse vähenemise eest maksta trahvi, mis on võrreldav TTL-iga võrgusegmentides, seega, kui võrgus on pidevad segmendid, võib see trahv saavutada piiramatu suuruse. See juhtub iga kord, kui klient soetab lukustuse ja siis katkestatakse ühendus teise segmendi, enne kui ta on selle vabastanud.

Põhimõtteliselt, kui võrgu lõpmatuid pidevaid segmente on, võib süsteem olla kergelt kättesaamatu lõpmatuks ajaks.

Tõhusus, talitlushäiretest taastumine ja fsync

Paljud kasutavad Redis't, kuna on vajalik tagada kõrge lukustusserveri tõhusus, lähtudes latentsusaegadest, mis on vajalikud lukustuste soetamiseks ja vabastamiseks, samuti nendega seotud operatsioonide arvust, mida suudetakse sekundis teha. Selle nõude täitmiseks on kommunikatsioonistrateegia N Redis serveriga, et vähendada latentsusaega. See on mitmeülekande strateegia (või 'vaeste mitmeülekande' strateegia, kus sokkel seatakse mitteblokeerivasse režiimi, saadetakse kõik käsud ja käsud loetakse hiljem, lähtudes arvamusest, et kliendi ja iga instantsi pöörlemisaeg on sarnane).

Tõsi, peame arvesse võtma ka pikaajalise andmete säilitamise kaalutluse, kui soovime luua mudeli, mis tagab usaldusväärse talitlushäiretest taastumise.

Põhimõtteliselt, et selgitada probleemi, oletame, et konfigureerime Redis'i ilma pikaajalise andmesalvestuseta. Klient suudab lukustada 3 5 instantsist. Üks neist instantsidest, mille klient on suutnud lukustada, taaskäivitub, ja sel hetkel tekivad taas 3 instantsi sama ressursi jaoks, mida me saame lukustada, ja teine klient võib omakorda lukustada taaskäitatud instantsi, rikkudes lukustamise eksklusiivsuse turvafunktsiooni.

Kui sisse lülitada eelteavitav andmete salvestamine (AOF), siis olukord paraneb veidi. Näiteks saame serverit tõsta, edastades SHUTDOWN käsku ja taaskäivitades selle. Kuna Redis'is on aeg semantiliselt rakendatud nii, et see jookseb ka siis, kui server on väljas, on kõik meie nõudmised normaalsed. Normaalne seni, kuni tagatakse riist- ja tarkvaralise katkestamise korral normaalne sulgemine. Aga mis siis, kui on toitekatkestus? Kui Redis on vaikimisi konfigureeritud, koos fsync'iga, mis sünkroniseeritakse kettale iga sekundi järel, siis võib olla nii, et pärast taaskäivitamist jääb meie võtme otsa. Teoreetiliselt, kui tahame tagada lukustamise turvalisuse igas instantsi taaskäivitamises, peame lülitama fsync=always pikaajalise andmesalvestuse seadetes. See tapab täielikult jõudluse, viies selle selliste CP-süsteemide tasemele, mida traditsiooniliselt kasutatakse jagatud lukustamise turvalisuse rakendamiseks.

Aga olukord on parem, kui esmapilgul tundub. Põhimõtteliselt säilib algoritmi turvalisus, kuna kui instants taaskäivitub pärast riket, ei osale see enam aktiivsetes lukustamistes.

Selle tagamiseks on vajalik vaid tagada, et pärast riket jääks instants kättesaamatuks ajaks, mis veidi ületab maksimaalse TTL, mida me kasutame. Nii ootame, kuni aegumistähtaeg möödub ja automaatne vabastamine toimub kõikide võtmete puhul, mis olid aktiivsed rikke hetkel.

Kasutades edasi lükatud taaskäivitusi, on põhimõtteliselt võimalik saavutada turvalisust ka siis, kui Redis ei säilita andmeid püsivalt. Tuleb siiski märkida, et see võib kaasa tuua karistuse kättesaadavuse rikkumise eest. Näiteks juhul, kui enamik instantsidest ebaõnnestub, muutub süsteem TTL ajal globaalselt kättesaamatuks (ja sel ajal ei saa ühtegi ressurssi blokeerida).

Suurendame algoritmi kättesaadavust: pikendame blokeeringut

Kui klientide teostatav töö koosneb väikestest etappidest, on võimalik vähendada vaikimisi määratud blokeeringu aegumisaega ja rakendada blokeeringute pikendamise mehhanismi. Põhimõtteliselt, kui klient on arvutustega hõivatud ja blokeeringu aegumisaeg on ohtlikult madal, saab kõigile instantsidele saata Lua skripti, mis pikendab võtme TTL-i, kui see veel eksisteerib ja selle väärtus on endiselt juhuslik, saadud siis, kui blokeering saavutati.

Klient peab arvestama blokeeringut uuesti saavutatuks ainult juhul, kui tal õnnestus blokeerida enamik instantsidest enne aegumisaega.

Tõsi, tehniliselt algoritm sellega ei muutu, seega peab maksimum korduste arv blokeeringute saavutamiseks olema piiratud, vastasel juhul rikkuvad kättesaadavuse omadused.

Allikas: habr.com