Tämä kurssi on jo päättynyt.

Koordinoidusti hajautetut järjestelmät (syventävä)

Kuten johdannossa jo ohimennen mainittiin, koordinoituja hajautettuja järjestelmiä on kahta päätyyppiä sen mukaan, mitä koordinoidaan:

  1. Resurssien koordinointi: Palvelu replikoidaan hajautetulla resurssialustalla (tai infrastruktuurilla), jotta eri paikoissa sijaitseville käyttäjille voidaan tarjota melko lähellä (fyysisestikin tai ainakin eri sijaintiensa avulla saatavilla pysyvää) olevaa palvelua samalla säilyttäen sen vaaditunlainen yhdenmukaisuus (ristiriidattomuus). Pilvi ja monet hajautetut asiakas-palvelin -järjestelmät kuuluvat tähän luokkaan.
  2. Palvelujen koordinointi: Hajallaan olevat toimijat vuorovaikuttavat yhteisen hajautetun palvelun tuottamiseksi tiettyjen ristiriidattomuusvaatimusten mukaisesti. Esimerkiksi tapahtumatietokannat ja hajautetut tilikirjat ovat tällaisia ja edellyttävät vahvaa ristiriidattomuutta. Verkkoindeksointirobotit (web crawlers), haut tai logistiikkasovellukset voivat hyvinkin toimia heikomman ristiriidattomuuden puitteissa.

Nämä tyypit eriytyvät vasta seuraavassa alaluvussa. Tässä käsitellään yleisiä ominaisuuksia, jotka soveltuvat molempiin: peruskäsitteet sekä replikointi ja koordinointi.

Hajautuksen peruskäsitteet (syventävä)

Synkronointi

Hajautettujen resurssien ja palvelujen vuorovaikutus toteutetaan synkronoinnilla, jota on yleistäen seuraavia tyyppejä:

  1. Synkroninen: Kaikki hajautetun järjestelmän komponentit synkronoidaan eli pidetään ajan tasalla toistensa tilasta — askel kerrallaan tai kierroksina. Syy-yhteys saavutetaan eksplisiittisesti. Esimerkkejä ovat turvallisuuden kannalta kriittiset järjestelmät, kuten ilma-aluksen fly-by-wire -ohjaus, joissa ennustettavuus ja taattu reaaliaikainen reagointikyky ovat tarpeen.
  2. Asynkroninen: Erilliset oliot askeltavat mielivaltaisessa järjestyksessä ja toimivat eri nopeuksilla. Tapahtumien järjestys varmistetaan kollektiivisen vuorovaikutuksen kautta. Tyypillisiä esimerkkejä ovat tapahtumajärjestelmät, tietokannat, verkon indeksointirobotit jne.
  3. Osittain synkroninen: Toimintojen järjestykseen sovelletaan joitain rajoituksia, mutta askelittaista synkronointia ei ole. Tyypillisiä esimerkkejä ovat SCADA-ohjausjärjestelmät tai arvokkaat transaktiot varastojärjestelmissä, joissa oikea-aikaisuus vaikuttaa palvelun oikeellisuuteen.
Luotettava ryhmäviestintä
Ryhmäviestintää tarvitaan varmistamaan viestien luotettava toimitus hajautettujen olioiden välillä. Nämä voivat olla yksinkertaisia kahden pisteen välisiä suoria sanomia, joihin liittyy asianmukaiset kuittaukset. Vaihtoehtoisesti voidaan käyttää luotettavaa ja turvallista monilähetystä variaatioineen redundanttien kanavien tarjoamiseen, tai viestien järjestystä voidaan säätää julkaisu-tilaus -käytäntöjen yhteydessä. Kanavat ja viestit voidaan salata tai allekirjoittaa, joskin tämä aiheuttaa kustannuksia. Ryhmäviestintään kuuluvat myös valtuustietojen hallinta ja kryptografiset protokollat, joihin puolestaan kuuluvat PKI ja avainten jakelu.
Yksimielisyys

Yksimielisyys tarkoittaa samaa käsitystä arvoista, jotka voivat olla esimerkiksi datan tai prosessin tunnuksia. Yksimielisyys edellyttää seuraavien ominaisuuksien säilyttämistä:

  1. Sopiminen: Kaikki hyvät prosessit ovat yhtä mieltä samasta arvosta.
  2. Päteminen: Sovittu arvo on pätevä eli (mahdollisimman) oikea.
  3. Päättyminen: Päätös arvosta tehdään lopulta, eli neuvottelu ei jatku loputtomiin.

Konsensuksen erityinen tyyppi riippuu käsiteltävien vikojen semantiikasta (törmäys, laiminlyönti, bysanttilainen jne.). Vikatyyppejä käsitellään tuonnempana.

Ristiriidattomuus

Ristiriidattomuudella on erilaisia vivahteita. Taustalla on kuitenkin aina oletus determinismistä eli saman proseduurin suoritus johtaa aina samaan tilaan.

Vahva ristiriidattomuus: Osallistujien tulee sopia yhdestä johdonmukaisesta toimenpiteiden järjestyksestä. Perusmalli on tiukka ristiriidattomuus. Linearisoitavuus lisää siihen vaatimuksen, että havaittu toimintojen järjestys vastaa niiden todellista järjestystä. Vahvoja malleja käytetään korkean riskin sovelluksissa, kun ristiriidattomuutta arvostetaan enemmän kuin saatavuutta. Vahvojen rajoitusten pakottaminen tuottaa järjestelmiin viiveitä toistuvan synkronoinnin vuoksi. Perinteiset relaatiotietokannat, kuten MySQL tai Microsoftin SQL Server, mutta myös modernit NoSQL-tietokannat, kuten MongoDB tai Googlen Chubby-lukkopalvelu, ovat esimerkkejä näiden toteuttamisesta.

Heikko ristiriidattomuus: Osallistujat eivät välttämättä havaitse samaa tapahtumien järjestystä. Tämä voi johtaa eri tiloihin, ja vaatimuksista riippuen voidaan tai pitää käyttää konfliktinratkaisun mekanismeja.

  1. Peräkkäisyyden ristiriidattomuus: Kunkin prosessin itse suorittamien toimien järjestys säilyy, vaikka kahden eri prosessin tapahtumat eivät lomittuisikaan oikein.
  2. Kausaalinen ristiriidattomuus: edellistä vaatimusta höllennetään koskemaan vain sellaisia tapahtumia, jotka ovat toisiinsa syy-seuraus -yhteydessä. Näin on tarkalleen silloin kun kumpikin käyttää samaa dataa ja ainakin toinen kirjoittaa.
  3. Lopullinen ristiriidattomuus: Osallistujat päätyvät lopulta ristiriidattomaan tilaan. Jos sitä ei ole havaittavissa silloin kun tarvitaan, ratkaistaan konflikti sitä varten varatuilla mekanismeilla.

Järjestelmät, joissa ristiriidattomuus ei ole vahvaa, yleistyivät internetin myötä, kun laajojen web-palvelintoteutusten piti palvella suurta määrää käyttäjiä. Hyvä saatavuus oli mahdollista luopumalla vahvasta ristiriidattomuudesta. Esimerkkeinä ovat Amazonin Dynamo ja Facebookin Cassandra.

Replikointi ja koordinointi hyökkäysmahdollisuuden heikentäjänä (syventävä)

Perushaaste luotettavien hajautettujen järjestelmien kehittämisessä on tukea yhteisen tehtävän suorittamiseen tarvittavien hajautettujen olioiden yhteistyötä, vaikka osa näistä olioista tai niiden välinen viestintä epäonnistuisi. On varmistettava palvelutoimintojen järjestys ja vältettävä hajautettujen resurssien pilkkoutumista osioihin, jotta saadaan kokonaisvaltainen “koordinoitu” resurssijoukko.

Yleinen menetelmä vikasietoisen palvelun toteuttamiseksi on replikoida palvelimia ja koordinoida asiakkaiden vuorovaikutuksia palvelinkopioiden kanssa. Mikään hajautettu tietojärjestelmä (esim. www) ei kuitenkaan voi tarjota kuin kaksi kolmesta mahdollisesta ominaisuudesta C, A ja P:

  1. Ristiriidattomuus (Consistency) tarkoittaa yhtä ajantasaista kopiota tiedoista, eli jokainen palvelin palauttaa oikean vastauksen jokaiseen pyyntöön.
  2. Saatavuus (Availability): jokainen tietopyyntö saa lopulta vastauksen.
  3. Osioitumattomuus (Partition): Verkon kestävyys sitä vastaan, että palvelimet jakautuisivat keskenään kommunikoimattomiin ryhmiin.

Luonnollisesti tietoturvahyökkäykset yrittävät vaikuttaa näihin ominaisuuksiin.

Replikoiden eli kopioiden hallinta on keskeinen koordinointimekanismi, joka luonnehtii minkä tahansa hajautetun järjestelmän toimivuutta. Mekanismin valinta määräytyy järjestelmän synkronointimallista, ryhmäviestinnän tyypistä ja erityisesti tarkasteltavien häiriöiden (vikojen tai hyökkäysten) luonteesta. Mekanismit voivat olla yksinkertaisia äänestyksiä tai johtajan valintaprosesseja tai monimutkaisempia konsensuslähestymistapoja törmäysten tai bysanttilaisen vikaantumisen käsittelemiseksi. Tietokantatapahtumien sitoutumisprotokollat ovat tärkeitä, samoin kuin tunnistetietojen hallinta- ja PKI-infrastruktuurit, jotka tarjoavat varmennettua pääsynvalvontaa. Tässä mainitaan lyhyesti muutama laajalti käytetty tekniikka. Valtuutusta ja todennusta hajautetuissa järjestelmissä käsitellään myöhemmässä pääluvussa.

Paxos
Paxos on joukko monimutkaisia ja erittäin monimutkaisia protokollia asynkronisen konsensuksen saavuttamiseksi. Alussa kaikki voivat ehdottaa arvoa sovittavana olevalle tiedolle. Jos enemmistö vastauksissaan hyväksyy arvon, voidaan siirtyä seuraavaan tietoon. Protokolla voi joutua tilanteeseen, jossa prosessit jatkavat arvojen ehdottamista loputtomiin ja jumiutuvat alkuvaiheeseen, koska enemmistöä ei voida muodostaa. Käytännössä tämä on harvinaista ja Paxos on edelleen yksi laajimmin käytetyistä koordinointiprotokollista. Yksi esimerkki on Googlen Chubby-tiedostojärjestelmä. Paxosin tilalle on ehdotettu yksinkertaisempaa RAFT-protokollaa, joka tarjoaa samat takuut.
Bysanttilainen vikasietoisuus (BFT)

Bysanttilainen vikaantuminen (Byzantine failure tai fault) on mahdollinen, jos joukko erillään olevia toimijoita rakentaa viestinnän avulla kokonaisnäkemyksensä järjestelmän tilasta. Hyökkääjä voi lähettää moduloitua tietoa (esim. oikeiden ja väärien arvojen yhdistelmiä) eri toimijoille, jolloin vastaanotettujen arvojen perusteella ne eivät pysty muodostamaan oikeaa näkymää. Bysanttilainen hyökkäys voi käyttää väärin pääsynvalvonnan, viestinvälityksen tai koordinoinnin palveluita tai itse dataa.

Bysanttilaisen vikaantumisen sietävät protokollat (Byzantine fault tolerant, BFT) käyttävät koordinoitua replikointia, joka takaa oikean toiminnan niin kauan kuin enintään kolmasosa prosesseista käyttäytyy väärin.

BFT:ssä prosessit vaihtavat toisiltaan saamiaan arvoja kierroksittain. Konsensuksen saavuttamiseksi tarvittavien kierrosten määrä määräytyy järjestelmässä olevien huonojen osallistujien lukumäärän mukaan. Kierroksittaisuus tarkoittaa, että protokolla on synkroninen. On osoitettu, että on mahdotonta päästä yksimielisyyteen asynkronisen viestinnän tapauksessa (eli Paxos ei voisikaan olla täydellinen). Synkronisen tiedonsiirron välttämättömyyden ja BFT-käsittelyyn vaadittavan sanomanvaihdon melko korkean yleiskuorman vuoksi BFT-protokollia käytetään enimmäkseen tietyissä kriittisissä sovelluksissa.

Turvallisuuden näkökulmasta BFT-protokolla on houkutteleva rakennuspalikka tunkeutumista sietävien järjestelmien rakentamiselle, koska se sietää mielivaltaista haitallista käyttäytymistä. Identtiset kopiot eivät kuitenkaan riitä, koska niissä on samat haavoittuvuudet. Vastustaja, joka voi rämettää yhden kopion, voi helposti tehdä saman muille, jos ne ovat identtisiä. Replikoinnin lisäksi tarvitaan monimuotoisuus tai erilaiset suojausmenetelmät.

Sitoutumisen protokollat
Useat sovellukset, kuten tietokannat, tarvitsevat jakamattomuus- eli atomicity-ominaisuuden, mikä tarkoittaa sitä, että kaikki osallistujat joko sitoutuvat (commit) tiettyyn operaatioon tai eivät tee mitään. Jälkimmäisessä tapauksessa mahdolliset alustukset peruutetaan (rollback). Tässä voidaan käyttää kaksivaiheista sitoutumista tai vahvempaa kolmivaiheista sitoutumista, joka on BFT-protokollan laajennus. Vaikka kolmivaiheisuus on vankempi kuin BFT, sitä ei ole yleisesti käytössä yhtäältä viestinvälityksen kustannusten vuoksi ja toisaalta siksi, että se on herkkä osioimaan verkkoa (vrt. edellä CAP-ominaisuuksien P). Käytännössä järjestelmät käyttävät joko BFT:tä sen yksinkertaisuuden vuoksi tai Paxos-protokollaa sen kestävyyden vuoksi. Tavanomaisen tietokannan päivitys voi soveltaa kaksivaiheisuutta.
Palautusta lähetetään...