架构师训练营 Week5 - 课后作业

用户头像
关注
发布于: 2020 年 10 月 25 日
架构师训练营 Week5 - 课后作业

做业务实现多了,很久没有怎么接触算法代码了。参考了网上的实现花了接近一天才完成这个作业。



1. 一致性哈希环



这里不多说,老师在课上讲了。 上个图来表示下:



2. TreeMap 与 一致性Hash环

网上搜到的一致性hash实现大多都是通过TreeMap来实现的。感觉TreeMap展开是一条线,Root节点是最中间。有空研究下firstKey 和tailMap的逻辑再来扩充这部分的分析



3. 一致性Hash实现

https://github.com/SmileRR/Architect-001/tree/main/DistributeCache/src/main/java/org/eg

  • Consistent Hash Cluster实现

package org.eg;
import org.eg.cache.Cluster;
import org.eg.cache.Node;
import org.eg.hash.HashAlgorithm;
import java.util.ArrayList;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHashCluster extends Cluster {
private SortedMap<Long, Node> circle = new TreeMap<Long, Node>();
private final HashAlgorithm algorithm;
private final int numberOfReplicies;
public ConsistentHashCluster(HashAlgorithm algorithm, int numberOfReplicas) {
this.algorithm = algorithm;
this.numberOfReplicies = numberOfReplicas;
}
@Override
public void addNode(Node node) {
for (int i = 0; i < numberOfReplicies; i++) {
circle.put(algorithm.hash(node.toString() + i), node);
}
}
@Override
public void removeNode(Node node) {
for (int i = 0; i < numberOfReplicies; i++) {
circle.remove(algorithm.hash(node.toString() + i));
}
}
@Override
public List<Node> getNodes() {
List<Node> nodes = new ArrayList<Node>();
for (Node node: circle.values()) {
if (!nodes.contains(node))
nodes.add(node);
}
return nodes;
}
@Override
public Node get(String key) {
if (circle.isEmpty()) return null;
long hash = algorithm.hash(key);
//顺时针(正序)查找
if (! circle.containsKey(hash)) {
SortedMap<Long, Node> tailMap = circle.tailMap(hash);
hash = tailMap.isEmpty()?circle.firstKey():tailMap.firstKey();
}
return circle.get(hash);
}
}



4. 求100万KV, 10节点时的标准差

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

这里引用了很多不同的Hash算法,对比在不同数量虚拟节点是标准差和性能影响。可以看出虚拟节点数量的增加在达到某个值后就不在明显。150并非是所有Hash算法的最有解,但也是达到了某一个数量级。

同时对比性能影响,算法和虚拟节点导致标准差变小,性能也随之下降。所以需要选一个折衷点。



准备的测试代码准本来打算对每一种Hash算法做遍历测试找出本算法的最优虚拟节点数,轻视了每一次计算所花的时间,在等待了5分钟后暂时放弃了寻找最优的想法。通过图表了解了他们的区别,在需要时再集中测试吧。

额外提出一点,很有意思。试了好几遍,用NATIVE HASH 在只有原始节点时T1显然很突兀的在性能指标中花了更多的时间,CRC32 HASH也是同样问题。

测试代码:

package org.eg;
import org.eg.cache.Cluster;
import org.eg.cache.Node;
import org.eg.hash.HashAlgorithm;
import java.util.UUID;
public class TestCluster {
static final int DATA_SIZE = 1000000;
static final int NODE_SIZE = 10;
static final int REPLICIES_RANGE = 500;
public static void main(String[] args) {
long start = System.currentTimeMillis();
int virtalNodes = 1;
System.out.println("DataSize: " + DATA_SIZE + ", NodeSize: " + NODE_SIZE + ", VirtualNodes: " + virtalNodes);
new TestCluster().testHashAlgorithm(virtalNodes);
virtalNodes = 50;
System.out.println("DataSize: " + DATA_SIZE + ", NodeSize: " + NODE_SIZE + ", VirtualNodes: " + virtalNodes);
new TestCluster().testHashAlgorithm(virtalNodes);
virtalNodes = 100;
System.out.println("DataSize: " + DATA_SIZE + ", NodeSize: " + NODE_SIZE + ", VirtualNodes: " + virtalNodes);
new TestCluster().testHashAlgorithm(virtalNodes);
virtalNodes = 150;
System.out.println("DataSize: " + DATA_SIZE + ", NodeSize: " + NODE_SIZE + ", VirtualNodes: " + virtalNodes);
new TestCluster().testHashAlgorithm(virtalNodes);
virtalNodes = 300;
System.out.println("DataSize: " + DATA_SIZE + ", NodeSize: " + NODE_SIZE + ", VirtualNodes: " + virtalNodes);
new TestCluster().testHashAlgorithm(virtalNodes);
virtalNodes = 500;
System.out.println("DataSize: " + DATA_SIZE + ", NodeSize: " + NODE_SIZE + ", VirtualNodes: " + virtalNodes);
new TestCluster().testHashAlgorithm(virtalNodes);
virtalNodes = 1000;
System.out.println("DataSize: " + DATA_SIZE + ", NodeSize: " + NODE_SIZE + ", VirtualNodes: " + virtalNodes);
new TestCluster().testHashAlgorithm(virtalNodes);
// new TestCluster().identifyNoOfReplicies();
System.out.println("Time spent: " + (System.currentTimeMillis() - start));
}
// 测试各种Hash算法在100万K-V下
private void testHashAlgorithm(int replicies) {
for (HashAlgorithm alg : HashAlgorithm.values()) {
long start = System.currentTimeMillis();
Cluster cluster = new ConsistentHashCluster(alg, replicies);
setup(cluster);
long sdt = calcStandardDeviation(cluster);
System.out.println( alg + ", " + sdt + ", " + (System.currentTimeMillis()- start));
}
}
//识别最优虚拟节点数量,待优化
private void identifyNoOfReplicies() {
StringBuilder sb = new StringBuilder();
for (HashAlgorithm alg: HashAlgorithm.values()
) {
long bestSDT = Long.MAX_VALUE;
long bestNum = 1;
for (int i = 1; i < REPLICIES_RANGE; i++) {
long sdt = testHashAlgorithm(alg, i);
if(bestSDT > sdt) {
bestSDT = sdt;
bestNum = i;
}
}
System.out.println("Algorithm : " + alg + ", Best VirtualNodes: " + bestNum + ", StandardDeviation:" + bestSDT);
}
}
private long testHashAlgorithm(HashAlgorithm alg, int noOfReplicies) {
Cluster cluster = new ConsistentHashCluster(alg, noOfReplicies);
setup(cluster);
long sdt = calcStandardDeviation(cluster);
return sdt;
}
private void setup(Cluster cluster) {
for (int i = 0; i < NODE_SIZE; i++) {
cluster.addNode(new Node("c" + i, "192.168.0." + i));
}
for (int i = 0; i < DATA_SIZE; i++) {
String key = UUID.randomUUID().toString() + i;
String value = "value" + key;
cluster.get(key).put(key, value);
}
}
private long calcStandardDeviation(Cluster cluster) {
long sum = 0;
long avg = DATA_SIZE / NODE_SIZE;
for (Node node : cluster.getNodes()) {
sum += Math.pow((node.getData().size() - avg), 2);
}
long sdt = Math.round(Math.sqrt(sum / NODE_SIZE));
return sdt;
}
}



发布于: 2020 年 10 月 25 日 阅读数: 18
用户头像

关注

还未添加个人签名 2018.09.18 加入

还未添加个人简介

评论 (2 条评论)

发布
用户头像
童鞋,你的标签少了 架构师训练营第 1 期
2020 年 10 月 25 日 18:45
回复
好像是哦,多谢哈。好几次都给忘了,貌似没得改了
2020 年 10 月 25 日 21:02
回复
没有更多了
架构师训练营 Week5 - 课后作业