最重要的一点忘了写了:一致性哈希算法为啥能在节点变更的时候只有少量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 对应同一个节点:这就好比你去淘宝搜一样商品,看了一家店后又看到卖同样同样东西的另一家店,卖家给你提供了个店铺的列表跟你说这几家店铺都是我的。殊途同归的感觉

面具体看一致性哈希代码 源码-->

serialx/hashring?github.com

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)