Raft är en algoritm för att lösa konsensusproblem i ett nätverk av opålitlig beräkning [1] . Den utvecklades med hänsyn till bristerna i den äldre Paxos-algoritmen . Vid val av nyckelidéer gavs företräde åt enklare och mer praktiska lösningar. Men trots sin relativa enkelhet tillhandahåller Raft en säker och effektiv tillståndsmaskinimplementering ovanpå ett klusterberäkningssystem .
Det finns många implementeringar av Raft med öppen källkod i olika programmeringsspråk [2] . Trots det gemensamma motståndet mellan Raft och Paxos är Raft faktiskt ett protokoll från Paxos-familjen och delar många implementeringsdetaljer med MultiPaxos, ZAB ( Zookeeper Atomic Broadcast ) och andra.
En tydlig separation av faser: Raft erbjuder en nedbrytning av klusterhanteringsuppgiften i flera löst kopplade deluppgifter, varav de viktigaste är: val av ledare (omröstning) och protokollreplikering. Var och en av dessa uppgifter möjliggör en mer detaljerad uppdelning. Detta förenklar förståelsen av algoritmen och minskar risken för fel i implementeringen.
Explicit ledare: Raft antar att det alltid finns en explicit ledare på klustret. Endast denna ledare skickar nya poster till andra klusternoder. Således följer de återstående noderna ledaren och interagerar inte med varandra (förutom röstningsfasen). Om en extern klient ansluter till klustret genom en normal nod, omdirigeras alla dess förfrågningar till ledaren och kommer endast därifrån till noderna.
Arbetsprotokoll kan inte innehålla luckor: det vill säga poster läggs till strikt sekventiellt. Detta medför vissa begränsningar jämfört med Paxos, men låter dig förenkla algoritmen avsevärt. Dessutom tillåter detaljerna för tillämpade uppgifter, oftast, inte att arbeta korrekt med protokoll som innehåller luckor. Att Paxos låter sådana luckor uppstå är ofta en nackdel med Paxos, som är mycket svår att hantera.
Ändra storlek på kluster: Raft gör det enkelt att konfigurera om ett kluster utan att sluta arbeta: lägg till eller ta bort noder.
Flotten är byggd ovanpå ett kluster, där varje nod kör en tillståndsmaskin. Raft tillhandahåller tillförlitlig leverans av signaler till alla noder i en given ordning. Således säkerställs övergången av alla tillståndsmaskiner längs samma sekvenser av tillstånd. Således kommer varje nod garanterat att komma överens med andra noder.
En viktig omständighet är att Raft strikt numrerar alla poster i arbetsprotokollet. Anmälningar måste vara strikt i följd. Dessa siffror spelar en viktig roll i driften av algoritmen. Enligt dem bestäms graden av relevans för nodens tillstånd. När man väljer en ledare blir den mest uppdaterade noden alltid ledaren. Samma nummer används för att numrera röstningssessioner. En nod kan bara rösta en gång per röstbegäran.
Om en normal nod inte tar emot meddelanden från ledaren under en längre tid, går den in i "kandidat"-tillståndet och skickar en begäran till andra noder om att rösta. Andra noder röstar på den kandidat från vilken de fick den första förfrågan. Om kandidaten får ett meddelande från ledaren, drar han tillbaka sin kandidatur och återgår till det normala tillståndet. Om kandidaten får majoriteten av rösterna blir han ledare. Om han inte fick majoritet (detta är fallet när flera kandidater dök upp i klustret på en gång och rösterna delades), så väntar kandidaten en slumpmässig tid och inleder ett nytt omröstningsförfarande.
Omröstningsproceduren upprepas tills en ledare har utsetts.
Ledaren är fullt ansvarig för korrekt protokollreplikering. Den skickar en begäran till alla noder i klustret om att lägga till en ny post och anser transaktionen vara framgångsrik först efter att majoriteten av noderna har bekräftat att data har tillämpats och resultatet har sparats på beständiga media.
Som framgår av beskrivningen av algoritmen baseras röstningen på slumpmässiga förväntningar. För att algoritmen ska fungera effektivt måste följande relationer vara uppfyllda:
I tillämpade problem uppfylls dessa villkor oftast lätt. Interaktionstiden för noder mäts vanligtvis i millisekunder. Rösttiden är sekunder. Tiden för normal drift mellan fel är månader.