海量數(shù)據(jù)分流處理-------一致性哈希算法

大學(xué)時期做移動開發(fā)(ios),畢業(yè)后開始做大數(shù)據(jù)開發(fā),到現(xiàn)在也為止也做過不少工程項目粪躬,掌握了不少我只認為是工具的東西捉貌,比如Hadoop中的HDFS、Mapreduce暖侨、Yarn椭住、HBase、Hive字逗、Sqoop京郑、Flume、Mahout葫掉、Pig些举、Zookeeper等和Spark中的Spark SQL、Spark Streaming俭厚、MLlib等户魏,越來越意識到算法在工程中的重要性,有了扎實的的算法基礎(chǔ)挪挤,新的技術(shù)叼丑,新的工具能夠很快的學(xué)會并且掌握,也是通往高級工程師的必經(jīng)之路扛门。今天來說一說海量數(shù)據(jù)分流處理中的一種方法:一致性哈希算法鸠信。

海量數(shù)據(jù)分流處理(負載均衡)的幾種方法

一、傳統(tǒng)Hash方法

實際應(yīng)用:流量分發(fā)

1.png

這個算法的問題在于容錯性和擴展性不好尖飞。所謂容錯性是指當系統(tǒng)中某一個或幾個服務(wù)器變得不可用時症副,整個系統(tǒng)是否可以正確高效運行;而擴展性是指當加入新的服務(wù)器后政基,整個系統(tǒng)是否可以正確高效運行贞铣。

現(xiàn)假設(shè)有一臺服務(wù)器宕機了,那么為了填補空缺沮明,要將宕機的服務(wù)器從編號列表中移除辕坝,后面的服務(wù)器按順序前移一位并將其編號值減一,此時每個key就要按h = Hash(key) % (N-1)重新計算荐健;同樣酱畅,如果新增了一臺服務(wù)器,雖然原有服務(wù)器編號不用改變江场,但是要按h = Hash(key) % (N+1)重新計算哈希值纺酸。因此系統(tǒng)中一旦有服務(wù)器變更,大量的key會被重定位到不同的服務(wù)器從而造成大量的緩存不命中址否。而這種情況在分布式系統(tǒng)中是非常糟糕的餐蔬。

二、一致性Hash算法

假設(shè)某哈希函數(shù)H的值空間為0 - (2^32)-1(即哈希值是一個32位無符號整形)佑附,將各個服務(wù)器進行一個哈希樊诺,具體可以選擇服務(wù)器的ip或主機名作為關(guān)鍵字進行哈希,這樣每臺機器就能確定其在哈希環(huán)上的位置音同,這里假設(shè)將上文中三臺服務(wù)器使用ip地址哈希后在環(huán)空間的位置如下:


Snip20170814_48.png

將數(shù)據(jù)塊A词爬、B、C权均、D的key使用相同的函數(shù)H計算出哈希值h顿膨,根據(jù)h確定此數(shù)據(jù)在環(huán)上的位置


Snip20170814_49.png

從各數(shù)據(jù)塊的位置沿環(huán)順時針“行走”,第一臺遇到的服務(wù)器就是其應(yīng)該定位到的服務(wù)器叽赊。
Snip20170814_50.png

可擴展性分析:增加一個server4虽惭,D重新指向server4


Snip20170814_51.png

容錯性分析:server1掛掉,A重新指向server2


Snip20170814_52.png

綜上所述蛇尚,一致性哈希算法對于節(jié)點的增減都只需重定位環(huán)空間中的一小部分數(shù)據(jù)芽唇,具有較好的容錯性和可擴展性

思考:

一致性哈希算法在服務(wù)節(jié)點太少時,容易因為節(jié)點分部不均勻而造成數(shù)據(jù)傾斜問題取劫,此時應(yīng)該怎么辦匆笤?有時間我們討論虛擬節(jié)點。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末谱邪,一起剝皮案震驚了整個濱河市炮捧,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌惦银,老刑警劉巖咆课,帶你破解...
    沈念sama閱讀 222,627評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件末誓,死亡現(xiàn)場離奇詭異,居然都是意外死亡书蚪,警方通過查閱死者的電腦和手機喇澡,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,180評論 3 399
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來殊校,“玉大人晴玖,你說我怎么就攤上這事∥鳎” “怎么了呕屎?”我有些...
    開封第一講書人閱讀 169,346評論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長敬察。 經(jīng)常有香客問我秀睛,道長,這世上最難降的妖魔是什么莲祸? 我笑而不...
    開封第一講書人閱讀 60,097評論 1 300
  • 正文 為了忘掉前任琅催,我火速辦了婚禮,結(jié)果婚禮上虫给,老公的妹妹穿的比我還像新娘藤抡。我一直安慰自己,他們只是感情好抹估,可當我...
    茶點故事閱讀 69,100評論 6 398
  • 文/花漫 我一把揭開白布缠黍。 她就那樣靜靜地躺著,像睡著了一般药蜻。 火紅的嫁衣襯著肌膚如雪瓷式。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,696評論 1 312
  • 那天语泽,我揣著相機與錄音贸典,去河邊找鬼。 笑死踱卵,一個胖子當著我的面吹牛廊驼,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播惋砂,決...
    沈念sama閱讀 41,165評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼妒挎,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了西饵?” 一聲冷哼從身側(cè)響起酝掩,我...
    開封第一講書人閱讀 40,108評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎眷柔,沒想到半個月后期虾,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體原朝,經(jīng)...
    沈念sama閱讀 46,646評論 1 319
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,709評論 3 342
  • 正文 我和宋清朗相戀三年镶苞,在試婚紗的時候發(fā)現(xiàn)自己被綠了喳坠。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 40,861評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡宾尚,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出谢澈,到底是詐尸還是另有隱情煌贴,我是刑警寧澤,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布锥忿,位于F島的核電站牛郑,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏敬鬓。R本人自食惡果不足惜淹朋,卻給世界環(huán)境...
    茶點故事閱讀 42,196評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望钉答。 院中可真熱鬧础芍,春花似錦、人聲如沸数尿。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,698評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽右蹦。三九已至诊杆,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間何陆,已是汗流浹背晨汹。 一陣腳步聲響...
    開封第一講書人閱讀 33,804評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留贷盲,地道東北人淘这。 一個月前我還...
    沈念sama閱讀 49,287評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像巩剖,于是被迫代替她去往敵國和親慨灭。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 45,860評論 2 361

推薦閱讀更多精彩內(nèi)容