分布式集群架构场景化解决方案(一)-一致性Hash算法

Scroll Down

分布式集群架构场景化解决方案(一)-一致性Hash算法

普通Hash算法与Hash算法使用场景

Hash算法,比如说在安全加密领域MD5、SHA等加密算法,在数据存储和查找方面有Hash表等, 以上都应用到了Hash算法。

为什么需要使用Hash算法?

Hash算法较多的应用在数据存储和查找领域,最经典的就是Hash表,它的查询效率非常高,其中的哈希算法如果设计的比较ok的话,那么Hash表的数据查询时间复杂度可以接近于O(1)

Hash算法的主要场景

  • 请求的负载均衡(比如nginx的ip_hash策略)Nginx的IP_hash策略可以在客户端ip不变的情况下,将其发的请求始终路由到同⼀个目标服务器上,实现会话粘滞,避免处理session共享问题

  • 分布式存储-分布式数据存储方案中最为重要的一点就是数据分片,也就是所谓的 Sharding。以分布式内存数据库Redis为例,将数据分片存储在三台服务器上,将key使用hash算法进行计算,判断应当存储在哪一台服务器上,减轻单个Redis服务的压力

普通Hash算法的问题

普通Hash算法存在⼀个问题,以ip_hash为例,假定下载用户ip固定没有发生改变,现在tomcat3出现了问题,down机了,服务器数量由3个变为了2个,之前所有的计算都需要重新计算

image-20200623164839205

如果在真实生产情况下,后台服务器很多台,客户端也有很多,那么影响是很大的,缩容和扩容都会存在这样的问题,大量用户的请求会被路由到其他的⽬标服务器处理,用户在原来服务器中的会话都会丢失

⼀致性Hash算法

⼀致性哈希算法思路如下:

开头和结尾分别定为为1和2的32次方减一,构成一个环,每个服务端节点的IP地址进行求值并且对应到Hash环上,针对客户端的用户,也根据它的IP进行Hash求值,这样对应到环上的某个位置,顺时针找到最近的服务器节点就是它应当访问的服务器节点

image-20200623165133100

使用一致性算法的话,假如一个服务器3下线,那么原来路由到3的客户端重新会路由到服务器4,这样只需要迁移一部分原有应该访问到服务器3的请求到服务器4上面,降低了迁移请求造成的影响
image-20200623170133690

同样,增加一个服务器也会将请求的迁移降低到最低

image-20200623170201011

一致性Hash算法的缺点

如上面所述,每一台服务器负责一段,对于节点的增减有很方便的扩展下和容错性

缺点:

当一致性哈希算法在服务节点太少时,容易因为节点分布不均匀导致数据倾斜问题,大量数据都传递到了一台服务器,导致服务器压力过大

解决方案:

为了解决这种问题,一致性Hash算法引入了虚拟节点的方案,针对每一个服务节点计算多个Hash,每个计算结果未知都放置一个此服务节点,称为虚拟节点

具体做法:

在服务器的IP或者主机名或者用于计算的Key值后面增加编号来实现,例如每台服务器可以扩展成三个节点,就可以计算"节点1的IP#1","节点1的IP#2","节点1的IP#3","节点2的IP#1","节点2的IP#2","节点2的IP#3",这样就相当于将两个Hash节点扩展成了6个Hash节点,并且路由到虚拟节点时也是实际节点去处理的,这样就避免了我们所说的数据倾斜问题

image-20200623172438301

手写一致性算法实现

public class ConsistentHashMain {
    private static int virtualNode = 3;
    public static void main(String[] args) {
        //服务端的IP
        String[] serverIps = new String[]{"10.20.169.61","10.20.168.209","10.20.165.20"};
        //使用排序Map,这样的话可以取到最近的那个节点
        SortedMap<Integer,String> hashServerMap = new TreeMap<>();
        for (String server : serverIps) {
            for (int i = 0; i < virtualNode; i++) {
                //对原有节点IP进行编号
                String tempServer = server + "#" +i;
                //hash值只取正值
                Integer hashCode = Math.abs(tempServer.hashCode());
                hashServerMap.put(hashCode,"虚拟节点"+i+"指向的->"+ server);
            }
        }
        //模拟客户端的请求IP
        String[] clientIps = new String[]{"127.0.0.1","10.53.214.22","20.23.241.23","112.55.22.24","22.55.22.24"};
        for (String clientIp : clientIps) {
            //获取客户端的IP的Hash值
            Integer hashCode = Math.abs(clientIp.hashCode());
            //取出比该值更大的Map数据
            SortedMap<Integer, String> tailMap = hashServerMap.tailMap(hashCode);
            //如果为空,则直接取原来的第一个节点
            if (tailMap.isEmpty()) {
                Integer key = hashServerMap.firstKey();
                String value = hashServerMap.get(key);
                System.out.println("客户端IP:"+clientIp+"分发到了服务器的节点:"+value);
            }else{
            //否则取顺时针第一个节点    
                Integer key = tailMap.firstKey();
                String value = hashServerMap.get(key);
                System.out.println("客户端IP:"+clientIp+"分发到了服务器的节点:"+value);
            }
        }
    }
    
}