Въведение
Алгоритъмът за последователно хеширане беше предложен в статията Consistentthashinganddomtrees през 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.
Принцип на работа
Алгоритъмът за последователно хеширане е един от текущите масови протоколи за разпределени хеш таблици. Той модифицира простия хеш алгоритъм и решава проблема с hotPot ), принципът му е разделен на две стъпки:
Първо се изчислява хеш-стойността на възела за съхранение, което абстрахира пространството за съхранение в пръстен и конфигурира възела за съхранение на пръстена. Всички възли на пръстена имат стойност. Второ, хеширайте данните и ги картографирайте към най-близкия възел по посока на часовниковата стрелка. Когато даден възел се повреди офлайн, според метода на картографиране на алгоритъма, се засягат само обектите с данни в интервала между дефектния възел на пръстена и следващия възел, а самите тези обекти се картографират към дефектния възел. . Когато има увеличение на възлите, например добавяне на възел H между възли A и B, само обектите с данни между възел H се движат обратно на часовниковата стрелка, докато B бъдат засегнати, и те се пренасочват към H. Следователно, когато възел се промени, данните за цялото пространство за съхранение няма да бъдат преназначени, което решава проблема с неефективността, причинена от простия хеш алгоритъм за добавяне или изтриване на възли и пренасочване на всички данни.
Като важен алгоритъм в областта на разпределеното съхранение, последователният хеш алгоритъм основно решава ключов проблем в средата за съхранение, представена от P2P - как да се извърши обработка на данни в динамична мрежова топология. Разпределете и изберете маршрутизиране. В топологията за съхранение, формирана от алгоритъма, всеки възел за съхранение трябва само да поддържа малко количество информация за съседните възли и когато възел се присъедини/напусне системата, само малък брой свързани възли участват в поддръжката на топологията, което прави последователност Гръцкият алгоритъм се превърна в практичен DHT (DistributedHashTable) алгоритъм. Но последователният алгоритъм за хеширане все още има своите недостатъци. Първо, в процеса на заявка съобщението за заявка трябва да премине през O(n) стъпки (n представлява общия брой възли в системата), за да достигне до запитвания възел. Не е трудно да си представим, че когато мащабът на системата е много голям, броят на възлите може да надхвърли един милион и такава ефективност на заявките очевидно е трудно да отговори на нуждите на използване. Второ, когато се добави или изтрие нов физически възел в разпределена система за съхранение, която използва последователен алгоритъм за хеширане, данните, свързани със следващия възел, трябва да бъдат мигрирани и честотата на попадение на заявката и ефективността на съхранението ще намалеят, засягайки цялостната система. Производителност.
Връзката с хеш алгоритъма
Последователният хеш алгоритъм е предложен на базата на хеш алгоритъма. В динамично променяща се разпределена среда алгоритъмът за хеширане трябва да отговаря на няколко условия: баланс, монотонност и дисперсия.
①Балансирането означава, че резултатът от хеша трябва да бъде равномерно разпределен към всеки възел, което решава проблема с балансирането на натоварването алгоритмично.
② Монотонност означава, че при добавяне или изтриване на възли това не влияе на нормалната работа на системата.
③Децентрализацията означава, че данните трябва да се съхраняват разпръснато на всеки възел в разпределен клъстер (самите възли могат да имат резервни копия) и не е необходимо всеки възел да съхранява всички данни.
Предимства
Мащабируемост. Последователният алгоритъм за хеширане гарантира, че когато сървърите се добавят или намаляват, промените в съхранението на данни са най-малко, което значително спестява разходите за движение на данни в сравнение с традиционните алгоритми за хеширане.
За по-добра адаптация към бързия растеж на данните. Използвайте последователен алгоритъм за хеширане за разпространение на данни. Когато данните продължават да растат, някои виртуални възли може да съдържат много данни, което води до неравномерно разпределение на данните във виртуалните възли. По това време виртуални възли с много данни могат да бъдат разделени. Това разделяне е само. То разделя оригиналния виртуален възел на две без повторно хеширане и разделяне на всички данни. След като виртуалният възел е разделен, ако натоварването на физическия сървър все още е небалансирано, трябва само да коригирате разпределението на съхранението на някои виртуални възли между сървърите. По този начин броят на физическите сървъри може да се разширява динамично с нарастването на данните, а цената е много по-малка от преразпределението на всички данни чрез традиционните хеш алгоритми.
Приложение
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.
Системата HepyCloud приема подобрен последователен алгоритъм за хеширане, за да постигне равномерно разпределение и бързо позициониране на данните. При избора на хеш функция, тя се разглежда главно от следните два аспекта: (1) Ефективност на работата; ( 2) Хешът е еднороден. Оперативна ефективност означава, че избраната хеш функция има висока изчислителна ефективност, реализира бързо позициониране на данни и постига добро потребителско изживяване; Hash uniform означава, че избраната хеш функция има добро разпределение, което гарантира, че данните се съхраняват равномерно разпределение на устройството. Алгоритъмът на Дейвис-Майер е по-добър избор. От една страна, ефективната ефективност на работа осигурява бързо позициониране на данните; от друга страна, равномерното хеш разпределение осигурява равномерно разпределение на данните. От гледна точка на действителната употреба, подобреният последователен хеш и алгоритъмът на Дейвис-Майер се прилагат към системата HepyCloud, за да се реализира равномерното разпределение на данните на устройството за съхранение. Системата разполага с 23 устройства за съхранение с капацитет за съхранение от 186TB и 14478054 файла. Броят на файловете на всяко устройство е около 629410 (общ брой файлове/брой устройства). По отношение на позиционирането на данните, след тестване и действително използване, неговата производителност е сравнима с други разпределени файлови системи и е достатъчна, за да отговори на изискванията за производителност на системата за съхранение.