第五周作业

 关注

发布于: 2020 年 09 月 13 日

实现一致性hash算法
设计：主要就是如何查找数据对应的虚拟节点，再对过虚拟节点找到host节点。这里就是这两重查找。
方法：
第二重查找比较好实现，现在一个map，key是虚拟节点的hash值，value是host的指针。
第一重查找，使用一个二叉查找树，把虚拟节点的hash值都存进去，然后找到比数据的key大的第一个节点即可。
具体实现如下：
这里使用的是AVL树。
修改一下AVL树的search方法，返回比key大的第一个节点：
func (n *AVLNode) search(key uint32) *AVLNode {
	if n == nil {
		return nil
	}
	if key < n.key {
		if n.left == nil {
			return n
		}
		if key > n.left.key && n.left.right == nil {
			return n
		}
		return n.left.search(key)
	} else if key > n.key {
		return n.right.search(key)
	} else {
		return n
	}
}
这里还不能解决大于最后一个节点key的问题，大于最后一个节点key会找不到node，这时直接用最小的节点。不在AVL树中实现，在一致性hash里实现：
func (ch ConsistentHash) FindHost(key string) *Host {
	hashCode := consistentHash(key)
	treeNode := ch.Tree.Search(hashCode)
	if treeNode == nil {
		return ch.NodeToHost[ch.minNode.HashCode]
	}
	return ch.NodeToHost[treeNode.GetKey()]
}
另一个问题是hash码的生成，这里比较粗暴，直接使用了md5
func consistentHash(key string) uint32 {
	hashCode := md5.Sum([]byte(key))
	return binary.BigEndian.Uint32(hashCode[:])
}
测试了下数据分布的不均衡性。
结果不能直视，偏差很严重。
    Test: hashing_test.go:29: [32425 53348 63359 71598 76364 331352 88699 91193 95433 96229]
    Test: hashing_test.go:30: 6.3214788394e+10
    Test: hashing_test.go:29: [33333 50932 59221 74560 77893 84034 90337 89785 95558 344347]
    Test: hashing_test.go:30: 6.9828818126e+10
    Test: hashing_test.go:29: [33381 52406 64908 71716 77347 329458 87441 87977 94054 101312]
    Test: hashing_test.go:30: 6.223820256e+10
    Test: hashing_test.go:29: [280066 52752 60191 70098 83642 81866 85742 92984 92846 99813]
    Test: hashing_test.go:30: 3.803517957e+10
    Test: hashing_test.go:29: [34555 51598 62330 68853 82560 80123 85542 93593 89595 351251]
    Test: hashing_test.go:30: 7.3199627306e+10
    Test: hashing_test.go:29: [31832 51041 63647 67781 76119 336340 90271 92518 94834 95617]
    Test: hashing_test.go:30: 6.6026894246e+10
    Test: hashing_test.go:29: [32420 300780 60233 67778 77484 80461 86843 96705 99670 97626]
    Test: hashing_test.go:30: 4.85777876e+10
    Test: hashing_test.go:29: [32137 54039 309663 72570 77930 82691 90708 90210 92920 97132]
    Test: hashing_test.go:30: 5.2456002328e+10
    Test: hashing_test.go:29: [32815 51137 64610 317851 76246 81243 84009 93603 97592 100894]
    Test: hashing_test.go:30: 5.683223625e+10
    Test: hashing_test.go:29: [33447 49671 308874 70767 77257 84072 88045 93998 96335 97534]
    Test: hashing_test.go:30: 5.2414630858e+10
﻿

发布于: 2020 年 09 月 13 日阅读数: 19

原文链接:【http://xie.infoq.cn/article/ec128ea55e5c244722ab757db】。文章转载请联系作者。

Vincent

 关注

还未添加个人签名 2018.07.06 加入

上个课还要写作业，哎，挺好，挺好。

发布

暂无评论