大學(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ā)
這個算法的問題在于容錯性和擴展性不好尖飞。所謂容錯性是指當系統(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)空間的位置如下:
將數(shù)據(jù)塊A词爬、B、C权均、D的key使用相同的函數(shù)H計算出哈希值h顿膨,根據(jù)h確定此數(shù)據(jù)在環(huán)上的位置
從各數(shù)據(jù)塊的位置沿環(huán)順時針“行走”,第一臺遇到的服務(wù)器就是其應(yīng)該定位到的服務(wù)器叽赊。
可擴展性分析:增加一個server4虽惭,D重新指向server4
容錯性分析:server1掛掉,A重新指向server2
綜上所述蛇尚,一致性哈希算法對于節(jié)點的增減都只需重定位環(huán)空間中的一小部分數(shù)據(jù)芽唇,具有較好的容錯性和可擴展性
思考:
一致性哈希算法在服務(wù)節(jié)點太少時,容易因為節(jié)點分部不均勻而造成數(shù)據(jù)傾斜問題取劫,此時應(yīng)該怎么辦匆笤?有時間我們討論虛擬節(jié)點。