首页 > 数据库 >[Redis]一致性哈希

[Redis]一致性哈希

时间:2024-07-07 23:53:29浏览次数:18  
标签:Node Redis 算法 哈希 一致性 服务器 节点

一致性哈希算法(Consistent Hashing)最早在论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中被提出。简单来说,一致性哈希将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数 H 的值空间为 0-2^32-1(即哈希值是一个 32 位无符号整形),整个哈希空间环如下:
image

整个空间按顺时针方向组织。0 和 232-1 在零点中方向重合。

  下一步将各个服务器使用 Hash 进行一个哈希,具体可以选择服务器的 ip 或主机名作为关键字进行哈希,这样每台机器就能确定其在哈希环上的位置,这里假设将上文中四台服务器使用 ip 地址哈希后在环空间的位置如下:
image

接下来使用如下算法定位数据访问到相应服务器:将数据 key 使用相同的函数 Hash 计算出哈希值,并确定此数据在环上的位置,从此位置沿环顺时针“行走”,第一台遇到的服务器就是其应该定位到的服务器。

  例如我们有 Object A、Object B、Object C、Object D 四个数据对象,经过哈希计算后,在环空间上的位置如下:

image

根据一致性哈希算法,数据 A 会被定为到 Node A 上,B 被定为到 Node B 上,C 被定为到 Node C 上,D 被定为到 Node D 上。

下面分析一致性哈希算法的容错性和可扩展性。现假设 Node C 不幸宕机,可以看到此时对象 A、B、D 不会受到影响,只有 C 对象被重定位到 Node D。一般的,在一致性哈希算法中,如果一台服务器不可用,则受影响的数据仅仅是此服务器到其环空间中前一台服务器(即沿着逆时针方向行走遇到的第一台服务器)之间数据,其它不会受到影响。

下面考虑另外一种情况,如果在系统中增加一台服务器 Node X,如下图所示:
image

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

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

另外,一致性哈希算法在服务节点太少时,容易因为节点分部不均匀而造成数据倾斜问题。例如系统中只有两台服务器,其环分布如下,
image

此时必然造成大量数据集中到 Node A 上,而只有极少量会定位到 Node B 上。为了解决这种数据倾斜问题,一致性哈希算法引入了虚拟节点机制,即对每一个服务节点计算多个哈希,每个计算结果位置都放置一个此服务节点,称为虚拟节点。具体做法可以在服务器 ip 或主机名的后面增加编号来实现。例如上面的情况,可以为每台服务器计算三个虚拟节点,于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值,于是形成六个虚拟节点:

image

同时数据定位算法不变,只是多了一步虚拟节点到实际节点的映射,例如定位到“Node A#1”、“Node A#2”、“Node A#3”三个虚拟节点的数据均定位到 Node A 上。这样就解决了服务节点少时数据倾斜的问题。在实际应用中,通常将虚拟节点数设置为 32 甚至更大,因此即使很少的服务节点也能做到相对均匀的数据分布。

标签:Node,Redis,算法,哈希,一致性,服务器,节点
From: https://www.cnblogs.com/DCFV/p/18289130

相关文章

  • NoSQL之Redis集群
    目录1.Redis主从复制(1)Redis主从复制工作原理(2)搭建Redis主从复制2.Redis哨兵模式(1)Redis哨兵工作原理(2)搭建Redis哨兵模式3.Redis集群模式(1)集群模式的工作原理(2)集群模式的特点(3)搭建Redis群集模式(4)集群模式与哨兵模式的主要区别1.Redis主从复制(1)Redis主从复制工作原理1.......
  • NoSQL之 Redis配置与优化
    目录1.关系数据库和非关系数据库2.Redis安装部署(1)Redis简介(2)Redis为什么那么快?(3)Redis安装部署(1)环境准备(2)安装redis(3)修改配置文件(4)定义systemd服务管理脚本(4)redis-benchmark测试工具3.Redis数据库常用命令(1)Redis数据类型4.Redis高可用(1)Redis持久化5.Redis性能管理(1)内存碎片6.re......
  • Redis中间件与Web中间件
    易混淆概念辨析在不同的上下文中,“Redis中间件”可以有不同的含义,这可能导致一些混淆。让我们来分解一下:Web中间件与消息中间件的区别:Web中间件:在ASP.NETCore(或类似框架)中,中间件是指处理HTTP请求管道的组件,例如处理请求、认证、日志记录等。这些中间件按顺序构成一个请求......
  • Leetcode刷题记录1 哈希+双指针+滑动窗口
    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档文章目录前言hot1001.哈希#1.两数之和#49.字母异位词分组#128.最长连续序列2.双指针#283.移动零#11.盛最多水的容器#15.三数之和#42.接雨水3.滑动窗口#3.无重复字符的最长子串#438.找到字符串中所有......
  • Redis基本命令源码解析-字符串命令
    1.set用于将kv设置到数据库中2.mset批量设置kvmset(msetnx)key1value1key2value2...mset:msetCommandmsetnx:msetnxCommandmsetCommand和msetnxCommand都调用msetGenericCommand2.1msetGenericCommand如果参数个数为偶数,则响应参数错误并返回如果nx=1,则......
  • [Redis]持久化
    持久化Redis的数据全部在内存里,如果突然宕机,数据就会全部丢失,因此必须有一种机制来保证Redis的数据不会因为故障而丢失,这种机制就是Redis的持久化机制。Redis的持久化机制有两种,第一种是快照,第二种是AOF日志。快照是一次全量备份,AOF日志是连续的增量备份。快照是内存数据的二......
  • [Redis]扩容
    原因扩容原因:当hashtable存储的元素过多,可能由于碰撞也过多,导致其中某链表很长,最后致使查找和插入时间复杂度很大。因此当元素超多一定的时候就需要扩容。缩容原因:当元素数量比较少的时候就需要缩容以节约不必要的内存。为了让哈希表的负载因子(loadfactor)维持在一个合理的范围......
  • 深度解析 Raft 分布式一致性协议
    深度解析Raft分布式一致性协议本文参考转载至:浅谈Raft分布式一致性协议|图解Raft-白泽来了-博客园(cnblogs.com)深度解析Raft分布式一致性协议-掘金(juejin.cn)raft-zh_cn/raft-zh_cn.mdatmaster·maemual/raft-zh_cn(github.com)本篇文章将模拟一个KV......
  • [Redis]ZSet
    通过value查score在Redis的有序集合(zset)中,通过成员(member)获取其对应的分数(score)的复杂度是O(logN),其中N是有序集合中的元素数量。这是因为Redis使用跳跃表(skiplist)和哈希表(hashtable)的组合来实现有序集合。跳跃表用于按顺序存储元素,以便高效地按分数排序和查找范围,而哈......
  • Redis 高阶应用
    生成全局唯一ID全局唯一ID需要满足以下要求:唯一性:在分布式环境中,要全局唯一高可用:在高并发情况下保证可用性高性能:在高并发情况下生成ID的速度必须要快,不能花费太长时间递增性:要确保整体递增的,以便于数据库创建索引安全性:ID的规律性不能太明显,以免信息泄......