Raft on algoritmi konsensusongelmien ratkaisemiseen epäluotettavan laskennan verkossa [1] . Se kehitettiin ottaen huomioon vanhemman Paxos-algoritmin puutteet . Avainideoita valittaessa etusijalle annettiin yksinkertaisempia ja käytännöllisempiä ratkaisuja. Suhteellisesta yksinkertaisuudestaan huolimatta Raft tarjoaa kuitenkin turvallisen ja tehokkaan tilakonetoteutuksen klusterilaskentajärjestelmän päälle .
Raftista on monia avoimen lähdekoodin toteutuksia eri ohjelmointikielillä [2] . Huolimatta yhteisestä vastustuksesta Raftin ja Paxosin välillä, itse asiassa Raft on Paxos-perheen protokolla ja jakaa monia toteutustietoja MultiPaxosin, ZAB:n ( Zookeeper Atomic Broadcast ) ja muiden kanssa.
Selkeä vaiheiden erottelu: Raft tarjoaa klusterin hallintatehtävän hajotuksen useisiin löyhästi kytkettyihin alitehtäviin, joista tärkeimmät ovat: johtajan valinta (äänestys) ja protokollan replikointi. Jokainen näistä tehtävistä mahdollistaa yksityiskohtaisemman jaon. Tämä yksinkertaistaa algoritmin ymmärtämistä ja vähentää virheiden riskiä sen toteutuksessa.
Eksplisiittinen johtaja: Raft olettaa, että klusterissa on aina eksplisiittinen johtaja. Vain tämä johtaja lähettää uusia tietueita muille klusterin solmuille. Siten loput solmut seuraavat johtajaa eivätkä ole vuorovaikutuksessa toistensa kanssa (paitsi äänestysvaiheessa). Jos ulkoinen asiakas muodostaa yhteyden klusteriin normaalin solmun kautta, niin kaikki sen pyynnöt ohjataan johtajalle ja vain sieltä tulevat solmuille.
Työprotokollat eivät saa sisältää aukkoja: toisin sanoen merkinnät lisätään tiukasti peräkkäin. Tämä asettaa joitain rajoituksia verrattuna Paxosiin, mutta antaa sinun yksinkertaistaa algoritmia huomattavasti. Lisäksi sovellettavien tehtävien erityispiirteet eivät useimmiten salli aukkoja sisältävien protokollien oikeaa käyttöä. Se, että Paxos sallii tällaisten aukkojen syntymisen, on usein Paxoksen haitta, jota on erittäin vaikea käsitellä.
Klusterin koon muuttaminen: Raftin avulla on helppo määrittää klusteri uudelleen keskeyttämättä työtä: lisää tai poista solmuja.
Lautta on rakennettu klusterin päälle, jokaisessa solmussa on tilakone. Raft tarjoaa luotettavan signaalin toimituksen kaikille solmuille tietyssä järjestyksessä. Näin varmistetaan kaikkien tilakoneiden siirtyminen samoja tilasarjoja pitkin. Siten jokainen solmu tulee taatusti sopimukseen muiden solmujen kanssa.
Tärkeä seikka on, että Raft numeroi tarkasti kaikki työpöytäkirjamerkinnät. Ilmoittautumisten tulee olla tiukasti peräkkäisiä. Näillä luvuilla on tärkeä rooli algoritmin toiminnassa. Niiden mukaan määritetään solmun tilan relevanssiaste. Johtajaa valittaessa ajantasaisimmasta solmusta tulee aina johtaja. Samoja numeroita käytetään äänestysistuntojen numeroimiseen. Solmu voi äänestää vain kerran äänestyspyyntöä kohden.
Jos normaali solmu ei saa viestejä johtajalta pitkään aikaan, se siirtyy "ehdokas"-tilaan ja lähettää muille solmuille pyynnön äänestää. Muut solmut äänestävät ehdokasta, jolta he saivat ensimmäisen pyynnön. Jos ehdokas saa viestin johtajalta, hän peruuttaa ehdokkuutensa ja palaa normaalitilaan. Jos ehdokas saa enemmistön äänistä, hänestä tulee johtaja. Jos hän ei saanut enemmistöä (tämä on tilanne, kun klusteriin ilmestyi useita ehdokkaita kerralla ja äänet jakautuivat), ehdokas odottaa satunnaisen ajan ja aloittaa uuden äänestysmenettelyn.
Äänestysmenettely toistetaan, kunnes johtaja on valittu.
Johtaja on täysin vastuussa asianmukaisesta protokollan replikaatiosta. Se lähettää kaikille klusterin solmuille pyynnön lisätä uusi tietue ja pitää tapahtumaa onnistuneena vasta, kun suurin osa solmuista on vahvistanut, että tiedot on käytetty ja tulos on tallennettu pysyvälle medialle.
Kuten algoritmin kuvauksesta näkyy, äänestäminen perustuu satunnaisiin odotuksiin. Jotta algoritmi toimisi tehokkaasti, seuraavat suhteet on täytettävä:
Sovellettavissa ongelmissa nämä ehdot täyttyvät useimmiten helposti. Solmujen vuorovaikutusaika mitataan yleensä millisekunteina. Äänestysaika on sekuntia. Normaalin toiminnan aika vikojen välillä on kuukausia.