往期精选
Java 一致性 Hash 算法在负载均衡中的应用，强烈推荐！
技术文章第一时间送达！
作者：MarkLux http://marklux.cn/blog/90
一致性Hash是一种特殊的Hash算法，由于其均衡性、持久性的映射特点，被广泛的应用于负载均衡领域，如nginx和memcached都采用了一致性Hash来作为集群负载均衡的方案。
本文将介绍一致性Hash的基本思路，并讨论其在分布式缓存集群负载均衡中的应用。同时也会进行相应的代码测试来验证其算法特性，并给出和其他负载均衡方案的一些对比。
一致性Hash算法简介
可以看到，当节点被删除时，其余节点在环上的映射不会发生改变，只是原来打在对应节点上的Key现在会转移到顺时针方向的下一个节点上去。增加一个节点也是同样的，最终都只有少部分的Key发生了失效。不过发生节点变动后，整体系统的压力已经不是均衡的了，下文中提到的方法将会解决这个问题。
问题与优化
public class HashUtil {
/**
* 计算Hash值, 使用FNV1_32_HASH算法
* @param str
* @return
*/
public static int getHash(String str) {
final int p = 16777619;
int hash = (int)2166136261L;
for (int i = 0; i < str.length(); i++) {
hash =( hash ^ str.charAt(i) ) * 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;
}
}
public class ConsistentHashingWithoutVirtualNode {
/**
* 集群地址列表
*/
private static String[] groups = {
"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",
"192.168.0.3:111", "192.168.0.4:111"
};
/**
* 用于保存Hash环上的节点
*/
private static SortedMap<Integer, String> sortedMap = new TreeMap<>();
/**
* 初始化，将所有的服务器加入Hash环中
*/
static {
// 使用红黑树实现，插入效率比较差，但是查找效率极高
for (String group : groups) {
int hash = HashUtil.getHash(group);
System.out.println("[" + group + "] launched @ " + hash);
sortedMap.put(hash, group);
}
}
/**
* 计算对应的widget加载在哪个group上
*
* @param widgetKey
* @return
*/
private static String getServer(String widgetKey) {
int hash = HashUtil.getHash(widgetKey);
// 只取出所有大于该hash值的部分而不必遍历整个Tree
SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
if (subMap == null || subMap.isEmpty()) {
// hash值在最尾部，应该映射到第一个group上
return sortedMap.get(sortedMap.firstKey());
}
return subMap.get(subMap.firstKey());
}
public static void main(String[] args) {
// 生成随机数进行测试
Map<String, Integer> resMap = new HashMap<>();
for (int i = 0; i < 100000; i++) {
Integer widgetId = (int)(Math.random() * 10000);
String server = getServer(widgetId.toString());
if (resMap.containsKey(server)) {
resMap.put(server, resMap.get(server) + 1);
} else {
resMap.put(server, 1);
}
}
resMap.forEach(
(k, v) -> {
System.out.println("group " + k + ": " + v + "(" + v/1000.0D +"%)");
}
);
}
}
[192.168.0.1:111] launched @ 8518713
[192.168.0.2:111] launched @ 1361847097
[192.168.0.3:111] launched @ 1171828661
[192.168.0.4:111] launched @ 1764547046
group 192.168.0.2:111: 8572(8.572%)
group 192.168.0.1:111: 18693(18.693%)
group 192.168.0.4:111: 17764(17.764%)
group 192.168.0.3:111: 27870(27.87%)
group 192.168.0.0:111: 27101(27.101%)
public class ConsistentHashingWithVirtualNode {
/**
* 集群地址列表
*/
private static String[] groups = {
"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",
"192.168.0.3:111", "192.168.0.4:111"
};
/**
* 真实集群列表
*/
private static List<String> realGroups = new LinkedList<>();
/**
* 虚拟节点映射关系
*/
private static SortedMap<Integer, String> virtualNodes = new TreeMap<>();
private static final int VIRTUAL_NODE_NUM = 1000;
static {
// 先添加真实节点列表
realGroups.addAll(Arrays.asList(groups));
// 将虚拟节点映射到Hash环上
for (String realGroup: realGroups) {
for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {
String virtualNodeName = getVirtualNodeName(realGroup, i);
int hash = HashUtil.getHash(virtualNodeName);
System.out.println("[" + virtualNodeName + "] launched @ " + hash);
virtualNodes.put(hash, virtualNodeName);
}
}
}
private static String getVirtualNodeName(String realName, int num) {
return realName + "&&VN" + String.valueOf(num);
}
private static String getRealNodeName(String virtualName) {
return virtualName.split("&&")[0];
}
private static String getServer(String widgetKey) {
int hash = HashUtil.getHash(widgetKey);
// 只取出所有大于该hash值的部分而不必遍历整个Tree
SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
String virtualNodeName;
if (subMap == null || subMap.isEmpty()) {
// hash值在最尾部，应该映射到第一个group上
virtualNodeName = virtualNodes.get(virtualNodes.firstKey());
}else {
virtualNodeName = subMap.get(subMap.firstKey());
}
return getRealNodeName(virtualNodeName);
}
public static void main(String[] args) {
// 生成随机数进行测试
Map<String, Integer> resMap = new HashMap<>();
for (int i = 0; i < 100000; i++) {
Integer widgetId = i;
String group = getServer(widgetId.toString());
if (resMap.containsKey(group)) {
resMap.put(group, resMap.get(group) + 1);
} else {
resMap.put(group, 1);
}
}
resMap.forEach(
(k, v) -> {
System.out.println("group " + k + ": " + v + "(" + v/100000.0D +"%)");
}
);
}
}
group 192.168.0.2:111: 18354(18.354%)
group 192.168.0.1:111: 20062(20.062%)
group 192.168.0.4:111: 20749(20.749%)
group 192.168.0.3:111: 20116(20.116%)
group 192.168.0.0:111: 20719(20.719%)
private static void refreshHashCircle() {
// 当集群变动时，刷新hash环，其余的集群在hash环上的位置不会发生变动
virtualNodes.clear();
for (String realGroup: realGroups) {
for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {
String virtualNodeName = getVirtualNodeName(realGroup, i);
int hash = HashUtil.getHash(virtualNodeName);
System.out.println("[" + virtualNodeName + "] launched @ " + hash);
virtualNodes.put(hash, virtualNodeName);
}
}
}
private static void addGroup(String identifier) {
realGroups.add(identifier);
refreshHashCircle();
}
private static void removeGroup(String identifier) {
int i = 0;
for (String group:realGroups) {
if (group.equals(identifier)) {
realGroups.remove(i);
}
i++;
}
refreshHashCircle();
}
running the normal test.
group 192.168.0.2:111: 19144(19.144%)
group 192.168.0.1:111: 20244(20.244%)
group 192.168.0.4:111: 20923(20.923%)
group 192.168.0.3:111: 19811(19.811%)
group 192.168.0.0:111: 19878(19.878%)
removed a group, run test again.
group 192.168.0.2:111: 23409(23.409%)
group 192.168.0.1:111: 25628(25.628%)
group 192.168.0.4:111: 25583(25.583%)
group 192.168.0.0:111: 25380(25.38%)
[192.168.0.1:111-192.168.0.4:111] :5255
[192.168.0.1:111-192.168.0.3:111] :5090
[192.168.0.1:111-192.168.0.2:111] :5069
[192.168.0.1:111-192.168.0.0:111] :4938
running the normal test.
group 192.168.0.2:111: 18890(18.89%)
group 192.168.0.1:111: 20293(20.293%)
group 192.168.0.4:111: 21000(21.0%)
group 192.168.0.3:111: 19816(19.816%)
group 192.168.0.0:111: 20001(20.001%)
add a group, run test again.
group 192.168.0.2:111: 15524(15.524%)
group 192.168.0.7:111: 16928(16.928%)
group 192.168.0.1:111: 16888(16.888%)
group 192.168.0.4:111: 16965(16.965%)
group 192.168.0.3:111: 16768(16.768%)
group 192.168.0.0:111: 16927(16.927%)
[192.168.0.0:111-192.168.0.7:111] :3102
[192.168.0.4:111-192.168.0.7:111] :4060
[192.168.0.2:111-192.168.0.7:111] :3313
[192.168.0.1:111-192.168.0.7:111] :3292
[192.168.0.3:111-192.168.0.7:111] :3261
缓慢缩容，等到Hash环完全同步后再操作。可以通过监听退出集群的访问QPS来实现这一点，等到该集群几乎没有QPS时再将其撤下。- 手动删除，如果Hash环上对应的节点找不到了，就手动将其从Hash环上删除，然后重新进行调度，这个方式有一定的风险，对于网络抖动等异常情况兼容的不是很好。- 主动拉取和重试，当Hash环上节点失效时，主动从ZK上重新拉取集群状态来构建新Hash环，在一定次数内可以进行多次重试。
对比：HashSlot
了解了一致性Hash算法的特点后，我们也不难发现一些不尽人意的地方：
-
整个分布式缓存需要一个路由服务来做负载均衡，存在单点问题（如果路由服务挂了，整个缓存也就凉了）； -
Hash环上的节点非常多或者更新频繁时，查找性能会比较低下。
节点A 0－5460
节点B 5461－10922
节点C 10923－16383
节点A 1365-5460
节点B 6827-10922
节点C 12288-16383
节点D 0-1364,5461-6826,10923-12287
-
每个节点都保存有完整的HashSlot - 节点映射表，也就是说，每个节点都知道自己拥有哪些Slot，以及某个确定的Slot究竟对应着哪个节点。 -
无论向哪个节点发出寻找Key的请求，该节点都会通过CRC(Key) % 16384计算该Key究竟存在于哪个Slot，并将请求转发至该Slot所在的节点。
加入专业技术讨论企鹅群：248148860 ^^