架构师课作业 - 第五周

发布于: 20 小时前

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

整体思路是, 分为两个实体类 (服务节点 与 子类:虚拟节点) , 两个服务类 (一致性hash算法 与 子类:含虚拟节点的一致性hash算法)

  • ServiceNode类: 服务节点, 定义服务节点的名称、ip地址等

  • VirtualServiceNode类: 虚拟节点, 继承ServiceNode类

  • ConsistentHash类: 一致性hash算法, 仅是针对服务节点

  • VirtualConsistentHash类: 一致性hash算法, 包含虚拟节点

/**
* 服务节点
*/
public class ServiceNode {
// 节点ID
private String nodeId;
// 节点名称
private String nodeName;
// 节点IP
private String ipAddress;
public ServiceNode(String nodeId, String nodeName, String ipAddress) {
this.nodeId = nodeId;
this.nodeName = nodeName;
this.ipAddress = ipAddress;
}
public String getNodeId() {
return nodeId;
}
public String getNodeName() {
return nodeName;
}
public String getIpAddress() {
return ipAddress;
}
}

/**
* 虚拟服务节点
*/
public class VirtualServiceNode extends ServiceNode {
private boolean virtualTag;
private ServiceNode realServiceNode;
public VirtualServiceNode(String nodeId, String nodeName, String ipAddress, ServiceNode serviceNode) {
super(nodeId, nodeName, ipAddress);
virtualTag = true;
realServiceNode = serviceNode;
}
public boolean isVirtualTag() {
return virtualTag;
}
public ServiceNode getRealServiceNode() {
return realServiceNode;
}
}

/**
* 一致性Hash算法
*/
public class ConsistentHash {
private final SortedMap<Integer, ServiceNode> sortedMap;
public ConsistentHash() {
this.sortedMap = new TreeMap<Integer, ServiceNode>();
}
/**
* 根据服务节点, 构建一致性Hash环
* @param serviceNodes
*/
public void buildHashRing(List<ServiceNode> serviceNodes){
for (ServiceNode serviceNode : serviceNodes) {
increaseServiceNode(serviceNode);
}
System.out.println("一致性Hash环构建完毕");
}
/**
* Hash环增加节点
* @param serviceNode
*/
public void increaseServiceNode(ServiceNode serviceNode){
final int hash = getHash(serviceNode.getNodeId());
System.out.println("[" + serviceNode.getNodeName() + "]加入集合中, 其Hash值为" + hash);
sortedMap.put(hash, serviceNode);
}
/**
* Hash环减少节点
* @param serviceNode
*/
public void reduceServiceNode(ServiceNode serviceNode){
final int hash = getHash(serviceNode.getNodeId());
System.out.println("[" + serviceNode.getNodeName() + "]从集合中移除, 其Hash值为" + hash);
sortedMap.remove(hash);
}
/**
* 查找节点
* @param key
* @return
*/
public ServiceNode getServiceNode(String key){
final int hash = getHash(key);
final SortedMap<Integer, ServiceNode> serviceNodeSortedMap = sortedMap.tailMap(hash);
if(serviceNodeSortedMap.isEmpty()){
final ServiceNode serviceNode = sortedMap.get(sortedMap.firstKey());
System.out.println("未找到节点, 取首个节点[" + serviceNode.getNodeName() + "]");
return sortedMap.get(sortedMap.firstKey());
}
final ServiceNode serviceNode = serviceNodeSortedMap.get(serviceNodeSortedMap.firstKey());
System.out.println("找到节点[" + serviceNode.getNodeName() + "]");
return serviceNode;
}
private static int getHash(String str) {
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < str.length(); i++)
hash = (hash ^ str.charAt(i)) * 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;
}
}

/**
* 一致性Hash算法 (包含虚拟节点)
*/
public class ConsistentHashWithVirtualNode extends ConsistentHash {
/**
* 虚拟节点数
*/
private final int virtualNum;
public ConsistentHashWithVirtualNode(int virtualNum) {
this.virtualNum = virtualNum;
}
/**
* 增加节点 (包括虚拟节点)
* @param serviceNode
*/
@Override
public void increaseServiceNode(ServiceNode serviceNode) {
super.increaseServiceNode(serviceNode);
// 虚拟节点新增
final List<ServiceNode> virtualServiceNode = getVirtualServiceNode(serviceNode);
for (ServiceNode virServiceNode : virtualServiceNode) {
super.increaseServiceNode(virServiceNode);
}
}
/**
* 减少节点 (包括虚拟节点)
* @param serviceNode
*/
@Override
public void reduceServiceNode(ServiceNode serviceNode) {
super.reduceServiceNode(serviceNode);
// 虚拟节点删除
final List<ServiceNode> virtualServiceNode = getVirtualServiceNode(serviceNode);
for (ServiceNode virServiceNode : virtualServiceNode) {
super.reduceServiceNode(virServiceNode);
}
}
/**
* 根据服务节点, 构建虚拟节点集合
* @param serviceNode
* @return
*/
private List<ServiceNode> getVirtualServiceNode(ServiceNode serviceNode){
List<ServiceNode> serviceNodes = new ArrayList<>(virtualNum);
for (int i = 0; i < virtualNum; i++) {
VirtualServiceNode virtualServiceNode = new VirtualServiceNode(
serviceNode.getNodeId() + "." + i,
serviceNode.getNodeName() + "." + i,
serviceNode.getIpAddress(),
serviceNode);
serviceNodes.add(virtualServiceNode);
}
return serviceNodes;
}
}

实际使用方式:

public class ZTest {
static final ServiceNode serviceNodeTest = new ServiceNode("TEST", "节点TEST", "192.168.0.255");
public static void main(String[] args) {
ConsistentHash consistentHash = new ConsistentHashWithVirtualNode(2);
consistentHash.buildHashRing(buildServiceNodes());
// 新增节点
consistentHash.increaseServiceNode(serviceNodeTest);
// 删除节点
consistentHash.reduceServiceNode(serviceNodeTest);
// 查找节点
consistentHash.getServiceNode(UUID.randomUUID().toString().replaceAll("-", ""));
consistentHash.getServiceNode(UUID.randomUUID().toString().replaceAll("-", ""));
consistentHash.getServiceNode(UUID.randomUUID().toString().replaceAll("-", ""));
}
private static List<ServiceNode> buildServiceNodes() {
List<ServiceNode> serviceNodes = new ArrayList<>();
for (int i = 0; i < 10; i++) {
serviceNodes.add(new ServiceNode(
UUID.randomUUID().toString().replaceAll("-", ""),
"节点" + (char) (65 + i),
"192.168.0." + i));
}
return serviceNodes;
}
}

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

用例代码如下

public class ZTest {
public static void main(String[] args) {
ConsistentHash consistentHash = new ConsistentHashWithVirtualNode(150);
consistentHash.buildHashRing(buildServiceNodes());
// 循环100万次
Map<ServiceNode, Integer> map = new HashMap<>();
for (int i = 0; i < 1000000; i++) {
ServiceNode serviceNode = consistentHash.getServiceNode(UUID.randomUUID().toString().replaceAll("-", ""));
if (serviceNode instanceof VirtualServiceNode) {
// 通过虚拟节点找到真实服务节点
serviceNode = ((VirtualServiceNode) serviceNode).getRealServiceNode();
}
// 统计KV分布到服务节点的次数
final Integer num = map.getOrDefault(serviceNode, 0);
map.put(serviceNode, num + 1);
}
// 打印各个节点被分配次数
int[] nums = new int[10];
int i = 0;
for (Map.Entry<ServiceNode, Integer> entry : map.entrySet()) {
nums[i++] = entry.getValue();
System.out.println("节点[" + entry.getKey().getNodeName() + "] 分配到次数: " + entry.getValue());
}
// 标准差
final double deviation = standardDeviation(nums);
System.out.println("标准差为: " + deviation);
}
private static List<ServiceNode> buildServiceNodes() {
List<ServiceNode> serviceNodes = new ArrayList<>();
for (int i = 0; i < 10; i++) {
serviceNodes.add(new ServiceNode(
UUID.randomUUID().toString().replaceAll("-", ""),
"节点" + (char) (65 + i),
"192.168.0." + i));
}
return serviceNodes;
}
/**
* 标准差
* @param array
* @return
*/
public static double standardDeviation(int[] array) {
int sum = 0;
for (int i = 0; i < array.length; i++) {
sum += array[i];
}
double average = sum / array.length;
int total = 0;
for (int i = 0; i < array.length; i++) {
total += (array[i] - average) * (array[i] - average);
}
return Math.sqrt(total / array.length);
}
}

结果得出标准差如下

用户头像

Tulane

关注

还未添加个人签名 2018.09.18 加入

还未添加个人简介

评论

发布
暂无评论
架构师课作业 - 第五周