一致性hash算法深入探究

简介: 一致性hash算法深入探究

1产生背景

负载均衡策略中,我们提到过源地址hash算法,让某些请求固定的落在对应的服务器上。这样可以解决会话信息保留的问题。

同时,标准的hash,如果机器节点数发生变更。那么请求会被重新hash,打破了原始的设计初衷,怎么解决呢?

一致性hash上场。


2 原理探究

以4台机器为例,一致性hash的算法如下:

首先求出各个服务器的哈希值,并将其配置到0~2 32 的圆上

然后采用同样的方法求出存储数据的键的哈希值,也映射圆上

从数据映射到的位置开始顺时针查找,将数据保存到找到的第一个服务器上

如果到最大值仍然找不到,就取第一个。这就是为啥形象的称之为环

cb026636b87b4a0dad55acfae1a34439.png

添加节点:

d66edfaed50241fca948a2ca237bbccf.png

删除节点原理雷同


3 特性

单调性(Monotonicity):单调性是指如果已经有一些请求通过哈希分派到了相应的服务器进行处理,又有新的服务器加入到系统中时候,应保证原有的请求可以被映射到原有的或者新的服务器中去,而不会被映射到原来的其它服务器上去。


分散性(Spread):分布式环境中,客户端请求时可能只知道其中一部分服务器,那么两个客户端看到不同的部

分,并且认为自己看到的都是完整的hash环,那么问题来了,相同的key可能被路由到不同服务器上去。以上图为例,加入client1看到的是1,4;client2看到的是2,3;那么2-4之间的key会被俩客户端重复映射到3,4上去。分散性反应的是这种问题的严重程度。


平衡性(Balance):平衡性是指客户端hash后的请求应该能够分散到不同的服务器上去。一致性hash可以做到尽量分散,但是不能保证每个服务器处理的请求的数量完全相同。这种偏差称为hash倾斜。如果节点的分布算法设计不合理,那么平衡性就会收到很大的影响。


4 优化hash算法

增加虚拟节点可以优化hash算法,使得切段和分布更细化。即实际有m台机器,但是扩充n倍,在环上放置m*n

个,那么均分后,key的段会分布更细化。


560a4d803189479584780efcf9a94d44.png

5 实现

package com.oldlu.hash;
import java.util.Random;
import java.util.SortedMap;
import java.util.TreeMap;
/**
  * 一致性Hash算法
  */
public class Hash {
//服务器列表    
private static String[] servers = { "192.168.0.1",    
        "192.168.0.2", "192.168.0.3", "192.168.0.4" };            
//key表示服务器的hash值,value表示服务器    
private static SortedMap<Integer, String> serverMap = new TreeMap<Integer, String>();    
static {    
        for (int i=0; i<servers.length; i++) {        
        int hash = getHash(servers[i]);            
        //理论上,hash环的最大值为2^32            
//这里为做实例,将ip末尾作为上限也就是254            
//那么服务器是0‐4,乘以60后可以均匀分布到 0‐254 的环上去            
//实际的请求ip到来时,在环上查找即可            
        hash *= 60;            
        System.out.println("add " + servers[i] + ", hash=" + hash);            
        serverMap.put(hash, servers[i]);            
        }        
        }    
//查找节点    
private static String getServer(String key) {    
        int hash = getHash(key);        
        //得到大于该Hash值的所有server        
        SortedMap<Integer, String> subMap = serverMap.tailMap(hash);        
        if(subMap.isEmpty()){        
        //如果没有比该key的hash值大的,则从第一个node开始            
        Integer i = serverMap.firstKey();            
        //返回对应的服务器            
        return serverMap.get(i);            
        }else{        
        //第一个Key就是顺时针过去离node最近的那个结点            
        Integer i = subMap.firstKey();            
        //返回对应的服务器            
        return subMap.get(i);            
        }        
        }    
//运算hash值    
//该函数可以自由定义,只要做到取值离散即可    
//这里取ip地址的最后一节    
private static int getHash(String str) {    
        String last = str.substring(str.lastIndexOf(".")+1,str.length());
String last = str.substring(str.lastIndexOf(".")+1,str.length());        
        return Integer.valueOf(last);        
        }    
public static void main(String[] args) {    
        //模拟5个随机ip请求        
        for (int i = 1; i < 8; i++) {        
        String ip = "192.168.1."+ i*30;            
        System.out.println(ip +" ‐‐‐> "+getServer(ip));            
        }        
        //将5号服务器加到2‐3之间,取中间位置,150        
        System.out.println("add 192.168.0.5,hash=150");        
        serverMap.put(150,"192.168.0.5");        
        //再次发起5个请求        
        for (int i = 1; i < 8; i++) {        
        String ip = "192.168.1."+ i*30;            
        System.out.println(ip +" ‐‐‐> "+getServer(ip));            
        }        
  }    
   }

6 验证结果

4台机器加入hash环

模拟请求,根据hash值,准确调度到下游节点

添加节点5,key取150

再次发起请求

目录
相关文章
|
消息中间件 算法 分布式数据库
Raft算法:分布式一致性领域的璀璨明珠
【4月更文挑战第21天】Raft算法是分布式一致性领域的明星,通过领导者选举、日志复制和安全性解决一致性问题。它将复杂问题简化,角色包括领导者、跟随者和候选者。领导者负责日志复制,确保多数节点同步。实现细节涉及超时机制、日志压缩和网络分区处理。广泛应用于分布式数据库、存储系统和消息队列,如Etcd、TiKV。其简洁高效的特点使其在分布式系统中备受青睐。
|
算法 分布式数据库
Paxos算法:分布式一致性的基石
【4月更文挑战第21天】Paxos算法是分布式一致性基础,由Leslie Lamport提出,包含准备和提交阶段,保证安全性和活性。通过提案编号、接受者和学习者实现,广泛应用于分布式数据库、锁和配置管理。其简单、高效、容错性强,影响了后续如Raft等算法,是理解分布式系统一致性关键。
|
存储 缓存 负载均衡
一致性 Hash 算法 Hash 环发生偏移怎么解决
一致性 Hash 算法 Hash 环发生偏移怎么解决
253 1
|
4月前
|
消息中间件 存储 缓存
zk基础—1.一致性原理和算法
本文详细介绍了分布式系统的特点、理论及一致性算法。首先分析了分布式系统的五大特点:分布性、对等性、并发性、缺乏全局时钟和故障随时发生。接着探讨了分布式系统理论,包括CAP理论(一致性、可用性、分区容错性)和BASE理论(基本可用、软状态、最终一致性)。文中还深入讲解了两阶段提交(2PC)与三阶段提交(3PC)协议,以及Paxos算法的推导过程和核心思想,强调了其在ZooKeeper中的应用。最后简述了ZAB算法,指出其通过改编的两阶段提交协议确保节点间数据一致性,并在Leader故障时快速恢复服务。这些内容为理解分布式系统的设计与实现提供了全面的基础。
|
17天前
|
机器学习/深度学习 传感器 算法
基于不变扩展卡尔曼滤波器RI-EKF的同时定位与地图构建SLAM算法的收敛性和一致性特性研究(Matlab代码实现)
基于不变扩展卡尔曼滤波器RI-EKF的同时定位与地图构建SLAM算法的收敛性和一致性特性研究(Matlab代码实现)
|
3月前
|
存储 负载均衡 算法
我们来说一说 Java 的一致性 Hash 算法
我是小假 期待与你的下一次相遇 ~
116 1
|
存储 算法 NoSQL
(七)漫谈分布式之一致性算法下篇:一文从根上儿理解大名鼎鼎的Raft共识算法!
Raft通过一致性检查,能在一定程度上保证集群的一致性,但无法保证所有情况下的一致性,毕竟分布式系统各种故障层出不穷,如何在有可能发生各类故障的分布式系统保证集群一致性,这才是Raft等一致性算法要真正解决的问题。
289 11
|
存储 算法 索引
(六)漫谈分布式之一致性算法上篇:用二十六张图一探Raft共识算法奥妙之处!
现如今,大多数分布式存储系统都投向了Raft算法的怀抱,而本文就来聊聊大名鼎鼎的Raft算法/协议!
321 8
|
存储 算法 Java
(五)漫谈分布式之一致性算法篇:谁说Paxos晦涩难懂?你瞧这不一学就会!
没在时代发展的洪流中泯然于众的道理很简单,是因为它们并不仅是空中楼阁般的高大上理论,而是有着完整落地的思想,它们已然成为构建分布式系统不可或缺的底层基石,而本文则来好好聊聊分布式与一致性思想的落地者:Paxos与Raft协议(算法)。
267 6
|
缓存 负载均衡 算法
(四)网络编程之请求分发篇:负载均衡静态调度算法、平滑轮询加权、一致性哈希、最小活跃数算法实践!
先如今所有的技术栈中,只要一谈关于高可用、高并发处理相关的实现,必然会牵扯到集群这个话题,也就是部署多台服务器共同对外提供服务,从而做到提升系统吞吐量,优化系统的整体性能以及稳定性等目的。
313 2

热门文章

最新文章