Kufunga kwa kusambazwa kwa kutumia Redis

Habari Habr!

Leo tunakuletea tafsiri ya nakala ngumu juu ya utekelezaji wa kufuli iliyosambazwa kwa kutumia Redis na kukualika uzungumze juu ya matarajio ya Redis kama mada. Uchambuzi wa algorithm ya Redlock katika swali kutoka kwa Martin Kleppmann, mwandishi wa kitabu "Maombi ya Mzigo wa Juu", kupewa hapa.

Kufunga kwa kusambazwa ni jambo la asili muhimu sana linalotumika katika mazingira mengi ambapo michakato tofauti lazima ifanyie kazi rasilimali zinazoshirikiwa kwa namna ya kipekee.

Kuna idadi ya maktaba na machapisho huko nje ambayo yanaelezea jinsi ya kutekeleza DLM (Kidhibiti cha Kufungia Kilichosambazwa) kwa kutumia Redis, lakini kila maktaba huchukua njia tofauti na dhamana wanazotoa ni dhaifu kabisa ikilinganishwa na kile kinachoweza kufikiwa na muundo wa kisasa zaidi.

Katika nakala hii, tutajaribu kuelezea algorithm ya kisheria ya masharti ambayo inaonyesha jinsi ya kutekeleza kufuli iliyosambazwa kwa kutumia Redis. Tutazungumza juu ya algorithm inayoitwa Redlock, hutumia kidhibiti cha kufuli kilichosambazwa na, kwa maoni yetu, kanuni hii ni salama kuliko mbinu ya kawaida ya tukio moja. Tunatumahi kuwa jumuiya itaichambua, itatoa maoni, na kuitumia kama kianzio kwa miradi ngumu zaidi au mbadala.

Utekelezaji

Kabla ya kuendelea na maelezo ya algorithm, tunatoa viungo kadhaa vya utekelezaji tayari. Wanaweza kutumika kwa kumbukumbu.

• Redlock-rb (utekelezaji wa Ruby). Kuna pia uma Redlock-rb, ambayo inaongeza kifurushi (gem) kwa urahisi wa usambazaji, na sio tu kwa hiyo.
• Redlock-py (Utekelezaji wa Python).
• Ufungaji wa hewa (utekelezaji wa Asyncio Python).
• Redlock-php (utekelezaji wa PHP).
• PHPRedisMutex (utekelezaji mwingine wa PHP)
• cheprasov/php-redis-lock (Maktaba ya PHP kwa kufuli)
• Usawazishaji upya (utekelezaji wa Go).
• Redisson (utekelezaji wa Java).
• Redis::DistLock (utekelezaji wa Perl).
• Redlock-cpp (utekelezaji wa C++).
• Redlock-cs (utekelezaji wa C#/.NET).
• RedLock.net (utekelezaji wa C#/.NET). Kwa usaidizi wa kusawazisha na viendelezi vya kufunga.
• ScarletLock (utekelezaji wa C# .NET na hifadhi ya data inayoweza kusanidiwa)
• Redlock4Net (utekelezaji wa C# .NET)
• nodi-nyekundu (utekelezaji wa NodeJS). Inajumuisha usaidizi wa kupanua kufuli.

Dhamana ya Usalama na Upatikanaji

Tutaunda muundo wetu na sifa tatu tu ambazo tunafikiri hutoa dhamana ya chini inayohitajika ili kutumia kwa ufanisi kufuli iliyosambazwa.

1. Mali ya usalama: Kutengwa kwa pande zote. Wakati wowote, mteja mmoja tu anaweza kushikilia kufuli.
2. Upatikanaji wa Mali A: Hakuna vikwazo. Inawezekana kila wakati kupata kufuli, hata ikiwa mteja aliyefunga rasilimali atashindwa au kutua kwenye sehemu tofauti ya diski.
3. Upatikanaji wa Mali B: Uvumilivu wa Makosa. Maadamu nodi nyingi za Redis zinafanya kazi, wateja wanaweza kupata na kutoa kufuli.

Kwa nini utekelezaji kulingana na urejesho wa kushindwa haitoshi katika kesi hii
Ili kuelewa ni nini tutaboresha, hebu tuchambue hali ya sasa na maktaba nyingi za kufunga zilizosambazwa kulingana na Redis.

Njia rahisi zaidi ya kufunga rasilimali kwa kutumia Redis ni kuunda ufunguo katika mfano. Kwa kawaida, ufunguo huundwa kwa muda mdogo wa maisha, hii inafanikiwa kwa kutumia kipengele cha kumalizika muda kilichotolewa katika Redis, hivyo mapema au baadaye ufunguo huu unatolewa (mali 2 katika orodha yetu). Wakati mteja anahitaji kutolewa rasilimali, inafuta ufunguo.

Kwa mtazamo wa kwanza, suluhisho hili linafanya kazi vizuri kabisa, lakini kuna tatizo: usanifu wetu unajenga hatua moja ya kushindwa. Ni nini hufanyika ikiwa mfano wa mwenyeji wa Redis utashindwa? Tuongeze mtumwa basi! Na tutaitumia ikiwa mtangazaji hapatikani. Kwa bahati mbaya, chaguo hili haliwezekani. Kwa kufanya hivi, hatutaweza kutekeleza vizuri mali ya kutengwa ambayo tunahitaji kuhakikisha usalama, kwa sababu uigaji katika Redis ni sawa.

Ni wazi, katika mfano kama huu hali ya mbio hufanyika:

1. Mteja A anapata kufuli kwa bwana.
2. Bwana hushindwa kabla ya kuingia muhimu kuhamishiwa kwa mtumwa.
3. Mfuasi anapandishwa cheo na kuwa kiongozi.
4. Mteja B anapata kufuli kwenye rasilimali ile ile ambayo A tayari imefungwa. UKIUKAJI WA USALAMA!

Wakati mwingine ni kawaida kabisa kwamba katika hali maalum, kama vile kutofaulu, wateja wengi wanaweza kushikilia kufuli kwa wakati mmoja. Katika hali kama hizi, suluhisho la replication linaweza kutumika. Vinginevyo, tunapendekeza ufumbuzi ulioelezwa katika makala hii.

Utekelezaji sahihi na mfano mmoja

Kabla ya kujaribu kushinda mapungufu ya usanidi wa hali moja iliyoelezwa hapo juu, hebu tuelewe jinsi ya kushughulikia vizuri kesi hii rahisi, kwa kuwa suluhisho hili ni halali katika maombi ambapo hali ya mbio inakubalika mara kwa mara, na pia kwa sababu kuzuia mfano mmoja hutumika kama msingi ambao unatumika katika algoriti iliyosambazwa iliyofafanuliwa hapa.

Ili kupata kufuli, fanya hivi:

SET resource_name my_random_value NX PX 30000

Amri hii husakinisha ufunguo ikiwa tu haipo (chaguo la NX), na muda wa uhalali wa milisekunde 30000 (chaguo la PX). Ufunguo umewekwa "myrandomvalue" Thamani hii lazima iwe ya kipekee kwa wateja wote na maombi yote ya kufunga.
Kimsingi, thamani ya nasibu hutumika kuachilia kufuli kwa usalama, kwa hati inayoambia Redis: ondoa tu ufunguo ikiwa upo na thamani iliyohifadhiwa ndani yake ndiyo hasa iliyotarajiwa. Hii inafanikiwa kwa kutumia hati ifuatayo ya Lua:

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

Hii ni muhimu ili kuzuia kufuli iliyoshikiliwa na mteja mwingine kutoka kwa kuondolewa. Kwa mfano, mteja anaweza kupata kufuli, kisha kufungwa katika baadhi ya operesheni ambayo hudumu zaidi ya kufuli ya kwanza (ili ufunguo upate muda wa kuisha), na baadaye kuondoa kufuli ambayo mteja mwingine alikuwa ameweka.
Kutumia DEL rahisi si salama kwa sababu mteja anaweza kuondoa kufuli iliyoshikiliwa na mteja mwingine. Kinyume chake, unapotumia hati iliyo hapo juu, kila kufuli "hutiwa saini" kwa mfuatano wa nasibu, kwa hivyo ni mteja tu aliyeiweka hapo awali anayeweza kuiondoa.

Je, mfuatano huu wa nasibu unapaswa kuwa nini? Nadhani inapaswa kuwa ka 20 kutoka /dev/urandom, lakini unaweza kupata njia za bei nafuu za kufanya kamba kuwa ya kipekee vya kutosha kwa madhumuni yako. Kwa mfano, itakuwa sawa kuweka RC4 na /dev/urandom na kisha kutoa mtiririko wa bahati nasibu kutoka kwayo. Suluhisho rahisi zaidi linajumuisha mchanganyiko wa wakati mmoja katika azimio la microsecond pamoja na kitambulisho cha mteja; si salama, lakini pengine ni juu ya kazi katika mazingira mengi.

Muda tunaotumia kama kipimo cha maisha ya ufunguo unaitwa "maisha ya kufunga". Thamani hii ni kiasi cha muda kabla ya kufuli kutolewa kiotomatiki na muda ambao mteja analazimika kukamilisha operesheni kabla ya mteja mwingine kufunga nyenzo hiyo, bila kukiuka dhamana za kuheshimiana za kutengwa. Dhamana hii ni mdogo tu kwa dirisha fulani la wakati, ambalo huanza kutoka wakati lock inunuliwa.

Kwa hivyo tumejadili njia nzuri ya kupata na kutolewa kufuli. Mfumo (ikiwa tunazungumza juu ya mfumo usiosambazwa unaojumuisha mfano mmoja na unaopatikana kila wakati) ni salama. Wacha tuongeze dhana hii kwa mfumo uliosambazwa, ambapo hatuna dhamana kama hizo.

Algorithm ya kufunga upya

Toleo lililosambazwa la algoriti huchukulia kuwa tuna N Redis masters. Nodi hizi hazitegemei kabisa zenyewe, kwa hivyo hatutumii urudufishaji au mfumo mwingine wowote wa uratibu usio wazi. Tayari tumeshughulikia jinsi ya kupata na kutoa kufuli kwa njia salama katika tukio moja. Tunachukua kuwa algorithm, wakati wa kufanya kazi na mfano mmoja, itatumia hasa njia hii. Katika mifano yetu tunaweka N hadi 5, ambayo ni thamani inayofaa. Kwa hivyo, tutahitaji kutumia mabwana 5 wa Redis kwenye kompyuta tofauti au mashine za kawaida ili kuhakikisha kwamba wanatenda kwa kiasi kikubwa bila kujitegemea.

Ili kupata kufuli, mteja hufanya shughuli zifuatazo:

1. Hupata wakati wa sasa katika milisekunde.
2. Hujaribu kupata kufuli kwa matukio yote ya N, kwa kutumia jina la ufunguo sawa na thamani nasibu katika visa vyote. Katika Hatua ya 2, mteja anapoweka kufuli kwa kila tukio, mteja hutumia ucheleweshaji ili kuipata ambayo ni fupi ya kutosha ikilinganishwa na wakati ambapo kufuli hutolewa kiotomatiki. Kwa mfano, ikiwa muda wa kuzuia ni sekunde 10, basi ucheleweshaji unaweza kuwa kati ya milisekunde 5-50. Hii huondoa hali ambayo mteja anaweza kubaki kuzuiwa kwa muda mrefu akijaribu kufikia nodi ya Redis iliyoshindwa: ikiwa mfano haupatikani, basi tunajaribu kuunganisha kwenye tukio lingine haraka iwezekanavyo.
3. Kuchukua lock, mteja anahesabu muda gani umepita; Ili kufanya hivyo, huondoa kutoka kwa thamani halisi ya muda muhuri wa wakati uliopatikana katika hatua ya 1. Iwapo na tu ikiwa mteja aliweza kupata kufuli katika matukio mengi (angalau 3), na jumla ya muda uliochukuliwa pata lock, chini ya muda wa kufuli, lock inachukuliwa kuwa imepatikana.
4. Ikiwa kufuli imepatikana, muda wa kufuli unachukuliwa kuwa muda wa kufuli asilia ukiondoa muda uliopita uliokokotolewa katika hatua ya 3.
5. Ikiwa mteja atashindwa kupata kufuli kwa sababu fulani (ama haikuweza kufunga matukio ya N/2+1, au muda wa kufuli ulikuwa hasi), basi itajaribu kufungua hali zote (hata zile alizofikiria kuwa haziwezi kuzizuia). )

Je, algorithm ni sawa?

Algorithm hii inatokana na dhana kwamba, ingawa hakuna saa iliyosawazishwa ambayo michakato yote ingefanya kazi, wakati wa ndani katika kila mchakato bado unapita kwa takriban kasi sawa, na kosa ni ndogo ikilinganishwa na jumla ya muda ambao kufuli huwekwa. iliyotolewa moja kwa moja. Dhana hii ni sawa na hali ya kawaida kwa kompyuta za kawaida: kila kompyuta ina saa ya ndani, na tunaweza kuhesabu ukweli kwamba tofauti ya wakati kati ya kompyuta tofauti ni ndogo.

Katika hatua hii, ni lazima tuunde kwa uangalifu zaidi sheria yetu ya kutengwa ya pande zote mbili: kutengwa kwa pande zote kunahakikishwa ikiwa tu mteja anayeshikilia kufuli anatoka wakati kufuli ni halali (thamani hii iliyopatikana katika hatua ya 3), ukiondoa muda zaidi (jumla ya wachache). milisekunde ili kufidia tofauti ya wakati kati ya michakato).

Nakala ifuatayo ya kupendeza inaelezea zaidi juu ya mifumo kama hii ambayo inahitaji uratibu wa vipindi vya wakati: Ukodishaji: utaratibu mzuri wa kustahimili makosa kwa uthabiti wa akiba ya faili iliyosambazwa.

Jaribu tena kushindwa

Wakati mteja anashindwa kupata kufuli, lazima ajaribu tena baada ya kuchelewa kwa nasibu; hii inafanywa ili kusawazisha wateja wengi wanaojaribu kupata kufuli kwenye rasilimali moja kwa wakati mmoja (ambayo inaweza kusababisha hali ya "mgawanyiko wa ubongo" ambapo hakuna washindi). Zaidi ya hayo, kwa kasi mteja anapojaribu kupata kufuli kwenye matukio mengi ya Redis, ndivyo dirisha linavyopunguza ambapo hali ya mgawanyiko wa ubongo inaweza kutokea (na hitaji la kujaribu tena kupungua). Kwa hivyo, kwa hakika, mteja anapaswa kujaribu kutuma amri za SET kwa matukio ya N wakati huo huo kwa kutumia multiplexing.

Inafaa kusisitiza hapa jinsi ilivyo muhimu kwa wateja ambao wanashindwa kupata idadi kubwa ya kufuli kutoa kufuli (sehemu) zilizopatikana, ili wasisubiri ufunguo kuisha kabla ya kufuli kwenye rasilimali kununuliwa tena. (ingawa ikiwa mgawanyiko wa mtandao utatokea , na mteja atapoteza mawasiliano na matukio ya Redis, basi unapaswa kulipa adhabu ya upatikanaji wakati unasubiri ufunguo kuisha).

Achilia kufuli

Kutoa kufuli ni operesheni rahisi ambayo inahitaji tu kufungua matukio yote, bila kujali kama mteja anaonekana kuwa amefunga mfano fulani.

Mazingatio ya Usalama

Je, algorithm ni salama? Hebu jaribu kufikiria nini kinatokea katika matukio tofauti.

Kuanza, hebu tuchukulie kuwa mteja aliweza kupata kufuli katika hali nyingi. Kila mfano utakuwa na ufunguo wenye maisha sawa kwa wote. Walakini, kila funguo hizi ziliwekwa kwa wakati tofauti, kwa hivyo zitaisha kwa nyakati tofauti. Lakini, ikiwa ufunguo wa kwanza umewekwa kwa wakati usio mbaya zaidi kuliko T1 (wakati ambao tunachagua kabla ya kuwasiliana na seva ya kwanza), na ufunguo wa mwisho uliwekwa kwa wakati usio mbaya zaidi kuliko T2 (wakati ambapo majibu yalipokelewa. kutoka kwa seva ya mwisho), basi tuna hakika kwamba ufunguo wa kwanza katika seti ambayo muda wake utaisha utaishi angalau MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Vifunguo vingine vyote vitakwisha muda baadaye, kwa hivyo tunaweza kuwa na uhakika kwamba funguo zote zitakuwa halali kwa wakati mmoja kwa angalau wakati huu.

Katika muda ambao funguo nyingi zinasalia kuwa halali, mteja mwingine hataweza kupata kufuli, kwa kuwa utendakazi wa N/2+1 SET NX hauwezi kufaulu ikiwa funguo za N/2+1 tayari zipo. Kwa hivyo, mara tu kufuli kumepatikana, haiwezekani kuipata tena kwa wakati mmoja (hii itakiuka mali ya kutengwa kwa pande zote).
Hata hivyo, tunataka kuhakikisha kuwa wateja wengi wanaojaribu kupata kufuli kwa wakati mmoja hawawezi kufaulu kwa wakati mmoja.

Ikiwa mteja amefunga matukio mengi kwa takriban au zaidi ya muda wa juu zaidi wa kufuli, itazingatia kufuli kuwa si sahihi na kufungua matukio. Kwa hiyo, tunapaswa kuzingatia tu kesi ambayo mteja aliweza kuzuia matukio mengi kwa muda chini ya tarehe ya kumalizika muda wake. Katika kesi hii, kuhusu hoja hapo juu, wakati wa wakati MIN_VALIDITY hakuna mteja anayepaswa kuwa na uwezo wa kupata tena kufuli. Kwa hivyo, wateja wengi wataweza kufunga matukio ya N/2+1 kwa wakati mmoja (ambayo huisha mwishoni mwa hatua ya 2) tu wakati muda wa kufunga nyingi ulikuwa mkubwa kuliko saa ya TTL, ambayo hufanya kufuli kuwa batili.

Je, unaweza kutoa uthibitisho rasmi wa usalama, kuonyesha algoriti zilizopo sawa, au kupata hitilafu katika yaliyo hapo juu?

Mazingatio ya Ufikiaji

Upatikanaji wa mfumo hutegemea sifa kuu tatu:

1. Toa kufuli kiotomatiki (vitufe huisha muda wake): Vifunguo vitapatikana tena ili kutumika kwa kufuli.
2. Ukweli kwamba wateja kawaida husaidia kila mmoja kwa kuondoa kufuli wakati kufuli inayohitajika haijapatikana, au imepatikana na kazi imekamilika; kwa hivyo kuna uwezekano kwamba hatutahitaji kusubiri funguo kuisha ili kupata tena kufuli.
3. Ukweli kwamba wakati mteja anahitaji kujaribu tena kupata kufuli, husubiri kwa muda mrefu zaidi kulinganisha na kipindi kinachohitajika ili kupata kufuli nyingi. Hii inapunguza uwezekano wa hali ya mgawanyiko wa ubongo kutokea wakati wa kushindana kwa rasilimali.

Walakini, kuna adhabu ya upatikanaji sawa na TTL ya sehemu za mtandao, kwa hivyo ikiwa kuna sehemu zinazounganishwa, adhabu inaweza kuwa ya muda usiojulikana. Hii hutokea wakati mteja anapata kufuli na kisha kuchomoka hadi sehemu nyingine kabla ya kuifungua.

Kimsingi, kwa kuzingatia sehemu za mtandao zisizo na kikomo, mfumo unaweza kubaki haupatikani kwa muda usio na kipimo.

Utendaji, kushindwa na fsync

Watu wengi hutumia Redis kwa sababu wanahitaji utendaji wa seva ya kufuli ya juu kulingana na muda wa kusubiri unaohitajika ili kupata na kutoa kufuli, na idadi ya usakinishaji/matoleo ambayo yanaweza kukamilishwa kwa sekunde. Ili kukidhi hitaji hili, kuna mkakati wa kuwasiliana na seva za N Redis ili kupunguza muda wa kusubiri. Huu ni mkakati wa kuzidisha (au "kuzidisha kwa mtu maskini", ambapo soketi huwekwa katika hali isiyozuia, kutuma amri zote, na kusoma amri baadaye, ikizingatiwa kuwa wakati wa kurudi na kurudi kati ya mteja na kila mfano ni sawa) .

Hata hivyo, tunapaswa pia kuzingatia uzingatiaji unaohusishwa na hifadhi ya data ya muda mrefu ikiwa tunajitahidi kuunda muundo na uokoaji wa kuaminika kutokana na kushindwa.

Kimsingi, ili kufafanua suala hilo, wacha tufikirie kuwa tunasanidi Redis bila uhifadhi wa data wa muda mrefu hata kidogo. Mteja anaweza kuzuia matukio 3 kati ya 5. Moja ya matukio ambayo mteja aliweza kuzuia imeanzishwa upya, na kwa wakati huu kuna matukio 3 tena kwa rasilimali hiyo hiyo, ambayo tunaweza kuzuia, na mteja mwingine anaweza, kwa upande wake, kuzuia tukio lililoanzishwa upya, kukiuka mali ya usalama ambayo inachukua upekee wa kufuli.

Ikiwa utawezesha data mbele (AOF), hali itaboresha kidogo. Kwa mfano, unaweza kukuza seva kwa kutuma amri ya SHUTDOWN na kuianzisha upya. Kwa kuwa shughuli za mwisho wa matumizi katika Redis hutekelezwa kisemantiki kwa njia ambayo muda unaendelea kutiririka hata seva inapozimwa, mahitaji yetu yote ni sawa. Hii ni kawaida mradi kuzima kwa kawaida kumehakikishwa. Nini cha kufanya katika kesi ya kukatika kwa umeme? Ikiwa Redis imeundwa kwa chaguo-msingi, na usawazishaji wa fsync kwenye diski kila sekunde, basi inawezekana kwamba baada ya kuanza upya hatutakuwa na ufunguo wetu. Kinadharia, ikiwa tunataka kuhakikisha usalama wa kufuli wakati wa kuwasha tena kwa mfano wowote, tunapaswa kuwasha fsync=always katika mipangilio ya uhifadhi wa data wa muda mrefu. Hii itaua utendakazi kabisa, hadi kiwango cha mifumo ya CP ambayo jadi hutumiwa kutekeleza kufuli zilizosambazwa kwa usalama.

Lakini hali ni nzuri zaidi kuliko inaonekana katika mtazamo wa kwanza. Kimsingi, usalama wa algoriti huhifadhiwa kwa sababu mfano unapoanzishwa upya baada ya kutofaulu, haushiriki tena katika kufuli yoyote ambayo inatumika kwa sasa.

Ili kuhakikisha hili, tunahitaji tu kuhakikisha kwamba baada ya kushindwa mfano unabaki kuwa haupatikani kwa muda unaozidi kiwango cha juu cha TTL tunachotumia. Kwa njia hii tutasubiri hadi tarehe ya kumalizika muda na kutolewa kwa moja kwa moja kwa funguo zote ambazo zilikuwa zikifanya kazi wakati wa kushindwa.

Kutumia kuanza tena kuchelewa, kimsingi inawezekana kufikia usalama hata kwa kukosekana kwa uvumilivu wowote wa muda mrefu katika Redis. Kumbuka, hata hivyo, kwamba hii inaweza kusababisha faini kwa kukiuka ufikivu. Kwa mfano, ikiwa matukio mengi hayatafaulu, mfumo hautapatikana duniani kote kwa TTL (na hakuna nyenzo inayoweza kuzuiwa kwa wakati huu).

Tunaongeza upatikanaji wa algorithm: tunapanua kuzuia

Ikiwa kazi iliyofanywa na wateja ina hatua ndogo, inawezekana kupunguza muda wa kufuli chaguo-msingi na kutekeleza utaratibu wa kupanua kufuli. Kimsingi, ikiwa mteja anashughulika na kompyuta na thamani ya kuisha kwa kufuli iko chini sana, unaweza kutuma hati ya Lua kwa hali zote zinazopanua TTL ya ufunguo ikiwa ufunguo bado upo na thamani yake bado ni thamani ya nasibu inayopatikana wakati kufuli ilipatikana.

Mteja anapaswa kuzingatia tu kufuli itakayopatikana tena ikiwa imeweza kufunga matukio mengi ndani ya kipindi cha uhalali.

Kweli, kitaalam algorithm haibadilika, kwa hivyo idadi ya juu ya majaribio ya mara kwa mara ya kupata kufuli lazima iwe mdogo, vinginevyo sifa za ufikiaji zitakiukwa.

Chanzo: mapenzi.com