Implementation
For completeness here is a simple implementation in Java. In order for consistent hashing to be effective it is important to have a hash function thatmixes well. Most implementations ofObject
'shashCode
donot mix well - for example, they typically produce a restricted number of small integer values - so we have aHashFunction
interface to allow a custom hash function to be used. MD5 hashes are recommended here.
import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHash<T> {
private final HashFunction hashFunction;
private final int numberOfReplicas;
private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();
public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,
Collection<T> nodes) {
this.hashFunction = hashFunction;
this.numberOfReplicas = numberOfReplicas;
for (T node : nodes) {
add(node);
}
}
public void add(T node) {
for (int i = 0; i < numberOfReplicas; i++) {
circle.put(hashFunction.hash(node.toString() + i), node);
}
}
public void remove(T node) {
for (int i = 0; i < numberOfReplicas; i++) {
circle.remove(hashFunction.hash(node.toString() + i));
}
}
public T get(Object key) {
if (circle.isEmpty()) {
return null;
}
int hash = hashFunction.hash(key);
if (!circle.containsKey(hash)) {
SortedMap<Integer, T> tailMap = circle.tailMap(hash);
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
return circle.get(hash);//这一行可以有很大优化,毕竟在万个以内的整数中查找一个最接近的大于等于hash的算法是非常简单的,而不必用treemap的实现。
}
}
numberOfReplicas的经验值在100-200之间,这就是一个物理 节点对应多少个虚拟节点,如果我们把环形拉直,其实就是每个
节点在数组中的位置,物理节点很少,比如10个物理节点,如果平均分布在Integer.MIN-Integer.MAX中,那么每个节点间的区间
大约有2^29这么大,假如某一时间段的一些key的hash正好在这一范围,那么它们就被聚集到某一台物理节点上。在采用了虚拟节点
后,每个物理节点对应的虚拟节点和其它物理节点对应的虚拟节点是平均交叉分布的,极大地减少了节点区间带来的分布聚集。
以下是一个简单实现的测试:
分享到:
相关推荐
Consistent Hashing and Random Trees
python库。 资源全名:ConsistentHashing-0.1.9.tar.gz
libconhash is a consistent hashing libraray, which can be compiled both on Windows and Linux platform. High performance, easy to use, and easy to scale according to node's processing capacity.
第一次提出一致性哈希环的论文,说的是比较好的,稍微有点英语基础的,应该都可以看懂。在分布式,缓存流行的今天,确实是不错的充电利器。
跳跃一致哈希计算 甚至服务器之间的数据分布也非常重要:另一个重要方面是能够... 关于一致性哈希,使用的算法是谷歌的论文“A Fast, Minimal Memory, Consistent Hash Algorithm”中提出的Jump Consistent Hashing。
在分布式系统中,常常需要使用缓存,而且通常是集群,访问缓存和添加缓存都需要一个 hash 算法来寻找到合适的 Cache 节点。但,通常不是用取余hash,而是使用我们今天的主角—— 一致性 hash 算法。
Consistent-Hashing Consistent Hashing 一致哈希
技术文档分享,免费获取请私信博主。
响的虚拟节点包括c31,c22,c11(顺时针查找到第个节点),这3个虚拟节点分别对应机器c3,c2,c1。即新加的台机器,同时影响到原有的3台机器。理想情况下
Implementing Consistent Hashing in Kotlin Java Kotlin实现的一致性哈希工具 简单示例 val a = HostPortPhysicalNode("A", "192.169.1.1", 8080) val b = HostPortPhysicalNode("B", "192.169.1.2", 8080) val c =...
本篇文章对一致性hash算法(consistent hashing)的使用进行了详细的分析介绍。需要的朋友参考下
如果没有找到,则取整个环的第个节点。测试结果测试代码是整理的,主体法没有变分布平均性测试:测试随机成的众多key是否会平均分布到各个结点上测试结果如下:最上是参
开源项目-lafikl-consistent.zip,lafikl/consistent: a package for Consistent Hashing and Consistent Hashing With Bounded Loads.
安装使用以下命令安装依赖项: $ npm install 用法var ConsistentHashing = require ( './consistent_hashing' ) ;var nodeNames = [ 'node1' , 'node2' , 'node3' , 'node4' , 'node5' , 'node6' ] ;var replica...
Consistent-hashing: Go中的散列环实现
一致性哈希,consistent hashing。 算法入门必备 清晰版本,非扫描。
consistent hashing算法的c实现版本 数据结构使用红黑树。
Ringo is an experimental, distributed, replicating key-value store based on consistent hashing and immutable data. Unlike many general-purpose databases, Ringo is designed for a specific use case: For...
Next, you will learn about data partitioning and consistent hashing in Cassandra through examples and also see high availability features and replication in Cassandra. Finally, you'll learn about ...