Golang 实现一致性哈希负载均衡

个人理解：一致性哈希算法

1. 根据每一台服务器不同的 ip:port 根据自己的 key生成算法 ，生成一个唯一的 key 值
2. key => ip:port 把机器唯一的 key 映射机器访问地址 ip:port 设置到一个 有序的循环圆 上
3. 请求过来的时候，根据请求内容生成按 自己的 key生成算法 也生成一个 请求的 key
4. 请求的 key 和 有序的循环圆 上 机器的 key 循环对比， 第一个 机器的 key 大于 请求的 key 就是最优解，由它来处理该请求
5. 如果 请求的 key 比 有序的循环圆 上 机器的 key 都大，那么由 圆上第一条机器 处理
6. 有序的循环圆 上机器，根据访问情况。近实时增删机器映射

一致性哈希负载均衡 具体编码实现

 package load_balance

import (
"errors"
"fmt"
"hash/crc32"
"sort"
"strconv"
"strings"
"sync"
)

type Hash func(data []byte) uint32

type UInt32Slice []uint32

func (s UInt32Slice) Len() int {
return len(s)
}

func (s UInt32Slice) Less(i, j int) bool {
return s[i] < s[j]
}

func (s UInt32Slice) Swap(i, j int) {
s[i], s[j] = s[j], s[i]
}

type HashBanlance struct {
mux      sync.RWMutex
hash     Hash
replicas int               //复制因子
keys     UInt32Slice       //已排序的节点hash切片
hashMap  map[uint32]string //节点哈希和Key的map,键是hash值，值是节点key

//观察主体
conf LoadBalanceConf
}

func NewHashBanlance(replicas int, fn Hash) *HashBanlance {
m := &HashBanlance{
replicas: replicas,
hash:     fn,
hashMap:  make(map[uint32]string),
}
if m.hash == nil {
//最多32位,保证是一个2^32-1环
m.hash = crc32.ChecksumIEEE
}
return m
}

// 验证是否为空
func (c *HashBanlance) IsEmpty() bool {
return len(c.keys) == 0
}

// Add 方法用来添加缓存节点，参数为节点key，比如使用IP
func (c *HashBanlance) Add(params ...string) error {
if len(params) == 0 {
return errors.New("param len 1 at least")
}
addr := params[0]
c.mux.Lock()
defer c.mux.Unlock()
// 结合复制因子计算所有虚拟节点的hash值，并存入m.keys中，同时在m.hashMap中保存哈希值和key的映射
for i := 0; i < c.replicas; i++ {
hash := c.hash([]byte(strconv.Itoa(i) + addr))
c.keys = append(c.keys, hash)
c.hashMap[hash] = addr
}
// 对所有虚拟节点的哈希值进行排序，方便之后进行二分查找
sort.Sort(c.keys)
return nil
}

// Get 方法根据给定的对象获取最靠近它的那个节点
func (c *HashBanlance) Get(key string) (string, error) {
if c.IsEmpty() {
return "", errors.New("node is empty")
}
hash := c.hash([]byte(key))

// 通过二分查找获取最优节点，第一个"服务器hash"值大于"数据hash"值的就是最优"服务器节点"
idx := sort.Search(len(c.keys), func(i int) bool { return c.keys[i] >= hash })

// 如果查找结果 大于 服务器节点哈希数组的最大索引，表示此时该对象哈希值位于最后一个节点之后，那么放入第一个节点中
if idx == len(c.keys) {
idx = 0
}
c.mux.RLock()
defer c.mux.RUnlock()
return c.hashMap[c.keys[idx]], nil
}

func (c *HashBanlance) SetConf(conf LoadBalanceConf) {
c.conf = conf
}  

负载轮询测试代码

测试结果