Hvernig samkvæm hashing leysir stigstærðarvandamál
Samræmd hashing er aðferð sem gerir stærðargráðu dreifðra kerfa mun mýkri og áreiðanlegri. Ólíkt eldri hashing aðferðum sem bila þegar netþjónum er bætt við eða fjarlægt, dregur samræmd hashing úr truflunum með því að endurdreifa aðeins litlum hluta gagna. Þessi aðferð tryggir:
- Lágmarks gagnaflutningurÞegar netþjóni er bætt við eða fjarlægður er aðeins um það bil 1/n lykla endurúthlutað, sem kemur í veg fyrir truflanir á kerfinu.
- Betri dreifing álagsSýndarhnútar dreifa vinnuálagi jafnt yfir netþjóna, koma í veg fyrir nettengingar og tryggja skilvirka nýtingu auðlinda.
- Bætt bilunarþolEf netþjónn bilar, þá taka aðeins nágrannaþjónar hans á sig aukaálagið, sem heldur kerfinu stöðugu.
- Stöðugleiki skyndiminniFlest gögn í skyndiminni haldast óbreytt meðan á skalun stendur, sem dregur úr álagi á gagnagrunninn og viðheldur afköstum.
Samræmd hashing er mikið notuð í nútímakerfum eins og Amazon DynamoDB, Netflix CDN og Discord til að takast á við ófyrirsjáanlegar umferðartoppa og tryggja áreiðanlega afköst. Með því að tengja netþjóna og gögn á hringlaga hash-hring hámarkar það stigstærð og áreiðanleika í dreifðum arkitektúrum.
Samræmd hashing í dreifðum kerfum | Einföld útskýring + sýnikennsla
sbb-itb-59e1987
Hvernig samkvæm hashing virkar
Samræmd hashing vs. hefðbundin hashing: Samanburður á gagnaflutningi
Hash-hringurinn og lyklaúthlutun
Samræmd hashing notar a hringlaga kjötrými, oft kallaður kjötkásshringur, til að koma í staðinn fyrir einfalda modulo-aðferðina. Þessi hringur táknar kjötkássugildi á bilinu 0 til 2^32-1. Bæði netþjónar og gagnalyklar eru kjötkássaðir með sömu virkni og staðsettir á hringnum.
Þegar lykill er beðinn um, þá skráir kerfið lykilinn á ákveðinn stað í hringnum. Þaðan færist það réttsælis þar til það nær fyrsta marki uppmannsins, sem ber síðan ábyrgð á að geyma og stjórna þeim lykli. Þessi réttsælisregla ákvarðar hvaða netþjónn sér um hvaða hluta af hash-rýminu.
Ólíkt hefðbundinni hashingu bindur samræmd hashing ekki kerfið við heildarfjölda netþjóna. Hver netþjónn tekur ákveðinn punkt á hringnum og á hlutann á milli sín og fyrri netþjónsins rangsælis.
Bæta við og fjarlægja hnúta
Þegar nýr netþjónn er bætt við er hann hassaður á ákveðna stöðu í hringnum og tekur við lyklum frá næsta nágranna sínum sem er réttsælis. Mikilvægt er að hafa í huga að restin af kerfinu helst óbreytt. Til dæmis, í uppsetningu með 100 hnútum, þyrfti aðeins að bæta við einum hnúti í viðbót 0.90% gagnlykla að flytja. Aftur á móti myndi hefðbundin hashing krefjast flutnings 99.01% gagnanna.
Ferlið er svipað þegar netþjónn er fjarlægður. Ef netþjónn fer án nettengingar eða bilar eru lyklar hans færðir réttsælis yfir á næsta netþjón. Þessi markvissa endurdreifing lágmarkar truflanir og kemur í veg fyrir útbreidda gagnaflutninga og skyndiminnistap sem getur komið upp með hefðbundnum aðferðum. Með því að tryggja að aðeins lítill hluti lykla sé endurdreifður styður samræmd hashing stigstærð og áreiðanleg hýsingarkerfi.
Með skilvirkri uppflettingartímaflækjustigi upp á O(log N) þegar tvíundarleitartré er notað til að geyma hnútastöður, tryggir samræmd hashing jöfn afköst jafnvel þótt kerfið stækki. Þessi straumlínulagaða gagnaflutningur leggur einnig grunninn að því að hámarka álagsdreifingu í gegnum sýndarhnúta.
Notkun sýndarhnúta fyrir betri dreifingu álags
Til að bæta álagsjöfnun, sýndarhnútar (VNodes) koma við sögu. Ef efnislegur netþjónn birtist aðeins á einum stað í hringnum getur það leitt til ójafnrar dreifingar álags. Sýndarhnútar bregðast við þessu með því að úthluta mörgum stöðum í hringnum til hvers efnislegs netþjóns.
Þessi aðferð dreifir vinnuálaginu jafnar. Þegar netþjónn bilar eru verkefni hans deilt á milli margra netþjóna í stað þess að byrða aðeins einn nágranna. Sýndarhnútar gera einnig kleift að afkastagetubundin vigtun, sem þýðir að netþjónar með meiri auðlindir (eins og meiri örgjörva eða vinnsluminni) geta tekist á við stærri hluta beiðna með því að fá úthlutað fleiri sýndarhnúta.
Venjulega úthluta kerfi um 100 sýndarhnútum á hvern netþjón, sem býður upp á fínstillta stjórn á álagsjöfnun. Jafnvel í stórum uppsetningum er minnisþörfin lágmarks. Til dæmis myndi hash-hringur sem styður 60.000 líkamlega netþjóna með 6 milljónum sýndarhnúta aðeins þurfa um það bil 12 til 27 megabæt af minni til að geyma vörpunina. Þessi samsetning skilvirkni og sveigjanleika gerir sýndarhnúta að mikilvægu tæki fyrir samræmd hash-kerfi.
Hvernig samkvæm hashing leysir vandamál með stigstærð
Minni gagnaflutningur við stærðargráðu
Einn helsti kosturinn við samfellda hashingu er hvernig hún lágmarkar gagnaflutninga við upp- eða niðurskalun. Í hefðbundinni modulo hashingu getur jafnvel lítil breyting - eins og að bæta einum netþjóni við stóran klasa - krafist þess að nánast allir lyklar séu endurúthlutaðir. Samfelld hashing, hins vegar, endurdreifir aðeins um 1/n af lyklunum þegar nýr netþjónn er kynntur. Þetta dregur verulega úr magni gagnaflutninga um netið. Til dæmis, í prófun með 1.500 hlutum dreifðum yfir 80 vélar (sumar hverjar upplifðu breytingar), olli samfelld hashing aðeins 25% aukningu í endurvörpuðum pörum, en hefðbundin hashing hefði krafist þess að nánast allir lyklar yrðu færðir. Þessi skilvirkni er mikilvæg til að koma í veg fyrir netþrengsli og truflanir á þjónustu, sérstaklega í umhverfum þar sem flutningur mikils magns gagna getur verið truflandi. Með því að takmarka gagnaflutninga tryggir samfelld hashing stöðugra kerfi, jafnvel við bilun í hnútum.
Betri afköst og áreiðanleiki
Samræmd hashing bætir einnig afköst og áreiðanleika með því að halda í skefjum áhrifum hnútabilana. Í hefðbundnum einingakerfum getur bilun í einum hnúti krafist endurhashingar á lyklunum upp að 90%, sem leiðir til flóðs af endurútreikningsbeiðnum til upprunaþjóna. Með samræmdri hashing eru truflanir staðbundnar - aðeins nágrannahnútar á hashinghringnum taka á sig aukaálagið. Snemmbúnar útfærslur komust að því að smávægilegur aukakostnaður við að fara í gegnum hashinghringinn var hverfandi samanborið við þann tíma sem fór í netsendingar.
Athyglisverð notkun á samfelldri hashingu kemur frá Akamai Technologies, sem notaði hana í Content Delivery Network sínu til að dreifa umferð á milli snúningsþjóna. Þessi aðferð hjálpaði til við að leysa "slashdotting" vandamálið á tíunda áratugnum, þar sem skyndilegar umferðarhækkunir ollu því að netþjónar hrundu. Tim Berners-Lee sagði jafnvel að þessi lausn hefði tekist á við þessar umferðarhækkunir á áhrifaríkan hátt.
Viðhalda skilvirkni skyndiminnis
Skilvirk skyndiminni er mikilvæg bæði fyrir afköst og kostnaðarstjórnun, og stöðug hashing gegnir lykilhlutverki í að viðhalda heilleika skyndiminnsins. Með því að takmarka endurúthlutun gagna við lítinn hluta lykla, hjálpar stöðug hashing til við að varðveita "hlýja" skyndiminn, sem geyma gögn sem oft eru skoðuð. Þetta er nauðsynlegt vegna þess að skyndiminniskort getur leitt til kostnaðarsamra gagnagrunnsfyrirspurna og aukins álags á bakendakerfi. Með því að halda flestum skyndiminnigögnum ósnortnum meðan á stigstærð stendur, lágmarkar stöðug hashing hættuna á útbreiddri ógildingu skyndiminnsins.
"Með því að lágmarka ógildingu skyndiminnisins bætir stöðug hashing notendaupplifun með hraðari hleðslutíma og dregur úr bandvíddarkostnaði." – Naeem Ul Haq, sérfræðingur í kerfishönnun
Raunverulegt dæmi um þetta má sjá í viðleitni Discord til að stækka kerfið í júlí 2017. Til að styðja við 5.000.000 notendur samtímis nýtti Discord sér samræmda hashing (e. consistorable hashing) innan Elixir-byggðrar arkitektúrs síns. Þetta gerði kleift að tengja tiltekna spjallrásir á skilvirkan hátt við rétta hnútpunkta, sem tryggir greiðanlegan stækk og áreiðanlegan árangur. Auk þess að varðveita skilvirkni skyndiminnis hjálpar samræmd hashing einnig til við að dreifa vinnuálagi á skilvirkan hátt, jafnvel þegar getu netþjóna er mismunandi.
Að vinna með mismunandi netþjónsgetu
Í umhverfum með fjölbreyttum netþjónsbúnaði notar samræmd hashing sýndarhnúta til að jafna álagið út frá hverjum og einum. sýndar einkaþjónar afkastageta. Til dæmis er hægt að úthluta þjóni með tvöfaldri afkastagetu en öðrum tvöfalt fleiri sýndarhnútum, sem gerir honum kleift að meðhöndla hlutfallslega stærri hluta af vinnuálaginu. Með því að úthluta sýndarhnútum í samræmi við það – t.d. 100 hnútar fyrir venjulega þjóna og 200 fyrir þá með mikla afkastagetu – nær kerfið jafnvægi í dreifingu álags með lágmarks sveiflum. Þessi aðferð tryggir að öflugri þjónar séu nýttir til fulls, en minna afkastamiklir þjónar meðhöndla vinnuálag sem passar við afkastagetu þeirra. Niðurstaðan er vel jafnvægið og skilvirkt hýsingaruppsetning sem aðlagast óaðfinnanlega mismunandi vélbúnaðargetu.
Íhugun um framkvæmd samfelldrar hashingar
Nú þegar við höfum fjallað um kostina, skulum við kafa ofan í hagnýtu smáatriðin við að innleiða samræmda hassun á áhrifaríkan hátt.
Að velja kjötfall
Kjölfallsfallið sem þú velur gegnir mikilvægu hlutverki í afköstum og lykladreifingu. Fyrir flest hýsingarumhverfi, ódulkóðaðar kjötföll Forrit eins og MurmurHash, xxHash eða MetroHash eru tilvalin því þau eru hröð og þjaka ekki örgjörvanum með óþarfa öryggisálagi. Dulkóðunarklukkuvirkni (t.d. MD5, SHA-1) er of mikil í þessum tilgangi og getur hægt á kerfinu þínu.
"Besta kjötfallið fyrir samræmda kjötun verður að vera hratt og framleiða einsleita úttak." – Neo Kim
Gott kjötkássafall tryggir að lyklar séu jafnt dreifðir yfir kjötkássrýmið og forðast þannig heita punkta þar sem einn hnútur verður ofhlaðinn. 32-bita kjötkássafall býður upp á um 4,29 milljarða mögulegra staðsetninga á sýndarhringnum, sem er nægt pláss til að draga úr árekstri. Til að viðhalda samræmi verða allir viðskiptavinir og hnútar að nota sama kjötkássafall, sem tryggir að þeir séu sammála um hvernig lyklar tengjast hnútum. Að auki gerir notkun á kjötkássuúttaki sem eru veldi af tveimur kleift að framkvæma hraðari bitaskiptar aðgerðir, sem eru skilvirkari en mátútreikningar.
Að stjórna breytingum á hnútum
Að meðhöndla breytingar í klasanum – eins og hnútar sem sameinast eða fara – er annar mikilvægur þáttur í samræmdri hashingu. Hash-hringurinn verður að aðlagast kraftmikið án þess að trufla þjónustu. Með því að nota sjálfjöfnandi tvíundarleitartré (BST) Að geyma staðsetningar hnúta tryggir að uppflettingaraðgerðir haldist skilvirkar, með flækjustigi O(log N), jafnvel þótt hringurinn þróist. Þessi uppbygging gerir það auðvelt að finna fljótt "næsta hnút réttsælis" fyrir hvaða lykil sem er.
Til að stjórna uppfærslum á öruggan hátt skal nota lesenda- og ritunarlása til að samstilla breytingar við BST þegar hnútar eru bættir við eða fjarlægðir. slúðursreglugerð getur einnig hjálpað með því að gera hnútum kleift að skiptast reglulega á upplýsingum um stöðu sína á jafningja-til-jafningja hátt. Þetta kemur í veg fyrir þörfina fyrir miðlægan stjórnanda, sem gæti orðið flöskuháls. Til að koma í veg fyrir ofhleðslu á einn nágranna þegar hnútur bilar, raðaðu upphaflegu skiptingarúthlutunum af handahófi þannig að álagið dreifist jafnt yfir klasa. Þegar þessir aðferðir eru komnir á sinn stað mun stöðugt eftirlit hjálpa til við að viðhalda jafnvægi.
Eftirlit og stilling álagsdreifingar
Jafnvel með vel hönnuðum hash-hring er mikilvægt að fylgjast með dreifingu álagsins til að koma í veg fyrir ójafnvægi á keyrslutíma. Fylgstu reglulega með fjöldi lykla sem hver hnútur á til að greina hugsanleg vandamál snemma. Fylgist vel með fjölda sýndarhnúta sem eru úthlutaðir hverjum efnislegum hnúti – að úthluta um 100 sýndarhnútum á hvern efnislegan hnút er góður upphafspunktur til að greina og leysa ójafnvægi.
"Góð regla til að fylgja gæti verið að reikna út 100 sýndarhnúta fyrir hvern raunverulegan hnút með hámarksafköstum. Þetta myndi leyfa þér að breyta álaginu á hvaða hnút sem er um 1%." – Greg Holt
Fyrir kerfi með blandaða vélbúnaðargetu er hægt að úthluta fleiri sýndarhnútum til netþjóna með meiri örgjörva- eða minnisauðlindir, sem tryggir að þeir höndli hlutfallslega stærri hluta vinnuálagsins. Til að koma í veg fyrir að einn hnútur verði ofhlaðinn skaltu innleiða ... takmarkaðar álag – ef hnútur fer yfir afkastagetu sína, skal beina innkomandi beiðnum á varahnút.
Raunverulegt dæmi um þessa meginreglu í verki er OpenStack Swift. Í febrúar 2011 sýndu þeir fram á að með 100 hnútum og 10.000.000 gagnakennum, þá leiddi það til þess að aðeins 90.423 auðkenni (0,90%) voru færð með því að bæta við einum hnút með samræmdri hashingu og 1.000 sýndarhnútum. Aftur á móti krafðist hefðbundin modulus hashing flutnings á 9.900.989 auðkennum (99,01%). Þetta sýnir hvernig samræmd hashing getur gert stigstærð mun skilvirkari og lágmarkað truflanir.
Niðurstaða
Helstu kostir stöðugrar hashingar
Samræmd hashing er byltingarkennd fyrir dreifð kerfi og býður upp á leið til að stækka á skilvirkan hátt með því að flytja aðeins brot (1/n) af lyklum þegar netþjónum er bætt við eða fjarlægt. Ólíkt hefðbundinni modulo hashing heldur þessi aðferð flestum lyklunum stöðugum, sem tryggir hátt skyndiminni og kemur í veg fyrir að netþjónar verði ofhlaðnir.
Annar áberandi eiginleiki er þess bilanaþol. Ef hnútur fer niður eru aðeins lyklarnir sem úthlutað er til þess hnútar dreift áfram til næsta hnúta í kjöthringnum, og restin af kerfinu verður óbreytt. Sýndarhnútar bæta þetta ferli enn frekar með því að dreifa gögnum jafnar yfir netþjóna og leyfa sterkari netþjónum að takast á við meiri umferð. Saman skapa þessir eiginleikar ramma fyrir seigla og afkastamikla innviði.
"Samræmd hashing gerir dreifingu lyklanna óháða fjölda netþjóna sem kerfið notar. Þannig getum við stækkað eða minnkað án þess að það hafi áhrif á kerfið í heild." – Animesh Gaitonde, tæknistjóri hjá Amazon
Raunveruleg dæmi sýna fram á þennan ávinning. Til dæmis notar DynamoDB frá Amazon stöðuga hashingu til að takast á við miklar umferðartoppa, eins og á Black Friday, án nokkurra vandamála. Á sama hátt notar Netflix þetta í Open Connect CDN sínu til að tengja efni á áhrifaríkan hátt við jaðarþjóna um allan heim.
Samræmd hashing í nútíma hýsingu
Þökk sé skilvirkni og áreiðanleika hefur samræmd hashing orðið hornsteinn nútíma hýsingarlausna. Hýsingaraðilar nota þessa aðferð til að stækka umferð áreynslulaust og jafna umferð á milli alþjóðlegra gagnavera. Möguleikinn á að bæta við eða fjarlægja afkastagetu án þess að valda víðtækri gagnadreifingu tryggir... stöðug afköst og áreiðanleiki.
Þessi tækni passar fullkomlega inn í nútíma hýsingararkitektúr, sem verður að takast á við breytilegt vinnuálag og starfa á mörgum svæðum. Með uppflettingartíma allt að 20 míkrósekúndur og hæfni til að viðhalda virkni skyndiminnsins við breytingar á innviðum, gerir stöðug hashing hýsingarlausnum kleift að veita stöðuga þjónustu eftir því sem kerfin þróast. Serverion, Við höfum innleitt samræmdar meginreglur um hashing til að bjóða upp á sveigjanlega og afkastamikla hýsingu í dreifðum gagnaverum okkar.
Algengar spurningar
Hvernig hjálpar stöðug hashing til við að draga úr gagnaflutningi þegar dreifð kerfi eru stækkuð?
Samræmd hashing virkar með því að raða hnútum og gögnum í hringlaga hash-hring. Þegar hnútur sameinast eða yfirgefur kerfið, eru aðeins gögnin sem tengjast þeim tiltekna hnúti og næsta nágranna hans endurúthlutað. Þessi aðferð dregur verulega úr magni gagna sem þarf að færa og hefur aðeins áhrif á lítinn hluta af heildargagnagrunninum.
Þessi hönnun lágmarkar truflanir við uppskalun, sem gerir ferlið mýkri og skilvirkara. Hún hentar sérstaklega vel fyrir dreifð kerfi sem stjórna stöðugt breytilegu vinnuálagi.
Hvernig hjálpa sýndarhnútar til við að dreifa álaginu í samræmdri hassun?
Sýndarhnútar, eða vnodes, gegna lykilhlutverki í samræmdri hashingu og hjálpa til við að dreifa álagi jafnar í dreifðum kerfum. Í stað þess að tengja hvern netþjón við aðeins einn stað á hash-hringnum er netþjónum úthlutað mörgum sýndarstöðum. Þetta skiptir lykilrýminu í minni, auðveldari hluta, sem tryggir að umferð og geymsla dreifist jafnar yfir alla netþjóna.
Svona virkar þetta: þegar lykill er dulkóðaður er hann úthlutaður næsta vnode sem færist réttsælis á dulkóðunarhringnum. Með mörgum vnode á hverjum netþjóni forðast kerfið að ofhlaða einn netþjón og viðheldur jafnvægðu álagi. Að bæta við eða fjarlægja netþjón hefur aðeins áhrif á lykla sem eru tengdir vnode hans, sem dregur úr magni gagna sem þarf að flytja. Þessi hönnun styður mjúka stigstærð og tryggir áreiðanlega afköst - eitthvað sem er mikilvægt fyrir innviði eins og ... Serverion’hýsingarvettvangur , þar sem skilvirk auðlindastjórnun er nauðsynleg til að skila stöðugum árangri.
Hvernig eykur stöðug hashing bilanaþol í dreifðum kerfum?
Samræmd hashing styrkir bilanaþol með því að dreifa gögnum yfir hnúta á þann hátt að truflanir þegar hnútur fer án nettengingar eru lágmarkaðar. Þetta virkar í gegnum hringlaga hashinghring sem kortleggur bæði gögn og netþjóna. Þegar hnútur bilar eru aðeins gögnin sem tengjast þeim tiltekna hnúti úthlutað næsta nágranna sínum í hringnum. Þessi aðferð dregur verulega úr gagnaflutningi en heldur restinni af kerfinu gangandi snurðulaust.
Þessi aðferð tryggir ekki aðeins mikla tiltækileika heldur styður einnig við sveigjanleika. Að bæta við eða fjarlægja hnúta veldur lágmarks truflunum á kerfinu. Með því að stjórna bilunum í hnútum á skilvirkan hátt verður samræmd hashing hornsteinninn í að skapa áreiðanleg dreifð kerfi.
