动手实现一致性 hash 算法

发布于: 4 小时前

在分布式缓存场景中,我们在实现缓存集群线性伸缩的同时,还要保证失效或需要搬挪的key尽可能的少,而一致性hash算法正是解决该问题的很好方案。

一致性hash算法网上的资料很多,本文着重于实例讲解。问题如下:

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

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

类设计及简介

  • ConsistentHashingWithVirtualNode

  • 通过ConcurrentSkipListMap来模拟环,保存所有虚拟节点的hash值(及实际节点映射);

  • 通过virtualNode来调整一个实际节点映射的虚拟节点数;

  • 通过IHash接口隔离不同的hash值计算;

  • IHash

  • 提供了两个实现:HashImpl01和HashImpl02

具体实现如下:

package com.example.consistenthashing.demo;
import java.util.concurrent.ConcurrentNavigableMap;
import java.util.concurrent.ConcurrentSkipListMap;
/**
* @author linyurong
* @date 2020/7/3 9:57
*/
public class ConsistentHashingWithVirtualNode {
private ConcurrentSkipListMap<Integer, String> circle;
private IHash hashHelper;
private int virtualNode;
private static final int DEFAULT_VIRTUAL_NODE = 150;
private static final String SPILT_FOR_VIRTUAL = "&&VN";
public ConsistentHashingWithVirtualNode(String configs, int virtualNode, IHash hashHelper) {
this.circle = new ConcurrentSkipListMap();
this.virtualNode = virtualNode;
this.hashHelper = hashHelper == null ? new HashImpl01() : hashHelper;
setVirtualNodeForRealNode(configs);
}
public ConsistentHashingWithVirtualNode(String configs) {
this(configs, DEFAULT_VIRTUAL_NODE, null);
}
/**
* 分配节点
* @param key
* @return
*/
public String getServer(String key) {
int hash = hashHelper.getHash(key);
ConcurrentNavigableMap<Integer, String> subMap = circle.tailMap(hash);
String value = subMap.isEmpty() ? circle.firstEntry().getValue() : subMap.firstEntry().getValue();
String server = value.substring(0, value.indexOf(SPILT_FOR_VIRTUAL));
return server;
}
/**
* 获取实际节点映射的虚拟节点数
* @return
*/
public int getVirtualNode() {
return this.virtualNode;
}
/**
* 获取IHash实现名称
* @param key
* @return
*/
public String getHashHelper() {
return this.hashHelper.getClass().getSimpleName();
}
/**
* 构建真实节点和虚拟节点的映射关系,保存在circle成员变量中
* @param configs
* @return
*/
private void setVirtualNodeForRealNode(String configs) {
String[] nodes = configs.split(",");
for (String node : nodes) {
for (int i = 0; i < virtualNode; i++) {
String virtualNodeName = node + SPILT_FOR_VIRTUAL + i;
int hash = hashHelper.getHash(virtualNodeName);
this.circle.put(hash, virtualNodeName);
}
}
}
}

package com.example.consistenthashing.demo;
public interface IHash {
int getHash(String key);
}

package com.example.consistenthashing.demo;
import org.apache.commons.codec.digest.Md5Crypt;
public class HashImpl01 implements IHash {
@Override
public int getHash(String key) {
String crypt = Md5Crypt.md5Crypt(key.getBytes());
return Math.abs(crypt.hashCode());
}
}

package com.example.consistenthashing.demo;
public class HashImpl02 implements IHash {
@Override
public int getHash(String key) {
final int p = 16777619;
Long hash = 2166136261L;
for(int ind = 0,num = key.length();ind<num;ind++){
hash = (hash^key.charAt(ind))*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.intValue();
}
}

测试类:

package com.example.consistenthashing.demo;
import java.util.HashMap;
import java.util.Map;
import java.util.UUID;
public class ConsistentHashingTest {
//标准方差
public static double getStd(Map<String, Integer> map) {
double sum = 0;
int cnt = 0;
for (Map.Entry<String, Integer> entry : map.entrySet()) {
sum += entry.getValue();
cnt++;
}
double average = sum / cnt;
int total = 0;
for (Map.Entry<String, Integer> entry : map.entrySet()) {
total += (entry.getValue() - average) * (entry.getValue() - average);
}
double standardDeviation = Math.sqrt(total / cnt);
return standardDeviation;
}
/**
* 测试方法
* @param consistentHashing
* @param configs
*/
public static void testConsistentHashing(ConsistentHashingWithVirtualNode consistentHashing, String configs) {
Map<String, Integer> calcMap = new HashMap<>(4);
String[] servers = configs.split(",");
for (int i = 0; i < servers.length; i++) {
calcMap.put(servers[i], 0);
}
int size = 1000000;
for (int i = 0; i < size; i++) {
String key = UUID.randomUUID().toString();
String server = consistentHashing.getServer(key);
calcMap.put(server, calcMap.get(server) + 1);
}
System.out.println(calcMap);
System.out.println(consistentHashing.getHashHelper() + "[KV size: " + size + ", virtual size : "
+ consistentHashing.getVirtualNode() + ", standardDeviation: " + getStd(calcMap) + "]");
}
public static void main(String[] args) {
String configs = "192.168.0.1,192.168.0.2,192.168.0.3,192.168.0.4,192.168.0.5,192.168.0.6,192.168.0.7,192.168.0.8,192.168.0.9,192.168.0.10";
System.out.println("====================================");
ConsistentHashingWithVirtualNode consistentHashing2 = new ConsistentHashingWithVirtualNode(configs, 100, null);
testConsistentHashing(consistentHashing2, configs);
System.out.println("====================================");
ConsistentHashingWithVirtualNode consistentHashing = new ConsistentHashingWithVirtualNode(configs, 150, null);
testConsistentHashing(consistentHashing, configs);
System.out.println("====================================");
ConsistentHashingWithVirtualNode consistentHashing3 = new ConsistentHashingWithVirtualNode(configs, 200, null);
testConsistentHashing(consistentHashing3, configs);
System.out.println("************************************");
ConsistentHashingWithVirtualNode consistentHashing4 = new ConsistentHashingWithVirtualNode(configs, 100, new HashImpl02());
testConsistentHashing(consistentHashing4, configs);
System.out.println("====================================");
ConsistentHashingWithVirtualNode consistentHashing5 = new ConsistentHashingWithVirtualNode(configs, 150, new HashImpl02());
testConsistentHashing(consistentHashing5, configs);
System.out.println("====================================");
ConsistentHashingWithVirtualNode consistentHashing6 = new ConsistentHashingWithVirtualNode(configs, 200, new HashImpl02());
testConsistentHashing(consistentHashing6, configs);
System.out.println("====================================");
}
}

测试结果:

/Library/Java/JavaVirtualMachines/jdk-13.0.2.jdk/Contents/Home/bin/java "-javaagent:/Applications/IntelliJ IDEA.app/Contents/lib/idea_rt.jar=50937:/Applications/IntelliJ IDEA.app/Contents/bin" -Dfile.encoding=UTF-8 -classpath /Users/lyr/workspace/consistent-hashing/target/classes:/Users/lyr/app/apache-maven-3.6.3/repository/org/springframework/boot/spring-boot-starter/2.3.1.RELEASE/spring-boot-starter-2.3.1.RELEASE.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/springframework/boot/spring-boot/2.3.1.RELEASE/spring-boot-2.3.1.RELEASE.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/springframework/spring-context/5.2.7.RELEASE/spring-context-5.2.7.RELEASE.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/springframework/spring-aop/5.2.7.RELEASE/spring-aop-5.2.7.RELEASE.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/springframework/spring-beans/5.2.7.RELEASE/spring-beans-5.2.7.RELEASE.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/springframework/spring-expression/5.2.7.RELEASE/spring-expression-5.2.7.RELEASE.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/springframework/boot/spring-boot-autoconfigure/2.3.1.RELEASE/spring-boot-autoconfigure-2.3.1.RELEASE.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/springframework/boot/spring-boot-starter-logging/2.3.1.RELEASE/spring-boot-starter-logging-2.3.1.RELEASE.jar:/Users/lyr/app/apache-maven-3.6.3/repository/ch/qos/logback/logback-classic/1.2.3/logback-classic-1.2.3.jar:/Users/lyr/app/apache-maven-3.6.3/repository/ch/qos/logback/logback-core/1.2.3/logback-core-1.2.3.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/apache/logging/log4j/log4j-to-slf4j/2.13.3/log4j-to-slf4j-2.13.3.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/apache/logging/log4j/log4j-api/2.13.3/log4j-api-2.13.3.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/slf4j/jul-to-slf4j/1.7.30/jul-to-slf4j-1.7.30.jar:/Users/lyr/app/apache-maven-3.6.3/repository/jakarta/annotation/jakarta.annotation-api/1.3.5/jakarta.annotation-api-1.3.5.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/springframework/spring-core/5.2.7.RELEASE/spring-core-5.2.7.RELEASE.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/springframework/spring-jcl/5.2.7.RELEASE/spring-jcl-5.2.7.RELEASE.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/yaml/snakeyaml/1.26/snakeyaml-1.26.jar:/Users/lyr/app/apache-maven-3.6.3/repository/commons-codec/commons-codec/1.14/commons-codec-1.14.jar:/Users/lyr/app/apache-maven-3.6.3/repository/org/slf4j/slf4j-api/1.7.30/slf4j-api-1.7.30.jar com.example.consistenthashing.demo.ConsistentHashingTest
====================================
{192.168.0.2=101551, 192.168.0.1=120475, 192.168.0.4=105641, 192.168.0.3=97290, 192.168.0.10=87970, 192.168.0.9=103506, 192.168.0.6=84701, 192.168.0.5=106181, 192.168.0.8=93261, 192.168.0.7=99424}
HashImpl01[KV size: 1000000, virtual size : 100, standardDeviation: 9673.774857830835]
====================================
{192.168.0.2=97546, 192.168.0.1=107032, 192.168.0.4=96250, 192.168.0.3=98791, 192.168.0.10=108375, 192.168.0.9=99844, 192.168.0.6=102380, 192.168.0.5=102917, 192.168.0.8=92548, 192.168.0.7=94317}
HashImpl01[KV size: 1000000, virtual size : 150, standardDeviation: 4931.149561714794]
====================================
{192.168.0.2=100513, 192.168.0.1=107244, 192.168.0.4=104366, 192.168.0.3=109506, 192.168.0.10=86365, 192.168.0.9=109111, 192.168.0.6=100560, 192.168.0.5=97395, 192.168.0.8=90667, 192.168.0.7=94273}
HashImpl01[KV size: 1000000, virtual size : 200, standardDeviation: 7470.55071597804]
************************************
{192.168.0.2=99612, 192.168.0.1=86849, 192.168.0.4=108020, 192.168.0.3=85367, 192.168.0.10=96784, 192.168.0.9=108807, 192.168.0.6=101018, 192.168.0.5=107816, 192.168.0.8=94048, 192.168.0.7=111679}
HashImpl02[KV size: 1000000, virtual size : 100, standardDeviation: 8794.3269213738]
====================================
{192.168.0.2=105941, 192.168.0.1=102442, 192.168.0.4=107121, 192.168.0.3=90559, 192.168.0.10=86803, 192.168.0.9=105603, 192.168.0.6=95949, 192.168.0.5=109358, 192.168.0.8=95001, 192.168.0.7=101223}
HashImpl02[KV size: 1000000, virtual size : 150, standardDeviation: 7191.12564206745]
====================================
{192.168.0.2=106971, 192.168.0.1=112452, 192.168.0.4=104434, 192.168.0.3=88770, 192.168.0.10=85037, 192.168.0.9=92755, 192.168.0.6=106592, 192.168.0.5=102617, 192.168.0.8=95305, 192.168.0.7=105067}
HashImpl02[KV size: 1000000, virtual size : 200, standardDeviation: 8507.775619984344]
====================================
Process finished with exit code 0

总结

从测试结果来看,影响一致性hash算法的分配均衡因素有:

  • 真实节点映射的虚拟节点数;

  • hash值计算逻辑(该因素还会影响执行性能);

发布于: 4 小时前 阅读数: 5
用户头像

林昱榕

关注

开心生活,努力工作。 2018.02.13 加入

还未添加个人简介

评论

发布
暂无评论
动手实现一致性hash算法