Konsekvent hashning

Inom datavetenskap är konsekvent hashning en speciell typ av hashteknik så att när en hashtabell ändras, behöver endast $displaystyle n/m}$ \ nycklar i genomsnitt ommappas där $n$ är numret av nycklar och $m$ är antalet platser. I motsats till detta, i de flesta traditionella hash-tabeller, gör en förändring i antalet arrayslots att nästan alla nycklar ommappas eftersom mappningen mellan nycklarna och luckorna definieras av en modulär operation .

Historia

Termen "konsekvent hashning" introducerades av David Karger et al. vid MIT för användning i distribuerad cachning , särskilt för webben . Denna akademiska uppsats från 1997 i Symposium on Theory of Computing introducerade termen "konsekvent hashing" som ett sätt att distribuera förfrågningar bland en föränderlig population av webbservrar. Varje plats representeras sedan av en server i ett distribuerat system eller kluster. Tillägget av en server och borttagningen av en server (under skalbarhet eller avbrott) kräver endast $num\_keys/num\_slots$ objekt för att blandas om när antalet platser (dvs. servrar) ändras. Författarna nämner linjär hashing och dess förmåga att hantera sekventiell servertillägg och borttagning, medan konsekvent hashning gör att servrar kan läggas till och tas bort i en godtycklig ordning. Uppsatsen användes senare för att ta itu med den tekniska utmaningen att hålla reda på en fil i peer-to-peer-nätverk som en distribuerad hashtabell .

Teradata använde denna teknik i sin distribuerade databas, som släpptes 1986, även om de inte använde denna term. Teradata använder fortfarande konceptet med en hashtabell för att uppfylla exakt detta syfte. Akamai Technologies grundades 1998 av forskarna Daniel Lewin och F. Thomson Leighton (medförfattare till artikeln som myntade "consistent hashing"). I Akamais nätverk för innehållsleverans används konsekvent hashning för att balansera belastningen inom ett kluster av servrar, medan en stabil äktenskapsalgoritm används för att balansera belastningen över kluster.

Konsekvent hashning har också använts för att minska effekten av partiella systemfel i stora webbapplikationer för att tillhandahålla robust cachelagring utan att orsaka det systemomfattande nedfallet av ett fel. Konsekvent hashning är också hörnstenen i distribuerade hashtabeller (DHT), som använder hashvärden för att partitionera ett nyckelutrymme över en distribuerad uppsättning noder, och sedan konstruera ett överläggsnätverk av anslutna noder som ger effektiv nodhämtning per nyckel.

Rendezvous hashing , designad 1996, är en enklare och mer allmän teknik . Den uppnår målen med konsekvent hashning med den mycket olika algoritmen med högsta slumpmässiga vikt (HRW).

Grundläggande teknik

I detta fall skulle användning av konsekvent hash resultera i att "BLOB" får lagrad server 139. En BLOB mappas till nästa server som visas på cirkeln i medursordning tills den når en server som är ζ ≤ server ID $\ zeta \leq {\text{server-ID}}}$

I problemet med lastbalansering , till exempel, när en BLOB måste tilldelas en av $n$ servrar på ett kluster , kan en standardhashfunktion användas på ett sådant sätt att vi beräknar hashvärdet för det BLOB, förutsatt att det resulterande värdet av hashen är $\beta$ , utför vi modulär operation med antalet servrar ( $n$ i det här fallet) för att bestämma servern där vi kan placera BLOB: $\zeta =\beta \ \%\ n$ ; därför kommer BLOB att placeras i servern vars ${\text{server-ID}}$ är efterföljaren till $\zeta$ i detta fall. Men när en server läggs till eller tas bort under avbrott eller skalning (när $n$ ändras), bör alla BLOBs i varje server omtilldelas och flyttas på grund av omhasning , men denna operation är dyr.

Konsekvent hashning utformades för att undvika problemet med att behöva tilldela varje BLOB när en server läggs till eller tas bort i hela klustret. Den centrala idén är att vi använder en hashfunktion som slumpmässigt mappar både BLOB och servrar till en enhetscirkel, vanligtvis $2\pi$ radianer. Till exempel, $\zeta =\Phi \ \%\ 360$ (där $\Phi$ är hash av en BLOB eller serverns identifierare, som IP-adress eller UUID ). Varje BLOB tilldelas sedan till nästa server som visas på cirkeln i medurs ordning. Vanligtvis används binär sökalgoritm eller linjär sökning för att hitta en "punkt" eller server för att placera den specifika BLOB i $O(\log N)$ eller $O( N)$ respektive komplexitet; och i varje iteration, som sker medurs, utförs en operation $\zeta \ \leq \ \Psi$ (där $\Psi$ är värdet på servern i klustret) för att hitta servern för att placera BLOB. Detta ger en jämn fördelning av BLOB till servrar. Men ännu viktigare, om en server misslyckas och tas bort från cirkeln, behöver bara de BLOB som mappades till den misslyckade servern omfördelas till nästa server i medursordning. På samma sätt, om en ny server läggs till, läggs den till i enhetscirkeln, och endast BLOB:erna som är mappade till den servern behöver omtilldelas.

Viktigt, när en server läggs till eller tas bort, behåller den stora majoriteten av BLOB:arna sina tidigare servertilldelningar, och tillägget av $n^{th}$ server orsakar bara $1/n$ bråkdel av BLOB:erna som ska flyttas. Även om processen att flytta BLOB:ar över cacheservrar i klustret beror på sammanhanget, identifierar den nyligen tillagda cacheservern sin "efterträdare" och flyttar alla BLOB:er vars mappning tillhör denna server (dvs. vars hashvärde är mindre än det av den nya servern), från den. Men i fallet med webbsidescachar är det i de flesta implementeringar ingen inblandning i att flytta eller kopiera, förutsatt att den cachade BLOB är tillräckligt liten. När en förfrågan träffar en nyligen tillagd cacheserver inträffar en cachemiss och en begäran till den faktiska webbservern görs och BLOB:en cachelagras lokalt för framtida förfrågningar. De redundanta BLOB:arna på de tidigare använda cacheservrarna skulle tas bort enligt cache-eviction-policyerna .

Genomförande

Låt $h_{b}(x)$ och $h_{s}(x)$ vara hashfunktionerna som används för BLOB respektive serverns unika identifierare. I praktiken används ett binärt sökträd (BST) för att dynamiskt upprätthålla ${\text{server-ID}}$ inom ett kluster eller hashring, och för att hitta efterföljaren eller minimum inom BST, är trädgenomgången Begagnade.

Infoga $x$ i klustret

Låt $\beta$ vara hashvärdet för en BLOB så att, $h_{b}(x)=\beta \ \%\ 360$ där $x\in \mathrm {BLOB}$ och $h_{b}(x)=\zeta$ . För att infoga $x$ , hitta efterföljaren till $\zeta$ i BST för ${\text{server-ID}}$ s. Om $\zeta$ är större än alla ${\text{server-ID}}$ s, placeras BLOB i servern med minsta ${\text{server-ID }}$ värde.

Ta bort $x$ från klustret

Hitta efterföljaren till $\zeta$ i BST, ta bort BLOB från det returnerade ${\text{server-ID}}$ . Om $\zeta$ inte har någon efterföljare, ta bort BLOB från det minsta av ${\text{server-ID}}$ s.

Infoga en server i klustret

Låt $\Phi$ vara hashvärdet för en servers identifierare så att $h_{s}(x)=\Phi \ \%\ 360$ där $x\in \{{\text{IP-adress, UUID}}\}$ och $h_{s}(x) =\theta$ . Flytta alla BLOB, vars hashvärde är mindre än $\theta$ , från servern vars ${\text{server-ID}}$ är efterföljaren till $\theta$ . Om $\theta$ är störst av alla ${\displaystyle {\text{server-ID}}},$ flytta de relevanta BLOB:erna från den minsta av $:t {\displaystyle {\text{server-ID} }}$ s till $\theta$ .

Ta bort en server från klustret

Hitta efterföljaren till $\theta$ i BST, flytta BLOB från $\theta$ till dess efterföljande server. Om $\theta$ inte har en efterföljare, flytta BLOB:erna till det minsta av ${\text{server-ID}}$ s.

Variansminskning

För att undvika skevhet av flera noder inom radianen, vilket sker på grund av bristande slumpmässighet i distributionen av servrarna inom klustret, används flera etiketter. Dessa dubbletter av etiketter kallas "virtuella noder", dvs flera etiketter som pekar på en enda "riktig" etikett eller server i klustret. Mängden virtuella noder eller dubbletter av etiketter som används för en viss server inom ett kluster kallas "vikten" för den specifika servern.

Praktiska tillägg

Ett antal tillägg till den grundläggande tekniken behövs för att effektivt använda konsekvent hashning för lastbalansering i praktiken. I det grundläggande schemat ovan, om en server misslyckas, tilldelas alla dess BLOB:er till nästa server i medursordning, vilket potentiellt fördubblar belastningen på den servern. Detta kanske inte är önskvärt. För att säkerställa en jämnare omfördelning av BLOB vid serverfel, kan varje server hashas till flera platser i enhetscirkeln. När en server misslyckas kommer BLOB:erna som är tilldelade till var och en av dess repliker på enhetscirkeln att omtilldelas till en annan server i medursordning, vilket omfördelar BLOB:erna mer jämnt. En annan förlängning gäller en situation där en enda BLOB blir "het" och nås ett stort antal gånger och måste finnas på flera servrar. I denna situation kan BLOB tilldelas flera angränsande servrar genom att korsa enhetscirkeln i medurs ordning. En mer komplex praktisk övervägande uppstår när två BLOB:s hashas nära varandra i enhetscirkeln och båda blir "heta" samtidigt. I det här fallet kommer båda BLOB:arna att använda samma uppsättning sammanhängande servrar i enhetscirkeln. Denna situation kan förbättras genom att varje BLOB väljer en annan hashfunktion för att mappa servrar till enhetscirkeln.

Jämförelse med Rendezvous Hashing och andra alternativ

Rendezvous-hashning , designad 1996, är en enklare och mer allmän teknik och tillåter fullständigt distribuerad överenskommelse om en uppsättning $k$ -alternativ av en möjlig uppsättning av $n$ -alternativ. Det kan faktiskt visas att konsekvent hashning är ett specialfall av rendezvous-hashing. På grund av dess enkelhet och allmänhet används nu Rendezvous Hashing istället för Consistent Hashing i många applikationer.

Om nyckelvärden alltid kommer att öka monotont kan ett alternativt tillvägagångssätt med en hashtabell med monotona nycklar vara mer lämplig än konsekvent hashning.

Komplexitet

Asymptotisk tidskomplexitet för $N$ -noder (eller slots) och $K$ -nycklar

	Klassiskt hashbord	Konsekvent hashning
lägg till en nod	$O(K)$	$O(K/N+\log N)$
ta bort en nod	$O(K)$	$O(K/N+\log N)$
lägg till en nyckel	$O(1)$	$O(\log N)$
ta bort en nyckel	$O(1)$	$O(\log N)$

O $O(K/N)$ är en genomsnittlig kostnad för omfördelning av nycklar och ${\displaystyle O(\log N)}-$ för konsekvent hashning kommer från faktum att en binär sökning bland nodvinklar krävs för att hitta nästa nod på ringen.

Exempel

Kända exempel på konsekvent hashing är:

• Couchbase automatiserad datapartitionering
• OpenStacks objektlagringstjänst Swift
• Partitioneringskomponent i Amazons lagringssystem Dynamo
• Datapartitionering i Apache Cassandra
• Datapartitionering i Voldemort
• Akkas konsekventa hash-router
• Riak , en distribuerad nyckel-värdedatabas
• Gluster , ett nätverksanslutet lagringsfilsystem
• Akamais nätverk för leverans av innehåll
• Discord chat-applikation
• Ackordalgoritm _

• Roughgarden, Tim; Valiant, Gregory (28 mars 2021). "Den moderna algoritmiska verktygslådan, introduktion till konsekvent hashing" (PDF) . Stanford University . Arkiverad (PDF) från originalet den 25 juli 2021 . Hämtad 7 oktober 2021 .
• Moitra, Ankur (10 februari 2016). "Avancerade algoritmer, 6.854" (PDF) . Massachusetts Institute of Technology . Arkiverad (PDF) från originalet den 13 april 2021 . Hämtad 8 oktober 2021 .

externa länkar

• Förstå konsekvent hashning
• Konsekvent hashning av Michael Nielsen den 3 juni 2009
• Konsekvent Hashing, Danny Lewin och skapandet av Akamai
• Jump Consistent Hashing: En snabb, minimalt minne, konsekvent hashalgoritm
• Rendezvous Hashing: ett alternativ till Consistent Hashing
• Implementeringar på olika språk:
  • C
  • C++
  • C#
  • Erlang
  • Gå
  • Java
  • PHP
  • Rubin
  • Pytonorm
  • Python (igen)
  • Perl
  • Perl6