Úvod
Konzistentní hashovací algoritmus byl navržen v článku Consistentthashingandrandomtrees v roce 1997 a je široce používán v distribuovaných systémech. Konzistentní hašování je druh hašovacího algoritmu. Jednoduše řečeno, při odebírání nebo přidávání serveru může tento algoritmus co možná nejméně změnit vztah mapování mezi existujícím požadavkem na službu a serverem pro zpracování požadavku, aby byla co nejvíce uspokojena monotónnost. Sexuální požadavky. V běžném distribuovaném clusteru může existovat vzájemná korespondence mezi požadavky na služby a servery pro zpracování požadavků, což znamená, že vztah mapování mezi požadavky na služby a servery pro zpracování je pevný a určitý požadavek je zpracováván pevným serverem. Tato metoda nedokáže vyvážit zatížení celého systému a může způsobit, že některé servery budou příliš zaneprázdněné, aby mohly zpracovávat nové požadavky. Jiné servery jsou příliš nečinné, využití zdrojů celého systému je nízké a když dojde k výpadku serveru v distribuovaném clusteru, některé servisní požadavky nelze zpracovat přímo.
Další vylepšení mohou využít hašovací algoritmus k mapování vztahu mezi požadavkem na službu a zpracovávajícím serverem k dosažení účelu dynamické alokace. Požadavek na službu je konvertován pomocí hašovacího algoritmu a konvertovaným výsledkem je operace modulo na hodnotě uzlu serveru a hodnota modulo je server pro zpracování požadavku odpovídající požadavku na službu. Tato metoda si dokáže poradit se selháním uzlu. Když dojde k výpadku distribuovaného uzlu clusteru, mohou být požadavky na služby redistribuovány na jiné dostupné servery pomocí algoritmu hash. Vyhnete se tak situaci, kdy nelze žádost zpracovat.
Nedostatky této metody jsou ale také zřejmé. Pokud server uloží data odpovídající požadavku na službu, pokud se přepočítá hodnota hash požadavku, velké množství požadavků bude přemístěno na různé servery. Způsobuje, že data, která mají být použita žádostí, jsou neplatná, což je v distribuovaném systému velmi špatné. Dobře navržený distribuovaný systém by měl mít dobrou monotónnost, to znamená, že přidávání a odebírání serverů nezpůsobí velké množství přemístění hashů a důsledné hashování může tento problém vyřešit.
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.
Princip fungování
Konzistentní hashovací algoritmus je jedním ze současných běžných protokolů distribuovaných hashovacích tabulek. Upravuje jednoduchý hashovací algoritmus a řeší problém hotPot, jeho princip je rozdělen do dvou kroků:
Nejprve se vypočítá hodnota hash storage nodu, která abstrahuje úložný prostor do kruhu a nakonfiguruje storage node na kruhu. Všechny uzly na kruhu mají hodnotu. Za druhé, hashujte data a namapujte je na nejbližší uzel ve směru hodinových ručiček. Když uzel selže offline, podle metody mapování algoritmu jsou ovlivněny pouze datové objekty v intervalu mezi vadným uzlem v kruhu a následujícím uzlem a tyto objekty samy jsou mapovány na vadný uzel. . Když dojde k nárůstu uzlů, například přidáním uzlu H mezi uzly A a B, pouze datové objekty mezi uzlem H projdou proti směru hodinových ručiček, dokud nebudou ovlivněny B, a ty se přemapují na H. Proto, když se uzel změní, data na celém úložném prostoru nebudou přemapována, což řeší problém neefektivity způsobený jednoduchým hashovacím algoritmem pro přidání nebo odstranění uzlů a přemapování všech dat.
Konzistentní hashovací algoritmus jako důležitý algoritmus v oblasti distribuovaného úložiště v zásadě řeší klíčový problém v prostředí úložiště reprezentovaný P2P způsobem zpracování dat v dynamické topologii sítě. Distribuujte a vyberte směrování. V topologii úložiště tvořené algoritmem potřebuje každý uzel úložiště pouze udržovat malé množství informací o sousedních uzlech, a když se uzel připojí/opustí systém, na údržbě topologie se podílí pouze malý počet souvisejících uzlů, což zajišťuje konzistenci Řecký algoritmus se stal praktickým algoritmem DHT (DistributedHashTable). Ale konzistentní hashovací algoritmus má stále své nedostatky. Nejprve v procesu dotazování musí zpráva s dotazem projít O(n) kroků (n představuje celkový počet uzlů v systému), aby dosáhla dotazovaného uzlu. Není těžké si představit, že když je rozsah systému velmi velký, počet uzlů může překročit jeden milion a taková efektivita dotazů je samozřejmě obtížné splnit potřeby použití. Za druhé, když je v distribuovaném úložném systému, který používá konzistentní hashovací algoritmus, přidán nebo odstraněn nový fyzický uzel, musí být migrována data související s dalším uzlem a sníží se četnost dotazů a efektivita úložiště, což ovlivní celý systém. Výkon.
Vztah s hashovacím algoritmem
Na základě hašovacího algoritmu je navržen konzistentní hashovací algoritmus. V dynamicky se měnícím distribuovaném prostředí by měl hashovací algoritmus splňovat několik podmínek: rovnováha, monotónnost a disperze.
①Vyvažování znamená, že výsledek hash by měl být rovnoměrně distribuován do každého uzlu, což řeší problém vyrovnávání zátěže algoritmicky.
② Monotónnost znamená, že při přidávání nebo odstraňování uzlů to neovlivňuje normální provoz systému.
③Decentralizace znamená, že data by měla být uložena rozptýleně na každém uzlu v distribuovaném clusteru (uzly mohou mít samy zálohy) a není nutné, aby každý uzel ukládal všechna data.
Výhody
Škálovatelnost. Konzistentní hashovací algoritmus zajišťuje, že když jsou servery přidávány nebo redukovány, změny úložiště dat jsou nejmenší, což výrazně šetří režii přesunu dat ve srovnání s tradičními hashovacími algoritmy.
Aby se lépe přizpůsobili rychlému nárůstu dat. K distribuci dat použijte konzistentní hashovací algoritmus. Když data neustále rostou, některé virtuální uzly mohou obsahovat velké množství dat, což má za následek nerovnoměrné rozložení dat na virtuálních uzlech. V tuto chvíli lze rozdělit virtuální uzly s velkým množstvím dat. Toto rozdělení je pouze Rozdělí původní virtuální uzel na dva bez opětovného hašování a rozdělení všech dat. Pokud je po rozdělení virtuálního uzlu zatížení fyzického serveru stále nevyvážené, stačí upravit rozložení úložiště některých virtuálních uzlů mezi servery. Tímto způsobem lze počet fyzických serverů dynamicky rozšiřovat s růstem dat a náklady jsou mnohem menší než redistribuce všech dat tradičními hashovacími algoritmy.
aplikace
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.
Systém HepyCloud využívá vylepšený konzistentní hašovací algoritmus pro dosažení jednotné distribuce a rychlého umístění dat. Při výběru hashovací funkce se posuzuje především z následujících dvou hledisek: (1) Provozní efektivita; (2) Hash je jednotný. Provozní efektivita znamená, že vybraná hashovací funkce má vysokou výpočetní efektivitu, realizuje rychlé umístění dat a dosahuje dobré uživatelské zkušenosti; hash uniform znamená, že vybraná hašovací funkce má dobré rozložení, což zajišťuje uložení dat Rovnoměrné rozložení na zařízení. Davies-Meyerův algoritmus je lepší volbou. Na jedné straně efektivní provozní efektivita zajišťuje rychlé umístění dat; na druhou stranu jednotné rozložení hash zajišťuje rovnoměrné rozložení dat. Z hlediska skutečného použití je na systém HepyCloud aplikován vylepšený konzistentní hash a Davies-Meyerův algoritmus, aby bylo dosaženo rovnoměrného rozložení dat na úložném zařízení. Systém má 23 úložných zařízení s úložnou kapacitou 186TB a 14478054 souborů. Počet souborů na každém zařízení je asi 629410 (celkový počet souborů/počet zařízení). Z hlediska umístění dat je po testování a skutečném použití jeho výkon srovnatelný s ostatními distribuovanými souborovými systémy a pro splnění požadavků na výkon úložného systému stačí.