接下來三種哈希算法的應(yīng)用都跟分布式系統(tǒng)有關(guān)。接下來就看一下哈希算法是如何解決這些分布式問題的侦鹏。

應(yīng)用五：負(fù)載均衡

負(fù)載均衡算法有很多诡曙，比如輪詢、隨機(jī)略水、加權(quán)輪詢等价卤。那如何才能實(shí)現(xiàn)一個(gè)會話粘滯（session sticky）的負(fù)載均衡算法呢？也就是說渊涝，我們需要在同一個(gè)客戶端上慎璧，在一次會話中的所有請求都路由到同一個(gè)服務(wù)器上。

借助哈希算法驶赏，這些問題都可以非常完美地解決炸卑。我們可以通過哈希算法既鞠，對客戶端 IP 地址或者會話 ID 計(jì)算哈希值煤傍，將取得的哈希值與服務(wù)器列表的大小進(jìn)行取模運(yùn)算，最終得到的值就是應(yīng)該被路由到的服務(wù)器編號嘱蛋。 這樣蚯姆，我們就可以把同一個(gè) IP 過來的所有請求五续，都路由到同一個(gè)后端服務(wù)器上。

應(yīng)用六：數(shù)據(jù)分片

哈希算法用于數(shù)據(jù)分片龄恋，這里有兩個(gè)例子疙驾。

1. 如何統(tǒng)計(jì)“搜索關(guān)鍵詞”出現(xiàn)的次數(shù)？

假如我們有 1T 的日志文件郭毕，這里面記錄了用戶的搜索關(guān)鍵詞它碎，我們想要快速統(tǒng)計(jì)出每個(gè)關(guān)鍵詞被搜索的次數(shù)，該怎么做呢显押？

這個(gè)問題有兩個(gè)難點(diǎn)扳肛，第一個(gè)是搜索日志很大，沒辦法放到一臺機(jī)器的內(nèi)存中乘碑。第二個(gè)難點(diǎn)是挖息，如果只用一臺機(jī)器來處理這么巨大的數(shù)據(jù)，處理時(shí)間會很長兽肤。

針對這兩個(gè)難點(diǎn)套腹，我們可以先對數(shù)據(jù)進(jìn)行分片，然后采用多臺機(jī)器處理的方法资铡，來提高處理速度电禀。具體的思路是這樣的：為了提高處理的速度，我們用 n 臺機(jī)器并行處理笤休。我們從搜索記錄的日志文件中鞭呕，依次讀出每個(gè)搜索關(guān)鍵詞，并且通過哈希函數(shù)計(jì)算哈希值宛官，然后再跟 n 取模葫松，最終得到的值，就是應(yīng)該被分配到的機(jī)器編號底洗。這樣同一個(gè)搜索關(guān)鍵詞會被分配到同一個(gè)機(jī)器上腋么。每個(gè)機(jī)器會分別計(jì)算關(guān)鍵詞出現(xiàn)的次數(shù)，最后合并起來就是最終的結(jié)果亥揖。

實(shí)際上珊擂，這里的處理過程也是 MapReduce 的基本設(shè)計(jì)思想。

2. 如何快速判斷圖片是否在圖庫中费变？

假設(shè)現(xiàn)在我們的圖庫中有 1 億張圖片摧扇，很顯然，在單臺機(jī)器上構(gòu)建散列表是行不通的挚歧。因?yàn)閱闻_機(jī)器的內(nèi)存有限扛稽，而 1 億張圖片構(gòu)建散列表顯然遠(yuǎn)遠(yuǎn)超過了單臺機(jī)器的內(nèi)存上限。

我們同樣可以對數(shù)據(jù)進(jìn)行分片滑负，然后采用多機(jī)處理在张。我們準(zhǔn)備 n 臺機(jī)器用含，讓每臺機(jī)器只維護(hù)某一部分圖片對應(yīng)的散列表。我們每次從圖庫中讀取一個(gè)圖片帮匾，計(jì)算唯一標(biāo)識啄骇，然后與機(jī)器個(gè)數(shù) n 求余取模，得到的值就對應(yīng)要分配的機(jī)器編號瘟斜，然后將這個(gè)圖片的唯一標(biāo)識和圖片路徑發(fā)往對應(yīng)的機(jī)器構(gòu)建散列表缸夹。

當(dāng)我們要判斷一個(gè)圖片是否在圖庫中的時(shí)候，我們通過同樣的哈希算法螺句，計(jì)算這個(gè)圖片的唯一標(biāo)識明未，然后與機(jī)器個(gè)數(shù) n 求余取模。假設(shè)得到的值是 k壹蔓，那就去編號 k 的機(jī)器構(gòu)建的散列表中查找趟妥。

實(shí)際上，針對這種海量數(shù)據(jù)的處理問題佣蓉，我們都可以采用多機(jī)分布式處理披摄。借助這種分片的思路，可以突破單機(jī)內(nèi)存勇凭、CPU 等資源的限制疚膊。

應(yīng)用七：分布式存儲

現(xiàn)在互聯(lián)網(wǎng)面對的都是海量的數(shù)據(jù)、海量的用戶虾标。我們?yōu)榱颂岣邤?shù)據(jù)的讀取寓盗、寫入能力，一般都采用分布式的方式來存儲數(shù)據(jù)璧函，比如分布式緩存傀蚌。我們有海量的數(shù)據(jù)需要緩存，所以一個(gè)緩存機(jī)器肯定是不夠的蘸吓。于是善炫，我們就需要將數(shù)據(jù)分布在多臺機(jī)器上。

該如何決定將哪個(gè)數(shù)據(jù)放到哪個(gè)機(jī)器上呢库继？我們可以借用前面數(shù)據(jù)分片的思想箩艺，即通過哈希算法對數(shù)據(jù)取哈希值，然后對機(jī)器個(gè)數(shù)取模宪萄，這個(gè)最終值就是應(yīng)該存儲的緩存機(jī)器編號艺谆。

但是，如果數(shù)據(jù)增多拜英，原來的 10 個(gè)機(jī)器已經(jīng)無法承受了静汤，我們就需要擴(kuò)容了，比如擴(kuò)到 11 個(gè)機(jī)器，這時(shí)候麻煩就來了撒妈。因?yàn)榛峙@里并不是簡單地加個(gè)機(jī)器就可以了排监。

原來的數(shù)據(jù)是通過與 10 來取模的狰右。比如 13 這個(gè)數(shù)據(jù)，存儲在編號為 3 這臺機(jī)器上舆床。但是新加了一臺機(jī)器中棋蚌，我們對數(shù)據(jù)按照 11 取模，原來 13 這個(gè)數(shù)據(jù)就被分配到 2 號這臺機(jī)器上了挨队。

因此谷暮，所有的數(shù)據(jù)都要重新計(jì)算哈希值，然后重新搬移到正確的機(jī)器上盛垦。這樣就相當(dāng)于湿弦，緩存中的數(shù)據(jù)一下子就都失效了。所有的數(shù)據(jù)請求都會穿透緩存腾夯，直接去請求數(shù)據(jù)庫颊埃。這樣就可能發(fā)生雪崩效應(yīng)，壓垮數(shù)據(jù)庫蝶俱。

所以班利，我們需要一種方法，使得在新加入一個(gè)機(jī)器后榨呆，并不需要做大量的數(shù)據(jù)搬移罗标。這時(shí)候，一致性哈希算法就要登場了积蜻。

假設(shè)我們有 k 個(gè)機(jī)器闯割，數(shù)據(jù)的哈希值的范圍是 [0, MAX]。我們將整個(gè)范圍劃分成 m 個(gè)小區(qū)間（m 遠(yuǎn)大于 k）竿拆，每個(gè)機(jī)器負(fù)責(zé) m/k 個(gè)小區(qū)間纽谒。當(dāng)有新機(jī)器加入的時(shí)候，我們就將某幾個(gè)小區(qū)間的數(shù)據(jù)如输，從原來的機(jī)器中搬移到新的機(jī)器中鼓黔。這樣，既不用全部重新哈希不见、搬移數(shù)據(jù)澳化，也保持了各個(gè)機(jī)器上數(shù)據(jù)數(shù)量的均衡。

除了我們上面講到的分布式緩存稳吮，實(shí)際上缎谷，一致性哈希算法的應(yīng)用非常廣泛，在很多分布式存儲系統(tǒng)中灶似，都可以見到一致性哈希算法的影子列林。

解答開篇 & 內(nèi)容小結(jié)

在負(fù)載均衡應(yīng)用中瑞你，利用哈希算法替代映射表，可以實(shí)現(xiàn)一個(gè)會話粘滯的負(fù)載均衡策略希痴。

在數(shù)據(jù)分片應(yīng)用中者甲，通過哈希算法對處理的海量數(shù)據(jù)進(jìn)行分片，多機(jī)分布式處理砌创，可以突破單機(jī)資源的限制虏缸。

在分布式存儲應(yīng)用中，利用一致性哈希算法嫩实，可以解決緩存等分布式系統(tǒng)的擴(kuò)容刽辙、縮容導(dǎo)致數(shù)據(jù)大量搬移的難題。

課后思考

這兩節(jié)總共講了七個(gè)哈希算法的應(yīng)用甲献。實(shí)際上宰缤，講的也只是冰山一角，哈希算法還有很多其他的應(yīng)用晃洒，比如網(wǎng)絡(luò)協(xié)議中的 CRC 校驗(yàn)慨灭、Git commit id 等等。除了這些锥累，你還能想到其他用到哈希算法的地方嗎缘挑？