加關注，第一時間接收數據結構系列教程
上一節，我講了哈希算法的四個應用，它們分別是：安全加密、數據校驗、唯一標識、散列函數。今天，我們再來看剩餘三種應用：負載均衡、數據分片、分佈式存儲。
你可能已經發現，這三個應用都跟分佈式系統有關。沒錯，今天我就帶你看下，哈希算法是如何解決這些分佈式問題的。
應用五：負載均衡
我們知道，負載均衡算法有很多，比如輪詢、隨機、加權輪詢等。那如何才能實現一個會話粘滯（session sticky）的負載均衡算法呢？也就是說，我們需要在同一個客戶端上，在一次會話中的所有請求都路由到同一個服務器上。
最直接的方法就是，維護一張映射關係表，這張表的內容是客戶端 IP 地址或者會話 ID 與服務器編號的映射關係。客戶端發出的每次請求，都要先在映射表中查找應該路由到的服務器編號，然後再請求編號對應的服務器。這種方法簡單直觀，但也有幾個弊端：
- 如果客戶端很多，映射表可能會很大，比較浪費內存空間；
- 客戶端下線、上線，服務器擴容、縮容都會導致映射失效，這樣維護映射表的成本就會很大；
如果藉助哈希算法，這些問題都可以非常完美地解決。我們可以通過哈希算法，對客戶端 IP 地址或者會話 ID 計算哈希值，將取得的哈希值與服務器列表的大小進行取模運算，最終得到的值就是應該被路由到的服務器編號。 這樣，我們就可以把同一個 IP 過來的所有請求，都路由到同一個後端服務器上。
應用六：數據分片
哈希算法還可以用於數據的分片。我這裡有兩個例子。
1. 如何統計“搜索關鍵詞”出現的次數？
假如我們有 1T 的日誌文件，這裡面記錄了用戶的搜索關鍵詞，我們想要快速統計出每個關鍵詞被搜索的次數，該怎麼做呢？
我們來分析一下。這個問題有兩個難點，第一個是搜索日誌很大，沒辦法放到一臺機器的內存中。第二個難點是，如果只用一臺機器來處理這麼巨大的數據，處理時間會很長。
針對這兩個難點，我們可以先對數據進行分片，然後採用多臺機器處理的方法，來提高處理速度。具體的思路是這樣的：為了提高處理的速度，我們用 n 臺機器並行處理。我們從搜索記錄的日誌文件中，依次讀出每個搜索關鍵詞，並且通過哈希函數計算哈希值，然後再跟 n 取模，最終得到的值，就是應該被分配到的機器編號。
這樣，哈希值相同的搜索關鍵詞就被分配到了同一個機器上。也就是說，同一個搜索關鍵詞會被分配到同一個機器上。每個機器會分別計算關鍵詞出現的次數，最後合併起來就是最終的結果。
實際上，這裡的處理過程也是 MapReduce 的基本設計思想。
2. 如何快速判斷圖片是否在圖庫中？
如何快速判斷圖片是否在圖庫中？上一節我們講過這個例子，不知道你還記得嗎？當時我介紹了一種方法，即給每個圖片取唯一標識（或者信息摘要），然後構建散列表。
假設現在我們的圖庫中有 1 億張圖片，很顯然，在單臺機器上構建散列表是行不通的。因為單臺機器的內存有限，而 1 億張圖片構建散列表顯然遠遠超過了單臺機器的內存上限。
我們同樣可以對數據進行分片，然後採用多機處理。我們準備 n 臺機器，讓每臺機器只維護某一部分圖片對應的散列表。我們每次從圖庫中讀取一個圖片，計算唯一標識，然後與機器個數 n 求餘取模，得到的值就對應要分配的機器編號，然後將這個圖片的唯一標識和圖片路徑發往對應的機器構建散列表。
當我們要判斷一個圖片是否在圖庫中的時候，我們通過同樣的哈希算法，計算這個圖片的唯一標識，然後與機器個數 n 求餘取模。假設得到的值是 k，那就去編號 k 的機器構建的散列表中查找。
現在，我們來估算一下，給這 1 億張圖片構建散列表大約需要多少臺機器。
散列表中每個數據單元包含兩個信息，哈希值和圖片文件的路徑。假設我們通過 MD5 來計算哈希值，那長度就是 128 比特，也就是 16 字節。文件路徑長度的上限是 256 字節，我們可以假設平均長度是 128 字節。如果我們用鏈表法來解決衝突，那還需要存儲指針，指針只佔用 8 字節。所以，散列表中每個數據單元就佔用 152 字節（這裡只是估算，並不準確）。
假設一臺機器的內存大小為 2GB，散列表的裝載因子為 0.75，那一臺機器可以給大約 1000 萬（2GB*0.75/152）張圖片構建散列表。所以，如果要對 1 億張圖片構建索引，需要大約十幾臺機器。在工程中，這種估算還是很重要的，能讓我們事先對需要投入的資源、資金有個大概的瞭解，能更好地評估解決方案的可行性。
實際上，針對這種海量數據的處理問題，我們都可以採用多機分佈式處理。藉助這種分片的思路，可以突破單機內存、CPU 等資源的限制。
應用七：分佈式存儲
現在互聯網面對的都是海量的數據、海量的用戶。我們為了提高數據的讀取、寫入能力，一般都採用分佈式的方式來存儲數據，比如分佈式緩存。我們有海量的數據需要緩存，所以一個緩存機器肯定是不夠的。於是，我們就需要將數據分佈在多臺機器上。
該如何決定將哪個數據放到哪個機器上呢？我們可以借用前面數據分片的思想，即通過哈希算法對數據取哈希值，然後對機器個數取模，這個最終值就是應該存儲的緩存機器編號。
但是，如果數據增多，原來的 10 個機器已經無法承受了，我們就需要擴容了，比如擴到 11 個機器，這時候麻煩就來了。因為，這裡並不是簡單地加個機器就可以了。
原來的數據是通過與 10 來取模的。比如 13 這個數據，存儲在編號為 3 這臺機器上。但是新加了一臺機器中，我們對數據按照 11 取模，原來 13 這個數據就被分配到 2 號這臺機器上了。
因此，所有的數據都要重新計算哈希值，然後重新搬移到正確的機器上。這樣就相當於，緩存中的數據一下子就都失效了。所有的數據請求都會穿透緩存，直接去請求數據庫。這樣就可能發生雪崩效應，壓垮數據庫。
所以，我們需要一種方法，使得在新加入一個機器後，並不需要做大量的數據搬移。這時候，一致性哈希算法就要登場了。
假設我們有 k 個機器，數據的哈希值的範圍是 [0, MAX]。我們將整個範圍劃分成 m 個小區間（m 遠大於 k），每個機器負責 m/k 個小區間。當有新機器加入的時候，我們就將某幾個小區間的數據，從原來的機器中搬移到新的機器中。這樣，既不用全部重新哈希、搬移數據，也保持了各個機器上數據數量的均衡。
一致性哈希算法的基本思想就是這麼簡單。除此之外，它還會藉助一個虛擬的環和虛擬結點，更加優美地實現出來。這裡我就不展開講了，如果感興趣，你可以看下這個介紹。
除了我們上面講到的分佈式緩存，實際上，一致性哈希算法的應用非常廣泛，在很多分佈式存儲系統中，都可以見到一致性哈希算法的影子。
解答開篇 & 內容小結
這兩節的內容理論不多，比較貼近具體的開發。今天我講了三種哈希算法在分佈式系統中的應用，它們分別是：負載均衡、數據分片、分佈式存儲。
在負載均衡應用中，利用哈希算法替代映射表，可以實現一個會話粘滯的負載均衡策略。在數據分片應用中，通過哈希算法對處理的海量數據進行分片，多機分佈式處理，可以突破單機資源的限制。在分佈式存儲應用中，利用一致性哈希算法，可以解決緩存等分佈式系統的擴容、縮容導致數據大量搬移的難題。
覺得不錯，歡迎大家點贊和轉發，謝謝支持。
閱讀更多 xiuxiuing 的文章
