请稍等 ...
×

采纳答案成功!

向帮助你的同学说点啥吧!感谢那些助人为乐的人

关于一致性hash输出结果并不均匀的问题

回答1 浏览102 2020-10-11 18:44:41
package load_balance

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

//
type Hash func(data []byte) uint32

type Uint32Slice []uint32

func (u Uint32Slice) Len() int {
	return len(u)
}

func (u Uint32Slice) Less(i, j int) bool {
	return u[i] < u[j]
}

func (u Uint32Slice) Swap(i, j int) {
	u[i],u[j] = u[j],u[i]
}

type consistentHashBalance struct {
	mux sync.RWMutex
	hash Hash
	replicas int // 复制因子,虚拟节点
	keys Uint32Slice //存放排序后的节点hash的切片
	hashMap map[uint32]string //节点hash和addr的map,key是hash值,value是addr的值
}

func NewConsistentHashBalance(replicas int,fn Hash) *consistentHashBalance{
	m :=&consistentHashBalance{
		replicas: replicas,
		hash: fn,
		hashMap: make(map[uint32]string),
	}
	if m.hash == nil{
		m.hash=crc32.ChecksumIEEE
	}
	return m
}

//判断节点hash的切片是否为空
func (c *consistentHashBalance)IsEmpty()bool  {
	return len(c.keys)==0
}


//添加节点
func (c *consistentHashBalance)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()
	//给当前的addr生成虚拟节点hash,并存放在切片里面里面
	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
	}
	//对虚拟节点hash值排序,方便二分查找
	sort.Sort(c.keys)
	return nil
}

func (c *consistentHashBalance)Get(key string)(string,error)  {
	if c.IsEmpty(){
		return "",errors.New("hash Node is empty")
	}
	hash := c.hash([]byte(key))
	//通过二分查找获取最优节点
	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
}

这是本人的代码,但是结果并不均匀,

测试代码

package load_balance

import (
	"fmt"
	"testing"
)

func TestNewConsistentHashBalance(t *testing.T) {
	rb := NewConsistentHashBalance(10,nil)
	rb.Add("127.0.0.1:2005")
	rb.Add("127.0.0.1:2006")
	rb.Add("127.0.0.1:2007")
	rb.Add("127.0.0.1:2008")
	rb.Add("127.0.0.1:2009")


	fmt.Println(rb.Get("http://127.0.0.1:2002/test"))
	fmt.Println(rb.Get("http://127.0.0.1:2002/add"))
	fmt.Println(rb.Get("http://127.0.0.1:2002/getUser"))
	fmt.Println(rb.Get("http://127.0.0.1:2002/test"))
	fmt.Println(rb.Get("http://127.0.0.1:2002/func"))
	fmt.Println("---------------")
	fmt.Println(rb.Get("127.0.0.1"))
	fmt.Println(rb.Get("192.168.0.1"))
	fmt.Println(rb.Get("127.0.0.1"))

}

输出结果

图片描述

添加回答

已采纳回答

你输出的结果没问题啊,第1第4一致的

2020-10-20 10:14:49

(打造简历金牌项目)Vue+Go 开发企业级微服务网关项目

难度中级
时长30小时
人数797
好评度100%

简历中摒弃烂大街的培训机构项目,带你开发企业级微服务网关

讲师

互联网老鸟,技术博客专家,知名互联网公司资深开发工程师,负责部门的技术架构工作。从0到1经历过多个热门产品的后端架构开发,也经历过多次产品的重构和平台迁移。热衷于技术分享,对微服务、网关技术有独到见解。

意见反馈 帮助中心 APP下载
官方微信