Viime vuosina pilvilaskennan ja big datan kaltaisten käsitteiden tulon myötä hajautetut järjestelmät ovat kasvattaneet suosiotaan ja merkitystään.
Yksi tällaisista järjestelmistä ovat hajautetut välimuistitietokannat, jotka ovat monien vilkkaasti liikennöityjen dynaamisten verkkosivujen ja -sovellusten voimanlähteenä. Nämä hyödyntävät algoritmia, joka tunnetaan nimellä consistent hashing.
Mitä on consistent hashing? Mikä on sen taustalla oleva motivaatio, ja miksi sinun pitäisi välittää siitä?
Tässä artikkelissa käyn ensin läpi hashingin yleisen käsitteen ja sen tarkoituksen, minkä jälkeen kuvaan hajautetun hashingin ja siihen liittyvät ongelmat. Tämä puolestaan johdattaa meidät otsikkoaiheeseemme.
Mitä on hashaus?
Mitä ”hashaus” tarkoittaa? Merriam-Webster määrittelee substantiivin hash seuraavasti: ”pilkottu liha, joka on sekoitettu perunoihin ja ruskistettu”, ja verbin ”pilkkoa (kuten liha ja perunat) pieniksi paloiksi”. Kulinaristisia yksityiskohtia lukuun ottamatta hash tarkoittaa siis karkeasti ottaen ”pilkkoa ja sekoittaa” – ja juuri siitä on peräisin myös tekninen termi.
Hash-funktio on funktio, joka mapittaa yhden datan osan – tyypillisesti jonkin objektin kuvauksen, joka on usein mielivaltaisen kokoinen – toiseen datan osaan, tyypillisesti kokonaislukuun, joka tunnetaan nimellä hash-koodi tai yksinkertaisesti hash.
Esimerkiksi jokin hash-funktio, joka on suunniteltu hashaamaan merkkijonoja ja jonka ulostuloalue on 0 .. 100, voi kartoittaa merkkijonon Hello vaikkapa luvuksi 57, Hasta la vista, baby luvuksi 33 ja minkä tahansa muun mahdollisen merkkijonon joksikin luvuksi tuon alueen sisällä. Koska mahdollisia sisääntuloja on paljon enemmän kuin ulostuloja, mihin tahansa numeroon voidaan liittää monia erilaisia merkkijonoja, mikä on ilmiö, jota kutsutaan törmäykseksi. Hyvien hash-funktioiden pitäisi jotenkin ”pilkkoa ja sekoittaa” (tästä termi) syöttötiedot siten, että eri syöttöarvojen ulostulot jakautuvat mahdollisimman tasaisesti ulostuloalueelle.
Hash-funktioilla on monia käyttötarkoituksia, ja jokaiseen niistä voidaan haluta erilaisia ominaisuuksia. On olemassa erityyppisiä hash-funktioita, joita kutsutaan kryptografisiksi hash-funktioiksi, joiden on täytettävä rajoitettu joukko ominaisuuksia, ja niitä käytetään tietoturvatarkoituksiin – muun muassa salasanasuojaukseen, viestien eheyden tarkistamiseen ja sormenjälkien ottamiseen sekä tietojen korruptoitumisen havaitsemiseen, mutta ne eivät kuulu tämän artikkelin piiriin.
Ei-kryptografisilla hash-funktioilla on myös useita käyttötarkoituksia, joista yleisin on niiden käyttö hash-taulukoissa, mikä on se, joka koskee meitä ja jota tutkimme tarkemmin.
Hash-taulukoiden (Hash Maps) esittely
Kuvitellaan, että tarvitsisimme luettelon jostain kerhosta ja samalla pystymme etsimään mitä tahansa tiettyä jäsentä. Voisimme hoitaa asian pitämällä listan matriisissa (tai linkitetyssä listassa) ja suorittamalla haun iteroimalla elementtejä, kunnes löydämme halutun (saattaisimme hakea esimerkiksi heidän nimensä perusteella). Pahimmassa tapauksessa tämä tarkoittaisi kaikkien jäsenten tarkistamista (jos etsimämme jäsen on viimeinen tai sitä ei ole lainkaan) tai keskimäärin puolet jäsenistä. Kompleksisuusteorian termein katsottuna haun kompleksisuus olisi tällöin O(n), ja se olisi kohtuullisen nopea pienelle listalle, mutta se muuttuisi hitaammaksi ja hitaammaksi suorassa suhteessa jäsenten lukumäärään.
Miten tätä voisi parantaa? Oletetaan, että kaikilla näillä kerhon jäsenillä oli jäsen ID, joka sattui olemaan juokseva numero, joka kuvastaa järjestystä, jossa he liittyivät kerhoon.
Edellyttäen, että haku ID:n mukaan olisi hyväksyttävää, voisimme sijoittaa kaikki jäsenet matriisiin, jonka indeksit vastaisivat heidän ID:nsä (esimerkiksi jäsen, jolla on ID=10, olisi matriisissa indeksillä 10). Näin voisimme käyttää jokaista jäsentä suoraan, ilman minkäänlaista hakua. Se olisi hyvin tehokasta, itse asiassa niin tehokasta kuin se vain voi olla, mikä vastaa pienintä mahdollista monimutkaisuutta, O(1), joka tunnetaan myös nimellä vakioaika.
Mutta myönnettäköön, että kerhon jäsenen ID skenaariomme on hieman keksitty. Entä jos ID olisivat isoja, ei-sekventiaalisia tai satunnaislukuja? Tai jos haku ID:n perusteella ei olisi hyväksyttävää ja meidän pitäisi sen sijaan hakea nimen (tai jonkin muun kentän) perusteella? Olisi varmasti hyödyllistä säilyttää nopea suora haku (tai jotain lähelle sitä) ja samalla pystyä käsittelemään mielivaltaisia tietokokonaisuuksia ja vähemmän rajoittavia hakukriteerejä.
Tässä kohtaa hash-funktiot tulevat apuun. Sopivaa hash-funktiota voidaan käyttää mielivaltaisen datan kartoittamiseen kokonaisluvuksi, jolla on samanlainen rooli kuin kerhomme jäsenellä ID, vaikkakin muutamilla tärkeillä eroilla.
Ensiksikin, hyvällä hash-funktiolla on yleensä laaja ulostuloväli (tyypillisesti koko 32- tai 64-bittisen kokonaisluvun vaihteluväli), joten matriisin rakentaminen kaikkia mahdollisia indeksejä varten olisi joko epäkäytännöllistä tai pelkkää mahdottomuutta ja kolossaalista muistin tuhlausta. Tämän ongelman ratkaisemiseksi voimme käyttää kohtuullisen kokoista arraya (vaikkapa vain kaksi kertaa niin monta elementtiä kuin aiomme tallentaa) ja suorittaa modulo-operaation hash-operaatiolle saadaksemme array-indeksin. Indeksi olisi siis index = hash(object) mod N, jossa N on matriisin koko.
Toiseksi, objektien hashit eivät ole uniikkeja (paitsi jos työskentelemme kiinteän tietokokonaisuuden ja räätälöidyn täydellisen hash-funktion kanssa, mutta emme käsittele sitä tässä). Yhteentörmäyksiä syntyy (joita modulo-operaatio lisää entisestään), joten pelkkä suora hakemistokäyttö ei toimi. On olemassa useita tapoja käsitellä tätä, mutta tyypillinen tapa on liittää kuhunkin array-indeksiin lista, joka tunnetaan yleisesti nimellä ämpäri (bucket), joka pitää sisällään kaikki objektit, joilla on sama indeksi.
Meillä on siis array, jonka koko on N ja jonka jokainen merkintä osoittaa objekti-ämpäriin. Lisätäksemme uuden objektin, meidän on laskettava sen hash modulo N ja tarkistettava tuloksena olevan indeksin kohdalla oleva ämpäri ja lisättävä objekti, jos se ei ole vielä siellä. Etsiäksemme objektin, teemme samoin, vain katsomme ämpäriin tarkistaaksemme, onko objekti siellä. Tällaista rakennetta kutsutaan hash-tauluksi, ja vaikka haku ämpäreiden sisällä on lineaarista, oikein mitoitetussa hash-taulussa pitäisi olla kohtuullisen pieni määrä objekteja per ämpäri, mikä johtaa lähes vakioaikaan pääsyyn (keskimääräinen monimutkaisuus O(N/k), jossa k on ämpäreiden lukumäärä).
Monimutkaisten objektien kohdalla hash-funktiota ei tyypillisesti käytetä koko objektiin vaan sen sijaan avaimeen. Kerhon jäsenesimerkissämme jokainen objekti saattaa sisältää useita kenttiä (kuten nimi, ikä, osoite, sähköposti, puhelin), mutta voisimme valita avaimeksi vaikkapa sähköpostin, jolloin hash-funktiota sovellettaisiin vain sähköpostiin. Itse asiassa avaimen ei tarvitse olla osa objektia; on tavallista tallentaa avain/arvo -pareja, joissa avain on yleensä suhteellisen lyhyt merkkijono ja arvo voi olla mielivaltainen tieto. Tällaisissa tapauksissa hash-taulukkoa tai hash mapia käytetään sanakirjana, ja tällä tavalla jotkin korkean tason kielet toteuttavat objektit tai assosiatiiviset matriisit.
Skaalautuminen: Hajautettu hajautus
Nyt kun olemme käsitelleet hajautusta, olemme valmiita tarkastelemaan hajautettua hajautusta.
Jossain tilanteissa voi olla tarpeellista tai toivottavaa jakaa hash-taulukko useampaan osaan, joita isännöidään eri palvelimilla. Yksi tärkeimmistä motiiveista tälle on ohittaa yhden tietokoneen käytön muistirajoitukset, mikä mahdollistaa mielivaltaisen suurten hash-taulukoiden rakentamisen (kunhan palvelimia on tarpeeksi).
Tällaisessa skenaariossa objektit (ja niiden avaimet) on jaettu useammalle palvelimelle, mistä nimi johtuu.
Tyypillinen käyttötapaus tälle on muistissa olevien välimuistien, kuten Memcachedin, toteuttaminen.
Tällaiset asetelmat koostuvat välimuistipalvelinten poolista, jotka isännöivät monia avain-/arvopareja ja joita käytetään tarjoamaan nopea pääsy alun perin muualla tallennettuihin (tai laskettuihin) tietoihin. Esimerkiksi tietokantapalvelimen kuormituksen vähentämiseksi ja samalla suorituskyvyn parantamiseksi sovellus voidaan suunnitella siten, että se hakee ensin tiedot välimuistipalvelimilta ja vain jos niitä ei löydy sieltä – tilanne, jota kutsutaan välimuistivirheeksi (cache miss) – hakee tiedot tietokannasta, suorittaa asiaankuuluvan kyselyn ja tallentaa tulokset välimuistiin sopivalla avaimella, jotta ne löytyisivät seuraavan kerran, kun niitä tarvitaan.
Miten jakelu nyt tapahtuu? Millä kriteereillä määritetään, mitkä avaimet sijoitetaan mihinkin palvelimiin?
Yksinkertaisin tapa on ottaa hash modulo palvelimien lukumäärästä. Eli server = hash(key) mod N, jossa N on poolin koko. Tallentaakseen tai hakeakseen avaimen asiakas laskee ensin hashin, soveltaa modulo N-operaatiota ja käyttää tuloksena saatua indeksiä ottaakseen yhteyttä asianmukaiseen palvelimeen (luultavasti käyttämällä IP-osoitteiden hakutaulukkoa). Huomaa, että avainten jakamiseen käytettävän hash-funktion on oltava sama kaikissa asiakkaissa, mutta sen ei tarvitse olla sama kuin välimuistipalvelimien sisäisesti käyttämä.
Katsotaanpa esimerkki. Oletetaan, että meillä on kolme palvelinta, A, B ja C, ja meillä on joitakin merkkijonoavaimia ja niiden hasheja:
| KEY | HASH | HASH mod 3 |
|---|---|---|
| ”john” | 1633428562 | 2 |
| ”bill” | 7594634739 | 0 |
| ”jane” | 5000799124 | 1 |
| ”steve” | 9787173343 | 0 |
| ”kate” | 3421657995 | 2 |
Asiakas haluaa hakea avaimen john arvon. Sen hash modulo 3 on 2, joten sen on otettava yhteyttä palvelimeen C. Avainta ei löydy sieltä, joten asiakas hakee tiedot lähteestä ja lisää ne. Pool näyttää seuraavalta:
| A | B | C | |
|---|---|---|---|
| ”john” |
Seuraavaksi joku toinen (tai sama) asiakas haluaa noutaa arvoa avaimelle bill. Sen hash modulo 3 on 0, joten sen on otettava yhteyttä palvelimeen A. Avainta ei löydy sieltä, joten asiakas hakee tiedon lähteestä ja lisää sen. Pool näyttää nyt seuraavalta:
| A | B | C |
|---|---|---|
| ”bill” | ”john” |
Jäljelle jääneiden avainten lisäämisen jälkeen pool näyttää seuraavalta:
| A | B | C |
|---|---|---|
| ”bill” | ”jane” | ”john” |
| ”steve” | ”kate” |
Uudelleenkäsittelyongelma
Tämä jakojärjestelmä on yksinkertainen, intuitiivinen ja toimii hyvin. Siis kunnes palvelimien määrä muuttuu. Mitä tapahtuu, jos yksi palvelimista kaatuu tai tulee käyttökelvottomaksi? Avaimet on tietenkin jaettava uudelleen puuttuvan palvelimen huomioon ottamiseksi. Sama pätee, jos pooliin lisätään yksi tai useampi uusi palvelin; avaimet on jaettava uudelleen, jotta uudet palvelimet saadaan mukaan. Tämä pätee mihin tahansa jakelujärjestelmään, mutta yksinkertaisen moduulijakelumme ongelma on se, että kun palvelinten määrä muuttuu, useimmat hashes modulo N muuttuvat, joten useimmat avaimet on siirrettävä toiselle palvelimelle. Joten vaikka yksi palvelin poistettaisiin tai lisättäisiin, kaikki avaimet on todennäköisesti siirrettävä uudelleen eri palvelimelle.
Edellisestä esimerkistämme, jos poistamme palvelimen C, meidän on uudelleensuoritettava kaikki avaimet käyttämällä hash modulo 2:ää hash modulo 3:n sijasta, ja avainten uusiksi sijainneiksi tulisi:
| KEY | HASH | HASH mod 2 |
|---|---|---|
| ”john” | 1633428562 | 0 |
| ”bill” | 7594634739 | 1 |
| ”jane” | 5000799124 | 0 |
| ”steve” | 9787173343 | 1 |
| ”kate” | 3421657995 | 1 |
| 1 | ”kate” | 3421657995 | 1 |
| 1 | 1 |
| 1 | ”bill” |
| ”jane” | ”steve” |
| ”kate” |
Huomaa, että kaikki keskeiset paikat ovat muuttuneet, eivät ainoastaan palvelimelta C peräisin olevat.
Aiemmin mainitsemassamme tyypillisessä käyttötapauksessa (välimuistitallennus) tämä tarkoittaisi sitä, että yhtäkkiä avaimia ei löydy, koska niitä ei vielä ole niiden uudessa sijainnissa.
Siten useimmat kyselyt johtavat ohituksiin, ja alkuperäiset tiedot on todennäköisesti haettava uudelleen lähteestä, jotta ne voidaan hakea uudestaan, mikä kuormittaa voimakkaasti alkuperäistä palvelinta tai alkuperäisiä palvelimia (tyypillisesti tietokanta). Tämä voi hyvinkin heikentää suorituskykyä huomattavasti ja mahdollisesti kaataa alkuperäpalvelimet.
Ratkaisu:
Miten tämä ongelma voidaan siis ratkaista? Tarvitsemme jakelujärjestelmän, joka ei riipu suoraan palvelinten lukumäärästä, jotta palvelimia lisättäessä tai poistettaessa siirrettävien avainten määrä on mahdollisimman pieni. Yksi tällainen järjestelmä – nokkela, mutta yllättävän yksinkertainen – on nimeltään consistent hashing, ja sen kuvasivat ensimmäisen kerran Karger et al. MIT:ssä vuonna 1997 julkaistussa akateemisessa artikkelissa (Wikipedian mukaan).
Consistent Hashing on hajautettu hashing-järjestelmä, joka toimii hajautetun hash-taulukon palvelinten tai kohteiden lukumäärästä riippumatta osoittamalla niille paikan abstraktilla ympyrällä eli hash-renkaalla. Näin palvelimet ja objektit voivat skaalautua ilman, että se vaikuttaa koko järjestelmään.
Kuvitellaan, että hash-tulostusalue on kuvattu ympyrän reunaan. Tämä tarkoittaa, että pienin mahdollinen hash-arvo, nolla, vastaisi nollakulmaa, suurin mahdollinen arvo (jokin iso kokonaisluku, jota kutsumme INT_MAX) vastaisi 2𝝅 radiaanin (tai 360 asteen) kulmaa, ja kaikki muut hash-arvot mahtuisivat lineaarisesti jonnekin siltä väliltä. Voisimme siis ottaa avaimen, laskea sen hash-arvon ja selvittää, missä se sijaitsee ympyrän reunalla. Olettaen, että INT_MAX on 1010 (esimerkin vuoksi), edellisen esimerkkimme avaimet näyttäisivät seuraavalta:
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| ”john” | 1633428562 | 58.8 |
| ”bill” | 7594634739 | 273.4 |
| ”jane” | 5000799124 | 180 |
| ”steve” | 9787173343 | 352.3 |
| ”kate” | 3421657995 | 123.2 |
Kuvitellaan nyt, että sijoitimme palvelimet myös ympyrän reunalle, antamalla myös niille pseudosattumanvaraisesti kulmat. Tämä pitäisi tehdä toistettavasti (tai ainakin niin, että kaikki asiakkaat ovat yhtä mieltä palvelimien kulmista). Kätevä tapa tehdä tämä on hashata palvelimen nimi (tai IP-osoite tai jokin tunnus) – kuten tekisimme mille tahansa muulle avaimelle – jotta saisimme selville sen kulman.
Esimerkissämme asiat voisivat näyttää tältä:
| 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 |
Koska meillä on sekä objektien että palvelimien avaimet samalla ympyrällä, voimme määritellä yksinkertaisen säännön, jolla ensin mainittu yhdistetään jälkimmäiseen: Kukin objektin avain kuuluu palvelimeen, jonka avain on lähimpänä, vastapäivään (tai myötäpäivään, riippuen käytetyistä konventioista). Toisin sanoen saadaksemme selville, miltä palvelimelta pyydämme tiettyä avainta, meidän on paikannettava avain ympyrästä ja liikuttava nousevan kulman suunnassa, kunnes löydämme palvelimen.
Esimerkissämme:
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| ”john” | 1633428562 | 58.7 |
| ”C” | 2269549488 | 81.7 |
| ”kate” | 3421657995 | 123.1 |
| ”jane” | 5000799124 | 180 |
| ”A” | 5572014557 | 200.5 |
| ”lasku” | 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 |
Ohjelmointinäkökulmasta katsottuna pitäisimme lajiteltua luetteloa palvelinarvoista (jotka voivat olla kulmia tai numeroita missä tahansa reaaliväleissä) ja kävisimme tätä luetteloa läpi (tai käyttäisimme binäärihakua) etsiessämme ensimmäisen palvelimen, jonka arvo on suurempi tai yhtä suuri kuin halutun avaimen arvo. Jos tällaista arvoa ei löydy, meidän on kierrettävä ympäri ja otettava luettelosta ensimmäinen.
Voidaksemme varmistaa, että objektin avaimet jakautuvat tasaisesti palvelimien kesken, meidän on sovellettava yksinkertaista temppua: Määritellä jokaiselle palvelimelle ei yhtä vaan monta tarraa (kulmaa). Niinpä sen sijaan, että meillä olisi nimilaput A, B ja C, meillä voisi olla vaikkapa A0 .. A9, B0 .. B9 ja C0 .. C9, jotka kaikki ovat ripoteltuina pitkin ympyrää. Tekijä, jolla tarrojen (palvelimen avainten) määrää lisätään, eli painoarvo, riippuu tilanteesta (ja voi olla jopa erilainen jokaisella palvelimella), jotta voidaan säätää avainten todennäköisyyttä päätyä kuhunkin palvelimeen. Jos esimerkiksi palvelin B olisi kaksi kertaa tehokkaampi kuin muut, sille voitaisiin antaa kaksi kertaa enemmän tarroja, minkä seurauksena sille päätyisi kaksi kertaa enemmän objekteja (keskimäärin).
Esimerkissämme oletamme, että kaikilla kolmella palvelimella on yhtä suuri painoarvo 10 (tämä toimii hyvin kolmelle palvelimelle, 10-50 palvelimelle painoarvo välillä 100-500 toimisi paremmin, ja suuremmat poolit saattavat tarvita vielä suurempia painoja):
| 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 | 180 | 180 | 180 | ”C7” | C |
| ”bill” | 7594873884 | 273.4 | ”A4” | A | |||
| ”steve” | 9786437450 | 352.3 | ”C6” | C |
Mikä hyöty tästä ympyrämenetelmästä on? Kuvitellaan, että palvelin C poistetaan. Tämän huomioon ottamiseksi meidän on poistettava ympyrästä tarrat C0 .. C9. Tämä johtaa siihen, että poistettujen etikettien vieressä aiemmin olleet objektiavaimet saavat nyt satunnaiset etiketit Ax ja Bx, jolloin ne osoitetaan uudelleen palvelimille A ja B.
Mutta mitä tapahtuu muille objektiavaimille, niille, jotka alun perin kuuluivat A:een ja B:een? Ei mitään! Se on asian hienous: Cx-merkintöjen puuttuminen ei vaikuta näihin avaimiin millään tavalla. Palvelimen poistaminen johtaa siis siihen, että sen objektiavaimet osoitetaan satunnaisesti uudelleen muille palvelimille, jolloin kaikki muut avaimet jäävät koskemattomiksi:
| 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 |
Samankaltaista tapahtuu, jos palvelimen poistamisen sijasta lisäämme palvelimen. Jos haluaisimme lisätä esimerkkiin palvelimen D (vaikkapa C:n tilalle), meidän olisi lisättävä tarrat D0 .. D9. Tuloksena olisi, että noin kolmannes nykyisistä avaimista (jotka kaikki kuuluvat A tai B) osoitettaisiin uudelleen D:lle, ja loput pysyisivät taas ennallaan:
| 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 |
Näin johdonmukainen hajautus (consistent hashing) ratkaisee uudelleensuuntausongelman.
Yleisesti vain k/N avainta täytyy uudelleenkartoittaa, kun k on avainten määrä ja N on palvelimien määrä (tarkemmin sanottuna palvelimien alku- ja loppumäärän maksimi).
Havaitsimme, että käytettäessä hajautettua välimuistitietovarastointia suorituskyvyn optimoimiseksi voi käydä niin, että välimuistitietovarastointipalvelimien määrä muuttuu (syynä voi olla palvelimen kaatuminen tai tarve lisätä tai poistaa palvelin yleiskapasiteetin lisäämiseksi tai vähentämiseksi). Käyttämällä johdonmukaista hajautusta avainten jakamiseen palvelimien välillä voimme olla varmoja siitä, että jos näin tapahtuu, uudelleen hajautettavien avainten määrä – ja siten vaikutus alkuperäpalvelimiin – minimoidaan, mikä estää mahdolliset käyttökatkokset tai suorituskykyongelmat.
Useille järjestelmille, kuten Memcachedille ja Redisille, on olemassa asiakkaita, jotka tukevat johdonmukaista hajautusta jo valmiiksi.
Vaihtoehtoisesti voit toteuttaa algoritmin itse valitsemallasi kielellä, ja sen pitäisi olla suhteellisen helppoa, kunhan käsite on ymmärretty.
Jos datatiede kiinnostaa sinua, Toptalin blogissa
on joitakin parhaita artikkeleita aiheesta.