Конзистентан хеш

Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу.
Када завршите са провером, допишете да након |проверено=.

Конзистентан хеш је посебна врста хеширања таква да, у случају када се величина хеш табеле мења уз примену конзистентног хеширања, само $K/n$ кључева треба да се у просеку мапирају (пресликају), при чему је $K$ је број кључева, а $n$ број места. Насупрот овоме, у већини традиционалних хеш табела промена броја места у низу резултује поновним мапирањем готово свих кључева.

Конзистентним хеширањем се постижу исти циљеви као и Рендезвоус хеширањем (које се још назива и ХРW хеширање). Ове две технике користе разичите алгоритме, и развијене су у исто време, независно једна од друге.

Историја уреди

Идеја, коју су првобитно развили Каргер и други на МИТ-у за употребоу приликом дистрибуираног хеширања, се сада примењује и у другим областима. У раду објављеном 1997. први пут се спомиње израз „конзистентно хеширање“ које означава начин на који се дистрибуирају захтеви међу променљивом популацијом веб сервера. Свако место је представљен нодом у дистрибуираном систему. Додавање (приступи) и уклањање (напуштања/кварови) чворова захтева једино да се $K/n$ ставки поново измеша када се број слотова/чворова промени^[1]

Конзистентно хеширање се користи и за смањење утицаја делимичних кварова система у великим веб апликацијама како би се омогућио велики кеш без испадања читавог система.^[2]

Концепт конзистентног хеширања се примењује приликом израде дистибуираних хеш табела (ДХТс). Ове табеле користе конзистентно хеширање да изделе простор са кључевима међу дистрибуираним скупом чворова, и обезбеде мрежу преклапања која спаја чворове на такав начин да се нод одговоран за сваки од кључева може брзо пронаћи.

Рендезвоус хеширање, створено у исто време кад и конзистентно хеширање, постиже исте резултате употребом веома другачијег алгоритма, под називом Највећа насумична тежина (енгл.Хигхест Рандом Wеигхт, ХРW).

Потреба за конзистентним хеширањем уреди

Извесна ограничења се могу сусрести приликом рада колекција машина за хеширање. Уобичајени начин балансирања оптерећења $n$ кеш машина састоји се од стављања објекта $o$ у број кеш машине ${\mbox{hash}}(o)\mod n$ . Међутим, ово неће успети уколико се кеш машина додаје или одузима, јер се $n$ мења и сваки објекат се хешира на нову локацију. Ово може довести до катастрофалних последица пошто кеш машине у том случају преплављују захтевима сервере на којима се ствара садржај.

Конзистентно хеширање мапира објекте на исту кеш машину, колико год је то могуће. То значи да, када се дода кеш машина, она преузима свој део објеката од свих других кеш машина, а када се она уклони, њени објекти се расподеле међу преосталим кеш машинама.

Основи алгоритма конзистентног хеширања су придодавање једног или више интервала хеш вредности сваком кешу, при чему су границе интервала одређене израчунавањем хеша за сваки идентификатор кеша. (Хеш функција која се користи за одређивање интервала не мора бити идентична функцији којом се хеширају кеширане вредности. Само се распони тих двеју функција морају подударати.) Ако се кеш уклони, његов интервал преузима кеш са суседним интервалом. Сви остали кешеви остају неизмењен

Техника уреди

Конзистетно хеширање се заснива на мапирању сваког објекта на тачки кружнице (или мапирању сваког објекта на под одговарајућим углом). Систем мапира сваку доступну машину (или друго складишно место) на много привидно насумично дистрибуираних тачака на кружници једног круга. Да би пронашао место где објекат треба бити постављен, систем проналази локацију кључа тог објекта на кружници; потом иде низ кружницу док не упадне у прво место које пронађе (или прво доступно менсто са већим углом). Као резултат тога, свако место садржи све ресурсе смештене између своје тачке и тачке претходног места. Уколико место постане недоступно (на пример, зато што копмјутер на којем се налази није доступан), онда ће углови под којима се мапира бити уклоњени. Захтеви за ресурсима који би се мапирали на сваку од ових тачака се сада мапирају на следећу највишу тачку. Пошто је свако место повезано са много привидно насумично дистрибуираним тачкама, ресурси који су се налазили на том месту ће се сада мапирати на више различитих места. Ставке које су се мапирале на изгубљено место морају бити прерасподељене на преосталим местима, али ће вредности које се мапирају на друга места се неће мењати и остаће на истом месту. Сличан процес се дешава када се дода место. Додавањем места приморавамо све ресурсе који могу постојати између тог и следећег мањег угла да се мапирају на ново место. Ови рсурси неће више бити повезани са претходним местом, и свака вредност која је раније ту била похрањена неће бити пронађена већ описаним методом селекције. Део кључева повезаних са сваким од места може се мењати променом броја углова на које се то место мапира.

Монотони кључеви уреди

Уколико се зна да ће вредности кључева стално монотоно расти, алтернативни приступ конзистентном хеширању је могућ.

Карактеристике уреди

Дејвид Каргер и остали наводе неколико карактеристика конзистентног хеширања које га чине корисним за дитрибуиране протоколе кеширања на интернету:^[1]

"раширено"
"оптерећење(унос)"
"глаткост"
"равнотежа"
"монотоно"

Примери где се користи уреди

Неки познати случајеви где се конзистентно хеширање користи су:

Опенстацк'с Објецт Стораге Сервице Сwифт.^[3]
Партитионинг цомпонент оф Амазон'с стораге сyстем Дyнамо.^[4]
Дата партитионинг ин Апацхе Цассандра.^[5]
Акка'с цонсистент хасхинг роутер.^[6]

Референце уреди

^ ^а ^б Каргер, D.; Лехман, Е.; Леигхтон, Т.; Паниграхy, Р.; Левине, M.; Леwин, D. (1997). „Цонсистент Хасхинг анд Рандом Треес: Дистрибутед Цацхинг Протоцолс фор Релиевинг Хот Спотс он тхе Wорлд Wиде Wеб”. Процеедингс оф тхе Тwентy-нинтх Аннуал АЦМ Сyмпосиум он Тхеорy оф Цомпутинг. АЦМ Пресс Неw Yорк, НY, УСА. стр. 654—663. дои:10.1145/258533.258660.
^ Каргер, D.; Схерман, А.; Беркхеимер, А.; Богстад, Б.; Дханидина, Р.; Иwамото, К.; Ким, Б.; Маткинс, L.; Yерусхалми, Y. (1999). „Wеб Цацхинг wитх Цонсистент Хасхинг”. Цомпутер Нетwоркс. 31 (11): 1203—1213. дои:10.1016/С1389-1286(99)00055-9. Архивирано из оригинала 21. 07. 2008. г. Приступљено 19. 03. 2014.
^ Партитионед Цонсистент Хасх Ринг — сwифт 2.7.1.дев78 доцументатион
^ ДеЦандиа, Г.; Хасторун, D.; Јампани, M.; Какулапати, Г.; Лаксхман, А.; Пилцхин, А.; Сивасубраманиан, С.; Воссхалл, П.; Вогелс, W. (2007). „Дyнамо: Амазон'с Хигхлy Аваилабле Кеy-Валуе Сторе”. Процеедингс оф тхе 21ст АЦМ Сyмпосиум он Оператинг Сyстемс Принциплес.
^ Лаксхман, Авинасх; Малик, Прасхант (2010). „Цассандра: а децентрализед струцтуред стораге сyстем”. АЦМ СИГОПС Оператинг Сyстемс Ревиеw.
^ Акка Роутинг

Спољашње везе уреди

Разумевање Конзистентног Хеширања
Имплементација на разним језицима:
- C++ Архивирано на сајту Wayback Machine (16. новембар 2020)
- C#
- Ерланг
- Го
- Јава
- ПХП
- Пyтхон
- Рубy

[KargerEtAl1997-1] а ^б Каргер, D.; Лехман, Е.; Леигхтон, Т.; Паниграхy, Р.; Левине, M.; Леwин, D. (1997). „Цонсистент Хасхинг анд Рандом Треес: Дистрибутед Цацхинг Протоцолс фор Релиевинг Хот Спотс он тхе Wорлд Wиде Wеб”. Процеедингс оф тхе Тwентy-нинтх Аннуал АЦМ Сyмпосиум он Тхеорy оф Цомпутинг. АЦМ Пресс Неw Yорк, НY, УСА. стр. 654—663. дои:10.1145/258533.258660.

[KargerEtAl1999-2] Каргер, D.; Схерман, А.; Беркхеимер, А.; Богстад, Б.; Дханидина, Р.; Иwамото, К.; Ким, Б.; Маткинс, L.; Yерусхалми, Y. (1999). „Wеб Цацхинг wитх Цонсистент Хасхинг”. Цомпутер Нетwоркс. 31 (11): 1203—1213. дои:10.1016/С1389-1286(99)00055-9. Архивирано из оригинала 21. 07. 2008. г. Приступљено 19. 03. 2014.

[3] Партитионед Цонсистент Хасх Ринг — сwифт 2.7.1.дев78 доцументатион

[Amazon2007-4] ДеЦандиа, Г.; Хасторун, D.; Јампани, M.; Какулапати, Г.; Лаксхман, А.; Пилцхин, А.; Сивасубраманиан, С.; Воссхалл, П.; Вогелс, W. (2007). „Дyнамо: Амазон'с Хигхлy Аваилабле Кеy-Валуе Сторе”. Процеедингс оф тхе 21ст АЦМ Сyмпосиум он Оператинг Сyстемс Принциплес.

[Lakshman2010b-5] Лаксхман, Авинасх; Малик, Прасхант (2010). „Цассандра: а децентрализед струцтуред стораге сyстем”. АЦМ СИГОПС Оператинг Сyстемс Ревиеw.

[akka-routing-6] Акка Роутинг

[1]

[2]

[3]

[4]

[5]

[6]