Johdanto
Johdonmukaista hajautusalgoritmia ehdotettiin julkaisussa Consistentthashingandrandomtrees vuonna 1997, ja sitä käytetään laajalti hajautetuissa järjestelmissä. Johdonmukainen hajautus on eräänlainen hajautusalgoritmi. Yksinkertaisesti sanottuna palvelinta poistettaessa tai lisättäessä tämä algoritmi voi muuttaa olemassa olevan palvelupyynnön ja käsittelypyyntöpalvelimen välistä kartoitussuhdetta mahdollisimman vähän, jotta monotonisuus voidaan tyydyttää mahdollisimman paljon. Seksuaaliset vaatimukset. Tavallisessa hajautetussa klusterissa palvelupyyntöjen ja käsittelypyyntöpalvelimien välillä voi olla yksi-yhteen vastaavuus, mikä tarkoittaa, että palvelupyyntöjen ja käsittelypalvelimien välinen kartoitussuhde on kiinteä ja tietyn pyynnön käsittelee kiinteä palvelin. Tämä menetelmä ei voi kuormitusta tasapainottaa koko järjestelmää ja saattaa aiheuttaa joidenkin palvelimien olevan liian kiireisiä käsittelemään uusia pyyntöjä. Muut palvelimet ovat liian käyttämättömiä, koko järjestelmän resurssien käyttöaste on alhainen, ja kun hajautetun klusterin palvelin kaatuu, joitain palvelupyyntöjä ei voida käsitellä suoraan.
Lisäparannukset voivat käyttää hash-algoritmia palvelupyynnön ja käsittelypalvelimen välisen suhteen kartoittamiseen dynaamisen allokoinnin tavoitteen saavuttamiseksi. Palvelupyyntö muunnetaan hash-algoritmin kautta ja muunnettu tulos on modulo-operaatio palvelimen solmun arvolla ja modulo-arvo on palvelupyyntöä vastaava pyyntökäsittelypalvelin. Tämä menetelmä voi selviytyä solmuvirheistä. Kun hajautettu klusterisolmu menee alas, palvelupyynnöt voidaan jakaa uudelleen muille käytettävissä oleville palvelimille hajautusalgoritmin avulla. Näin vältetään tilanne, jossa pyyntöä ei voida käsitellä.
Mutta tämän menetelmän puutteet ovat myös ilmeisiä. Jos palvelin tallentaa palvelupyyntöä vastaavat tiedot, jos pyynnön hash-arvo lasketaan uudelleen, suuri määrä pyyntöjä siirretään eri palvelimille. Aiheuttaa pyynnön käyttämät tiedot virheellisiksi, mikä on erittäin huonoa hajautetussa järjestelmässä. Hyvin suunnitellun hajautetun järjestelmän monotonisuuden tulee olla hyvä, eli palvelimien lisääminen ja poistaminen ei aiheuta suurta määrää hajautussiirtoja, ja johdonmukainen hajautus voi vain ratkaista tämän ongelman.
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.
Toimintaperiaate
Johdonmukainen hajautusalgoritmi on yksi nykyisistä valtavirran hajautetun hash-taulukon protokollista. Se muokkaa yksinkertaista hash-algoritmia ja ratkaisee hotPot ) -ongelman, sen periaate on jaettu kahteen vaiheeseen:
Ensin lasketaan tallennussolmun hash-arvo, joka abstraktioi tallennustilan renkaaksi ja konfiguroi renkaan tallennussolmun. Kaikilla renkaan solmuilla on arvo. Toiseksi hajauta tiedot ja yhdistä se lähimpään solmuun myötäpäivään. Kun solmu epäonnistuu offline-tilassa, algoritmin kartoitusmenetelmän mukaan vaikuttaa vain renkaan viallisen solmun ja seuraavan solmun välisellä aikavälillä oleviin tietoobjekteihin, ja nämä objektit itse kartoitetaan vialliseen solmuun. . Kun solmujen määrä lisääntyy, esimerkiksi lisäämällä solmu H solmujen A ja B väliin, vain solmun H väliset dataobjektit kulkevat vastapäivään, kunnes se vaikuttaa B:hen, ja ne kartoitetaan uudelleen H:ksi. Näin ollen, kun solmu vaihtuu, koko tallennustilan tietoja ei kartoiteta uudelleen, mikä ratkaisee tehottomuuden ongelman, jonka aiheuttaa yksinkertainen hajautusalgoritmi lisätä tai poistaa solmuja ja kartoittaa kaikki tiedot uudelleen.
Johdonmukainen hajautusalgoritmi, joka on tärkeä algoritmi hajautetun tallennuksen alalla, ratkaisee periaatteessa avainongelman tallennusympäristössä, jota edustaa P2P-miten tietojenkäsittely suoritetaan dynaamisessa verkkotopologiassa. Jaa ja valitse reititys. Algoritmin muodostamassa tallennustopologiassa jokaisen tallennussolmun tarvitsee ylläpitää vain vähän tietoa viereisistä solmuista, ja kun solmu liittyy/poistuu järjestelmästä, vain pieni määrä toisiinsa liittyviä solmuja osallistuu topologian ylläpitoon, mikä tekee johdonmukaisuudesta Kreikan algoritmista on tullut käytännöllinen DHT (DistributedHashTable) -algoritmi. Mutta johdonmukaisella hajautusalgoritmilla on edelleen puutteita. Ensinnäkin kyselyprosessissa kyselysanoman on käytävä läpi O(n) vaihetta (n edustaa järjestelmän solmujen kokonaismäärää), jotta se saavuttaa kyselyn kohteena olevan solmun. Ei ole vaikea kuvitella, että kun järjestelmän mittakaava on erittäin suuri, solmujen määrä voi ylittää miljoonan, ja tällaista kyselytehokkuutta on ilmeisen vaikea vastata käyttötarpeisiin. Toiseksi, kun uusi fyysinen solmu lisätään tai poistetaan hajautetussa tallennusjärjestelmässä, joka käyttää johdonmukaista hajautusalgoritmia, seuraavaan solmuun liittyvät tiedot on siirrettävä ja kyselyn osumataajuus ja tallennustehokkuus laskevat, mikä vaikuttaa koko järjestelmään. Esitys.
Suhde hash-algoritmiin
Hajautusalgoritmin perusteella ehdotetaan johdonmukaista hajautusalgoritmia. Dynaamisesti muuttuvassa hajautetussa ympäristössä hash-algoritmin tulee täyttää useita ehtoja: tasapaino, monotonisuus ja dispersio.
①Tasapainottaminen tarkoittaa, että tiivisteen tulos tulee jakaa tasaisesti jokaiselle solmulle, mikä ratkaisee kuormituksen tasapainotuksen algoritmisesti.
② Monotonisuus tarkoittaa, että solmuja lisättäessä tai poistettaessa se ei vaikuta järjestelmän normaaliin toimintaan.
③Hajauttaminen tarkoittaa, että tiedot tulee tallentaa hajautetusti jokaiseen hajautetun klusterin solmuun (solmuilla voi olla itse varmuuskopioita), eikä jokaisen solmun tarvitse tallentaa kaikkea dataa.
Edut
Skaalautuvuus. Johdonmukainen hajautusalgoritmi varmistaa, että kun palvelimia lisätään tai vähennetään, tiedon tallennusmuutokset ovat vähiten, mikä säästää huomattavasti tiedonsiirron ylimääräisiä kustannuksia perinteisiin hajautusalgoritmeihin verrattuna.
Sopeutua paremmin tiedon nopeaan kasvuun. Käytä johdonmukaista hajautusalgoritmia tietojen jakamiseen. Kun data jatkaa kasvuaan, jotkin virtuaaliset solmut voivat sisältää paljon dataa, mikä johtaa tietojen epätasaiseen jakautumiseen virtuaalisissa solmuissa. Tällä hetkellä virtuaaliset solmut, joissa on paljon dataa, voidaan jakaa. Tämä jako on vain Se jakaa alkuperäisen virtuaalisen solmun kahteen ilman uudelleentiivistämistä ja kaikkien tietojen jakamista. Jos fyysisen palvelimen kuormitus on edelleen epätasapainossa virtuaalisen solmun jakamisen jälkeen, sinun tarvitsee vain säätää joidenkin virtuaalisten solmujen tallennusjakoa palvelimien kesken. Tällä tavalla fyysisten palvelimien määrää voidaan dynaamisesti laajentaa datan kasvun myötä, ja kustannukset ovat paljon pienemmät kuin kaiken datan uudelleenjakaminen perinteisillä hajautusalgoritmeilla.
Sovellus
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-järjestelmä ottaa käyttöön parannetun johdonmukaisen hajautusalgoritmin tasaisen jakelun ja tietojen nopean paikantamisen saavuttamiseksi. Hash-funktiota valittaessa se otetaan pääasiassa huomioon kahdesta seuraavista näkökohdista: (1) Toiminnan tehokkuus; (2) Hash on yhtenäinen. Toiminnallinen tehokkuus tarkoittaa, että valitulla hash-funktiolla on korkea laskennallinen tehokkuus, se toteuttaa tiedon nopean paikantamisen ja hyvän käyttökokemuksen; hash yhtenäinen tarkoittaa, että valitulla hash-funktiolla on hyvä jakautuminen, mikä varmistaa, että tiedot tallennetaan Tasainen jakautuminen laitteeseen. Davies-Meyer-algoritmi on parempi valinta. Toisaalta tehokas toiminnan tehokkuus varmistaa tiedon nopean paikantamisen; toisaalta tasainen hash-jakauma varmistaa tiedon tasaisen jakautumisen. Varsinaisen käytön näkökulmasta HepyCloud-järjestelmään sovelletaan parannettua johdonmukaista hashia ja Davies-Meyer-algoritmia tietojen tasaisen jakautumisen toteuttamiseksi tallennuslaitteella. Järjestelmässä on 23 tallennuslaitetta, joiden tallennuskapasiteetti on 186 Tt ja 14478054 tiedostoa. Kussakin laitteessa olevien tiedostojen määrä on noin 629 410 (tiedostojen kokonaismäärä/laitteiden määrä). Tietojen paikannuksessa sen suorituskyky on testauksen ja todellisen käytön jälkeen verrattavissa muihin hajautettuihin tiedostojärjestelmiin ja se riittää täyttämään tallennusjärjestelmän suorituskykyvaatimukset.