大學(xué)時(shí)期做移動(dòng)開發(fā)(ios),畢業(yè)后開始做大數(shù)據(jù)開發(fā)，到現(xiàn)在也為止也做過不少工程項(xiàng)目，掌握了不少我只認(rèn)為是工具的東西，比如Hadoop中的HDFS、Mapreduce、Yarn、HBase、Hive、Sqoop、Flume、Mahout、Pig、Zookeeper等和Spark中的Spark SQL、Spark Streaming、MLlib等，越來越意識(shí)到算法在工程中的重要性，有了扎實(shí)的的算法基礎(chǔ)，新的技術(shù)，新的工具能夠很快的學(xué)會(huì)并且掌握，也是通往高級(jí)工程師的必經(jīng)之路。今天來說一說海量數(shù)據(jù)分流處理中的一種方法：一致性哈希算法。
海量數(shù)據(jù)分流處理(負(fù)載均衡)的幾種方法
一、傳統(tǒng)Hash方法
實(shí)際應(yīng)用：流量分發(fā)
這個(gè)算法的問題在于容錯(cuò)性和擴(kuò)展性不好。所謂容錯(cuò)性是指當(dāng)系統(tǒng)中某一個(gè)或幾個(gè)服務(wù)器變得不可用時(shí)，整個(gè)系統(tǒng)是否可以正確高效運(yùn)行；而擴(kuò)展性是指當(dāng)加入新的服務(wù)器后，整個(gè)系統(tǒng)是否可以正確高效運(yùn)行。
現(xiàn)假設(shè)有一臺(tái)服務(wù)器宕機(jī)了，那么為了填補(bǔ)空缺，要將宕機(jī)的服務(wù)器從編號(hào)列表中移除，后面的服務(wù)器按順序前移一位并將其編號(hào)值減一，此時(shí)每個(gè)key就要按h = Hash(key) % (N-1)重新計(jì)算；同樣，如果新增了一臺(tái)服務(wù)器，雖然原有服務(wù)器編號(hào)不用改變，但是要按h = Hash(key) % (N+1)重新計(jì)算哈希值。因此系統(tǒng)中一旦有服務(wù)器變更，大量的key會(huì)被重定位到不同的服務(wù)器從而造成大量的緩存不命中。而這種情況在分布式系統(tǒng)中是非常糟糕的。
二、一致性Hash算法
假設(shè)某哈希函數(shù)H的值空間為0 - (2^32)-1（即哈希值是一個(gè)32位無符號(hào)整形），將各個(gè)服務(wù)器進(jìn)行一個(gè)哈希，具體可以選擇服務(wù)器的ip或主機(jī)名作為關(guān)鍵字進(jìn)行哈希，這樣每臺(tái)機(jī)器就能確定其在哈希環(huán)上的位置，這里假設(shè)將上文中三臺(tái)服務(wù)器使用ip地址哈希后在環(huán)空間的位置如下：
將數(shù)據(jù)塊A、B、C、D的key使用相同的函數(shù)H計(jì)算出哈希值h，根據(jù)h確定此數(shù)據(jù)在環(huán)上的位置
從各數(shù)據(jù)塊的位置沿環(huán)順時(shí)針“行走”，第一臺(tái)遇到的服務(wù)器就是其應(yīng)該定位到的服務(wù)器。
可擴(kuò)展性分析：增加一個(gè)server4，D重新指向server4
容錯(cuò)性分析：server1掛掉，A重新指向server2
綜上所述，一致性哈希算法對(duì)于節(jié)點(diǎn)的增減都只需重定位環(huán)空間中的一小部分?jǐn)?shù)據(jù)，具有較好的容錯(cuò)性和可擴(kuò)展性
思考：
一致性哈希算法在服務(wù)節(jié)點(diǎn)太少時(shí)，容易因?yàn)楣?jié)點(diǎn)分部不均勻而造成數(shù)據(jù)傾斜問題，此時(shí)應(yīng)該怎么辦？有時(shí)間我們討論虛擬節(jié)點(diǎn)。
