一致性 Hash 算法的实现及分析

用户头像
天天向上
关注
发布于: 2020 年 10 月 25 日



1、一致性Hash算法

import java.util.*;
public class ConsistentHash<T> {
/**
* 每个服务器节点的虚拟节点的个数,默认150个
*/
private int virtualNodeNum = 150;
/**
* 虚拟结点在Hash环上的位置
*/
public TreeSet<Integer> hashRing = new TreeSet<>();
/**
* 虚拟结点和服务器结点的映射关系
*/
public Map<Integer, T> virtualNodeMapping = new HashMap<>();
/**
* 实际的服务器结点
*/
public List<T> nodes = new ArrayList<>();
public ConsistentHash(int virtualNodeNum, List<T> nodes) {
this.virtualNodeNum = virtualNodeNum;
initVirtualNodes(nodes);
}
public int getVirtualNodeNum() {
return virtualNodeNum;
}
private void initVirtualNodes(List<T> nodes) {
for (int i = 0; i < nodes.size(); i++) {
addNode(nodes.get(i));
}
}
public void addNode(T node) {
this.nodes.add(node);
for (int i = 0; i < virtualNodeNum; i++) {
Integer virtualNode = createVirtualNode(createVirtualNodeName(node.hashCode(), i));
hashRing.add(virtualNode);
virtualNodeMapping.put(virtualNode, node);
}
}
private String createVirtualNodeName(int nodeHashCode, int virtualNodeIndex) {
return "node" + nodeHashCode + "#" + virtualNodeIndex;
}
private Integer createVirtualNode(String virtualNodeName) {
Random random = new Random();
while (true) {
String s = virtualNodeName + "#" + random.nextInt();
Integer index = Math.abs(s.hashCode());
if (!hashRing.contains(index)) {
return index;
}
}
}
private Integer getVirtualNode(Integer parameterHash) {
Integer virtualNode = hashRing.first();
Iterator<Integer> iterator = hashRing.iterator();
while (iterator.hasNext()) {
Integer temp = iterator.next();
if (temp > parameterHash) {
virtualNode = temp;
break;
}
}
return virtualNode;
}
public T getNode(Integer parameterHashCode) {
Integer virtualNode = getVirtualNode(parameterHashCode);
return virtualNodeMapping.get(virtualNode);
}
}



Server类用来对调用进行计数

import java.util.concurrent.atomic.AtomicInteger;
public class Server {
private AtomicInteger count = new AtomicInteger(0);
private String ip;
public Server(String ip) {
this.ip = ip;
}
public void service() {
count.addAndGet(1);
}
public int getCount() {
return count.get();
}
public String getIp() {
return ip;
}
}



构建10个服务器结点的服务

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
public class Service {
private List<Server> servers = new ArrayList<>();
private ConsistentHash<Server> consistentHash;
public Service(int virtualNodeNum) {
servers.add(new Server("192.168.0.1"));
servers.add(new Server("192.168.0.2"));
servers.add(new Server("192.168.0.3"));
servers.add(new Server("192.168.0.4"));
servers.add(new Server("192.168.0.5"));
servers.add(new Server("192.168.0.6"));
servers.add(new Server("192.168.0.7"));
servers.add(new Server("192.168.0.8"));
servers.add(new Server("192.168.0.9"));
servers.add(new Server("192.168.0.10"));
consistentHash = new ConsistentHash(virtualNodeNum, servers);
}
public void service(Integer i) {
Server server = consistentHash.getNode(i);
server.service();
}
public void printBalanceResult() {
System.out.println("虚拟结点数为" + consistentHash.getVirtualNodeNum() + "时,标准差为" + standardDeviation());
for (int i = 0; i < servers.size(); i++) {
Server server = servers.get(i);
System.out.println("服务器" + server.getIp() + "接收到的请求数为:" + server.getCount());
}
}
private double standardDeviation() {
Integer num = servers.size();
BigDecimal sum = BigDecimal.ZERO;
for (int i = 0; i < num; i++) {
sum = sum.add(new BigDecimal(servers.get(i).getCount()));
}
BigDecimal avg = sum.divide(new BigDecimal(num), 2, BigDecimal.ROUND_DOWN);
BigDecimal deviationVar = BigDecimal.ZERO;
for (int i = 0; i < num; i++) {
deviationVar = deviationVar.add((new BigDecimal(servers.get(i).getCount()).subtract(avg)).pow(2));
}
return Math.sqrt(deviationVar.divide(new BigDecimal(num), 2, BigDecimal.ROUND_DOWN).doubleValue());
}
}



2、测试结果

import org.junit.Test;
import java.util.Random;
public class ConsistentHashTest {
private void test(int virtualNodeNum) {
Service service = new Service(virtualNodeNum);
Random random = new Random(Integer.MAX_VALUE);
for (int i = 0; i < 1000000; i++) {
service.service(Math.abs(random.nextInt()));
}
service.printBalanceResult();
}
@Test
public void test100VirtualNode() {
test(100);
}
@Test
public void test150VirtualNode() {
test(150);
}
@Test
public void test200VirtualNode() {
test(200);
}
}

150个虚拟结点的测试结果:

虚拟结点数为150时,标准差为5082.597229763539
服务器192.168.0.1接收到的请求数为:97285
服务器192.168.0.2接收到的请求数为:104577
服务器192.168.0.3接收到的请求数为:96278
服务器192.168.0.4接收到的请求数为:111228
服务器192.168.0.5接收到的请求数为:104670
服务器192.168.0.6接收到的请求数为:98761
服务器192.168.0.7接收到的请求数为:97731
服务器192.168.0.8接收到的请求数为:92970
服务器192.168.0.9接收到的请求数为:96511
服务器192.168.0.10接收到的请求数为:99989

100个虚拟结点的测试结果:

虚拟结点数为200时,标准差为9887.882725841766
服务器192.168.0.1接收到的请求数为:91733
服务器192.168.0.2接收到的请求数为:104090
服务器192.168.0.3接收到的请求数为:101407
服务器192.168.0.4接收到的请求数为:99101
服务器192.168.0.5接收到的请求数为:118211
服务器192.168.0.6接收到的请求数为:101417
服务器192.168.0.7接收到的请求数为:110598
服务器192.168.0.8接收到的请求数为:90961
服务器192.168.0.9接收到的请求数为:81025
服务器192.168.0.10接收到的请求数为:101457

200个虚拟结点的测试结果:

虚拟结点数为100时,标准差为11033.066890035609
服务器192.168.0.1接收到的请求数为:121222
服务器192.168.0.2接收到的请求数为:104118
服务器192.168.0.3接收到的请求数为:91737
服务器192.168.0.4接收到的请求数为:89922
服务器192.168.0.5接收到的请求数为:87783
服务器192.168.0.6接收到的请求数为:98833
服务器192.168.0.7接收到的请求数为:118913
服务器192.168.0.8接收到的请求数为:93781
服务器192.168.0.9接收到的请求数为:99416
服务器192.168.0.10接收到的请求数为:94275



将服务器数量修改为3台,测试结果:

虚拟结点数为150时,标准差为15951.119862881102
服务器192.168.0.1接收到的请求数为:355792
服务器192.168.0.2接收到的请求数为:320270
服务器192.168.0.3接收到的请求数为:323938
虚拟结点数为200时,标准差为8785.087452609678
服务器192.168.0.1接收到的请求数为:322892
服务器192.168.0.2接收到的请求数为:332723
服务器192.168.0.3接收到的请求数为:344385
虚拟结点数为100时,标准差为24151.648975173517
服务器192.168.0.1接收到的请求数为:367477
服务器192.168.0.2接收到的请求数为:315480
服务器192.168.0.3接收到的请求数为:317043



用户头像

天天向上

关注

还未添加个人签名 2018.09.20 加入

还未添加个人简介

评论

发布
暂无评论
一致性Hash算法的实现及分析