Konzistentan heš

Konzistentan heš je posebna vrsta heširanja takva da, u slučaju kada se veličina heš tabele menja uz primenu konzistentnog heširanja, samo $K/n$ ključeva treba da se u proseku mapiraju (preslikaju), pri čemu je $K$ je broj ključeva, a $n$ broj mesta. Nasuprot ovome, u većini tradicionalnih heš tabela promena broja mesta u nizu rezultuje ponovnim mapiranjem gotovo svih ključeva.

Konzistentnim heširanjem se postižu isti ciljevi kao i Rendezvous heširanjem (koje se još naziva i HRW heširanje). Ove dve tehnike koriste razičite algoritme, i razvijene su u isto vreme, nezavisno jedna od druge.

Istorija

Ideja, koju su prvobitno razvili Karger i drugi na MIT-u za upotrebou prilikom distribuiranog heširanja, se sada primenjuje i u drugim oblastima. U radu objavljenom 1997. prvi put se spominje izraz „konzistentno heširanje“ koje označava način na koji se distribuiraju zahtevi među promenljivom populacijom veb servera. Svako mesto je predstavljen nodom u distribuiranom sistemu. Dodavanje (pristupi) i uklanjanje (napuštanja/kvarovi) čvorova zahteva jedino da se $K/n$ stavki ponovo izmeša kada se broj slotova/čvorova promeni

Konzistentno heširanje se koristi i za smanjenje uticaja delimičnih kvarova sistema u velikim veb aplikacijama kako bi se omogućio veliki keš bez ispadanja čitavog sistema.

Koncept konzistentnog heširanja se primenjuje prilikom izrade distibuiranih heš tabela (DHTs). Ove tabele koriste konzistentno heširanje da izdele prostor sa ključevima među distribuiranim skupom čvorova, i obezbede mrežu preklapanja koja spaja čvorove na takav način da se nod odgovoran za svaki od ključeva može brzo pronaći.

Rendezvous heširanje, stvoreno u isto vreme kad i konzistentno heširanje, postiže iste rezultate upotrebom veoma drugačijeg algoritma, pod nazivom Najveća nasumična težina (engl.Highest Random Weight, HRW).

Potreba za konzistentnim heširanjem

Izvesna ograničenja se mogu susresti prilikom rada kolekcija mašina za heširanje. Uobičajeni način balansiranja opterećenja $n$ keš mašina sastoji se od stavljanja objekta $o$ u broj keš mašine ${\mbox{hash}}(o)\mod n$. Međutim, ovo neće uspeti ukoliko se keš mašina dodaje ili oduzima, jer se $n$ menja i svaki objekat se hešira na novu lokaciju. Ovo može dovesti do katastrofalnih posledica pošto keš mašine u tom slučaju preplavljuju zahtevima servere na kojima se stvara sadržaj.

Konzistentno heširanje mapira objekte na istu keš mašinu, koliko god je to moguće. To znači da, kada se doda keš mašina, ona preuzima svoj deo objekata od svih drugih keš mašina, a kada se ona ukloni, njeni objekti se raspodele među preostalim keš mašinama.

Osnovi algoritma konzistentnog heširanja su pridodavanje jednog ili više intervala heš vrednosti svakom kešu, pri čemu su granice intervala određene izračunavanjem heša za svaki identifikator keša. (Heš funkcija koja se koristi za određivanje intervala ne mora biti identična funkciji kojom se heširaju keširane vrednosti. Samo se rasponi tih dveju funkcija moraju podudarati.) Ako se keš ukloni, njegov interval preuzima keš sa susednim intervalom. Svi ostali keševi ostaju neizmenjen

Tehnika

Konzistetno heširanje se zasniva na mapiranju svakog objekta na tački kružnice (ili mapiranju svakog objekta na pod odgovarajućim uglom). Sistem mapira svaku dostupnu mašinu (ili drugo skladišno mesto) na mnogo prividno nasumično distribuiranih tačaka na kružnici jednog kruga. Da bi pronašao mesto gde objekat treba biti postavljen, sistem pronalazi lokaciju ključa tog objekta na kružnici; potom ide niz kružnicu dok ne upadne u prvo mesto koje pronađe (ili prvo dostupno mensto sa većim uglom). Kao rezultat toga, svako mesto sadrži sve resurse smeštene između svoje tačke i tačke prethodnog mesta. Ukoliko mesto postane nedostupno (na primer, zato što kopmjuter na kojem se nalazi nije dostupan), onda će uglovi pod kojima se mapira biti uklonjeni. Zahtevi za resursima koji bi se mapirali na svaku od ovih tačaka se sada mapiraju na sledeću najvišu tačku. Pošto je svako mesto povezano sa mnogo prividno nasumično distribuiranim tačkama, resursi koji su se nalazili na tom mestu će se sada mapirati na više različitih mesta. Stavke koje su se mapirale na izgubljeno mesto moraju biti preraspodeljene na preostalim mestima, ali će vrednosti koje se mapiraju na druga mesta se neće menjati i ostaće na istom mestu. Sličan proces se dešava kada se doda mesto. Dodavanjem mesta primoravamo sve resurse koji mogu postojati između tog i sledećeg manjeg ugla da se mapiraju na novo mesto. Ovi rsursi neće više biti povezani sa prethodnim mestom, i svaka vrednost koja je ranije tu bila pohranjena neće biti pronađena već opisanim metodom selekcije. Deo ključeva povezanih sa svakim od mesta može se menjati promenom broja uglova na koje se to mesto mapira.

Monotoni ključevi

Ukoliko se zna da će vrednosti ključeva stalno monotono rasti, alternativni pristup konzistentnom heširanju je moguć.

Karakteristike

Dejvid Karger i ostali navode nekoliko karakteristika konzistentnog heširanja koje ga čine korisnim za ditribuirane protokole keširanja na internetu:

• "rašireno"
• "opterećenje(unos)"
• "glatkost"
• "ravnoteža"
• "monotono"

Primeri gde se koristi

Neki poznati slučajevi gde se konzistentno heširanje koristi su:

1. Openstack's Object Storage Service Swift.
2. Partitioning component of Amazon's storage system Dynamo.
3. Data partitioning in Apache Cassandra.
4. Akka's consistent hashing router.

Spoljašnje veze

• Razumevanje Konzistentnog Heširanja
• Implementacija na raznim jezicima:
  • C++ Архивирано на сајту Wayback Machine (16. новембар 2020)
  • C#
  • Erlang
  • Go
  • Java
  • PHP
  • Python
  • Ruby