架构师训练营第五周作业

 关注
发布于: 2020 年 07 月 05 日
﻿
用你熟悉的编程语言实现一致性 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左右的时候达到均匀性较好（标准差较小）的情况。
发布于: 2020 年 07 月 05 日阅读数: 36
锦澄

 关注
还未添加个人签名 2019.12.29 加入
还未添加个人简介
发布
暂无评论