架构师训练营作业 -- Week 5

关注
发布于: 2020 年 07 月 08 日
﻿
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
﻿
一致性哈希算法的几个关键点：
环
此算法将用TreeMap模拟“环”，因为“环”的实质是一个有序的键值存储结构。
// the big ring
private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();
虚拟节点
为了使节点尽量分散，我们需要引入虚拟节点。虚拟节点将在创建每个真实节点是一并创建。
// the number of virtual nodes
private final int numberOfReplicas;
// create node
public void add(T node) {
  // create virtual nodes
  for (int i = 0; i < numberOfReplicas; i++) {
    circle.put(hash(node.toString() + i), node);
  }
}
﻿
哈希算法
Java自带的哈希算法有两大缺点：
a. 不够分散
b. 无法保证在分布式计算平台上哈希值的一致性
为了弥补这两个缺点，需要引入Murmur Hash算法。
private static int hash(String s) {
		HashFunction hashFunction = Hashing.murmur3_128(13);
		return Math.abs(hashFunction.hashString(s, Charsets.UTF_8).hashCode());
	}
﻿
以下是完整代码演示，包含标准差测试。
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;
import org.apache.commons.lang3.RandomStringUtils;
import com.google.common.base.Charsets;
import com.google.common.hash.HashFunction;
import com.google.common.hash.Hashing;
public class ConsistentHashingImpl<T> {
	// the number of virtual nodes
	private final int numberOfReplicas;
	// the big ring
	private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();
	private List<Integer> keyHashes = new ArrayList<>();
	// Attention: the T node object must overwrite the toString method to ensure each node name is consistent.
	public ConsistentHashingImpl(int numberOfReplicas, Collection<T> nodes) {
		this.numberOfReplicas = numberOfReplicas;
		for (T node : nodes) {
			add(node);
		}
	}
	public void add(T node) {
		for (int i = 0; i < numberOfReplicas; i++) {
			int hashCode = hash(node.toString() + i);
			circle.put(hashCode, node);
		}
	}
	public void remove(T node) {
		for (int i = 0; i < numberOfReplicas; i++) {
			circle.remove(hash(node.toString() + i));
		}
	}
	public T get(Object key) {
		if (circle.isEmpty()) {
			return null;
		}
		int hash = hash(String.valueOf(key));
		keyHashes.add(hash);
//		System.out.println("hash(" + key + ") = " + hash);
		if (!circle.containsKey(hash)) {
			SortedMap<Integer, T> tailMap = circle.tailMap(hash);
			hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
		}
		return circle.get(hash);
	}
	
	private static int hash(String s) {
		HashFunction hashFunction = Hashing.murmur3_128(13);
		return hashFunction.hashString(s, Charsets.UTF_8).hashCode();
	}
	
	public static void main(String[] args) {
		int replicas = 1000;
		int numOfNodes = 10;
		if(args.length >= 2) {
			numOfNodes = Integer.valueOf(args[0]);
			replicas = Integer.valueOf(args[1]);
		}
		List<String> servers = new ArrayList<>();
		for (int i = 0; i < numOfNodes; i++) {
			servers.add(RandomStringUtils.randomAlphabetic(8));
		}
		// create a clusters 
		ConsistentHashingImpl<String> cHash = new ConsistentHashingImpl<String>(replicas, servers);
		System.out.println(String.format("Created a ring which contains %s nodes, each node maps to %s virtual nodes.", numOfNodes, replicas));
		// testing 
		HashMap<String, Integer> counter = new HashMap<>();
		
		String node = "";
		int sampleCnt = 1000000;
		for (int i = 0; i < sampleCnt; i++) {
			node = cHash.get(RandomStringUtils.randomAlphanumeric(6));
			counter.put(node, counter.containsKey(node) ? counter.get(node) + 1 : 1);
		}
		// analysis
		double mean = sampleCnt / numOfNodes;
		double numi = 0.0;
		double sum = 0.0;
		Collection<Integer> values = counter.values();
		System.out.println("Max: " + Collections.max(values));
		System.out.println("Min: " + Collections.min(values));
		int totalInCache = values.stream().mapToInt(v -> v.intValue()).sum();
		System.out.println("Sum: " + totalInCache);
		
		for (String nodeName : counter.keySet()) {
			numi = Math.pow((counter.containsKey(nodeName) ? counter.get(nodeName) : 0) - mean, 2);
			sum += numi;
		}
		
		double stdev = Math.sqrt(sum/numOfNodes);
		System.out.println("Standard deviation: " + stdev);
	}
}
输出样本：
Created a ring which contains 10 nodes, each node maps to 1000 virtual nodes.
Max: 103582
Min: 97759
Sum: 1000000
Standard deviation: 1924.6792979610914
﻿