ProHoster > Blogi > antaminen > Hajautettu lukitus Rediksen avulla

Hajautettu lukitus Rediksen avulla

Hei Habr!

Tänään tuomme huomiosi käännöksen monimutkaisesta artikkelista, joka koskee hajautetun lukituksen toteuttamista Rediksen avulla, ja kutsumme sinut keskustelemaan Rediksen näkymistä aiheena. Kyseisen Redlock-algoritmin analyysi Martin Kleppmannilta, kirjan kirjoittajaKorkean kuormituksen sovellukset", annettu täällä.

Hajautettu lukitus on erittäin hyödyllinen primitiivi, jota käytetään monissa ympäristöissä, joissa eri prosessien on toimittava jaetuilla resursseilla toisensa poissulkevalla tavalla.

Siellä on useita kirjastoja ja julkaisuja, jotka kuvaavat DLM:n (Distributed Lock Manager) käyttöönottoa Rediksen avulla, mutta jokaisessa kirjastossa on erilainen lähestymistapa, ja niiden tarjoamat takuut ovat melko heikkoja verrattuna siihen, mikä on saavutettavissa hieman hienostuneemmalla suunnittelulla.

Tässä artikkelissa yritämme kuvata ehdollisen kanonisen algoritmin, joka osoittaa, kuinka hajautettu lukitus toteutetaan Redisillä. Puhumme algoritmista nimeltä redlock, se toteuttaa hajautetun lukonhallinnan, ja mielestämme tämä algoritmi on turvallisempi kuin tavallinen yhden esiintymän lähestymistapa. Toivomme, että yhteisö analysoi sen, antaa palautetta ja käyttää sitä lähtökohtana monimutkaisemmille tai vaihtoehtoisille projekteille.

Toteutus

Ennen kuin siirrymme algoritmin kuvaukseen, tarjoamme useita linkkejä valmiisiin toteutuksiin. Niitä voidaan käyttää viitteenä.

Turvallisuus ja saatavuustakuu

Aiomme mallintaa suunnittelumme vain kolmella ominaisuudella, joiden uskomme antavan vähimmäistakuut, joita tarvitaan hajautetun lukituksen tehokkaaseen käyttöön.

  1. Turvallisuusominaisuus: Keskinäinen poissulkeminen. Kulloinkin vain yksi asiakas voi pitää lukkoa.
  2. Saatavuus Kiinteistö A: Ei umpikujaa. Lukitus on aina mahdollista hankkia, vaikka resurssin lukinnut asiakas epäonnistuu tai päätyy eri levysegmenttiin.
  3. Saatavuus Ominaisuus B: Vikasietoisuus. Niin kauan kuin suurin osa Redis-solmuista on käynnissä, asiakkaat voivat hankkia ja vapauttaa lukkoja.

Miksi virheenpalautukseen perustuva toteutus ei tässä tapauksessa riitä
Ymmärtääksemme, mitä aiomme parantaa, analysoidaan useimpien Redikseen perustuvien hajautettujen lukituskirjastojen nykytilaa.

Yksinkertaisin tapa lukita resurssi Rediksen avulla on luoda instanssiin avain. Tyypillisesti avain luodaan rajoitetulla käyttöiällä, tämä saavutetaan Rediksen tarjoaman vanhenemisominaisuuden avulla, joten ennemmin tai myöhemmin tämä avain vapautetaan (ominaisuus 2 luettelossamme). Kun asiakkaan on vapautettava resurssi, se poistaa avaimen.

Ensi silmäyksellä tämä ratkaisu toimii varsin hyvin, mutta siinä on ongelma: arkkitehtuurimme luo yhden virhepisteen. Mitä tapahtuu, jos isäntä Redis-ilmentymä epäonnistuu? Lisätään sitten orja! Ja käytämme sitä, jos esittäjä ei ole tavoitettavissa. Valitettavasti tämä vaihtoehto ei ole käyttökelpoinen. Näin tekemällä emme pysty kunnolla toteuttamaan keskinäistä poissulkemisominaisuutta, jota tarvitsemme turvallisuuden varmistamiseksi, koska replikointi Redisissä on asynkronista.

Ilmeisesti tällaisessa mallissa esiintyy kilpailutilanne:

  1. Asiakas A saa lukon isäntäkoneeseen.
  2. Isäntä epäonnistuu ennen kuin avaimen syöttö siirretään orjalle.
  3. Seuraaja ylennetään johtajaksi.
  4. Asiakas B hankkii lukon samalle resurssille, jonka A on jo lukinnut. TURVALLISUUDEN RIKKOMUS!

Joskus on täysin normaalia, että erityisissä olosuhteissa, kuten vika, monet asiakkaat voivat pitää lukkoa yhtä aikaa. Tällaisissa tapauksissa voidaan käyttää replikointiin perustuvaa ratkaisua. Muussa tapauksessa suosittelemme tässä artikkelissa kuvattua ratkaisua.

Oikea toteutus yhdellä instanssilla

Ennen kuin yritämme voittaa yllä kuvatut yhden ilmentymän konfiguraation puutteet, on ymmärrettävä, kuinka tämä yksinkertainen tapaus käsitellään oikein, koska tämä ratkaisu on itse asiassa pätevä sovelluksissa, joissa kilpailutilanne on ajoittain hyväksyttävä, ja myös siksi, että esto yksi ilmentymä toimii perustana, jota käytetään tässä kuvatuissa hajautetuissa algoritmeissa.

Voit hankkia lukon seuraavasti:

SET resource_name my_random_value NX PX 30000

Tämä komento asentaa avaimen vain, jos sitä ei vielä ole (NX-vaihtoehto), ja sen voimassaoloaika on 30000 XNUMX millisekuntia (PX-vaihtoehto). Avain on asetettu asentoon "myrandomvalue" Tämän arvon on oltava yksilöllinen kaikissa asiakkaissa ja kaikissa lukituspyynnöissä.
Periaatteessa lukon vapauttamiseen turvallisesti käytetään satunnaista arvoa, jossa komentosarja kertoo Redis: poista avain vain, jos se on olemassa ja siihen tallennettu arvo on juuri sitä mitä odotettiin. Tämä saavutetaan käyttämällä seuraavaa Lua-skriptiä:

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

Tämä on tärkeää, jotta estetään toisen asiakkaan hallussa olevan lukon poistaminen. Asiakas voi esimerkiksi hankkia lukon, sitten lukkiutua johonkin toimintoon, joka kestää kauemmin kuin ensimmäinen lukko (jotta avaimella ehtii vanhentua), ja myöhemmin poistaa toisen asiakkaan asettaman lukon.
Yksinkertaisen DEL:n käyttäminen ei ole turvallista, koska asiakas voi poistaa toisen asiakkaan hallussa olevan lukon. Sitä vastoin yllä olevaa komentosarjaa käytettäessä jokainen lukko "allekirjoitetaan" satunnaisella merkkijonolla, joten vain sen aiemmin sijoittanut asiakas voi poistaa sen.

Mikä tämän satunnaisen merkkijonon pitäisi olla? Oletan, että sen pitäisi olla 20 tavua tiedostosta /dev/urandom, mutta voit löytää halvempia tapoja tehdä merkkijonosta riittävän ainutlaatuinen tarkoituksiin. Esimerkiksi olisi hyvä siementää RC4 tiedostoon /dev/urandom ja sitten luoda siitä näennäissatunnainen stream. Yksinkertaisempi ratkaisu sisältää mikrosekunnin resoluution unix-ajan ja asiakastunnuksen yhdistelmän; se ei ole yhtä turvallinen, mutta se on todennäköisesti tehtävänsä mukainen useimmissa yhteyksissä.

Aikaa, jota käytämme avaimen käyttöiän mittaana, kutsutaan "lukon käyttöikääksi". Tämä arvo on sekä aika, joka kuluu ennen kuin lukitus vapautetaan automaattisesti, että aika, joka asiakkaan on suoritettava toiminto ennen kuin toinen asiakas voi puolestaan ​​lukita kyseisen resurssin rikkomatta molemminpuolisia poissulkemistakuita. Tämä takuu on rajoitettu vain tiettyyn ajanjaksoon, joka alkaa lukon ostohetkestä.

Joten olemme keskustelleet hyvästä tavasta lukon hankkimiseen ja vapauttamiseen. Järjestelmä (jos puhumme hajauttamattomasta järjestelmästä, joka koostuu yhdestä ja aina käytettävissä olevasta ilmentymästä) on turvallinen. Laajennetaan tämä käsite hajautettuun järjestelmään, jossa meillä ei ole tällaisia ​​takuita.

Redlock-algoritmi

Algoritmin hajautettu versio olettaa, että meillä on N Redis-masteria. Nämä solmut ovat täysin riippumattomia toisistaan, joten emme käytä replikointia tai muita implisiittisiä koordinaatiojärjestelmiä. Olemme jo käsitelleet kuinka lukko hankitaan ja avataan turvallisesti yhdessä tapauksessa. Pidämme itsestäänselvyytenä, että algoritmi käyttää täsmälleen tätä menetelmää yksittäisen esiintymän kanssa työskennellessään. Esimerkeissämme asetamme N arvoon 5, mikä on kohtuullinen arvo. Siksi meidän on käytettävä viittä Redis-masteria eri tietokoneissa tai virtuaalikoneissa varmistaaksemme, että ne toimivat pitkälti toisistaan ​​riippumatta.

Lukon hankkimiseksi asiakas suorittaa seuraavat toiminnot:

  1. Hakee nykyisen ajan millisekunteina.
  2. Yrittää peräkkäin saada lukon kaikkiin N tapauksiin käyttämällä samaa avaimen nimeä ja satunnaisia ​​arvoja kaikissa tapauksissa. Vaiheessa 2, kun asiakas asettaa lukon tapauskohtaisesti, asiakas käyttää sen hankkimiseen viivettä, joka on tarpeeksi lyhyt verrattuna aikaan, jonka jälkeen lukko vapautetaan automaattisesti. Jos eston kesto on esimerkiksi 10 sekuntia, viive voi olla välillä ~5-50 millisekuntia. Tämä eliminoi tilanteen, jossa asiakas voi pysyä estettynä pitkään yrittäessään tavoittaa epäonnistuneen Redis-solmun: jos ilmentymä ei ole käytettävissä, yritämme muodostaa yhteyden toiseen ilmentymään mahdollisimman pian.
  3. Lukon ottamiseksi asiakas laskee, kuinka paljon aikaa on kulunut; Tätä varten se vähentää todellisesta aika-arvosta aikaleiman, joka saatiin vaiheessa 1. Jos ja vain jos asiakas onnistui saamaan lukon suurimmassa osassa tapauksia (vähintään 3), sekä kokonaisajan, joka kului saada lukko, vähemmän kuin lukon kesto, lukko katsotaan hankituksi.
  4. Jos lukko on hankittu, lukon kestoksi otetaan alkuperäinen lukon kesto miinus vaiheessa 3 laskettu kulunut aika.
  5. Jos asiakas ei jostain syystä saa lukkoa (joko se ei pystynyt lukitsemaan N/2+1 esiintymää tai lukituksen kesto oli negatiivinen), se yrittää avata kaikkien ilmentymien lukituksen (myös ne, joita se ei luullut pystyvänsä estämään ).

Onko algoritmi asynkroninen?

Tämä algoritmi perustuu oletukseen, että vaikka ei ole synkronoitua kelloa, jolla kaikki prosessit toimisivat, paikallinen aika kussakin prosessissa kulkee silti suunnilleen samalla tahdilla ja virhe on pieni verrattuna kokonaisaikaan, jonka jälkeen lukko on vapautetaan automaattisesti. Tämä oletus on hyvin samanlainen kuin tavallisille tietokoneille tyypillinen tilanne: jokaisessa tietokoneessa on paikallinen kello, ja yleensä voimme luottaa siihen, että aikaero eri tietokoneiden välillä on pieni.

Tässä vaiheessa meidän on muotoiltava tarkemmin keskinäinen poissulkemissääntömme: vastavuoroinen poissulkeminen on taattu vain, jos lukkoa pitelevä asiakas poistuu lukon voimassaoloaikana (tämä arvo saadaan vaiheessa 3), josta on vähennetty lisäaika (yhteensä muutama millisekuntia prosessien välisen aikaeron kompensoimiseksi).

Seuraava mielenkiintoinen artikkeli kertoo lisää sellaisista järjestelmistä, jotka vaativat aikavälien koordinointia: Vuokrasopimukset: tehokas vikasietoinen mekanismi hajautetun tiedostovälimuistin yhtenäisyyteen.

Yritä uudelleen epäonnistuessa

Kun asiakas ei saa lukkoa, sen on yritettävä uudelleen satunnaisen viiveen jälkeen; Tämä tehdään synkronoinnin poistamiseksi useista asiakkaista, jotka yrittävät hankkia lukon samaan resurssiin samanaikaisesti (mikä voi johtaa "aivojen jakautumiseen", jossa ei ole voittajia). Lisäksi mitä nopeammin asiakas yrittää saada lukituksen suurimmassa osassa Redis-esiintymiä, sitä kapeampi ikkuna voi tapahtua jaettujen aivojen tilanteessa (ja sitä pienempi on uudelleenyritysten tarve). Siksi ihannetapauksessa asiakkaan tulisi yrittää lähettää SET-komentoja N instanssiin samanaikaisesti käyttämällä multipleksointia.

Tässä on syytä korostaa, kuinka tärkeää on, että asiakkaat, jotka eivät onnistu hankkimaan suurinta osaa lukoista, vapauttavat (osittain) hankitut lukot, jotta heidän ei tarvitse odottaa avaimen vanhenemista ennen kuin resurssin lukko voidaan hankkia uudelleen (tosin jos verkon pirstoutuminen tapahtuu ja asiakas menettää yhteyden Redis-esiintymiin, sinun on maksettava saatavuussakko odottaessasi avaimen vanhenemista).

Vapauta lukko

Lukon vapauttaminen on yksinkertainen toimenpide, joka vaatii yksinkertaisesti kaikkien esiintymien lukituksen avaamisen riippumatta siitä, onko asiakas näyttänyt lukinneen tietyn ilmentymän onnistuneesti.

Turvallisuusnäkökohdat

Onko algoritmi turvallinen? Yritetään kuvitella, mitä tapahtuu eri skenaarioissa.

Aluksi oletetaan, että asiakas onnistui saamaan lukon suurimmassa osassa tapauksia. Jokainen esiintymä sisältää avaimen, jolla on sama käyttöikä kaikille. Jokainen näistä avaimista on kuitenkin asennettu eri aikaan, joten ne vanhenevat eri aikoina. Mutta jos ensimmäinen avain asennettiin ajankohtana, joka ei ole huonompi kuin T1 (aika, jonka valitsemme ennen yhteydenottoa ensimmäiseen palvelimeen), ja viimeinen avain asennettiin ajankohtana, joka ei ole huonompi kuin T2 (aika, jolloin vastaus vastaanotettiin viimeiseltä palvelimelta), olemme varmoja, että joukon ensimmäinen avain, joka vanhenee, säilyy ainakin hengissä MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Kaikki muut avaimet vanhenevat myöhemmin, joten voimme olla varmoja, että kaikki avaimet ovat yhtä aikaa voimassa ainakin tämän ajan.

Sinä aikana, jolloin useimmat avaimet ovat voimassa, toinen asiakas ei pysty hankkimaan lukkoa, koska N/2+1 SET NX -toiminnot eivät voi onnistua, jos N/2+1 avaimia on jo olemassa. Siksi kun lukko on hankittu, sitä ei voi hankkia uudelleen samalla hetkellä (tämä loukkaisi keskinäistä poissulkemisominaisuutta).
Haluamme kuitenkin varmistaa, että useat asiakkaat, jotka yrittävät hankkia lukon samanaikaisesti, eivät voi onnistua samaan aikaan.

Jos asiakas on lukinnut suurimman osan ilmentymistä suurin piirtein tai pidemmäksi ajaksi kuin enimmäislukon kesto, se katsoo lukon kelpaamattomaksi ja avaa ilmentymien lukituksen. Siksi meidän on otettava huomioon vain tapaus, jossa asiakas onnistui estämään suurimman osan tapauksista vanhentumispäivää lyhyemmässä ajassa. Tässä tapauksessa edellä mainitun väitteen osalta ajan kuluessa MIN_VALIDITY yhdenkään asiakkaan ei pitäisi pystyä hankkimaan lukkoa uudelleen. Siksi monet asiakkaat voivat lukita N/2+1 esiintymää samaan aikaan (joka päättyy vaiheen 2 lopussa) vain, kun aika useimpien lukitsemiseen oli suurempi kuin TTL-aika, mikä tekee lukituksesta mitättömän.

Voitko tarjota muodollisen todisteen turvallisuudesta, osoittaa olemassa olevat samankaltaiset algoritmit tai löytää virheen yllä olevista?

Esteettömyysnäkökohdat

Järjestelmän saatavuus riippuu kolmesta pääpiirteestä:

  1. Vapauta lukot automaattisesti (kun avaimet vanhenevat): Avaimet ovat lopulta jälleen käytettävissä lukoissa.
  2. Se, että asiakkaat yleensä auttavat toisiaan poistamalla lukkoja, kun haluttua lukkoa ei ole hankittu tai se on hankittu ja työ on suoritettu; joten on todennäköistä, että meidän ei tarvitse odottaa avainten vanhenemista saadaksemme lukon takaisin.
  3. Se, että kun asiakkaan on yritettävä hankkia lukko uudelleen, se odottaa suhteellisen pidempään kuin useimpien lukkojen hankkimiseen tarvittava aika. Tämä vähentää todennäköisyyttä, että aivot jakautuvat kilpailemalla resursseista.

Verkkosegmenttien TTL:n suuruinen käytettävyyssakko on kuitenkin olemassa, joten jos peräkkäisiä segmenttejä on, sakko voi olla rajoittamaton. Tämä tapahtuu aina, kun asiakas saa lukon ja repii sen sitten toiseen segmenttiin ennen kuin se voi vapauttaa sen.

Periaatteessa, kun otetaan huomioon äärettömät vierekkäiset verkkosegmentit, järjestelmä voi olla poissa käytöstä äärettömän ajan.

Suorituskyky, vikasieto ja fsync

Monet ihmiset käyttävät Redisiä, koska he tarvitsevat korkean lukituspalvelimen suorituskyvyn, kun otetaan huomioon lukkojen hankkimiseen ja vapauttamiseen vaadittava viive sekä sekunnissa suoritettavien hankintojen/julkaisujen määrä. Tämän vaatimuksen täyttämiseksi on olemassa strategia kommunikoida N Redis -palvelimen kanssa latenssin vähentämiseksi. Tämä on multipleksointistrategia (tai "köyhän miehen multipleksointi", jossa pistoke asetetaan estotilaan, lähettää kaikki komennot ja lukee komennot myöhemmin olettaen, että kiertoaika asiakkaan ja kunkin esiintymän välillä on samanlainen) .

Meidän on kuitenkin otettava huomioon myös pitkän aikavälin tietojen säilytykseen liittyvä harkinta, jos pyrimme luomaan mallin, joka toipuu luotettavasti häiriöistä.

Periaatteessa ongelman selventämiseksi oletetaan, että määritämme Rediksen ilman pitkäkestoista tietojen tallennusta. Asiakas onnistuu estämään 3 tapausta viidestä. Yksi ilmentymistä, jonka asiakas onnistui estämään, käynnistetään uudelleen, ja tällä hetkellä samalla resurssilla on taas 5 esiintymää, jotka voimme estää, ja toinen asiakas voi puolestaan ​​estää uudelleenkäynnistetyn ilmentymän rikkoen suojausominaisuutta. olettaa lukkojen yksinoikeudella.

Jos otat data ahead (AOF) käyttöön, tilanne paranee hieman. Voit esimerkiksi mainostaa palvelinta lähettämällä SHUTDOWN-komennon ja käynnistämällä sen uudelleen. Koska Rediksen vanhenemistoiminnot on semanttisesti toteutettu siten, että aika kuluu edelleen, vaikka palvelin on sammutettu, kaikki vaatimuksemme ovat kunnossa. Tämä on normaalia niin kauan kuin normaali sammutus on taattu. Mitä tehdä sähkökatkon sattuessa? Jos Redis on oletusarvoisesti määritetty fsync-synkronoimalla levyllä joka sekunti, on mahdollista, että uudelleenkäynnistyksen jälkeen meillä ei ole avaintamme. Teoriassa, jos haluamme taata lukituksen turvallisuuden minkä tahansa ilmentymän uudelleenkäynnistyksen aikana, meidän pitäisi ottaa käyttöön fsync=always asetuksissa pitkäaikaista tietojen tallennusta varten. Tämä tappaa täysin suorituskyvyn CP-järjestelmien tasolle asti, joita perinteisesti käytetään hajautettujen lukkojen turvalliseen toteuttamiseen.

Mutta tilanne on parempi kuin miltä ensi silmäyksellä näyttää. Periaatteessa algoritmin turvallisuus säilyy, koska kun ilmentymä käynnistetään uudelleen vian jälkeen, se ei enää osallistu mihinkään sillä hetkellä aktiivisena olevaan lukkoon.

Tämän varmistamiseksi meidän on vain varmistettava, että ilmentymä ei ole käytettävissä vian jälkeen jonkin aikaa, joka ylittää käyttämämme enimmäismäärän. Tällä tavalla odotamme kaikkien vikahetkellä aktiivisten avainten vanhenemispäivää ja automaattista vapauttamista.

Viivästettyjen uudelleenkäynnistysten avulla on periaatteessa mahdollista saavuttaa tietoturva myös ilman pitkäaikaista pysyvyyttä Redisissä. Huomaa kuitenkin, että tämä voi johtaa sakkoon esteettömyyden rikkomisesta. Jos esimerkiksi suurin osa esiintymistä epäonnistuu, järjestelmä ei ole maailmanlaajuisesti käytettävissä TTL:lle (eikä resursseja voida estää tänä aikana).

Lisäämme algoritmin saatavuutta: laajennamme estoa

Jos asiakkaiden tekemä työ koostuu pienistä vaiheista, on mahdollista lyhentää lukon oletusaikaa ja ottaa käyttöön mekanismi lukkojen pidentämiseksi. Periaatteessa, jos asiakas on kiireinen laskemalla ja lukon vanhenemisarvo on vaarallisen alhainen, voit lähettää kaikkiin esiintymiin Lua-skriptin, joka laajentaa avaimen TTL:ää, jos avain on edelleen olemassa ja sen arvo on edelleen satunnainen arvo, joka saadaan, kun lukko hankittu.

Asiakkaan tulee harkita lukon uudelleenhankimista vain, jos se on onnistunut lukitsemaan suurimman osan tapauksista voimassaoloaikana.

Totta, teknisesti algoritmi ei muutu, joten toistuvien lukkoyritysten enimmäismäärää on rajoitettava, muuten saavutettavuusominaisuuksia rikotaan.

Lähde: will.com

Lisää kommentti