Golang 一文讀懂一致性 Hash 算法

虛構場景：我們有 10 億張圖片，存在了 1000 臺服務器上，圖片命名格式爲 [年份 4 位][月份 2 位][毫秒時間戳 13 位]，圖片信息存儲在了 MySQL 數據庫中，現在爲了提高圖片的查找速度，請幫我們設計一套圖片緩存系統，前期先給 10 臺服務器，每臺服務器可以存儲 100 萬張圖片，請設計一種算法，可以實現圖片快速查找？

我們分析一下，首先，有 10 臺服務器，每臺服務器可存儲 100 萬張圖片，總計可存儲 1000 萬張圖片，我們有 10 億張圖片，所以我們的緩存系統要實現淘汰算法，還得設計一種算法，這 1000 萬張圖片如何存儲在這 10 臺服務器上？

今天，重點講如何實現 1000 萬張圖片存儲在這 10 臺服務器上，後期講淘汰算法，及單飛模式防止 Mysql 數據庫被擊穿。

首先，想到的就是求模算法，每請求一次圖片，就計算圖片的 Hash 值，然後對 10 求模，算出將要查找的服務器，如果服務器上存在該圖片，就直接返回圖片地址，如果不存在，需要查詢 mysql 服務器，將圖片下載下來存儲到該服務器，然後再返回給客戶端。這種模式既簡單好理解，也容易實現，但它缺少了擴展性和穩定性。假如有 1 臺服務器宕機，或者新增 2 臺服務器，那麼這種算法計算的值將全部失效。爲什麼會失效呢？假如某張圖片 2023091695739153928.jpg，根據對 10 求模算法，現在存儲在第 8 臺服務器。現在新增了 2 臺服務器，分別定義爲 11 號，和 12 號服務器。如果現在再去查找，則算法變爲對 12 求模，得到的值爲 0，而這臺服務器上卻沒有這張圖片。

我們對其進行改良，分析上面的問題，可知隨着服務器數量的變化，它的餘數也在變化，我們乾脆對一個很大的數進行求模，例如 2^32 次方，約 42 億多，這樣的話，10 億張圖片都可以容下，都有它的位置，且是固定的，可惜，我們沒有這麼多的服務器，如何將圖片存儲在服務器上呢？我們能想到的是，將一個區間的數據存在服務器上，我們將其想象成一個很長很長的線段，由 42 億多個點組成，線段上的每個點，代表一張圖片。而每個服務器也進行哈希求模，放置在線段上，服務器在線段位置的前面的點都存儲這臺服務器上。例如下圖：

通過以上的改良，我們知道，新增服務器或減少服務器，隻影響新服務器在線段上的位置到前一個服務器在線段上的位置之間的圖片。就會變成下圖：

我們再進行改良，將線段首尾連接起來，組成一個圓環，且增加虛擬節點服務器，這樣可以平衡圖片數據在服務器上均衡存放。例如下圖：

上面的 A1,A2,A3 所對應的服務器都爲 A 服務器，這樣做可以增加服務器容量的均衡性，不會發生數據傾斜。接下來，我們引入今天的主角，一致性 Hash 算法。

一致性哈希算法在 1997 年由麻省理工學院提出，是一種特殊的哈希算法，在移除或者添加一個服務器時，能夠儘可能小地改變已存在的服務請求與處理請求服務器之間的映射關係；

一致性哈希解決了簡單哈希算法在分佈式哈希表（Distributed Hash Table，DHT）中存在的動態伸縮等問題。一致性 hash 算法本質上也是一種取模算法。以前的求模是對服務器的數量求模，而一致性 Hash 算法是對 2^32 （約 42 億多）求模。算法的具體計算步驟如下：

1，將整個哈希值空間按照順時針方向組成一個虛擬的圓環，稱爲 Hash 環。

2，將每個服務器使用 Hash 函數進行 Hash，可以選擇服務器的 IP 或主機名作爲關鍵字進行哈希，從而確定每臺機器在哈希圓環上的位置，服務器可以增加虛擬節點，虛擬節點映射到物理服務器。

3，將數據 key 使用相同的函數計算出哈希值，然後確定在 Hash 環的位置，從此位置沿順時針尋找，遇到的第一臺服務器，就是要存儲到此的服務器。

我們使用 Golang 來實現一致性 Hash 算法。我們定義的 Map 結構，包含 hash 算法，虛擬節點數，存放 key 的排序數組，及虛擬節點到物理服務器的映射。代碼中有註釋。

type Hash func(data []byte) uint32
// hash 一個hash算法，可以自定義hash算法，默認爲crc32.ChecksumIEEE
// replicas 每個peer節點可產生幾個虛擬節點，由該值確定
// keys 儲存所有虛擬節點的hash值，每個值對應一個鍵值
// hashMap 根據hash值找到相應的peer，真實主機節點
type Map struct {
    hash     Hash
    replicas int
    keys     []int // Sorted
    hashMap  map[int]string
}
// 新建一個Map實例，用來存儲節點和鍵值的關係
func New(replicas int, fn Hash) *Map {
    m := &Map{
        replicas: replicas,
        hash:     fn,
        hashMap:  make(map[int]string),
    }
    if m.hash == nil {
        m.hash = crc32.ChecksumIEEE
    }
    return m
}
// 查看當前map中是否有鍵值
func (m *Map) IsEmpty() bool {
    return len(m.keys) == 0
}
// 添加鍵值到map中
func (m *Map) Add(keys ...string) {
    for _, key := range keys {
      // 一個key就是一個peer節點
      // 對於每個key，都會生成replicas個虛擬節點，並把虛擬節點和key的對應關係存起來
        for i := 0; i < m.replicas; i++ {
        // 算法,將Node-A節點按照副本數量，分成0Node-A,1Node-A,2Node-A
            hash := int(m.hash([]byte(strconv.Itoa(i) + key)))
            // 算出的hash 值添加到虛擬節點列表中
            m.keys = append(m.keys, hash)
            // 將hash值和真實的節點進行關聯
            m.hashMap[hash] = key
        }
    }
    // 排序，這個動作非常重要，因爲只有這樣，才能構造一個有序的 Hash 環
    sort.Ints(m.keys)
}
// 這邊的key爲一個cache中的key，即要查詢的key
// 計算這個key的hash值，找到與之最爲接近的虛擬節點，再通過虛擬節點找到具體的peer
func (m *Map) Get(key string) string {
    if m.IsEmpty() {
        return ""
    }
  // 計算key對應的hash值
    hash := int(m.hash([]byte(key)))
    // 使用二分法查找key對應的hash值最近的虛擬節點
    idx := sort.Search(len(m.keys), func(i int) bool { return m.keys[i] >= hash })
    // 一致性hash的虛擬節點應該構成一個環
    if idx == len(m.keys) {
        idx = 0
    }
    return m.hashMap[m.keys[idx]]
}

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/Y16a_vUZdhX0nvIbORI7Yw

猜你喜歡