漫画:什么是一致性哈希?

简介: 未来两年内,系统预估的总订单数量可达一亿条左右。按Mysql单表存储500万条记录来算,暂时不必分库,单库30个分表是比较合适的水平分表方案。

640.jpg640.jpg

640.jpgimage.gif

640.jpg

一年之前——

640.jpg

640.jpg

未来两年内,系统预估的总订单数量可达一亿条左右。

按Mysql单表存储500万条记录来算,暂时不必分库,单库30个分表是比较合适的水平分表方案。

于是小灰设计了这样的分表逻辑:

1. 订单表创建单库30个分表

1. 对用户ID和30进行取模,取模结果决定了记录存于第几个分表

1. 查询时需要以用户ID作为条件,根据取模结果确定查询哪一个分表

分表方式如下图(为了便于描述,简化为5个分表):

640.jpgimage.gif

过了两个月——

640.jpg

640.jpg

又过了半年多——

640.jpg

640.jpg

image.gif640.jpg

640.jpg

640.jpg

image.gif

640.jpg

image.gif

640.jpg


小灰的回忆告一段落——

640.jpgimage.gif

640.jpg

640.jpg640.jpg

image.gif640.jpg

640.jpg

1.首先,我们把全量的缓存空间当做一个环形存储结构。环形空间总共分成2^32个缓存区,在Redis中则是把缓存key分配到16384个slot。

640.jpg

2.每一个缓存key都可以通过Hash算法转化为一个32位的二进制数,也就对应着环形空间的某一个缓存区。我们把所有的缓存key映射到环形空间的不同位置。

640.jpg

3.我们的每一个缓存节点(Shard)也遵循同样的Hash算法,比如利用IP做Hash,映射到环形空间当中。

640.jpg

4.如何让key和节点对应起来呢?很简单,每一个key的顺时针方向最近节点,就是key所归属的存储节点。所以图中key1存储于node1,key2,key3存储于node2,key4存储于node3。

image.gif640.jpg

640.jpg

image.gif640.jpg

image.gif

1.增加节点

当缓存集群的节点有所增加的时候,整个环形空间的映射仍然会保持一致性哈希的顺时针规则,所以有一小部分key的归属会受到影响。

640.jpg

有哪些key会受到影响呢?图中加入了新节点node4,处于node1和node2之间,按照顺时针规则,从node1到node4之间的缓存不再归属于node2,而是归属于新节点node4。因此受影响的key只有key2。

640.jpg

最终把key2的缓存数据从node2迁移到node4,就形成了新的符合一致性哈希规则的缓存结构。

2.删除节点

当缓存集群的节点需要删除的时候(比如节点挂掉),整个环形空间的映射同样会保持一致性哈希的顺时针规则,同样有一小部分key的归属会受到影响。

640.jpg

有哪些key会受到影响呢?图中删除了原节点node3,按照顺时针规则,原本node3所拥有的缓存数据就需要“托付”给node3的顺时针后继节点node1。因此受影响的key只有key4。

640.jpg

image.gif

最终把key4的缓存数据从node3迁移到node1,就形成了新的符合一致性哈希规则的缓存结构。

640.jpg

640.jpg

640.jpg

image.gif

640.jpg

640.jpg

image.gif640.jpg

640.jpg

640.jpg

image.gif640.jpg

如上图所示,假如node1的ip是192.168.1.109,那么原node1节点在环形空间的位置就是hash(“192.168.1.109”)。

我们基于node1构建两个虚拟节点,node1-1 和 node1-2,虚拟节点在环形空间的位置可以利用(IP+后缀)计算,例如:

hash(“192.168.1.109#1”),hash(“192.168.1.109#2”)

此时,环形空间中不再有物理节点node1,node2,只有虚拟节点node1-1,node1-2,node2-1,node2-2。由于虚拟节点数量较多,缓存key与虚拟节点的映射关系也变得相对均衡了。

640.jpg640.jpg640.jpg

640.jpg

640.jpg

相关文章
|
2月前
|
存储 缓存 算法
一文讲透一致性哈希的原理和实现
一文讲透一致性哈希的原理和实现
|
12月前
|
存储 缓存 算法
数据结构与算法第十六讲:分布式算法之一致性Hash算法
数据结构与算法第十六讲:分布式算法之一致性Hash算法
108 0
|
存储 负载均衡 算法
一致性hash算法深入探究
一致性hash算法深入探究
66 0
|
机器学习/深度学习 算法 C语言
算法修炼之练气篇——练气七层
前言:每天练习五道题,炼气篇大概会练习200道题左右,题目有C语言网上的题,也有洛谷上面的题,题目简单适合新手入门。(代码都是命运之光自己写的,练完这200多道题就考了今年第十四届的B组蓝桥杯C/C++获得了省一,后面还会更新“算法修炼之筑基篇”里面包括了省赛到国赛这一个月训练的刷奖计划,大概有40道左右,感兴趣的话可以关注一下命运之光)
124 0
|
算法
基础算法练习200题09、水池注水
基础算法练习200题09、水池注水
140 0
基础算法练习200题09、水池注水
|
存储 缓存 算法
拼夕夕二面:说说布隆过滤器与布谷鸟过滤器?应用场景?我懵了。。
拼夕夕二面:说说布隆过滤器与布谷鸟过滤器?应用场景?我懵了。。
409 0
拼夕夕二面:说说布隆过滤器与布谷鸟过滤器?应用场景?我懵了。。
|
存储 消息中间件 缓存
面试时遇到一致性哈希算法这样回答会让面试官眼前一亮
面试时遇到一致性哈希算法这样回答会让面试官眼前一亮
面试时遇到一致性哈希算法这样回答会让面试官眼前一亮
|
存储 缓存 弹性计算
嗖嗖嗖,想了解一致性Hash,看这一篇就可以了
嗖嗖嗖,想了解一致性Hash,看这一篇就可以了
220 0
嗖嗖嗖,想了解一致性Hash,看这一篇就可以了
|
存储 缓存 算法
面试高频考题——手撸一个 LRU 算法!
今天给大家讲一道面试中经常容易遇到的一道题:“手写一个 LRU 算法”。
226 0
面试高频考题——手撸一个 LRU 算法!
|
存储 数据采集 缓存
冷饭新炒:理解布隆过滤器算法的实现原理
这是《冷饭新炒》系列的第六篇文章。本文会翻炒一个用途比较广的算法 - 布隆过滤器算法。
1592 0
冷饭新炒:理解布隆过滤器算法的实现原理