hash
取模
一致性hash
目的是为了解决传统hash服务上下限导致的hash全都得全部映射好，只需要部分改变，比如k1推到s1,但s1没了，只会影响k1，而不会影响到其他
以及可以让同一类请求每次都映射到同一节点上，适用于 本地缓存之类的场景，提高缓存命中率
虚拟节点解决的问题：实例节点分布不均
虚拟节点越多，hash上的对象分配更均匀
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| package com.grace.gateway.core.algorithm;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHashing {
private final int virtualNodeNum;
private final SortedMap<Integer, String> hashCircle = new TreeMap<>();
public ConsistentHashing(List<String> nodes, int virtualNodeNum) {
this.virtualNodeNum = virtualNodeNum;
for (String node : nodes) {
addNode(node);
}
}
public void addNode(String node) {
for (int i = 0; i < virtualNodeNum; i++) {
String virtualNode = node + "&&VN" + i;
hashCircle.put(getHash(virtualNode), node);
}
}
public String getNode(String key) {
if (hashCircle.isEmpty()) {
return null;
}
int hash = getHash(key);
SortedMap<Integer, String> tailMap = hashCircle.tailMap(hash);
Integer nodeHash = tailMap.isEmpty() ? hashCircle.firstKey() : tailMap.firstKey();
return hashCircle.get(nodeHash);
}
private 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;
}
}
|
权重随机
1
2
3
4
5
6
7
8
9
10
11
| @Override
public ServiceInstance selectInstance(GatewayContext context, List<ServiceInstance> instances) {
int totalWeight = instances.stream().mapToInt(ServiceInstance::getWeight).sum();
if (totalWeight <= 0) return null;
int randomWeight = ThreadLocalRandom.current().nextInt(totalWeight);
for (ServiceInstance instance : instances) {
randomWeight -= instance.getWeight();
if (randomWeight < 0) return instance;
}
return null;
}
|