Hvordan vi implementerede konsekvent hashing effektivt

Ablys realtime-platform distribueres over mere end 14 fysiske datacentre og 100'erne af noder. For at vi skal sikre, at både belastning og data distribueres jævnt og konsekvent på tværs af alle vores noder, bruger vi konsistente hashing-algoritmer.

I denne artikel forstår vi, hvad konsekvent hashing handler om, og hvorfor det er et vigtigt værktøj i skalerbare distribuerede systemarkitekturer. Desuden skal vi se på datastrukturer, der kan bruges til at implementere denne algoritme effektivt i skala. I slutningen skal vi også se på et fungerende eksempel på det samme.

Hashing revideret igen

Kan du huske den gode gamle naive Hashing-tilgang, som du lærte på college? Ved hjælp af en hash-funktion sørgede vi for, at ressourcer, der kræves af computerprogrammer, kunne lagres i hukommelsen på en effektiv måde, hvilket sikrer, at datastrukturer i hukommelsen indlæses jævnt. Vi sørgede også for, at denne strategi til lagring af ressourcer også gjorde informationsindsamling mere effektiv og dermed fik programmer til at køre hurtigere.

Den klassiske hashing-tilgang anvendte en hash-funktion til at generere et pseudo-tilfældigt tal, der derefter divideres med størrelsen på hukommelsesområdet for at omdanne den tilfældige identifikator til en position inden for den tilgængelige plads. Noget der lignede følgende:

placering = hash (nøgle) mod størrelse

Så hvorfor kan vi ikke bruge den samme metode til håndtering af anmodninger via netværket?

I et scenarie, hvor forskellige programmer, computere eller brugere anmoder om nogle ressourcer fra flere servernoder, har vi brug for en mekanisme til at kortlægge anmodninger jævnt til tilgængelige serverknudepunkter, hvilket sikrer, at belastningen er afbalanceret, og at der kan opretholdes ensartet ydelse. Vi kunne betragte serverknudepunkterne som de pladsholdere, som en eller flere af anmodningerne kan kortlægges til.

Lad os tage et skridt tilbage. I den klassiske hashingmetode antager vi altid, at:

  • Antallet af hukommelsesplaceringer er kendt, og
  • Dette nummer ændres aldrig.

Hos Ably skalerer vi for eksempel rutinemæssigt klyngestørrelsen op og ned hele dagen og er også nødt til at klare uventede fejl. Men hvis vi overvejer scenariet nævnt ovenfor, kan vi ikke garantere, at antallet af serverknudepunkter forbliver det samme. Hvad hvis en af ​​dem uventet mislykkes? Med en naiv hashing-tilgang ville vi ende med at skulle omskifte hver enkelt tast, da den nye kortlægning er afhængig af antallet af noder / hukommelsesplaceringer som vist nedenfor:

FørEfter

Problemet i et distribueret system med simpel omskylning - hvor placeringen af ​​hver tast bevæger sig - er, at der er tilstand gemt på hver node; en lille ændring i klyngestørrelsen for eksempel kan resultere i en enorm mængde arbejde for at blande alle data rundt om klyngen. Når klyngestørrelsen vokser, bliver dette uholdbar, da mængden af ​​arbejde, der kræves for hver hashændring vokser lineært med klyngestørrelsen. Det er her begrebet konsistent hashing kommer ind.

Konsekvent Hashing - hvad er det alligevel?

Konsekvent Hashing kan beskrives som følger:

  • Det repræsenterer ressourceanmodere (som vi fra nu af vil referere til som 'anmodninger' med henblik på dette blogindlæg) og serverknudepunkterne i en eller anden form for en virtuel ringstruktur, kendt som en hashring.
  • Antallet af placeringer er ikke længere fast, men ringen anses for at have et uendeligt antal point, og serverknudepunkterne kan placeres tilfældigt på denne ring. Selvfølgelig kan du vælge dette tilfældige nummer igen ved hjælp af en hash-funktion, men det andet trin med at dele det med antallet af tilgængelige placeringer springes over, da det ikke længere er et endeligt antal.
  • Anmodningerne, dvs. brugere, computere eller serverløse programmer, der er analoge med nøgler i klassisk hashing-tilgang, placeres også på den samme ring ved hjælp af den samme hash-funktion.

Så hvordan er beslutningen om, hvilken anmodning der serveres af den servernode, der er foretaget? Hvis vi antager, at ringen er ordnet, så ringens retning med uret svarer til en stigende rækkefølge af placeringsadresser, kan hver anmodning serveres af den serverknudepunkt, der først vises i denne medurs retning; det vil sige, at den første serverknude med en adresse, der er større end adressen på anmodningen, serverer den. Hvis adressen på anmodningen er højere end den højeste adressede knude, serveres den af ​​serverknuden med den mindst adresse, da gennemgangen gennem ringen går cirkulært. Dette illustreres nedenfor:

Teoretisk set ejer hver serverknudepunkt et område af hashring, og alle anmodninger, der kommer ind i dette interval, vil blive betjent af den samme serverknudepunkt. Hvad nu, hvis en af ​​disse serverknudepunkter mislykkes, siger Node 3, rækkevidden for den næste serverknude udvides og enhver anmodning, der kommer i hele dette interval, går til den nye serverknude. Men det er det. Det er netop dette område, der svarer til den mislykkede serverknudepunkt, der skulle tildeles igen, mens resten af ​​hashring- og anmodningsnode-tildelinger stadig ikke påvirkes. Dette i modsætning til den klassiske hashing-teknik, hvor ændringen i størrelsen på hashbordet effektivt forstyrrer ALLE kortlægninger. Takket være konstant hashing vil kun en del (i forhold til ringfordelingsfaktoren) af anmodningerne blive påvirket af en given ringændring. (En ringændring forekommer på grund af en tilføjelse eller fjernelse af en node, der får nogle af anmodningsknudepartierne til at ændre sig.)

En effektiv implementeringsmetode

Nu hvor vi er tilpas med, hvad en hashring er ...

Vi er nødt til at implementere følgende for at få det til at fungere:

  1. En kortlægning fra vores hashrum til knudepunkter i klyngen, så vi kan finde de knudepunkter, der er ansvarlige for en given anmodning.
  2. En samling af disse anmodninger til klyngen, der løses til en given knude. Når vi bevæger os fremad, vil dette give os mulighed for at finde ud af, hvilke hashes, der er påvirket af tilføjelsen eller fjernelsen af ​​en bestemt knude.

Kortlægning

For at gennemføre den første del ovenfor, har vi brug for følgende:

  • En hashfunktion til beregning af positionen i ringen givet en identifikator for anmodninger.
  • En måde at finde ud af, hvilken knude der svarer til en hashed-anmodning.

For at finde ud af noden, der svarer til en bestemt anmodning, kan vi bruge en simpel datastruktur til dets repræsentation, der består af følgende:

  • En række hasjer, der svarer til knudepunkter i ringen.
  • Et kort (hash-tabel) til at finde den node, der svarer til en bestemt anmodning.

Dette er i det væsentlige en primitiv repræsentation af et bestilt kort.

For at finde en knude, der er ansvarlig for en given hash i ovenstående struktur, er vi nødt til at:

  • Udfør en modificeret binær søgning for at finde den første node-hash i den matrix, der er lig med eller større end (≥) den hash, du ønsker at slå op.
  • Slå op noden svarende til den fundne node-hash på kortet

Tilføjelse eller fjernelse af en node

Som vi så i begyndelsen af ​​artiklen, når en ny knude tilføjes, skal en del af hashringen, der består af forskellige anmodninger, tildeles denne knude. Omvendt, når en node fjernes, skal de anmodninger, der blev tildelt den knude, håndteres af en anden knude.

Hvordan finder vi de anmodninger, der er berørt af en ringændring?

En løsning er at itereere alle de anmodninger, der er tildelt en knude. For hver anmodning beslutter vi, om det falder inden for rammerne af den ringændring, der er sket, og flytter den et andet sted, hvis det er nødvendigt.

Dog kræves det arbejde, der kræves for at gøre dette, efterhånden som antallet af anmodninger, der er tildelt til en given knudepunkt. Situationen bliver værre, da antallet af ringændringer, der opstår, har tendens til at stige, når antallet af knuder stiger. I ringeste tilfælde, da ringændringer ofte er relateret til lokaliserede fejl, kan en øjeblikkelig belastning, der er forbundet med en ringændring, også øge sandsynligheden for andre berørte knudepunkter, hvilket muligvis kan føre til sammenhængende problemer i hele systemet.

For at imødegå dette, ønsker vi, at flytningen af ​​anmodninger skal være så effektiv som muligt. Ideelt set gemmer vi alle anmodninger i en datastruktur, der giver os mulighed for at finde dem, der er berørt af en enkelt hashændring hvor som helst på ringen

Effektivt at finde berørte hash

Tilføjelse eller fjernelse af en node fra klyngen vil ændre tildelingen af ​​anmodninger i en del af ringen, som vi vil referere til som det berørte område. Hvis vi kender grænserne for det berørte område, vil vi være i stand til at flytte anmodningerne til deres korrekte placering.

For at finde grænserne for det berørte område ved at starte ved hash H for den tilføjede eller fjernede knude kan vi bevæge sig bagud (mod uret i diagrammet) rundt om ringen fra H, indtil en anden knude findes. Lad os kalde hash for denne knude S (til start). De anmodninger, der er mod uret fra denne node, placeres for den, så de vil ikke blive berørt.

Bemærk, at dette er en forenklet skildring af, hvad der sker; i praksis er strukturen og algoritmen yderligere kompliceret, fordi vi bruger replikationsfaktorer på større end, 1 og specialiserede replikationsstrategier, hvor kun en delmængde af noder er anvendelig til enhver given anmodning.

De anmodninger, der har placeringshasjer i området mellem den fundne knude og den knude, der blev tilføjet (eller fjernet), er dem, der skal flyttes.

Effektivt at finde anmodningerne i det berørte område

En løsning er simpelthen at itereere gennem alle anmodninger, der svarer til en knude, og opdatere dem, der har en hash inden for området.

I JavaScript der kan se sådan ud:

for (const anmodning om anmodninger) {
  hvis (indeholder (S, H, request.hash)) {
    / * anmodningen påvirkes af ændringen * /
    request.relocate ();
  }
}
funktionen indeholder (lavere bund, øvre kant, hash) {
   const wrapsOver = upperBound 
   const aboveLower = hash> = lowBound;
   const belowUpper = upperBound> = hash;
   if (wrapsOver) {
     tilbage over lavere || belowUpper;
   } andet {
     vende tilbage nederst && nedenforUpper;
   }
}

Da ringen er cirkulær, er det ikke nok bare at finde forespørgsler, hvor S <= r

Iterering gennem alle anmodninger på en given knude er fint, så længe antallet af anmodninger er relativt lavt, eller hvis tilføjelse eller fjernelse af knudepunkter er relativt sjældent.

Imidlertid stiger det krævede arbejde, når antallet af forespørgsler ved en given knude vokser, og værre er, ringændringer har en tendens til at forekomme oftere, når antallet af knudepunkter stiger, hvad enten det skyldes automatisk skalering eller failover, hvilket udløser samtidig belastning over systemet til at rebalance anmodningerne.

I værste tilfælde kan belastning, der er forbundet med dette, øge sandsynligheden for fejl på andre knudepunkter, muligvis føre til sammenhængende problemer i hele systemet.

For at afbøde dette kan vi også gemme anmodninger i en separat ringedatasstruktur svarende til den, der er omtalt tidligere. I denne ring kortlægger en hash direkte til den anmodning, der er placeret ved den hash.

Derefter kan vi finde anmodningerne inden for et interval ved at gøre følgende:

  • Find den første anmodning efter starten af ​​intervallet, S.
  • Iterer med uret, indtil du finder en anmodning, der har en hash uden for rækkevidden.
  • Flyt de anmodninger, der var inden for området.

Antallet af anmodninger, der skal gentages for en given hash-opdatering, vil i gennemsnit være R / N, hvor R er antallet af anmodninger, der er placeret i området for noden og N er antallet af hash i ringen, under forudsætning af en jævn fordeling af anmodninger.

Lad os omsætte ovenstående forklaring til handling med et fungerende eksempel:

Antag, at vi har en klynge, der indeholder to knudepunkter A og B.

Lad os generere tilfældigt en 'placering hash' for hver af disse noder: (forudsat at 32-bit hash), så vi får

A: 0x5e6058e5

B: 0xa2d65c0

Dette placerer knudepunkterne på en imaginær ring, hvor numrene 0x0, 0x1, 0x2… er placeret fortløbende op til 0xffffffff, som igen er krøllet for at blive efterfulgt af 0x0.

Da knudepunkt A har hash 0x5e6058e5, er det ansvarligt for enhver anmodning, der hashes inden for området0xa2d65c0 + 1 op til 0xffffffff og fra 0x0 op til 0x5e6058e5, som vist nedenfor:

B på den anden side er ansvarlig for området0x5e6058e5 + 1up til 0xa2d65c0. Således fordeles hele hashrummet.

Denne kortlægning fra noder til deres hash skal deles med hele klyngen, så resultatet af ringberegningen altid er det samme. Enhver knude, der kræver en bestemt anmodning, kan således bestemme, hvor den bor

Lad os sige, at vi vil finde (eller oprette) en anmodning, der har identifikatoren '[email protected]'.

  1. Vi beregner en hash H for identifikatoren, siger 0x89e04a0a
  2. Vi ser på ringen og finder den første knude med en hash, der er større end H. Her sker der tilfældigvis B.

Derfor er B den knudepunkt, der er ansvarlig for denne anmodning. Hvis vi har brug for anmodningen igen, gentager vi ovenstående trin og lander igen på den samme knude, som har den tilstand, vi har brug for.

Dette eksempel er lidt forenklet. I virkeligheden vil det at have en enkelt hash for hver knude sandsynligvis fordele belastningen ganske uretfærdigt. Som du måske har bemærket, er B i dette eksempel ansvarlig for (0xa2d656c0-0x5e6058e5) / 232 = 26,7% af ringen, mens A er ansvarlig for resten. Ideelt set vil hver knude være ansvarlig for en lige stor del af ringen.

En måde at gøre dette mere retfærdigt på er at generere flere tilfældige hascher for hver node, som nedenfor:

I virkeligheden finder vi, at resultaterne af dette stadig er utilfredsstillende, så vi opdeler ringen i 64 lige store størrelser og sikrer, at en hash for hver knude er placeret et sted i hvert segment; detaljerne herom er imidlertid ikke vigtige. Målet er bare at sikre, at hver knude er ansvarlig for en lige stor del af ringen, så belastningen er jævnt fordelt. (En anden fordel ved at have flere hasjer for hver knude er, at hasherne kan føjes til eller fjernes fra ringen gradvist for at undgå pludselige spidser af belastning.)

Antag, at vi nu tilføjer en ny knude til ringen kaldet C. Vi genererer en tilfældig hash til C.

A: 0x5e6058e5

B: 0xa2d65c0

C: 0xe12f751c

Nu er ringepladsen mellem 0xa2d65c0 + 1 og 0xe12f751c (som plejede at hash til A) nu delegeret til C. Alle de andre anmodninger fortsætter med at hash til den samme knude som før. For at håndtere dette magtskifte skal alle anmodninger i det interval, der allerede findes på A, flytte al deres tilstand til C.

Du forstår nu, hvorfor hashing er nødvendigt i distribuerede systemer for at fordele belastningen jævnt. Konsistent hashing er dog påkrævet for at sikre minimering af det nødvendige arbejde i klyngen, når der sker en ringændring.

Derudover skal der findes noder på flere placeringer på ringen for at statistisk sikre, at belastningen mere sandsynligt bliver distribueret mere jævnt. Iterering af en hel hashring for hver ringændring er ineffektiv. Når dit distribuerede system skalerer, er det nødvendigt at have en mere effektiv måde at bestemme, hvad der er ændret, for at minimere ydelseseffekten af ​​ringændringer så meget som muligt. Nye indekser og datatyper er nødvendige for at løse dette.

Det er svært at opbygge distribuerede systemer. Vi elsker det, og vi elsker at chatte om. Brug Ably, hvis du har brug for en. Hvis du vil chatte, skal du række ud!

Tak til John Diamond, Distribueret systemingeniør hos Ably, for hans input til denne artikel.

Srushtika er en advokat for Ably Realtime