- 1、本文档共7页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
一致性哈希算法及java实一致性哈希算法及java实现一致性哈希算法及java实现一致性哈希算法及java实现
一致性哈希算法及java实现
应用场景
在做服务器负载均衡时候可供选择的负载均衡的算法有很多,包括: 轮循算法(Round Robin)、哈希算法(HASH)、最少连接算法(Least Connection)、响应速度算法(Response Time)、加权法(Weighted )等。其中哈希算法是最为常用的算法.
典型的应用场景是: 有N台服务器提供缓存服务,需要对服务器进行负载均衡,将请求平均分发到每台服务器上,每台机器负责1/N的服务。
常用的算法是对hash结果取余数 (hash() mod N):对机器编号从0到N-1,按照自定义的hash()算法,对每个请求的hash()值按N取模,得到余数i,然后将请求分发到编号为i的机器。但这 样的算法方法存在致命问题,如果某一台机器宕机,那么应该落在该机器的请求就无法得到正确的处理,这时需要将当掉的服务器从算法从去除,此时候会有(N- 1)/N的服务器的缓存数据需要重新进行计算;如果新增一台机器,会有N /(N+1)的服务器的缓存数据需要进行重新计算。对于系统而言,这通常是不可接受的颠簸(因为这意味着大量缓存的失效或者数据需要转移)。那么,如何设 计一个负载均衡策略,使得受到影响的请求尽可能的少呢?
在Memcached、Key-Value Store、Bittorrent DHT、LVS中都采用了Consistent Hashing算法,可以说Consistent Hashing 是分布式系统负载均衡的首选算法。
基本场景
比如你有 N 个 cache 服务器(后面简称 cache ),那么如何将一个对象 object 映射到 N 个 cache 上呢,你很可能会采用类似下面的通用方法计算 object 的 hash 值,然后均匀的映射到到 N 个 cache ;
hash(object)%N
一切都运行正常,再考虑如下的两种情况;
一个 cache 服务器 m down 掉了(在实际应用中必须要考虑这种情况),这样所有映射到 cache m 的对象都会失效,怎么办,需要把 cache m 从 cache 中移除,这时候 cache 是 N-1 台,映射公式变成了 hash(object)%(N-1) ;
由于访问加重,需要添加 cache ,这时候 cache 是 N+1 台,映射公式变成了 hash(object)%(N+1) ;
1 和 2 意味着什么?这意味着突然之间几乎所有的 cache 都失效了。对于服务器而言,这是一场灾难,洪水般的访问都会直接冲向后台服务器;再来考虑第三个问题,由于硬件能力越来越强,你可能想让后面添加的节点多做点活,显然上面的 hash 算法也做不到。
有什么方法可以改变这个状况呢,这就是consistent hashing。
?
hash 算法和单调性
Hash 算法的一个衡量指标是单调性( Monotonicity ),定义如下:
单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。
容易看到,上面的简单 hash 算法 hash(object)%N 难以满足单调性要求。
consistent hashing 算法的原理
consistent hashing 是一种 hash 算法,简单的说,在移除 / 添加一个 cache 时,它能够尽可能小的改变已存在 key 映射关系,尽可能的满足单调性的要求。
下面就来按照 5 个步骤简单讲讲 consistent hashing 算法的基本原理。
环形hash 空间
考虑通常的 hash 算法都是将 value 映射到一个 32 为的 key 值,也即是 0~2^32-1 次方的数值空间;我们可以将这个空间想象成一个首( 0 )尾( 2^32-1 )相接的圆环,如下面图 1 所示的那样。
图 1 环形 hash 空间
把对象映射到hash 空间
接下来考虑 4 个对象 object1~object4 ,通过 hash 函数计算出的 hash 值 key 在环上的分布如图 2 所示。
hash(object1) = key1;
… …
hash(object4) = key4;
图 2 4 个对象的 key 值分布
把cache 映射到hash 空间
Consistent hashing 的基本思想就是将对象和 cache 都映射到同一个 hash 数值空间中,并且使用相同的hash 算法。
假设当前有 A,B 和 C 共 3 台 cache ,那么其映射结果将如图 3 所示,他们在 hash 空间中,以对应的 hash值排列。
hash(cache A
您可能关注的文档
- 一、原核细胞和真核细胞的比一、原核细胞和真核细胞的比较一、原核细胞和真核细胞的比较一、原核细胞和真核细胞的比较.ppt
- 一、电子商务概述一、电子商概述务概述.ppt
- 一、自由基的基本知识一、自基的基本知识一、自由基的基本知识一、自由基的基本知识.ppt
- 一、均线战法研究一、均线战研究法研究.ppt
- 一、物业管理基本理论应用案一、物业管理基本理论应用案例一、物业管理基本理论应用案例一、物业管理基本理论应用案例.ppt
- 一;大宗现货的介绍一;大宗货的介绍现货的介绍.doc
- 一.安评应试串讲一.安评应串讲试串讲.ppt
- 一:厦门市房屋建筑和市政基设施工程施工许可证申请表一:厦门市房屋建筑和市政基础设施工程施工许可证申请表一:厦门市房屋建筑和市政基础设施工程施工许可证申请表一:厦门市房屋建筑和市政基础设施工程施工许可证申请表.doc
- 一、制定中考英语复习计划一制定中考英语复习计划一、制定中考英语复习计划一、制定中考英语复习计划.ppt
- 一、药品不良应监测概述及法一、药品不良应监测概述及法规一、药品不良应监测概述及法规一、药品不良应监测概述及法规.ppt
最近下载
- 医院物业工程部管理方案.pptx
- 院前急救题库复习测试卷附答案.doc
- 教学查房标准规范.doc
- 2020新亮剑高考物理总复习讲义:第十四单元选修3-4课时3含解析.docx
- 足球传切配合技巧:精准传切,协同进攻.pptx
- 2024年共青团知识自测题库及答案.pdf VIP
- 人教版(2024新教材)七年级上册数学第1-2章综合测试卷(含答案).docx
- 卫星通信网络设计与链路计算常江.pptx VIP
- 四川省 2022-2024 年职业教育人才培养和教育教学改革研究项目申报书《中高职贯通培养下一体化专业课程体系建设》.pdf
- 外研版高中英语选修六Module3InterpersonalRelationships:Friendship单元练习.docx
文档评论(0)