Java三齐王乱点兵算法_韩信的大招:一致性哈希算法

2024-01-30 17:50

本文主要是介绍Java三齐王乱点兵算法_韩信的大招:一致性哈希算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

韩信点兵的成语来源淮安民间传说。常与多多益善搭配。寓意越多越好。我们来看下主公刘邦和韩信大将军的对话。

刘邦:“你觉得我可以带兵多少?”

韩信:“最多十万。”

刘邦不解的问:“那你呢?”

韩信自豪地说:“越多越好,多多益善嘛!

假如刘邦现在给了韩信一千个士兵,需要大致均匀分成三组。士兵的编号是六位数,从 1-100000 随机分配。比如第一个士兵的值是 245,第二个士兵的编号是 82593,其他士兵类似。那么如何对士兵进行分配呢?

刘邦:韩将军,你看这些士兵怎么分配好呢?

韩信:这还不简单,我的一技能就能搞定。

一技能:哈希算法

分组

韩信的一技能哈希算法:将士兵的编号 num 值当做一个哈希值,再和总做小组数 N 做取余操作,得出的结果在 0 到 N - 1 之间,这个士兵就属于那个组。

如下图所示,每来一个士兵都有一个六位的 hash 值(也可以称作编号),然后被韩信用除以 3 取余数的方式分配到三个组。比如第一组中的编号为 123456 的士兵,除以 3 之后,整除,余数为 0,所以分配到第一组。

d881b1b7c057b48c8fbf2f0341617cf9.png

哈希算法

查找士兵

现在已经分好组了,假如想找到编号为 666666 的士兵该怎么找?首先将 666666 除以 3,得到余数 0,说明在第一个组,然后去第一个组里面找就可以了。

这里有小伙伴可能会问,为什么不是把所有士兵放到一个组?

因为一个组太大了,影响行军速度。映射到互联网架构中,就是通过增加节点从而减小单节点的负载压力。

哈希分组弊端

刘邦看了这个一技能后,大呼:

韩将军真是厉害。

哈希算法看起来很完美,那我再给你五百士兵,需要分成四个组怎么办?

这时,韩信的副将说话了:

这还不简单,再用 4 取余不就好了吗?

刘邦摸着下巴思索片刻后,对副将说:

这个方案可行,但很多士兵都被重新分组了,刚刚建立的团队友情就被分解了。

我们来看下刘邦为什么觉得方案不可行。

比如原来分配到一组的编号为 3 的士兵,当分成四组的时候,通过公式计算:3%4=3,所以会分配到到第四组。

依次类推,会发现很多士兵进行了重新分配,只有小部分不会变换分组,比如 1,2,12 不会被重新分组。

韩信对着刘邦点点头,对着主公说道:

主公,您说得没错,这就是我的一技能的弱点所在。

不过我还有一个技能:一致性哈希。

二技能:一致性哈希

哈希环

一致性哈希算法也用了取模运算,但是它与哈希算法不同的地方:

哈希算法:对节点的数量进行取模运算。

一致性哈希算法:对 2^32 进行取模运算。

可以想象一下,一致性哈希算法,是将整个哈希值空间组成了一个虚拟的圆环,也就是哈希环。

如下图,把 3 个组映射到固定大小为 2^32 的哈希环中。三个组一共将整个环分成了三个区域,C-A(第一组)、A-B(第二组)、B-C(第三组)。如下图所示:

0090da1629b89b6ae9014aff21b77e9d.png

分成三组

第一组负责存储落在 C-A 区间内的数据。

第二组负责存储落在 A-B 区间内的数据。

第三组负责存储落在 B-C 区间内的数据。

士兵分配

假定编号为 9527 的士兵,进行哈希运算后,落到 C-A 区域。如下图所示:

27d3e532c86a0334d2c0cd03eedf29f2.png

士兵所站位置

第二步,让这个士兵顺时针往前走,遇到的第一个节点 A 就是他所在的组了。如下图所示:

a29854bbdc0dadcf8efd3ba084968520.png

顺时针遇到第一个节点

增加分组

目前三个节点的时候,假定编号为 89757 的士兵经过哈希运算后,分配到了 B-C 区域(第三组),也就是属于 C 节点管控。如下图所示:

a3a58948787c014b4a1709841defc97c.png

属于 C 节点

回到刘邦刚问的问题,如果分组变成四组,该怎么进行士兵分配。

如下图所示,增加一个节点 D,原来的区域 B-C 变成了区域 B-D(第三组) 和 D-C(第四组)。

5436abb9d727e3fe3869709068431934.png

增加 D 节点

那么这名士兵属于哪个节点管控呢?如下图所示,士兵顺时针往前走,先走到了 D 节点,所以属于 D 节点管控。虽然还是属于第三组,但是这名士兵的领导者已经变了:由 C 变成了 D。

4fa427dc7aa4cf236c7604d297dbd932.png

领导者变了

从上面的变化来看,只有 B-C 区域中的部分数据会进行迁移:B-D 之间的数据会由 C 节点迁移到 D 节点。

而其他数据不受影响,也不用进行迁移。而且节点越多,需要迁移的数据就越少。这就是多多益善了~

刘邦看了后,大赞韩信:

不亏是大将军,萧何当时月下追你,值了!

哈希环缺陷

萧何看了韩信画的哈希环后,觉得有些不对劲,思索片刻后,对韩信说:

将军,你这个哈希环上的节点分布不太均匀啊,你看第三组和第四组的的区域好小啊。

萧何说得没错,确实存在这个问题,放到互联网架构中,就存在如下问题:

节点分布不均匀,导致业务对节点的访问冷热不均。

韩信眼中充满着赞赏,知我者莫若萧何。然后胸有成竹地说道:

你说得没错,不过我还有一个技能,虚拟节点映射。

三技能:虚拟节点

一般虚拟节点比物理节点要多,并相对均匀地分布在哈希环上。如下图所示,12 个虚拟节点 N1~N12,相对均匀地分布在虚拟节点上。如果有士兵属于 N2/N3/N4 中的某一个,都会重新映射到 A 节点,依次类推,N5/N6/N7 属于 B 节点的虚拟节点映射。

baa5fd4f457c4269aeb3f473c27f1b35.png

虚拟节点

我们来看下萧何的提出的问题,真实的 B-D 区域比较小,用虚拟节点后,N5/N6/N7 属于 B 节点,N8/N9/N10 属于 D 节点,他们分到的虚拟节点一样多,而且区域大致相等。所以士兵的分配也比较均匀。

萧何看了韩信的三技能后,直呼:妙哉妙哉!

总结

本篇通过韩信点兵的故事,然后从故事中衍生出刘邦、韩信、萧何的对话,来讲解士兵的分组的问题。现在对故事中的知识点做一个总结:

哈希算法会带来增加或删除节点时,

数据迁移量太大的问题。

一致性哈希算法

降低了数据迁移量。

节点较少

,哈希环上每个节点实际占据的区间大小不一,最终导致业务对节点的访问

冷热不均。

引入

虚拟节点映射解决了分布不均问题。

节点

越多时,

使用哈希

算法时,需要迁移的数据就

越多,而使用一致性哈希算法,迁移的数据就

越少。

一致性哈希算法本质上是一种

路由寻址算法,适合简单的路由寻址场景。

一致性哈希算法常用在负载均衡的架构设计中。

这篇关于Java三齐王乱点兵算法_韩信的大招:一致性哈希算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/661055

相关文章

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时,有没有考虑过 JVM 是如何把静态的字节码(byte code)转化为运行时对象的呢,这个问题看似简单,但清楚的同学相信也不会太多,这篇文章首先介绍 JVM 类初始化的机制,然后给出几个易出错的实例来分析,帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段,分别是:loading 、Linking、initialization

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类,它们之间的依赖,构建起了整个框架。想要理解整个架构,最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文(security context)的信息。当前操作的用户是谁,该用户是否已经被认证,他拥有哪些角色权限…这些都被保

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory