周练习 5
发布于: 2020 年 10 月 24 日
用你熟悉的编程语言实现一致性 hash 算法
本次实现是客户端根据 key 的 hash 值模拟算出 hash 环上对应的虚拟节点,进而映射到对应的缓存服务节点.
主要依赖:
<dependencies> <dependency> <groupId>redis.clients</groupId> <artifactId>jedis</artifactId> <version>2.9.0</version> </dependency> <dependency> <groupId>org.projectlombok</groupId> <artifactId>lombok</artifactId> <version>1.18.8</version> </dependency> </dependencies>复制代码
选择算法代码:
package com.example.hash;
import java.util.*;
public class DefaultNodeManger {
private List<Integer> nodeList;
private Map<Integer, Integer> nodeLinker;
public Integer getRedisNode(String key){ Integer virtualNode = this.getVirtualNode(key); return this.nodeLinker.get(virtualNode); }
public Integer getVirtualNode(String key){ int hashCode = key.hashCode(); int targetIndex = getTargetIndex(hashCode); Integer result = this.nodeList.get(targetIndex);
return result; }
private int getTargetIndex(int hashCode) { int size = this.nodeList.size(); int targetIndex = 0; for (int i = 1; i < size; i++) { Integer currentNode = this.nodeList.get(i); int position = currentNode; if (position > hashCode) { targetIndex = i - 1; break; } else { targetIndex = i; continue; } } return targetIndex; }
public DefaultNodeManger(int virtualNodeNumber, List<Integer> redisNodes){ this.nodeList = new ArrayList<Integer>(virtualNodeNumber); this.nodeLinker = new HashMap<Integer, Integer>(virtualNodeNumber); this.init(virtualNodeNumber, redisNodes); Collections.sort(this.nodeList); }
private void init(int virtualNodeNumber, List<Integer> redisNodes) { int redisNodeNumber = redisNodes.size(); Random random = new Random(); // start position always is negative in first int startPosition = random.nextInt(Integer.MAX_VALUE) + Integer.MIN_VALUE; int positionInterval = Integer.MAX_VALUE / virtualNodeNumber; int position = 0; for (int i = 0; i < virtualNodeNumber; i++) { for (int j = 0; j < redisNodeNumber; j++) { startPosition += positionInterval; Integer redisNode = redisNodes.get(j); boolean containsThisPosition = this.nodeList.contains(startPosition); if (!containsThisPosition) { position = startPosition; } else { position = this.findUniquePositionByStart(startPosition); } this.putNodeData(position, redisNode); }
} }
private int findUniquePositionByStart(int alreadyOwnedPosition) { int lessThanThisPosition = Integer.MIN_VALUE; for(Integer currentPosition : this.nodeList){ if (currentPosition > lessThanThisPosition && currentPosition < alreadyOwnedPosition) { lessThanThisPosition = currentPosition; } } // return average between the had one position and the less one position // unless very bad luck return alreadyOwnedPosition + lessThanThisPosition / 2; }
private void putNodeData(int position, Integer redisNode) { this.nodeList.add(position); this.nodeLinker.put(position, redisNode); }
@Override public String toString() { return "DefaultNodeManger{" + "nodeList=" + nodeList + ", nodeLinker=" + nodeLinker + '}'; }}
复制代码
其中,在 init 方法中,开始计算虚拟节点的起始位置变量 startPosition 和相邻两个虚拟节点的间隔 positionInterval,可能需要根据自己实际情况进行调整,这里就不再做优化了.
还有,加入缓存节点重新添加和分配虚拟节点的功能,这里因为时间关系就没有做了,其实我也是想做一个专门管理 hash 环的环状数据格式.
2.编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算 这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
调用端代码:
package com.example;
import com.example.hash.DefaultNodeManger;import com.example.redis.JedisFactory;import redis.clients.jedis.Jedis;
import java.util.ArrayList;import java.util.List;
public class Application {
public static void main(String[] args) { List<Integer> redisNodes = prepareRedisNodeList(); DefaultNodeManger nodeManger = new DefaultNodeManger(1500, redisNodes); System.out.println(nodeManger); long counter = 1000000L; long startTime = System.currentTimeMillis(); System.out.println("start at : " + startTime); String key = ""; Integer redisNode = null; Jedis operator = JedisFactory.prepareJedis(); while (counter >= 0) { key = "testHashInDemo" + counter; redisNode = nodeManger.getRedisNode(key); operator.select(redisNode); operator.set(key, "testDemoHash"); counter--; } long endTime = System.currentTimeMillis(); long cost = endTime - startTime; System.out.println("cost : " + cost); }
private static List<Integer> prepareRedisNodeList() { List<Integer> result = new ArrayList<Integer>(); for (int i = 0; i < 10; i++) { result.add(i); } return result; }}
复制代码
客户端代码利用本地 redis 的 0 到 9 这十个数据库作为缓存服务节点,循环将 100 万的数据写入到对应数据库中
在 DefaultNodeManger 的 init 方法中,开始计算虚拟节点的起始位置变量 startPosition 将其固定为 Integer 的最小值加一,不然每次算出来的标准差都不尽相同.
以下是结果:
可以看到,在这个情况下,一开始随着单个缓存服务节点的虚拟节点增多,标准差降低,而过了一定阈值后,反而上升,当然也有可能跟存入的 key 其实并不是乱序的有关.
而如果将 DefaultNodeManger 的 init 方法中,开始计算虚拟节点的起始位置变量 startPosition,进行调整,该值也随之变动,变化幅度也不低.
如果需要使用,可能要根据业务进行调整;虚拟节点的分布在 hash 环上应该要尽可能地达到最平均分布的状态
划线
评论
复制
发布于: 2020 年 10 月 24 日阅读数: 72
何毅曦
关注
还未添加个人签名 2019.03.20 加入
还未添加个人简介
评论