一道滴滴的負載均衡前端面試題

02-02

這是之前我去面試滴滴時的一道面試題，它看起來可能不那麼的偏前端，但我仍然覺得很有意思，我省略安全校驗、意外錯誤處理等細節性的問題，單單來聊聊負載均衡相關的方面。當然了，我本身不是後端，這方面經驗肯定不是十分足，歡迎各位賜教。

問題是這樣的：我們要實現一個利用 WebSocket 進行實時通訊的基於 Web 的即時通訊應用，假設未來用戶量會很大，我們要用到多個伺服器，那我們如何實現兩個用戶間的通訊呢？

我們先來看看只有一台機器時的情況。

在連接上 WebSocket 後，我們會獲得一個 Socket 對象，我們將該 Socket 對象放到一張映射表上存起來。之後，我們就可以根據該 Socket 對象所對應的 user 的 uuid 來獲取到。

當 UserA 向 UserB 發送請求時，UserA 會在發送消息時攜帶上 UserB 的信息（比如 uuid），這樣後端伺服器就可以根據 UserA 提供的 UserB 的信息，從映射表中查到 UserB 對應的 Socket 對象，從而成功地向 UserB 發送消息。

用戶量少的時候我們可以這樣簡單地用單台機器來處理，我們再來看看多台機器會遇到一些什麼問題？

首先，我們面臨的第一個問題就是：如何知道另一個用戶在哪台伺服器上？

我們可能第一個想法就是：所有機器都使用一張映射表，映射表裡記錄了每台機器都儲存了哪些 Socket，當有新用戶連接的時候，被負載均衡器分配到的伺服器會向我們所有的其它伺服器發送一條消息，以更新映射表，這樣我們就成功地定位到了另一用戶所在的伺服器了。

但大家都會發現，這樣的策略雖然簡單，但非常的粗暴，當用戶數和伺服器數很多的時候，每次更新用戶上下線都是一種很大的壓力。

於是我們有了第二個想法：我們每台機器不再保存所有用戶的映射，我們使用單台伺服器（簡稱 S）來保存所有的用戶映射，當某伺服器需要尋找另一用戶所在的伺服器時，就向伺服器 S 查詢。

這樣的策略顯然是依賴單點伺服器的，性能的瓶頸會在這單台伺服器上。

回頭一想，我們或許方向有點走錯了，雖然我們要在單台機器上要依賴映射表，但在定位伺服器時不一定也要用映射表啊！然後就是第三個想法：我們使用一種演算法，來對 uuid 進行 hash，將得到的 hash 作為伺服器的 ID 就可以了。

我們定義一個函數 hash，它接受一個參數 uuid，返回一個對應伺服器的 ID：hash(uuid) => serverId。hash 函數我們用最簡單的演算法 mod——也就是取模——來舉例。比如我們有 6 台機器，uuid 為 7，那麼我們的運算過程是這樣的：hash(7) => mod(7, 6) => 1，於是我們就知道，uuid 為 7 的用戶所在的伺服器應該是 ID 為 1 的伺服器。

這種方法可以讓我們不再依賴單個節點。但它引入了新的問題：當我增加或減少機器數量的時候，會導致取模時的除數發生變化，這意味著我們需要把所有的在線用戶進行重新計算，運算量非常龐大。

那麼這個時候，殺手鐧要來了：一致性哈希。

一致性哈希簡單來講，就是我們建立無數個虛擬節點（比如 2^32 個），把它們圍成一個環狀。然後，我們把一些真實的伺服器放置在這些節點上，在執行 hash(uuid) 時，其除數為虛擬節點數，於是我們會得出一個虛擬節點的 ID，我們根據這個虛擬節點所在的位置，往後查找真實伺服器，從而定位到用戶所對應的伺服器中。在增減伺服器時，我們只需要移動很少量的對象（很少量的緩存會失效）。

關於一致性哈希，我找到一篇由 @劉夢馨寫的《聊聊一致性哈希》，這篇文章講解得非常的通俗易懂，大家想了解更多關於一致性哈希的話建議大家去閱讀。

參考文獻：

一致哈希 - 維基百科
聊聊一致性哈希 - 知乎專欄
題圖：ZStack 的伸縮性秘密（第二部分）無狀態服務