一致性 hash

发布于: 2020 年 07 月 09 日

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

基类

public interface Cache {
void set(String key, String value);
String get(String key);
}

Cache基类

用于通用实现cache操作

public interface ICacheService extends Cache {
long getCacheSize();
}

Cache实现类

public class CacheServiceImpl implements ICacheService{
private Map<String, String> cacheMap = new ConcurrentHashMap<>();
@Override
public void set(String key, String value) {
cacheMap.put(key, value);
}
@Override
public String get(String key) {
return cacheMap.get(key);
}
@Override
public long getCacheSize() {
return cacheMap.size();
}
}

Hash环

  1. TreeMap红黑树天然支持高效查找,ceilingEntry()函数查找当前key应该落在的cache节点

  2. HashCode使用FNVHash算法,使Hash值更加均匀

  3. 支持指定具体Cache实现方式

/**
* @Date : 2020/7/9 11:46 AM
* @Description : 一致性hash环
*/
public final class ConsistencyHashRing {
private TreeMap<Integer, Cache> map = new TreeMap<>();
private List<ICacheService> cacheList = new ArrayList<>();
private int virtualNodeNum;
public void initConsistencyHashRing(List<String> serverIpList, int virtualNodeNum, Class<? extends ICacheService> clazz) {
if (CollectionUtils.isEmpty(serverIpList)) {
return;
}
this.virtualNodeNum = virtualNodeNum;
serverIpList.forEach(ip -> {
try {
int ipHash = getHashCode(ip);
ICacheService cache = clazz.newInstance();
map.put(ipHash, cache);
cacheList.add(cache);
for (int i = 0; i < virtualNodeNum; i++) {
int virtualHash = getVirtualNodeHash(ip + i, virtualNodeNum);
map.put(virtualHash, cache);
}
} catch (Exception e) {
e.printStackTrace();
}
});
}
Cache getServer(String key) {
assert StringUtils.isNotEmpty(key);
int hashCode = getHashCode(key);
Map.Entry<Integer, Cache> cacheEntry = map.ceilingEntry(hashCode);
return cacheEntry == null ? map.firstEntry().getValue() : cacheEntry.getValue();
}
private int getVirtualNodeHash(String ip, int virtualNum) {
String virtualIp = ip + ":virtual:" + virtualNum;
return getHashCode(virtualIp);
}
/**
* FNVHash算法
*
* @param data
* @return
*/
private int getHashCode(String data) {
// data = Md5Crypt.md5Crypt(data.getBytes());
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < data.length(); i++) {
hash = (hash ^ data.charAt(i)) * p;
}
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
return Math.abs(hash);
}
private long getSumSize() {
return cacheList.stream().mapToLong(ICacheService::getCacheSize).sum();
}
@Override
public String toString() {
long sum = getSumSize();
long avg = sum / cacheList.size();
long sumDiff = cacheList.stream().mapToLong(cache -> {
long cacheSize = cache.getCacheSize();
long diff = cacheSize - avg;
return diff * diff;
}).sum();
String template = "服务节点数:%d 虚拟节点数:%d\r\n";
String format = String.format(template, cacheList.size(), virtualNodeNum);
StringBuilder sbu = new StringBuilder(format);
for (int i = 0; i < cacheList.size(); i++) {
long cacheSize = cacheList.get(i).getCacheSize();
sbu.append("第").append(i).append("个节点").append("cache数量:").append(cacheSize).append("\r\n");
}
// 标准差公式: (每个样本 - 平均值)的平方之和 / (服务器数 - 1),结果再取平方根
double sqrt = Math.sqrt(sumDiff / (cacheList.size() - 1));
sbu.append("标准差:").append(sqrt).append("\r\n");
return sbu.toString();
}
}

用户直接操作CacheServer,内部指定Cache的具体实现方式

public class CacheServer implements Cache{
private ConsistencyHashRing consistencyHashRing;
public CacheServer(List<String> serverList, int virtualCount) {
consistencyHashRing = new ConsistencyHashRing();
consistencyHashRing.initConsistencyHashRing(serverList, virtualCount, CacheServiceImpl.class);
}
@Override
public void set(String key, String value) {
Cache cache = consistencyHashRing.getServer(key);
cache.set(key, value);
}
@Override
public String get(String key) {
Cache cache = consistencyHashRing.getServer(key);
return cache.get(key);
}
@Override
public String toString() {
return consistencyHashRing.toString();
}
}

main函数

/**
* @Date : 2020/7/9 1:26 PM
* @Description :
*/
public class CacheMain {
private static ExecutorService executorService = new ThreadPoolExecutor(10, 10, 10, TimeUnit.SECONDS, new ArrayBlockingQueue<>(1));
public static void main(String[] args) throws ExecutionException, InterruptedException {
String serialResult = serialResult(0);
String serialResult100 = serialResult(100);
String serialResult300 = serialResult(300);
String serialResult500 = serialResult(500);
System.out.println();
System.out.println(serialResult);
System.out.println(serialResult100);
System.out.println(serialResult300);
System.out.println(serialResult500);
}
private static String serialResult(int virtualCount) {
String ipStr = "192.168.10.10";
List<String> ipList = IntStream.range(0, 10).boxed()
.map(i -> ipStr + i).collect(toList());
CacheServer cacheServer = new CacheServer(ipList, virtualCount);
Stopwatch started = Stopwatch.createStarted();
int maxCount = 1000000;
for (int i = 0; i < maxCount; i++) {
cacheServer.set("key:" + i, "value:" + i);
System.out.println("key:" + i);
}
return cacheServer.toString() + " 耗时:" + started.stop();
}
private static String parallelResult(int virtualCount) throws ExecutionException, InterruptedException {
String ipStr = "192.168.10.10";
List<String> ipList = IntStream.range(0, 10).boxed()
.map(i -> ipStr + i).collect(toList());
CacheServer cacheServer = new CacheServer(ipList, virtualCount);
Stopwatch started = Stopwatch.createStarted();
CompletableFuture.allOf(IntStream.range(0, 10).boxed().map(num ->
CompletableFuture.runAsync(() -> {
int maxCount = 100000;
for (int i = 0; i < maxCount; i++) {
cacheServer.set(Thread.currentThread().getName() + ":key:" + i, "value:" + i);
System.out.println(Thread.currentThread().getName() + ":key:" + i);
}
}, executorService)).toArray(CompletableFuture[]::new)).get();
return cacheServer.toString() + " 耗时:" + started.stop();
}
}

测试结果

服务节点数:10 虚拟节点数:0
第0个节点cache数量:43950
第1个节点cache数量:17128
第2个节点cache数量:2549
第3个节点cache数量:200307
第4个节点cache数量:439140
第5个节点cache数量:54913
第6个节点cache数量:38112
第7个节点cache数量:165825
第8个节点cache数量:27928
第9个节点cache数量:10148
标准差:136645.181221293
服务节点数:10 虚拟节点数:100
第0个节点cache数量:110642
第1个节点cache数量:102568
第2个节点cache数量:104212
第3个节点cache数量:100112
第4个节点cache数量:90182
第5个节点cache数量:105007
第6个节点cache数量:99653
第7个节点cache数量:108661
第8个节点cache数量:82271
第9个节点cache数量:96692
标准差:8559.965478902353
服务节点数:10 虚拟节点数:300
第0个节点cache数量:103301
第1个节点cache数量:108235
第2个节点cache数量:90724
第3个节点cache数量:93514
第4个节点cache数量:101656
第5个节点cache数量:88390
第6个节点cache数量:113624
第7个节点cache数量:101026
第8个节点cache数量:98185
第9个节点cache数量:101345
标准差:7718.145502645049
服务节点数:10 虚拟节点数:500
第0个节点cache数量:97527
第1个节点cache数量:93576
第2个节点cache数量:101842
第3个节点cache数量:101476
第4个节点cache数量:96864
第5个节点cache数量:103557
第6个节点cache数量:96292
第7个节点cache数量:104967
第8个节点cache数量:102286
第9个节点cache数量:101613
标准差:3677.101847923171
服务节点数:10 虚拟节点数:1000
第0个节点cache数量:96408
第1个节点cache数量:103762
第2个节点cache数量:100520
第3个节点cache数量:99368
第4个节点cache数量:96394
第5个节点cache数量:100543
第6个节点cache数量:96158
第7个节点cache数量:100778
第8个节点cache数量:107945
第9个节点cache数量:98124
标准差:3697.321327664124
服务节点数:10 虚拟节点数:3000
第0个节点cache数量:98855
第1个节点cache数量:100362
第2个节点cache数量:103029
第3个节点cache数量:100546
第4个节点cache数量:99497
第5个节点cache数量:105667
第6个节点cache数量:96533
第7个节点cache数量:99691
第8个节点cache数量:97276
第9个节点cache数量:98544
标准差:2686.149660759802
服务节点数:10 虚拟节点数:5000
第0个节点cache数量:99880
第1个节点cache数量:99464
第2个节点cache数量:100005
第3个节点cache数量:99765
第4个节点cache数量:100635
第5个节点cache数量:101017
第6个节点cache数量:98405
第7个节点cache数量:101878
第8个节点cache数量:101622
第9个节点cache数量:97329
标准差:1399.6224490911825
服务节点数:10 虚拟节点数:10000
第0个节点cache数量:100607
第1个节点cache数量:99901
第2个节点cache数量:99970
第3个节点cache数量:101476
第4个节点cache数量:100140
第5个节点cache数量:99643
第6个节点cache数量:98579
第7个节点cache数量:101316
第8个节点cache数量:98976
第9个节点cache数量:99392
标准差:935.3614274706863
服务节点数:10 虚拟节点数:50000
第0个节点cache数量:100249
第1个节点cache数量:99739
第2个节点cache数量:99587
第3个节点cache数量:100525
第4个节点cache数量:100537
第5个节点cache数量:99728
第6个节点cache数量:100600
第7个节点cache数量:100033
第8个节点cache数量:99835
第9个节点cache数量:99167
标准差:473.8575735387164
服务节点数:10 虚拟节点数:100000
第0个节点cache数量:99926
第1个节点cache数量:99089
第2个节点cache数量:99898
第3个节点cache数量:99686
第4个节点cache数量:100802
第5个节点cache数量:100615
第6个节点cache数量:100746
第7个节点cache数量:99903
第8个节点cache数量:99760
第9个节点cache数量:99575
标准差:554.7747290567587

用户头像

石印掌纹

关注

还未添加个人签名 2018.11.22 加入

还未添加个人简介

评论

发布
暂无评论
一致性hash