写点什么

一致性 Hash

发布于: 2020 年 07 月 08 日
一致性Hash

算法简述

算法关键

  1. 有一个哈希环,一共有2^23个数字

  2. 通过hash(value)%2^23 = hashKey来定位环上的位置

  3. 数据的key定位到环上的位置没有节点,就顺时针找到下一个节点

  4. 使用虚拟节点来矫正一致性hash的偏斜,虚拟节点可以通过给物理节点增加编号来实现

代码实现

package cn.qiangjun.hash;
import lombok.Data;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;
/**
* @Author: 梅子黄时雨 qiangjun@aliyun.com
* @Date: 2020/7/7 17:33
*/
@Data
public class ConsistentHash {
/**
* hash环
*/
private TreeMap<Long, Node> hashCricle = new TreeMap<>();
/**
* 每个节点缓存的数量
*/
private ConcurrentHashMap<String, AtomicInteger> countEveryNode = new ConcurrentHashMap<>(10);
/**
* 虚拟节点
*/
private int virtualCopies = 32 * 10000;
/**
* 添加一个节点
* 创建虚拟节点
*
* @param node
*/
public void addNode(Node node) {
String machineIp = node.getMachineIp();
for (int i = 0; i < virtualCopies; i++) {
long key = FNVHash(machineIp +"#"+i);
hashCricle.put(key, node);
}
countEveryNode.put(node.getMachineIp(), new AtomicInteger(0));
return;
}
/**
* 批量新增节点
*
* @param nodes
*/
public void addNodes(Node... nodes) {
for (int i = 0; i < nodes.length; i++) {
addNode(nodes[i]);
}
}
/**
* 删除一个节点
*
* @param node
*/
public void remove(Node node) {
String machineIp = node.getMachineIp();
for (int i = 0; i < virtualCopies; i++) {
long key = FNVHash(machineIp +"#"+i);
hashCircle.remove(key);
}
countEveryNode.remove(node.getMachineIp());
}
/**
* 获取节点
*
* @param value 缓存对象
*/
public Node getNode(String value) {
long key = FNVHash(value);
SortedMap<Long, Node> tailMap = hashCircle.tailMap(key);
long hashKey = tailMap.isEmpty() ? hashCircle.firstKey() : tailMap.firstKey();
Node node = hashCircle.get(hashKey);
String machineIp = node.getMachineIp();
countEveryNode.get(machineIp).incrementAndGet();
return node;
}
// 32位的 Fowler-Noll-Vo 哈希算法
// 比使用java自带的Object.hashCode()散列的均匀
private static Long FNVHash(String key) {
final int p = 16777619;
Long hash = 2166136261L;
for (int idx = 0, num = key.length(); idx < num; ++idx) {
hash = (hash ^ key.charAt(idx)) * p;
}
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
if (hash < 0) {
hash = Math.abs(hash);
}
return hash;
}
}

分析

一致性Hash还可以分为带虚拟节点和待有限负载的一致性Hash,他们的区别可见下表。

从上表看来,带虚拟节点的HASH最优,其中有两个点很重要:

  1. 虚拟节点要多

  2. hash算法要足够均匀。

计算分布数量的标准差

我们通过改变虚拟节点的个数来比较一致性HASH和带虚拟节点的HASH的分布数量的标准差。

一致性Hash

带虚拟节点的一致性Hash

标准差越小,数据分布越均匀。



发布于: 2020 年 07 月 08 日阅读数: 62
用户头像

还未添加个人签名 2017.10.30 加入

半壁山房待明月,一盏清茗酬知音。

评论

发布
暂无评论
一致性Hash