【golang】分散式緩存 - 一致性哈希演算法

前言

　　之前也瞭解到過一致性哈希演算法，但是沒有用go實現過，剛好最近看GeeCache，動手實現下一致性哈希演算法

正文:

　　我們先來想下一致性哈希演算法的數據結構含有哪些內容:

　　1.map 用來存儲虛擬節點對應的真實節點，是一個映射表

　　2.hash 哈希函數

　　3.key 哈希環，存儲所有虛擬節點

　　4.replicas 虛擬節點的倍數

瞭解過一致性哈希演算法的朋友，應該是能夠理解為什麼要有上面的內容，下麵我們用代碼實現下:

type Hash func([]byte) uint32
type Map struct {
    hash    Hash  // hash演算法
    key     []int // hash環
    replicas int  // 虛擬節點的數量
    m      map[int]string // 虛擬節點和真實節點的映射表
}

下麵，我們實現獲取節點的方法:

　　將key經過hash運算，在哈希環上順時針找到第一個節點，存入

func (m *Map) Get(key string) string {
    hash := int(m.hash([]byte(key)))  // 獲取key對應的hash值
//    順時針找到第一個虛擬節點
    idx := sort.Search(len(m.key), func(i int) bool {
        return m.key[i] >= hash
    })
//    返回對應的真實節點:記得對哈希環取餘
    return m.m[m.key[idx % len(m.key)]]
}

添加節點的方法

func (m *Map) Add(key ...string)  {
    for _,realKey := range key{
        for i := 0; i < m.replicas; i++ {
        //    真實節點對應的虛擬節點
            hash := int(m.hash([]byte(strconv.Itoa(i)+realKey)))
        //    添加到換上
            m.key = append(m.key,hash)
        //    添加到映射表上
            m.m[hash] = realKey
        }
    }
    // 遞增排序，方便順時針查找
    sort.Ints(m.key)
}

以上就是一致性哈希的實現方法，也挺好理解的。記錄下~

| 不驕不躁，保持學習