用你熟悉的编程语言实现一致性 hash 算法。 编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
Node.java
package com.tale.hash;
public class Node {
private String ip;
private String name;
public Node(String ip, String name) { this.ip = ip; this.name = name; }
public String getIp() { return ip; }
public void setIp(String ip) { this.ip = ip; }
public String getName() { return name; }
public void setName(String name) { this.name = name; }
}
ConHashTest.java
package com.tale.hash;
import java.math.BigDecimal;
import java.util.*;
public class ConHashTest {
private static final String IP_PREFIX = "192.168.1.";// 机器节点IP前缀
// 方差
public static double Variance(int[] x) {
int m = x.length;
double sum = 0;
//求和
for (double value : x) sum += value;
double dAve = sum / m;//求平均值
double dVar = 0;
//求方差
for (double v : x) dVar += (v - dAve) * (v - dAve);
return dVar / m;
}
// 标准差
public static double StandardDivination(int[] x) {
return Math.sqrt(Variance(x));
}
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();// 每台真实机器节点上保存的记录条数
HashFunction hashFunction = new HashFunctionImpl();
LinkedHashMap<Integer, Double> variances = new LinkedHashMap<>();
for (int numberOfReplicas = 100; numberOfReplicas <= 1000; numberOfReplicas += 10) {
System.out.println("单个机器的虚拟节点: " + numberOfReplicas);
map.clear();
//真实物理节点
List<Node> realNodes = new ArrayList<>();
for (int i = 1; i <= 10; i++) {
map.put(IP_PREFIX + i, 0);// 每台真实机器节点上保存的记录条数初始为0
Node node = new Node(IP_PREFIX + i, "node" + i);
realNodes.add(node);
}
ConsistentHash consistentHash = new ConsistentHash(hashFunction, numberOfReplicas, realNodes);
// 将1000000条记录尽可能均匀的存储到10台机器节点
for (int i = 0; i < 1000000; i++) {
// 产生随机一个字符串当做一条记录，可以是其它更复杂的业务对象,比如随机字符串相当于对象的业务唯一标识
String data = UUID.randomUUID().toString() + i;
// 通过记录找到真实机器节点
Node node = consistentHash.get(data);
// 每台真实机器节点上保存的记录条数加1
map.put(node.getIp(), map.get(node.getIp()) + 1);
}
// 打印每台真实机器节点保存的记录条数
int[] numbers = new int[10];
for (int i = 1; i <= 10; i++) {
numbers[i - 1] = map.get("192.168.1." + i);
System.out.println(IP_PREFIX + i + "节点记录条数：" + map.get("192.168.1." + i));
}
System.out.println("方差: " + BigDecimal.valueOf(Variance(numbers)));
System.out.println("标准差: " + BigDecimal.valueOf(StandardDivination(numbers)));
variances.put(numberOfReplicas, StandardDivination(numbers));
System.out.println();
System.out.println();
}
System.out.println(variances);
}
}
ConsistentHash.java
package com.tale.hash;
import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHash {
private final HashFunction hashFunction;// hash 函数接口
private final int numberOfReplicas;// 每个机器节点关联的虚拟节点个数
private final SortedMap<Integer, Node> circle = new TreeMap<>();// 环形虚拟节点
/**
* @param hashFunction hash 函数接口
* @param numberOfReplicas 每个机器节点关联的虚拟节点个数
* @param nodes 真实机器节点
*/
public ConsistentHash(HashFunction hashFunction, int numberOfReplicas, Collection<Node> nodes) {
this.hashFunction = hashFunction;
this.numberOfReplicas = numberOfReplicas;
nodes.forEach(this::add);
}
/**
* 增加真实机器节点
*/
public void add(Node node) {
for (int i = 0; i < this.numberOfReplicas; i++) {
circle.put(this.hashFunction.hash(node.getIp() + i), node);
}
}
/**
* 删除真实机器节点
*/
public void remove(Node node) {
for (int i = 0; i < this.numberOfReplicas; i++) {
circle.remove(this.hashFunction.hash(node.getIp() + i));
}
}
/**
* 取得真实机器节点
*/
public Node get(String key) {
if (circle.isEmpty()) return null;
Integer hash = hashFunction.hash(key);
if (!circle.containsKey(hash)) {
SortedMap<Integer, Node> tailMap = circle.tailMap(hash);// 沿环的顺时针找到一个虚拟节点
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
return circle.get(hash); // 返回该虚拟节点对应的真实机器节点的信息
}
}
HashFunction.java
package com.tale.hash;
public interface HashFunction {
Integer hash(String key);
}
HashFunctionImpl.java
package com.tale.hash;
public class HashFunctionImpl implements HashFunction {
@Override
public Integer hash(String key) {
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < key.length(); i++) hash = (hash ^ key.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;
}
}
本文由 biezhi 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为:
2020/07/09 13:46