一致性 Hash 算法的实际应用
记得一年前分享过一篇《一致性 Hash 算法分析》,当时只是分析了这个算法的实现原理、解决了什么问题等。
但没有实际实现一个这样的算法,毕竟要加深印象还得自己撸一遍,于是本次就当前的一个路由需求来着手实现一次。
看过《为自己搭建一个分布式 IM(即时通讯) 系统》的朋友应该对其中的登录逻辑有所印象。
先给新来的朋友简单介绍下 cim 是干啥的:
其中有一个场景是在客户端登录成功后需要从可用的服务端列表中选择一台服务节点返回给客户端使用。
而这个选择的过程就是一个负载策略的过程;第一版本做的比较简单,默认只支持轮询的方式。
虽然够用,但不够优雅?。
因此我的规划是内置多种路由策略供使用者根据自己的场景选择,同时提供简单的 API 供用户自定义自己的路由策略。
先来看看一致性 Hash 算法的一些特点:
构造一个 0 ~ 2^32-1 大小的环。 服务节点经过 hash 之后将自身存放到环中的下标中。 客户端根据自身的某些数据 hash 之后也定位到这个环中。 通过顺时针找到离他最近的一个节点,也就是这次路由的服务节点。 考虑到服务节点的个数以及 hash 算法的问题导致环中的数据分布不均匀时引入了虚拟节点。 自定义有序 Map根据这些客观条件我们很容易想到通过自定义一个有序数组来模拟这个环。
这样我们的流程如下:
先不考虑排序所消耗的时间,单看这个路由的时间复杂度:
最好是第一次就找到,时间复杂度为O(1)。 最差为遍历完数组后才找到,时间复杂度为O(N)。理论讲完了来看看具体实践。
我自定义了一个类:SortArrayMap
他的使用方法及结果如下:
可见最终会按照 key 的大小进行排序,同时传入 hashcode = 101 时会按照顺时针找到 hashcode = 1000 这个节点进行返回。
下面来看看具体的实现。
成员变量和构造函数如下:
其中最核心的就是一个 Node 数组,用它来存放服务节点的 hashcode 以及 value 值。
其中的内部类 Node 结构如下:
写入数据的方法如下:
相信看过 ArrayList 的源码应该有印象,这里的写入逻辑和它很像。
写入之前判断是否需要扩容,如果需要则复制原来大小的 1.5 倍数组来存放数据。 之后就写入数组,同时数组大小 +1。但是存放时是按照写入顺序存放的,遍历时自然不会有序;因此提供了一个 Sort 方法,可以把其中的数据按照 key 其实也就是 hashcode 进行排序。
排序也比较简单,使用了 Arrays 这个数组工具进行排序,它其实是使用了一个 TimSort 的排序算法,效率还是比较高的。
最后则需要按照一致性 Hash 的标准顺时针查找对应的节点:
代码还是比较简单清晰的;遍历数组如果找到比当前 key 大的就返回,没有查到就取第一个。
这样就基本实现了一致性 Hash 的要求。
ps:这里并不包含具体的 hash 方法以及虚拟节点等功能(具体实现请看下文),这个可以由使用者来定,SortArrayMap 可作为一个底层的数据结构,提供有序 Map 的能力,使用场景也不局限于一致性 Hash 算法中。
TreeMap 实现SortArrayMap 虽说是实现了一致性 hash 的功能,但效率还不够高,主要体现在 sort 排序处。
下图是目前主流排序算法的时间复杂度:
最好的也就是 O(N) 了。
这里完全可以换一个思路,不用对数据进行排序;而是在写入的时候就排好顺序,只是这样会降低写入的效率。
比如二叉查找树,这样的数据结构 jdk 里有现成的实现;比如 TreeMap 就是使用红黑树来实现的,默认情况下它会对 key 进行自然排序。
来看看使用 TreeMap 如何来达到同样的效果。
运行结果:
1127.0.0.1000
效果和上文使用 SortArrayMap 是一致的。
只使用了 TreeMap 的一些 API:
写入数据候,TreeMap 可以保证 key 的自然排序。 tailMap 可以获取比当前 key 大的部分数据。 当这个方法有数据返回时取第一个就是顺时针中的第一个节点了。 如果没有返回那就直接取整个 Map 的第一个节点,同样也实现了环形结构。ps:这里同样也没有 hash 方法以及虚拟节点(具体实现请看下文),因为 TreeMap 和 SortArrayMap 一样都是作为基础数据结构来使用的。
为了方便大家选择哪一个数据结构,我用 TreeMap 和 SortArrayMap 分别写入了一百万条数据来对比。
先是 SortArrayMap:
耗时 2237 毫秒。
TreeMap:
耗时 1316毫秒。
结果是快了将近一倍,所以还是推荐使用 TreeMap 来进行实现,毕竟它不需要额外的排序损耗。
cim 中的实际应用下面来看看在 cim 这个应用中是如何具体使用的,其中也包括上文提到的虚拟节点以及 hash 算法。
在应用的时候考虑到就算是一致性 hash 算法都有多种实现,为了方便其使用者扩展自己的一致性 hash 算法因此我定义了一个抽象类;其中定义了一些模板方法,这样大家只需要在子类中进行不同的实现即可完成自己的算法。
AbstractConsistentHash,这个抽象类的主要方法如下:
add 方法自然是写入数据的。 sort 方法用于排序,但子类也不一定需要重写,比如 TreeMap 这样自带排序的容器就不用。 getFirstNodeValue 获取节点。 process 则是面向客户端的,最终只需要调用这个方法即可返回一个节点。下面我们来看看利用 SortArrayMap 以及 AbstractConsistentHash 是如何实现的。
就是实现了几个抽象方法,逻辑和上文是一样的,只是抽取到了不同的方法中。
只是在 add 方法中新增了几个虚拟节点,相信大家也看得明白。
把虚拟节点的控制放到子类而没有放到抽象类中也是为了灵活性考虑,可能不同的实现对虚拟节点的数量要求也不一样,所以不如自定义的好。
但是 hash 方法确是放到了抽象类中,子类不用重写;因为这是一个基本功能,只需要有一个公共算法可以保证他散列地足够均匀即可。
因此在 AbstractConsistentHash 中定义了 hash 方法。
这里的算法摘抄自 xxl_job,网上也有其他不同的实现,比如 FNV1_32_HASH 等;实现不同但是目的都一样。
这样对于使用者来说就非常简单了:
他只需要构建一个服务列表,然后把当前的客户端信息传入 process 方法中即可获得一个一致性 hash 算法的返回。
同样的对于想通过 TreeMap 来实现也是一样的套路:
他这里不需要重写 sort 方法,因为自身写入时已经排好序了。
而在使用时对于客户端来说只需求修改一个实现类,其他的啥都不用改就可以了。
运行的效果也是一样的。
这样大家想自定义自己的算法时只需要继承 AbstractConsistentHash 重写相关方法即可,客户端代码无须改动。
路由算法扩展性但其实对于 cim 来说真正的扩展性是对路由算法来说的,比如它需要支持轮询、hash、一致性hash、随机、LRU等。
只是一致性 hash 也有多种实现,他们的关系就如下图:
应用还需要满足对这一类路由策略的灵活支持,比如我也想自定义一个随机的策略。
因此定义了一个接口:RouteHandle
1public interface RouteHandle { 3 /** 4 * 再一批服务器里进行路由 5 * @param values 6 * @param key 7 * @return 8 */ 9 String routeServer(List String values,String key) ;
其中只有一个方法,也就是路由方法;入参分别是服务列表以及客户端信息即可。
而对于一致性 hash 算法来说也是只需要实现这个接口,同时在这个接口中选择使用 SortArrayMapConsistentHash 还是 TreeMapConsistentHash 即可。
这里还有一个 setHash 的方法,入参是 AbstractConsistentHash;这就是用于客户端指定需要使用具体的那种数据结构。
而对于之前就存在的轮询策略来说也是同样的实现 RouteHandle 接口。
这里我只是把之前的代码搬过来了而已。
接下来看看客户端到底是如何使用以及如何选择使用哪种算法。
为了使客户端代码几乎不动,我将这个选择的过程放入了配置文件。
不管这里的策略如何改变,在使用处依然保持不变。
只需要注入 RouteHandle,调用它的 routeServer 方法。
1@Autowired 2private RouteHandle routeHandle ; 3String server = routeHandle.routeServer(serverCache.getAll(),String.valueOf(loginReqVO.getUserId()));
既然使用了注入,那其实这个策略切换的过程就在创建 RouteHandle bean 的时候完成的。
也比较简单,需要读取之前的配置文件来动态生成具体的实现类,主要是利用反射完成的。
这样处理之后就比较灵活了,比如想新建一个随机的路由策略也是同样的套路;到时候只需要修改配置即可。
感兴趣的朋友也可提交 PR 来新增更多的路由策略。
希望看到这里的朋友能对这个算法有所理解,同时对一些设计模式在实际的使用也能有所帮助。
相信在金三银四的面试过程中还是能让面试官眼前一亮的,毕竟根据我这段时间的面试过程来看听过这个名词的都在少数?(可能也是和候选人都在 1~3 年这个层级有关)。
以上所有源码:
https://github.com/crossoverJie/cim
如果本文对你有所帮助还请不吝转发。
原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/60451.html
jd相关文章
- 【NLP基础】英文关键词抽取RAKE算法
- react中的diff算法,通俗易懂的解读
- 人生九段算法:用算法经营自己的人生(1-4段)
- php面试题-算法题总结篇
- 「数据结构与算法Javascript描述」十大排序算法
- Java递归算法应用
- hash一致性算法以及应用场景_什么不是算法的基本特性
- 刷完这19道leetcode二分查找算法,不信进不了大厂
- 极大极小值算法应用于五子棋
- Union Find 并查集算法原理及应用
- LeetCode算法-栈相关题目
- 一致性 Hash 算法原理&应用梳理
- 2022新书《图神经网络》,崔鹏、裴健等领域大牛撰写,全面介绍GNN算法与应用
- C++ STL 标准模板库(容器总结)算法
- 数据结构、算法与应用 习题5.3 p104
- 三维声技术在赛事直播中的应用,TWS耳机中音频技术落地实践,通话降噪算法落地应用及挑战
- 下(应用篇)| 推荐几款较流行的量子算法
- 顺序表应用4-2:元素位置互换之逆置算法(数据改进)(SDUT 3663)
- 【数据挖掘】关联规则挖掘 Apriori 算法 ( 关联规则简介 | 数据集 与 事物 Transaction 概念 | 项 Item 概念 | 项集 Item Set | 频繁项集 | 示例解析 )
- DSP CLA算法开发案例——基于TMS320F2837xD+FPGA开发板
- R语言关联规则挖掘apriori算法挖掘评估汽车性能数据
- C语言归并排序算法
- 有没有主宰世界的主算法?
- 程序兵法:Java String 源码的排序算法(一)
- PRICAI 2016 论文精选 | 特征选取与实例选取的差分进化算法
- Linux系统中应用的多种算法思想(linux使用的算法)
- MySQL中位取反教程详解算法步骤及应用方法(mysql中位取反怎么算)
- KMP算法在Oracle环境中的应用实践(kmp oracle实现)
- .NET下文本相似度算法余弦定理和SimHash浅析及应用实例分析
- python快速查找算法应用实例