Az elmúlt években, az olyan fogalmak megjelenésével, mint a felhőalapú számítástechnika és a big data, az elosztott rendszerek népszerűségre és jelentőségre tettek szert.
Az egyik ilyen típusú rendszer, az elosztott gyorsítótárak, amelyek számos nagy forgalmú dinamikus weboldalt és webes alkalmazást működtetnek, jellemzően az elosztott hashing egy speciális esetéből állnak. Ezek a konzisztens hashing néven ismert algoritmust használják ki.
Mi a konzisztens hashing? Mi a motiváció mögötte, és miért érdekel?
Ebben a cikkben először a hashing általános fogalmát és célját tekintem át, majd az elosztott hashing leírása és a vele járó problémák következnek. Ez viszont elvezet minket a címben szereplő témánkhoz.
Mi a hashing?
Miről szól a “hashing”? A Merriam-Webster a hash főnevet úgy definiálja, mint “apróra vágott, burgonyával összekevert és megbarnított hús”, az igét pedig úgy, mint “apró darabokra vágni (mint a húst és a burgonyát)”. Tehát, a kulináris részleteket félretéve, a hash nagyjából azt jelenti, hogy “aprítani és összekeverni” – és pontosan innen származik a szakkifejezés is.
A hash-függvény olyan függvény, amely egy adatdarabot – jellemzően valamilyen objektumot leíró, gyakran tetszőleges méretű – egy másik adatdarabhoz, jellemzően egy egész számhoz képez le, amelyet hash-kódnak vagy egyszerűen hash-nek neveznek.
Egy hash-függvény, amelyet például stringek hashelésére terveztek, és amelynek kimeneti tartománya 0 .. 100, leképezheti a Hello stringet mondjuk a 57 számra, a Hasta la vista, baby-t a 33 számra, és bármely más lehetséges stringet az adott tartományon belüli valamely számra. Mivel sokkal több lehetséges bemenet van, mint kimenet, bármely adott számhoz sok különböző karakterláncot lehet hozzárendelni, ezt a jelenséget kollíziónak nevezzük. A jó hash-függvényeknek valahogy úgy kell “feldarabolniuk és összekeverniük” (innen a kifejezés) a bemeneti adatokat, hogy a különböző bemeneti értékekhez tartozó kimenetek a lehető legegyenletesebben oszoljanak el a kimeneti tartományban.
A hash-függvényeknek sokféle felhasználási területe van, és mindegyikhez különböző tulajdonságokra lehet szükség. Létezik a hash-függvények egy típusa, az úgynevezett kriptográfiai hash-függvények, amelyeknek szigorú tulajdonságkészletnek kell megfelelniük, és amelyeket biztonsági célokra használnak – többek között olyan alkalmazásokra, mint a jelszóvédelem, az üzenetek integritásának ellenőrzése és az ujjlenyomatok készítése, valamint az adatkorrupció felderítése, de ezek nem tartoznak e cikk tárgykörébe.
A nem kriptográfiai hash-függvényeknek is számos felhasználási módja van, a leggyakoribb a hash-táblákban való alkalmazásuk, amely minket érint, és amelyet részletesebben is megvizsgálunk.
A hash-táblák (Hash Maps)
Tegyük fel, hogy egy klub összes tagjának listáját kell vezetnünk, miközben bármelyik konkrét tagra rákereshetünk. Ezt úgy tudnánk megoldani, hogy a listát egy tömbben (vagy összekapcsolt listában) tartjuk, és a kereséshez addig iteráljuk az elemeket, amíg meg nem találjuk a kívánt tagot (például a neve alapján kereshetnénk). Ez legrosszabb esetben az összes tag ellenőrzését jelentené (ha a keresett tag az utolsó, vagy egyáltalán nincs jelen), vagy átlagosan a felét. Bonyolultságelméleti szempontból a keresés ekkor O(n) komplexitású lenne, és egy kis lista esetén viszonylag gyors lenne, de a tagok számával egyenes arányban egyre lassabbá válna.
Hogyan lehetne ezt javítani? Tegyük fel, hogy az összes ilyen klubtagnak van egy ID tagja, ami történetesen egy sorszám, ami a klubhoz való csatlakozásuk sorrendjét tükrözi.
Tegyük fel, hogy a ID szerinti keresés elfogadható lenne, akkor az összes tagot elhelyezhetnénk egy tömbben, ahol az indexük megegyezik a ID-ükkel (például egy ID=10 tag a 10 indexen lenne a tömbben). Ez lehetővé tenné számunkra, hogy minden egyes taghoz közvetlenül, keresés nélkül hozzáférjünk. Ez nagyon hatékony lenne, valójában a lehető leghatékonyabb, ami a lehető legalacsonyabb komplexitásnak, O(1), más néven konstans időnek felel meg.
De, bevalljuk, a mi klubtag ID forgatókönyvünk kissé mesterkélt. Mi lenne, ha ID nagy, nem szekvenciális vagy véletlen számok lennének? Vagy ha a ID szerinti keresés nem lenne elfogadható, és helyette név (vagy más mező) szerint kellene keresnünk? Minden bizonnyal hasznos lenne megtartani a gyors közvetlen hozzáférést (vagy valami hasonlót), ugyanakkor tetszőleges adathalmazokat és kevésbé korlátozó keresési feltételeket is kezelni tudnánk.
Itt jönnek a segítségünkre a hash függvények. Egy megfelelő hash függvénnyel egy tetszőleges adatot leképezhetünk egy egész számra, ami hasonló szerepet fog játszani, mint a klubtagunk ID, bár néhány fontos különbséggel.
Először is, egy jó hash függvénynek általában széles kimeneti tartománya van (tipikusan egy 32 vagy 64 bites egész szám teljes tartománya), így egy tömb létrehozása az összes lehetséges indexhez vagy nem lenne praktikus, vagy egyszerűen lehetetlen, és kolosszális memóriapazarlás lenne. Ennek kiküszöbölésére rendelkezhetünk egy elfogadható méretű tömbtel (mondjuk, csak kétszer annyi elemmel, mint amennyit tárolni szeretnénk), és a hash-en modulo műveletet végezhetünk, hogy megkapjuk a tömb indexét. Így az index index = hash(object) mod N lenne, ahol N a tömb mérete.
Másodszor, az objektumok hash-jei nem lesznek egyediek (hacsak nem egy rögzített adathalmazzal és egy egyedi, tökéletes hash-függvénnyel dolgozunk, de ezt most nem tárgyaljuk). Lesznek ütközések (amit a modulo művelet tovább növel), és ezért az egyszerű közvetlen index-hozzáférés nem fog működni. Ezt többféleképpen is kezelhetjük, de egy tipikus megoldás az, hogy minden tömbindexhez csatolunk egy listát, közismert nevén bucket-et, amely az adott indexen osztozó összes objektumot tartalmazza.
Így van egy N méretű tömbünk, amelynek minden egyes bejegyzése egy objektum bucket-re mutat. Egy új objektum hozzáadásához ki kell számolnunk a hash modulo N objektumot, és ellenőrizni kell az így kapott indexnél lévő vödröt, és hozzáadni az objektumot, ha még nincs benne. Egy objektum kereséséhez ugyanígy járunk el, csak megnézzük a vödörben, hogy van-e ott az objektum. Egy ilyen struktúrát hash-táblának nevezünk, és bár a vödrökön belüli keresések lineárisak, egy megfelelően méretezett hash-táblának ésszerűen kevés objektumot kell tartalmaznia vödrönként, ami szinte állandó idejű hozzáférést eredményez (átlagos bonyolultsága O(N/k), ahol k a vödrök száma).
Összetett objektumok esetén a hash-függvényt általában nem az egész objektumra, hanem egy kulcsra alkalmazzuk. A klubtag példánkban az egyes objektumok több mezőt is tartalmazhatnak (például név, kor, cím, e-mail, telefon), de választhatnánk mondjuk az e-mail címet kulcsként, így a hash-függvényt csak az e-mailre alkalmaznánk. Valójában a kulcsnak nem kell az objektum részeinek lennie; gyakori a kulcs/érték párok tárolása, ahol a kulcs általában egy viszonylag rövid karakterlánc, az érték pedig egy tetszőleges adat lehet. Ilyen esetekben a hash-táblázatot vagy hash-térképet szótárként használják, és néhány magas szintű nyelv így valósítja meg az objektumokat vagy asszociatív tömböket.
Skálázás:
Most, hogy már tárgyaltuk a hash-táblázást, készen állunk arra, hogy megvizsgáljuk az elosztott hash-táblázást.
Egy hash-táblát bizonyos helyzetekben szükséges vagy kívánatos lehet több részre osztani, amelyeket különböző kiszolgálókon tárolnak. Ennek egyik fő motivációja az, hogy megkerüljük az egyetlen számítógép használatából adódó memóriakorlátozásokat, lehetővé téve tetszőlegesen nagy hash-táblák létrehozását (elegendő számú szerver esetén).
Egy ilyen forgatókönyvben az objektumok (és kulcsaik) több szerver között vannak elosztva, innen a név.
Egy tipikus felhasználási eset a memórián belüli gyorsítótárak, például a Memcached megvalósítása.
Az ilyen felállások olyan gyorsítótár-kiszolgálókból állnak, amelyek sok kulcs-érték párt tárolnak, és az eredetileg máshol tárolt (vagy kiszámított) adatok gyors elérését biztosítják. Például egy adatbázis-kiszolgáló terhelésének csökkentése és egyúttal a teljesítmény javítása érdekében egy alkalmazás úgy tervezhető, hogy először lekérdezi az adatokat a gyorsítótár-kiszolgálókról, és csak ha azok nincsenek ott – ez az úgynevezett cache miss helyzet -, akkor fordul vissza az adatbázishoz, lefuttatja a megfelelő lekérdezést, és az eredményeket megfelelő kulccsal gyorsítótárba teszi, hogy a következő alkalommal, amikor szükség van rájuk, megtalálhatók legyenek.
Most, hogyan történik a terjesztés? Milyen kritériumok alapján határozzák meg, hogy mely kulcsokat melyik szervereken kell elhelyezni?
A legegyszerűbb, ha a szerverek számának hash modulóját vesszük. Vagyis server = hash(key) mod N, ahol N a pool mérete. Egy kulcs tárolásához vagy lekérdezéséhez az ügyfél először kiszámítja a hash-t, alkalmazza a modulo N műveletet, és az így kapott index segítségével felveszi a kapcsolatot a megfelelő szerverrel (valószínűleg egy IP-címeket tartalmazó keresőtábla segítségével). Vegyük figyelembe, hogy a kulcselosztáshoz használt hash-függvénynek minden ügyfélnél azonosnak kell lennie, de nem kell, hogy ugyanaz legyen, mint amit a gyorsítótárazó kiszolgálók belsőleg használnak.
Lássunk egy példát. Tegyük fel, hogy van három szerverünk, A, B és C, és van néhány string kulcsunk a hash-jeikkel:
| KEY | HASH | HASH mod 3 |
|---|---|---|
| “john” | 1633428562 | 2 |
| “bill” | 7594634739 | 0 |
| “jane” | 5000799124 | 1 |
| “steve” | 9787173343 | 0 |
| “kate” | 3421657995 | 2 |
A kliens a john kulcs értékét szeretné lekérdezni. Ennek hash modulo 3 értéke 2, ezért a C szerverrel kell felvennie a kapcsolatot. A kulcsot ott nem találja, ezért a kliens lekéri az adatokat a forrásból, és hozzáadja. A pool így néz ki:
| A | B | C |
|---|---|---|
| “john” |
A következő kliens (vagy ugyanaz) a bill kulcs értékét szeretné lekérni. A hash modulo 3-je 0, tehát a A szerverrel kell felvennie a kapcsolatot. A kulcsot ott nem találja, ezért a kliens lekéri az adatokat a forrásból és hozzáadja. A pool most így néz ki:
| A | B | C |
|---|---|---|
| “bill” | “john” |
A többi kulcs hozzáadása után a pool így néz ki:
| A | B | C |
|---|---|---|
| “bill” | “jane” | “john” |
| “steve” | “kate” |
Az újrahasznosítási probléma
Ez az elosztási séma egyszerű, intuitív, és jól működik. Egészen addig, amíg a szerverek száma meg nem változik. Mi történik, ha az egyik szerver összeomlik vagy elérhetetlenné válik? A kulcsokat természetesen újra kell osztani a hiányzó szerver miatt. Ugyanez vonatkozik arra az esetre is, ha egy vagy több új szerverrel bővül a pool; a kulcsokat újra kell osztani az új szerverek bevonásával. Ez bármilyen elosztási sémára igaz, de a mi egyszerű moduláris elosztásunkkal az a probléma, hogy amikor a szerverek száma változik, a legtöbb hashes modulo N is változik, így a legtöbb kulcsot át kell helyezni egy másik szerverre. Tehát még akkor is, ha egyetlen szervert eltávolítunk vagy hozzáadunk, valószínűleg az összes kulcsot újra át kell helyezni egy másik szerverre.
A korábbi példánkból kiindulva, ha eltávolítjuk a C kiszolgálót, akkor az összes kulcsot a hash modulo 3 helyett a hash modulo 2 használatával kell újra átmásolnunk, és a kulcsok új helyei a következők lesznek:
| KEY | HASH | HASH mod 2 |
|---|---|---|
| “john” | 1633428562 | 0 |
| “bill” | 7594634739 | 1 |
| “jane” | 5000799124 | 0 |
| “steve” | 9787173343 | 1 |
| “kate” | 3421657995 | 1 |
| A | B | |
|---|---|---|
| “john” | “John” | “bill” |
| “jane” | “steve” | |
| “kate” |
Megjegyezzük, hogy minden kulcshely megváltozott, nem csak a C szerverről származó kulcsok.
A korábban említett tipikus felhasználási esetben (gyorsítótárazás) ez azt jelentené, hogy a kulcsok hirtelen nem lesznek megtalálhatók, mert még nem lesznek jelen az új helyükön.
A legtöbb lekérdezés tehát nem találatot fog eredményezni, és az eredeti adatokat valószínűleg újra le kell majd kérni a forrásból, hogy újra lekérdezzük őket, ami nagy terhet ró a származási szerver(ek)re (jellemzően egy adatbázis). Ez nagymértékben ronthatja a teljesítményt, és esetleg összeomolhatnak a származási szerverek.
A megoldás:
Hogyan oldható meg tehát ez a probléma? Olyan elosztási sémára van szükségünk, amely nem függ közvetlenül a szerverek számától, így a szerverek hozzáadásakor vagy eltávolításakor minimálisra csökken az áthelyezendő kulcsok száma. Az egyik ilyen – okos, mégis meglepően egyszerű – sémát konzisztens hashelésnek nevezik, és először Karger és társai írták le az MIT-n egy 1997-es tudományos dolgozatban (a Wikipedia szerint).
A konzisztens hashelés egy olyan elosztott hashelési séma, amely a szerverek vagy objektumok számától függetlenül működik az elosztott hash-táblában azáltal, hogy egy absztrakt körön vagy hash-gyűrűn pozíciókat rendel hozzájuk. Ez lehetővé teszi a kiszolgálók és objektumok skálázását anélkül, hogy a teljes rendszerre hatással lenne.
Tegyük fel, hogy a hash-kimeneti tartományt egy kör szélére képeztük le. Ez azt jelenti, hogy a minimálisan lehetséges hash-érték, a nulla, egy nulla szögnek felelne meg, a maximálisan lehetséges érték (valami nagy egész szám, amit INT_MAX-nek fogunk hívni) egy 2𝝅 radián (vagy 360 fok) szögnek felelne meg, és minden más hash-érték lineárisan illeszkedne valahol a kettő között. Tehát vehetnénk egy kulcsot, kiszámíthatnánk a hash-értékét, és kideríthetnénk, hogy hol helyezkedik el a kör szélén. Feltételezve, hogy a INT_MAX értéke 1010 (a példa kedvéért), az előző példánkban szereplő kulcsok így néznének ki:
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| “john” | 1633428562 | 58.8 |
| “bill” | 7594634739 | 273.4 |
| “jane” | 5000799124 | 180 |
| “steve” | 9787173343 | 352.3 |
| “kate” | 3421657995 | 123.2 |
Most képzeljük el, hogy a kiszolgálókat is a kör szélére helyeztük, szintén pszeudo-véletlenszerűen szögeket rendelve hozzájuk. Ezt megismételhető módon kell megtenni (vagy legalábbis úgy, hogy minden kliens megegyezzen a szerverek szögeiben). Ennek egy kényelmes módja, hogy a szerver nevét (vagy IP-címét, vagy valamilyen azonosítót) – ahogyan bármely más kulccsal tennénk – hasheléssel adjuk meg a szögét.
Példánkban a dolgok így nézhetnek ki:
| 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 |
Mivel mind az objektumok, mind a kiszolgálók kulcsai ugyanazon a körön vannak, definiálhatunk egy egyszerű szabályt az előbbiek és az utóbbiak társítására: Minden objektumkulcs ahhoz a kiszolgálóhoz fog tartozni, amelynek a kulcsa az óramutató járásával ellentétes irányban (vagy az óramutató járásával megegyezően, az alkalmazott konvencióktól függően) a legközelebb van. Más szóval, ahhoz, hogy megtudjuk, melyik szervertől kérhetünk egy adott kulcsot, meg kell keresnünk a kulcsot a körön, és addig kell haladnunk a növekvő szög irányában, amíg nem találunk egy szervert.
Példánkban:
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| “john” | 1633428562 | 58.7 |
| “C” | 2269549488 | 81.7 |
| “kate” | 3421657995 | 123.1 |
| “jane” | 5000799124 | 180 |
| “A” | 5572014557 | 200.5 |
| “számla” | 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 | 180 | “A” | A |
| “bill” | 7594873884 | 273.4 | “B” | B | |
| “steve” | 9786437450 | 352.3 | “C” | C |
Programozási szempontból azt tennénk, hogy a szerverértékek (amelyek lehetnek szögek vagy számok bármely valós intervallumban) rendezett listáját vezetnénk, és ezt a listát végigjárnánk (vagy bináris keresést használnánk), hogy megtaláljuk az első olyan szervert, amelynek értéke nagyobb vagy egyenlő a kívánt kulcs értékénél. Ha nem találunk ilyen értéket, akkor körbe kell tekernünk, az elsőt véve a listából.
Az objektumkulcsok szerverek közötti egyenletes eloszlásának biztosításához egy egyszerű trükköt kell alkalmaznunk: Nem egy, hanem sok címkét (szöget) kell rendelnünk minden szerverhez. Tehát ahelyett, hogy A, B és C címkéink lennének, lehetnének mondjuk A0 .. A9, B0 .. B9 és C0 .. C9, a kör mentén elszórtan. Az a tényező, amellyel a címkék (szerverkulcsok) számát növelni kell, az úgynevezett súly, a helyzettől függ (és akár szerverenként eltérő is lehet), hogy beállítsuk a kulcsok mindegyikre kerülésének valószínűségét. Ha például a B szerver kétszer olyan erős lenne, mint a többi, akkor kétszer annyi címkét lehetne hozzá rendelni, és ennek eredményeként (átlagosan) kétszer annyi objektum kerülne rá.
Példánkban feltételezzük, hogy mindhárom szerver súlya egyenlő, 10 (ez három szerver esetén jól működik, 10-50 szerver esetén a 100 és 500 közötti súly jobban működne, nagyobb pooloknál pedig még nagyobb súlyokra lehet szükség):
| 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 |
Szóval, mi a haszna ennek az egész körös megközelítésnek? Képzeljük el, hogy a C kiszolgálót eltávolítjuk. Ahhoz, hogy ezt figyelembe vegyük, el kell távolítanunk a C0 .. C9 címkéket a körből. Ez azt eredményezi, hogy a korábban a törölt címkékkel szomszédos objektumkulcsok most véletlenszerűen Ax és Bx címkét kapnak, és újra a A és B szerverekhez rendeljük őket.
De mi történik a többi objektumkulccsal, azokkal, amelyek eredetileg a A és B szerverekhez tartoztak? Semmi! Ez a dolog szépsége: A Cx címkék hiánya semmilyen módon nem befolyásolja ezeket a kulcsokat. Tehát egy kiszolgáló eltávolítása azt eredményezi, hogy az objektumkulcsok véletlenszerűen átkerülnek a többi kiszolgálóhoz, az összes többi kulcsot érintetlenül hagyva:
| KEY | HASH | ANGLE (FOK) |
|---|---|---|
| “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 |
Valami hasonló történik, ha egy szerver eltávolítása helyett hozzáadunk egyet. Ha a példánkhoz D kiszolgálót akarnánk hozzáadni (mondjuk a C helyett), akkor D0 .. D9 címkéket kellene hozzáadnunk. Az eredmény az lenne, hogy a meglévő kulcsok nagyjából egyharmadát (amelyek mind a A vagy B szerverhez tartoznak) átcsoportosítanánk a D szerverhez, a többi pedig változatlan maradna:
| 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 |
Így oldja meg a következetes hashing a rehashing problémát.
Általában csak k/N kulcsot kell újratérképezni, ha k a kulcsok száma és N a szerverek száma (pontosabban a szerverek kezdeti és végső számának maximuma).
Megfigyeltük, hogy amikor a teljesítmény optimalizálása érdekében elosztott gyorsítótárat használunk, előfordulhat, hogy a gyorsítótár szerverek száma változik (ennek oka lehet egy szerver összeomlása, vagy az, hogy a teljes kapacitás növelése vagy csökkentése érdekében szervert kell hozzáadni vagy eltávolítani). Ha a kulcsok konzisztens kivonatolással oszlanak el a kiszolgálók között, biztosak lehetünk benne, hogy ha ez megtörténik, akkor az újbóli kivonatolásra kerülő kulcsok száma – és ezáltal a származási szerverekre gyakorolt hatás – minimálisra csökken, megelőzve a lehetséges leállásokat vagy teljesítményproblémákat.
Számos rendszerhez, például a Memcachedhez és a Redishez léteznek olyan kliensek, amelyek már a dobozból támogatják a konzisztens kivonatolást.
Változatlanul implementálhatja az algoritmust saját maga is, az Ön által választott nyelven, ami viszonylag egyszerűnek kell lennie, ha megértette a koncepciót.
Ha az adattudomány érdekli, a Toptal blogon
a témában a legjobb cikkeket találja.