专栏首页老男孩成长之路微服务细剖:一致性hash的原理和实现,面试划重点

微服务细剖:一致性hash的原理和实现,面试划重点

以存储为例,在整个微服务系统中,我们的存储不可能说只是一个单节点。

  • 一是为了提高稳定,单节点宕机情况下,整个存储就面临服务不可用;
  • 二是数据容错,同样单节点数据物理损毁,而多节点情况下,节点有备份,除非互为备份的节点同时损毁。

那么问题来了,多节点情况下,数据应该写入哪个节点呢?

hash

所以本质来讲:我们需要一个可以将输入值“压缩”并转成更小的值,这个值通常状况下是唯一、格式极其紧凑的,比如uint64

  • 幂等:每次用同一个值去计算 hash 必须保证都能得到同一个值

这个就是 hash 算法完成的。

但是采取普通的 hash 算法进行路由,如:key % N 。有一个节点由于异常退出了集群或者是心跳异常,这时再进行 hash route ,会造成大量的数据重新 分发到不同的节点 。节点在接受新的请求时候,需要重新处理获取数据的逻辑:如果是在缓存中,容易引起 缓存雪崩

此时就需要引入 consistent hash 算法了。

consistent hash

我们来看看 consistent hash 是怎么解决这些问题的:

rehash

先解决大量 rehash 的问题:

如上图,当加入一个新的节点时,影响的key只有 key31,新加入(剔除)节点后,只会影响该节点附近的数据。其他节点的数据不会收到影响,从而解决了节点变化的问题。

这个正是:单调性。这也是 normal hash 算法无法满足分布式场景的原因。

数据倾斜

其实上图可以看出:目前多数的key都集中在 node 1 上。如果当 node 数量比较少的情况下,可以回引发多数 key 集中在某个 node 上,监控时发现的问题就是:节点之间负载不均。

为了解决这个问题,consistent hash 引入了 virtual node 的概念。

既然是负载不均,我们就人为地构造一个均衡的场景出来,但是实际 node 只有这么多。所以就使用 virtual node 划分区域,而实际服务的节点依然是之前的 node。

具体实现

先来看看 Get()

Get

先说说实现的原理:

  1. 计算 key 的hash
  2. 找到第一个匹配的 virtual node 的 index,并取到对应的 h.keys[index] :virtual node hash 值
  3. 对应到这个 ring 中去寻找一个与之匹配的 actual node

其实我们可以看到 ring 中获取到的是一个 []node 。这是因为在计算 virtual node hash ,可能会发生hash冲突,不同的 virtual node hash 对应到一个实际node。

这也说明:nodevirtual node 是一对多的关系。而里面的 ring 就是下面这个设计:

这个其实也就表明了一致性hash的分配策略:

  1. virtual node 作为值域划分。key 去获取 node ,从划分依据上是以 virtual node 作为边界
  2. virtual node 通过 hash ,在对应关系上保证了不同的 node 分配的key是大致均匀的。也就是 打散绑定
  3. 加入一个新的 node,会对应分配多个 virtual node。新节点可以负载多个原有节点的压力,从全局看,较容易实现扩容时的负载均衡。

Add Node

看完 Get 其实大致就知道整个一致性hash的设计:

type ConsistentHash struct {
  hashFunc Func                         // hash 函数
  replicas int                          // 虚拟节点放大因子
  keys     []uint64                 // 存储虚拟节点hash
  ring     map[uint64][]interface{}                 // 虚拟节点与实际node的对应关系
  nodes    map[string]lang.PlaceholderType  // 实际节点存储【便于快速查找,所以使用map】
  lock     sync.RWMutex
}

好了这样,基本的一个一致性hash就实现完备了。

具体代码:https://github.com/tal-tech/go-zero/blob/master/core/hash/consistenthash.go

使用场景

开头其实就说了,一致性hash可以广泛使用在分布式系统中:

  1. 分布式缓存。可以在 redis cluster 这种存储系统上构建一个 cache proxy,自由控制路由。而这个路由规则就可以使用一致性hash算法
  2. 服务发现
  3. 分布式调度任务

以上这些分布式系统中,都可以在负载均衡模块中使用。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • ​业务开发中你用到了哪些算法(续)?

    上次我们一起聊了聊普通 hash 算法在实际中的应用,但是按照一猿小讲的风格,绝不能止于应用,为了能让面试官再喝一壶,还是要稍微升华一下,话不多说,本期的分享正...

    一猿小讲
  • 【小妙招】如何借助Proxy代理,提升架构扩展性

    但有些业务功能比较特殊,比如发起一次http请求创建一笔订单,前提要求用户先登录,为了解决这个问题,http协议header中引入了Cookie,存储上下文信息...

    用户7676729
  • 一文搞懂一致性hash的原理和实现

    在 go-zero 的分布式缓存系统分享里,Kevin 重点讲到过一致性hash的原理和分布式缓存中的实践。本文来详细讲讲一致性hash的原理和在 go-zer...

    不会飞的小鸟
  • 成为Java顶尖程序员,先过了下面问

    首先,声明下,以下知识点并非阿里的面试题。这里,笔者结合自己过往的面试经验,整理了一些核心的知识清单,帮助读者更好地回顾与复习 Java 服务端核心技术。本文会...

    搜云库
  • 一文归纳总结分布式架构的那些事!

    进入十一月,最火热的话题与期待的日子自然是双十一狂欢购物节了,作为程序员的你除了要清空自己的购物车之外,最关心的是不是双十一架构技术是如何承受亿级用户流量的冲击...

    Java架构
  • 从Java程序员到架构师,从工程师到技术专家,迷茫之路

    怎样学习才能从一名Java初级程序员成长为一名合格的架构师,或者说一名合格的架构师应该有怎样的技术知识体系,这是不仅一个刚刚踏入职场的初级程序员也是工作三五年之...

    慕容千语
  • 【面试题】2018年最全Java面试通关秘籍汇总集!

    前几天在交流群里有些小伙伴问面试相关的试题,当时给出了一些问题,苦于打字太累就没写下去了,但觉得这是一个很不负责任的表现,于是下来整理了一下近几年的私藏,特分享...

    Java后端技术
  • 面试官:你对Redis缓存了解吗?面对这11道面试题是否有很多问号?

    面试官:你对Redis缓存了解吗?面对这11道面试题是否有很多问号? ...

    Java架构师必看
  • 面试官:你对Redis缓存了解吗?面对这11道面试题你是否有很多问号?

    只要问到缓存,上来第一个问题,肯定是先问问你项目哪里用了缓存?为啥要用?不用行不行?如果用了以后可能会有什么不良的后果?

    程序员追风
  • Linux后台开发必看(给进军bat的你)

    我是程序员小贱
  • WCF技术剖析(卷1)之前言

    第一次邂逅WCF是在微软举办的一场关于Windows Vista技术推广培训上,时间大概是2005年10月份,当时对WCF可谓是一见钟情。如果读者也像我一样,之...

    蒋金楠
  • 这5个常问的Redis面试题你答得出来吗?(详细剖析)

    在前几年,redis 如果要搞几个节点,每个节点存储一部分的数据,得借助一些中间件来实现,比如说有codis,或者 twemproxy,都有。有一些 redis...

    用户2781897
  • iOS微信内存监控

    本文介绍如何实现离线化的内存监控工具,用于 App 上线后发现内存问题。

    WeTest质量开放平台团队
  • iOS微信内存监控

    目前iOS主流的内存监控工具是Instruments的Allocations,但只能用于开发阶段。本文介绍如何实现离线化的内存监控工具,用于App上线后发现内存...

    WeTest质量开放平台团队
  • Linux后台开发必看!

    一 自我介绍二 面试情况三 相关知识点汇总1 c/c++相关2 计算机网络3 数据结构相关4 数据库相关5 操作系统6 Linux基础知识及应用编程(后台必备!...

    公众号guangcity
  • Java面试通关要点 汇总集

    首先,声明下,以下知识点并非阿里的面试题。这里,笔者结合自己过往的面试经验,整理了一些核心的知识清单,帮助读者更好地回顾与复习 Java 服务端核心技术。本文会...

    Java技术江湖
  • 三万倍提升,起飞的PostgreSQL主从优化实践

    ? 导语 | 某些业务场景安全性要求很高,核心空间的数据不能随意修改,本文介绍腾讯云数据库PostgreSQL在大量drop业务场景下主从复制产生的性能问题,...

    腾小云
  • FPGA Xilinx Zynq 系列(二十三)Zynq 片上系统的开发

    今天给大侠带来FPGA Xilinx Zynq 系列第二十三篇,开启十一章,讲述Zynq 片上系统的开发等相关内容,本篇内容目录简介如下:

    FPGA技术江湖
  • 后端架构师技术图谱

    转自: GitHub/architect-awesome , 大体结构如下(更新时间: 2018-06-22)

    用户1216491

扫码关注云+社区

领取腾讯云代金券