Увод
Конзистентни алгоритам хеширања је предложен у раду Цонсистенттхасхингандрандомтреес 1997. године и широко се користи у дистрибуираним системима. Конзистентно хеширање је врста алгоритма хеширања. Једноставно речено, приликом уклањања или додавања сервера, овај алгоритам може што мање променити однос мапирања између постојећег захтева за услугу и сервера захтева за обраду, како би се што више задовољила монотоност. Сексуални захтеви. У обичном дистрибуираном кластеру може постојати једна-на-један кореспонденција између захтева за услугом и сервера захтева за обраду, што значи да је однос мапирања између захтева за услугу и сервера за обраду фиксан, а одређени захтев обрађује фиксни сервер. Овај метод не може да избалансира оптерећење целог система и може довести до тога да неки сервери буду презаузети за обраду нових захтева. Други сервери су превише неактивни, коришћење ресурса целокупног система је ниско, а када се сервер у дистрибуираном кластеру поквари, неки захтеви за услугу не могу да се обрађују директно.
Даља побољшања могу користити хеш алгоритам за мапирање односа између захтева за услугу и сервера за обраду како би се постигла сврха динамичке алокације. Захтев за услугу се конвертује преко хеш алгоритма, а конвертовани резултат је модуло операција на вредности чвора сервера, а модуло вредност је сервер за обраду захтева који одговара захтеву за услугу. Овај метод може да се носи са отказом чвора. Када се чвор дистрибуираног кластера поквари, захтеви за услугу могу се редистрибуирати на друге доступне сервере путем хеш алгоритма. Тиме се избегава ситуација у којој се захтев не може обрадити.
Али недостаци ове методе су такође очигледни. Ако сервер сачува податке који одговарају захтеву за услугу, ако се поново израчуна хеш вредност захтева, велики број захтева ће бити измештен на различите сервере. Узрокује да подаци које користи захтев буду неважећи, што је веома лоше у дистрибуираном систему. Добро дизајниран дистрибуирани систем треба да има добру монотоност, односно додавање и уклањање сервера неће изазвати велики број хеш премештања, а доследно хеширање може само да реши овај проблем.
The consistent hash algorithm maps the entire hash value space into a virtual circle, and the value range of the entire hash space is 0~232-1. The entire space is organized in a clockwise direction. 0~232-1 coincides in the direction of the zero point. Next, use the following algorithm to map the service request, use the hash algorithm to calculate the corresponding hash value of the service request, and then look up clockwise along the circle according to the location of the hash value. The first server encountered is the corresponding processing request Server. When a new server is added, the affected data is only the data between the newly added server and the previous server in its ring space (that is, the first server encountered in the counterclockwise direction), and everything else Will not be affected. To sum up, the consistent hash algorithm only needs to relocate a small part of the data in the ring space for the increase or decrease of nodes, which has good fault tolerance and scalability.
Принцип рада
Конзистентни хеш алгоритам је један од тренутних маинстреам дистрибуираних хеш табела протокола. Модификује једноставан хеш алгоритам и решава проблем хотПот, његов принцип је подељен у два корака:
Прво се израчунава хеш вредност чвора за складиштење, чиме се простор за складиштење апстрахује у прстен и конфигурише чвор за складиштење на прстену. Сви чворови на прстену имају вредност. Друго, хеширајте податке и мапирајте их до најближег чвора у смеру казаљке на сату. Када чвор не успе ван мреже, према методи мапирања алгоритма, утичу само на објекте података у интервалу између неисправног чвора на прстену и следећег чвора, а ови објекти се сами мапирају у неисправни чвор. . Када дође до повећања чворова, на пример, додавањем чвора Х између чворова А и Б, само објекти података између чвора Х крећу се у смеру супротном од казаљке на сату док то не утиче на Б, и они се поново мапирају у Х. Стога, када се чвор промени, подаци о читавом простору за складиштење неће бити поново мапирани, што решава проблем неефикасности узроковане једноставним хеш алгоритмом за додавање или брисање чворова и поновно мапирање свих података.
Као важан алгоритам у области дистрибуираног складиштења, конзистентни хеш алгоритам у основи решава кључни проблем у окружењу за складиштење који представља П2П-како извршити обраду података у динамичкој топологији мреже. Дистрибуирајте и изаберите рутирање. У топологији складиштења коју формира алгоритам, сваки складишни чвор треба да одржава само малу количину информација о суседним чворовима, а када се чвор придружи/напусти систему, само мали број повезаних чворова учествује у одржавању топологије, што чини доследност Грчки алгоритам је постао практичан ДХТ (ДистрибутедХасхТабле) алгоритам. Али доследни алгоритам хеширања и даље има своје недостатке. Прво, у процесу упита, порука упита мора да прође кроз О(н) корака (н представља укупан број чворова у систему) да би стигла до чвора за који се поставља упит. Није тешко замислити да када је обим система веома велики, број чворова може да пређе милион, а таква ефикасност упита очигледно тешко задовољава потребе употребе. Друго, када се дода или избрише нови физички чвор у дистрибуираном систему складиштења који користи конзистентан хеш алгоритам, подаци који се односе на следећи чвор морају да се мигрирају, а стопа погодака упита и ефикасност складиштења ће се смањити, што ће утицати на цео систем. Перформансе.
Однос са хеш алгоритмом
Конзистентан хеш алгоритам је предложен на основу хеш алгоритма. У динамички променљивом дистрибуираном окружењу, хеш алгоритам треба да задовољи неколико услова: равнотежу, монотоност и дисперзију.
①Балансирање значи да резултат хеша треба да буде равномерно распоређен на сваки чвор, што алгоритамски решава проблем балансирања оптерећења.
② Монотоничност значи да приликом додавања или брисања чворова то не утиче на нормалан рад система.
③Децентрализација значи да подаци треба да се складиште дисперзовано на сваком чвору у дистрибуираном кластеру (чворови могу сами да имају резервне копије), и није неопходно да сваки чвор чува све податке.
Предности
Прилагодљивост. Доследан алгоритам хеширања обезбеђује да када се сервери додају или смање, промене складиштења података буду најмање, што у великој мери штеди трошкове кретања података у поређењу са традиционалним алгоритмима хеширања.
Да би се боље прилагодили брзом расту података. Користите доследан алгоритам хеширања за дистрибуцију података. Када подаци наставе да расту, неки виртуелни чворови могу да садрже много података, што доводи до неравномерне дистрибуције података на виртуелним чворовима. У овом тренутку, виртуелни чворови са пуно података могу се поделити. Ова подела је само. Она дели оригинални виртуелни чвор на два без поновног хеширања и дељења свих података. Након што се виртуелни чвор подели, ако је оптерећење физичког сервера и даље неуравнотежено, потребно је само да прилагодите дистрибуцију складишта неких виртуелних чворова међу серверима. На овај начин се број физичких сервера може динамички проширивати са растом података, а цена је много мања од прерасподеле свих података традиционалним хеш алгоритмима.
Апликација
The distributed storage system HepyCloud is a massive data storage system independently developed by the Institute of High Energy, Chinese Academy of Sciences. The system uses key-value technology. Realize the fast storage, positioning and high scalability of massive data, and support EB-level storage. The system proposes the idea of a unified layout and improves the consistent hash algorithm.
ХепиЦлоуд систем усваја побољшани конзистентни алгоритам хеширања како би се постигла уједначена дистрибуција и брзо позиционирање података. Приликом избора хеш функције она се углавном разматра са следећа два аспекта: (1) Оперативна ефикасност; (2) Хеш је уједначен. Оперативна ефикасност значи да изабрана хеш функција има високу рачунарску ефикасност, остварује брзо позиционирање података и постиже добро корисничко искуство; Хасх униформ значи да изабрана хеш функција има добру дистрибуцију, обезбеђујући да се подаци чувају Равномерна дистрибуција на уређају. Давиес-Меиер алгоритам је бољи избор. С једне стране, ефикасна радна ефикасност обезбеђује брзо позиционирање података; с друге стране, униформна хеш дистрибуција обезбеђује равномерну дистрибуцију података. Са становишта стварне употребе, побољшани конзистентни хеш и Давиес-Меиер алгоритам се примењују на ХепиЦлоуд систем да би се остварила равномерна дистрибуција података на уређају за складиштење. Систем има 23 уређаја за складиштење капацитета 186ТБ и 14478054 датотека. Број датотека на сваком уређају је око 629410 (укупан број датотека/број уређаја). У погледу позиционирања података, након тестирања и стварне употребе, његове перформансе су упоредиве са другим дистрибуираним системима датотека и довољне су да задовоље захтеве перформанси система за складиштење података.