Jaotatud lukustamine Redis'i abil

Tere, Habr!

Täna pakume teie tähelepanu tõlget keerulisest artiklist jaotatud lukustuste rakendamisest Redis'i abil ning arutame Redis'i perspektiivit ka teema osas. Analüüsitakse Martin Kleppmanni Redlocki algoritmi, kes on raamatu autor "Karmid rakendused", mis on esitatud siit.

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

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

Selles artiklis proovime kirjeldada tinglikult kanonilist algoritmi, mis demonstreerib, kuidas rakendada jaotatud lukustusi Redis'i abil. Räägime algoritmist nimega Redlock, see, see ja see algorithmi on ohut. Loodame, et kogukond analüüsib seda, annab tagasisidet ja kasutab seda keerukamate või alternatiivsete projektide elluviimise lähtepunktina.

Teostused

Enne algoritmi kirjelduse juurde asumist toome välja mõned lingid juba valmisteostele. Nendega saab tutvuda viidates.

• Redlock-rb (teostus Ruby jaoks). Samuti on olemas forki Redlock-rb, mis lisab mugavuse pärast paketina (gem) ja mitte ainult selleks.
• Redlock-py (teostus Python jaoks).
• Aioredlock (teostus Asyncio Python jaoks).
• Redlock-php (teostus PHP jaoks).
• PHPRedisMutex (veel üks teostus PHP jaoks)
• cheprasov/php-redis-lock (PHP-moodul lukustamiseks)
• Redsync (teostus Go jaoks).
• Redisson (teostus Java jaoks).
• Redis::DistLock (teostus Perl jaoks).
• Redlock-cpp (teostus C++ jaoks).
• Redlock-cs (teostus C#/.NET).
• RedLock.net (teostus C#/.NET). Toetab async ja lukustamise laiendusi.
• ScarletLock (teostus C# .NET konfiguratsiooniga andmehoidla jaoks)
• Redlock4Net (teostus C# .NET)
• node-redlock (rakendamine NodeJS-i jaoks). Sisaldab lukustuse pikendamise toetust.

Turvalisuse ja kättesaadavuse garantiid

Kavandame oma projekti, seadistades ainult kolm omadust, mis, nagu meie arvates, pakuvad minimaalset garantiid ja võimaldavad tõhusat jaotatud lukustuse kasutamist.

1. Turvalisuse omadus: Vastastikune välistamine. Igasuguses hetkes võib vaid üks klient hoida lukku.
2. Kättesaadavuse omadus A: Vastastikuste lukustuste puudumine. Lõppkokkuvõttes on alati võimalik saada lukku, isegi kui ressursi lukustanud klient ebaõnnestub või satub teisele kettasegmendile.
3. Kättesaadavuse omadus B: Rikete taluvus. Kui enamus Redis sõlmedest töötab, saavad kliendid lukke omandada ja vabastada.

Miks taastumisest sõltuva rakenduse tõhusus ei ole sel juhul piisav
Et mõista, mida me kavatseme parandada, analüüsime praegust olukorda enamikus jaotatud lukustuse raamatukogudes, mis põhinevad Redis-il.

Ressursi blokeerimise kõige lihtsam viis Redis'i abil on luua instantsis võtmed. Tavaliselt luuakse võti piiratud eluaega, mis saavutatakse Redis'is olemasoleva expires omaduse abil, seega vabastatakse see võti varem või hiljem (meie loendi omadus 2). Kui kliendile on vajalik ressursi vabastamine, kustutab ta võtme.

Esmapilgul töötab see lahendus kenasti, kuid probleem on selles, et meie arhitektuuris tekib ühtne rikke punkt. Mis juhtub, kui peamine Redis'i instants ebaõnnestub? Lisame siis alaminstantsi! Ja kasutame seda, kui peamine on kättesaamatu. Kahjuks pole see variant elujõuline. Selliselt mängides ei suuda me õigesti rakendada vastasseisu omadust, mis on vajalik meie ohutuse tagamiseks, kuna reproduktsioon Redis'is on asünkroonne.

Ilmselgelt tekib sellises mudelis võistlusolukord:

1. Kliendi A blokeering omandatakse peamisel instantsil.
2. Peamine ebaõnnestub enne, kui võti on alaminstantsile edastatud.
3. Alaminstants tõuseb peamiseks.
4. Kliendi B omandab sama ressursi blokeeringu, mis on juba A poolt blokeeritud. OHUTUSE RIKKUMINE!

Mõnikord on täiesti normaalne, et erilistes olukordades, näiteks väljajätmise korral, võivad paljud kliendid samaaegselt hoida lukku. Sellistel juhtudel võib rakendada replikatsioonipõhist lahendust. Muudel juhtudel soovitame järgida selles artiklis kirjeldatud lahendust.

Õige teostamine ühe instantsi puhul

Enne kui püüame ületada ülalkirjeldatud ühe instantsi konfiguratsiooni puudusi, vaatame, kuidas õigesti käituda selles lihtsalt olukorras, kuna selline lahendus on tegelikult lubatud nendes rakendustes, kus võistlusolukord on aeg-ajalt lubatud, samuti seetõttu, et ühe instantsi lukku seadmise aluseks on see, mida kasutatakse siin kirjeldatud hajutatud algoritmis.

Luku omandamiseks teeme järgmist:

SET resource_name my_random_value NX PX 30000

See käsk seab võtme ainult siis, kui see veel ei eksisteeri (valik NX), kehtivusaeg on 30000 millisekundit (valik PX). võtme väärtuseks on "myrandomvalue". See väärtus peab olema unikaalne kõigi klientide ja kõikide lukustamissoovide seas.
Põhimõtteliselt kasutatakse juhuslikku väärtust ohutuks lukustuse vabastamiseks, kasutades skripti, mis teatab Redis'ile: eemalda võti, ainult kui see eksisteerib, ja väärtus, mis on seal salvestatud – on täpselt 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 vabastamist, mille on teinud teine klient. Näiteks võib klient omandada lukustuse, siis jääda mingisugusesse operatsiooni kinni, mis kestab kauem kui esimese lukustuse kehtivusaeg (nii, et võtme kehtivusaeg on juba aegunud), ja hiljem kustutada lukustus, mille seadis mõni teine klient.
Lihtsa DEL'i kasutamine ei ole ohutu, kuna klient võib kustutada lukustuse, mille on seadnud teine klient. Seevastu, kasutades eeltoodud skripti, on iga lukustus „allkirjastatud“ juhuslikku stringiga, seega saab seda kustutada vaid see klient, kes selle varem seadis.

Milline peaks olema see juhuslik string? Arvan, et see peaks olema 20 baiti /dev/urandom'ist, kuid on olemas ka odavamaid viise, et luua piisavalt ainulaadne string teie ees seisvate eesmärkide jaoks. Näiteks on võimalik RC4 külvata /dev/urandom'ist ja seejärel selle põhjal genereerida pseudojuhuslik voog. Lihtsam lahendus hõlmab Unix-aega mikrosekundilise täpsusega pluss kliendi ID; see ei ole nii turvaline, kuid vastab tõenäoliselt enamikus kontekstidest esitatud ülesannetele.

Aeg, mida kasutame võtme eluea näitajana, nimetatakse "lukustuse kehtivuse ajaks". See väärtus on samaaegselt aeg, mille möödudes lukustus automaatselt vabastatakse, ja aeg, mille jooksul kliendil on võimalus tehingut teostada, enne kui teine klient saab omakorda selle ressursi lukustada, ilma et see rikuks tõeliselt vastastikuse välistamise garantiisid. Selline garantii on piiratud vaid kindla ajavahemikuga, mis algab lukustuse omandamise hetkest.

Nii et, oleme arutanud head moodust hankida ja vabastada lukku. System (kui tegemist on mittejaotatud süsteemiga, mis koosneb ühest ja alati kättesaadavast instantsist) on turvaline. Laieneme sellele kontseptsioonile jaotatud süsteemis, kus selliseid garantiisid meil enam ei ole.

Redlock algoritm

Jaotatud versiooni algoritmist eeldatakse, et meil on N peamist Redis't. Need sõlmed on täiesti sõltumatud üksteisest, seetõttu me ei kasuta replikatsiooni ega mingit muud varjatud koordineerimissüsteemi. Oleme juba rääkinud, kuidas turvaliselt hankida ja vabastada lukku ühes instantsis. Eeldame, et algoritm kasutab ühes instantsis töötades seda meetodit. Meie näidetes seame N-iks 5, mis on täiesti mõistlik väärtus. Seetõttu peame kasutama 5 peamist Redis't erinevates arvutites või virtuaalmasinates, et tagada nende põhiline sõltumatuse üksteisest.

Luku saamiseks täidab klient järgmised toimingud:

1. Saab praegust aega millisekundites.
2. Järgneb üritusele kõikide N instantside lukustamine, kasutades kõigil juhtudel sama võtme nime ja juhuslikke väärtusi. Etapi 2 jooksul, kui lukustame iga instantsi, kasutab klient, et see saada, viivitust, mis on piisavalt lühike võrreldes ajaga, mille jooksul lukk automaatselt eemaldatakse. Näiteks kui lukustamise kestus on 10 sekundit, võib viivitus olla vahemikus ~ 5-50 millisekundit. Seega välistatakse olukord, kus klient võib pikka aega lukus olla, püüdes ühendust katkestanud Redis sõlmega: kui instants pole saadaval, püüame võimalikult kiiresti ühendust võtta teise instantsiga.
3. Kliendil on blokeeringu saamiseks arvutada, kui kaua aega on möödunud; selleks lahutab ta praegusest ajast ajamärgi, mis saadi esimese sammu käigus. Ainus hetk, mil blokeering on edukas, on siis, kui klient suudab blokeerida enamikku instantsidest (vähemalt 3), ja kogu aeg, mis kulus blokeeringu saamiseks, on lühem kui blokeeringu kehtivusaeg.
4. Kui blokeering on saadud, on selle kehtivusaeg algne blokeeringu kestus miinuseks möödunud aeg, mis arvutati kolmandas sammus.
5. Kui kliendil ei õnnestu mingil põhjusel blokeeringut saada (kas ei suudeta blokeerida N/2+1 instantsi või on blokeeringu kehtivusaeg negatiivne), siis ta püüab kõik instantsid uuesti vabastada (ka need, mida ta arvas, et ei suutnud blokeerida).

Kas algoritm on asünkroonne?

See algoritm põhineb eeldusel, et kuigi kõikidel protsessidel ei ole sünkroonitud kelli, kulgeb iga protsessi kohaliku aja voog siiski ligikaudu ühes tempos ning viga on väike võrreldes sellele ajale, mille möödudes lukustus automaatselt tühistatakse. See eeldus meenutab olukorda, mis on iseloomulik tavalistele arvutitele: igal arvutil on kohalik kell ja tavaliselt võime loota, et erinevate arvutite ajavahe on väike.

Selles etapis peame oma vastastikuse välistamise reegli täpsemalt sõnastama: vastastikune välistamine on tagatud ainult siis, kui klient, kes lukustuse hoiab, lõpetab tegevuse ajavahemikus, mille jooksul lukustus on kehtiv (see väärtus saadakse 3. sammus), miinus veel natuke aega (kokku mõni millisekund, et kompenseerida ajavahe protsesside vahel).

Sarnaste süsteemide kohta, mis nõuavad ajavahe koordineerimist, räägib järgmine huvitav artikkel: Leases: tõhus veakindel mehhanism jaotatud failide vahemälu järjepidevuse jaoks.

Uuesti proovimine, kui ebaõnnestub

Kui kliendil ei õnnestu lukku saada, peab ta proovima uuesti, läbides juhusliku viivituse; see toimub selleks, et desünkroniseerida mitut klienti, kes üritavad sama ressursi lukku korraga saada (mis võib viia „jaotatud mõistuse” olukorrani, kus ei ole võitjat). Lisaks, mida kiiremini klient üritab enamikku Redis instantsidest lukku saada, seda kitsam on aken, kus jaotatud mõistuse olukord võib tekkida (ja seda vähem on vaja uuesti proovida). Seetõttu peaks klient ideaalis proovima samal ajal saata SET käsud N instantsile multiplexerimise abil.

Siin on oluline rõhutada, kui tähtis on, et kliendid, kes ei suutnud enamikku lukustustest osta, vabastaksid (osaliselt) ostetud lukustused, et ei peaks ootama võtme kehtivusaja lõpuni, enne kui lukustus ressursi üle saab taas ostetud (kuid kui toimub võrgu fragmentatsioon ja klient kaotab ühenduse Redis’i instantsidega, siis tuleb maksta karistus kättesaadavuse rikkumise eest, samal ajal kui oodatakse võtme kehtivusaja lõppemist).

Lukustuse vabastamine

Lukustuse vabastamine on lihtne toiming, mis nõuab lihtsalt, et vabastada kõik instantsid, sõltumata sellest, kas klient arvab, et ta suutis konkreetse instantsi edukalt lukustada.

Turvalisuse kaalutlused

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

Esmaltame, et klient suudab saada enamus instantsidest blokeeritud. Iga instants sisaldab võtme, millel on kõigil sama eluaeg. Siiski määrati iga võtme aeg erineval hetkel, mistõttu kehtivus lõppeb neil erinevalt. Kui esimene võti loodi ajavahemikus, mis ei ole halvem kui T1 (aeg, mille valime enne esimesse serverisse ühendust), ja viimane võti loodi ajavahemikus, mis ei ole halvem kui T2 (aeg, mil saime vastuse viimasest serverist), siis oleme kindlad, et esimene võti, mille kehtivusaeg lõpeb, kehtib vähemalt MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Kõik teised võtmed aeguvad hiljem, seega võime olla kindlad, et kõik võtmed on samal ajal kehtivad vähemalt selle aja jooksul.

Ajal, mil enamik võtitest kehtib, ei saa teine klient blokeeringut omandada, kuna N/2+1 SET NX operatsioon ei saa lõppeda edu saavutamisega, kui juba on olemas N/2+1 võtmed. Seetõttu, kui blokeering on omandatud, ei ole võimalik seda samal hetkel uuesti omandada (see rikuks vastastikuse välistuse omadust).
Tõsi, me tahame veenduda, et mitu klienti, kes üritavad samal ajal blokeeringut omandada, ei saa samal ajal selles õnnestuda.

Kui klient on enamiku instantsidest blokeerinud, kulutades selleks aega umbes või rohkem, kui maksimaalne blokeeringu kestus, siis peab ta blokeeringut kehtetuks ja vabastab instantsid. Seetõttu peame arvestama vaid sellega, et kliendil õnnestus enamus instantsidest blokeerida ajaga, mis on lühem kui kehtivusaeg. Sel juhul, mis puudutab eeltoodud argumenti, aja jooksul MIN_VALIDITY Ükski klient ei tohiks olla suuteline blokeeringut uuesti saama. Seetõttu saavad paljud kliendid blokeerida N/2+1 eksemplari samal ajal (mis lõppeb etapi 2 lõpetamise ajal), ainult juhul, kui enamikule blokeerimise aeg oli pikem kui TTL aeg, muutes blokeeringu kehtetuks.

Kas suudate esitada ametlikku turvalisuse tõestust, tuua välja sarnased olemasolevad algoritmid või leida esitatud lahenduses vea?

Saadavuse kaalutlused

Süsteemi k beschikbaarheid sõltub kolmest peamisest omadusest:

1. Automaatne blokeeringu eemaldamine (kuna võtmete kehtivusaeg lõppeb): lõpuks saavad võtmed uuesti kättesaadavaks, et neid blokeeringuteks kasutada.
2. Fakt, et kliendid aitavad tavaliselt teineteist, eemaldades blokeeringud, kui vajalik blokeering ei ole soetatud või kui see on soetatud ja töö on lõpetatud; seega on täiesti tõenäoline, et me ei pea ootama võtmete aegumist, et uuesti blokeeringut soetada.
3. Kui klient peab lukustuse uuesti saama, ootab ta võrreldes enamiku lukustuste omandamiseks kuluvaga suhteliselt kauem. See vähendab olukorra tekkimise tõenäosust, kus aju on jagatud ressursside konkurentsis.

Kuid pideva saadavuse vähenemise eest tuleb maksta trahvi, mis võrdub TTL-i ajaga võrgu segmentides, seega võivad pidevad segmendid selle trahvi määramatuks muuta. See juhtub igal korral, kui klient omandab lukustuse ja siis katkestatakse teises segmendis enne, kui ta selle vabastada jõuab.

Põhimõtteliselt, kui võrgu segmente on lõputult, võib süsteem olla kättesaamatu lõpmatu aja.

Tõhusus, taastumine tõrgetest ja fsync

Paljud kasutavad Redis't, kuna on vajalik tagada kõrge tulude lukustamise serveri jõudlus, viivituste tasemel, mis on vajalik lukustamise ja vabastamise kujundamiseks, samuti operatsioonide arvu osas, mida suudame sekundis teostada. Selle nõude täitmiseks on olemas suhtlemisstrateegia N Redis serveriga, et vähendada viivitust. See on multiplexerimise strateegia (või nn „vaesestamise multiplexer”, mille korral socket seatakse mitteblokeerivasse režiimi, saadab kõik käsud ja loeb neid hiljem, arvestades, et ajakulu kliendi ja iga instantsiga on sarnane).

Tõsi, tuleb arvesse võtta ka pikaajaliste andmete säilitamise aspekti, kui soovime luua mudeli, millel on usaldusväärne taastamine tõrgete korral.

Tõepoolest, et selgust tuua, oletame, et konfigureerime Redis ilma pikaajalise andmesäilitamiseta. Klient suudab lukustada 3 5 instantsist. Üks instantsidest, mille klient suudab lukustada, taaskäivitub ning selle hetkeni tekib taas 3 instantsi sama ressursi jaoks, mille me saame lukustada, ning teine klient võib omakorda lukustada taaskäitatud instantsi, rikkudes lukustuste eksklusiivsuse turvafunktsiooni.

Kui lubada edasiviivat andmesalvestust (AOF), paraneb olukord veidi. Näiteks saab serverit suurendada, saates käsu SHUTDOWN ja taaskäivitades selle. Kuna Redis'is on aeg tõlgendatud nii, et see jätkub ka serveri väljalülitamisel, ei ole kõik meie nõudmised probleemiks. Kõik on korras seni, kuni katkestus toimub korralikult. Aga mis juhtub elektrikatkestuste korral? Kui Redis on vaikimisi seadistatud nii, et fsync sünkroniseerib kettale iga sekundi järel, on võimalik, et pärast taaskäivitamist jääb meie võtme arvule puudu. Teoreetiliselt, kui me tahame tagada lukustuste turvalisuse igasuguse instantsi taaskäivitamise korral, peame lubama fsync=always andmesalvestuse seadetes. See tapab täielikult jõudluse, viies selle sellisele CP-süsteemide tasemele, mida traditsiooniliselt kasutatakse turvaliste jaotatud lukustuste rakendamiseks.

Kuid olukord on parem, kui esmapilgul tundub. Põhimõtteliselt tagatakse algoritmi turvalisus, kuna pärast tõrget taaskäivitatud instants ei osale enam üheski aktiivses lukustuses.

Selle tagamiseks on vajalik vaid tagada, et instants jääks pärast tõrget kättesaamatuks ajaks, mis veidi ületab meie kasutatava maksimaalse TTL. Nii ootame kõigi tõrke ajal aktiivsete võtmete aegumist ja automaatset vabastamist.

Kasutades viivitusega taaskäivitusi, on põhimõtteliselt võimalik saavutada turvalisust ka siis, kui Redis ei säilita midagi pikaajaliselt. Tuleb märkida, et see võib siiski põhjustada kergendusteenuse rikkumise trahvi. Näiteks, kui enamik instantsidest tõrgeb, muutub süsteem globaalselt kättesaamatuks TTL aja jooksul (ja sellel ajal ei saa ühtegi ressurssi lukustada).

Tõstame algoritmi kättesaadavust: pikendame lukustust

Kui klientide töö koosneb väikestest etappidest, siis on võimalik vähendada vaikimisi määratud lukustusperioodi aega ja rakendada lukustuste pikendamise mehhanismi. Üldiselt, kui klient on arvutuste tegemisega hõivatud ja lukustuse kestuse väärtus ohtlikult väheneb, võib kõikidele instantsidele saata Lua skripti, mis pikendab võtme TTL-i, kui võtme olemasolu jätkub ja selle väärtus on endiselt juhuslik, nagu lukustuse soetamise hetkel.

Klient peaks lukustust uuesti omandatuks pidama ainult juhul, kui tal on õnnestunud enamiku instantside lukustamine lukustuse kehtivuse jooksul.

Tõsi, tehniliselt see algoritm ei muutu, seetõttu peab lukustuste korduvate katsete maksimaalne arv olema piiratud, vastasel juhul võivad kergesti rikkuda kättesaadavuse omadused.

Allikas: habr.com