Jaotatud lukustamine Redise abil

Tere Habr!

Täna juhime teie tähelepanu Redise abil hajutatud lukustamise rakendamist käsitleva keeruka artikli tõlkele ja kutsume teid rääkima Redise kui teema väljavaadetest. Vaatlusaluse Redlocki algoritmi analüüs Martin Kleppmannilt, raamatu "Suure koormusega rakendused", antud siin.

Hajutatud lukustamine on väga kasulik primitiiv, mida kasutatakse paljudes keskkondades, kus erinevad protsessid peavad töötama jagatud ressurssidel üksteist välistaval viisil.

Seal on mitmeid teeke ja postitusi, mis kirjeldavad DLM-i (Distributed Lock Manager) rakendamist Redise abil, kuid iga teegi lähenemine on erinev ja nende pakutavad garantiid on üsna nõrgad võrreldes sellega, mis on saavutatav veidi keerukama disainiga.

Selles artiklis proovime kirjeldada tingimuslikku kanoonilist algoritmi, mis näitab, kuidas Redise abil hajutatud lukustamist rakendada. Räägime algoritmist nimega redlock, rakendab see hajutatud lukuhaldurit ja meie arvates on see algoritm turvalisem kui tavaline ühe eksemplari lähenemisviis. Loodame, et kogukond analüüsib seda, annab tagasisidet ja kasutab seda keerukamate või alternatiivsete projektide lähtepunktina.

Rakendamine

Enne algoritmi kirjelduse juurde asumist pakume mitmeid linke valmisrakendustele. Neid saab kasutada viitamiseks.

• Redlock-rb (rakendus Ruby jaoks). On olemas ka kahvel Redlock-rb, mis lisab paketi (gem) levitamise hõlbustamiseks ja mitte ainult selleks.
• Redlock-py (Pythoni juurutamine).
• Aioredlock (Asyncio Pythoni juurutamine).
• Redlock-php (rakendus PHP jaoks).
• PHPRedisMutex (teine ​​PHP rakendus)
• cheprasov/php-redis-lock (PHP teek lukkude jaoks)
• Redsync (rakendus Go jaoks).
• Redisson (Java juurutamine).
• Redis::DistLock (rakendus Perli jaoks).
• Redlock-cpp (rakendus C++ jaoks).
• Redlock-cs (rakendus C#/.NET jaoks).
• RedLock.net (rakendus C#/.NET jaoks). Toega asünkroonimis- ja lukulaiendustele.
• ScarletLock (konfigureeritava andmesalvestiga C# .NET-i juurutamine)
• Redlock4Net (rakendus C# .NET jaoks)
• node-redlock (rakendus NodeJS-i jaoks). Sisaldab tuge lukkude pikendamiseks.

Turvalisuse ja kättesaadavuse garantiid

Modelleerime oma disaini vaid kolme omadusega, mis meie arvates annavad minimaalsed garantiid, mis on vajalikud hajutatud lukustuse tõhusaks kasutamiseks.

1. Turvaomadus: vastastikune välistamine. Igal ajahetkel saab lukku hoida ainult üks klient.
2. Kättesaadavuse omadus A: ummikuid pole. Alati on võimalik lõpuks lukk hankida, isegi kui ressursi lukustanud klient ebaõnnestub või satub teisele kettasegmendile.
3. Kättesaadavuse omadus B: tõrketaluvus. Kuni enamik Redise sõlmedest töötab, saavad kliendid lukke hankida ja vabastada.

Miks sel juhul tõrke taastamisel põhinevast rakendamisest ei piisa
Et mõista, mida me täiustame, analüüsime praegust olukorda enamiku Redisel põhinevate hajutatud lukustusteekide puhul.

Lihtsaim viis ressursi lukustamiseks Redise abil on eksemplaris võtme loomine. Tavaliselt luuakse võti piiratud elueaga, see saavutatakse Redises pakutava aegumise funktsiooni abil, nii et varem või hiljem see võti vabastatakse (meie loendis on atribuut 2). Kui klient peab ressursi vabastama, kustutab ta võtme.

Esmapilgul töötab see lahendus üsna hästi, kuid on probleem: meie arhitektuur loob ühe tõrkepunkti. Mis juhtub, kui host Redise eksemplar ebaõnnestub? Lisame siis ori! Ja me kasutame seda, kui saatejuht pole saadaval. Kahjuks see variant ei ole elujõuline. Seda tehes ei saa me turvalisuse tagamiseks vajalikku vastastikuse välistamise omadust õigesti rakendada, kuna Redises replikatsioon on asünkroonne.

Ilmselgelt esineb sellises mudelis võistlustingimus:

1. Klient A omandab kapteni lukustuse.
2. Ülemseade ebaõnnestub enne võtme sisestuse edastamist alamseadmele.
3. Järgija ülendatakse juhiks.
4. Klient B omandab luku samale ressursile, mille A on juba lukustanud. TURVALISUSE RIKKUMINE!

Mõnikord on täiesti normaalne, et erilistel asjaoludel, näiteks rikke korral, võivad paljud kliendid lukku korraga käes hoida. Sellistel juhtudel saab rakendada replikatsioonipõhist lahendust. Vastasel juhul soovitame selles artiklis kirjeldatud lahendust.

Õige rakendamine ühe eksemplariga

Enne kui proovite ületada ülalkirjeldatud ühe eksemplari konfiguratsiooni puudusi, mõistkem, kuidas seda lihtsat juhtumit õigesti käsitleda, kuna see lahendus kehtib tegelikult rakendustes, kus võistlustingimused on aeg-ajalt vastuvõetavad, ja ka seetõttu, et blokeerimine üks eksemplar on aluseks, mida kasutatakse siin kirjeldatud hajutatud algoritmis.

Luku saamiseks toimige järgmiselt.

SET resource_name my_random_value NX PX 30000

See käsk installib võtme ainult siis, kui seda veel pole (valik NX), kehtivusajaga 30000 XNUMX millisekundit (PX valik). Võti on seatud "myrandomvalue" See väärtus peab olema ainulaadne kõigi klientide ja kõigi lukustustaotluste puhul.
Põhimõtteliselt kasutatakse luku ohutuks vabastamiseks juhuslikku väärtust, kus skript ütleb Redisele: eemaldage võti ainult siis, kui see on olemas ja sellesse salvestatud väärtus 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 teise kliendi käes oleva luku eemaldamise vältimiseks. Näiteks võib klient hankida luku, seejärel lukustuda mõne toiminguga, mis kestab kauem kui esimene lukk (et võtmel oleks aeg aeguda), ja hiljem eemaldada luku, mille mõni teine ​​klient oli pannud.
Lihtsa DEL-i kasutamine on ebaturvaline, kuna klient saab eemaldada teise kliendi käes oleva luku. Seevastu ülaltoodud skripti kasutamisel on iga lukk "allkirjastatud" juhusliku stringiga, nii et ainult selle varem paigutanud klient saab selle eemaldada.

Mis see juhuslik string peaks olema? Ma arvan, et see peaks olema failist /dev/urandom 20 baiti, kuid võite leida odavamaid viise, kuidas string oma eesmärkide jaoks piisavalt unikaalseks muuta. Näiteks oleks hea külvata RC4 koos /dev/urandom ja seejärel genereerida sellest pseudojuhuslik voog. Lihtsam lahendus hõlmab mikrosekundilise eraldusvõimega unix-aja ja kliendi ID kombinatsiooni; see pole nii turvaline, kuid tõenäoliselt sobib see enamikus kontekstides.

Aega, mida kasutame võtme eluea mõõtmiseks, nimetatakse "luku elueaks". See väärtus on nii aeg, mis kulub enne luku automaatset vabastamist, kui ka aeg, mille klient peab toimingu lõpule viima, enne kui teine ​​​​klient saab selle ressursi lukustada, ilma et see rikuks tegelikult vastastikust välistamise garantiid. See garantii kehtib ainult teatud aja jooksul, mis algab luku ostmise hetkest.

Seega oleme arutanud head viisi luku soetamiseks ja vabastamiseks. Süsteem (kui me räägime hajutamata süsteemist, mis koosneb ühest ja alati kättesaadavast eksemplarist) on turvaline. Laiendame seda kontseptsiooni hajutatud süsteemile, kus meil selliseid garantiisid pole.

Redlocki algoritm

Algoritmi hajutatud versioon eeldab, et meil on N Redise masterit. Need sõlmed on üksteisest täiesti sõltumatud, mistõttu me ei kasuta replikatsiooni ega muid kaudseid koordineerimissüsteeme. Oleme juba käsitlenud, kuidas turvaliselt hankida ja vabastada lukk ühel eksemplaril. Peame enesestmõistetavaks, et ühe eksemplariga töötades kasutab algoritm täpselt seda meetodit. Meie näidetes määrame N väärtuseks 5, mis on mõistlik väärtus. Seega peame erinevates arvutites või virtuaalmasinates kasutama 5 Redise juhtseadet, et tagada nende toimimine üksteisest suuresti sõltumatult.

Luku hankimiseks teeb klient järgmised toimingud:

1. Hangib praeguse aja millisekundites.
2. Püüab järjestikku lukustada kõigil N eksemplaridel, kasutades kõigil juhtudel sama võtme nime ja juhuslikke väärtusi. 2. etapis, kui klient seadistab luku eksemplaripõhiselt, kasutab klient selle hankimiseks viivitust, mis on piisavalt lühike võrreldes ajaga, mille järel lukk automaatselt vabastatakse. Näiteks kui blokeerimise kestus on 10 sekundit, siis võib viivitus olla vahemikus ~5-50 millisekundit. See välistab olukorra, kus klient võib ebaõnnestunud Redise sõlme jõudmisel pikka aega blokeeritud olla: kui eksemplar pole saadaval, proovime võimalikult kiiresti ühenduse luua teise eksemplariga.
3. Luku võtmiseks arvutab klient välja, kui palju aega on möödunud; Selleks lahutab see tegelikust ajaväärtusest ajatempli, mis saadi sammus 1. Kui ja ainult siis, kui kliendil õnnestus enamikul juhtudel (vähemalt 3) lukk hankida, ning kogu aeg, mis kulus saada lukk, lühem kui luku kestus, loetakse lukk omandatuks.
4. Kui lukk on omandatud, loetakse luku kestuseks algne luku kestus, millest on lahutatud sammus 3 arvutatud kulunud aeg.
5. Kui kliendil ei õnnestu mingil põhjusel lukku hankida (kas ta ei saanud lukustada N/2+1 eksemplari või luku kestus oli negatiivne), proovib ta avada kõik eksemplarid (isegi need, mida arvas, et ei saa blokeerida ).

Kas algoritm on asünkroonne?

See algoritm põhineb eeldusel, et kuigi puudub sünkroniseeritud kell, millel kõik protsessid töötaksid, voolab iga protsessi kohalik aeg siiski ligikaudu samas tempos ja viga on väike võrreldes koguajaga, mille järel lukustus toimib. automaatselt vabastatud. See eeldus on väga sarnane tavaarvutitele omasele olukorrale: igal arvutil on lokaalne kell ja enamasti saame arvestada sellega, et ajavahe erinevate arvutite vahel on väike.

Siinkohal peame hoolikamalt sõnastama oma vastastikuse välistamise reegli: vastastikune välistamine on garanteeritud ainult siis, kui lukku hoidev klient väljub luku kehtivuse ajal (see väärtus saadi sammus 3), millest on lahutatud veel mõni aeg (kokku paar millisekundites, et kompenseerida protsesside vahelist ajavahet).

Järgmine huvitav artikkel räägib rohkem sellistest ajavahemike kooskõlastamist nõudvatest süsteemidest: Liisingud: tõhus tõrketaluv mehhanism hajutatud failide vahemälu järjepidevuse tagamiseks.

Proovige ebaõnnestumise korral uuesti

Kui kliendil ei õnnestu lukku hankida, peab ta pärast juhuslikku viivitust uuesti proovima; seda tehakse selleks, et desünkroonida mitu klienti, kes üritavad samaaegselt samale ressursile lukustada (mis võib viia "aju lõhenenud" olukorrani, kus võitjaid pole). Lisaks, mida kiiremini klient üritab enamiku Redise eksemplaride puhul lukku hankida, seda kitsam on aken, milles võib tekkida aju jagunemine (ja seda väiksem on korduskatsete vajadus). Seetõttu peaks klient ideaaljuhul proovima multipleksimist kasutades saata SET-käske korraga N eksemplarile.

Siinkohal tasub rõhutada, kui oluline on klientidel, kes ei suuda enamuse lukke hankida, vabastada (osaliselt) omandatud lukud, et nad ei peaks ootama võtme aegumist, enne kui ressursi lukku saab uuesti hankida (Kuigi kui toimub võrgu killustumine ja klient kaotab ühenduse Redise eksemplaridega, peate võtme aegumist oodates maksma saadavuse trahvi).

Vabastage lukk

Luku vabastamine on lihtne toiming, mis nõuab lihtsalt kõigi eksemplaride lukust avamist, olenemata sellest, kas klient näib olevat konkreetse eksemplari edukalt lukustanud.

Turvakaalutlused

Kas algoritm on ohutu? Proovime ette kujutada, mis juhtub erinevatel stsenaariumidel.

Alustuseks oletame, et kliendil õnnestus enamikul juhtudel lukk saada. Iga eksemplar sisaldab võtit, millel on kõigi jaoks sama eluiga. Kuid kõik need võtmed paigaldati erineval ajal, seega aeguvad need erinevatel aegadel. Kuid kui esimene võti installiti mitte halvemal ajal kui T1 (aeg, mille valime enne esimese serveriga ühenduse võtmist) ja viimane võti installiti mitte halvemal ajal kui T2 (vastuse saamise aeg viimasest serverist), siis oleme kindlad, et komplekti esimene võti, mis aegub, jääb vähemalt ellu MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Kõik teised võtmed aeguvad hiljem, seega võime olla kindlad, et kõik võtmed kehtivad samaaegselt vähemalt selle aja.

Aja jooksul, mil enamik võtmeid kehtib, ei saa teine ​​klient lukku hankida, kuna N/2+1 SET NX-i toimingud ei õnnestu, kui N/2+1 võtmed on juba olemas. Seega, kui lukk on soetatud, ei ole võimalik seda samal hetkel uuesti soetada (see rikuks vastastikust välistamist).
Siiski tahame olla kindlad, et mitu klienti, kes üritavad korraga lukku hankida, ei saaks korraga õnnestuda.

Kui klient on lukustanud enamiku esinemisjuhtudest ligikaudu või kauemaks kui maksimaalne lukustusaeg, loeb ta luku kehtetuks ja avab eksemplarid. Seetõttu peame arvestama vaid juhtumiga, kus kliendil õnnestus enamik juhtumeid blokeerida aegumiskuupäevast lühema aja jooksul. Sel juhul, pidades silmas ülaltoodud argumenti, aja jooksul MIN_VALIDITY ühelgi kliendil ei tohiks olla võimalik lukku uuesti hankida. Seetõttu saavad paljud kliendid lukustada N/2+1 eksemplari samal ajal (mis lõpeb 2. etapi lõpus) ​​ainult siis, kui enamuse lukustamise aeg oli pikem kui TTL aeg, mis muudab luku kehtetuks.

Kas saate esitada ametliku turvatõendi, osutada olemasolevatele sarnastele algoritmidele või leida ülaltoodust vea?

Juurdepääsetavuse kaalutlused

Süsteemi saadavus sõltub kolmest põhiomadusest:

1. Lukkude automaatne vabastamine (võtmete aegumisel): Võtmed on lõpuks taas saadaval, et neid lukkude jaoks kasutada.
2. Asjaolu, et kliendid reeglina abistavad üksteist lukkude eemaldamisega, kui soovitud lukk pole soetatud või on soetatud ja töö on tehtud; seega ei pea me tõenäoliselt ootama, kuni võtmed aeguvad, et lukk uuesti kätte saada.
3. Asjaolu, et kui klient peab uuesti proovima lukku hankida, ootab ta suhteliselt kauem aega, kui kulub enamiku lukkude hankimiseks. See vähendab ressursside pärast konkureerimisel tekkiva ajulõhestumise tõenäosust.

Siiski kehtib võrgusegmentide TTL-iga võrdne kättesaadavustrahv, nii et külgnevate segmentide olemasolul võib trahv olla määramata. See juhtub alati, kui klient omandab luku ja rebib seejärel teise segmendi, enne kui saab selle vabastada.

Põhimõtteliselt, arvestades lõpmatuid külgnevaid võrgusegmente, võib süsteem jääda lõpmatuks ajaks kättesaamatuks.

Jõudlus, tõrkesiirde ja fsync

Paljud inimesed kasutavad Redist, kuna neil on vaja kõrget lukustusserveri jõudlust lukkude hankimiseks ja vabastamiseks vajaliku latentsusaja ning sekundis sooritatavate hankimiste/väljalaskmiste arvu osas. Selle nõude täitmiseks on olemas strateegia N Redise serveritega suhtlemiseks, et vähendada latentsust. See on multipleksimisstrateegia (ehk "vaese mehe multipleksimine", kus pesa pannakse mitteblokeerivasse režiimi, saadab kõik käsud ja loeb käske hiljem, eeldades, et edasi-tagasi aeg kliendi ja iga eksemplari vahel on sarnane) .

Siiski peame arvestama ka pikaajalise andmesalvestusega seotud kaalutlustega, kui püüame luua tõrgetest usaldusväärse taastumisega mudeli.

Põhimõtteliselt oletame probleemi selgitamiseks, et konfigureerime Redise ilma pikaajalise andmete salvestamiseta. Kliendil õnnestub blokeerida 3 juhtu 5-st. Üks eksemplaridest, mille kliendil õnnestus blokeerida, taaskäivitatakse ja praegusel hetkel on sama ressursi jaoks jälle 3 eksemplari, mille saame blokeerida, ja teine ​​klient saab omakorda blokeerida taaskäivitatud eksemplari, rikkudes seda turbeomadust. eeldab lukkude eksklusiivsust.

Kui lubate andmed ette (AOF), paraneb olukord veidi. Näiteks saate serverit reklaamida, saates käsu SHUTDOWN ja taaskäivitades selle. Kuna aegumistoimingud on Redis semantiliselt realiseeritud nii, et aeg jätkub ka siis, kui server on välja lülitatud, on kõik meie nõuded korras. See on normaalne seni, kuni on tagatud normaalne väljalülitus. Mida teha elektrikatkestuse korral? Kui Redis on vaikimisi konfigureeritud nii, et fsync sünkroonib kettal iga sekundi järel, siis on võimalik, et pärast taaskäivitamist pole meil oma võtit. Teoreetiliselt, kui tahame tagada lukuturvalisuse mis tahes eksemplari taaskäivitamise ajal, peaksime lubama fsync=always andmete pikaajalise salvestamise seadetes. See hävitab jõudluse täielikult kuni CP-süsteemide tasemeni, mida traditsiooniliselt kasutatakse hajutatud lukkude turvaliseks rakendamiseks.

Kuid olukord on parem, kui esmapilgul tundub. Põhimõtteliselt säilib algoritmi turvalisus, sest kui eksemplar pärast riket taaskäivitatakse, ei osale see enam üheski hetkel aktiivses lukus.

Selle tagamiseks peame lihtsalt tagama, et eksemplar jääb pärast tõrget kättesaamatuks ajavahemikuks, mis ületab veidi meie kasutatavat maksimaalset TTL-i. Nii ootame aegumiskuupäeva ja kõigi rikke hetkel aktiivsete võtmete automaatse vabastamiseni.

Viivitatud taaskäivitamist kasutades on põhimõtteliselt võimalik saavutada turvalisus ka siis, kui Redis puudub igasugune pikaajaline püsivus. Pange tähele, et juurdepääsetavuse rikkumise eest võib see kaasa tuua trahvi. Näiteks kui enamik eksemplare ebaõnnestub, muutub süsteem TTL-i jaoks globaalselt kättesaamatuks (ja selle aja jooksul ei saa ühtegi ressurssi blokeerida).

Suurendame algoritmi kättesaadavust: pikendame blokeerimist

Kui klientide poolt tehtav töö koosneb väikestest sammudest, on võimalik vaikimisi lukustusaega lühendada ja rakendada lukkude pikendamise mehhanismi. Põhimõtteliselt, kui klient on arvutitööga hõivatud ja luku aegumise väärtus on ohtlikult madal, saate kõigile eksemplaridele saata Lua skripti, mis pikendab võtme TTL-i, kui võti on endiselt olemas ja selle väärtus on ikkagi juhuslik väärtus, mis saadakse lukk sai soetatud.

Klient peaks pidama luku uuesti hankimist ainult siis, kui tal on õnnestunud kehtivusaja jooksul lukustada enamik juhtumeid.

Tõsi, tehniliselt algoritm ei muutu, seega tuleb piirata maksimaalset korduvate lukkude hankimise katsete arvu, vastasel juhul rikutakse ligipääsetavuse omadusi.

Allikas: www.habr.com