在web架构中,分布式是个常见的架构设计。尤其是大家比较熟悉的Memcached,或者其他cache产品常常被设计成分布式集群。分布式往往采用hash(key)%n 的方式,但这种算法比较简单,便于实现和理解。但弊端是不能动态增删节点。比较合理的方法改用一致性哈希(consistent hashing)分布。一致性哈希,简单的说在移除 / 添加一个 cache 时,它能够尽可能小的改变已存在 key 映射关系,尽可能的满足单调性的要求。原理不再赘述,google和度娘都能得到答案。重点说一下最常见的实现方式。
Java中采用md5散列的方式,计算hash值,这样基本上能保证key散列出啦的hash不会重复。
private static long md5HashingAlg(String key) { MessageDigest md5 = MD5.get(); md5.reset(); md5.update(key.getBytes()); byte[] bKey = md5.digest(); long res = ((long) (bKey[3] & 0xFF) << 24) | ((long) (bKey[2] & 0xFF) << 16) | ((long) (bKey[1] & 0xFF) << 8)| (long) (bKey[0] & 0xFF); return res; }
在对server节点初始化的时候,为了避免节点过少数据分布不均匀,都会初始化一些虚拟节点。具体方法上面计算hash值的方式类同,一把采用根据权重虚拟出来一些key,具体不过多介绍。
一致性哈希算法中,把哈希值想象成一个环状。有关一致性哈希算法,介绍里面说0~2^32-1的数据,不要误以为哈希环要保存2^32个数据。他只是说,哈希环存的key的哈希值范围是0~2^32-1,并不是key的哈希值要覆盖0~2^32-1所有数据。
既要保存hash值,又要保存对应的节点地址,貌似最简单的就是map,在Java中没有什么map可以满足是个环状。那就找一个排序的,0开头,2^32-1做尾。查找时查到尾没有结果,再返回头找这样可以理解为是个环状了。
在初始化的时候,把节点的hash和节点地址保存在TreeMap里,client查找时,根据key的hash值去treeMap得到自己应该查询的节点,往下查找比自己hash值大的,如果有则得到结果返回。如果没有,则回到treeMap的头,取第一个返回结果。
如图中所示:根据key计算出hash,去treeMap查找比key哈希大的那部分,取出第一个值就是结果。如果没有别key哈希大的部分,则取treeMap的第一个值。
代码的实现:
private final Long findPointFor(Long hv) { SortedMap<Long, String> tmap = this.consistentBuckets.tailMap(hv); return (tmap.isEmpty()) ? this.consistentBuckets.firstKey() : tmap.firstKey(); }
相关推荐
Java Kotlin实现的一致性哈希工具 简单示例 val a = HostPortPhysicalNode("A", "192.169.1.1", 8080) val b = HostPortPhysicalNode("B", "192.169.1.2", 8080) val c = HostPortPhysicalNode("C", "192.168.1.13",...
在分布式系统中,常常需要使用缓存,而且通常是集群,访问缓存和添加缓存都需要一个 hash 算法来寻找到合适的 Cache 节点。但,通常不是用取余hash,而是使用我们今天的主角—— 一致性 hash 算法。
包 jch 提供了 Go 中 Jump Consistent Hash 一致性哈希算法的实现。 一致性哈希旨在最小化存储桶数量变化时的哈希变化,对于数据分片特别有用。 有关一致性哈希的更多信息,请访问 。 Jump Consistent Hash 由 ...
lua 一致性哈希基于 yaoweibin 的一致性哈希分支( )在 lua 中重新实现一致性哈希用法 local chash = require " chash "chash. add_upstream ( " 192.168.0.251 " )chash. add_upstream ( " 192.168.0.252 " )chash...
如果没有找到,则取整个环的第个节点。测试结果测试代码是整理的,主体法没有变分布平均性测试:测试随机成的众多key是否会平均分布到各个结点上测试结果如下:最上是参
Nginx:一致性哈希(第三方模块ngx_http_consistent_hash):ngx_http_consistent_hash-master.zip
本文将会从实际应用场景出发,介绍一致性哈希算法(Consistent Hashing)及 其在分布式系统中的应用。首先本文会描述一个在日常开发中经常会遇到的问题 场景,借此介绍一致性哈希算法以及这个算法如何解决此问题;接...
#fly-archflylib创立的各种常见的架构技术内容列表cassandra-demo cassandra数据库的入门编程consistent-hash Java implementation of consistent-hashing基于java的一致性hash的实现一致性hash(consistent-hashing)...
一致性哈希 这是环的一种无依赖Java的实现。 使用字符串作为哈希键,并使用PJW哈希变体哈希。 该实现非常快,并且具有良好的密钥分发。 var ConsistentHash = require('consistent-hash') var hr = new ...
Node.JS 的一致性哈希模块 安装 npm install consistent 用法 var consistent = require ( 'consistent' ) ; var ring = consistent ( { members : [ "member1" , "member2" , { key : "member3" , weight :...
hash_ring 当操作分布式服务器时,“一致性哈希环”是一个有用的数据结构。 该库是基于出色的实现的Consistent Hash Ring的实现。安装将此添加到应用程序的shard.yml : dependencies : hash_ring : github : ...
一致的散列这是一致性哈希的简单JavaScript实现。 有关一致性哈希的更多信息,请参见。安装使用以下命令安装依赖项: $ npm install 用法var ConsistentHashing = require ( './consistent_hashing' ) ;var node...
php-consistent-hasha good php consistent hash helper,一个用php写的一致性hash 助手,主要用于解决internet中的热点(hot spot)问题特性平衡性(Balance):平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,...
跳转一致哈希 John Lamping和Eric Veach的跳转一致性哈希算法[1]的实现。 [1] 用法import jump "github.com/lithammer/go-jump-consistent-hash"func main () { h := jump . Hash ( 256 , 1024 ) // h = 520} 包括...
在《基于一致性hash算法(consistent hashing)的使用详解》一文中已经介绍了一致性hash的基本原理,本文将会对其具体实现细节进行描述,并用c++语言对一致性hash进行了简单的实现
一致性哈希算法是分布式系统中常用的算法,为什么要用这个算法? 比如:一个分布式存储系统,要将数据存储到具体的节点(服务器)上, 在服务器数量不发生改变的情况下,如果采用普通的hash再对服务器总数量取模的...
环一致散列跳转一致哈希集合一致哈希磁悬浮一致性哈希 (第3.4节)粗略设计注意事项从与Karger等人成一直线的圆圈开始N个节点可以复制R次以改善分片分布。 复制的节点称为虚拟节点。 分片复制节点的散列在cicle上成...
跳跃一致哈希计算 甚至服务器之间的数据分布也非常重要:另一个重要方面是能够... 关于一致性哈希,使用的算法是谷歌的论文“A Fast, Minimal Memory, Consistent Hash Algorithm”中提出的Jump Consistent Hashing。
本文实例讲述了PHP实现的一致性哈希算法。分享给大家供大家参考,具体如下: <?php /** * Flexihash - A simple consistent hashing implementation for PHP. * * The MIT License * * Copyright (c) 2008 ...
Consistent Hashing based Key-Value Memory Storage基于的分布式内存键值存储——CHKV。目前的定位就是作为 Cache,DataBase 的功能先不考虑。系统设计NameNode : 维护 DataNode节点 列表,用心跳检测 DataNode...