架构师训练营 week05 作业（hash 算法）

// 哈希函数签名
type Hash func(data []byte) uint32
// 一致性哈希实体
type Map struct {
	hash     Hash           // 哈希函数
	replicas int            // 每个真实节点对应的虚拟节点个数
	circle   []int          // 哈希环
	hashMap  map[int]string // 存储虚拟节点与真实节点的映射
}
// 创建实例
func New(replicas int, hashFunc Hash) *Map {
	m := &Map{
		hash:     hashFunc,
		replicas: replicas,
		hashMap: make(map[int]string),
	}
	if m.hash == nil {
		m.hash = crc32.ChecksumIEEE
	}
	return m
}


// 添加真实节点
func (m *Map) Add(peers ...string) {
	for _, peer := range peers {
		for i := 0; i < m.replicas; i++ {
			// 根据节点的名称+编号计算hash值
			hashVal := int(m.hash([]byte(strconv.Itoa(i) + peer)))
			//log.Printf("peer:[%s-%d], hash:[%d]\n", peer, i, hashVal)
			m.circle = append(m.circle, hashVal)
			m.hashMap[hashVal] = peer
		}
	}
	// 排序是为了接下来方便查询
	sort.Ints(m.circle)
	//log.Printf("circle:\n %v\n",m.circle)
}


// 根据请求的key选择对应的真实节点
// 返回真实节点的名称
func (m *Map) Get(key string) string {
	if len(m.circle) == 0 {
		return ""
	}
	// 首先计算key对应的hash值
	hashVal := int(m.hash([]byte(key)))
	// 二分查找
	index := sort.Search(len(m.circle), func(i int) bool {
		return m.circle[i] >= hashVal
	})
	return m.hashMap[m.circle[index%len(m.circle)]]
}


func TestConsistentHash(t *testing.T) {
	// 创建一个一致性哈希实例，并自定义hash函数
	chash := New(3, func(data []byte) uint32 {
		i, _ := strconv.Atoi(string(data))
		return uint32(i)
	})
	// 添加真实节点，为了方便说明，这里的节点名称只用数字进行表示
	chash.Add("4", "6", "2")

	testCases := map[string]string{
		"15": "6",
		"11": "2",
		"23": "4",
		"27": "2",
	}
	for k, v := range testCases {
		if chash.Get(k) != v {
			t.Errorf("Asking for %s, should have yielded %s", k, v)
		}
	}

	// 新增一个节点"8"，对应增加3个虚拟节点，分别为8,18,28
	chash.Add("8")

	// 此时如果查询的key为27，将会对应到虚拟节点28，也就是映射到真实节点8
	testCases["27"] = "8"

	for k, v := range testCases {
		if chash.Get(k) != v {
			t.Errorf("Asking for %s, should have yielded %s", k, v)
		}
	}
}


var keysPtr = flag.Int("keys", 10000, "key number")
var nodesPtr = flag.Int("nodes", 3, "node number of old cluster")
var newNodesPtr = flag.Int("new-nodes", 4, "node number of new cluster")

// 测试一致性哈希的数据迁移率
func TestMigrateRatio(t *testing.T) {
	flag.Parse()
	var keys = *keysPtr
	var nodes = *nodesPtr
	var newNodes = *newNodesPtr
	fmt.Printf("keys:%d, nodes:%d, newNodes:%d\n", keys, nodes, newNodes)

	c := New(3, nil)
	for i := 0; i < nodes; i++ {
		c.Add(strconv.Itoa(i))
	}

	newC := New(3, nil)
	for i := 0; i < newNodes; i++ {
		newC.Add(strconv.Itoa(i))
	}

	migrate := 0
	for i := 0; i < keys; i++ {
		server := c.Get(strconv.Itoa(i))
		newServer:= newC.Get(strconv.Itoa(i))
		if server != newServer {
			migrate++
		}
	}
	migrateRatio := float64(migrate) / float64(keys)
	fmt.Printf("%f%%\n", migrateRatio*100)
}


$ go test -v -run=TestMigrateRatio -keys 1000000 -nodes 3 -new-nodes 4
=== RUN   TestMigrateRatio
keys:1000000, nodes:3, newNodes:4
22.984500%
--- PASS: TestMigrateRatio (0.50s)