解读两个一致性哈希算法
最重要的一点忘了写了:一致性哈希算法为啥能在节点变更的时候只有少量key迁移是因为sortkeys列表其实就是一个哈希环，客户端的哈希值和存量的节点哈希值在有序的sortkeys列表中的相对位置没有变，变的是下线节点前面的哈希到再前面一个之间的值所以变更率为:1-n/m
open-falcon中transfer会为judge和graph生成两个一致性哈希环
func initNodeRings() {
cfg := g.Config()
JudgeNodeRing = rings.NewConsistentHashNodesRing(int32(cfg.Judge.Replicas), cutils.KeysOfMap(cfg.Judge.Cluster))
GraphNodeRing = rings.NewConsistentHashNodesRing(int32(cfg.Graph.Replicas), cutils.KeysOfMap(cfg.Graph.Cluster))
}
哈希环的目的是为了给每个上报上来的counter:endpoint+metric+tag 算一致性哈希打到不同后端judge 和graph实例中.返回来查找时也这样干.典型的分布式缓存思想，这是falcon承受高并发的基础。一致性哈希普遍存在 lvs nginx 等lb应用场景中。Nginx的负载均衡 - 一致性哈希 (Consistent Hash)
哈希Hash，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。
不定长输入-->哈希函数-->定长的散列值
1.哈希算法的本质是对原数据的有损压缩
2.哈希运算包括 加法Hash、 位运算Hash、乘法Hash、除法Hash、查表Hash、混合Hash
3.散列值的固定长度是将输入分成固定长度位,依次进行hash运算,然后用不通方法迭代.位不足补全
4.哈希表的查找: 集合中拿出一个元素作对比,不一致再缩小范围查找,而哈希的查找是根据key值直接计算出这个元素在集合中的位置,近乎O(1)时间复杂度
5.哈希的抗碰撞能力:对于任意两个不同的数据块，其hash值相同的可能性极小:对于一个给定的数据块，找到和它hash值相同的数据块极为困难。
6.抗篡改能力：对于一个数据块，哪怕只改动其一个比特位，其hash值的改动也会非常大。
下面来看下一致性哈希算法
当有节点变更(增加或减少时)只有少量key 需要reblance到新的节点。
良好的一致性哈希算法应该满足:
平衡性:是指哈希的结果尽量均分到所有节点中
单调性:
分散性:由不同终端哈希的结果不一致,好的一致性哈希算法应避免这个
负载:不同的终端可能将相同的内容映射到不同的节点
1.一致性哈希算法需要的数据结构为 一个map 一个排序后的哈希key列表
2.生成哈希环的过程为: 为每个节点通过散列算法(md5 crc32)生成 key,更新map,添加key列表
3.查找过程:根据要存储的 字符串算出key2 然后通过二分查找法找到比key2大一点的那个key1的索引,根据key1去map中拿到对应的节点
4.引入虚拟节点是为了解决数据倾斜的问题:一致性哈希算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜问题
5.虚拟节点做法就是生成多个(一般30+)个hashkey 对应同一个节点:这就好比你去淘宝搜一样商品,看了一家店后又看到卖同样同样东西的另一家店,卖家给你提供了个店铺的列表跟你说这几家店铺都是我的。殊途同归的感觉
面具体看一致性哈希代码 源码-->
falcon中用的哈希环源码
https://github.com/toolkits/consistent
1.先看下数据结构 :记住这个map 和 sortkeys,因为这两个是核心
type HashKey uint32
type HashKeyOrder []HashKey
type HashRing struct {
ring map[HashKey]string //哈希环中的map
sortedKeys []HashKey //哈希key列表
nodes []string //节点列表
weights map[string]int
}
再看下falcon中的 是不是发现差不多
// Consistent holds the information about the members of the consistent hash circle.
type Consistent struct {
circle map[uint32]string
members map[string]bool
sortedHashes uints
NumberOfReplicas int
count int64
scratch [64]byte
sync.RWMutex
}2.再来看下生成哈希环的过程：
首先初始化下结构体,然后调用一个生成环的函数
func New(nodes []string) *HashRing {
hashRing := &HashRing{
ring: make(map[HashKey]string),
sortedKeys: make([]HashKey, 0),
nodes: nodes,
weights: make(map[string]int),
}
//生成哈希环
hashRing.generateCircle()
return hashRing
}看下这里的逻辑: 1.循环所有虚拟节点,根据node生成 hashkey 分别塞入map 和sortkeys中
func (h *HashRing) generateCircle() {
totalWeight := 0
//这段关于权重的可以不看
for _, node := range h.nodes {
if weight, ok := h.weights[node]; ok {
totalWeight += weight
} else {
totalWeight += 1
h.weights[node] = 1
}
}
for _, node := range h.nodes {
weight := h.weights[node]
// 三个节点且权重都是1时 factor=40 factor是为了增加虚拟节点
factor := math.Floor(float64(40*len(h.nodes)*weight) / float64(totalWeight))
for j := 0; j < int(factor); j++ {
//nodekey : 'node01-00' 'node01-01' 'node01-02'
nodeKey := fmt.Sprintf("%s-%d", node, j)
//bKey : [236 120 185 49 156 84 249 99 169 176 131 185 148 230 91 141]
bKey := hashDigest(nodeKey)
for i := 0; i < 3; i++ {
//key:3261919718
//key:2087224356
//key:2167064686
key := hashVal(bKey[i*4 : i*4+4])
fmt.Printf("Akey:%v\n",key)
//把h.ring这个map 塞了3*factor=120 个 value为这个node的key
h.ring[key] = node
//列表添加操作
h.sortedKeys = append(h.sortedKeys, key)
}
}
}
//h.sortedKeys ring.keys() 就是[31575610 64842500 65702829 80981415 ...]
sort.Sort(HashKeyOrder(h.sortedKeys))
}看下这里的hashDigest：就是生成MD5 []byte
func hashDigest(key string) [md5.Size]byte {
return md5.Sum([]byte(key))
}falcon用的是crc32.ChecksumIEEE
func (c *Consistent) 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))
}看下这里的hashval：将生成的md5 byte每四位进行位移+或操作作为hashkey
func hashVal(bKey []byte) HashKey {
//位移加或操作
return ((HashKey(bKey[3]) << 24) |
(HashKey(bKey[2]) << 16) |
(HashKey(bKey[1]) << 8) |
(HashKey(bKey[0])))
}看到这里我们心里就有谱了:为每个节点算出3*40=120个uint32的数字作为key塞入map和hashkey列表中 最后将hashkey列表排序，为最后的二分查找做准备
3.最后我们看下查找的过程：
查找的过程就是先根据 key生成哈希key 通过sortkeys列表二分查找找到这个key在列表中的索引,根据索引拿到hashkey 再去map get出对应的节点
func (h *HashRing) GetNode(stringKey string) (node string, ok bool) {
//首先要获取这个key 在sortedKeys列表中的索引
pos, ok := h.GetNodePos(stringKey)
if !ok {
return "", false
}
return h.ring[h.sortedKeys[pos]], true
}
func (h *HashRing) GetNodePos(stringKey string) (pos int, ok bool) {
if len(h.ring) == 0 {
return 0, false
}
// key 为hashkey 2880865363
key := h.GenKey(stringKey)
nodes := h.sortedKeys
/*
这里获取hashkey在h.sortedKeys中的索引采用的是二分查找法
sort.Search 的第二个参数很有意思,是一个返回bool的方法
*/
pos = sort.Search(len(nodes), func(i int) bool { return nodes[i] > key })
if pos == len(nodes) {
// Wrap the search, should return first node
return 0, true
} else {
return pos, true
}
}让我们来看下查找这里：使用的
/*
这里获取hashkey在h.sortedKeys中的索引采用的是二分查找法
sort.Search 的第二个参数很有意思,是一个返回bool的方法
*/
pos = sort.Search(len(nodes), func(i int) bool { return nodes[i] > key })
让我们来看下源码中Search的说明：连我这么渣的英文都看出来了这是二分查找法：
过程就是根据算出的 key1 和这个有序列表做二分查找找到大于key1的最小的key
>>1就是除以2的一次方 就是减半了
// Search uses binary search to find and return the smallest index i
// in [0, n) at which f(i) is true, assuming that on the range [0, n),
// f(i) == true implies f(i+1) == true. That is, Search requires that
// f is false for some (possibly empty) prefix of the input range [0, n)
// and then true for the (possibly empty) remainder; Search returns
// the first true index. If there is no such index, Search returns n.
// (Note that the "not found" return value is not -1 as in, for instance,
// strings.Index.)
// Search calls f(i) only for i in the range [0, n).
func Search(n int, f func(int) bool) int {
// Define f(-1) == false and f(n) == true.
// Invariant: f(i-1) == false, f(j) == true.
i, j := 0, n
for i < j {
h := int(uint(i+j) >> 1) // avoid overflow when computing h
// i ≤ h < j
if !f(h) {
i = h + 1 // preserves f(i-1) == false
} else {
j = h // preserves f(j) == true
}
}
// i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i.
return i
}
来撸个python的二分查找
def bin_search(data_set,val):
#low 和high代表下标 最小下标，最大下标
low=0
high=len(data_set)-1
while low <=high:# 只有当low小于High的时候证明中间有数
mid=(low+high)//2
print "low:%d,mid:%d,high:%d" % (low,mid, high)
if data_set[mid]==val:
return mid #返回他的下标
elif data_set[mid]>val:
high=mid-1
else:
low=mid+1
return # return null证明没有找到
data_set = list(range(100))
print(bin_search(data_set, 34))下面我们来测试下这个一致性哈希算法 在节点变化时key的迁移情况
func RingInit(server_arr []string) *hashring.HashRing{
return hashring.New(server_arr)
}
func PengzhuangCeshi(){
servers1 :=[]string{
"192.168.0.241:11212",
"192.168.0.242:11212",
"192.168.0.243:11212",
"192.168.0.244:11212",
"192.168.0.245:11212",
}
servers2 :=[]string{
"192.168.0.241:11212",
"192.168.0.242:11212",
"192.168.0.243:11212",
"192.168.0.244:11212",
}
r1 := RingInit(servers1)
r2 := RingInit(servers2)
test_num :=10000000
client_ip := "10.10.10.10"
migr_num :=0
for i:=0;i<test_num;i++{
key :=fmt.Sprintf("%s_%v",client_ip,i)
choose_server1,_ := r1.GetNode(key)
choose_server2,_ := r2.GetNode(key)
if choose_server1 !=choose_server2{
migr_num+=1
}
}
fmt.Println("migr_num",migr_num)
fmt.Printf("migr_rate %.3f", float32(migr_num)/float32(test_num))
}
func main(){
PengzhuangCeshi()
//Test()
}
test_num :=10000000
4/5变化
migr_num 1839416
migr_rate 0.184
5/2变化
migr_num 5737265
migr_rate 0.574
3/2变化
migr_num 3072919
migr_rate 0.307
4/3变化
migr_num 2491462
migr_rate 0.249
如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响。
我们推测迁移率为 rate = 1- m/n if m<n ???
最后废话少说 撸个python的一致性哈希环
#coding:utf-8
import md5
class ConsistentHashRing(object):
def __init__(self,nodes,replicas=3):
self.replicas = replicas
self.ring = {}
self.sort_keys = []
if nodes:
for node in nodes:
self.add_nodes(node)
def add_nodes(self,node):
for i in xrange(self.replicas):
key='%s_%d'%(node,i)
hashkey = self.gen_key(key)
#print hashkey
self.ring[hashkey] = node
self.sort_keys.append(hashkey)
self.sort_keys.sort()
def gen_key(self,key):
m = md5.new()
m.update(key)
return long(m.hexdigest(), 16)
def get_node(self,data_key):
return self.get_node_pos(data_key)[0]
def get_node_pos(self,data_key):
key = self.gen_key(data_key)
nodes = self.sort_keys
for i in xrange(0,len(nodes)):
node = nodes[i]
if key <= node:
return self.ring[node],i
return self.ring[nodes[0]],0
if __name__ == '__main__':
nodes=["node-1","node-2","node-3"]
Ring = ConsistentHashRing(nodes)
for i in xrange(10000):
print Ring.get_node("key1-%d"%i)
上一篇： win10以太网未启用dhcp怎么办?
下一篇： C#中利用MD5实现密码加密实例