[介绍]
一致性Hash(Consistent Hashing)被应用在很多地方,如LVS, 缓存(memcache, redis)等等.
[Ref 1],与 [Ref 2]已经给出了非常清楚明白的解释,我也是参考他们的。其他相关的文章更是多得汗牛充栋。
我写这个小短文(以我自己的语言重新组织)的目的是为了加深印象,以及稍加补充我觉得更加好理解的解释。
[现实问题]
问题:对key使用普通hash方法产生hashcode,以决定该key分配到那些缓存节点上。当减少(或者增加)节点数量时,将会倒置几乎所有的key都将重新分配到其他的节点上。因为hash的mod值从N,变成了N-1(or N+1). 譬如原来映射到节点 X, 则之后映射到X-1 (or X+1). 进而原有的缓存内容全部失效。 这将引起系统功能的剧烈变化。
[为什么一致性Hash]
一致性hash中,针对 key 和 缓存节点 都生成hash code(0 ~ 2^32-1)。将这些hash code映射到一个环上。这样,按照以顺时针方向,key距离那个节点比较近,就分配到哪个节点上。
这样,增加、减少节点则只对换上相邻的key产生影响。其他的key仍然还在原有节点上。
此图来自 [Ref 1]
[深入]
1. 平衡性
只是映射节点和key的话,可能有些节点load很大,其他确很小。引起所谓的,不平衡问题。为了缓解(注意:缓解,而非彻底解决)这个问题,引入虚拟节点的概念。每个物理节点,对应若干虚拟节点。使用虚拟节点的hashcode映射到环上,注意:同一物理节点的虚拟节点在换上不相邻。因为有了更多的“节点”在环上、而且物理节点都打散了,则key的分布必然会更平均一些。
[Ref 1]中也描述了
2. 判断该算法好坏的四个特性
- 平衡性 Balance "哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。" [Ref 2]
- 单调性 Monotonicity。 What:已缓存到NodeA中的内容,由于增加新节点NodeX,可能不得不映射到新的节点上。只能映射到原有NodeA或者新的NodeX中。而不能映射到其他Node上。How: 一致性Hash的圆环很简单的保证了这点。
- 分散性 Spread。 相同内容被cache到不同节点上、导致低存储效率的程度。BY:什么时候会曹成重复cache呢?谁给个实际的例子? [Ref 2]说“在分布式环境中,终端有可能看不到所有的缓冲,而是只能看到其中的一部分”, 为啥不能看到所有缓冲?
- 负载 Load - BY:无法理解[Ref 2]中说解释的Load。
[Ref 2]中给出了比较好的解释。但是需要认真读才行。读之前,请理解一致性hash。读的时候,请结合一致性hash。
Reference
2. 一致性hash算法简介
相关推荐
响的虚拟节点包括c31,c22,c11(顺时针查找到第个节点),这3个虚拟节点分别对应机器c3,c2,c1。即新加的台机器,同时影响到原有的3台机器。理想情况下
在分布式系统中,常常需要使用缓存,而且通常是集群,访问缓存和添加缓存都需要一个 hash 算法来寻找到合适的 Cache 节点。但,通常不是用取余hash,而是使用我们今天的主角—— 一致性 hash 算法。
一致性哈希 consistent-hash Implementing Consistent Hashing in Kotlin Java Kotlin实现的一致性哈希工具 简单示例 val a = HostPortPhysicalNode("A", "192.169.1.1", 8080) val b = HostPortPhysicalNode("B", ...
本篇文章对一致性hash算法(consistent hashing)的使用进行了详细的分析介绍。需要的朋友参考下
如果没有找到,则取整个环的第个节点。测试结果测试代码是整理的,主体法没有变分布平均性测试:测试随机成的众多key是否会平均分布到各个结点上测试结果如下:最上是参
#fly-archflylib创立的各种常见的架构技术内容列表cassandra-demo cassandra数据库的入门编程consistent-hash Java implementation of consistent-hashing基于java的一致性hash的实现一致性hash(consistent-hashing)...
跳跃一致哈希计算 甚至服务器之间的数据分布也非常重要:另一个重要方面是能够... 关于一致性哈希,使用的算法是谷歌的论文“A Fast, Minimal Memory, Consistent Hash Algorithm”中提出的Jump Consistent Hashing。
摘要视图订阅登录 | 注册算法艺术(8)1004760次第1338名90篇16篇4篇595条一致性hash算法 - consistent hashing - s
一致的散列这是一致性哈希的简单JavaScript实现。 有关一致性哈希的更多信息,请参见。安装使用以下命令安装依赖项: $ npm install 用法var ConsistentHashing = require ( './consistent_hashing' ) ;var node...
在《基于一致性hash算法(consistent hashing)的使用详解》一文中已经介绍了一致性hash的基本原理,本文将会对其具体实现细节进行描述,并用c++语言对一致性hash进行了简单的实现
本文实例讲述了PHP实现的一致性Hash算法。分享给大家供大家参考,具体如下: 一致性哈希算法是分布式系统中常用的算法,为...因此,引入了一致性Hash(Consistent Hashing)分布算法 把数据用hash函数(如md5,sha1
本文将会从实际应用场景出发,介绍一致性哈希算法(Consistent Hashing)及 其在分布式系统中的应用。首先本文会描述一个在日常开发中经常会遇到的问题 场景,借此介绍一致性哈希算法以及这个算法如何解决此问题;接...
php-consistent-hasha good php consistent hash helper,一个用php写的一致性hash 助手,主要用于解决internet中的热点(hot spot)问题特性平衡性(Balance):平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,...
一致性Hash算法 algorithm.cap algorithm.subset 给一个set打印出所有子集 jdk jdk 知识 jdk.autoboxing 自动装箱拆箱 jdk.longaccumulator 计数器 jdk.threadlocal DateFormatService: 如何线程安全的使用 ...
Consistent Hashing based Key-Value Memory Storage基于的分布式内存键值存储——CHKV。目前的定位就是作为 Cache,DataBase 的功能先不考虑。系统设计NameNode : 维护 DataNode节点 列表,用心跳检测 DataNode...
本文实例讲述了PHP实现的一致性哈希算法。分享给大家供大家参考,具体如下: <?php /** * Flexihash - A simple consistent hashing implementation for PHP. * * The MIT License * * Copyright (c) 2008 ...
RedisJumphash提供了非常快速的一致性哈希函数,以使用Redis构建分布式系统。 用法 JUMPHASH <key> 成功调用将返回给定密钥的存储桶。 它不需要任何存储。 如果您更改存储桶的数量,该算法将保证需要的重定位次数...
该存储库提供了常用分布式技术的演示,例如一致性哈希,分布式锁,分布式事务,领导者选举等。 技术 模块 地位 评论 一致性哈希 一致性哈希 完毕 分散式锁 分布式锁 正在做 分散式交易 分布式交易 完毕 共识算法 ...
环一致散列跳转一致哈希集合一致哈希磁悬浮一致性哈希 (第3.4节)粗略设计注意事项从与Karger等人成一直线的圆圈开始N个节点可以复制R次以改善分片分布。 复制的节点称为虚拟节点。 分片复制节点的散列在cicle上成...