Sep 20, 2016

Hajautetut järjestelmät: juoruja ja ristiriitoja

Distributed_systems.jpgHajautetuista järjestelmistä on tullut uusi normaali tapa tehdä sovelluksia. Järjestelmiltä vaaditaan sekä elastisuutta että saatavuutta. Jotta nämä saavutetaan, täytyy järjestelmä levittää useammalle palvelimelle.

Vielä viime vuosiin asti hajautettujen järjestelmien kanssa on pidetty yllä illuusiota, jossa palvelut elävät sulassa sovussa ja jakavat kaikki saman todellisuuden ja jossa muutokset tilassa tapahtuvat yhtä aikaan kaikkialla. Peter Deutsch on kerännyt 8 hajautettujen järjestelmien harhakuvitelmaa, jotka ylläpitävät tätä illuusiota:

  • Verkko on luotettava
  • Latenssia ei ole
  • Kaistanleveys on ääretön
  • Verkko on turvallinen
  • Verkkotopologio ei muutu
  • On yksi ylläpitäjä
  • Siirtokustannuksia ei ole
  • Verkko on homogeeninen

Miksi emme siis vain ota nämä seikat huomioon ja tee järjestelmiä, joissa tällaisia ongelmia ei ole? Vastaus on yksinkertainen - koska se on vaikeaa.


"A distributed system is one in which the failure of
a computer you didn't know existed can render your
own computer unusable."
  -Leslie Lamport


Elämä hajautetuissa järjestelmissä ei ole helppoa - asioista ei päästä yhteisymmärykseen, syntyy konflikteja ja ei tiedetä onko joku verkkosolmu (node) suuttunut ja pitää mykkäkoulua vai onko se kokonaan poistunut keskuudesta. Esittelen tässä muutaman tavan, kuinka elämää hajautetuissa järjestelmissä voi helpottaa.

Juoruja

Koska hajautetuissa järjestelmissä kannattaa suosia asynkronista kommunikointia, on mallia kommunikaation otettu juoruavista mummoista. Juorut ovat nopeita leviämään pitkienkin matkojen päähän. Parasta ja pahinta juoruissa on se, että ne leviävät ilman, että kukaan ohjaa ja hallitsee sitä. Ja jos kuulee saman juorun useammasta lähteestä, niin juorun täytyy pitää paikkansa. Kuulostaa siis todella hyvältä tavalta välittää tietoa myös tietoverkossa, jossa kommunikointi on epävarmaa ja latenssit ovat pitkiä.

Juoruilua voidaan käyttää monessa eri tarkoituksessa. Yksi käytetyimmistä kohteista on tietokoneklusterien hallinnointi. Esimerkki juorusta on, kun klusterin johtaja (cluster leader) saa tiedon, että uusi jäsen on liittymässä klusteriin. Johtaja lähettää juorun liikkeelle, että uusi jäsen on liittymässä, lopulta kaikki klusterin jäsenet ovat saaneet tiedon uudesta jäsenestä.

Teknisellä tasolla juoruamiseen määritetään protokolla (gossip protocol), jonka puitteissa tietoa levitetään. Yksi ehkä eniten tunnetuista on SWIM-protokolla (Scalable Weakly-consistent Infection-style process group Membership protocol) tai sen muunnokset.

Juoruaminen aloitetaan määrittelemällä ensin juoru. Esim. klusterin hallinnassa juoru voi olla viesti, jossa kerrotaan, ketkä kuuluvat klusteriin.

Esimerkki Akka-kirjaston käyttämä viesti:

Gossip_graphic_1.jpg


Tässä viestissä itse juoruttava asia on klusterin jäsenet. Juoruviesti itsessään on ristiriidaton replikoitu tietotyyppi (Conflic-free Replicated Data Type, CRDT) ja juorun version tyyppi on vektorikello (vector clock), joista enemmän tietoa myöhemmin blogissa.

Yleisesti ottaen gossip-protokolla voidaan tehdä näin:

1) Jokainen juorukierros aloitetaan valitsemalla satunnainen kohde (klusterin jäsen/solmu). Satunnaisuutta voidaan optimoida valitsemalla kohde, jolla on joko vanhempi tai uudempi versio juorun tilasta (gossip state).

2) Juoruaja lähettää juoruviestin valitulle kohteelle pyyntö/vastaus keskustelumallilla (request/reply conversational fashion).

3) Vastaanottaja käyttää saadun juorun versiota päättelemään, onko hänellä uudempi, vanhempi vai konfliktoiva version juorun tilasta.

- Jos saatu juoru on ristiriidassa oman kanssa, eri versiot yhdistetään, muutoin
- Uudempi versio juorusta pidetään ja vanhempi unohdetaan

4) Vastaanottaja merkitsee itsenä juorun nähneeksi ja palauttaa päivitetyn juorun tilan alkuperäiselle juoruajalle

Juorukierroksia jatketaan niin kauan, että kaikki klusterin jäsenet ovat nähneet juorun, ja saaneet myös vahvistuksen, että muutkin ovat nähneet sen. Tätä sanotaan klusterikonvergenssiksi (cluster convergence).

Riitoja ja yhteisymmärrystä

Jotta hajautetussa järjestelmässä voidaan luottaa tietoon (C osa CAP-teoreemasta), pitää siitä aluksi päästä yhteisymmärrykseen eri jäsenten kanssa. Tätä varten on kehitetty algoritmeja, jotka pyrkivät pitämään yllä konsensusta klusterissa. Konsensus on perusongelma vikasietoisissa hajautetuissa järjestelmissä. Konsensuksen turvavaatimukset ovat:

  • vain arvo, jota on ehdotettu, voidaan valita
  • vain yksi arvo voidaan valita
  • prosessi ei koskaan luule arvoa valituksi, ellei sitä ole oikeasti valittu

Yleensä konsensusalgoritmit pääsevät yhteisymmärrykseen, jos yli puolet palvelimista on saatavilla.

Konsensusta yritetään tyypillisisesti hakea monistetuille tilakoneille (replicated state machine), jotka ovat yleisiä rakennuspalikoita, kun rakennetaan vikasietoisia järjestelmiä. Jokaisella palvelimella on tilakone ja loki. Tilakone on kohde, joka yritetään tehdä vikasietoiseksi, esimerkiksi silpputaulu (hash table).

Asiakkaalle silpputaulu näkyy vain yhtenä silpputauluna ja hän ei näe, että se on monistettu verkossa useammalle palvelimelle.

Ehkä kuuluisin näistä on Leslie Lamportin kehittämä Paxos-algoritmi, jossa mallia on otettu fiktiivisestä lainsäädäntöprotokollasta Paxosin saarella Kreikassa. Viihdyttävästä tekstistä huolimatta algoritmi on monimutkainen ja sen ymmärtäminen on hankalaa, vaikkakin algoritmi on formaalisti todistettu. Lamport julkaisi aiheesta toisenkin artikkelin, jossa algoritmia on yritetty selittää paremmin. Silti sitä on vaikea ymmärtää ja kritiikkinä onkin esitetty, että se ei sovellu hyvin käytännön ongelmien ratkaisuun. 

Paxos-algoritmin hankaluuksista on yritetty ottaa oppia ja varsin tuore julkaisu (2013) on esittänyt yksinkertaistetun algoritmin nimeltään Raft. Raft-algoritmille löytyykin jo monta toteutusta eri ohjelmointikielille. Esimerkiksi CoreOs:n etcd, joka on hajautettu avain-arvo-tietokanta, käyttää Raft-algoritmia konsensuksen hallintaan.

Raft-algoritmissa konsensus saavutetaan valitun johtajan avulla. Palvelin on Raft-klusterissa joko johtaja, ehdokas tai seuraaja. Johtajan vastuulla on lokin replikointi seuraajille. Johtaja lähettää säännöllisesti heartbeat-viestejä seuraajille kertoakseen olemassa olostaan. Jokaisella seuraajalla on aikakatkaisu (timeout), jota ennen heartbeat-viesti pitäisi saapua johtajalta. Aikakatkaisu nollataan aina, kun viesti tulee perille. Mikäli seuraaja ei saa viestiä ajoissa, siirtää hän tilansa ehdokkaaksi ja aloittaa johtajan äänestysprosessin lähettämällä äänestyspyynnön seuraajille. Mikäli ehdokas saa eniten kannatusta, tulee seuraajasta uusi johtaja.

Tilanvaihto tapahtuu Raft-protokollassa johtajan kautta, johtaja kirjoittaa muutoksen tapahtumalokiin ja aloittaa lokin replikoinnin seuraajille. Kun johtaja saa kuittauksen suurimmalta osalta seuraajista tehdään tilanvaihto pysyväksi.

Teoriasta käytäntöön

Kuten todettua, elämä hajautettujen järjestelmien kanssa ei ole helppoa. Toisaalta ilman niitä se on nykyään jopa mahdotonta. Tässä esitetyillä algoritmeilla voidaan elämää kuitenkin helpottaa, ja tuoda osa takaisin siitä illuusiosta, jossa muutokset ovat paikallisia, jolloin liiketoimintalogiikan toteuttaminen on helpompaa.

Vaikka et suoraan käyttäisikään näitä algoritmeja, niin on hyvä tietää, että mahdollisesti muut käyttämäsivät kirjastot tai liitännäiset voivat niitä käyttää (esim. ZooKeeper, etcd, Consul, Lagom sekä hajautetut tietovarastot, kuten Cassandra, Riak KV ja Voldemort). On hyvä tietää, kuinka käyttämäsi työkalut toimivat pinnan alla, jotta tiedät, mitkä ovat niiden hyödyt ja mitkä rajoitteet, ja osaat käyttää niitä oikein.

Related articles