大學(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é)點。
