Tillståndsmaskinreplikering

Inom datavetenskap är tillståndsmaskinreplikering ( SMR ) eller tillståndsmaskinsmetod en allmän metod för att implementera en feltolerant tjänst genom att replikera servrar och koordinera klientinteraktioner med serverreplikor . Tillvägagångssättet ger också ett ramverk för att förstå och designa protokoll för replikeringshantering.

Problemdefinition

Distribuerad tjänst

När det gäller kunder och tjänster. Varje tjänst omfattar en eller flera servrar och exportoperationer som klienter anropar genom att göra förfrågningar. Även om att använda en enda centraliserad server är det enklaste sättet att implementera en tjänst, kan den resulterande tjänsten bara vara lika feltolerant som processorn som exekverar den servern. Om denna feltoleransnivå är oacceptabel kan flera servrar som misslyckas oberoende av varandra användas. Vanligtvis exekveras repliker av en enskild server på separata processorer i ett distribuerat system, och protokoll används för att koordinera klientinteraktioner med dessa repliker.

Statsmaskin

Huvudartikel: Finite-state-maskin

För den efterföljande diskussionen kommer en State Machine att definieras som följande tuppel av värden (Se även Mealy machine och Moore Machine ):

  • En uppsättning stater
  • En uppsättning ingångar
  • En uppsättning utgångar
  • En övergångsfunktion (Input × State → State)
  • En utgångsfunktion (Input × State → Output)
  • En framstående stat som kallas Start.

En tillståndsmaskin börjar vid staten märkt Start. Varje mottagen ingång passerar genom övergångs- och utmatningsfunktionen för att producera ett nytt tillstånd och en utgång. Tillståndet hålls stabilt tills en ny ingång tas emot, medan utsignalen kommuniceras till lämplig mottagare.

Denna diskussion kräver att en tillståndsmaskin är deterministisk : flera kopior av samma tillståndsmaskin börjar i starttillståndet och att ta emot samma ingångar i samma ordning kommer att anlända till samma tillstånd som har genererat samma utdata.

Vanligtvis begränsar system baserade på tillståndsmaskinreplikering frivilligt sina implementeringar till att använda finita-tillståndsmaskiner för att förenkla felåterställning.

Feltolerans

Determinism är en idealisk egenskap för att tillhandahålla feltolerans. Intuitivt, om det finns flera kopior av ett system, skulle ett fel i det ena märkas som en skillnad i tillståndet eller produktionen från de andra.

Ett litet avdrag visar att det minsta antalet kopior som behövs för feltolerans är tre; en som har ett fel och två andra som vi jämför State och Output med. Två kopior räcker inte eftersom det inte finns något sätt att avgöra vilken kopia som är den felaktiga.

Ytterligare avdrag visar att ett system med tre kopior kan stödja högst ett fel (efter vilket det måste reparera eller ersätta den felaktiga kopian). Om mer än en av kopiorna skulle misslyckas, kan alla tre stater och utgångar skilja sig åt, och det skulle inte finnas något sätt att välja vilken som är den korrekta.

I allmänhet måste ett system som stöder F-fel ha 2F+1 kopior (även kallade repliker). De extra kopiorna används som bevis för att avgöra vilka av kopiorna som är korrekta och vilka som är felaktiga. Särskilda fall kan förbättra dessa gränser.

Allt detta avdrag förutsätter att repliker endast upplever slumpmässiga oberoende fel som minnesfel eller hårddiskkrasch. Fel som orsakas av repliker som försöker ljuga, lura eller samverka kan också hanteras av State Machine Approach, med isolerade ändringar.

Misslyckade repliker krävs inte för att stoppa; de kan fortsätta att fungera, inklusive generera falska eller felaktiga utdata.

Specialfall: Fail-Stop

Teoretiskt sett, om en misslyckad replik garanteras att stoppa utan att generera utdata, krävs endast F+1 repliker, och klienter kan acceptera den första utdata som genereras av systemet. Inga befintliga system uppnår denna gräns, men den används ofta när man analyserar system byggda ovanpå ett feltolerant lager (eftersom det feltoleranta lagret ger fail-stop semantik till alla lager ovanför det).

Specialfall: bysantinskt misslyckande

Fel där en replik skickar olika värden i olika riktningar (till exempel korrekt utdata till några av dess andra repliker och felaktiga utdata till andra) kallas bysantinska fel . Bysantinska misslyckanden kan vara slumpmässiga, falska fel eller illvilliga, intelligenta attacker. 2F+1 repliker, med icke-kryptografiska hash räcker för att överleva alla icke-skadliga bysantinska misslyckanden (med hög sannolikhet). Skadliga attacker kräver kryptografiska primitiver för att uppnå 2F+1 (med meddelandesignaturer), eller så kan icke-kryptografiska tekniker användas men antalet repliker måste ökas till 3F+1.

Statens maskintillvägagångssätt

Den föregående intuitiva diskussionen innebär enkel teknik för att implementera en feltolerant tjänst i termer av en State Machine:

  1. Placera kopior av State Machine på flera oberoende servrar.
  2. Ta emot klientförfrågningar, tolkade som indata till tillståndsmaskinen.
  3. Välj en beställning för ingångarna.
  4. Utför ingångar i vald ordning på varje server.
  5. Svara på klienter med utdata från tillståndsmaskinen.
  6. Övervaka repliker för skillnader i tillstånd eller utdata.

Resten av denna artikel utvecklar detaljerna i denna teknik.

Bilagan innehåller diskussioner om typiska tillägg som används i verkliga system som loggning , kontrollpunkter , omkonfigurering och tillståndsöverföring .

Beställning av ingångar

Det kritiska steget i att bygga ett distribuerat system av statliga maskiner är att välja en beställning för indata som ska bearbetas. Eftersom alla icke-felaktiga repliker kommer att anlända till samma tillstånd och utgång om de ges samma indata, är det absolut nödvändigt att indata skickas i en likvärdig ordning vid varje replik. Många lösningar har föreslagits i litteraturen.

En synlig kanal är en kommunikationsväg mellan två enheter som aktivt deltar i systemet (som klienter och servrar). Exempel: klient till server, server till server

En dold kanal är en kommunikationsväg som inte avslöjas för systemet. Exempel: klient till klient kanaler är vanligtvis dolda; som användare som kommunicerar över en telefon, eller en process som skriver filer till disk som läses av en annan process.

När alla kommunikationsvägar är synliga kanaler och inga dolda kanaler existerar, kan en partiell global ordning ( Causal Order) härledas från kommunikationsmönstret. Causal Order kan härledas oberoende av varje server. Indata till tillståndsmaskinen kan utföras i kausal ordning, vilket garanterar konsekvent tillstånd och utdata för alla icke-felaktiga repliker.

I öppna system är dolda kanaler vanliga och en svagare form av beställning måste användas. En ordning av ingångar kan definieras med hjälp av ett röstningsprotokoll vars resultat endast beror på de synliga kanalerna.

Problemet med att rösta för ett enda värde av en grupp oberoende enheter kallas Consensus . I förlängningen kan en serie värden väljas av en serie konsensusinstanser. Detta problem blir svårt när deltagarna eller deras kommunikationsmedium kan uppleva misslyckanden.

Indata kan ordnas efter sin position i serien av konsensusinstanser ( Consensus Order ) . Consensus Order kan härledas oberoende av varje server. Indata till tillståndsmaskinen kan utföras i konsensusordning, vilket garanterar konsekvent tillstånd och utdata för alla icke-felaktiga repliker.

Optimera orsaks- och konsensusordning
I vissa fall finns ytterligare information tillgänglig (som realtidsklockor). I dessa fall är det möjligt att uppnå effektivare orsaks- eller konsensusordning för ingångarna, med ett minskat antal meddelanden, färre meddelanderundor eller mindre meddelandestorlekar. Se referenser för detaljer
Ytterligare optimeringar är tillgängliga när man tar hänsyn till semantiken för State Machine-operationer (som läs- och skrivoperationer). Se referenser Generalized Paxos .

Skickar utgångar

Klientförfrågningar tolkas som indata till tillståndsmaskinen och bearbetas till utdata i lämplig ordning. Varje replik kommer att generera en utdata oberoende. Icke-felaktiga repliker kommer alltid att producera samma utdata. Innan klientsvaret kan skickas måste felaktiga utgångar filtreras bort. Normalt kommer en majoritet av replikerna att returnera samma utdata, och denna utdata skickas som svar till klienten.

Systemfel

Om det inte finns någon majoritet av replikerna med samma utdata, eller om mindre än en majoritet av replikerna returnerar en utdata, har ett systemfel inträffat. Klientsvaret måste vara den unika Output: FAIL.

Revision och feldetektering

Den permanenta, oplanerade kompromissen av en replik kallas ett misslyckande . Bevis på misslyckande är svårt att få, eftersom repliken helt enkelt kan vara långsam att svara, eller till och med ljuga om dess status.

Icke-felaktiga repliker kommer alltid att innehålla samma tillstånd och producera samma utdata. Denna invariant möjliggör feldetektering genom att jämföra tillstånd och utdata för alla repliker. Vanligtvis förklaras en replik med tillstånd eller utgång som skiljer sig från majoriteten av replikerna vara felaktig.

En vanlig implementering är att skicka kontrollsummor av det aktuella repliktillståndet och de senaste utgångarna mellan servrar. En granskningsprocess på varje server startar om den lokala repliken om en avvikelse upptäcks. Kryptografisk säkerhet krävs inte för kontrollsummor.

Det är möjligt att den lokala servern har äventyrats eller att granskningsprocessen är felaktig och repliken fortsätter att fungera felaktigt. Detta fall hanteras på ett säkert sätt av utgångsfiltret som beskrivits tidigare (se Skicka utgångar ) .

Bilaga: Tillägg

Inmatningslogg

I ett system utan fel kan ingångarna kasseras efter att ha bearbetats av tillståndsmaskinen. Realistiska distributioner måste kompensera för övergående icke-felbeteenden i systemet, såsom meddelandeförlust, nätverkspartitioner och långsamma processorer.

En teknik är att lagra serien av ingångar i en logg. Under tider av övergående beteende kan repliker begära kopior av en loggpost från en annan replik för att fylla i saknade indata.

I allmänhet krävs inte att loggen är beständig (den kan hållas i minnet). En beständig logg kan kompensera för längre övergående perioder eller stödja ytterligare systemfunktioner som Checkpoints och Reconfiguration .

Kontrollpunkter

Om den lämnas omarkerad kommer en logg att växa tills den tar slut på alla tillgängliga lagringsresurser. För fortsatt drift är det nödvändigt att glömma loggposter. I allmänhet kan en loggpost glömmas bort när dess innehåll inte längre är relevant (till exempel om alla repliker har bearbetat en ingång, behövs inte längre kunskapen om ingången).

En vanlig teknik för att kontrollera loggstorleken är att lagra ett duplikattillstånd (kallat en kontrollpunkt ), och sedan kasta alla loggposter som bidrog till kontrollpunkten. Detta sparar utrymme när det duplicerade tillståndet är mindre än storleken på loggen.

Kontrollpunkter kan läggas till till valfri State Machine genom att stödja en extra ingång som kallas CHECKPOINT . Varje replik upprätthåller en kontrollpunkt utöver det aktuella tillståndsvärdet. När loggen växer sig stor skickar en replik kommandot CHECKPOINT precis som en klientförfrågan. Systemet kommer att säkerställa att repliker som inte är felaktiga bearbetar detta kommando i samma ordning, varefter alla loggposter före kontrollpunkten kan kasseras.

I ett system med kontrollpunkter ignoreras förfrågningar om loggposter som inträffar före kontrollpunkten. Repliker som inte kan hitta kopior av en nödvändig loggpost är felaktiga och måste anslutas till systemet igen (se Omkonfigurering ).

Omkonfigurering

Omkonfiguration gör att repliker kan läggas till och tas bort från ett system medan klientförfrågningar fortsätter att behandlas. Planerat underhåll och replikfel är vanliga exempel på omkonfigurering. Omkonfigurering innebär att avsluta och gå med .

Att sluta

När en server upptäcker att dess tillstånd eller utgång är felaktig (se Granskning och feldetektering ), kan den selektivt avsluta systemet. På samma sätt kan en administratör manuellt utföra ett kommando för att ta bort en replik för underhåll.

En ny ingång läggs till i State Machine som heter QUIT . En replik skickar detta kommando till systemet precis som en klientförfrågan. Alla icke-felaktiga repliker tar bort den avslutande repliken från systemet när den här inmatningen bearbetas. Under denna tid kan repliken ignorera alla protokollmeddelanden. Om en majoritet av icke-felaktiga repliker finns kvar, är avslutningen framgångsrik. Om inte finns det ett systemfel .

Sammanfogning

Efter att ha avslutats kan en misslyckad server selektivt starta om eller återansluta till systemet. På samma sätt kan en administratör lägga till en ny replik till gruppen för ytterligare kapacitet.

En ny ingång läggs till i State Machine som heter JOIN . En replik skickar detta kommando till systemet precis som en klientförfrågan. Alla icke-felaktiga repliker lägger till kopplingsnoden till systemet när denna indata bearbetas. En ny kopia måste vara uppdaterad om systemets stat innan den ansluts (se State Transfer ) .

Statsöverföring

När en ny replik görs tillgänglig eller en gammal replik startas om, måste den tas upp till det aktuella tillståndet innan indata bearbetas (se Gå med ). Logiskt sett kräver detta att varje ingång från systemets gryning appliceras i lämplig ordning.

Typiska distributioner kortsluter det logiska flödet genom att utföra en tillståndsöverföring av den senaste kontrollpunkten (se kontrollpunkter ). Detta innebär att direkt kopiera tillståndet för en replik till en annan med hjälp av ett out-of-band-protokoll.

En kontrollpunkt kan vara stor, vilket kräver en förlängd överföringsperiod. Under denna tid kan nya ingångar läggas till i loggen. Om detta inträffar måste den nya repliken också ta emot de nya ingångarna och tillämpa dem efter att kontrollpunkten har tagits emot. Typiska distributioner lägger till den nya repliken som observatör till beställningsprotokollet innan tillståndsöverföringen påbörjas, vilket gör att den nya repliken kan samla in indata under denna period.

Optimera tillståndsöverföring

Vanliga distributioner minskar tillståndsöverföringstider genom att endast skicka tillståndskomponenter som skiljer sig åt. Detta kräver kunskap om State Machines interna delar. Eftersom tillståndsöverföring vanligtvis är ett out-of-band-protokoll är detta antagande inte svårt att uppnå.

Komprimering är en annan funktion som vanligtvis läggs till i tillståndsöverföringsprotokoll, vilket minskar storleken på den totala överföringen.

Ledarval (för Paxos)

Paxos är ett protokoll för att lösa konsensus och kan användas som protokoll för att implementera Consensus Order.

Paxos kräver en enda ledare för att säkerställa livlighet. Det vill säga, en av replikerna måste förbli ledare tillräckligt länge för att uppnå konsensus om nästa operation av statsmaskinen. Systembeteende påverkas inte om ledaren byter efter varje instans, eller om ledaren byter flera gånger per instans. Det enda kravet är att en replik förblir ledare tillräckligt länge för att föra systemet framåt.

Konfliktlösning

I allmänhet är en ledare endast nödvändig när det råder oenighet om vilken operation som ska utföras, och om dessa operationer är i konflikt på något sätt (till exempel om de inte pendlar).

När motstridiga operationer föreslås, agerar ledaren som den enda auktoriteten för att ställa in protokollet, definiera en ordning för operationerna, vilket gör att systemet kan göra framsteg.

Med Paxos kan flera repliker tro att de är ledare samtidigt. Den här egenskapen gör Leader Election för Paxos mycket enkel, och alla algoritmer som garanterar en "eventuell ledare" kommer att fungera.

Historisk bakgrund

Ett antal forskare publicerade artiklar om den replikerade tillståndsmaskinens strategi i början av 1980-talet. Anita Borg beskrev en implementering av ett feltolerant operativsystem baserat på replikerade tillståndsmaskiner i en tidning från 1983 " Ett meddelandesystem som stödjer feltolerans" . Leslie Lamport föreslog också tillståndsmaskinens tillvägagångssätt, i sin artikel från 1984 om "Användning av tid istället för timeout i distribuerade system" . Fred Schneider utvecklade senare tillvägagångssättet i sin artikel "Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial" .

Ken Birman utvecklade den virtuella synkroniseringsmodellen i en serie artiklar publicerade mellan 1985 och 1987. Den primära referensen till detta arbete är "Exploiting Virtual Synchrony in Distributed Systems", som beskriver Isis Toolkit, ett system som användes för att bygga New York och schweiziska börser, franska flygledningssystem, US Navy AEGIS Warship och andra applikationer.

Nyligen utförda arbeten av Miguel Castro och Barbara Liskov använde tillvägagångssättet för tillståndsmaskiner i vad de kallar en "Praktisk bysantinsk feltolerans" -arkitektur som replikerar särskilt känsliga tjänster med en version av Lamports ursprungliga tillvägagångssätt, men med optimeringar som avsevärt förbättrar prestandan.

Senast har det också skapats BFT-SMaRt-biblioteket, ett högpresterande bysantinskt feltolerant replikeringsbibliotek för tillståndsmaskiner utvecklat i Java. Detta bibliotek implementerar ett protokoll som mycket liknar PBFT:s, plus kompletterande protokoll som erbjuder tillståndsöverföring och omkonfigurering av värdar i farten (dvs JOIN- och LEAVE-operationer). BFT-SMaRt är det senaste försöket att implementera tillståndsmaskinreplikering, som fortfarande underhålls aktivt.

Raft , en konsensusbaserad algoritm, utvecklades 2013.

Motiverad av PBFT introducerades Tendermint BFT för partiella asynkrona nätverk och det används främst för Proof of Stake-blockkedjor.

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=State_machine_replication&oldid=1139730236 "