Mysql分片：一致性哈希算法

一、一致性哈希的核心原理

????????哈希取模最大的痛點是：當分片數量（例如數據庫節點數）發生變化時，幾乎所有數據的哈希結果都會改變，導致大規模的數據遷移。一致性哈希就是為了解決這個“伸縮性差”的問題而誕生的。

核心思想：數據和節點共舞的“虛擬圓環”

????????一致性哈希不再簡單粗暴地用數據哈希值對節點數量取模。它的核心在于引入了一個 “哈希環”（Hash Ring 或 Hash Circle）的概念。你可以把這個哈希環想象成一個巨大的虛擬圓盤，它的周長覆蓋了所有可能的哈希值范圍（比如從0到 $^{2^{32}}$ -1，或者 $^{2^{64}}$ ?1，取決于哈希算法的輸出范圍）。

在這個哈希環上，有兩類重要的參與者：

存儲節點（服務器/數據庫）：
- 我們不再直接用服務器數量做模數。而是將每一個真實的存儲節點（比如你的 db_0、db_1、db_2 這些數據庫服務器），通過一個哈希函數計算出一個哈希值。
- 這些哈希值就相當于服務器在圓環上的“座標點”。每個節點都會根據自己的哈希值，被放置到哈希環上的一個特定位置。
數據記錄：
- 同樣地，每一條待存儲的數據記錄（比如一個用戶的信息、一個訂單的詳情），我們會選擇它的某個字段作為分片鍵（比如 user_id 或 order_id）。
- 然后，我們用同樣的哈希函數計算這個分片鍵的哈希值，把數據也映射到哈希環上的一個位置。這個哈希值就像是數據的“身份證號碼”，它也對應著圓環上的一個“座標點”。

????????哈希環示意圖：?

? ? ? ? ? ? ? ? ? ? ? ?

智能羅盤：數據如何找到它的“歸宿”？

????????當一條數據（或一個查詢請求）要尋找它的存儲位置時，一致性哈希的“智能羅盤”就會啟動：

數據路由法則：從數據在哈希環上的存儲數據位置開始，沿著圓環順時針方向查找，遇到的第一個存儲節點，就是這條數據存儲的節點位置！

比如，在該哈希環上：?

data1 存儲在 nodeA：
- data1 位于 0 和 nodeA 之間。從 data1 順時針查找，遇到的第一個存儲節點是 nodeA。
data2?存儲在 nodeB：
- data2?位于 nodeA?和 nodeB?之間。從 data2?順時針查找，遇到的第一個存儲節點是 nodeB。
data3 存儲在 nodeC：
- data3 位于 nodeB?和 nodeC?之間。從 data3 順時針查找，遇到的第一個存儲節點是 nodeC。
data4 存儲在 nodeA：
- data4 位于 nodeC 和 0 之間（或者說 nodeC 到 2^32-1 ?之間，因為環是閉合的）。從 data4 順時針查找，遇到的第一個存儲節點是 nodeA。

二、一致性哈希執行案例

我們來設計一個簡單且易于理解的一致性哈希執行案例。我們將聚焦在一個非常常見的場景：一個簡單的分布式緩存系統。

場景設定：

????????假設你正在開發一個熱門的社交應用，其中有很多用戶頭像圖片需要緩存。為了提高訪問速度和系統承載能力，你決定使用多個緩存服務器來存儲這些圖片。當用戶請求某個頭像時，你需要知道這張圖片存在哪個緩存服務器上。

緩存內容：用戶頭像圖片。
唯一標識：user_id (用戶ID)，我們將用它作為分片鍵。
緩存服務器：初始有 3 臺服務器，命名為 CacheA, CacheB, CacheC。

我們將使用一致性哈希來決定每張圖片存儲在哪臺緩存服務器上。

步驟一：服務器“入座”哈希環

在系統啟動時，我們的緩存服務器需要先在哈希環上找到自己的“座位”。

我們會用哈希函數計算每臺服務器名稱的哈希值：
- Hash("CacheA") rightarrow 假設得到 100
- Hash("CacheB") rightarrow 假設得到 1500
- Hash("CacheC") rightarrow 假設得到 3000

我們在這假設該哈希函數計算的哈希值在0-3599之間

（注：為了簡化，實際哈希值范圍很大，這里用小數字示意相對位置）?

我們將這些哈希值標注在哈希環上：

? ? ? ? ? ? ? ? ? ? ? ? ? ?

步驟二：用戶頭像圖片“找主人”

????????現在，當用戶請求或上傳一張頭像（user_id）時，系統需要知道它應該存在哪臺緩存服務器上。

我們以兩個用戶為例：

用戶ID: 1001 的頭像
- 我們用同樣的哈希函數計算 user_id = 1001 的哈希值：
  Hash("1001") rightarrow 假設得到 500
- 將 500 標注在哈希環上。
- 查找規則：從 500 這個點開始，沿著哈希環順時針方向查找，遇到的第一個緩存服務器是誰，它就歸誰管。
- 根據圖示，從 500 順時針，第一個遇到的服務器是 CacheB (1500)。
- 結論：用戶1001的頭像 存儲到 CacheB。
用戶ID: 2002 的頭像
- Hash("2002") rightarrow 假設得到 3200
- 將 3200 標注在哈希環上（這里同上，我就不在畫了）。
- 查找規則：從 3200 順時針查找，由于環是閉合的，它會繞過 3599?重新從 0 開始，遇到的第一個服務器是 CacheA (100)。
- 結論：用戶2002的頭像 存儲到 CacheA。

步驟三：服務器擴容，一致性哈希顯神通

? ? ? ?假設現在，你的社交應用用戶量暴增，CacheA, CacheB, CacheC 三臺服務器已經不夠用了！你需要新增一臺緩存服務器：CacheD。

哈希取模的痛點：如果是傳統哈希取模 (Hash(user_id) % N)，N從3變成4，那幾乎所有用戶頭像的位置都會重新計算，你需要把大量頭像數據從舊服務器搬到新位置，系統可能要停機維護，非常麻煩！
一致性哈希的優勢：
1. CacheD “入座”哈希環：
  - 我們計算 Hash("CacheD") rightarrow 假設得到 2000。
  - 將 CacheD (2000) 放置在哈希環上。它會落在 CacheB (1500) 和 CacheC (3000) 之間。
2. 數據遷移分析：
  - 觀察哈希環，CacheD 的加入，只會影響到它逆時針方向的那個服務器（CacheB）所負責的部分數據。
  - 原來從 CacheB (1500) 順時針到 CacheC (3000) 的這部分區間，現在被 CacheD (2000) 分割了。
  - 只有那些哈希值在 1500 到 2000 之間的用戶頭像，需要從 CacheB 遷移到 CacheD。
  - 而 CacheA 負責的頭像數據、以及 CacheB 負責的哈希值小于 1500 的頭像數據，位置完全不變！
? ? ? ? ? ? ? ? ??

????????這一特性是衡量分布式系統可伸縮性的關鍵優勢。相比于傳統哈希取模在節點變化時需要進行全局數據重分布，一致性哈希實現了漸進式、低影響的擴容/縮容操作，極大地降低了系統維護成本和業務中斷風險。

三、總結：

?????????一致性哈希算法通過將數據鍵與存儲節點共同映射至一個環形哈希空間，并基于“順時針最近匹配”原則進行數據路由，從而巧妙地解決了分布式系統在擴容或縮容場景下，傳統哈希取模算法導致的大規模數據遷移問題。這一機制顯著提升了系統的彈性伸縮能力和可用性。在構建高性能、高可擴展性的分布式緩存或分布式存儲系統時，一致性哈希提供了一種高效且穩定的數據分布與管理策略。

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/pingmian/88320.shtml
繁體地址，請注明出處：http://hk.pswp.cn/pingmian/88320.shtml
英文地址，請注明出處：http://en.pswp.cn/pingmian/88320.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！