专栏首页老男孩成长之路一个速度快,内存占用小的一致性哈希算法

一个速度快,内存占用小的一致性哈希算法

一致性哈希最早由 MIT的 Karger 提出,在发表于1997年的论文 Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web, Karger et al 和合作者们提出了一致性哈希的概念(consistent hash),用来解决分布式Cache的问题。这篇论文中提出在动态变化的Cache环境中,哈希算法应该满足的4个适应条件::Balance(均衡)、Monotonicity(单调性)、Spread(分散性)、Load(负载)。

在分布式缓存系统中使用一致性哈希算法时,某个节点的添加和移除不会重新分配全部的缓存,而只会影响小部分的缓存系统,如果均衡性做的好的话,当添加一个节点时,会均匀地从其它节点移一部分缓存到新的节点上;当删除一个节点的时候,这个节点上的缓存会均匀地分配到其它活着的节点上。

一致性哈希缓存还被扩展到分布式存储系统上。数据被分成一组Shard,每个Shard由一个节点管理,当需要扩容时,我们可以添加新的节点,然后将其它Shard的一部分数据移动到这个节点上。比如我们有10个Shard的分布式存储系统,当前存储了120个数据,每个Shard存储了12个数据。当扩容成12个Shard时,我们从每个Shard上拿走2个数据,存入到新的两个Shard上,这样每个Shard都存储了10个数据,而整个过程中我们只移动了20/120=1/6的数据。

Karger 一致性哈希算法将每个节点(bucket)关联一个圆环上的一些随机点,对于一个键值,将其映射到圆环中的一个点上,然后按照顺时针方向找到第一个关联bucket的点,将值放入到这个bucke中。因此你需要存储一组bucket和它们的关联点,当bucket以及每个bucket的关联点很多的时候,你就需要多一点的内存来记录它。这个你经常在网上看到的介绍一致性哈希的算法(有些文章将节点均匀地分布在环上,比如节点1节点2节点3节点4节点1节点2节点3节点4……, 这是不对的,在这种情况下节点2挂掉后它上面的缓存全部转移给节点3了)。

其它的一致性算法还有Rendezvous hashing, 计算一个key应该放入到哪个bucket时,它使用哈希函数h(key,bucket)计算每个候选bucket的值,然后返回值最大的bucket。buckets比较多的时候耗时也较长,有人也提出了一些改进的方法,比如将bucket组织成tree的结构,但是在reblance的时候花费时间又长了。

Java程序员熟悉的Memcached的客户端Spymemcached、Xmemcached以及Folsom都提供了Ketama算法。其实Ketama算法最早于2007年用c 实现(libketama),很多其它语言也实现了相同的算法,它是基于Karger 一致性哈希算法实现:

  • 建立一组服务器的列表 (如: 1.2.3.4:11211, 5.6.7.8:11211, 9.8.7.6:11211)
  • 为每个服务器节点计算一二百个哈希值
  • 从概念上讲,这些数值被放入一个环上(continuum). (想象一个刻度为 0 到 2^32的时钟,这个时钟上就会散落着一些数字)
  • 每一个数字关联一个服务器,所以服务器出现在这个环上的一些点上,它们是哈希分布的
  • 为了找个一个Key应该放入哪个服务器,先哈希你的key,得到一个无符号整数, 沿着圆环找到和它相邻的最大的数,这个数对应的服务器就是被选择的服务器
  • 对于靠近 2^32的 key, 因为没有超过它的数字点,按照圆环的原理,选择圆环中的第一个服务器。

以上两种算法可以处理节点增加和移除的情况。对于分布式存储系统,当一个节点失效时,我们并不期望它被移除,而是使用备份节点替换它,或者将它恢复起来,因为我们不期望丢掉它上面的数据。对于这种情况(节点可以扩容,但是不会移除节点),Google的 John Lamping, Eric Veach提供一个高效的几乎不占用持久内存的算法:Jump Consistent Hash。

Jump Consistent Hash算法的特点是:

  • 代码简单:寥寥几行代码
  • 不需要额外的内存映射:可是实时计算
  • 快速
  • 均匀:数据非常均匀地分布在各个节点

具体的算法可以查看其论文。

C语言实现的Jump Consistent Hash如下:

int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets)
{
    int64_t b = -1, j = 0;
    while (j < num_buckets) {
        b = j;
        key = key * 2862933555777941757ULL + 1;
        j = (b + 1) * (double(1LL << 31)/double((key >> 33) + 1));
    }
    return b;
}

可以看出这个算法非常的简单,因此也很容易的用Go来实现:

func JumpHash(key uint64, buckets int) int {
 var b, j int64
 if buckets <= 0 {
  buckets = 1
 }
 for j < int64(buckets) {
  b = j
  key = key*2862933555777941757 + 1
  j = int64(float64(b+1) * (float64(int64(1)<<31) / float64((key>>33)+1)))
 }
 return int(b)
}

我们可以写段代码测试它,看看它的分布是否均匀,在新增加一个节点的时候,是否只移动了一部分的数据:

package main
import "fmt"
func main() {
 buckets := make(map[int]int, 10)
 count := 10
 for i := uint64(0); i < 120000; i++ {
  b := JumpHash(i, count)
  buckets[b] = buckets[b] + 1
 }
 fmt.Printf("buckets: %v\n", buckets)
 //add two buckets
 count = 12
 for i := uint64(0); i < 120000; i++ {
  oldBucket := JumpHash(i, count-2)
  newBucket := JumpHash(i, count)
  //如果对象需要移动到新的bucket中,则首先从原来的bucket删除,再移动
  if oldBucket != newBucket {
   buckets[oldBucket] = buckets[oldBucket] - 1
   buckets[newBucket] = buckets[newBucket] + 1
  }
 }
 fmt.Printf("buckets after add two servers: %v\n", buckets)
}

因为Jump consistent hash算法不使用节点挂掉,如果你真的有这种需求,比如你要做一个缓存系统,你可以考虑使用ketama算法,或者对Jump consistent hash算法改造一下:节点挂掉时我们不移除节点,只是标记这个节点不可用。当选择节点时,如果选择的节点不可用,则再一次Hash,尝试选择另外一个节点,比如下面的算法将key加1再进行选择。

func JumpHash(key uint64, buckets int, checkAlive func(int) bool) int {
 var b, j int64 = -1, 0
 if buckets <= 0 {
  buckets = 1
 }
 for j < int64(buckets) {
  b = j
  key = key*2862933555777941757 + 1
  j = int64(float64(b+1) * (float64(int64(1)<<31) / float64((key>>33)+1)))
 }
 if checkAlive != nil && !checkAlive(int(b)) {
  return JumpHash(key+1, buckets, checkAlive) //最好设置深度,避免key+1一直返回当掉的服务器
 }
 return int(b)
}

上面的算法有一点问题,就是没有设定重试的测试,如果所有的节点都挂掉,则会进入死循环,所以最好设置一下重试次数(递归次数),超过n次还没有选择到则返回失败。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 分布式数据缓存中的一致性哈希算法

    一致性哈希算法在分布式缓存领域的 MemCached,负载均衡领域的 Nginx 以及各类 RPC 框架中都有广泛的应用,它主要是为了解决传统哈希函数添加哈希表...

    程序员历小冰
  • 分布式数据缓存中的一致性哈希算法

    一致性哈希算法在分布式缓存领域的 MemCached,负载均衡领域的 Nginx 以及各类 RPC 框架中都有广泛的应用,它主要是为了解决传统哈希函数添加哈希表...

    程序员历小冰
  • 分布式数据缓存中的一致性哈希算法

    一致性哈希算法在分布式缓存领域的 MemCached,负载均衡领域的 Nginx 以及各类 RPC 框架中都有广泛的应用,它主要是为了解决传统哈希函数添加哈希表...

    Bug开发工程师
  • 【翻译/介绍】jump consistent hash 零内存消耗,均匀,快速,简洁,来自Google的一致性哈希算法

    jump consistent hash是一种一致性哈希算法, 此算法零内存消耗,均匀分配,快速,并且只有5行代码。

    byronhe
  • 使用虚拟节点改进的一致性哈希算法

    1 作者:@lionets 分析缺点 连接:http://my.oschina.net/lionets/blog/288066 2 作者:@糖拌咸鱼 ...

    程序员小王
  • Java计算一个对象占用内存的大小

    在C/C++中计算某一个基本类型或者对象占用内存大小的方法很简单,只要调用库里面的sizeof()操作符即可,但是在Java的API里面并没有给我们提供类似的方...

    用户7886150
  • 哪种一致性哈希算法才是解决分布式缓存问题的王者?

    ? 导语 | 一致性哈希是由Karger等人于1997年提出的一种特殊的哈希算法,目的是解决分布式缓存的问题,现在在分布式系统中有着广泛的应用。本文将对ket...

    腾小云
  • 哈希革新Transformer:这篇ICLR高分论文让一块GPU处理64K长度序列

    大型的 Transformer 往往可以在许多任务上实现 sota,但训练这些模型的成本很高,尤其是在序列较长的时候。在 ICLR 的入选论文中,我们发现了一篇...

    机器之心
  • 基于sketch的网络测量方法介绍

    作者简介: 周政演,福州大学数计学院2016级计算机科学与技术(实验班)本科生,目前研究方向为网络测量,邮箱vancasola @gmail.com。

    SDNLAB
  • data_structure_and_algorithm -- 哈希算法(下)

    我们知道,负载均衡算法有很多,比如轮询、随机、加权轮询等。那如何才能实现一个会话粘滞(session sticky)的负载均衡算法呢?也就是说,我们需要在同一个...

    MachineLP
  • 聊聊jump consistent hash

    jump consistent hash是一致性哈希的一种实现,论文见A Fast, Minimal Memory, Consistent Hash Algor...

    code4it
  • Java、Rust、Go主流编程语言的哈希表比较

    哈希表(HashMap、字典)是日常编程当中所经常用到的一种数据结构,程序员经常接解到的大数据Hadoop技术栈、Redis缓存数据库等等最近热度很高的技术,其...

    beyondma
  • 哈希算法原来有这么多应用场景!

    这些定义和要求都比较理论,可能还是不好理解,我拿MD5这种哈希算法来具体说明一下。

    JavaEdge
  • Mysql InnoDB 为啥选择B+树索引 转

    Mysql数据库中的常见索引有多种方式,例如Hash索引,B-树索引,B+树索引,但是为啥mysql中默认是采用B+树索引索引呢?下面对这三种索引学习总结一下。...

    双面人
  • 系统如何设计才能更快地查询到数据?

    ? 导语 | 开通微信时,系统如何判断你输入的手机号没被注册?如何使用更少的存储空间、更快的速度解决这个问题?对于这个问题,腾讯微信支付数据开发工程师杭天梦带...

    腾小云
  • Hashmap源码解析

    做什么都怕进入狗咬尾巴的怪圈,上次看hashmap源码还是2012年,这次出去面试时被问到了hashmap的问题,整体思路还是记得的,巴拉巴拉一堆。回来再看一下...

    码农戏码
  • 向量将死,哈希是 AI 未来

    人工智能是建立在向量算法的基础上的,但最新的进展表明,对于某些 AI 应用程序而言,它们可以使用其他二进制来表示(例如神经哈希),以提供更小的内存占用和更快的反...

    AI科技评论
  • 使用Go构建区块链 第2部分:工作量证明

    在上一篇文章中,我们构建了一个非常简单的数据结构,这是区块链数据库的本质。我们可以通过它们之间的链状关系为它添加区块:每个区块都链接到前一个块。我们的区块链实现...

    银河1号
  • 第18期:索引设计(认识哈希表)

    MySQL 哈希索引又基于哈希表(散列表)来实现,所以了解什么是哈希表对 MySQL 哈希索引的理解至关重要。接下来,我们来一步一部介绍哈希表。

    爱可生开源社区

扫码关注云+社区

领取腾讯云代金券