架构师训练营 1 期第 5 周作业 -- 一致性哈希算法

package hashcache

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

//哈希环最大值
const hashRingMax uint32 = 1<<32 - 1
const nodeCountPerMachine = 150 //每台机器上的虚拟节点数
//真机节点
type machine struct {
	machineId uint32 //机器ID
	ip        string //机器的IP地址
}

func (s *machine) GetValue(key string) (interface{}, error) {
	//todo为了演示一致性哈希算法,这里具体从机器内存获取数据的步骤直接作假了 生成一个返回
	return `{"user_id":"123","name":"test"}`, nil
}

//虚拟存储节点
type virtualNode struct {
	*machine         //虚拟节点对应的真实机器ID
	nodeId    uint32 //虚拟节点ID
	ringIndex uint32 //该节点在哈希环上的索引
}
//虚拟节点在哈希环上的索引
func (s *virtualNode) getRingIndex() uint32 {
	if s.ringIndex == 0 {
		s.ringIndex = genHashRingIndex(strconv.Itoa(int(s.machineId + s.nodeId)))
	}
	return s.ringIndex
}


//所有虚拟存储节点 key为在哈希环上的索引ringIndex
type  virtualNodeSlice []*virtualNode
var virtualNodes virtualNodeSlice

func (s virtualNodeSlice)Len()int{
	return  len(s )
}
func (s virtualNodeSlice)Less(i, j int) bool{
	return s[i].ringIndex<s[j].ringIndex
}
func (s virtualNodeSlice)Swap(i, j int)  {
	  s[i]=s[j]
}
//获取哈希环上的点保存到的虚拟节点
func (s virtualNodeSlice)GetNodeByRingIndex(ringIndex uint32)  (*virtualNode,bool){
	if s.Len()==0{
		return nil, false
	}
	for  _,v:=range s{
		if ringIndex<v.ringIndex{
			return v,true
		}
	}
	//如果是最大的一个 那就返回 最小的节点
	return s[0],true
}
//往集群增加一台机器
func AddMachine(ip string) {
	id := genHashRingIndex(ip)
	machineObj := &machine{machineId: id, ip: ip}

	//每台机器对应150个虚拟节点
	var i uint32 = 0
	for ; i < nodeCountPerMachine; i++ {
		virtualNode := &virtualNode{machine: machineObj, nodeId: i,}
		virtualNode.getRingIndex()
		virtualNodes = append(virtualNodes, virtualNode)
	}
	//排序 把虚拟节点按从小到大排列
	sort.Sort(virtualNodes)
}

//通过key从缓存中获取数据
func GetValue(key string) (interface{}, error) {
	ringIndex := genHashRingIndex(key)

	//获取虚拟节点
	vNode, ok := virtualNodes.GetNodeByRingIndex(ringIndex)
	if !ok {
		return nil, errors.New("虚拟节点不存在")
	}
	return vNode.GetValue(key)
}

//把key做哈希运算并与哈希环取模获取在哈希环上的数值
func genHashRingIndex(key string) (ringIndex uint32) {
	return hashKey(key) % hashRingMax
}

//把字符串哈希为uint32
func hashKey(key string) uint32 {
	if len(key) < 64 {
		var scratch [64]byte
		copy(scratch[:], key)
		return crc32.ChecksumIEEE(scratch[:len(key)])
	}
	return crc32.ChecksumIEEE([]byte(key))
}


package user

import (
	"encoding/json"
	"errors"
)

type UserInfo struct{
	UserId string `json:"user_id"`
	Name  string  `json:"name"`
}

func (s *UserInfo)NewUser(userId ,name string )  {
	s.UserId=userId
	s.Name=name
}
func (s *UserInfo)DecodeJson(data string )error  {
	if err:=json.Unmarshal([]byte(data),s);err!=nil{
		return  errors.New("value is not userinfo")
	}
	return  nil
}

package main

import (
	"fmt"
	"errors"
	"geektime_lession/consistency_hash/user"
	"geektime_lession/consistency_hash/hashcache"

)


//通过userId从缓存中获取userinfo
func GetUserInfo(userId string) (*user.UserInfo, error) {
	obj, err := hashcache.GetValue(userId)
	if err != nil {
		return nil, err
	}
	data, ok := obj.(string )//这里只处理一种类型,因为主要是写一致性哈希算法,这里不关心
	if !ok {
		return nil, errors.New("value is not string")
	}
	userInfo:=&user.UserInfo{}
	if err:=userInfo.DecodeJson(data );err!=nil{
		return  nil, err
	}
	return userInfo, nil
}
func main() {
	hashcache.AddMachine("127.0.0.1")
	userId := "123"
	userInfo, err := GetUserInfo(userId)
	if err != nil {
		fmt.Println(err.Error())
		return
	}
	fmt.Println("userinfo=%v", userInfo)
}