本節(jié)分析哈希算法的其他三個(gè)應(yīng)用：負(fù)載均衡、數(shù)據(jù)分片、分布式存儲(chǔ)。這三個(gè)應(yīng)用都跟分布式系統(tǒng)有關(guān)。看下哈希算法是如何解決這些分布式問(wèn)題的。

五：負(fù)載均衡

問(wèn)題：那如何才能實(shí)現(xiàn)一個(gè)會(huì)話粘滯（session sticky）的負(fù)載均衡算法呢？也就是說(shuō)，我們需要在同一個(gè)客戶端上，在一次會(huì)話中的所有請(qǐng)求都路由到同一個(gè)服務(wù)器上。

方法一：維護(hù)一張映射關(guān)系表，這張表的內(nèi)容是客戶端 IP 地址或者會(huì)話 ID 與服務(wù)器編號(hào)的映射關(guān)系。

缺點(diǎn)：如果客戶端很多，映射表可能會(huì)很大，比較浪費(fèi)內(nèi)存空間；客戶端下線、上線，服務(wù)器擴(kuò)容、縮容都會(huì)導(dǎo)致映射失效，這樣維護(hù)映射表的成本就會(huì)很大；如果借助哈

哈希方法：通過(guò)一個(gè)hash算法，對(duì)客戶端ip地址或者會(huì)話id計(jì)算哈希值，將取得的哈希值與服務(wù)器列表的大小進(jìn)行取模，最后得到的值就是應(yīng)該被路由到的服務(wù)器的編號(hào)。這樣就可以把同一個(gè)ip過(guò)來(lái)的所有請(qǐng)求都路由到同一臺(tái)機(jī)器上去

六：數(shù)據(jù)分片

哈希算法還可以用于數(shù)據(jù)的分片

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

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

難點(diǎn)：一是搜索日志很大，沒(méi)辦法放到一臺(tái)機(jī)器的內(nèi)存中。二是，如果只用一臺(tái)機(jī)器來(lái)處理這么巨大的數(shù)據(jù)，處理時(shí)間會(huì)很長(zhǎng)

方案：可以先對(duì)數(shù)據(jù)進(jìn)行分片，然后采用多臺(tái)機(jī)器處理的方法，來(lái)提高處理速度。

具體的思路：

• 為了提高處理的速度，用 n 臺(tái)機(jī)器并行處理。
• 從搜索記錄的日志文件中，依次讀出每個(gè)搜索關(guān)鍵詞，并且通過(guò)哈希函數(shù)計(jì)算哈希值，然后再跟 n 取模，最終得到的值，就是應(yīng)該被分配到的機(jī)器編號(hào)。
• 哈希值相同的搜索關(guān)鍵詞就被分配到了同一個(gè)機(jī)器上。同一個(gè)搜索關(guān)鍵詞會(huì)被分配到同一個(gè)機(jī)器上。每個(gè)機(jī)器會(huì)分別計(jì)算關(guān)鍵詞出現(xiàn)的次數(shù)，最后合并起來(lái)就是最終的結(jié)果。實(shí)際上，這里的處理過(guò)程也是 MapReduce 的基本設(shè)計(jì)思想

加深理解：服務(wù)器會(huì)提前把1T分為很多份，給不同的計(jì)算機(jī)。 當(dāng)關(guān)鍵詞myth來(lái)了，所有計(jì)算機(jī)都搜，搜到的結(jié)果，hash一下，得到的值都是一樣的。 hash值位數(shù)很大，所以需要一個(gè)函數(shù)，讓這些hash百分百到一臺(tái)機(jī)子上，這就是對(duì)n取模了。 因?yàn)閔ash都一樣，所以取模后都到一臺(tái)機(jī)子上了。 相當(dāng)于很多臺(tái)計(jì)算機(jī)，瞬間得到結(jié)果，轉(zhuǎn)移到一臺(tái)機(jī)子上。

2、如何快速判斷圖片是否在圖庫(kù)中？

如何快速判斷圖片是否在圖庫(kù)中？上一節(jié)介紹了一種方法，即給每個(gè)圖片取唯一標(biāo)識(shí)（或者信息摘要），然后構(gòu)建散列表。假設(shè)圖庫(kù)中有 1 億張圖片，很顯然，在單臺(tái)機(jī)器上構(gòu)建散列表是行不通的。因?yàn)閱闻_(tái)機(jī)器的內(nèi)存有限，而 1 億張圖片構(gòu)建散列表顯然遠(yuǎn)遠(yuǎn)超過(guò)了單臺(tái)機(jī)器的內(nèi)存上限。

方案：同樣可以對(duì)數(shù)據(jù)進(jìn)行分片，然后采用多機(jī)處理。

具體思路：

• 準(zhǔn)備 n 臺(tái)機(jī)器，讓每臺(tái)機(jī)器只維護(hù)某一部分圖片對(duì)應(yīng)的散列表。
• 每次從圖庫(kù)中讀取一個(gè)圖片，計(jì)算唯一標(biāo)識(shí)，然后與機(jī)器個(gè)數(shù) n 求余取模，得到的值就對(duì)應(yīng)要分配的機(jī)器編號(hào)，然后將這個(gè)圖片的唯一標(biāo)識(shí)和圖片路徑發(fā)往對(duì)應(yīng)的機(jī)器構(gòu)建散列表。
• 當(dāng)要判斷一個(gè)圖片是否在圖庫(kù)中的時(shí)候，通過(guò)同樣的哈希算法，計(jì)算這個(gè)圖片的唯一標(biāo)識(shí)，然后與機(jī)器個(gè)數(shù) n 求余取模。假設(shè)得到的值是 k，那就去編號(hào) k 的機(jī)器構(gòu)建的散列表中查找。

現(xiàn)在估算一下，給這 1 億張圖片構(gòu)建散列表大約需要多少臺(tái)機(jī)器。散列表中每個(gè)數(shù)據(jù)單元包含兩個(gè)信息，哈希值和圖片文件的路徑。假設(shè)通過(guò) MD5 來(lái)計(jì)算哈希值，那長(zhǎng)度就是 128 比特，也就是 16 字節(jié)。文件路徑長(zhǎng)度的上限是 256 字節(jié)，我們可以假設(shè)平均長(zhǎng)度是 128 字節(jié)。如果我們用鏈表法來(lái)解決沖突，那還需要存儲(chǔ)指針，指針只占用 8 字節(jié)。

所以，散列表中每個(gè)數(shù)據(jù)單元就占用 152 字節(jié)（這里只是估算，并不準(zhǔn)確）。假設(shè)一臺(tái)機(jī)器的內(nèi)存大小為 2GB，散列表的裝載因子為 0.75，那一臺(tái)機(jī)器可以給大約 1000 萬(wàn)（2GB*0.75/152）張圖片構(gòu)建散列表。所以，如果要對(duì) 1 億張圖片構(gòu)建索引，需要大約十幾臺(tái)機(jī)器。在工程中，這種估算還是很重要的，能讓我們事先對(duì)需要投入的資源、資金有個(gè)大概的了解，能更好地評(píng)估解決方案的可行性。實(shí)際上，針對(duì)這種海量數(shù)據(jù)的處理問(wèn)題，我們都可以采用多機(jī)分布式處理。借助這種分片的思路，可以突破單機(jī)內(nèi)存、CPU 等資源的限制。

七：分布式存儲(chǔ)

為了提高數(shù)據(jù)的讀取、寫(xiě)入能力，一般都采用分布式的方式來(lái)存儲(chǔ)數(shù)據(jù)，比如分布式緩存。海量的數(shù)據(jù)需要緩存就需要將數(shù)據(jù)分布在多臺(tái)機(jī)器上。該如何決定將哪個(gè)數(shù)據(jù)放到哪個(gè)機(jī)器上呢？借用前面數(shù)據(jù)分片的思想，即通過(guò)哈希算法對(duì)數(shù)據(jù)取哈希值，然后對(duì)機(jī)器個(gè)數(shù)取模，這個(gè)最終值就是應(yīng)該存儲(chǔ)的緩存機(jī)器編號(hào)。

問(wèn)題：如果數(shù)據(jù)增多，原來(lái)的 10 個(gè)機(jī)器已經(jīng)無(wú)法承受了，就需要擴(kuò)容了，比如擴(kuò)到 11 個(gè)機(jī)器，這時(shí)候麻煩就來(lái)了。因?yàn)?#xff0c;這里并不是簡(jiǎn)單地加個(gè)機(jī)器就可以了。原來(lái)的數(shù)據(jù)是通過(guò)與 10 來(lái)取模的。比如 13 這個(gè)數(shù)據(jù)，存儲(chǔ)在編號(hào)為 3 這臺(tái)機(jī)器上。但是新加了一臺(tái)機(jī)器中，我們對(duì)數(shù)據(jù)按照 11 取模，原來(lái) 13 這個(gè)數(shù)據(jù)就被分配到 2 號(hào)這臺(tái)機(jī)器上了。

所有的數(shù)據(jù)都要重新計(jì)算哈希值，然后重新搬移到正確的機(jī)器上。這樣就相當(dāng)于，緩存中的數(shù)據(jù)一下子就都失效了。所有的數(shù)據(jù)請(qǐng)求都會(huì)穿透緩存，直接去請(qǐng)求數(shù)據(jù)庫(kù)。這樣就可能發(fā)生雪崩效應(yīng)，壓垮數(shù)據(jù)庫(kù)。

方案：需要一種方法，使得在新加入一個(gè)機(jī)器后，并不需要做大量的數(shù)據(jù)搬移。這時(shí)候，一致性哈希算法就要登場(chǎng)了。

核心思想：假設(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ù)，從原來(lái)的機(jī)器中搬移到新的機(jī)器中。這樣，既不用全部重新哈希、搬移數(shù)據(jù)，也保持了各個(gè)機(jī)器上數(shù)據(jù)數(shù)量的均衡。除此之外，借助一個(gè)虛擬的環(huán)和虛擬結(jié)點(diǎn)，更加優(yōu)美地實(shí)現(xiàn)出來(lái)。

內(nèi)容小結(jié)

• 在負(fù)載均衡應(yīng)用中，利用哈希算法替代映射表，可以實(shí)現(xiàn)一個(gè)會(huì)話粘滯的負(fù)載均衡策略。
• 在數(shù)據(jù)分片應(yīng)用中，通過(guò)哈希算法對(duì)處理的海量數(shù)據(jù)進(jìn)行分片，多機(jī)分布式處理，可以突破單機(jī)資源的限制。
• 在分布式存儲(chǔ)應(yīng)用中，利用一致性哈希算法，可以解決緩存等分布式系統(tǒng)的擴(kuò)容、縮容導(dǎo)致數(shù)據(jù)大量搬移的難題。

總結(jié)

以上是生活随笔為你收集整理的22 | 哈希算法（下）：哈希算法在分布式系统中有哪些应用？的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。