ProHoster > Блог > Administrado > Distribuita ŝlosado uzante Redis

Distribuita ŝlosado uzante Redis

Hej Habr!

Hodiaŭ, ni proponas al vi tradukon de kompleksa artikolo pri efektivigo de distribuitaj ŝlosoj uzante Redis kaj diskutas la potencialon de Redis kiel temo. Analizon de la koncerna Redlock-algoritmo provizas Martin Kleppmann, aŭtoro de la libro "Altaj Ŝarĝaj Aplikoj", estas donita tie.

Distribuitaj seruroj estas tre utila primitivo uzata en multaj medioj kie malsamaj procezoj devas labori pri komunaj rimedoj laŭ reciproke ekskluziva maniero.

Ekzistas kelkaj bibliotekoj kaj afiŝoj priskribantaj kiel efektivigi DLM (Distribuitan Ŝlosadministrilon) uzante Redis, sed ĉiu biblioteko uzas sian propran aliron, kaj la garantioj, kiujn ili provizas, estas sufiĉe malfortaj kompare kun tio, kion oni povas atingi per iom pli kompleksa dezajno.

En ĉi tiu artikolo, ni provos priskribi kanonikan algoritmon, kiu montras kiel efektivigi distribuitan ŝlosadon uzante Redis. Ni diskutos algoritmon nomatan RuĝseruroĜi efektivigas distribuitan ŝlosadministrilon, kaj ni kredas, ke ĉi tiu algoritmo estas pli sekura ol la tradicia unu-instanca aliro. Ni esperas, ke la komunumo analizos ĝin, donos rimarkojn, kaj uzos ĝin kiel deirpunkton por pli kompleksaj aŭ alternativaj projektoj.

Efektivigo

Antaŭ ol ni priskribos la algoritmon, ni provizos plurajn ligilojn al ekzistantaj efektivigoj. Ĉi tiuj povas esti uzataj kiel referenco.

Sekurecaj kaj haveblecaj garantioj

Ni modelos nian dezajnon per nur tri ecoj, kiuj laŭ nia kredo provizas la minimumajn garantiojn necesajn por la efika uzo de distribuitaj seruroj.

  1. Sekureca eco: Reciproka ekskludo. Nur unu kliento povas teni seruron samtempe.
  2. Havebleca Eco A: Neniuj Blokoj. Bloko ĉiam povas esti akirita fine, eĉ se la kliento kiu ŝlosis la rimedon malsukcesas aŭ estas movita al malsama diskosegmento.
  3. Havebleca Eco B: Erara Toleremo. Dum plimulto de Redis-nodoj funkcias, klientoj povas akiri kaj liberigi ŝlosojn.

Kial efektivigo bazita sur failover ne sufiĉas en ĉi tiu kazo
Por kompreni kion ni celas plibonigi, ni analizu la nunan staton de aferoj kun plej multaj Redis-bazitaj distribuitaj ŝlosbibliotekoj.

La plej simpla maniero ŝlosi rimedon per Redis estas krei ŝlosilon sur la instanco. Tipe, la ŝlosilo estas kreita kun limigita vivdaŭro, atingita per la funkcio "eksvalidiĝas" de Redis, do la ŝlosilo estas fine liberigita (eco 2 en nia listo). Kiam la kliento bezonas liberigi la rimedon, ĝi forigas la ŝlosilon.

Unuavide, ĉi tiu solvo ŝajnas funkcii, sed estas problemo: nia arkitekturo enkondukas ununuran punkton de fiasko. Kio okazas se la mastra Redis-instanco fiaskas? Ni aldonu sklavon! Kaj uzu ĝin se la mastra ne estas disponebla. Bedaŭrinde, ĉi tio ne estas farebla opcio. Fari tion malhelpus nin ĝuste efektivigi la reciprokan ekskludan econ, kiun ni bezonas por sekureco, ĉar replikado en Redis estas nesinkrona.

Evidente, en tia modelo ekestas konkurskondiĉo:

  1. Kliento A akiras ŝloson sur la majstra.
  2. La mastro malsukcesas antaŭ ol la ŝlosila enigo estas transdonita al la sklavo.
  3. La sekvanto estas promociita al la gvidanto.
  4. Kliento B akiras ŝloson sur la sama rimedo, kiu jam estas ŝlosita de A. SEKURECREMPO!

Iafoje, estas tute normale, ke pluraj klientoj samtempe tenas ŝloson sub specialaj cirkonstancoj, ekzemple dum paneo. En tiaj kazoj, oni povas uzi solvon bazitan sur replikado. Alie, ni rekomendas la solvon priskribitan en ĉi tiu artikolo.

Ĝusta efektivigo kun ununura instanco

Antaŭ ol provi superi la mankojn de la supre priskribita unu-instanca konfiguracio, ni rigardu kiel ĝuste trakti ĉi tiun simplan kazon, ĉar tia solvo efektive estas akceptebla en aplikoj kie konkurkondiĉoj estas foje akcepteblaj, kaj ankaŭ ĉar unu-instanca ŝlosado estas la fundamento uzata en la ĉi tie priskribita distribuita algoritmo.

Por aĉeti seruron, sekvu ĉi tiujn paŝojn:

SET resource_name my_random_value NX PX 30000

Ĉi tiu komando instalas la ŝlosilon nur se ĝi ne jam ekzistas (opcio NX), kun limtempo de 30000 milisekundoj (opcio PX). La ŝlosilo estas agordita al la valoro "myrandomvalue". Ĉi tiu valoro devas esti unika por ĉiuj klientoj kaj ĉiuj ŝlospetoj.
Esence, la hazarda valoro estas uzata por sekure liberigi la ŝloson, uzante skripton kiu diras al Redis forigi la ŝlosilon nur se ĝi ekzistas kaj la valoro konservita en ĝi estas ĝuste tio, kio estis atendita. Ĉi tio estas atingita per la jena Lua-skripto:

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

Ĉi tio gravas por malhelpi alian klienton forigi seruron metitan de alia kliento. Ekzemple, kliento povus aĉeti seruron, poste esti ŝlosita ekstere dum operacio kiu daŭras pli longe ol la komenca seruro (permesante al la ŝlosilo eksvalidiĝi), kaj poste forigi la seruron metitan de alia kliento.
Uzi simplan DEL estas nesekura, ĉar kliento povas forigi seruron antaŭe tenata de alia kliento. Kontraste, kun la supra skripto, ĉiu seruro estas "subskribita" per hazarda ĉeno, do nur la kliento, kiu antaŭe tenis ĝin, povas forigi ĝin.

Kio devus esti ĉi tiu hazarda ĉeno? Mi supozas, ke ĝi devus esti 20 bajtoj de /dev/urandom, sed ekzistas malpli multekostaj manieroj igi la ĉenon sufiĉe unika por viaj celoj. Ekzemple, enigi RC4 en /dev/urandom kaj poste generi pseŭdohazardan fluon el ĝi estus bone. Pli simpla solvo implikas kombini Uniksan tempon kun mikrosekunda distingivo kaj klienta identigilo; ĝi ne estas tiel sekura, sed ĝi verŝajne taŭgas por plej multaj kuntekstoj.

La tempo, kiun ni uzas por mezuri la vivdaŭron de ŝlosilo, nomiĝas la "vivdaŭro de la seruro". Ĉi tiu valoro estas kaj la tempo post kiu la seruro aŭtomate liberiĝas kaj la tempo, kiun kliento devas plenumi operacion antaŭ ol alia kliento povas, siavice, ŝlosi la rimedon sen malobservi la reciprokan ekskludan garantion. Ĉi tiu garantio estas limigita al specifa tempofenestro, kiu komenciĝas kiam la seruro estas akirita.

Do, ni diskutis bonan manieron akiri kaj liberigi ŝloson. La sistemo (se ni parolas pri nedistribuita sistemo konsistanta el ununura, ĉiam havebla instanco) estas sekura. Ni etendu ĉi tiun koncepton al distribuita sistemo, kie ni ne havas tiajn garantiojn.

Redlock-algoritmo

La distribuita versio de la algoritmo supozas, ke ni havas N Redis-mastrojn. Ĉi tiuj nodoj estas tute sendependaj unu de la alia, do ni ne uzas replikadon aŭ ian ajn alian implican kunordigan sistemon. Ni jam priskribis kiel sekure akiri kaj liberigi ŝloson sur unuopa instanco. Ni supozas, ke la algoritmo uzos ĉi tiun metodon kiam ĝi laboras kun unuopa instanco. En niaj ekzemploj, ni agordas N al 5, kio estas akceptebla valoro. Tial, ni devos uzi kvin Redis-mastrojn sur malsamaj komputiloj aŭ virtualaj maŝinoj por certigi, ke ili funkcias plejparte sendepende unu de la alia.

Por aĉeti seruron, la kliento plenumas la jenajn paŝojn:

  1. Akiras la nunan tempon en milisekundoj.
  2. Sinsekve provas akiri ŝloson por ĉiuj N instancoj, uzante la saman ŝlosilnomon kaj hazardajn valorojn en ĉiuj kazoj. En paŝo 2, dum akiro de ŝloso por ĉiu instanco, la kliento uzas prokraston por akiri ĝin, kiu estas sufiĉe mallonga kompare kun la tempo post kiu la ŝloso estas aŭtomate liberigita. Ekzemple, se la daŭro de la ŝloso estas 10 sekundoj, la prokrasto povas esti en la intervalo de ~5-50 milisekundoj. Tio malhelpas situacion en kiu kliento povus resti blokita dum longa tempo provante atingi paneintan Redis-nodon: se instanco ne estas disponebla, ni provas konektiĝi al alia instanco kiel eble plej baldaŭ.
  3. Por akiri ŝloson, la kliento kalkulas kiom da tempo pasis subtrahante la tempstampon akiritan en paŝo 1 de la nuna tempo. Se kaj nur se la kliento sukcesis akiri la ŝloson dum plimulto de kazoj (almenaŭ 3), kaj la tuta tempo bezonata por akiri la ŝloson estas malpli ol la eksvalidiĝtempo de la ŝloso, la ŝloso estas konsiderata akirita.
  4. Se ŝloso estas akirita, tiam ĝia daŭro estas konsiderata kiel la originala ŝlosdaŭro minus la pasinta tempo kalkulita en paŝo 3.
  5. Se la kliento pro iu ajn kialo malsukcesas akiri ŝloson (aŭ ĝi malsukcesas ŝlosi N/2+1 instancojn, aŭ la limtempo de la ŝloso estas negativa), ĝi provos malŝlosi ĉiujn instancojn (eĉ tiujn, kiujn oni pensis, ke ĝi ne povas ŝlosi).

Ĉu la algoritmo estas nesinkrona?

Ĉi tiu algoritmo baziĝas sur la supozo, ke kvankam ne ekzistas sinkronigita horloĝo trans ĉiuj procezoj, la loka tempo en ĉiu procezo ankoraŭ fluas je proksimume la sama rapideco, kaj la eraro estas malgranda kompare kun la tuta tempo post kiu la ŝloso estas aŭtomate liberigita. Ĉi tiu supozo estas tre simila al la situacio tipa por ordinaraj komputiloj: ĉiu komputilo havas lokan horloĝon, kaj ni kutime povas kalkuli, ke la tempa varianco inter malsamaj komputiloj estos malgranda.

Ĉe ĉi tiu punkto, ni bezonas pli zorge formuli nian regulon pri reciproka ekskludo: reciproka ekskludo estas garantiita nur se la kliento tenanta la ŝloson finas la procezon ene de la tempo, kiam la ŝloso estas valida (la valoro akirita en paŝo 3), minus iom da aldona tempo (nur kelkaj milisekundoj por kompensi la tempoprokraston inter procezoj).

La sekva interesa artikolo provizas pliajn detalojn pri similaj sistemoj, kiuj postulas tempo-ŝanĝiĝantan kunordigon: Lizkontraktoj: efika erar-tolerema mekanismo por distribuita dosierkaŝmemora konsistenco.

Reprovu ĉe malsukceso

Kiam kliento malsukcesas akiri ŝlosilon, ĝi devus reprovi post hazarda prokrasto. Ĉi tio estas farita por malhelpi, ke pluraj klientoj samtempe provi akiri ŝlosilon sur la sama rimedo ne plu sinkroniĝu (kio povas konduki al "disigita cerbo" situacio, en kiu ne estas gajnantoj). Krome, ju pli rapide kliento provas akiri ŝlosilon sur plimulto de Redis-instancoj, des pli mallarĝa estas la fenestro, en kiu povas okazi dividita cerbo (kaj des malpli da bezono de reprovoj). Tial, ideale, kliento devus provi samtempe sendi SET-komandojn al N instancoj uzante multipleksadon.

Indas emfazi ĉi tie kiom grave estas por klientoj, kiuj ne sukcesas akiri la plej multajn el siaj ŝlosoj, liberigi (parte) la ŝlosojn, kiujn ili akiris, por ke ili ne devu atendi, ke la ŝlosilo eksvalidiĝu, antaŭ ol ili povu denove akiri ŝloson sur la rimedo (kvankam se okazas reta fragmentiĝo kaj la kliento perdas konekteblecon al la Redis-instancoj, ekzistas puno pro la paneo dum atendado de la ŝlosilo eksvalidiĝu).

Malfermante la seruron

Malŝlosi ŝloson estas simpla operacio, kiu simple postulas malŝlosi ĉiujn instancojn, sendepende de ĉu la kliento kredas, ke ĝi sukcesis ŝlosi specifan instancon.

Sekurecaj konsideroj

Ĉu la algoritmo estas sekura? Ni provu imagi kio okazas en diversaj scenaroj.

Por komenci, ni supozu, ke la kliento sukcesis akiri ŝlosilon por la plej multaj el la instancoj. Ĉiu instanco enhavos ŝlosilon kun la sama vivdaŭro tra ĉiuj instancoj. Tamen, ĉiu el ĉi tiuj ŝlosiloj estis instalita je malsama tempo, do ili eksvalidiĝos je malsamaj tempoj. Tamen, se la unua ŝlosilo estis instalita je tempo ne pli malbona ol T1 (la tempo, kiun ni elektas antaŭ ol kontakti la unuan servilon), kaj la lasta ŝlosilo estis instalita je tempo ne pli malbona ol T2 (la tempo, kiam la respondo de la lasta servilo estis ricevita), tiam ni certas, ke la unua ŝlosilo en la aro eksvalidiĝonta ekzistos dum almenaŭ... MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFTĈiuj aliaj ŝlosiloj eksvalidiĝos poste, do ni povas esti certaj, ke ĉiuj ŝlosiloj validos almenaŭ tiel longe samtempe.

Dum la tempo kiam plej multaj ŝlosiloj restas validaj, alia kliento ne povos akiri seruron, ĉar N/2+1 SET NX operacioj ne povas sukcesi se N/2+1 ŝlosiloj jam ekzistas. Tial, post kiam seruro estas akirita, estas neeble reakiri ĝin samtempe (tio malobservus la reciprokan ekskludan econ).
Tamen, ni volas certigi, ke pluraj klientoj provantaj akiri ŝloson samtempe ne povas samtempe sukcesi.

Se kliento ŝlosis la plej multajn el la instancoj en tempo egala al aŭ pli granda ol la maksimuma ŝlosdaŭro, ĝi konsideros la ŝlosadon malvalida kaj malŝlosos la instancojn. Tial, ni nur bezonas konsideri la kazon, en kiu la kliento sukcesis ŝlosi la plej multajn el la instancoj en tempo pli mallonga ol la ŝlosdaŭro. En ĉi tiu kazo, rilate al la supra argumento, en MIN_VALIDITY Neniu kliento devus povi reakiri ŝloson. Tial, pluraj klientoj povos ŝlosi N/2+1 instancojn en la sama kvanto da tempo (kiu finiĝas ĉe la kompletigo de etapo 2) nur se la plimulto ŝlostempo estis pli granda ol la TTL, kio malvalidigas la ŝloson.

Ĉu vi povas provizi formalan pruvon de sekureco, indiki ekzistantajn similajn algoritmojn, aŭ trovi cimon en tio, kio estis prezentita?

Konsideroj pri alirebleco

La havebleco de sistemo dependas de tri ĉefaj karakterizaĵoj:

  1. Aŭtomata malŝlosado (kiam ŝlosiloj eksvalidiĝas): Ŝlosiloj poste denove estos haveblaj por esti uzataj por seruroj.
  2. La fakto, ke klientoj tipe helpas unu la alian forigante serurojn kiam la dezirata seruro ne estas akirita, aŭ estas akirita sed la laboro estas finita; tial, estas probable, ke ni ne devos atendi ĝis la ŝlosiloj eksvalidiĝos por reakiri seruron.
  3. La fakto, ke kiam kliento bezonas reprovi akiri ŝloson, ĝi atendas relative pli longan periodon ol la periodo bezonata por akiri plej multajn ŝlosojn. Tio reduktas la probablecon de dividita cerbo-situacio ekestiĝanta pro rimeda disputo.

Tamen, ekzistas puno pro reduktita disponebleco egala al la TTL-tempo en retsegmentoj, do se ekzistas apudaj segmentoj, ĉi tiu puno povas fariĝi senfina. Ĉi tio okazas kiam ajn kliento akiras ŝloson kaj poste estas fortranĉita al alia segmento antaŭ ol ĝi povas liberigi ĝin.

Principe, donitaj senfinajn kontinuajn retsegmentojn, la sistemo povus resti neatingebla dum senfina tempodaŭro.

Elfaro, Failover, kaj fsync

Multaj homoj uzas Redis ĉar ili postulas altan rendimenton de seruroj, rilate al la latenteco bezonata por akiri kaj liberigi serurojn, same kiel la nombro da akiroj/liberigoj, kiujn oni povas fari po sekundo. Por plenumi ĉi tiun postulon, ekzistas komunikada strategio por N Redis-serviloj por redukti latentecon. Ĉi tio estas multipleksa strategio (aŭ "malriĉula multipleksado", en kiu la ingo estas agordita al ne-bloka reĝimo, sendas ĉiujn komandojn, kaj prenas komandojn poste, supozante similajn tien-revenajn tempojn inter la kliento kaj ĉiu instanco).

Tamen, ni ankaŭ devas konsideri la longdaŭran stokadon de datumoj se ni volas krei modelon kun fidinda reakiro post fiasko.

Por klarigi la problemon, ni supozu, ke ni agordas Redis sen ia ajn konstanta datumstokado. Kliento sukcesas ŝlosi tri el la kvin instancoj. Unu el la instancoj, kiujn la kliento sukcesis ŝlosi, estas rekomencita, kaj tiam tri instancoj estas denove kreitaj por la sama rimedo, kiujn ni povas ŝlosi. Alia kliento siavice povas ŝlosi la rekomencitan instancon, malobservante la sekurecan econ de ŝlosi-ekskluziveco.

Ebligi antaŭtempan (AOF) plibonigos la situacion iomete. Ekzemple, vi povas antaŭenigi la servilon sendante la komandon SHUTDOWN kaj rekomencante ĝin. Ĉar la operacioj pri eksvalidiĝo de Redis estas semantike efektivigitaj tiel, ke la tempo daŭre fluas eĉ kiam la servilo estas malŝaltita, ĉiuj niaj postuloj estas plenumitaj. Ĉi tio estas bone kondiĉe ke eleganta malŝalto estas certigita. Sed kio pri elektropaneoj? Se Redis estas agordita defaŭlte, kun fsync-sinkronigado al disko ĉiun sekundon, eblas, ke post rekomenco ni perdos nian ŝlosilon. Teorie, se ni volas garantii serursekurecon tra iu ajn instanca rekomenco, ni devus ebligi fsync=always en la agordoj de persistaj datumoj. Tio tute malhelpos la rendimenton, ĝis la nivelo de CP-sistemoj tradicie uzataj por sekure efektivigi distribuitajn ŝlosojn.

Sed la situacio estas pli bona ol ĝi ŝajnas unuarigarde. Principe, la sekureco de la algoritmo estas konservita, ĉar kiam instanco rekomenciĝas post paneo, ĝi jam ne plu partoprenas en iuj ajn nuntempe aktivaj ŝlosoj.

Por garantii tion, ni simple bezonas certigi, ke post paneo, la instanco restu neatingebla dum periodo iomete pli longa ol la maksimuma TTL, kiun ni uzas. Tio permesos al ĉiuj ŝlosiloj, kiuj estis aktivaj dum la paneo, eksvalidiĝi kaj esti aŭtomate liberigitaj.

Per prokrastitaj rekomencoj, eblas atingi sekurecon eĉ sen ia longdaŭra persisto en Redis. Tamen, indas rimarki, ke tio povas rezultigi punon pro malobservoj de disponebleco. Ekzemple, se plimulto de instancoj malsukcesas, la sistemo fariĝos tutmonde neatingebla por la TTL (kaj neniu rimedo povas esti ŝlosita dum ĉi tiu tempo).

Pliigante la haveblecon de la algoritmo: plilongigante la blokperiodon

Se la laboro plenumita de klientoj konsistas el malgrandaj paŝoj, eblas redukti la defaŭltan ŝlosvivdaŭron kaj efektivigi ŝlosrenovigmekanismon. Principe, se kliento okupiĝas pri kalkuloj kaj la ŝlosvivdaŭro estas danĝere malalta, Lua-skripto povus esti sendita al ĉiuj instancoj, kiu plilongigas la ŝlosilvivdaŭron (TTL) se la ŝlosilo ankoraŭ ekzistas kaj ĝia valoro ankoraŭ estas la hazarda valoro akirita kiam la ŝloso estis akirita.

Kliento konsideru ŝloson kiel reakiritan nur se ili sukcese ŝlosis plimulton de la instancoj ene de la valideca periodo.

Tamen, teknike la algoritmo ne ŝanĝiĝas, do la maksimuma nombro da ripetaj provoj akiri ŝlosojn devas esti limigita, alie la disponeblecaj ecoj estos malobservitaj.

fonto: www.habr.com