Raft er en algoritme til at løse konsensusproblemer i et netværk af upålidelig databehandling [1] . Den blev udviklet under hensyntagen til manglerne ved den ældre Paxos-algoritme . Ved valg af nøgleideer blev der givet fortrinsret til enklere og mere praktiske løsninger. På trods af sin relative enkelhed giver Raft en sikker og effektiv implementering af tilstandsmaskiner oven på et klyngecomputersystem .
Der er mange open source-implementeringer af Raft i forskellige programmeringssprog [2] . På trods af den fælles modstand mellem Raft og Paxos, er Raft faktisk en protokol fra Paxos-familien og deler mange implementeringsdetaljer med MultiPaxos, ZAB ( Zookeeper Atomic Broadcast ) og andre.
En klar adskillelse af faser: Raft tilbyder en dekomponering af klyngestyringsopgaven i flere løst koblede underopgaver, hvoraf de vigtigste er: ledervalg (afstemning) og protokolreplikering. Hver af disse opgaver giver mulighed for en mere detaljeret opdeling. Dette forenkler forståelsen af algoritmen og mindsker risikoen for fejl i dens implementering.
Eksplicit leder: Raft antager, at der altid er en eksplicit leder på klyngen. Kun denne leder sender nye poster til andre klynge noder. De resterende noder følger således lederen og interagerer ikke med hinanden (bortset fra afstemningsfasen). Hvis en ekstern klient opretter forbindelse til klyngen gennem en normal node, omdirigeres alle dens anmodninger til lederen og kommer kun derfra til noderne.
Arbejdsprotokoller kan ikke indeholde huller: det vil sige, at indgange tilføjes strengt sekventielt. Dette pålægger nogle begrænsninger sammenlignet med Paxos, men giver dig mulighed for i høj grad at forenkle algoritmen. Derudover tillader de specifikke specifikationer af anvendte opgaver oftest ikke at arbejde korrekt med protokoller, der indeholder huller. At Paxos tillader sådanne huller at opstå, er ofte en ulempe ved Paxos, som er meget svær at håndtere.
Ændring af klyngestørrelse: Raft gør det nemt at omkonfigurere en klynge uden at stoppe arbejdet: tilføje eller fjerne noder.
Raft er bygget oven på en klynge, hvor hver knude kører en tilstandsmaskine. Raft giver pålidelig levering af signaler til alle noder i en given rækkefølge. Således er overgangen af alle tilstandsmaskiner langs de samme sekvenser af tilstande sikret. Således er hver node garanteret at komme i overensstemmelse med andre noder.
En vigtig omstændighed er, at Raft strengt nummererer alle poster i arbejdsprotokollen. Tilmeldinger skal være strengt fortløbende. Disse tal spiller en vigtig rolle i driften af algoritmen. Ifølge dem bestemmes graden af relevans af nodens tilstand. Når du vælger en leder, bliver den mest opdaterede node altid lederen. De samme tal bruges til at nummerere afstemningssessioner. En node kan kun stemme én gang pr. stemmeanmodning.
Hvis en normal node ikke modtager beskeder fra lederen i lang tid, går den ind i "kandidat"-tilstanden og sender en anmodning til andre noder om at stemme. Andre noder stemmer på den kandidat, som de modtog den første anmodning fra. Hvis kandidaten modtager en besked fra lederen, trækker han sit kandidatur tilbage og vender tilbage til normal tilstand. Hvis kandidaten får flertallet af stemmerne, bliver han leder. Hvis han ikke fik flertal (dette er tilfældet, når flere kandidater optrådte i klyngen på én gang, og stemmerne blev delt), så venter kandidaten på et tilfældigt tidspunkt og indleder en ny afstemningsprocedure.
Afstemningsproceduren gentages indtil en leder er valgt.
Lederen er fuldt ud ansvarlig for korrekt protokolreplikering. Den sender en anmodning til alle noder i klyngen om at tilføje en ny post og betragter først transaktionen som vellykket, efter at størstedelen af noderne har bekræftet, at dataene er blevet anvendt, og resultatet er blevet gemt på vedvarende medier.
Som det fremgår af beskrivelsen af algoritmen, er afstemningen baseret på tilfældige forventninger. For at algoritmen kan fungere effektivt, skal følgende relationer være opfyldt:
I anvendte problemer er disse betingelser oftest let opfyldt. Nodernes interaktionstid måles normalt i millisekunder. Afstemningstiden er sekunder. Tiden for normal drift mellem fejl er måneder.