一致性hash算法 java实现_信息的一致性

一致性hash算法 java实现_信息的一致性介绍一致性Hash算法是实现负载均衡的一种策略,后续会写如何实现负载均衡一致哈希是一种特殊的哈希算法。在使用一致哈希算法后,哈希表槽位数(大小)的改变平均只需要对K/n个关键字重新映射,其中K是关键字的数量,n是槽位数量。然而在传统的哈希表中,添加或删除一个槽位的几乎需要对所有关键字进行重新映射。强哈希考虑到单服务器不能承载,因此使用了分布式架构,最初的算法为hash()modn,hash()通常取用户ID,n为节点数。此方法容易实现且能够满足运营要求。缺点是当单点发

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

介绍

一致性Hash算法是实现负载均衡的一种策略,后续会写如何实现负载均衡

一致哈希是一种特殊的哈希算法。

在使用一致哈希算法后,哈希表槽位数(大小)的改变平均只需要对 K/n个关键字重新映射,其中K是关键字的数量, n是槽位数量。

然而在传统的哈希表中,添加或删除一个槽位的几乎需要对所有关键字进行重新映射。

强哈希

考虑到单服务器不能承载,因此使用了分布式架构,最初的算法为 hash() mod n, hash()通常取用户ID,n为节点数。

此方法容易实现且能够满足运营要求。缺点是当单点发生故障时,系统无法自动恢复。同样不也不能进行动态增加节点。

一致性hash算法 java实现_信息的一致性

优缺点

强哈希可以将数据均匀的打散到节点上。但是如果新增/删除节点呢?显然会发生大量的节点移动才能继续使用该算法,因此缺点是该算法与节点数目强耦合。

当node数发生变化的时候,hash item所对应的node发生剧烈变化,而发生变化的成本就是我们需要在node数发生变化的时候迁移数据。因而诞生了弱哈希

弱哈希

为了解决单点故障,使用 hash() mod (n/m)

这样任意一个用户都有 m 个服务器备选,可由 client 随机选取。

由于不同服务器之间的用户需要彼此交互,所以所有的服务器需要确切的知道用户所在的位置。

因此用户位置被保存到 memcached 中。当一台发生故障,client 可以自动切换到对应 backup,由于切换前另外 1 台没有用户的 session,因此需要 client 自行重新登录。

  • 好处

他比强哈希的好处是:解决了单点问题。

  • 缺点

但存在以下问题:负载不均衡,尤其是单台发生故障后剩下一台会压力过大;不能动态增删节点;节点发生故障时需要 client 重新登录

因而出现了一致性hash,一致性 hash 算法适用于动态变化的 Cache 环境。

一致性Hash算法

一致性哈希算法有多种具体的实现,包括 Chord 算法KAD 算法等实现,以上的算法的实现都比较复杂。

这里介绍一种网上广为流传的一致性哈希算法的基本实现原理,感兴趣的同学可以根据上面的链接或者去网上查询更详细的资料。

一致性哈希算法的基本实现原理是将机器节点和key值都按照一样的hash算法映射到一个0~2^32的圆环上。

当有一个写入缓存的请求到来时,计算 Key 值 k 对应的哈希值 Hash(k),如果该值正好对应之前某个机器节点的 Hash 值,则直接写入该机器节点, 如果没有对应的机器节点,则顺时针查找下一个节点,进行写入,如果超过 2^32 还没找到对应节点,则从0开始查找(因为是环状结构)。

如图 1 所示:

一致性hash算法 java实现_信息的一致性

图 1 中 Key K 的哈希值在 A 与 B 之间,于是 K 就由节点B来处理。

另外具体机器映射时,还可以根据处理能力不同,将一个实体节点映射到多个虚拟节点。

经过一致性哈希算法散列之后,当有新的机器加入时,将只影响一台机器的存储情况,

例如新加入的节点H的散列在 B 与 C 之间,则原先由 C 处理的一些数据可能将移至 H 处理, 而其他所有节点的处理情况都将保持不变,因此表现出很好的单调性。

而如果删除一台机器,例如删除 C 节点,此时原来由 C 处理的数据将移至 D 节点,而其它节点的处理情况仍然不变。

而由于在机器节点散列和缓冲内容散列时都采用了同一种散列算法,因此也很好得降低了分散性和负载。

而通过引入虚拟节点的方式,也大大提高了平衡性。

缺点

一致性Hash算法的缺点在于节点的插入可能并不是均匀的,节点在hash后在环上并不一定分布均匀,导致了每个节点实际占据换上的区间大小不一定相近,因此节点分布不够均匀

改进

 

基于虚拟节点的一致性哈希

一致性hash算法 java实现_信息的一致性

一台物理服务器,虚拟成若干个虚拟节点,随机分布在环上,压力近似均衡分摊。如有三台物理服务器,每台物理服务器虚拟出150个虚拟节点,随机分配在Hash环上的150个位置上。最后可使三台物理服务器近似均摊压力。当增加一台服务器时,先虚拟150个节点,然后散落在哈希环上。

上图中的例子是有四台物理主机,每台物理主机虚拟成三个节点来保证节点近似均匀分布。

通过测试,每台物理服务的虚拟节点在120到200之间,均衡性更好。

缺点

该方法缺点在于存储虚拟节点信息需要额外空间。

重映射改进

在OpenStack的Swift组件中,使用了一种比较特殊的方法来解决分布不均的问题,改进了这些数据分布的算法,将环上的空间均匀的映射到一个线性空间,这样,就保证分布的均匀性。

一致性hash算法 java实现_信息的一致性

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/188909.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Linux下安装Redis

    Linux下安装Redis官网下载链接:https://redis.io/download1、选择Stable(5.0)下的Download5.0.0链接进行下载(stable是稳定版本,默认下载的是linux版本)2、下载完成之后,打开WinSCP,把我们下载好的Redis压缩包,上传到Linux的/mnt/文件目录下3、使用putty连接到我们的Li…

  • 论文DepthTrack: Unveiling the Power of RGBD Tracking阅读及代码讲解[通俗易懂]

    论文DepthTrack: Unveiling the Power of RGBD Tracking阅读及代码讲解[通俗易懂]最近终于有了一篇的顶会像样的RGBDtracking的论文了:ICCV2021:DepthTrack:UnveilingthePowerofRGBDTrackingGithub:https://github.com/xiaozai/DeT数据集简介这边看完就随手记录一下关键的部分:主要是创建了个大规模的RGBDtrackingbenchmark:DepthTrack(有数据集之后才能促进算法的研究),当然随之也搞了个baselinetracker—DeT,这也是现在搞d

  • 先学java再学python_java和python应该先学好哪个呢

    先学java再学python_java和python应该先学好哪个呢java和python应该先学好哪个呢发布时间:2020-07-3011:21:41来源:亿速云阅读:82作者:清晨不懂java和python应该先学好哪个呢?其实想解决这个问题也不难,下面让小编带着大家一起学习怎么去解决,希望大家阅读完这篇文章后大所收获。作为一名Java程序员,肯定会建议你先学Java,然后再学Python,但如果你问一个Python程序员,可能会得到一个完全相反…

  • 向量范数和矩阵范数的理解

    向量范数和矩阵范数的理解向量范数今天来聊一聊机器学习矩阵论的相关知识——范数(Norm)。在学习机器学习基础算法的推导过程中,可以看到很多地方都应用到了这个范数。范数属于矩阵论的知识范围,可见数学基础的重要性。机器学习的数学基础重点推荐——MIT的机器学习数学基础课如果只需要快速了解,请参考——矩阵范数计算完整的MIT数学基础课程笔记可以参考:MIT18.06线性代数笔记这是个非常棒的手动演算流程,本文也将编码进行验算。向量范数定义:一个向量空间V到实数空间的映射,不仅如此,还要满足喜爱额条件:∣∣x∣∣⩾

  • MySQL管理工具安装说明[通俗易懂]

    MySQL管理工具安装说明[通俗易懂]NavicatforMySQL10.0.11简体中文版(Linux版)navicat_for_mysql_10.0.11_cn_linux.tar.gz使用方法:1.打开终端:应用程序->系统工具(或附件)->终端,切换到root账户:$su-密码:(注意:输入root账户密码时,密码不会显示出来,也没有提示的特殊字符,直接输完密码按Enter键

  • 【零基础】MT4量化入门一:跑一个简单的boll

    【零基础】MT4量化入门一:跑一个简单的boll一、前言  今天开始研究MT4了,MT4是大大有名的外汇交易和量化软件,使用一种叫做MQL的语言来开发量化程序(跟C比较像)。因为是外国人做的,用的也大部分是外国人,使用起来不是很顺手,跟极星各有优劣吧。这里我就先逐步讲一下MT4的使用,然后再简单跑一个boll指标,最后汇总下使用心得。二、安装  1、下载MT4  不熟悉这东西,连安装都是个麻烦事儿。MT4官网好找一搜就有,下载链…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号