架构师训练营第五周作业

发布于: 5 小时前
架构师训练营第五周作业

  • 用你熟悉的编程语言实现一致性 hash 算法。

  • 编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。

对于远程分布式对象缓存而言,由于传统的数组取余的路由算法存在加减机器的时候大量缓存不命中的问题,此时大量请求会穿透到DB上面,可能造成缓存雪崩。而一致性hash路由算法正好解决了这种问题。

这里实现一致性hash的代码如下:

import java.util.List;
public interface ILoadBalance {
/**
* 从nodes里面选择一台node
* @param nodes
* @param context
* @return
*/
ServerNode select(List<ServerNode> nodes, Context context);
}

@FunctionalInterface
public interface HashFunc {
int hash(String key);
}

public class ServerNode implements Comparable<ServerNode> {
public final String ip;
public final int port;
public ServerNode(String ip, int port) {
this.ip = ip;
this.port = port;
}
@Override
public String toString() {
return "ServerNode [ip=" + ip + ", port=" + port + "]";
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((ip == null) ? 0 : ip.hashCode());
result = prime * result + port;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
ServerNode other = (ServerNode) obj;
if (ip == null) {
if (other.ip != null)
return false;
} else if (!ip.equals(other.ip))
return false;
if (port != other.port)
return false;
return true;
}
@Override
public int compareTo(ServerNode o) {
int cmp = ip.compareTo(o.ip);
if (cmp == 0) {
cmp = Integer.compare(port, o.port);
}
return cmp;
}
}

public class Context {
private String key;
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
}

import java.util.Collections;
import java.util.List;
import java.util.Map.Entry;
import java.util.Objects;
import java.util.TreeMap;
import java.util.concurrent.ConcurrentHashMap;
public class ConsistentHashLoadBalance implements ILoadBalance {
private final int virtualCount;
private final ConcurrentHashMap<List<ServerNode>, ConsistentHashSelector> table = new ConcurrentHashMap<>();
private final HashFunc hasher;
public ConsistentHashLoadBalance(HashFunc hasher, int virtualCount) {
this.hasher = Objects.requireNonNull(hasher);
this.virtualCount = virtualCount;
}
@Override
public ServerNode select(List<ServerNode> nodes, Context context) {
if (nodes == null || nodes.isEmpty()) {
return null;
}
Collections.sort(nodes);
ConsistentHashSelector selector = table.get(nodes);
if (selector == null) {
selector = new ConsistentHashSelector(nodes);
ConsistentHashSelector old = table.putIfAbsent(nodes, selector);
if (old != null) {
selector = old;
}
}
return selector.select(context);
}
class ConsistentHashSelector {
private final TreeMap<Integer, ServerNode> hashCycle = new TreeMap<>();
public ConsistentHashSelector(List<ServerNode> nodes) {
nodes = Objects.requireNonNull(nodes);
for (ServerNode node : nodes) {
for (int i = 0; i < virtualCount; i++) {
hashCycle.put(hasher.hash(getKey(node, i)), node);
}
}
}
private String getKey(ServerNode node, int index) {
return new StringBuilder(node.ip)
.append('_')
.append(node.port)
.append('_')
.append(index)
.toString();
}
public ServerNode select(Context context) {
int key = hasher.hash(context.getKey());
Entry<Integer, ServerNode> entry = hashCycle.ceilingEntry(key);
if (entry == null && (entry = hashCycle.firstEntry()) == null) {
return null;
}
return entry.getValue();
}
}
}

最后附上测试代码:

package cn.seedeed.test.loadbalance;
import java.util.ArrayList;
import java.util.List;
import java.util.UUID;
import java.util.function.Function;
import com.google.common.collect.HashMultiset;
import com.google.common.hash.Hashing;
public class Main {
private static void testConistentHash(String name, HashFunc func, int virtualNodeCount,
List<ServerNode> nodes, int reqCount, Function<Integer, String> keyFunc) {
System.out.println("name:" + name + ", virtualNodeCount:" + virtualNodeCount + ", nodeSize:" + nodes.size() + ", reqCount:" + reqCount);
ILoadBalance balance = new ConsistentHashLoadBalance(
func, /* hash函数 */
virtualNodeCount /* 虚拟结点个数 */);
Context ctx = new Context();
// ctx.setKey("hello2");
// System.out.println(balance.select(nodes, ctx));
HashMultiset<ServerNode> counter = HashMultiset.create(); //统计每个node的数量
for (int i = 0; i < reqCount; i++) {
ctx.setKey(keyFunc.apply(i));
counter.add(balance.select(nodes, ctx));
}
System.out.println(counter);
double avg = counter.size() / (double) nodes.size();
// System.out.println("avg:" + avg);
//计算标准差
long sum1 = counter.elementSet().stream()
.map(node -> counter.count(node))
.mapToLong(i -> i.longValue())
.map(i -> (long) ((i - avg) * (i - avg)))
.sum();
double result1 = sum1 / (double) counter.elementSet().size();
double standardDeviation = Math.sqrt(result1);
System.out.println("标准差:" + standardDeviation);
System.out.println("end =======================");
}
/**
* @param args
*/
public static void main(String[] args) {
ArrayList<ServerNode> nodes = new ArrayList<>();
nodes.add(new ServerNode("172.63.55.65", 102));
nodes.add(new ServerNode("172.63.55.67", 1314));
nodes.add(new ServerNode("172.32.58.1", 1020));
nodes.add(new ServerNode("192.35.47.5", 25000));
nodes.add(new ServerNode("10.3.55.123", 4444));
nodes.add(new ServerNode("9.105.2.33", 6378));
nodes.add(new ServerNode("192.168.33.7", 5555));
nodes.add(new ServerNode("255.168.2.3", 4444));
nodes.add(new ServerNode("1.2.50.2", 2158));
nodes.add(new ServerNode("1.3.50.56", 7786));
//生成key的方式是"hello" + i
testConistentHash("murmur3_32", key -> Hashing.murmur3_32().hashUnencodedChars(key).asInt(),
10, nodes, 100_0000, i -> "hello" + i);
testConistentHash("murmur3_32", key -> Hashing.murmur3_32().hashUnencodedChars(key).asInt(),
20, nodes, 100_0000, i -> "hello" + i);
testConistentHash("murmur3_32", key -> Hashing.murmur3_32().hashUnencodedChars(key).asInt(),
50, nodes, 100_0000, i -> "hello" + i);
testConistentHash("murmur3_32", key -> Hashing.murmur3_32().hashUnencodedChars(key).asInt(),
100, nodes, 100_0000, i -> "hello" + i);
testConistentHash("murmur3_32", key -> Hashing.murmur3_32().hashUnencodedChars(key).asInt(),
150, nodes, 100_0000, i -> "hello" + i);
testConistentHash("murmur3_32", key -> Hashing.murmur3_32().hashUnencodedChars(key).asInt(),
200, nodes, 100_0000, i -> "hello" + i);
testConistentHash("murmur3_32", key -> Hashing.murmur3_32().hashUnencodedChars(key).asInt(),
250, nodes, 100_0000, i -> "hello" + i);
testConistentHash("murmur3_32", key -> Hashing.murmur3_32().hashUnencodedChars(key).asInt(),
300, nodes, 100_0000, i -> "hello" + i);
testConistentHash("murmur3_32", key -> Hashing.murmur3_32().hashUnencodedChars(key).asInt(),
400, nodes, 100_0000, i -> "hello" + i);
testConistentHash("murmur3_32", key -> Hashing.murmur3_32().hashUnencodedChars(key).asInt(),
500, nodes, 100_0000, i -> "hello" + i);
//生成key的方式是uuid
testConistentHash("murmur3_32", key -> Hashing.murmur3_32().hashUnencodedChars(key).asInt(),
10, nodes, 100_0000, i -> UUID.randomUUID().toString());
testConistentHash("murmur3_32", key -> Hashing.murmur3_32().hashUnencodedChars(key).asInt(),
20, nodes, 100_0000, i -> UUID.randomUUID().toString());
testConistentHash("murmur3_32", key -> Hashing.murmur3_32().hashUnencodedChars(key).asInt(),
50, nodes, 100_0000, i -> UUID.randomUUID().toString());
testConistentHash("murmur3_32", key -> Hashing.murmur3_32().hashUnencodedChars(key).asInt(),
100, nodes, 100_0000, i -> UUID.randomUUID().toString());
testConistentHash("murmur3_32", key -> Hashing.murmur3_32().hashUnencodedChars(key).asInt(),
150, nodes, 100_0000, i -> UUID.randomUUID().toString());
testConistentHash("murmur3_32", key -> Hashing.murmur3_32().hashUnencodedChars(key).asInt(),
200, nodes, 100_0000, i -> UUID.randomUUID().toString());
testConistentHash("murmur3_32", key -> Hashing.murmur3_32().hashUnencodedChars(key).asInt(),
250, nodes, 100_0000, i -> UUID.randomUUID().toString());
testConistentHash("murmur3_32", key -> Hashing.murmur3_32().hashUnencodedChars(key).asInt(),
300, nodes, 100_0000, i -> UUID.randomUUID().toString());
testConistentHash("murmur3_32", key -> Hashing.murmur3_32().hashUnencodedChars(key).asInt(),
400, nodes, 100_0000, i -> UUID.randomUUID().toString());
testConistentHash("murmur3_32", key -> Hashing.murmur3_32().hashUnencodedChars(key).asInt(),
500, nodes, 100_0000, i -> UUID.randomUUID().toString());
//生成key的方式是"hello" + i
testConistentHash("md5", key -> Hashing.md5().hashUnencodedChars(key).asInt(),
10, nodes, 100_0000, i -> "hello" + i);
testConistentHash("md5", key -> Hashing.md5().hashUnencodedChars(key).asInt(),
20, nodes, 100_0000, i -> "hello" + i);
testConistentHash("md5", key -> Hashing.md5().hashUnencodedChars(key).asInt(),
50, nodes, 100_0000, i -> "hello" + i);
testConistentHash("md5", key -> Hashing.md5().hashUnencodedChars(key).asInt(),
100, nodes, 100_0000, i -> "hello" + i);
testConistentHash("md5", key -> Hashing.md5().hashUnencodedChars(key).asInt(),
150, nodes, 100_0000, i -> "hello" + i);
testConistentHash("md5", key -> Hashing.md5().hashUnencodedChars(key).asInt(),
200, nodes, 100_0000, i -> "hello" + i);
testConistentHash("md5", key -> Hashing.md5().hashUnencodedChars(key).asInt(),
250, nodes, 100_0000, i -> "hello" + i);
testConistentHash("md5", key -> Hashing.md5().hashUnencodedChars(key).asInt(),
300, nodes, 100_0000, i -> "hello" + i);
testConistentHash("md5", key -> Hashing.md5().hashUnencodedChars(key).asInt(),
400, nodes, 100_0000, i -> "hello" + i);
testConistentHash("md5", key -> Hashing.md5().hashUnencodedChars(key).asInt(),
500, nodes, 100_0000, i -> "hello" + i);
//生成key的方式是uuid
testConistentHash("md5", key -> Hashing.md5().hashUnencodedChars(key).asInt(),
10, nodes, 100_0000, i -> UUID.randomUUID().toString());
testConistentHash("md5", key -> Hashing.md5().hashUnencodedChars(key).asInt(),
20, nodes, 100_0000, i -> UUID.randomUUID().toString());
testConistentHash("md5", key -> Hashing.md5().hashUnencodedChars(key).asInt(),
50, nodes, 100_0000, i -> UUID.randomUUID().toString());
testConistentHash("md5", key -> Hashing.md5().hashUnencodedChars(key).asInt(),
100, nodes, 100_0000, i -> UUID.randomUUID().toString());
testConistentHash("md5", key -> Hashing.md5().hashUnencodedChars(key).asInt(),
150, nodes, 100_0000, i -> UUID.randomUUID().toString());
testConistentHash("md5", key -> Hashing.md5().hashUnencodedChars(key).asInt(),
200, nodes, 100_0000, i -> UUID.randomUUID().toString());
testConistentHash("md5", key -> Hashing.md5().hashUnencodedChars(key).asInt(),
250, nodes, 100_0000, i -> UUID.randomUUID().toString());
testConistentHash("md5", key -> Hashing.md5().hashUnencodedChars(key).asInt(),
300, nodes, 100_0000, i -> UUID.randomUUID().toString());
testConistentHash("md5", key -> Hashing.md5().hashUnencodedChars(key).asInt(),
400, nodes, 100_0000, i -> UUID.randomUUID().toString());
testConistentHash("md5", key -> Hashing.md5().hashUnencodedChars(key).asInt(),
500, nodes, 100_0000, i -> UUID.randomUUID().toString());
}
}

运行结果:

name:murmur3_32, virtualNodeCount:10, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 122920, ServerNode [ip=172.63.55.67, port=1314] x 100352, ServerNode [ip=172.32.58.1, port=1020] x 109287, ServerNode [ip=192.168.33.7, port=5555] x 122356, ServerNode [ip=10.3.55.123, port=4444] x 77120, ServerNode [ip=255.168.2.3, port=4444] x 139302, ServerNode [ip=192.35.47.5, port=25000] x 112002, ServerNode [ip=9.105.2.33, port=6378] x 63527, ServerNode [ip=172.63.55.65, port=102] x 95222, ServerNode [ip=1.3.50.56, port=7786] x 57912]
标准差:25393.28213130394
end =======================
name:murmur3_32, virtualNodeCount:20, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 113838, ServerNode [ip=172.32.58.1, port=1020] x 66357, ServerNode [ip=172.63.55.67, port=1314] x 81159, ServerNode [ip=192.168.33.7, port=5555] x 91610, ServerNode [ip=10.3.55.123, port=4444] x 87447, ServerNode [ip=255.168.2.3, port=4444] x 138422, ServerNode [ip=192.35.47.5, port=25000] x 106617, ServerNode [ip=9.105.2.33, port=6378] x 102951, ServerNode [ip=172.63.55.65, port=102] x 99429, ServerNode [ip=1.3.50.56, port=7786] x 112170]
标准差:18930.063386053414
end =======================
name:murmur3_32, virtualNodeCount:50, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 77492, ServerNode [ip=172.63.55.67, port=1314] x 108427, ServerNode [ip=172.32.58.1, port=1020] x 81249, ServerNode [ip=192.168.33.7, port=5555] x 94645, ServerNode [ip=10.3.55.123, port=4444] x 98114, ServerNode [ip=255.168.2.3, port=4444] x 89613, ServerNode [ip=192.35.47.5, port=25000] x 118926, ServerNode [ip=9.105.2.33, port=6378] x 98384, ServerNode [ip=172.63.55.65, port=102] x 116676, ServerNode [ip=1.3.50.56, port=7786] x 116474]
标准差:14069.945870542644
end =======================
name:murmur3_32, virtualNodeCount:100, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 107877, ServerNode [ip=172.32.58.1, port=1020] x 102759, ServerNode [ip=172.63.55.67, port=1314] x 102176, ServerNode [ip=192.168.33.7, port=5555] x 105831, ServerNode [ip=10.3.55.123, port=4444] x 108132, ServerNode [ip=255.168.2.3, port=4444] x 87249, ServerNode [ip=192.35.47.5, port=25000] x 100292, ServerNode [ip=9.105.2.33, port=6378] x 96962, ServerNode [ip=172.63.55.65, port=102] x 100174, ServerNode [ip=1.3.50.56, port=7786] x 88548]
标准差:6910.900520192719
end =======================
name:murmur3_32, virtualNodeCount:150, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 105951, ServerNode [ip=172.32.58.1, port=1020] x 99284, ServerNode [ip=172.63.55.67, port=1314] x 93073, ServerNode [ip=192.168.33.7, port=5555] x 100634, ServerNode [ip=10.3.55.123, port=4444] x 112487, ServerNode [ip=255.168.2.3, port=4444] x 88166, ServerNode [ip=192.35.47.5, port=25000] x 101102, ServerNode [ip=9.105.2.33, port=6378] x 97656, ServerNode [ip=172.63.55.65, port=102] x 108661, ServerNode [ip=1.3.50.56, port=7786] x 92986]
标准差:7149.817648024318
end =======================
name:murmur3_32, virtualNodeCount:200, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 102494, ServerNode [ip=172.63.55.67, port=1314] x 94881, ServerNode [ip=172.32.58.1, port=1020] x 98951, ServerNode [ip=192.168.33.7, port=5555] x 99801, ServerNode [ip=10.3.55.123, port=4444] x 120280, ServerNode [ip=255.168.2.3, port=4444] x 88647, ServerNode [ip=192.35.47.5, port=25000] x 100716, ServerNode [ip=9.105.2.33, port=6378] x 102247, ServerNode [ip=172.63.55.65, port=102] x 102323, ServerNode [ip=1.3.50.56, port=7786] x 89660]
标准差:8316.290050256785
end =======================
name:murmur3_32, virtualNodeCount:250, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 98569, ServerNode [ip=172.63.55.67, port=1314] x 95566, ServerNode [ip=172.32.58.1, port=1020] x 98840, ServerNode [ip=192.168.33.7, port=5555] x 110215, ServerNode [ip=10.3.55.123, port=4444] x 112091, ServerNode [ip=255.168.2.3, port=4444] x 87893, ServerNode [ip=192.35.47.5, port=25000] x 100138, ServerNode [ip=9.105.2.33, port=6378] x 98847, ServerNode [ip=172.63.55.65, port=102] x 101265, ServerNode [ip=1.3.50.56, port=7786] x 96576]
标准差:6594.271195515089
end =======================
name:murmur3_32, virtualNodeCount:300, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 93985, ServerNode [ip=172.63.55.67, port=1314] x 102560, ServerNode [ip=172.32.58.1, port=1020] x 100094, ServerNode [ip=192.168.33.7, port=5555] x 109331, ServerNode [ip=10.3.55.123, port=4444] x 106084, ServerNode [ip=255.168.2.3, port=4444] x 86159, ServerNode [ip=192.35.47.5, port=25000] x 98557, ServerNode [ip=9.105.2.33, port=6378] x 100633, ServerNode [ip=172.63.55.65, port=102] x 103694, ServerNode [ip=1.3.50.56, port=7786] x 98903]
标准差:6129.686305187241
end =======================
name:murmur3_32, virtualNodeCount:400, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 94729, ServerNode [ip=172.32.58.1, port=1020] x 104115, ServerNode [ip=172.63.55.67, port=1314] x 104192, ServerNode [ip=192.168.33.7, port=5555] x 99786, ServerNode [ip=10.3.55.123, port=4444] x 105131, ServerNode [ip=255.168.2.3, port=4444] x 92291, ServerNode [ip=192.35.47.5, port=25000] x 100051, ServerNode [ip=9.105.2.33, port=6378] x 101376, ServerNode [ip=172.63.55.65, port=102] x 102345, ServerNode [ip=1.3.50.56, port=7786] x 95984]
标准差:4142.637155243023
end =======================
name:murmur3_32, virtualNodeCount:500, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 97076, ServerNode [ip=172.32.58.1, port=1020] x 103843, ServerNode [ip=172.63.55.67, port=1314] x 106050, ServerNode [ip=192.168.33.7, port=5555] x 94170, ServerNode [ip=10.3.55.123, port=4444] x 105353, ServerNode [ip=255.168.2.3, port=4444] x 94399, ServerNode [ip=192.35.47.5, port=25000] x 96338, ServerNode [ip=9.105.2.33, port=6378] x 100609, ServerNode [ip=172.63.55.65, port=102] x 109292, ServerNode [ip=1.3.50.56, port=7786] x 92870]
标准差:5521.729113239801
end =======================
name:murmur3_32, virtualNodeCount:10, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 122904, ServerNode [ip=172.32.58.1, port=1020] x 108825, ServerNode [ip=172.63.55.67, port=1314] x 100494, ServerNode [ip=192.168.33.7, port=5555] x 122443, ServerNode [ip=10.3.55.123, port=4444] x 77032, ServerNode [ip=255.168.2.3, port=4444] x 138889, ServerNode [ip=192.35.47.5, port=25000] x 112158, ServerNode [ip=9.105.2.33, port=6378] x 63891, ServerNode [ip=172.63.55.65, port=102] x 95333, ServerNode [ip=1.3.50.56, port=7786] x 58031]
标准差:25260.926677380623
end =======================
name:murmur3_32, virtualNodeCount:20, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 113809, ServerNode [ip=172.63.55.67, port=1314] x 80817, ServerNode [ip=172.32.58.1, port=1020] x 66377, ServerNode [ip=192.168.33.7, port=5555] x 91531, ServerNode [ip=10.3.55.123, port=4444] x 87196, ServerNode [ip=255.168.2.3, port=4444] x 137679, ServerNode [ip=192.35.47.5, port=25000] x 107177, ServerNode [ip=9.105.2.33, port=6378] x 103498, ServerNode [ip=172.63.55.65, port=102] x 99314, ServerNode [ip=1.3.50.56, port=7786] x 112602]
标准差:18888.04344022959
end =======================
name:murmur3_32, virtualNodeCount:50, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 77431, ServerNode [ip=172.63.55.67, port=1314] x 108391, ServerNode [ip=172.32.58.1, port=1020] x 82008, ServerNode [ip=192.168.33.7, port=5555] x 94472, ServerNode [ip=10.3.55.123, port=4444] x 98311, ServerNode [ip=255.168.2.3, port=4444] x 89787, ServerNode [ip=192.35.47.5, port=25000] x 118975, ServerNode [ip=9.105.2.33, port=6378] x 97894, ServerNode [ip=172.63.55.65, port=102] x 116067, ServerNode [ip=1.3.50.56, port=7786] x 116664]
标准差:13933.846654818619
end =======================
name:murmur3_32, virtualNodeCount:100, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 107445, ServerNode [ip=172.32.58.1, port=1020] x 102781, ServerNode [ip=172.63.55.67, port=1314] x 102098, ServerNode [ip=192.168.33.7, port=5555] x 106246, ServerNode [ip=10.3.55.123, port=4444] x 108399, ServerNode [ip=255.168.2.3, port=4444] x 86831, ServerNode [ip=192.35.47.5, port=25000] x 100441, ServerNode [ip=9.105.2.33, port=6378] x 97324, ServerNode [ip=172.63.55.65, port=102] x 99904, ServerNode [ip=1.3.50.56, port=7786] x 88531]
标准差:6996.031031949473
end =======================
name:murmur3_32, virtualNodeCount:150, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 105514, ServerNode [ip=172.32.58.1, port=1020] x 99450, ServerNode [ip=172.63.55.67, port=1314] x 92612, ServerNode [ip=192.168.33.7, port=5555] x 100963, ServerNode [ip=10.3.55.123, port=4444] x 112637, ServerNode [ip=255.168.2.3, port=4444] x 87922, ServerNode [ip=192.35.47.5, port=25000] x 101100, ServerNode [ip=9.105.2.33, port=6378] x 97843, ServerNode [ip=172.63.55.65, port=102] x 108325, ServerNode [ip=1.3.50.56, port=7786] x 93634]
标准差:7123.781945006459
end =======================
name:murmur3_32, virtualNodeCount:200, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 102617, ServerNode [ip=172.32.58.1, port=1020] x 98622, ServerNode [ip=172.63.55.67, port=1314] x 94798, ServerNode [ip=192.168.33.7, port=5555] x 99568, ServerNode [ip=10.3.55.123, port=4444] x 119816, ServerNode [ip=255.168.2.3, port=4444] x 88900, ServerNode [ip=192.35.47.5, port=25000] x 100219, ServerNode [ip=9.105.2.33, port=6378] x 102878, ServerNode [ip=172.63.55.65, port=102] x 102008, ServerNode [ip=1.3.50.56, port=7786] x 90574]
标准差:8081.4060781524895
end =======================
name:murmur3_32, virtualNodeCount:250, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 98809, ServerNode [ip=172.63.55.67, port=1314] x 95344, ServerNode [ip=172.32.58.1, port=1020] x 98962, ServerNode [ip=192.168.33.7, port=5555] x 109658, ServerNode [ip=10.3.55.123, port=4444] x 112406, ServerNode [ip=255.168.2.3, port=4444] x 87937, ServerNode [ip=192.35.47.5, port=25000] x 100218, ServerNode [ip=9.105.2.33, port=6378] x 99368, ServerNode [ip=172.63.55.65, port=102] x 100620, ServerNode [ip=1.3.50.56, port=7786] x 96678]
标准差:6547.847447825889
end =======================
name:murmur3_32, virtualNodeCount:300, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 93838, ServerNode [ip=172.32.58.1, port=1020] x 99579, ServerNode [ip=172.63.55.67, port=1314] x 103861, ServerNode [ip=192.168.33.7, port=5555] x 108714, ServerNode [ip=10.3.55.123, port=4444] x 105667, ServerNode [ip=255.168.2.3, port=4444] x 86431, ServerNode [ip=192.35.47.5, port=25000] x 98726, ServerNode [ip=9.105.2.33, port=6378] x 101381, ServerNode [ip=172.63.55.65, port=102] x 103080, ServerNode [ip=1.3.50.56, port=7786] x 98723]
标准差:5998.905050090391
end =======================
name:murmur3_32, virtualNodeCount:400, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 95460, ServerNode [ip=172.63.55.67, port=1314] x 104444, ServerNode [ip=172.32.58.1, port=1020] x 103677, ServerNode [ip=192.168.33.7, port=5555] x 100388, ServerNode [ip=10.3.55.123, port=4444] x 104886, ServerNode [ip=255.168.2.3, port=4444] x 91819, ServerNode [ip=192.35.47.5, port=25000] x 100358, ServerNode [ip=9.105.2.33, port=6378] x 101016, ServerNode [ip=172.63.55.65, port=102] x 101307, ServerNode [ip=1.3.50.56, port=7786] x 96645]
标准差:3986.954476790524
end =======================
name:murmur3_32, virtualNodeCount:500, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 97605, ServerNode [ip=172.32.58.1, port=1020] x 103133, ServerNode [ip=172.63.55.67, port=1314] x 106012, ServerNode [ip=192.168.33.7, port=5555] x 94974, ServerNode [ip=10.3.55.123, port=4444] x 105630, ServerNode [ip=255.168.2.3, port=4444] x 94837, ServerNode [ip=192.35.47.5, port=25000] x 96147, ServerNode [ip=9.105.2.33, port=6378] x 100910, ServerNode [ip=172.63.55.65, port=102] x 108107, ServerNode [ip=1.3.50.56, port=7786] x 92645]
标准差:5203.875344394791
end =======================
name:md5, virtualNodeCount:10, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 84566, ServerNode [ip=172.63.55.67, port=1314] x 101487, ServerNode [ip=172.32.58.1, port=1020] x 81959, ServerNode [ip=192.168.33.7, port=5555] x 53214, ServerNode [ip=10.3.55.123, port=4444] x 127767, ServerNode [ip=255.168.2.3, port=4444] x 110376, ServerNode [ip=192.35.47.5, port=25000] x 108657, ServerNode [ip=9.105.2.33, port=6378] x 69904, ServerNode [ip=172.63.55.65, port=102] x 138590, ServerNode [ip=1.3.50.56, port=7786] x 123480]
标准差:25796.716907389593
end =======================
name:md5, virtualNodeCount:20, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 97701, ServerNode [ip=172.32.58.1, port=1020] x 113021, ServerNode [ip=172.63.55.67, port=1314] x 101059, ServerNode [ip=192.168.33.7, port=5555] x 81908, ServerNode [ip=10.3.55.123, port=4444] x 112059, ServerNode [ip=255.168.2.3, port=4444] x 125819, ServerNode [ip=192.35.47.5, port=25000] x 99739, ServerNode [ip=9.105.2.33, port=6378] x 90768, ServerNode [ip=172.63.55.65, port=102] x 101157, ServerNode [ip=1.3.50.56, port=7786] x 76769]
标准差:13934.238350193384
end =======================
name:md5, virtualNodeCount:50, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 98011, ServerNode [ip=172.32.58.1, port=1020] x 123310, ServerNode [ip=172.63.55.67, port=1314] x 93989, ServerNode [ip=192.168.33.7, port=5555] x 90348, ServerNode [ip=10.3.55.123, port=4444] x 108582, ServerNode [ip=255.168.2.3, port=4444] x 115114, ServerNode [ip=192.35.47.5, port=25000] x 94590, ServerNode [ip=9.105.2.33, port=6378] x 101794, ServerNode [ip=172.63.55.65, port=102] x 72731, ServerNode [ip=1.3.50.56, port=7786] x 101531]
标准差:13255.632855507127
end =======================
name:md5, virtualNodeCount:100, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 104455, ServerNode [ip=172.63.55.67, port=1314] x 111779, ServerNode [ip=172.32.58.1, port=1020] x 96020, ServerNode [ip=192.168.33.7, port=5555] x 107909, ServerNode [ip=10.3.55.123, port=4444] x 118410, ServerNode [ip=255.168.2.3, port=4444] x 87862, ServerNode [ip=192.35.47.5, port=25000] x 83800, ServerNode [ip=9.105.2.33, port=6378] x 88620, ServerNode [ip=172.63.55.65, port=102] x 104467, ServerNode [ip=1.3.50.56, port=7786] x 96678]
标准差:10705.969661828862
end =======================
name:md5, virtualNodeCount:150, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 105814, ServerNode [ip=172.63.55.67, port=1314] x 110311, ServerNode [ip=172.32.58.1, port=1020] x 100342, ServerNode [ip=192.168.33.7, port=5555] x 101016, ServerNode [ip=10.3.55.123, port=4444] x 105290, ServerNode [ip=255.168.2.3, port=4444] x 100815, ServerNode [ip=192.35.47.5, port=25000] x 92486, ServerNode [ip=9.105.2.33, port=6378] x 90317, ServerNode [ip=172.63.55.65, port=102] x 99870, ServerNode [ip=1.3.50.56, port=7786] x 93739]
标准差:5994.61898705831
end =======================
name:md5, virtualNodeCount:200, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 112870, ServerNode [ip=172.63.55.67, port=1314] x 106452, ServerNode [ip=172.32.58.1, port=1020] x 95621, ServerNode [ip=192.168.33.7, port=5555] x 96912, ServerNode [ip=10.3.55.123, port=4444] x 97533, ServerNode [ip=255.168.2.3, port=4444] x 97550, ServerNode [ip=192.35.47.5, port=25000] x 91488, ServerNode [ip=9.105.2.33, port=6378] x 94292, ServerNode [ip=172.63.55.65, port=102] x 108920, ServerNode [ip=1.3.50.56, port=7786] x 98362]
标准差:6598.106016123112
end =======================
name:md5, virtualNodeCount:250, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 102211, ServerNode [ip=172.63.55.67, port=1314] x 113031, ServerNode [ip=172.32.58.1, port=1020] x 94163, ServerNode [ip=192.168.33.7, port=5555] x 101781, ServerNode [ip=10.3.55.123, port=4444] x 98324, ServerNode [ip=255.168.2.3, port=4444] x 102322, ServerNode [ip=192.35.47.5, port=25000] x 96834, ServerNode [ip=9.105.2.33, port=6378] x 90439, ServerNode [ip=172.63.55.65, port=102] x 103883, ServerNode [ip=1.3.50.56, port=7786] x 97012]
标准差:5878.611927997969
end =======================
name:md5, virtualNodeCount:300, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 102741, ServerNode [ip=172.63.55.67, port=1314] x 109362, ServerNode [ip=172.32.58.1, port=1020] x 95888, ServerNode [ip=192.168.33.7, port=5555] x 102065, ServerNode [ip=10.3.55.123, port=4444] x 99700, ServerNode [ip=255.168.2.3, port=4444] x 95617, ServerNode [ip=192.35.47.5, port=25000] x 95540, ServerNode [ip=9.105.2.33, port=6378] x 97702, ServerNode [ip=172.63.55.65, port=102] x 99811, ServerNode [ip=1.3.50.56, port=7786] x 101574]
标准差:4041.2768279344587
end =======================
name:md5, virtualNodeCount:400, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 109244, ServerNode [ip=172.63.55.67, port=1314] x 108304, ServerNode [ip=172.32.58.1, port=1020] x 99617, ServerNode [ip=192.168.33.7, port=5555] x 99856, ServerNode [ip=10.3.55.123, port=4444] x 96138, ServerNode [ip=255.168.2.3, port=4444] x 101103, ServerNode [ip=192.35.47.5, port=25000] x 96131, ServerNode [ip=9.105.2.33, port=6378] x 96922, ServerNode [ip=172.63.55.65, port=102] x 90609, ServerNode [ip=1.3.50.56, port=7786] x 102076]
标准差:5363.309910866609
end =======================
name:md5, virtualNodeCount:500, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 102644, ServerNode [ip=172.63.55.67, port=1314] x 103235, ServerNode [ip=172.32.58.1, port=1020] x 96839, ServerNode [ip=192.168.33.7, port=5555] x 101953, ServerNode [ip=10.3.55.123, port=4444] x 97786, ServerNode [ip=255.168.2.3, port=4444] x 100868, ServerNode [ip=192.35.47.5, port=25000] x 102551, ServerNode [ip=9.105.2.33, port=6378] x 98149, ServerNode [ip=172.63.55.65, port=102] x 95787, ServerNode [ip=1.3.50.56, port=7786] x 100188]
标准差:2542.3576852992182
end =======================
name:md5, virtualNodeCount:10, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 84781, ServerNode [ip=172.32.58.1, port=1020] x 81782, ServerNode [ip=172.63.55.67, port=1314] x 101468, ServerNode [ip=192.168.33.7, port=5555] x 52783, ServerNode [ip=10.3.55.123, port=4444] x 127511, ServerNode [ip=255.168.2.3, port=4444] x 110705, ServerNode [ip=192.35.47.5, port=25000] x 108852, ServerNode [ip=9.105.2.33, port=6378] x 69793, ServerNode [ip=172.63.55.65, port=102] x 137985, ServerNode [ip=1.3.50.56, port=7786] x 124340]
标准差:25870.219021106102
end =======================
name:md5, virtualNodeCount:20, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 97489, ServerNode [ip=172.32.58.1, port=1020] x 113120, ServerNode [ip=172.63.55.67, port=1314] x 100784, ServerNode [ip=192.168.33.7, port=5555] x 82145, ServerNode [ip=10.3.55.123, port=4444] x 111977, ServerNode [ip=255.168.2.3, port=4444] x 126296, ServerNode [ip=192.35.47.5, port=25000] x 99948, ServerNode [ip=9.105.2.33, port=6378] x 90665, ServerNode [ip=172.63.55.65, port=102] x 100749, ServerNode [ip=1.3.50.56, port=7786] x 76827]
标准差:13990.987120285687
end =======================
name:md5, virtualNodeCount:50, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 97936, ServerNode [ip=172.63.55.67, port=1314] x 93309, ServerNode [ip=172.32.58.1, port=1020] x 123724, ServerNode [ip=192.168.33.7, port=5555] x 90016, ServerNode [ip=10.3.55.123, port=4444] x 108705, ServerNode [ip=255.168.2.3, port=4444] x 114791, ServerNode [ip=192.35.47.5, port=25000] x 94693, ServerNode [ip=9.105.2.33, port=6378] x 101925, ServerNode [ip=172.63.55.65, port=102] x 73110, ServerNode [ip=1.3.50.56, port=7786] x 101791]
标准差:13282.463513972098
end =======================
name:md5, virtualNodeCount:100, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 104582, ServerNode [ip=172.32.58.1, port=1020] x 95725, ServerNode [ip=172.63.55.67, port=1314] x 111939, ServerNode [ip=192.168.33.7, port=5555] x 106951, ServerNode [ip=10.3.55.123, port=4444] x 118002, ServerNode [ip=255.168.2.3, port=4444] x 88407, ServerNode [ip=192.35.47.5, port=25000] x 83863, ServerNode [ip=9.105.2.33, port=6378] x 88211, ServerNode [ip=172.63.55.65, port=102] x 104991, ServerNode [ip=1.3.50.56, port=7786] x 97329]
标准差:10583.117385723357
end =======================
name:md5, virtualNodeCount:150, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 105620, ServerNode [ip=172.63.55.67, port=1314] x 110732, ServerNode [ip=172.32.58.1, port=1020] x 100289, ServerNode [ip=192.168.33.7, port=5555] x 100515, ServerNode [ip=10.3.55.123, port=4444] x 105301, ServerNode [ip=255.168.2.3, port=4444] x 100557, ServerNode [ip=192.35.47.5, port=25000] x 92988, ServerNode [ip=9.105.2.33, port=6378] x 90628, ServerNode [ip=172.63.55.65, port=102] x 99966, ServerNode [ip=1.3.50.56, port=7786] x 93404]
标准差:5966.830984702014
end =======================
name:md5, virtualNodeCount:200, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 113024, ServerNode [ip=172.63.55.67, port=1314] x 106525, ServerNode [ip=172.32.58.1, port=1020] x 95366, ServerNode [ip=192.168.33.7, port=5555] x 96491, ServerNode [ip=10.3.55.123, port=4444] x 97345, ServerNode [ip=255.168.2.3, port=4444] x 98034, ServerNode [ip=192.35.47.5, port=25000] x 91294, ServerNode [ip=9.105.2.33, port=6378] x 94409, ServerNode [ip=172.63.55.65, port=102] x 109511, ServerNode [ip=1.3.50.56, port=7786] x 98001]
标准差:6770.600106342125
end =======================
name:md5, virtualNodeCount:250, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 102431, ServerNode [ip=172.63.55.67, port=1314] x 113168, ServerNode [ip=172.32.58.1, port=1020] x 93831, ServerNode [ip=192.168.33.7, port=5555] x 101111, ServerNode [ip=10.3.55.123, port=4444] x 98115, ServerNode [ip=255.168.2.3, port=4444] x 102313, ServerNode [ip=192.35.47.5, port=25000] x 96569, ServerNode [ip=9.105.2.33, port=6378] x 91351, ServerNode [ip=172.63.55.65, port=102] x 104295, ServerNode [ip=1.3.50.56, port=7786] x 96816]
标准差:5853.733031152002
end =======================
name:md5, virtualNodeCount:300, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 103197, ServerNode [ip=172.32.58.1, port=1020] x 95802, ServerNode [ip=172.63.55.67, port=1314] x 108990, ServerNode [ip=192.168.33.7, port=5555] x 101749, ServerNode [ip=10.3.55.123, port=4444] x 99657, ServerNode [ip=255.168.2.3, port=4444] x 95965, ServerNode [ip=192.35.47.5, port=25000] x 95811, ServerNode [ip=9.105.2.33, port=6378] x 97685, ServerNode [ip=172.63.55.65, port=102] x 100021, ServerNode [ip=1.3.50.56, port=7786] x 101123]
标准差:3902.4415946942754
end =======================
name:md5, virtualNodeCount:400, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 109150, ServerNode [ip=172.63.55.67, port=1314] x 107983, ServerNode [ip=172.32.58.1, port=1020] x 99147, ServerNode [ip=192.168.33.7, port=5555] x 99983, ServerNode [ip=10.3.55.123, port=4444] x 96594, ServerNode [ip=255.168.2.3, port=4444] x 101437, ServerNode [ip=192.35.47.5, port=25000] x 95702, ServerNode [ip=9.105.2.33, port=6378] x 96656, ServerNode [ip=172.63.55.65, port=102] x 91364, ServerNode [ip=1.3.50.56, port=7786] x 101984]
标准差:5196.310075428524
end =======================
name:md5, virtualNodeCount:500, nodeSize:10, reqCount:1000000
[ServerNode [ip=1.2.50.2, port=2158] x 102264, ServerNode [ip=172.32.58.1, port=1020] x 96476, ServerNode [ip=172.63.55.67, port=1314] x 103701, ServerNode [ip=192.168.33.7, port=5555] x 102010, ServerNode [ip=10.3.55.123, port=4444] x 97660, ServerNode [ip=255.168.2.3, port=4444] x 100915, ServerNode [ip=192.35.47.5, port=25000] x 102185, ServerNode [ip=9.105.2.33, port=6378] x 98118, ServerNode [ip=172.63.55.65, port=102] x 96265, ServerNode [ip=1.3.50.56, port=7786] x 100406]
标准差:2530.332152109679
end =======================

测试发现:

使用了md5和murmur3_32两种算法作为一致性hash的key的hash算法,md5似乎均匀性比murmur3_32稍好一点,但是murmur3_32的性能又明显高于md5。对于murmur3_32算法,虚拟节点的个数大概是400左右达到均匀性较好(标准差较小)的情况。而对于md5算法,则是在虚拟节点在150左右的时候达到均匀性较好(标准差较小)的情况。

用户头像

锦澄

关注

还未添加个人签名 2019.12.29 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第五周作业