Så lad os forestille os. 5 katte er låst inde på værelset, og for at vække ejeren skal de alle sammen blive enige om dette, for de kan kun åbne døren ved at læne sig op ad den med fem af dem. Hvis en af kattene er Schrödingers kat, og de andre katte er uvidende om hans beslutning, opstår spørgsmålet: "Hvordan kan de gøre dette?"
I denne artikel vil jeg fortælle dig i enkle vendinger om den teoretiske komponent i verden af distribuerede systemer og principperne for deres arbejde. Og overvej også overfladisk hovedideen bag Paxos'a.
Når udviklere bruger cloud-infrastrukturer, forskellige databaser, arbejder i klynger af et stort antal noder, er de sikre på, at dataene vil være konsistente, sikre og altid tilgængelige. Men hvor er garantierne?
Faktisk er de garantier, vi har, leverandørgarantier. De er beskrevet i dokumentationen som følger: "Denne service er ret pålidelig, den har en given SLA, bare rolig, alt vil fungere fordelt som du forventer."
Vi er tilbøjelige til at tro på det bedste, fordi smarte onkler fra store virksomheder forsikrede os om, at alt vil blive godt. Vi stiller ikke spørgsmålet: hvorfor kan dette overhovedet fungere? Er der nogen formel begrundelse for, at sådanne systemer fungerer korrekt?
Jeg gik for nylig til og var meget inspireret af dette tema. Forelæsninger i skolen lignede mere undervisning i matematisk analyse end noget andet relateret til computersystemer. Men det er præcis sådan, de vigtigste algoritmer, som vi bruger hver dag, uden at have mistanke om det, blev bevist på én gang.
De fleste moderne distribuerede systemer bruger Paxos konsensusalgoritme og dens forskellige modifikationer. Det fedeste er, at gyldigheden og i princippet selve muligheden for eksistensen af denne algoritme kan bevises blot med pen og papir. Samtidig bruges algoritmen i praksis i store systemer, der opererer på et stort antal noder i skyerne.
Let illustration af, hvad der vil blive diskuteret næste: problemet med to generalerLad os tage et kig på opvarmningen .
Vi har to hære - rød og hvid. Hvide tropper er baseret i den belejrede by. Røde tropper ledet af generalerne A1 og A2 er placeret på to sider af byen. De rødhåredes opgave er at angribe den hvide by og vinde. Imidlertid er hver rød generals hær individuelt mindre end hæren af hvide.
Sejrsbetingelser for de rødhårede: begge generaler skal angribe på samme tid for at have en numerisk fordel i forhold til de hvide. For at gøre dette skal generalerne A1 og A2 være enige med hinanden. Hvis alle angriber hver for sig, vil de rødhårede tabe.
For at forhandle kan generalerne A1 og A2 sende budbringere til hinanden gennem den hvide bys territorium. Budbringeren kan med held nå frem til en allieret general eller kan blive opsnappet af fjenden. Spørgsmål: er der sådan en sekvens af kommunikation mellem de rødhårede generaler (rækkefølgen af at sende budbringere fra A1 til A2 og omvendt fra A2 til A1), hvor de garanteret bliver enige om et angreb i time X. Her, ved garantier er det underforstået, at begge generaler vil have en utvetydig bekræftelse på, at en allieret (en anden general) vil angribe nøjagtigt på det aftalte tidspunkt X.
Antag, at A1 sender en messenger til A2 med beskeden: "Lad os angribe i dag ved midnat!". General A1 kan ikke angribe uden bekræftelse fra General A2. Hvis budbringeren fra A1 er nået frem, så sender general A2 en bekræftelse med beskeden: "Ja, lad os fylde de hvide op i dag." Men nu ved general A2 ikke, om hans budbringer er nået frem eller ej, han har ingen garantier for, om angrebet vil være samtidig. Nu mangler General A2 igen bekræftelse.
Hvis vi beskriver deres kommunikation yderligere, viser det sig følgende: uanset hvor mange beskedudvekslingscyklusser der er, er der ingen måde at garantere begge generaler for, at deres beskeder er blevet modtaget (forudsat at en af budbringerne kan opsnappes).
De to generalers problem er en fantastisk illustration af et meget simpelt distribueret system, hvor der er to noder med upålidelig kommunikation. Så vi har ikke 100% garanti for, at de er synkroniserede. Om lignende problemer kun i større skala senere i artiklen.
Introduktion til begrebet distribuerede systemer
Et distribueret system er en gruppe af computere (herefter benævnt noder), der kan udveksle meddelelser. Hver enkelt knude er en selvstændig enhed. En node kan behandle opgaver på egen hånd, men for at kunne kommunikere med andre noder skal den sende og modtage beskeder.
Hvordan meddelelser konkret implementeres, hvilke protokoller der bruges - det interesserer os ikke i denne sammenhæng. Det er vigtigt, at noderne i et distribueret system kan udveksle data med hinanden ved at sende beskeder.
Selve definitionen ser ikke særlig kompliceret ud, men husk på, at et distribueret system har en række egenskaber, som vil være vigtige for os.
Attributter af distribuerede systemer
- samtidighed – muligheden for samtidige eller konkurrenceprægede begivenheder i systemet. Desuden vil vi overveje, at begivenheder, der fandt sted på to forskellige noder, potentielt er samtidige, indtil vi har en klar rækkefølge, hvori disse begivenheder forekommer. Og det gør vi normalt ikke.
- Intet globalt ur. Vi har ikke en klar rækkefølge af begivenheder på grund af manglen på et globalt ur. I den almindelige verden af mennesker er vi vant til, at vi absolut har timer og tid. Alt ændrer sig, når det kommer til distribuerede systemer. Selv ultrapræcise atomure har drift, og der er situationer, hvor vi ikke kan fortælle, hvilken af to begivenheder der skete først. Derfor kan vi heller ikke stole på tiden.
- Uafhængig fejl i systemknudepunkter. Der er et andet problem: noget kan gå galt, simpelthen fordi vores noder ikke er evige. Harddisken kan svigte, den virtuelle maskine i skyen kan genstarte, netværket kan blinke, og meddelelser vil gå tabt. Desuden er der situationer, hvor noderne fungerer, men samtidig modarbejder de systemet. Den sidste klasse af problemer fik endda et separat navn: problemet . Det mest populære eksempel på et distribueret system med et sådant problem er Blockchain. Men i dag vil vi ikke overveje denne særlige klasse af problemer. Vi vil være interesserede i situationer, hvor kun en eller flere noder kan svigte.
- Kommunikationsmodeller (meddelelsesmodeller) mellem noder. Vi har allerede fundet ud af, at noder kommunikerer ved at udveksle beskeder. Der er to velkendte meddelelsesmodeller: synkron og asynkron.
Modeller for kommunikation mellem noder i distribuerede systemer
Synkron model - vi ved med sikkerhed, at der er et begrænset kendt delta af tid, hvor meddelelsen med garanti vil nå fra en knude til en anden. Hvis denne tid er gået, og beskeden ikke er nået frem, kan vi roligt sige, at noden er fejlet. I sådan en model har vi en forudsigelig ventetid.
Asynkron model - i asynkrone modeller antager vi, at ventetiden er begrænset, men der er ikke noget tidsdelta, hvorefter det kan garanteres, at noden er svigtet. De der. ventetiden på en besked fra en node kan være vilkårligt lang. Dette er en vigtig definition, og vi vil tale om det yderligere.
Konsensusbegrebet i distribuerede systemer
Inden du formelt definerer begrebet konsensus, skal du overveje et eksempel på en situation, hvor vi har brug for det, nemlig − State Machine Replikation.
Vi har en del distribueret log. Vi vil gerne have, at den er konsistent og indeholder identiske data på alle noder i et distribueret system. Når en af noderne lærer en ny værdi, som den skal skrive til loggen, er dens opgave at tilbyde denne værdi til alle andre noder, så loggen opdateres på alle noder, og systemet skifter til en ny konsistent tilstand. Samtidig er det vigtigt, at noderne er enige indbyrdes: alle noder er enige om, at den foreslåede nye værdi er korrekt, alle noder accepterer denne værdi, og kun i dette tilfælde kan alle logge en ny værdi.
Med andre ord: ingen af noderne protesterede mod, at de havde mere opdateret information, og den foreslåede værdi var forkert. En aftale mellem noder og enighed om en enkelt korrekt accepteret værdi er konsensus i et distribueret system. Dernæst vil vi tale om algoritmer, der tillader et distribueret system at nå konsensus med garanteret.
Mere formelt kan vi definere en konsensusalgoritme (eller blot en konsensusalgoritme) som en funktion, der tager et distribueret system fra tilstand A til tilstand B. Desuden accepteres denne tilstand af alle noder, og alle noder kan bekræfte det. Som det viser sig, er denne opgave slet ikke så triviel, som den ser ud til ved første øjekast.
Konsensusalgoritmens egenskaber
Konsensusalgoritmen skal have tre egenskaber, for at systemet kan fortsætte med at eksistere og have en vis fremgang i overgangen fra stat til stat:
- Aftale – alle korrekt fungerende noder skal have samme værdi (i artikler findes denne egenskab også som en sikkerhedsegenskab). Alle noder der nu fungerer (ikke ude af drift og ikke mistet kontakten med resten) skal nå til enighed og acceptere en endelig fælles værdi.
Det er her vigtigt at forstå, at noderne i det distribuerede system, vi overvejer, gerne vil være enige. Det vil sige, vi taler nu om systemer, hvor noget simpelthen kan svigte (for eksempel fejler nogle knudepunkter), men i dette system er der absolut ingen knudepunkter, der bevidst modarbejder andre (de byzantinske generalers opgave). På grund af denne egenskab forbliver systemet konsekvent.
- Integritet - hvis alle korrekt fungerende noder tilbyder samme værdi v, så hver korrekt fungerende node skal acceptere denne værdi v.
- Opsigelse - alle korrekt fungerende noder vil i sidste ende få en vis værdi (liveness-egenskab), som gør det muligt for algoritmen at have fremskridt i systemet. Hver individuel korrekt fungerende node skal før eller siden acceptere den endelige værdi og bekræfte den: "For mig er denne værdi sand, jeg er enig med hele systemet."
Et eksempel på, hvordan konsensusalgoritmen fungerer
Selvom egenskaberne af algoritmen måske ikke er helt klare. Derfor vil vi med et eksempel illustrere, hvilke stadier den simpleste konsensusalgoritme gennemgår i et system med en synkron meddelelsesmodel, hvor alle noder fungerer som forventet, beskeder ikke går tabt og intet går i stykker (skeder det virkelig?).
- Det hele starter med et ægteskabsforslag (Propose). Antag, at en klient forbinder til en node kaldet "Node 1" og starter en transaktion og sender en ny værdi til noden - O. Fra nu af vil "Node 1" kaldes tilbud. Hvordan skal forslagsstilleren "Node 1" nu meddele hele systemet, at han har friske data, og han sender beskeder til alle andre noder: "Se! Jeg modtog værdien "O", og jeg vil gerne skrive den ned! Bekræft venligst, at du også vil notere "O" i din log."
- Næste trin er at stemme for den foreslåede værdi (afstemning). Hvad er det for? Det kan ske, at andre noder har modtaget nyere information, og de har data om den samme transaktion.
Når noden "Node 1" sender sin propuse, tjekker de andre noder deres logfiler for data om denne hændelse. Hvis der ikke er nogen konflikt, annoncerer noderne: "Ja, jeg har ingen andre data for denne begivenhed. 'O'-værdien er den mest opdaterede information, vi fortjener."I alle andre tilfælde kan noderne svare på "Node 1": "Hør! Jeg har nyere data om denne transaktion. Ikke "Åh", men noget bedre."
På afstemningsstadiet kommer noderne til en beslutning: enten accepterer de alle den samme værdi, eller en af dem stemmer imod, hvilket angiver, at han har nyere data.
- Hvis afstemningsrunden var vellykket, og alle var for, så flytter systemet til en ny fase - accept af værdien (Accept). "Node 1" samler alle svarene fra andre noder og rapporterer: "Alle var enige om værdien 'O'! Nu erklærer jeg officielt, at "O" er vores nye betydning, den samme for alle! Skriv det ned i din notesbog, glem det ikke. Skriv til din log!"
- Resten af noderne sender bekræftelse (Accepteret), at de har skrevet værdien "O" ned for sig selv, intet nyt er modtaget i løbet af denne tid (en slags to-fase commit). Efter denne betydningsfulde begivenhed mener vi, at den distribuerede transaktion er gennemført.
Konsensusalgoritmen består således i et simpelt tilfælde af fire trin: foreslå, stemme (stemme), acceptere (acceptere), bekræftelse af accept (accepteret).
Hvis vi på et tidspunkt ikke kunne nå til enighed, genstartes algoritmen under hensyntagen til oplysningerne fra de noder, der nægtede at bekræfte den foreslåede værdi.
Konsensusalgoritme i asynkront system
Inden da var alt glat, for det handlede om den synkrone meddelelsesmodel. Men vi ved, at vi i den moderne verden er vant til at gøre alting asynkront. Hvordan fungerer en lignende algoritme i et system med en asynkron meddelelsesmodel, hvor vi mener, at ventetiden på et svar fra en node kan være vilkårligt lang (en knudefejl kan i øvrigt også betragtes som et eksempel, når en node kan svare vilkårligt længe).
Nu hvor vi ved, hvordan konsensusalgoritmen fungerer i princippet, er spørgsmålet til de nysgerrige læsere, der er nået hertil: hvor mange noder i et system af N noder med en asynkron meddelelsesmodel, der kan gå ned, så systemet stadig kan nå konsensus ?
Det rigtige svar og begrundelsen bag spoileren.Det rigtige svar er: 0. Hvis selv en node i et asynkront system går ned, vil systemet ikke være i stand til at nå konsensus. Dette udsagn er bevist i den velkendte FLP-sætning (1985, Fischer, Lynch, Paterson, link til originalen i slutningen af artiklen): "Umuligheden af at nå en distribueret konsensus, hvis mindst én knude svigter."
Gutter, så har vi et problem, vi er vant til, at alt er asynkront med os. Og her er det. Hvordan fortsætter man med at leve?
Vi har lige talt om teori, om matematik. Hvad betyder "konsensus kan ikke nås", at oversætte fra matematisk sprog til vores - teknik? Det betyder, at "ikke altid kan opnås", dvs. der er et tilfælde, hvor konsensus ikke er opnåelig. Og hvad er denne sag?
Dette er præcis den krænkelse af liveness-egenskaben beskrevet ovenfor. Vi har ikke en fælles aftale, og systemet kan ikke udvikle sig (kan ikke afsluttes på en begrænset tid) i det tilfælde, hvor vi ikke har et svar fra alle noder. For i et asynkront system har vi ikke en forudsigelig responstid, og vi kan ikke vide, om en node er nede eller bare tager lang tid at reagere.
Men i praksis kan vi finde en løsning. Lad vores algoritme være i stand til at køre i lang tid i tilfælde af fejl (den kan potentielt køre i det uendelige). Men i de fleste situationer, når de fleste af noderne fungerer korrekt, vil vi have fremskridt i systemet.
I praksis har vi at gøre med delvist synkrone kommunikationsmodeller. Delvis synkronisme forstås som følger: i det generelle tilfælde har vi en asynkron model, men et bestemt begreb om "global stabiliseringstid" for et bestemt tidspunkt er formelt introduceret.
Dette øjeblik i tiden kommer måske ikke i det uendelige, men en dag må det komme. Det virtuelle vækkeur ringer, og fra det øjeblik kan vi forudsige tidsdeltaet, som beskederne når frem til. Fra dette tidspunkt skifter systemet fra asynkront til synkront. I praksis beskæftiger vi os med sådanne systemer.
Paxos algoritme løser konsensusproblemer
er en familie af algoritmer, der løser konsensusproblemet for delvist synkrone systemer, forudsat at nogle noder kan svigte. Forfatteren af Paxos er . Han foreslog et formelt bevis for eksistensen og rigtigheden af algoritmen i 1989.
Men beviset viste sig på ingen måde at være trivielt. Den første publikation udkom først i 1998 (33 sider), der beskriver algoritmen. Det viste sig, at det var ekstremt svært at forstå, og i 2001 blev der offentliggjort en forklaring til artiklen, som tog 14 sider. Mængderne af publikationer er givet for at vise, at problemet med konsensus faktisk slet ikke er simpelt, og bag sådanne algoritmer er der et enormt arbejde af de klogeste mennesker.
Det er interessant, at Leslie Lampor selv i sit foredrag bemærkede, at der i den anden artikel-forklaring er ét udsagn, én linje (han specificerede ikke hvilken), som kan fortolkes på forskellige måder. Og på grund af dette fungerer et stort antal moderne Paxos-implementeringer ikke helt korrekt.
En detaljeret analyse af Paxos' arbejde vil tage mere end én artikel, så jeg vil forsøge at formidle hovedideen i algoritmen meget kort. I linkene i slutningen af min artikel finder du materialer til yderligere dykning i dette emne.
Roller hos Paxos
Paxos-algoritmen har et begreb om roller. Overvej tre vigtigste (der er ændringer med yderligere roller):
- Forslagsstillere (der kan også være udtryk: ledere eller koordinatorer). Det er de fyre, der lærer om en ny mening fra brugeren og påtager sig rollen som leder. Deres opgave er at lancere en runde af forslag til en ny værdi og koordinere yderligere handlinger af knudepunkterne. Desuden tillader Paxos tilstedeværelsen af flere ledere i visse situationer.
- Acceptanter (vælgere). Dette er de noder, der stemmer for at acceptere eller afvise en bestemt værdi. Deres rolle er meget vigtig, fordi beslutningen afhænger af dem: hvilken tilstand systemet vil gå (eller ikke gå) til efter næste fase af konsensusalgoritmen.
- lærende. Noder, der blot accepterer og skriver den nye accepterede værdi, når systemets tilstand har ændret sig. De træffer ikke beslutninger, de modtager blot data og kan give dem til slutbrugeren.
En node kan kombinere flere roller i forskellige situationer.
Begrebet kvorum
Vi antager, at vi har et system med N noder. Og de fleste af dem F noder kan fejle. Hvis F-noder fejler, så burde vi have mindst 2F+1 acceptor noder.
Dette er nødvendigt, så vi altid, selv i den værste situation, "gode", korrekt fungerende noder har flertal. Det er F+1 "gode" noder, der stemte overens, og den endelige værdi vil blive accepteret. Ellers kan der opstå en situation, hvor forskellige lokale grupper får forskellige betydninger og ikke kan blive enige indbyrdes. Så vi har brug for et absolut flertal for at vinde afstemningen.
Generel idé om Paxos konsensusalgoritme
Paxos-algoritmen antager to store faser, som igen er opdelt i to trin hver:
- Fase 1a: Forbered dig. Under forberedelsesfasen informerer lederen (forslagsstilleren) alle noder: ”Vi starter en ny afstemningsfase. Vi har en ny runde. Antallet af denne runde er n. Vi begynder at stemme nu." Indtil videre rapporterer den blot starten på en ny cyklus, men rapporterer ikke den nye værdi. Opgaven for denne fase er at starte en ny runde og informere alle om sit unikke nummer. Det runde tal er vigtigt, det skal være større end alle tidligere stemmetal fra alle tidligere ledere. Da det er takket være det runde tal, at andre noder i systemet vil forstå, hvor friske lederens data er. Sandsynligvis har andre noder allerede afstemningsresultater fra langt senere runder og vil blot fortælle lederen, at han er bagud i tiden.
- Fase 1b: Løfte. Når acceptorknudepunkterne har modtaget nummeret på den nye afstemningsfase, er to udfald mulige:
- Antallet n af den nye stemme er større end antallet af nogen af de tidligere afstemninger, som acceptereren deltog i. Derefter sender acceptanten et løfte til lederen om, at den ikke længere vil deltage i nogen afstemninger med et tal mindre end n. Hvis acceptereren allerede har stemt for noget (det vil sige, den har allerede accepteret en vis værdi i anden fase), så tilføjer den den accepterede værdi og nummeret på den afstemning, den deltog i, til sit løfte.
- Ellers, hvis acceptereren allerede kender til den højttalte stemme, kan den simpelthen ignorere forberedelsestrinnet og ikke svare lederen.
- Fase 2a: Accepter. Lederen skal vente på et svar fra kvorummet (de fleste af noderne i systemet), og hvis det nødvendige antal svar modtages, har han to muligheder for udvikling af begivenheder:
- Nogle af acceptanterne har indsendt værdier, som de allerede har stemt på. I dette tilfælde vælger lederen værdien fra afstemningen med det højeste tal. Lad os kalde denne værdi x, og sende en besked som denne til alle noder: "Accepter (n, x)", hvor den første værdi er stemmetallet fra sit eget Foreslå trin, og den anden værdi er det, alle samledes til, dvs. værdi, som vi faktisk stemmer for.
- Hvis ingen af acceptanterne sendte nogen værdier, men de blot lovede at stemme i denne runde, kan lederen invitere dem til at stemme for deres værdi, den værdi som han overhovedet blev leder for. Lad os kalde det y. Den sender til alle knudepunkter en meddelelse i form: "Accepter (n, y)", analogt med det tidligere resultat.
- Fase 2b: Accepteret. Ydermere er acceptorknudepunkterne, efter at have modtaget beskeden "Accepter (...)", fra lederen enige i den (send bekræftelse til alle noder om, at de er enige i den nye værdi), hvis de ikke har lovet nogle (anden) leder til at deltage i afstemningen med rundens nummer n' > nellers ignorerer de bekræftelsesprompten.
Hvis flertallet af noder svarede lederen, og de alle bekræftede den nye værdi, anses den nye værdi for at være accepteret. Hurra! Hvis flertallet ikke er skrevet, eller der er noder, der nægtede at acceptere den nye værdi, så starter alt forfra.
Sådan fungerer Paxos-algoritmen. Hvert af disse stadier har mange finesser, vi overvejede praktisk talt ikke forskellige typer fejl, problemer med flere ledere og meget mere, men formålet med denne artikel er kun at introducere læseren til verden af distribueret databehandling på øverste niveau.
Det er også værd at bemærke, at Paxos ikke er den eneste af sin slags, der er andre algoritmer, f.eks. , men dette er et emne for en anden artikel.
Links til materialer til videre undersøgelse
Begynderniveau:
- , Preethi Kasireddy, blogartikel om Medium
- , Adi Kancherla, blogartikel om Medium
- Ittai Abraham blog
- , Ittai Abraham, blogartikel
Leslie Lamport Niveau:
- Fischer, Lynch og Paterson, forskningsartikel, 1985
- Leslie Lamport, forskningsartikel, 1998
- Leslie Lamport, forskningsartikel, 2001
Kilde: www.habr.com