用go实现一致性hash算法

前言

相信大家对一致性hash的用处很熟悉了吧，我这边就只简单的说一下，一致性哈希算法（Consistent Hashing）最早在论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中被提出。简单来说，一致性哈希将整个哈希值空间组织成一个虚拟的圆环（0-2^32-1）。

优势

可扩展性。一致性哈希算法保证了增加或减少服务器时，数据存储的改变最少，相比传统哈希算法大大节省了数据移动的开销。
更好地适应数据的快速增长。采用一致性哈希算法分布数据，当数据不断增长时，部分虚拟节点中可能包含很多数据、造成数据在虚拟节点上分布不均衡，此时可以将包含数据多的虚拟节点分裂，这种分裂仅仅是将原有的虚拟节点一分为二、不需要对全部的数据进行重新哈希和划分。虚拟节点分裂后，如果物理服务器的负载仍然不均衡，只需在服务器之间调整部分虚拟节点的存储分布。这样可以随数据的增长而动态的扩展物理服务器的数量，且代价远比传统哈希算法重新分布所有数据要小很多。

实践

本文的一致性hash算法实现了

服务器设置虚拟节点，做到node均衡
服务器的权重，可以根据服务器可承受压力来设置对应权重

package main

import (
	"crypto/sha1"
	"fmt"
	"sort"
	"strconv"
)

//服务器结构体 地址和存储权重
type server struct {
	addr   string
	weight int
}

//当前服务器相关信息
var servers []server

//默认的hash节点数
const defaultNodeNum = 100

//基础虚拟节点
type virtualNode struct {
	nodeKey string
	spotVal uint32
}

type nodes struct {
	virtualNodesArray []virtualNode
}

func (p *nodes) Len() int           { return len(p.virtualNodesArray) }
func (p *nodes) Less(i, j int) bool { return p.virtualNodesArray[i].spotVal < p.virtualNodesArray[j].spotVal }
func (p *nodes) Swap(i, j int)      { p.virtualNodesArray[i], p.virtualNodesArray[j] = p.virtualNodesArray[j], p.virtualNodesArray[i] }
func (p *nodes) Sort()              { sort.Sort(p) }

//生成对应uint32
func getUint32Val(s string) (v uint32) {
	//进行sha1
	h := sha1.New()
	defer h.Reset()
	h.Write([]byte(s))
	hashBytes := h.Sum(nil)
	//go语言的位运算符处理
	if len(hashBytes[4:8]) == 4 {
		v = (uint32(hashBytes[3]) << 24) | (uint32(hashBytes[2]) << 12) | (uint32(hashBytes[1]) << 6) | (uint32(hashBytes[0]) << 3)
	}

	return
}

func (p *nodes) setVirtualNodesArray(servers []server) {
	if len(servers) < 1 {
		return
	}
	//根据权重与节点数，维护一个map - 所有的hash圈上的值对应ip
	for _, v := range servers {
		//第一步计算出每台机器对应的虚拟节点数
		totalVirtualNodeNum := defaultNodeNum * v.weight
		for i := 0; i < totalVirtualNodeNum; i++ {
			iString := strconv.Itoa(i)
			//虚拟节点地址
			virtualAddr := fmt.Sprintf("%s:%s", v.addr, iString)

			virNode := virtualNode{
				nodeKey: v.addr,
				spotVal: getUint32Val(virtualAddr),
			}

			p.virtualNodesArray = append(p.virtualNodesArray, virNode)
		}
		p.Sort()
	}
}

//获取当前数据key对应的存储服务器
func (p *nodes) getNodeSever(w uint32) (addr string){
	i := sort.Search(len(p.virtualNodesArray), func(i int) bool { return p.virtualNodesArray[i].spotVal >= w })
	return p.virtualNodesArray[i].nodeKey
}

func main() {
	vNodes := new(nodes)
	servers = append(servers, server{"127.0.0.1", 1}, server{"127.0.0.2", 2}, server{"127.0.0.3", 3})
	//先赋值，生成虚拟node
	vNodes.setVirtualNodesArray(servers)
	//传入对应的文件名，作为文件key
	fname := "demo.jpg"
	uint32Val := getUint32Val(fname)

	ser := vNodes.getNodeSever(uint32Val)
	fmt.Println("文件对应存储服务器",ser)
}

附加

这里只是实现了一致性hash的基本使用，如果对算法优化，或者其他的功能添加有想法，作者非常乐于和大家一起学习，改进。