负载均衡--golang实现一致性hash算法

栏目: 服务器 · 发布时间: 6年前

内容简介:有没有好奇过redis、memcache等是怎么实现集群负载均衡的呢?其实他们都是通过一致性hash算法实现节点调度的。讲一致性hash算法前,先简述一下求余hash算法:

有没有好奇过 redis 、memcache等是怎么实现集群负载均衡的呢?

其实他们都是通过一致性hash算法实现节点调度的。

讲一致性hash算法前,先简述一下求余hash算法:

hash(object)%N
  1. 一个缓存服务器宕机了,这样所有映射到这台服务器的对象都会失效,我们需要把属于该服务器中的缓存移除,这时候缓存服务器是 N-1 台,映射公式变成了 hash(object)%(N-1) ;
  2. 由于QPS升高,我们需要添加多一台服务器,这时候服务器是 N+1 台,映射公式变成了 hash(object)%(N+1) 。

1 和 2 的改变都会出现所有服务器需要进行数据迁移。

一致性HASH算法

一致性HASH算法的出现有效的解决了上面普通求余算法在节点变动后面临全部缓存失效的问题:

type Consistent struct {
    numOfVirtualNode int
    hashSortedNodes  []uint32
    circle           map[uint32]string
    nodes            map[string]bool
}

简单地说,一致性哈希将整个哈希值空间组织成一个虚拟的圆环,如假设某空间哈希函数H的值空间是0-2^32-1(即哈希值是一个32位无符号整形),整个哈希空间如下:

负载均衡--golang实现一致性hash算法

image

下一步将各个服务器使用哈希算法计算出每台机器的位置,具体可以使用服务器的IP地址或者主机名作为关键字,并且是按照顺时针排列:

//这里我选择crc32,具体情况具体安排
func hashKey(host string) uint32 {
    scratch := []byte(host)
    return crc32.ChecksumIEEE(scratch)
}

这里我们假设三台节点memcache经计算后位置如下:

负载均衡--golang实现一致性hash算法

image

//add the node
c.Add("Memcache_server01")
c.Add("Memcache_server02")
c.Add("Memcache_server03")
func (c *Consistent) Add(node string) error {
    if _, ok := c.nodes[node]; ok {
        return errors.New("host already existed")
    }
    c.nodes[node] = true
    // add virtual node
    for i := 0; i < c.numOfVirtualNode; i++ {
        virtualKey := getVirtualKey(i, node)
        c.circle[virtualKey] = node
        c.hashSortedNodes = append(c.hashSortedNodes, virtualKey)
    }

    sort.Slice(c.hashSortedNodes, func(i, j int) bool {
        return c.hashSortedNodes[i] < c.hashSortedNodes[j]
    })
    return nil
}

接下来使用相同算法计算出数据的哈希值,并由此确定数据在此哈希环上的位置

假如我们有数据A、B、C和D,经过哈希计算后位置如下:

负载均衡--golang实现一致性hash算法

image

根据一致性哈希算法,数据A就被绑定到了server01上,D被绑定到了server02上,B、C在server03上,是按照顺时针找最近服务节点方法

这样得到的哈希环调度方法,有很高的容错性和可扩展性:

假设server03宕机

负载均衡--golang实现一致性hash算法

image

可以看到此时A、C、B不会受到影响,只是将B、C节点被重定位到Server 1。一般的,在一致性哈希算法中,如果一台服务器不可用,则受影响的数据仅仅是此服务器到其环空间中前一台服务器(即顺着逆时针方向行走遇到的第一台服务器)之间数据,其它不会受到影响。

考虑另外一种情况,如果我们在系统中增加一台服务器Memcached Server 04:

负载均衡--golang实现一致性hash算法

image

此时A、D、C不受影响,只有B需要重定位到新的Server 4。一般的,在一致性哈希算法中,如果增加一台服务器,则受影响的数据仅仅是新服务器到其环空间中前一台服务器(即顺着逆时针方向行走遇到的第一台服务器)之间数据,其它不会受到影响。

综上所述,一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据,具有较好的容错性和可扩展性。


以上所述就是小编给大家介绍的《负载均衡--golang实现一致性hash算法》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

从零开始做运营

从零开始做运营

张亮 / 中信出版社 / 2015-11-1 / 49.00元

运营是什么?怎样做运营?产品和运营是什么关系?我是否适合从事互联网运营?为什么我做的运营活动收效甚微? 在互联网大热的今天,互联网运营成为一个越来越重要的岗位,事关网站、产品的发展与存亡。很多年轻人带着对互联网的热情投身到这个行业,却发现自己对这个行业所知甚少,对互联网运营更加陌生,甚至有一些有志于从事互联网运营的人,因为对运营缺乏了解而难以确定自己的职业发展方向。本书的出发点就在于此,它将......一起来看看 《从零开始做运营》 这本书的介绍吧!

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具