ProHoster > Blog > administrasie > Verspreide sluiting met Redis

Verspreide sluiting met Redis

Haai Habr!

Vandag bring ons 'n vertaling van 'n komplekse artikel oor die implementering van verspreide sluiting met Redis onder u aandag en nooi ons u uit om te praat oor die vooruitsigte van Redis as 'n onderwerp. Ontleding van die betrokke Redlock-algoritme deur Martin Kleppmann, skrywer van die boek "Hoë vrag toepassings", gegee hier.

Verspreide sluiting is 'n baie nuttige primitief wat in baie omgewings gebruik word waar verskillende prosesse op 'n wedersyds uitsluitende wyse op gedeelde hulpbronne moet werk.

Daar is 'n aantal biblioteke en plasings daar buite wat beskryf hoe om DLM (Distributed Lock Manager) te implementeer met behulp van Redis, maar elke biblioteek volg 'n ander benadering en die waarborge wat hulle verskaf, is redelik swak in vergelyking met wat haalbaar is met effens meer gesofistikeerde ontwerp.

In hierdie artikel sal ons probeer om 'n voorwaardelike kanoniese algoritme te beskryf wat demonstreer hoe om verspreide sluiting met Redis te implementeer. Ons sal praat oor 'n algoritme genoem Rooislot, implementeer dit 'n verspreide slotbestuurder en, na ons mening, is hierdie algoritme veiliger as die gewone enkel-instansie-benadering. Ons hoop die gemeenskap sal dit ontleed, terugvoer gee en dit as 'n beginpunt vir meer komplekse of alternatiewe projekte gebruik.

Implementering

Voordat ons verder gaan na die beskrywing van die algoritme, verskaf ons verskeie skakels na gereedgemaakte implementerings. Hulle kan vir verwysing gebruik word.

Sekuriteit en beskikbaarheid waarborge

Ons gaan ons ontwerp modelleer met net drie eienskappe wat ons dink die minimum waarborge bied wat nodig is om verspreide sluiting effektief te gebruik.

  1. Sekuriteitseiendom: Wedersydse uitsluiting. Op enige gegewe tydstip kan slegs een kliënt die slot vashou.
  2. Beskikbaarheid Eiendom A: Geen dooiepunte nie. Dit is altyd moontlik om uiteindelik 'n slot te verkry, selfs as die kliënt wat die hulpbron gesluit het, misluk of op 'n ander skyfsegment beland.
  3. Beskikbaarheid Eiendom B: Foutverdraagsaamheid. Solank as wat die meerderheid Redis-nodusse loop, kan kliënte slotte verkry en loslaat.

Hoekom implementering gebaseer op mislukking herstel is nie genoeg in hierdie geval
Om te verstaan ​​wat ons gaan verbeter, kom ons ontleed die huidige stand van sake met die meeste verspreide sluitbiblioteke gebaseer op Redis.

Die eenvoudigste manier om 'n hulpbron met Redis te sluit, is om 'n sleutel in die geval te skep. Tipies word 'n sleutel geskep met 'n beperkte leeftyd, dit word bereik met behulp van die verval-funksie wat in Redis verskaf word, so vroeër of later word hierdie sleutel vrygestel (eienskap 2 in ons lys). Wanneer die kliënt die hulpbron moet vrystel, vee dit die sleutel uit.

Met die eerste oogopslag werk hierdie oplossing redelik goed, maar daar is 'n probleem: ons argitektuur skep 'n enkele punt van mislukking. Wat gebeur as die gasheer Redis-instansie misluk? Kom ons voeg dan 'n slaaf by! En ons sal dit gebruik as die aanbieder nie beskikbaar is nie. Ongelukkig is hierdie opsie nie lewensvatbaar nie. Deur dit te doen, sal ons nie die wedersydse uitsluitingseienskap wat ons nodig het om sekuriteit te verseker behoorlik kan implementeer nie, want replikasie in Redis is asynchronies.

Uiteraard kom in so 'n model 'n rastoestand voor:

  1. Kliënt A verkry 'n slot op die meester.
  2. Die meester misluk voordat die sleutelinskrywing aan die slaaf oorgedra word.
  3. Die volgeling word tot leier bevorder.
  4. Kliënt B verkry 'n slot op dieselfde hulpbron wat A reeds gesluit het. SEKURITEITSKENNING!

Soms is dit heeltemal normaal dat in spesiale omstandighede, soos 'n mislukking, baie kliënte die slot op dieselfde tyd kan vashou. In sulke gevalle kan 'n replikasie-gebaseerde oplossing toegepas word. Andersins beveel ons die oplossing aan wat in hierdie artikel beskryf word.

Korrekte implementering met 'n enkele geval

Voordat ons probeer om die tekortkominge van die enkel-instansie-konfigurasie wat hierbo beskryf word te oorkom, laat ons verstaan ​​hoe om hierdie eenvoudige saak behoorlik te hanteer, aangesien hierdie oplossing eintlik geldig is in toepassings waar 'n rastoestand van tyd tot tyd aanvaarbaar is, en ook omdat blokkering op 'n enkele instansie dien as die basis wat gebruik word in die verspreide algoritme wat hier beskryf word.

Om 'n slot te bekom, doen dit:

SET resource_name my_random_value NX PX 30000

Hierdie opdrag installeer slegs 'n sleutel as dit nie reeds bestaan ​​nie (NX-opsie), met 'n geldigheidstydperk van 30000 millisekondes (PX-opsie). Die sleutel is ingestel op "myrandomvalue" Hierdie waarde moet uniek wees vir alle kliënte en alle slotversoeke.
Basies word 'n ewekansige waarde gebruik om die slot veilig vry te stel, met 'n skrif wat vir Redis sê: verwyder die sleutel net as dit bestaan ​​en die waarde daarin gestoor is presies wat verwag is. Dit word bereik deur die volgende Lua-skrif te gebruik:

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

Dit is belangrik om te verhoed dat 'n slot wat deur 'n ander kliënt gehou word, verwyder word. Byvoorbeeld, 'n kliënt kan 'n slot verkry, dan toegesluit word in een of ander operasie wat langer as die eerste slot duur (sodat die sleutel tyd het om te verval), en later die slot wat 'n ander kliënt geplaas het, verwyder.
Die gebruik van 'n eenvoudige DEL is onveilig omdat 'n kliënt 'n slot wat deur 'n ander kliënt gehou word, kan verwyder. In teenstelling hiermee, wanneer die bogenoemde skrif gebruik word, word elke slot "geteken" met 'n ewekansige string, sodat slegs die kliënt wat dit voorheen geplaas het, dit kan verwyder.

Wat moet hierdie ewekansige string wees? Ek raai dit moet 20 grepe van /dev/urandom wees, maar jy kan goedkoper maniere vind om die string uniek genoeg vir jou doeleindes te maak. Byvoorbeeld, dit sal goed wees om RC4 te saai met /dev/urandom en dan 'n pseudo-ewekansige stroom daaruit te genereer. 'n Eenvoudiger oplossing behels 'n kombinasie van unix-tyd in mikrosekonde-resolusie plus die kliënt-ID; dit is nie so veilig nie, maar dit is waarskynlik opgewasse vir die taak in die meeste kontekste.

Die tyd wat ons as maatstaf van die sleutel se leeftyd gebruik, word die "slotleeftyd" genoem. Hierdie waarde is beide die hoeveelheid tyd voordat die slot outomaties vrygestel word en die tyd wat 'n kliënt het om 'n bewerking te voltooi voordat 'n ander kliënt op sy beurt daardie hulpbron kan sluit, sonder om werklik wedersydse uitsluitingswaarborge te oortree. Hierdie waarborg is slegs beperk tot 'n sekere tydsduur, wat begin vanaf die oomblik dat die slot gekoop word.

Ons het dus 'n goeie manier bespreek om 'n slot aan te skaf en vry te stel. Die stelsel (as ons praat van 'n nie-verspreide stelsel wat uit 'n enkele en altyd beskikbare instansie bestaan) is veilig. Kom ons brei hierdie konsep uit na 'n verspreide stelsel, waar ons nie sulke waarborge het nie.

Redlock-algoritme

Die verspreide weergawe van die algoritme neem aan dat ons N Redis-meesters het. Hierdie nodusse is heeltemal onafhanklik van mekaar, so ons gebruik nie replikasie of enige ander implisiete koördinasiestelsel nie. Ons het reeds gedek hoe om 'n slot veilig op 'n enkele geval te verkry en vry te stel. Ons aanvaar dit as vanselfsprekend dat die algoritme, wanneer daar met 'n enkele instansie gewerk word, presies hierdie metode sal gebruik. In ons voorbeelde stel ons N op 5, wat 'n redelike waarde is. Ons sal dus 5 Redis-meesters op verskillende rekenaars of virtuele masjiene moet gebruik om te verseker dat hulle grootliks onafhanklik van mekaar optree.

Om 'n slot te bekom, voer die kliënt die volgende bewerkings uit:

  1. Kry die huidige tyd in millisekondes.
  2. Poog opeenvolgend om 'n slot op alle N gevalle te verkry, met dieselfde sleutelnaam en ewekansige waardes in alle gevalle. In Fase 2, wanneer die kliënt 'n slot op 'n per-instansie basis opstel, gebruik die kliënt 'n vertraging om dit te verkry wat kort genoeg is in vergelyking met die tyd waarna die slot outomaties vrygestel word. Byvoorbeeld, as die blokkeringsduur 10 sekondes is, kan die vertraging in die reeks van ~5-50 millisekondes wees. Dit skakel die situasie uit waarin die kliënt vir 'n lang tyd geblokkeer kan bly terwyl hy probeer om 'n mislukte Redis-nodus te bereik: as die instansie nie beskikbaar is nie, probeer ons so gou as moontlik aan 'n ander instansie koppel.
  3. Om 'n slot te neem, bereken die kliënt hoeveel tyd verloop het; Om dit te doen, trek dit die tydstempel wat in stap 1 verkry is af van die werklike tydwaarde. As en slegs as die kliënt die slot op die meeste gevalle (ten minste 3) kon kry, en die totale tyd wat dit geneem het om die slot te verkry, minder as die slotduur, word die slot geag verkry te wees.
  4. As 'n slot verkry is, word die slottydperk beskou as die oorspronklike slotduur minus die verloop van tyd wat in stap 3 bereken is.
  5. As die kliënt om een ​​of ander rede nie daarin slaag om die slot te kry nie (of dit kon nie N/2+1 gevalle sluit nie, of die sluitduur was negatief), dan sal dit probeer om alle gevalle te ontsluit (selfs dié wat hy gedink het dit nie kon blokkeer nie) ).

Is die algoritme asynchronies?

Hierdie algoritme is gebaseer op die aanname dat, hoewel daar geen gesinchroniseerde klok is waarop alle prosesse sal werk nie, plaaslike tyd in elke proses steeds teen ongeveer dieselfde tempo vloei, en die fout is klein in vergelyking met die totale tyd waarna die slot is outomaties vrygestel. Hierdie aanname stem baie ooreen met die situasie wat tipies is vir gewone rekenaars: elke rekenaar het 'n plaaslike horlosie, en ons kan gewoonlik daarop staatmaak dat die tydsverskil tussen verskillende rekenaars klein is.

Op hierdie punt moet ons ons wedersydse uitsluitingsreël noukeuriger formuleer: wedersydse uitsluiting word slegs gewaarborg as die kliënt wat die slot hou, verlaat gedurende die tyd wat die slot geldig is (hierdie waarde verkry in stap 3), minus nog 'n tyd (totaal 'n paar millisekondes om te kompenseer vir die tydsverskil tussen prosesse).

Die volgende interessante artikel vertel meer oor sulke stelsels wat koördinering van tydintervalle vereis: Huurkontrakte: 'n doeltreffende foutverdraagsame meganisme vir konsekwentheid van verspreide lêerkas.

Herprobeer by mislukking

Wanneer 'n kliënt versuim om 'n slot te bekom, moet hy weer probeer na 'n lukrake vertraging; dit word gedoen om verskeie kliënte te de-sinchroniseer wat probeer om 'n slot op dieselfde hulpbron op dieselfde tyd te verkry (wat kan lei tot 'n "gesplete brein" situasie waarin daar geen wenners is nie). Boonop, hoe vinniger 'n kliënt probeer om 'n slot op 'n meerderheid Redis-gevalle te verkry, hoe nouer is die venster waarin 'n gesplete brein-situasie kan voorkom (en hoe minder is die behoefte aan herproberings). Daarom, ideaal gesproke, moet die kliënt probeer om SET-opdragte gelyktydig na N gevalle te stuur deur multipleksing te gebruik.

Dit is die moeite werd om hier te beklemtoon hoe belangrik dit is vir kliënte wat versuim om die meerderheid slotte te bekom om die (gedeeltelik) verkrygde slotte los te maak, sodat hulle nie hoef te wag dat die sleutel verval voordat die slot op die hulpbron weer verkry kan word nie. (alhoewel as netwerkfragmentasie plaasvind en die kliënt kontak met die Redis-gevalle verloor, moet u 'n beskikbaarheidsboete betaal terwyl u wag dat die sleutel verval).

Maak die slot los

Die vrystelling van 'n slot is 'n eenvoudige operasie wat eenvoudig vereis dat alle gevalle ontsluit word, ongeag of die kliënt blykbaar 'n spesifieke geval suksesvol gesluit het.

Veiligheidsoorwegings

Is die algoritme veilig? Kom ons probeer ons voorstel wat in verskillende scenario's gebeur.

Om mee te begin, kom ons neem aan dat die kliënt 'n slot op die meeste gevalle kon kry. Elke geval sal 'n sleutel bevat met dieselfde leeftyd vir almal. Elkeen van hierdie sleutels is egter op 'n ander tyd geïnstalleer, so hulle sal op verskillende tye verval. Maar, as die eerste sleutel geïnstalleer is op 'n tyd wat nie erger as T1 is nie (die tyd wat ons kies voordat ons die eerste bediener kontak), en die laaste sleutel is geïnstalleer op 'n tyd wat nie slegter as T2 is nie (die tyd waarop die antwoord ontvang is) vanaf die laaste bediener), dan is ons vol vertroue dat die eerste sleutel in die stel wat verval ten minste sal oorleef MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Alle ander sleutels sal later verval, so ons kan seker wees dat alle sleutels vir ten minste hierdie tyd gelyktydig geldig sal wees.

Gedurende die tyd wat die meeste sleutels geldig bly, sal 'n ander kliënt nie die slot kan verkry nie, aangesien N/2+1 SET NX-bewerkings nie kan slaag as N/2+1-sleutels reeds bestaan ​​nie. Sodra 'n slot verkry is, is dit dus onmoontlik om dit op dieselfde oomblik weer te verkry (dit sal die wedersydse uitsluitingseiendom skend).
Ons wil egter seker maak dat verskeie kliënte wat probeer om 'n slot op dieselfde tyd te bekom, nie op dieselfde tyd kan slaag nie.

As die kliënt die meerderheid gevalle vir ongeveer of meer as die maksimum sluitduur gesluit het, sal dit die slot as ongeldig beskou en die gevalle ontsluit. Daarom hoef ons net die geval in ag te neem waarin die kliënt daarin geslaag het om die meeste gevalle binne 'n tyd minder as die vervaldatum te blokkeer. In hierdie geval, met betrekking tot bogenoemde argument, gedurende die tyd MIN_VALIDITY geen kliënt behoort die slot weer te kan bekom nie. Daarom sal baie kliënte N/2+1-gevalle in dieselfde tyd (wat eindig aan die einde van fase 2) kan sluit slegs wanneer die tyd om die meerderheid te sluit groter was as die TTL-tyd, wat die slot ongeldig maak.

Kan jy 'n formele bewys van sekuriteit verskaf, bestaande soortgelyke algoritmes aandui, of 'n fout in die bogenoemde vind?

Toeganklikheidsoorwegings

Stelselbeskikbaarheid hang af van drie hoofkenmerke:

  1. Maak slotte outomaties los (soos sleutels verval): Sleutels sal uiteindelik weer beskikbaar wees om vir slotte gebruik te word.
  2. Die feit dat kliënte mekaar gewoonlik help deur slotte te verwyder wanneer die gewenste slot nie verkry is nie, of verkry is en die werk voltooi is; so dit is waarskynlik dat ons nie hoef te wag dat die sleutels verval om die slot weer te bekom nie.
  3. Die feit dat wanneer 'n kliënt weer moet probeer om 'n slot te bekom, wag dit vir 'n betreklik langer tyd as die tydperk wat nodig is om die meeste slotte te bekom. Dit verminder die waarskynlikheid dat 'n gesplete breinsituasie sal ontstaan ​​wanneer om hulpbronne meeding.

Daar is egter 'n beskikbaarheidstraf gelykstaande aan die TTL van die netwerksegmente, so as daar aaneenlopende segmente is, kan die straf onbepaald wees. Dit gebeur wanneer 'n kliënt 'n slot verkry en dan na 'n ander segment afskeur voordat dit dit kan loslaat.

In beginsel, gegewe oneindige aaneenlopende netwerksegmente, kan 'n stelsel vir 'n oneindige tydperk onbeskikbaar bly.

Werkverrigting, failover en fsync

Baie mense gebruik Redis omdat hulle hoë slotbedienerwerkverrigting benodig in terme van die latensie wat nodig is om slotte te verkry en vry te stel, en die aantal verkrygings/vrystellings wat per sekonde voltooi kan word. Om aan hierdie vereiste te voldoen, is daar 'n strategie om met N Redis-bedieners te kommunikeer om latensie te verminder. Dit is 'n multipleksingstrategie (of "arm man se multipleksing", waar die sok in 'n nie-blokkerende modus gesit word, alle opdragte stuur en die opdragte later lees, met die veronderstelling dat die heen-en terugreistyd tussen die kliënt en elke geval soortgelyk is) .

Ons moet egter ook die oorweging wat verband hou met langtermyn-databerging in ag neem as ons daarna streef om 'n model te skep met betroubare herstel van mislukkings.

Basies, om die probleem op te klaar, kom ons neem aan dat ons Redis konfigureer met geen langtermyn-databerging nie. Die kliënt slaag daarin om 3 uit 5 gevalle te blokkeer. Een van die gevalle wat die kliënt daarin geslaag het om te blokkeer, word herbegin, en op hierdie oomblik is daar weer 3 gevalle vir dieselfde hulpbron, wat ons kan blokkeer, en 'n ander kliënt kan op sy beurt die herbeginde instansie blokkeer, wat die sekuriteitseienskap oortree wat aanvaar eksklusiwiteit van slotte.

As jy data vooruit (AOF) aktiveer, sal die situasie effens verbeter. U kan byvoorbeeld 'n bediener bevorder deur die SHUTDOWN-opdrag te stuur en dit weer te begin. Aangesien vervalbedrywighede in Redis semanties geïmplementeer word op so 'n manier dat tyd aanhou vloei selfs wanneer die bediener afgeskakel is, is al ons vereistes in orde. Dit is normaal solank 'n normale afskakeling verseker word. Wat om te doen in geval van kragonderbrekings? As Redis by verstek gekonfigureer is, met fsync wat elke sekonde op skyf sinchroniseer, dan is dit moontlik dat ons na 'n herbegin nie ons sleutel sal hê nie. Teoreties, as ons slot sekuriteit wil waarborg tydens enige geval herbegin, moet ons aktiveer fsync=always in die instellings vir langtermyn-databerging. Dit sal prestasie heeltemal doodmaak, tot op die vlak van CP-stelsels wat tradisioneel gebruik word om verspreide slotte veilig te implementeer.

Maar die situasie is beter as wat dit met die eerste oogopslag lyk. In beginsel word die sekuriteit van die algoritme bewaar, want wanneer die instansie na 'n mislukking herbegin word, neem dit nie meer deel aan enige slot wat tans aktief is nie.

Om dit te verseker, moet ons net verseker dat na 'n mislukking die instansie onbeskikbaar bly vir 'n tydperk wat die maksimum TTL wat ons gebruik effens oorskry. Op hierdie manier sal ons wag tot die vervaldatum en outomatiese vrystelling van alle sleutels wat aktief was ten tyde van mislukking.

Deur vertraagde herbeginsels te gebruik, is dit in beginsel moontlik om sekuriteit te bereik selfs in die afwesigheid van enige langtermyn-volharding in Redis. Let egter daarop dat dit 'n boete tot gevolg kan hê vir die oortreding van toeganklikheid. Byvoorbeeld, as die meerderheid van die gevalle misluk, sal die stelsel wêreldwyd onbeskikbaar word vir die TTL (en geen hulpbron kan gedurende hierdie tyd geblokkeer word nie).

Ons verhoog die beskikbaarheid van die algoritme: ons brei die blokkering uit

As die werk wat deur kliënte uitgevoer word, uit klein stappe bestaan, is dit moontlik om die verstek-slotduur te verminder en 'n meganisme vir die verlenging van slotte te implementeer. In beginsel, as die kliënt besig is met rekenaarwerk en die slotvervalwaarde is gevaarlik laag, kan jy 'n Lua-skrip stuur na alle gevalle wat die TTL van die sleutel verleng as die sleutel nog bestaan ​​en die waarde daarvan steeds 'n ewekansige waarde is wat verkry word wanneer die slot verkry is.

'n Kliënt moet slegs oorweeg om 'n slot te herwin indien dit daarin geslaag het om die meeste gevalle binne die geldigheidstydperk te sluit.

True, tegnies verander die algoritme nie, so die maksimum aantal herhaalde pogings om slotte te verkry moet beperk word, anders sal die toeganklikheidseienskappe geskend word.

Bron: will.com

Voeg 'n opmerking