Så la oss forestille oss. Det er 5 katter innelåst i rommet, og for å vekke eieren, må de alle bli enige om dette seg imellom, for de kan bare åpne døren med fem av dem som lener seg på den. Hvis en av kattene er Schrödingers katt, og de andre kattene ikke vet om avgjørelsen hans, oppstår spørsmålet: "Hvordan kan de gjøre det?"
I denne artikkelen vil jeg fortelle deg på en enkel måte om den teoretiske komponenten i verden av distribuerte systemer og prinsippene for deres drift. Jeg vil også overfladisk undersøke hovedideen bak Paxos.
Når utviklere bruker skyinfrastrukturer, ulike databaser og jobber i klynger med et stort antall noder, er de sikre på at dataene vil være komplette, sikre og alltid tilgjengelige. Men hvor er garantiene?
I hovedsak er garantiene vi har leverandørgarantier. De er beskrevet i dokumentasjonen som følger: "Denne tjenesten er ganske pålitelig, den har en gitt SLA, ikke bekymre deg, alt vil fungere distribuert som du forventer."
Vi har en tendens til å tro på det beste, fordi smarte gutter fra store selskaper forsikret oss om at alt vil bli bra. Vi stiller ikke spørsmålet: hvorfor kan dette i det hele tatt fungere? Er det noen formell begrunnelse for riktig drift av slike systemer?
Jeg gikk nylig til og ble veldig inspirert av dette temaet. Forelesninger på skolen var mer som kalkulustimer enn noe relatert til datasystemer. Men dette er nøyaktig hvordan de viktigste algoritmene som vi bruker hver dag, uten engang å vite det, ble bevist på en gang.
De fleste moderne distribuerte systemer bruker Paxos konsensusalgoritme og dens ulike modifikasjoner. Det kuleste er at gyldigheten og, i prinsippet, selve muligheten for eksistensen av denne algoritmen kan bevises ganske enkelt med penn og papir. I praksis brukes algoritmen i store systemer som kjører på et stort antall noder i skyene.
En lett illustrasjon av det som vil bli diskutert videre: oppgaven til to generalerLa oss se etter en oppvarming .
Vi har to hærer - rød og hvit. Hvite tropper er basert i den beleirede byen. Røde tropper ledet av generalene A1 og A2 befinner seg på to sider av byen. De rødhåredes oppgave er å angripe den hvite byen og vinne. Imidlertid er hæren til hver rød general individuelt mindre enn den hvite hæren.
Seiersbetingelser for de røde: begge generalene må angripe samtidig for å ha en numerisk fordel over de hvite. For å gjøre dette, må generalene A1 og A2 komme til enighet med hverandre. Hvis alle angriper hver for seg, vil de rødhårede tape.
For å komme til enighet kan generalene A1 og A2 sende budbringere til hverandre gjennom territoriet til den hvite byen. Budbringeren kan lykkes med å nå en alliert general eller kan bli fanget opp av fienden. Spørsmål: er det en slik sekvens av kommunikasjoner mellom de rødhårede generalene (sekvensen med å sende bud fra A1 til A2 og omvendt fra A2 til A1), der de garantert blir enige om et angrep i time X. Her, garantier betyr at begge generalene vil ha en entydig bekreftelse på at en alliert (en annen general) definitivt vil angripe til avtalt tid X.
Anta at A1 sender en messenger til A2 med meldingen: «La oss angripe i dag ved midnatt!» General A1 kan ikke angripe uten bekreftelse fra General A2. Hvis budbringeren fra A1 har ankommet, sender general A2 bekreftelse med meldingen: "Ja, la oss drepe de hvite i dag." Men nå vet ikke general A2 om budbringeren hans har kommet eller ikke, han har ingen garanti for om angrepet vil være samtidig. Nå trenger general A2 igjen bekreftelse.
Hvis vi beskriver kommunikasjonen deres ytterligere, blir det klart at uansett hvor mange meldingsutvekslingssykluser det er, er det ingen måte å garantere at begge generalene har mottatt meldingene deres (forutsatt at begge budbringerne kan avlyttes).
The Two Generals Problem er en flott illustrasjon av et veldig enkelt distribuert system hvor det er to noder med upålitelig kommunikasjon. Dette betyr at vi ikke har 100 % garanti for at de er synkronisert. Lignende problemer diskuteres bare i større skala senere i artikkelen.
Vi introduserer konseptet distribuerte systemer
Et distribuert system er en gruppe datamaskiner (heretter vil vi kalle dem noder) som kan utveksle meldinger. Hver enkelt node er en slags autonom enhet. En node kan behandle oppgaver på egen hånd, men for å kommunisere med andre noder må den sende og motta meldinger.
Hvordan nøyaktig meldinger implementeres, hvilke protokoller som brukes - dette er ikke av interesse for oss i denne sammenhengen. Det er viktig at nodene til et distribuert system kan utveksle data med hverandre ved å sende meldinger.
Selve definisjonen ser ikke veldig komplisert ut, men vi må ta hensyn til at et distribuert system har en rekke attributter som vil være viktige for oss.
Attributter til distribuerte systemer
- samtidighet – muligheten for samtidige eller samtidige hendelser i systemet. Dessuten vil vi vurdere hendelser som skjer på to forskjellige noder som potensielt samtidige så lenge vi ikke har en klar rekkefølge for forekomst av disse hendelsene. Men som regel har vi det ikke.
- Ingen global klokke. Vi har ikke en klar rekkefølge av hendelser på grunn av mangelen på en global klokke. I den vanlige verden av mennesker er vi vant til at vi absolutt har klokker og tid. Alt endres når det kommer til distribuerte systemer. Selv ultrapresise atomklokker har drift, og det kan være situasjoner der vi ikke kan fortelle hvilken av to hendelser som skjedde først. Derfor kan vi heller ikke stole på tid.
- Uavhengig feil på systemnoder. Det er et annet problem: noe kan gå galt rett og slett fordi nodene våre ikke varer evig. Harddisken kan svikte, den virtuelle maskinen i skyen kan starte på nytt, nettverket kan blinke og meldinger vil gå tapt. Dessuten kan det være situasjoner der noder fungerer, men samtidig jobber mot systemet. Den siste klassen med problemer fikk til og med et eget navn: problem . Det mest populære eksemplet på et distribuert system med dette problemet er Blockchain. Men i dag vil vi ikke vurdere denne spesielle klassen av problemer. Vi vil være interessert i situasjoner der bare én eller flere noder kan svikte.
- Kommunikasjonsmodeller (meldingsmodeller) mellom noder. Vi har allerede etablert at noder kommuniserer ved å utveksle meldinger. Det er to velkjente meldingsmodeller: synkron og asynkron.
Modeller for kommunikasjon mellom noder i distribuerte systemer
Synkron modell – Vi vet med sikkerhet at det er et begrenset kjent tidsdelta der en melding garantert når fra en node til en annen. Hvis denne tiden har gått og meldingen ikke har kommet, kan vi trygt si at noden har sviktet. I denne modellen har vi forutsigbare ventetider.
Asynkron modell – i asynkrone modeller anser vi at ventetiden er begrenset, men det er ikke noe slikt tidsdelta som vi kan garantere at noden har sviktet. De. Ventetiden for en melding fra en node kan være vilkårlig lang. Dette er en viktig definisjon, og vi vil snakke om den videre.
Konsensusbegrepet i distribuerte systemer
Før vi formelt definerer begrepet konsensus, la oss vurdere et eksempel på en situasjon der vi trenger det, nemlig - Statens maskinreplikering.
Vi har en del distribuert logg. Vi ønsker at den skal være konsistent og inneholde identiske data på alle noder i det distribuerte systemet. Når en av nodene lærer en ny verdi som den skal skrive til loggen, blir dens oppgave å tilby denne verdien til alle andre noder slik at loggen oppdateres på alle noder og systemet flytter til en ny konsistent tilstand. I dette tilfellet er det viktig at nodene er enige seg imellom: alle noder er enige om at den foreslåtte nye verdien er riktig, alle noder aksepterer denne verdien, og bare i dette tilfellet kan alle skrive den nye verdien til loggen.
Med andre ord: ingen av nodene protesterte mot at de hadde mer relevant informasjon, og den foreslåtte verdien var feil. Enighet mellom noder og enighet om en enkelt korrekt akseptert verdi er konsensus i et distribuert system. Deretter vil vi snakke om algoritmer som lar et distribuert system garantert oppnå konsensus.
Mer formelt kan vi definere en konsensusalgoritme (eller rett og slett en konsensusalgoritme) som en bestemt funksjon som overfører et distribuert system fra tilstand A til tilstand B. Dessuten er denne tilstanden akseptert av alle noder, og alle noder kan bekrefte det. Som det viser seg, er denne oppgaven slett ikke så triviell som den ser ut ved første øyekast.
Egenskaper til konsensusalgoritmen
Konsensusalgoritmen må ha tre egenskaper for at systemet skal fortsette å eksistere og ha en viss fremgang i å bevege seg fra stat til stat:
- Avtale – alle noder som fungerer riktig må ha samme verdi (i artikler omtales denne egenskapen også som sikkerhetsegenskap). Alle noder som for øyeblikket fungerer (ikke har sviktet eller mistet kontakten med de andre) må komme til enighet og akseptere en endelig felles verdi.
Det er viktig å forstå her at nodene i det distribuerte systemet vi vurderer ønsker å være enige. Det vil si at vi nå snakker om systemer der noe rett og slett kan svikte (for eksempel svikter noen noder), men i dette systemet er det definitivt ingen noder som bevisst jobber mot andre (oppgaven til bysantinske generaler). På grunn av denne egenskapen forblir systemet konsekvent.
- Integritet - hvis alle riktig fungerende noder gir samme verdi v, som betyr at hver node som fungerer riktig må akseptere denne verdien v.
- Oppsigelse – alle korrekt fungerende noder vil etter hvert få en viss verdi (liveness-egenskap), som gjør at algoritmen kan gjøre fremskritt i systemet. Hver enkelt node må før eller siden godta den endelige verdien og bekrefte den: "For meg er denne verdien sann, jeg er enig med hele systemet."
Et eksempel på hvordan konsensusalgoritmen fungerer
Selv om egenskapene til algoritmen kanskje ikke er helt klare. Derfor vil vi illustrere med et eksempel hvilke stadier den enkleste konsensusalgoritmen går gjennom i et system med en synkron meldingsmodell, der alle noder fungerer som forventet, meldinger ikke går tapt og ingenting går i stykker (skjer dette virkelig?).
- Det hele starter med et ekteskapsforslag (Propose). La oss anta at en klient koblet til en node kalt "Node 1" og startet en transaksjon, og sender en ny verdi til noden - O. Fra nå av vil vi kalle "Node 1" tilbud. Som forslagsstiller må "Node 1" nå varsle hele systemet om at det har ferske data, og det sender meldinger til alle andre noder: "Se! Betydningen "O" kom til meg, og jeg vil skrive den ned! Vennligst bekreft at du også vil registrere "O" i loggen din."
- Neste trinn er å stemme for den foreslåtte verdien (Voting). Hva er den til? Det kan hende at andre noder har mottatt nyere informasjon, og de har data om samme transaksjon.
Når node "Node 1" sender sitt forslag, sjekker de andre nodene loggene sine for data om denne hendelsen. Hvis det ikke er noen motsetninger, kunngjør nodene: "Ja, jeg har ingen andre data for denne hendelsen. "O"-verdien er den siste informasjonen vi fortjener."I alle andre tilfeller kan noder svare på "Node 1": "Hør! Jeg har nyere data om denne transaksjonen. Ikke "O", men noe bedre."
På avstemningsstadiet kommer nodene til en avgjørelse: enten godtar de samme verdi, eller en av dem stemmer imot, noe som indikerer at han har nyere data.
- Hvis avstemningsrunden var vellykket og alle var for, så går systemet til et nytt stadium - Aksepter verdien. «Node 1» samler alle svarene fra andre noder og rapporterer: «Alle var enige om verdien «O»! Nå erklærer jeg offisielt at "O" er vår nye betydning, den samme for alle! Skriv det ned i den lille boken din, ikke glem. Skriv det ned i loggen din!"
- De resterende nodene sender bekreftelse (Godtatt) på at de har skrevet ned verdien "O", ingenting nytt har kommet i løpet av denne tiden (en slags to-fase commit). Etter denne betydelige hendelsen anser vi at den distribuerte transaksjonen er fullført.
Dermed består konsensusalgoritmen i et enkelt tilfelle av fire trinn: foreslå, stemme (stemme), akseptere (akseptere), bekrefte aksept (akseptert).
Hvis vi på et tidspunkt ikke klarte å komme til enighet, starter algoritmen på nytt, og tar hensyn til informasjonen gitt av nodene som nektet å bekrefte den foreslåtte verdien.
Konsensusalgoritme i et asynkront system
Før dette var alt glatt, fordi vi snakket om en synkron meldingsmodell. Men vi vet at i den moderne verden er vi vant til å gjøre alt asynkront. Hvordan fungerer en lignende algoritme i et system med en asynkron meldingsmodell, der vi mener at ventetiden på svar fra en node kan være vilkårlig lang (forresten, svikt i en node kan også betraktes som et eksempel når en node kan svare i vilkårlig lang tid).
Nå som vi vet hvordan konsensusalgoritmen fungerer i prinsippet, et spørsmål til de nysgjerrige leserne som har kommet så langt: hvor mange noder i et system av N noder med en asynkron meldingsmodell kan svikte slik at systemet fortsatt kan nå konsensus?
Riktig svar og begrunnelse ligger bak spoileren.Det riktige svaret er: 0. Hvis til og med én node i et asynkront system svikter, vil systemet ikke kunne oppnå konsensus. Denne påstanden er bevist i FLP-teoremet, velkjent i visse kretser (1985, Fischer, Lynch, Paterson, lenke til originalen på slutten av artikkelen): «Umuligheten av å oppnå en distribuert konsensus hvis minst én node svikter ."
Gutter, da har vi et problem, vi er vant til at alt er asynkront. Og her er det. Hvordan fortsette å leve?
Vi snakket bare om teori, om matematikk. Hva betyr «konsensus kan ikke oppnås», å oversette fra matematisk språk til vårt - ingeniørkunst? Dette betyr at "ikke alltid kan oppnås", dvs. Det er et tilfelle der konsensus ikke er oppnåelig. Hva slags sak er dette?
Dette er nøyaktig bruddet på liveness-egenskapen beskrevet ovenfor. Vi har ikke en felles avtale, og systemet kan ikke ha fremdrift (kan ikke fullføres på en begrenset tid) i tilfellet hvor vi ikke har respons fra alle noder. For i et asynkront system har vi ingen forutsigbar responstid, og vi kan ikke vite om en node har krasjet eller bare tar lang tid å svare.
Men i praksis kan vi finne en løsning. La vår algoritme være i stand til å fungere lenge i tilfelle feil (potensielt kan den fungere i det uendelige). Men i de fleste situasjoner, når de fleste noder fungerer som de skal, vil vi ha fremgang i systemet.
I praksis har vi å gjøre med delvis synkrone kommunikasjonsmodeller. Delvis synkroni forstås som følger: i det generelle tilfellet har vi en asynkron modell, men et visst begrep om "global stabiliseringstid" for et bestemt tidspunkt er formelt introdusert.
Dette øyeblikket kommer kanskje ikke over lengre tid, men det må komme en dag. Den virtuelle vekkerklokken vil ringe, og fra det øyeblikket kan vi forutsi tidsdeltaet som meldingene kommer til. Fra dette øyeblikket går systemet fra asynkront til synkront. I praksis forholder vi oss til nettopp slike systemer.
Paxos-algoritmen løser konsensusproblemer
er en familie av algoritmer som løser konsensusproblemet for delvis synkrone systemer, med forbehold om at noen noder kan svikte. Forfatteren av Paxos er . Han foreslo et formelt bevis på eksistensen og riktigheten av algoritmen i 1989.
Men beviset viste seg å være langt fra trivielt. Den første publikasjonen ble utgitt først i 1998 (33 sider) som beskriver algoritmen. Som det viste seg, var det ekstremt vanskelig å forstå, og i 2001 ble det publisert en forklaring av artikkelen, som tok 14 sider. Volumet av publikasjoner er gitt for å vise at problemet med konsensus faktisk ikke er enkelt, og bak slike algoritmer ligger en enorm mengde arbeid fra de smarteste menneskene.
Det er interessant at Leslie Lamport selv bemerket i sin forelesning at i den andre forklarende artikkelen er det én påstand, én linje (han spesifiserte ikke hvilken), som kan tolkes på forskjellige måter. Og på grunn av dette fungerer ikke et stort antall moderne Paxos-implementeringer helt korrekt.
En detaljert analyse av Paxos arbeid vil kreve mer enn én artikkel, så jeg vil prøve å kort formidle hovedideen til algoritmen. I lenkene på slutten av artikkelen min finner du materiale for videre dykking i dette emnet.
Roller hos Paxos
Paxos-algoritmen har et rollebegrep. La oss vurdere tre viktigste (det er modifikasjoner med tilleggsroller):
- Forslagsstillere (begrepene kan også brukes: ledere eller koordinatorer). Dette er gutta som lærer om noen nye verdier fra brukeren og tar på seg rollen som leder. Deres oppgave er å lansere en forslagsrunde for en ny verdi og koordinere videre handlinger til nodene. Dessuten tillater Paxos tilstedeværelsen av flere ledere i visse situasjoner.
- Akseptører (Velgere). Dette er noder som stemmer for å godta eller avvise en bestemt verdi. Deres rolle er veldig viktig, fordi beslutningen avhenger av dem: hvilken tilstand systemet vil (eller ikke vil) gå til etter neste trinn av konsensusalgoritmen.
- Learners. Noder som ganske enkelt godtar og skriver den nye aksepterte verdien når tilstanden til systemet har endret seg. De tar ikke beslutninger, de mottar bare dataene og kan gi dem til sluttbrukeren.
En node kan kombinere flere roller i ulike situasjoner.
Konseptet med quorum
Vi antar at vi har et system med N noder Og av dem maksimalt F noder kan mislykkes. Hvis F-noder mislykkes, må vi ha minst 2F+1 akseptornoder.
Dette er nødvendig for at vi alltid skal ha flertallet, selv i den verste situasjonen, av "gode" noder som fungerer riktig. Det er F+1 "gode" noder som stemte, og den endelige verdien vil bli akseptert. Ellers kan det oppstå en situasjon der våre ulike lokallag får ulik betydning og ikke kan bli enige seg imellom. Derfor trenger vi absolutt flertall for å vinne avstemningen.
Den generelle ideen om hvordan Paxos-konsensusalgoritmen fungerer
Paxos-algoritmen involverer to store faser, som igjen er delt inn i to trinn hver:
- Fase 1a: Forbered deg. Under forberedelsesfasen informerer leder (forslagsstiller) alle noder: «Vi starter en ny avstemmingsfase. Vi har en ny runde. Antallet for denne runden er n. Nå begynner vi å stemme." Foreløpig rapporterer den ganske enkelt starten på en ny syklus, men rapporterer ikke en ny verdi. Oppgaven til denne fasen er å starte en ny runde og informere alle om dets unike nummer. Det runde tallet er viktig, det må være en verdi større enn alle tidligere stemmetall fra alle tidligere ledere. Fordi det er takket være det runde tallet at andre noder i systemet vil forstå hvor ferske lederens data er. Det er sannsynlig at andre noder allerede har stemmeresultater fra mye senere runder og ganske enkelt vil fortelle lederen at han er bak tiden.
- Fase 1b: Løfte. Når akseptornodene mottok nummeret til det nye avstemningsstadiet, er to utfall mulig:
- Antallet n for den nye stemmen er større enn tallet på en tidligere stemme der akseptanten deltok. Deretter sender akseptøren et løfte til lederen om at den ikke skal delta i flere stemmer med et tall lavere enn n. Hvis akseptanten allerede har stemt for noe (det vil si at den allerede har akseptert en viss verdi i den andre fasen), så knytter den den aksepterte verdien og nummeret på stemmen den deltok i løftet sitt.
- Ellers, hvis akseptanten allerede vet om den høyere nummererte stemmen, kan den ganske enkelt ignorere forberedelsestrinnet og ikke svare lederen.
- Fase 2a: Godta. Lederen må vente på et svar fra quorumet (flertallet av noder i systemet), og hvis det nødvendige antallet svar mottas, har han to alternativer for utvikling av hendelser:
- Noen av akseptantene sendte verdier som de allerede hadde stemt på. I dette tilfellet velger lederen verdien fra avstemningen med maksimalt antall. La oss kalle denne verdien x, og den sender ut en melding til alle noder som: "Godta (n, x)", der den første verdien er stemmetallet fra sitt eget Foreslå-trinn, og den andre verdien er det alle samlet seg for, dvs. verdien vi faktisk stemmer for.
- Hvis ingen av akseptantene sendte noen verdier, men de bare lovet å stemme i denne runden, kan lederen invitere dem til å stemme for verdien deres, verdien han ble leder for i utgangspunktet. La oss kalle det y. Den sender en melding til alle noder som: "Godta (n, y)", lik det forrige utfallet.
- Fase 2b: Akseptert. Videre er akseptornodene, når de mottar meldingen "Godta(...)" fra lederen, enige i den (send bekreftelse til alle noder om at de er enige i den nye verdien) bare hvis de ikke har lovet noen (annet) ) leder for å delta i avstemningen med runde tall n' > n, ellers ignorerer de bekreftelsesforespørselen.
Hvis flertallet av nodene svarte på lederen, og alle bekreftet den nye verdien, anses den nye verdien som akseptert. Hurra! Hvis flertallet ikke nås eller det er noder som nektet å akseptere den nye verdien, begynner alt på nytt.
Slik fungerer Paxos-algoritmen. Hvert av disse stadiene har mange finesser, vi vurderte praktisk talt ikke ulike typer feil, problemer med flere ledere og mye mer, men formålet med denne artikkelen er bare å introdusere leseren til verden av distribuert databehandling på et høyt nivå.
Det er også verdt å merke seg at Paxos ikke er den eneste i sitt slag, det er andre algoritmer, for eksempel, , men dette er et emne for en annen artikkel.
Lenker til materiell for videre studier
Begynnernivå:
- , Preethi Kasireddy, bloggartikkel om Medium
- , Adi Kancherla, bloggartikkel om Medium
- , Ittai Abraham, blogg
- , Ittai Abraham, bloggartikkel
Leslie Lamport nivå:
- , Fischer, Lynch og Paterson, forskningsartikkel, 1985
- , Leslie Lamport, forskningsartikkel, 1998
- , Leslie Lamport, forskningsartikkel, 2001
Kilde: www.habr.com