Nov 24, 2016

Vektorikellot ja riidattomat tietotyypit hajautetuissa järjestelmissä

coding.jpgEdellisessä blogissani esittelin kaksi tapaa jolla tehdä elämästä hajautettujen järjestelmien kanssa helpompaa: juoruilu ja konsensusalgoritmit. Koska hajautetut järjestelmät ovat nykyisin normaali osa sovelluskehitystä, on niiden kanssa toimimiseen kehitetty useita tehokkaita tapoja. Tässä blogissa keskitynkin kahteen toisenlaiseen tapaan: vektorikelloihin ja riidattomiin tietotyyppeihin.

Vektorikellot

Hajautetuissa järjestelmissä prosessit juttelevat toisten prosessien kanssa verkon ylitse. Sama tieto on lähetetty useammalle palvelimelle ja jokainen prosessi palvelimella voi muuttaa tietoa. Lopputuloksena on, että jokaisella palvelimella on samasta asiasta erinäköinen tieto, ja yhteisymmärryksen löytäminen on vaikeaa.

Tietoa voitaisiin yrittäää pitää konsistenssina hajautettujen transaktioiden avulla (distributed transaction), mutta näiden ongelmana on, että ne eivät skaalaudu hyvin ja palvelun saatavuus kärsii - eli juuri ne edut hukataan, mitä hajautetuilta järjestelmiltä halutaan.

Asiaa helpottaisi, jos tiedettäisiin, missä järjestyksessä tietoa on vaihdettu missäkin palvelimella. Tätä ongelmaa Amazon esitti ratkaistavaksi käyttämällä vektorikelloja (vector clock).

Sama ongelma voidaan esittää esimerkin kautta: nelihenkinen perhe, johon kuuluu isä, äiti, poika ja tyttö, yrittävät sopia yhteisestä illallisesta. Isä ehdottaa pitsaa. Äiti keskustelee matkapuhelimella tytön kanssa ja he haluaisivat syödä kalaa. Myöhemmin äiti keskustelee vaihtoehdoista pojan kanssa ja päätyvät sittenkin hampurilaisiin. Kun isä varmistaa kaupassa ollessaan perheen yhteisessä keskusteluryhmässä, että onhan pitsa valittu ruoaksi, hän saa kahdenlaista tietoa: tyttö sanoo, että he ovat äitin kanssa sopinut kalasta, ja poika sanoo, että he ovat äitin kanssa sopineet hampurilaisista. Äiti ei jostain syystä ole keskustelussa mukana, joten he eivät tiedä, kumpi ruoista on sovittu: kala vai hampurilaiset.

Vektorikello tuo ratkaisun tähän, sillä sen avulla voidaan kertoa osittain, missä järjestyksessä muutokset ovat tapahtuneet. Vektorikello kertoo sen tiedon version, mikä kenelläkin aiheesta on, ja tämä lisätään jokaiseen lähetettyyn viestiin.

Sama keskustelu vektorikellojen kanssa menisi näin: isä ehdottaa ensimmäisen ruoan, ja lisää oman merkinnän vektorikelloon:

ruoka = pitsa
vektorikello = isä:1

Äiti ja tytär aloittavat keskustelun tämän tiedon pohjalta, jossa tytär ehdottaa kalaa, hän jättää kuitenkin isän merkinnän pohjaksi, jotta tiedetään, että muutos on tehty isän ehdotukseen:

ruoka = kala
vektorikello = isä:1, tytär:1

Äiti kuittaa, että kala sopii ja lisää oman merkinnnän vektorikelloon:

ruoka = kala
vektorikello = isä:1, tytär:1, äiti:1

Nyt poika liittyy mukaan keskusteluun ja ehdottaa äidille ruoaksi hampurilaisia. Hän ei kuitenkaan tiedä, että tytär ja äiti ovat keskustellet aiheesta, vaan hän tekee ehdotuksen isän ehdotuksen pohjalta, joten vektorikellossa on ainoastaan hänen ja isän merkinnät:

ruoka = hampurilaiset
vektorikello = isä:1, poika:1

Nyt äidillä on samasta tiedosta kaksi eri versiota, jotka ovat konfliktissa keskenään. Hänen täytyy tehdä päätös ja hän valitsee sittenkin hampurilaiset. Vektorikelloon hän lisää kaikkien eri henkilöiden merkinnät ja lisää omaan merkintäänsä yhden lisää:

ruoka = hampurilaiset
vektorikello = isä:1, tytär:1, poika:1, äiti:2

Nyt kun isä kysyy, mikä ruoka on sovittu, hän saa erilaiset viestit tyttäreltä ja pojalta:

ruoka = kala
vektorikello = isä:1, tytär:1, äiti:1

ja..

ruoka = hampurilaiset
vektorikello = isä:1, tytär:1, poika:1, äiti:2

Nyt saaduista viesteistä, voidaan nähdä ilman äitiäkin, että äiti ja poika ovat sopineet myöhemmin hampurilaiset ruoaksi, sillä äitin merkintä on suurempi pojalta saadussa viestissä, mitä sen on tyttäreltä saadussa viestissä.

Vektorikelloja onkin käytetty tyypillisesti hajautetuissa avain-arvo-tietokannoissa (key-value database). Näistä esimerkkejä ovat Amazonin DynamoDB, Bashon Riak KV ja Voldemort.

Riidattomat tietotyypit

Edellisessä esimerkissä äiti joutui valinnan eteen ja hän joutui ratkomaan ristiriitatilanteen, koska ehdotetut ruoat olivat erilaisia. Parasta olisi kuitenkin, jos saadut ehdotukset eivät olisi koskaan olleetkaan ristiriidassa toisten ehdotusten kanssa. Perinteisesti ongelma on ratkaistu käyttämällä vahvaa konsistenssia (strong consistency). Tämä on kuitenkin ristiriidassa saatavuuden kanssa etenkin verkkopartitioiden sattuessa. Ratkaisuksi tähän on siirrytty käyttämään aikanaan tapahtuvaa konsistenssia (eventual concistency). Mutta tämäkään ei ole ongelmatonta, sillä eventual consistency tuo mukanaa ristiriidat ja niistä toipumiset. Helpointa olisi, jos pystyisi käyttämään eventual consistencya ilman, että ristiriitoja syntyisi.

Tällaisia tietotyyppejä on olemassa ja niistä käytetään nimitystä CRDT(Conflict-free Replicated Data Type) suomeksi vaikkapa ristiriidattomat replikoidut tietotyypit. CRDT entiteettien tilaa pystyy muokkaamaan eri prosesseissa ja lopulta ne pystytään sulauttamaan yhdeksi entiteetiksi, ilman, että tietoa hukkuu. Äärimmäisen yksinkertaisena esimerkkinä olkoon laskuri, jota voi kasvattaa. Yksi prosessi voi kasvattaa sitä 3 kertaa ja toinen prosessi toisella palvelimella 2 kertaa. Kun nämä laskurit lopulta yhdistetään, saadaan selville, että laskuria on kasvatettu yhteensä 5 kertaa.

CRDT:tä on olemassa kahta eri tyyppiä.

  • Operaatioperustaiset kopioidut tietotyypit (commutative replicated data types, CmRTD), joissa itse operaatio jaetaan verkon ylitse toisille kopioille (esim. lisää laskuriin 10).
  • Tilapohjaiset kopioidut tietotyypit (convergent replicated data type, CvRTD), joissa tietotyypin paikallinen tila lähetetään toisille kopioille (esimerkiksi laskuri = 10). Yksi esimerkki tilapohjaistesta tietotyypistä on joukko, johon pystyy vain lisäämään jäseniä.

Erona näissä tavoissa on, että operaatioperustaiset tietotyypit tarvitsevat luotetun tiedonsiirtokanavan, mutta toisaalta tilapohjaisissa tietotyypin paikallisen entiteetin koko tila siirretään kaikillle kopioille, mikä voi olla suurten entiteettien kohdalla rasite.

Perinteisesti avainarvo-tietokannoissa arvo on ylikirjoitettu, kun se on haluttu päivittää, ja vektorikelloilla pidetty järjestystä yllä. Jos on tullut konflikeja, ne on tietokannan käyttäjän pitänyt ratkaista. Nyt esimerkiksi Riak KV -tietokanta antaa määrittää arvon tyypiksi CRDT-tietotyyppejä (flags, registers, counters, sets, maps), jolloin konflikteja ei pääse syntymään. Sovellustasolla Akka-kirjasto tarjoaa mahdollisuuden käyttää CmRDT-entiteettejä klusterissa. Jos haluaa käyttää CvRDT entiteettejäm on tähän mahdollisuus käyttämällä Eventuate-kirjastoa.

CRTD tietotyypit ovat vielä suhteellisen tuoreita, ja niillä ei pysty ratkaisemaan kaikkia ongelmia, mutta tutkimusta tehdään koko ajan lisää ja uusia tietotyyppejä kehitetään koko ajan.
Aivan tuoreessa artikkelissa(elokuu 2016) Martin Kleppmann ja Alastair R. Beresford ovat julkaisseet ristiriidattoman JSON tietotyypin, jolle löytynee helposti käyttökohteita niin palvelin-, käyttöliittymä- ja mobiilipuolelta.

 

Related articles