第五周作业 一致性 hash 算法

发布于: 2020 年 07 月 08 日

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

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

public interface HashService {
/**
*
* @param key
* @return
*/
Long hash(String key);
}
package com.example;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
public class HashServiceImpl implements HashService {
/**
* MurMurHash算法,性能高,碰撞率低
* @param key
* @return
*/
@Override
public Long hash(String key) {
ByteBuffer buf = ByteBuffer.wrap(key.getBytes());
int seed = 0x1234ABCD;
ByteOrder byteOrder = buf.order();
buf.order(ByteOrder.LITTLE_ENDIAN);
long m = 0xc6a4a7935bd1e995L;
int r = 47;
long h = seed ^ (buf.remaining() * m);
long k;
while (buf.remaining() >= 8) {
k = buf.getLong();
k *= m;
k ^= k >>> r;
k *= m;
h ^= k;
h *= m;
}
if (buf.remaining() > 0) {
ByteBuffer finish = ByteBuffer.allocate(8).order(ByteOrder.LITTLE_ENDIAN);
finish.put(buf).rewind();
h ^= finish.getLong();
h *= m;
}
h ^= h >>> r;
h *= m;
h ^= h >>> r;
buf.order(byteOrder);
return h;
}
}
package com.example;
import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHash<T> {
private final HashService hashService;
private final int nums;
private final SortedMap<Long,T> circleMap = new TreeMap<>();
public ConsistentHash(HashService hashService, int nums, Collection<T> nodes) {
this.hashService = hashService;
this.nums = nums;
for (T node :nodes) {
addNode(node);
}
}
public void addNode(T node) {
for (int i = 0; i < this.nums;i++) {
circleMap.put(this.hashService.hash(node.toString()+i),node);
}
}
public void removeNode(T node) {
for (int i = 0; i < this.nums;i++){
circleMap.remove(this.hashService.hash(node.toString()+i),node);
}
}
public T get(String key) {
if (circleMap.isEmpty()) {
return null;
}
long hash = hashService.hash(key);
if (!circleMap.containsKey(hash)) {
SortedMap<Long,T> tailMap = circleMap.tailMap(hash);
hash = tailMap.isEmpty() ? circleMap.firstKey():tailMap.firstKey();
}
return circleMap.get(hash);
}
}
package com.example;
public class Node<T> {
/**
* ip地址
*/
private String ip;
/**
* 名称
*/
private String 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;
}
public Node(String ip, String name) {
this.ip = ip;
this.name = name;
}
@Override
public String toString() {
return ip;
}
}
package com.example;
import java.nio.ByteOrder;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import java.util.UUID;
public class HashTest {
/**
* 思考
* 1.构建hash环 2^32-1
* 2.物理节点如何虚拟化出节点,节点个数是多少个?推荐个数100~200
* 3.hash函数如何设计?
*
* 环和虚拟节点的关系
* 虚拟节点和物理节点的关系
*
*
* @param args
*/
/**
* 机器节点IP前缀
*/
private static final String IP_PREFIX = "192.168.0.";
private static final int MACHINE_NUMS = 10;
public static void main(String[] args) {
// 每台真实机器节点上保存的记录条数
Map<String, Integer> map = new HashMap<>();
// 真实机器节点, 模拟10台
List<Node<String>> nodes = new ArrayList<Node<String>>();
for (int i = 1; i <= MACHINE_NUMS; i++) {
// 初始化记录
map.put(IP_PREFIX + i, 0);
Node<String> node = new Node<>(IP_PREFIX + i, "node" + i);
nodes.add(node);
}
HashService iHashService = new HashServiceImpl();
// 每台真实机器引入100个虚拟节点
ConsistentHash<Node<String>> consistentHash = new ConsistentHash<Node<String>>(iHashService, 2000, nodes);
// 将1000000条记录尽可能均匀的存储到10台机器节点上
for (int i = 0; i < 1000000; i++) {
// 产生随机一个字符串当做一条记录,可以是其它更复杂的业务对象,比如随机字符串相当于对象的业务唯一标识
String data = UUID.randomUUID().toString() + i;
// 通过记录找到真实机器节点
Node<String> node = consistentHash.get(data);
// 每台真实机器节点上保存的记录条数加1
map.put(node.getIp(), map.get(node.getIp()) + 1);
}
double[] x = new double[MACHINE_NUMS];
// 打印每台真实机器节点保存的记录条数
for (int i = 1; i <= MACHINE_NUMS; i++) {
System.out.println(IP_PREFIX + i + "节点记录条数:" + map.get(IP_PREFIX + i));
x[i-1] = Double.valueOf(map.get(IP_PREFIX + i));
}
System.out.println("标准差="+standardDiviation(x));
}
/**
* 方差s^2=[(x1-x)^2 +...(xn-x)^2]/n
* 或者
* s^2=[(x1-x)^2 +...(xn-x)^2]/(n-1)
* @param x
* @return
*/
public static double variance(double[] x) {
int m=x.length;
double sum=0;
//求和
for(int i=0;i<m;i++){
sum+=x[i];
}
//求平均值
double dAve=sum/m;
double dVar=0;
//求方差
for(int i=0;i<m;i++){
dVar+=(x[i]-dAve)*(x[i]-dAve);
}
return dVar/m;
}
/**
* 标准差σ=sqrt(s^2)
* @param x
* @return
*/
public static double standardDiviation(double[] x) {
return Math.sqrt(variance(x));
}
}

测试结果

10台机器每台机器300个虚拟节点

192.168.0.1节点记录条数:99322

192.168.0.2节点记录条数:99252

192.168.0.3节点记录条数:103462

192.168.0.4节点记录条数:95808

192.168.0.5节点记录条数:103246

192.168.0.6节点记录条数:97116

192.168.0.7节点记录条数:104757

192.168.0.8节点记录条数:98969

192.168.0.9节点记录条数:100953

192.168.0.10节点记录条数:97115

标准差=2869.7545539645025

10台机器每台机器250个虚拟节点

192.168.0.1节点记录条数:99368

192.168.0.2节点记录条数:100707

192.168.0.3节点记录条数:102003

192.168.0.4节点记录条数:95858

192.168.0.5节点记录条数:103418

192.168.0.6节点记录条数:95711

192.168.0.7节点记录条数:102387

192.168.0.8节点记录条数:100905

192.168.0.9节点记录条数:101368

192.168.0.10节点记录条数:98275

标准差=2520.109799195265

10台机器每台机器200个虚拟节点

192.168.0.1节点记录条数:101930

192.168.0.2节点记录条数:100200

192.168.0.3节点记录条数:98678

192.168.0.4节点记录条数:96921

192.168.0.5节点记录条数:102103

192.168.0.6节点记录条数:94536

192.168.0.7节点记录条数:104660

192.168.0.8节点记录条数:99009

192.168.0.9节点记录条数:101420

192.168.0.10节点记录条数:100543

标准差=2725.4295074354795

10台机器每台机器150个虚拟节点

192.168.0.1节点记录条数:103395

192.168.0.2节点记录条数:99778

192.168.0.3节点记录条数:99900

192.168.0.4节点记录条数:100719

192.168.0.5节点记录条数:103409

192.168.0.6节点记录条数:94361

192.168.0.7节点记录条数:101059

192.168.0.8节点记录条数:94599

192.168.0.9节点记录条数:104406

192.168.0.10节点记录条数:98374

标准差=3284.370046142791

10台机器每台机器100个虚拟节点

192.168.0.1节点记录条数:102878

192.168.0.2节点记录条数:101623

192.168.0.3节点记录条数:101383

192.168.0.4节点记录条数:99598

192.168.0.5节点记录条数:102544

192.168.0.6节点记录条数:91619

192.168.0.7节点记录条数:100336

192.168.0.8节点记录条数:95339

192.168.0.9节点记录条数:100470

192.168.0.10节点记录条数:104210

标准差=3598.433270188569

结论

按照标准差结论可知,10个节点虚拟节点数在200~250之间最后合适;

用户头像

雪域飞鸿

关注

我思故我在! 2018.01.15 加入

凡事有交代,件件有着落,事事有回音。

评论

发布
暂无评论
第五周作业 一致性hash算法