Golang 一致性 Hash 算法實現

❝

一致性 hash 算法是在分佈式應用中使用廣泛。其主要作用是爲了解決服務中的熱點問題。例如在分佈式數據存儲，比如 Redis 緩存集羣、有狀態的任務作業等，通過其解決請求的熱點問題，並且可以緩解當發生服務變動時出現的負載不平衡情況。

❞

本文將簡單介紹一致性 HASH 算法，並分析 golang 的一個開源實現包 (github.com/stathat/consistent)

一致性 hash 算法原理

解決的問題

在分佈式存儲中，爲了保證不同機器緩存的數據均衡性以及負載的均衡性，一般會在代理層先做一次 hash。正常情況下，我們會做取模操作，然後將服務分配給不同的機器。但是這種情況下當某臺服務宕機或者有新機器加入時，會直接影響到所有機器的緩存。爲了解決這個問題，所以出現了一致性 hash 算法。

如何解決

一致性 hash 算法，主要是解決如何將 hash 後的值映射到既定的機器中。下面是 hash 步驟：

1，將 hash 值構造爲一個圓環，一般爲 [0,2^32 - 1] 2. 在圓環上均勻的挑選 hash 點，作爲機器的節點 3. 在訪問機器時，hash 到圓環的某個點上，然後順時針訪問到的第一個節點即爲需要訪問的機器。

這樣，當某臺機器宕機時，宕機機器的下一臺機器將承包宕機機器的存儲任務。如果 hash 環中的兩個機器節點中添加了一個機器節點，那原有的節點存儲任務將被分一部分存儲任務給新增加的節點。

昇華

正常情況下，如果使用上面說的一致性 hash 算法，出現宕機時，一臺機器將幹兩臺機器的活，這顯然是不科學的。因此還需要有虛擬節點的概念。將虛擬節點放在圓環上，然後真正的服務節點維護多個虛擬節點（並且需要保證一臺服務節點上的多個虛擬節點需要離散分佈）。這樣，當一個服務節點宕機後，其實是多個離散的虛擬節點從 hash 環中消失，這樣可以保證正常的機器在保留原有數據的基礎上，還能承載宕機對應的離散節點的負載。

一致性 hash 算法的 golang 實現

github.com/stathat/consistent 是 golang 實現的一個一致性 hash 算法。

數據結構

在實現中，增加了分佈式緩存中較爲實用的副本的概念。結構如下：

type Consistent struct {
  circle           map[uint32]string  // 保存環
  members          map[string]bool  // 成員標記
  sortedHashes     uints // []int32 類型  標記了環上的虛擬節點，有序的slice
  NumberOfReplicas int // 副本數量
  count            int64 // 節點數量
  scratch          [64]byte // 未使用
  UseFnv           bool // 標記使用 FNV-1a hash
  sync.RWMutex  // 讀寫鎖標記
}

設置節點

初始化節點時，需要提供各個節點的名稱，以及副本的數量。初始化將進行如下操作：

  1. 將 hash 與 node 名的映射存入 circle 中

  2. 將 members 標記爲 true

  3. 將 hash 值放入有序的 sortedHashes 中

func (c *Consistent) Set(elts []string) {
  c.Lock()
  defer c.Unlock()
  for k := range c.members {  // 首先將清除不在elts 集合中的數據
    found := false
    for _, v := range elts {
      if k == v {
        found = true
        break
      }
    }
    if !found {
      c.remove(k)
    }
  }
  for _, v := range elts {  // 之後依次添加
    _, exists := c.members[v]
    if exists {
      continue
    }
    c.add(v)
  }
}
func (c *Consistent) add(elt string) {
  for i := 0; i < c.NumberOfReplicas; i++ {
    c.circle[c.hashKey(c.eltKey(elt, i))] = elt
  }
  c.members[elt] = true
  c.updateSortedHashes()  // 更新sortedHashes 字段，保證有序
  c.count++
}

訪問

當通過 name 映射一個 node 時，首先計算 hash 值，然後通過二分查找的方法從 sortedHashes slice 中拿到對應的 node 的 hash 值，最後通過 circle 映射出對應的 node name.

func (c *Consistent) Get(name string) (string, error) {
  c.RLock()
  defer c.RUnlock()
  if len(c.circle) == 0 {
    return "", ErrEmptyCircle
  }
  key := c.hashKey(name)
  i := c.search(key)
  return c.circle[c.sortedHashes[i]], nil
}

刪除

當某臺機器宕機時，可以刪除對應的 node 節點，以釋放快速調整服務請求。

func (c *Consistent) remove(elt string) {
  // 代碼中有加鎖
  for i := 0; i < c.NumberOfReplicas; i++ {
    delete(c.circle, c.hashKey(c.eltKey(elt, i)))
  }
  delete(c.members, elt)
  c.updateSortedHashes()
  c.count--
}

總結

從代碼的實現中，我們可以看出：

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

猜你喜歡