V posledních letech s nástupem konceptů, jako jsou cloud computing a big data, získaly distribuované systémy na popularitě a významu.
Jeden z takových typů systémů, distribuované cache, které pohánějí mnoho dynamických webových stránek a webových aplikací s vysokou návštěvností, se obvykle skládá z konkrétního případu distribuovaného hašování. Ty využívají algoritmus známý jako konzistentní hashování.
Co je to konzistentní hashování? Jaká je jeho motivace a proč byste se o něj měli zajímat?
V tomto článku nejprve přiblížím obecný koncept hashování a jeho účel, následovat bude popis distribuovaného hashování a problémů s ním spojených. To nás následně dovede k našemu titulnímu tématu.
Co je to hašování?
Co je to vlastně „hašování“? Merriam-Webster definuje podstatné jméno hash jako „nasekané maso smíchané s brambory a opečené“ a sloveso jako „nakrájet (jako maso a brambory) na malé kousky“. Pomineme-li tedy kulinářské detaily, hash zhruba znamená „nasekat a smíchat“ – a právě odtud pochází technický termín.
Hashovací funkce je funkce, která mapuje jednu část dat – obvykle popisující nějaký objekt, často libovolné velikosti – na jinou část dat, obvykle celé číslo, známé jako hashovací kód nebo prostě hash.
Například nějaká hašovací funkce určená k hašování řetězců s výstupním rozsahem 0 .. 100 může mapovat řetězec Hello například na číslo 57, Hasta la vista, baby na číslo 33 a jakýkoli jiný možný řetězec na nějaké číslo v tomto rozsahu. Protože možných vstupů je mnohem více než výstupů, bude na libovolné číslo namapováno mnoho různých řetězců, což je jev známý jako kolize. Dobré hašovací funkce by měly vstupní data nějak „rozsekat a promíchat“ (odtud termín) tak, aby výstupy pro různé vstupní hodnoty byly co nejrovnoměrněji rozloženy po celém výstupním rozsahu.
Hašovací funkce mají mnoho použití a pro každé z nich mohou být požadovány jiné vlastnosti. Existuje typ hashovacích funkcí známý jako kryptografické hashovací funkce, které musí splňovat omezený soubor vlastností a používají se pro bezpečnostní účely – mimo jiné pro aplikace, jako je ochrana hesel, kontrola integrity a otisků zpráv a detekce poškození dat, ale ty jsou mimo rozsah tohoto článku.
Nekryptografické hašovací funkce mají také několik použití, z nichž nejčastější je jejich použití v hašovacích tabulkách, což je právě to, které nás zajímá a které prozkoumáme podrobněji.
Představení hašovacích tabulek (hašovacích map)
Představte si, že bychom potřebovali vést seznam všech členů nějakého klubu a zároveň mít možnost vyhledat nějakého konkrétního člena. Mohli bychom to řešit tak, že bychom tento seznam uchovávali v poli (nebo ve spojovém seznamu) a pro vyhledávání bychom iterovali jednotlivé prvky, dokud bychom nenašli požadovaného člena (mohli bychom například hledat na základě jeho jména). V nejhorším případě by to znamenalo zkontrolovat všechny členy (pokud je hledaný člen poslední nebo se vůbec nevyskytuje) nebo v průměru polovinu z nich. Z hlediska teorie složitosti by pak hledání mělo složitost O(n) a pro malý seznam by bylo poměrně rychlé, ale bylo by stále pomalejší a pomalejší přímo úměrně počtu členů.
Jak by se to dalo zlepšit? Předpokládejme, že všichni tito členové klubu mají ID, což je shodou okolností pořadové číslo odrážející pořadí, v jakém do klubu vstoupili.
Pokud by vyhledávání podle ID bylo přijatelné, mohli bychom všechny členy umístit do pole, přičemž jejich indexy by odpovídaly jejich ID (například člen s ID=10 by byl v poli na indexu 10). To by nám umožnilo přistupovat ke každému členu přímo, bez jakéhokoli vyhledávání. To by bylo velmi efektivní, vlastně tak efektivní, jak jen může být, což odpovídá nejnižší možné složitosti O(1), známé také jako konstantní čas.
Ale je třeba přiznat, že náš scénář s členem klubu ID je poněkud vymyšlený. Co kdyby ID byla velká, nesekvenční nebo náhodná čísla? Nebo kdyby vyhledávání podle ID nebylo přijatelné a místo toho bychom potřebovali vyhledávat podle jména (nebo jiného pole)? Určitě by bylo užitečné zachovat náš rychlý přímý přístup (nebo něco blízkého) a zároveň být schopen pracovat s libovolnými soubory dat a méně omezujícími kritérii vyhledávání.
Tady přicházejí na pomoc hashovací funkce. Vhodnou hashovací funkci lze použít k namapování libovolného kusu dat na celé číslo, které bude hrát podobnou roli jako náš člen klubu ID, i když s několika důležitými rozdíly.
Předně, dobrá hashovací funkce má obecně široký výstupní rozsah (typicky celý rozsah 32 nebo 64bitového celého čísla), takže budování pole pro všechny možné indexy by bylo buď nepraktické, nebo prostě nemožné a znamenalo by kolosální plýtvání pamětí. Abychom to překonali, můžeme mít rozumně velké pole (řekněme jen dvojnásobek počtu prvků, které předpokládáme uložit) a provést operaci modulo na hash, abychom získali index pole. Takže index by byl index = hash(object) mod N, kde N je velikost pole.
Druhé, hashe objektů nebudou unikátní (pokud nepracujeme s pevnou datovou sadou a vlastní dokonalou hashovací funkcí, ale o tom zde nebudeme diskutovat). Bude docházet ke kolizím (ještě zvýšeným operací modulo), a proto prostý přímý přístup k indexu nebude fungovat. Existuje několik způsobů, jak se s tím vypořádat, ale typickým je připojit ke každému indexu pole seznam, běžně známý jako kbelík, který bude obsahovat všechny objekty sdílející daný index.
Máme tedy pole o velikosti N, přičemž každá položka ukazuje na kbelík s objekty. Chceme-li přidat nový objekt, musíme vypočítat jeho hash modulo N a zkontrolovat kbelík na výsledném indexu a přidat objekt, pokud tam ještě není. Chceme-li objekt vyhledat, postupujeme stejně, jen se podíváme do kbelíku a zkontrolujeme, zda se tam objekt nachází. Taková struktura se nazývá hašovací tabulka, a přestože vyhledávání v rámci kyblíků je lineární, správně dimenzovaná hašovací tabulka by měla mít přiměřeně malý počet objektů na kyblík, což vede k téměř konstantnímu času přístupu (průměrná složitost O(N/k), kde k je počet kyblíků).
U složitých objektů se hašovací funkce obvykle neaplikuje na celý objekt, ale místo toho na klíč. V našem příkladu člena klubu může každý objekt obsahovat několik polí (například jméno, věk, adresu, e-mail, telefon), ale jako klíč bychom mohli vybrat například e-mail, takže hashovací funkce by se aplikovala pouze na e-mail. Klíč ve skutečnosti nemusí být součástí objektu; běžně se ukládají dvojice klíč/hodnota, kde klíčem je obvykle relativně krátký řetězec a hodnotou může být libovolný údaj. V takových případech se hashovací tabulka nebo hashovací mapa používá jako slovník a tímto způsobem některé vysokoúrovňové jazyky implementují objekty nebo asociativní pole.
Scaling Out:
V některých situacích může být nutné nebo žádoucí rozdělit hashovací tabulku na několik částí, které jsou umístěny na různých serverech. Jednou z hlavních motivací je obejít paměťová omezení plynoucí z použití jediného počítače a umožnit konstrukci libovolně velkých hašovacích tabulek (při dostatečném počtu serverů).
V takovém případě jsou objekty (a jejich klíče) rozděleny mezi několik serverů, odtud také název.
Typickým případem použití je implementace mezipaměti, například Memcached.
Taková nastavení se skládají z fondu mezipaměťových serverů, které hostí mnoho dvojic klíč/hodnota a slouží k rychlému přístupu k datům původně uloženým (nebo vypočteným) jinde. Aby se například snížilo zatížení databázového serveru a zároveň se zvýšil výkon, může být aplikace navržena tak, že nejprve načte data z cachovacích serverů, a teprve pokud tam nejsou přítomna – situace známá jako chybějící cache – se vrátí do databáze, spustí příslušný dotaz a výsledky uloží do mezipaměti s příslušným klíčem, aby je bylo možné najít, až budou příště potřeba.
Jak tedy probíhá distribuce? Podle jakých kritérií se určuje, které klíče se umístí na které servery?
Nejjednodušší způsob je vzít hash modulo počtu serverů. Tedy server = hash(key) mod N, kde N je velikost fondu. Pro uložení nebo načtení klíče klient nejprve vypočítá hash, použije operaci modulo N a pomocí výsledného indexu kontaktuje příslušný server (pravděpodobně pomocí vyhledávací tabulky IP adres). Všimněte si, že hashovací funkce použitá pro distribuci klíčů musí být stejná u všech klientů, ale nemusí být stejná jako ta, kterou interně používají servery mezipaměti.
Podívejme se na příklad. Řekněme, že máme tři servery, A, B a C, a máme nějaké řetězcové klíče s jejich hash:
| KEY | HASH | HASH mod 3 |
|---|---|---|
| „john“ | 1633428562 | 2 |
| „bill“ | 7594634739 | 0 |
| „jane“ | 5000799124 | 1 |
| „steve“ | 9787173343 | 0 |
| „kate“ | 3421657995 | 2 |
Klient chce získat hodnotu pro klíč john. Jeho hash modulo 3 je 2, takže musí kontaktovat server C. Klíč se tam nenachází, proto klient načte data ze zdroje a přidá je. Fond vypadá takto:
| A | B | C |
|---|---|---|
| „john“ |
Další klient (nebo tentýž) chce získat hodnotu pro klíč bill. Jeho hash modulo 3 je 0, takže musí kontaktovat server A. Klíč tam nenajde, takže klient načte data ze zdroje a přidá je. Fond nyní vypadá takto:
| A | B | C |
|---|---|---|
| „bill“ | „john“ |
Po přidání zbylých klíčů vypadá fond takto:
| A | B | C |
|---|---|---|
| „bill“ | „jane“ | „john“ |
| „steve“ | „kate“ |
Problém rehashingu
Toto distribuční schéma je jednoduché, intuitivní a funguje dobře. Tedy dokud se nezmění počet serverů. Co se stane, když jeden ze serverů zkolabuje nebo se stane nedostupným? Klíče je samozřejmě třeba přerozdělit, aby se zohlednil chybějící server. Totéž platí, pokud se do fondu přidá jeden nebo více nových serverů; klíče je třeba přerozdělit tak, aby zahrnovaly nové servery. To platí pro jakékoliv distribuční schéma, ale problém s naší jednoduchou modulovou distribucí spočívá v tom, že když se změní počet serverů, změní se i většina hashes modulo N, takže většinu klíčů bude třeba přesunout na jiný server. Takže i když dojde k odebrání nebo přidání jediného serveru, bude pravděpodobně nutné všechny klíče přesunout na jiný server.
Z našeho předchozího příkladu vyplývá, že pokud bychom odstranili server C, museli bychom všechny klíče přehashovat pomocí hash modulo 2 místo hash modulo 3 a nová umístění klíčů by se stala:
| KEY | HASH | HASH mod 2 |
|---|---|---|
| „john“ | 1633428562 | 0 |
| „bill“ | 7594634739 | 1 |
| „Jane“ | 5000799124 | 0 |
| „Steve“ | 9787173343 | 1 |
| „kate“ | 3421657995 | 1 |
| A | B |
|---|---|
| „John“ | „bill“ |
| „Jane“ | „Steve“ |
| „Kate“ |
Všimněte si, že všechna klíčová místa se změnila, nejen ty ze serveru C.
V typickém případě použití, o kterém jsme se zmínili dříve (ukládání do mezipaměti), by to znamenalo, že najednou klíče nebudou nalezeny, protože se ještě nebudou nacházet na svém novém umístění.
Většina dotazů tedy povede k chybějícím údajům a původní data bude pravděpodobně nutné znovu načíst ze zdroje, aby byla znovu uložena, čímž dojde k velkému zatížení původních serverů (typicky databáze). To může velmi výrazně snížit výkon a případně způsobit pád původních serverů.
Řešení: Konzistentní kódování (Consistent Hashing)
Jak tedy tento problém vyřešit? Potřebujeme distribuční schéma, které není přímo závislé na počtu serverů, aby se při přidávání nebo odebírání serverů minimalizoval počet klíčů, které je třeba přemístit. Jedno takové schéma – chytré, ale překvapivě jednoduché – se nazývá konzistentní hašování a poprvé ho popsali Karger a spol. na MIT ve vědecké práci z roku 1997 (podle Wikipedie).
Konzistentní hašování je distribuované hašovací schéma, které funguje nezávisle na počtu serverů nebo objektů v distribuované hašovací tabulce tím, že jim přiřazuje pozici na abstraktním kruhu neboli hašovacím prstenci. To umožňuje škálování serverů a objektů bez vlivu na celkový systém.
Představte si, že bychom výstupní rozsah hashování namapovali na okraj kruhu. To znamená, že minimální možná hodnota hash, nula, by odpovídala úhlu nula, maximální možná hodnota (nějaké velké celé číslo, které nazveme INT_MAX) by odpovídala úhlu 2𝝅 radiánů (nebo 360 stupňů) a všechny ostatní hodnoty hash by se lineárně vešly někam mezi. Mohli bychom tedy vzít klíč, vypočítat jeho hash a zjistit, kde leží na hraně kruhu. Za předpokladu, že INT_MAX je 1010 (pro představu), by klíče z našeho předchozího příkladu vypadaly takto:
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| „john“ | 1633428562 | 58.8 |
| „bill“ | 7594634739 | 273.4 |
| „Jane“ | 5000799124 | 180 |
| „Steve“ | 9787173343 | 352.3 |
| „kate“ | 3421657995 | 123,2 |
Nyní si představte, že jsme servery umístili také na okraj kruhu, a to tak, že jsme jim pseudonáhodně přiřadili také úhly. To by mělo být provedeno opakovatelně (nebo alespoň tak, aby se všichni klienti na úhlech serverů shodli). Vhodným způsobem, jak to provést, je hashování názvu serveru (nebo IP adresy, nebo nějakého ID) – stejně jako bychom to udělali s jakýmkoli jiným klíčem – pro získání jeho úhlu.
V našem příkladu by věci mohly vypadat takto:
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| „john“ | 1633428562 | 58.8 |
| „bill“ | 7594634739 | 273.4 |
| „Jane“ | 5000799124 | 180 |
| „Steve“ | 9787173343 | 352.3 |
| „kate“ | 3421657995 | 123.2 |
| „A“ | 5572014558 | 200.6 |
| „B“ | 8077113362 | 290,8 |
| „C“ | 2269549488 | 81.7 |
Protože máme klíče pro objekty i servery na stejném kruhu, můžeme definovat jednoduché pravidlo pro přiřazení prvního k druhému: Každý klíč objektu bude patřit tomu serveru, jehož klíč je nejblíže, ve směru proti směru hodinových ručiček (nebo po směru hodinových ručiček, v závislosti na použitých konvencích). Jinými slovy, abychom zjistili, kterého serveru se máme zeptat na daný klíč, musíme najít klíč na kružnici a pohybovat se ve směru vzestupného úhlu, dokud nenajdeme server.
V našem příkladu:
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| „john“ | 1633428562 | 58.7 |
| „C“ | 2269549488 | 81.7 |
| „kate“ | 3421657995 | 123.1 |
| „Jane“ | 5000799124 | 180 |
| „A“ | 5572014557 | 200.5 |
| „bill“ | 7594634739 | 273.4 |
| „B“ | 8077113361 | 290,7 |
| „steve“ | 787173343 | 352.3 |
| KEY | HASH | ANGLE (DEG) | LABEL | SERVER |
|---|---|---|---|---|
| „john“ | 1632929716 | 58.7 | „C“ | C |
| „kate“ | 3421831276 | 123.1 | „A“ | A |
| „jane“ | 5000648311 | 180 | „A“ | A |
| „bill“ | 7594873884 | 273.4 | „B“ | B |
| „steve“ | 9786437450 | 352.3 | „C“ | C |
Z programátorského hlediska bychom udělali to, že bychom vedli setříděný seznam hodnot serverů (což mohou být úhly nebo čísla v libovolném reálném intervalu) a procházeli bychom tento seznam (nebo použili binární vyhledávání), abychom našli první server s hodnotou větší nebo rovnou hodnotě požadovaného klíče. Pokud žádnou takovou hodnotu nenajdeme, musíme to obejít a vzít první ze seznamu.
Abychom zajistili rovnoměrné rozložení klíčů objektů mezi servery, musíme použít jednoduchý trik: Přiřadit každému serveru ne jednu, ale mnoho značek (úhlů). Takže místo štítků A, B a C bychom mohli mít například A0 .. A9, B0 .. B9 a C0 .. C9, všechny rozmístěné podél kruhu. Faktor, o který se zvýší počet štítků (klíčů serverů), známý jako váha, závisí na situaci (a může být dokonce pro každý server jiný), aby se upravila pravděpodobnost, že klíče skončí na každém z nich. Pokud by například server B byl dvakrát výkonnější než ostatní, mohl by mu být přiřazen dvojnásobný počet štítků a v důsledku toho by na něm skončilo dvakrát více objektů (v průměru).
Pro náš příklad budeme předpokládat, že všechny tři servery mají stejnou váhu 10 (to funguje dobře pro tři servery, pro 10 až 50 serverů by lépe fungovala váha v rozmezí 100 až 500 a větší pooly mohou potřebovat ještě vyšší váhy):
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| „C6“ | 408965526 | 14.7 |
| „A1“ | 473914830 | 17 |
| „A2“ | 548798874 | 19.7 |
| „A3“ | 1466730567 | 52.8 |
| „C4“ | 1493080938 | 53.7 |
| „john“ | 1633428562 | 58.7 |
| „B2“ | 1808009038 | 65 |
| „C0“ | 1982701318 | 71.3 |
| „B3“ | 2058758486 | 74.1 |
| „A7“ | 2162578920 | 77.8 |
| „B4“ | 2660265921 | 95,7 |
| „C9“ | 3359725419 | 120.9 |
| „kate“ | 3421657995 | 123.1 |
| „A5“ | 3434972143 | 123.6 |
| „C1“ | 3672205973 | 132.1 |
| „C8“ | 3750588567 | 135 |
| „B0“ | 4049028775 | 145.7 |
| „B8“ | 4755525684 | 171.1 |
| „A9“ | 4769549830 | 171.7 |
| „jane“ | 5000799124 | 180 |
| „C7“ | 5014097839 | 180.5 |
| „B1“ | 5444659173 | 196 |
| „A6“ | 6210502707 | 223.5 |
| „A0“ | 6511384141 | 234.4 |
| „B9“ | 7292819872 | 262,5 |
| „C3“ | 7330467663 | 263.8 |
| „C5“ | 7502566333 | 270 |
| „bill“ | 7594634739 | 273.4 |
| „A4“ | 8047401090 | 289.7 |
| „C2“ | 8605012288 | 309.7 |
| „A8“ | 8997397092 | 323,9 |
| „B7“ | 9038880553 | 325.3 |
| „B5“ | 9368225254 | 337.2 |
| „B6“ | 9379713761 | 337.6 |
| „steve“ | 9787173343 | 352.3 |
| KEY | HASH | ANGLE (DEG) | LABEL | SERVER |
|---|---|---|---|---|
| „john“ | 1632929716 | 58.7 | „B2“ | B |
| „kate“ | 3421831276 | 123.1 | „A5“ | A |
| „jane“ | 5000648311 | 180 | „C7“ | C |
| „bill“ | 7594873884 | 273.4 | „A4“ | A |
| „steve“ | 9786437450 | 352.3 | „C6“ | C |
Takže, jaký je přínos celého tohoto kruhového přístupu? Představte si, že server C je odstraněn. Abychom to zohlednili, musíme z kruhu odstranit štítky C0 .. C9. To má za následek, že klíče objektů, které dříve sousedily s odstraněnými štítky, jsou nyní náhodně označeny Ax a Bx, čímž jsou znovu přiřazeny serverům A a B.
Co se ale stane s ostatními klíči objektů, těmi, které původně patřily do A a B? Nic! V tom je právě ta krása: Absence štítků Cx tyto klíče nijak neovlivní. Odstranění serveru tedy vede k tomu, že jeho objektové klíče jsou náhodně znovu přiřazeny ostatním serverům a všechny ostatní klíče zůstávají nedotčeny:
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| „A1“ | 473914830 | 17 |
| „A2“ | 548798874 | 19.7 |
| „A3“ | 1466730567 | 52.8 |
| „john“ | 1633428562 | 58.7 |
| „B2“ | 1808009038 | 65 |
| „B3“ | 2058758486 | 74.1 |
| „A7“ | 2162578920 | 77,8 |
| „B4“ | 2660265921 | 95.7 |
| „kate“ | 3421657995 | 123.1 |
| „A5“ | 3434972143 | 123.6 |
| „B0“ | 4049028775 | 145.7 |
| „B8“ | 4755525684 | 171.1 |
| „A9“ | 4769549830 | 171.7 |
| „jane“ | 5000799124 | 180 |
| „B1“ | 5444659173 | 196 |
| „A6“ | 6210502707 | 223.5 |
| „A0“ | 6511384141 | 234.4 |
| „B9“ | 7292819872 | 262.5 |
| „bill“ | 7594634739 | 273.4 |
| „A4“ | 8047401090 | 289.7 |
| „A8“ | 8997397092 | 323.9 |
| „B7“ | 9038880553 | 325.3 |
| „B5“ | 9368225254 | 337.2 |
| „B6“ | 9379713761 | 337.6 |
| „steve“ | 9787173343 | 352.3 |
| KEY | HASH | ANGLE (DEG) | LABEL | SERVER |
|---|---|---|---|---|
| „john“ | 1632929716 | 58.7 | „B2“ | B |
| „kate“ | 3421831276 | 123.1 | „A5“ | A |
| „jane“ | 5000648311 | 180 | „B1“ | B |
| „bill“ | 7594873884 | 273.4 | „A4“ | A |
| „steve“ | 9786437450 | 352.3 | „A1“ | A |
Něco podobného se stane, pokud místo odstranění serveru jeden přidáme. Pokud bychom chtěli do našeho příkladu přidat server D (řekněme jako náhradu za C), museli bychom přidat štítky D0 .. D9. Výsledkem by bylo, že zhruba třetina stávajících klíčů (všechny patřící A nebo B) by byla přiřazena D a zbytek by opět zůstal stejný:
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| „D2“ | 439890723 | 15.8 |
| „A1“ | 473914830 | 17 |
| „A2“ | 548798874 | 19.7 |
| „D8“ | 796709216 | 28,6 |
| „D1“ | 1008580939 | 36.3 |
| „A3“ | 1466730567 | 52.8 |
| „D5“ | 1587548309 | 57.1 |
| „john“ | 1633428562 | 58.7 |
| „B2“ | 1808009038 | 65 |
| „B3“ | 2058758486 | 74.1 |
| „A7“ | 2162578920 | 77,8 |
| „B4“ | 2660265921 | 95.7 |
| „D4“ | 2909395217 | 104.7 |
| „kate“ | 3421657995 | 123.1 |
| „A5“ | 3434972143 | 123.6 |
| „D7“ | 3567129743 | 128.4 |
| „B0“ | 4049028775 | 145.7 |
| „B8“ | 4755525684 | 171.1 |
| „A9“ | 4769549830 | 171.7 |
| „jane“ | 5000799124 | 180 |
| „B1“ | 5444659173 | 196 |
| „D6“ | 5703092354 | 205.3 |
| „A6“ | 6210502707 | 223.5 |
| „A0“ | 6511384141 | 234.4 |
| „B9“ | 7292819872 | 262.5 |
| „bill“ | 7594634739 | 273.4 |
| „A4“ | 8047401090 | 289.7 |
| „D0“ | 8272587142 | 297.8 |
| „A8“ | 8997397092 | 323.9 |
| „B7“ | 9038880553 | 325.3 |
| „D3“ | 9048608874 | 325.7 |
| „D9“ | 9314459653 | 335.3 |
| „B5“ | 9368225254 | 337.2 |
| „B6“ | 9379713761 | 337.6 |
| „steve“ | 9787173343 | 352.3 |
| KEY | HASH | ANGLE (DEG) | LABEL | SERVER |
|---|---|---|---|---|
| „john“ | 1632929716 | 58.7 | „B2“ | B |
| „kate“ | 3421831276 | 123.1 | „A5“ | A |
| „jane“ | 5000648311 | 180 | „B1“ | B |
| „bill“ | 7594873884 | 273.4 | „A4“ | A |
| „steve“ | 9786437450 | 352.3 | „D2“ | D |
Takto konzistentní hashování řeší problém rehashingu.
Obecně je třeba přemapovat pouze k/N klíčů, když k je počet klíčů a N je počet serverů (přesněji maximum počátečního a konečného počtu serverů).
Všimli jsme si, že při použití distribuovaného cachování pro optimalizaci výkonu se může stát, že se počet cachovacích serverů změní (důvodem může být pád serveru nebo potřeba přidat či odebrat server pro zvýšení či snížení celkové kapacity). Používáním konzistentního hashování k distribuci klíčů mezi servery si můžeme být jisti, že pokud k tomu dojde, bude počet klíčů, které se budou znovu hashovat – a tedy i dopad na původní servery – minimalizován, čímž se předejde případným výpadkům nebo problémům s výkonem.
Existují klienti pro několik systémů, jako jsou Memcached a Redis, kteří obsahují podporu konzistentního hashování již z výroby.
Alternativně můžete algoritmus implementovat sami, ve vámi zvoleném jazyce, a to by mělo být po pochopení konceptu relativně snadné.
Pokud vás datová věda zajímá, na blogu Toptal najdete jedny z nejlepších článků na toto téma
.