Kuvitettu todiste CAP-lauseesta

CAP-lause on hajautettujen järjestelmien peruslause, jonka mukaan millä tahansa hajautetulla järjestelmällä voi olla enintään kaksi seuraavista kolmesta ominaisuudesta.

• johdonmukaisuus
• saatavuus
• Partition toleranssi

tässä oppaassa tiivistetään Gilbertin ja Lynchin määrittely ja todiste CAP-lauseesta kuvin!

mikä on CAP-lause?

CAP-teoreeman mukaan hajautettu järjestelmä ei voi olla samanaikaisesti johdonmukainen, käytettävissä ja jakautumisen sietävä. Kuulostaa yksinkertaiselta, mutta mitä johdonmukaisuus tarkoittaa? vapaana? suvaitsevainen? Mitä oikein tarkoitat hajautetulla järjestelmällä?

tässä osiossa esittelemme yksinkertaisen hajautetun järjestelmän ja selitämme, mitä tarkoittaa, että kyseinen järjestelmä on käytettävissä, johdonmukainen ja osiosietoinen. Jos haluat muodollisen kuvauksen järjestelmästä ja kolmesta ominaisuudesta, tutustu Gilbertin ja Lynchin paperiin.

hajautettu järjestelmä

tarkastellaan hyvin yksinkertaista hajautettua järjestelmää. Järjestelmämme koostuu kahdesta palvelimesta, $G_1$ ja $G_2$. Molemmat palvelimet pitävät kirjaa samasta muuttujasta, $v$, jonka arvo on aluksi $v_0$. $G_1$ ja $G_2$ voivat kommunikoida keskenään ja voivat myös kommunikoida ulkoisten asiakkaiden kanssa. Tältä järjestelmämme näyttää.

asiakas voi pyytää kirjoittamaan ja lukemaan miltä tahansa palvelimelta. Kun palvelin vastaanottaa pyynnön, se suorittaa mitä tahansa laskelmia se haluaa ja sitten vastaa asiakkaalle. Esimerkiksi tältä kirjoitus näyttää.

ja Tältä näyttää lukema.

nyt kun olemme saaneet järjestelmämme perustetuksi, käydään läpi, mitä tarkoittaa, että järjestelmä on johdonmukainen, käytettävissä ja osioiden sietokykyinen.

johdonmukaisuus

näin Gilbert ja Lynch kuvaavat johdonmukaisuutta.

jokaisen kirjoitusoperaation päätyttyä alkavan lukuoperaation on palautettava kyseinen arvo tai myöhemmän kirjoitusoperaation

tulos johdonmukaisessa järjestelmässä, kun asiakas kirjoittaa arvon mille tahansa palvelimelle ja saa vastauksen, se odottaa saavansa kyseisen arvon (tai tuoreemman arvon) takaisin miltä tahansa palvelimelta, jolta se lukee.

tässä on esimerkki epäjohdonmukaisesta järjestelmästä.

asiakkaamme kirjoittaa $v_1$ to $G_1$ ja $G_1$ kuittaa, mutta kun se lukee $g_2$, se saa tunkkaista tietoa: $v_0$.

toisaalta tässä on esimerkki johdonmukaisesta järjestelmästä.

tässä järjestelmässä $G_1$ kopioi arvonsa $ G_2$ : ksi ennen kuin lähettää asiakkaalle kuittauksen. Näin ollen, kun asiakas lukee $G_2$, se saa kaikkein ajan tasalla arvo $v$: $v_1$.

saatavuus

näin Gilbert ja Lynch kuvailevat saatavuutta.

jokaisen järjestelmän ei-epäonnistuneen solmun vastaanottaman pyynnön on johdettava vastaukseen

käytettävissä olevassa järjestelmässä, jos asiakkaamme lähettää pyynnön palvelimelle eikä palvelin ole kaatunut, palvelimen on lopulta vastattava asiakkaalle. Palvelin ei saa ohittaa asiakkaan pyyntöjä.

Osiotoleranssi

näin Gilbert ja Lynch kuvailevat osioita.

verkko saa menettää mielivaltaisesti monta solmusta toiseen lähetettyä viestiä

tämä tarkoittaa, että kaikki viestit $g_1$ ja $G_2$ lähetetään toisilleen voidaan pudottaa. Jos kaikki viestit pudotettaisiin, järjestelmämme näyttäisi tältä.

järjestelmämme on kyettävä toimimaan oikein mielivaltaisista verkkoosioista huolimatta, jotta se on osioiden sietokykyinen.

todistus

nyt kun olemme perehtyneet johdonmukaisuuden, käytettävyyden ja osiotoleranssin käsitteeseen, voimme todistaa, että systeemillä ei voi olla samanaikaisesti kaikkia kolmea.

oletetaan ristiriidalle, että on olemassa systeemi, joka on johdonmukainen, käytettävissä ja osiota sietävä. Ensimmäinen asia teemme on osio meidän järjestelmä. Se näyttää tältä.

seuraavaksi asiakkaamme pyytää, että $v_1$ kirjoitetaan $ G_1$. Koska järjestelmämme on käytettävissä, $G_1$ on vastattava. Koska verkko on kuitenkin jaettu osiin, $G_1$ ei voi monistaa sen tietoja $G_2$. Gilbert ja Lynch kutsuvat tätä teloitusvaihetta $\alpha_1$.

seuraavaksi asiakkaamme antaa lukupyynnön $G_2$. Jälleen, koska järjestelmämme on käytettävissä, $G_2$ on vastattava. Ja koska verkko on jaettu osiin, $G_2$ ei voi päivittää arvoaan $g_1$. Se palauttaa $v_0$. Gilbert ja Lynch kutsuvat tätä teloitusvaihetta $\alpha_2$.

$G_2$ palauttaa$ v_0 $ asiakkaallemme sen jälkeen, kun asiakas oli jo kirjoittanut $v_1$ to $G_1$. Tämä on epäjohdonmukaista.

oletimme, että on olemassa johdonmukainen, käytettävissä oleva, osiota sietävä järjestelmä, mutta osoitimme vain, että mille tahansa sellaiselle järjestelmälle on olemassa toteutus, jossa järjestelmä toimii epäjohdonmukaisesti. Näin ollen tällaista järjestelmää ei ole olemassa.