五周 - 作业

关注
发布于: 2020 年 11 月 22 日
1、用你熟悉的编程语言实现一致性 hash 算法
1、ConsistentHash接口（一致性Hash），提供三个方法，说明见代码注释
2、Ring核心模型，提供三个方法：
   getLastSlot 根据value得到最近的Slot
   addSlots 增加slot到环上
   remove 从环上删除slot
3、Slot模型是关联Ring和Server的模型
4、Server模型：redis服务器以及它对于slot列表
5、ConsistentHashImpl 继承ConsistentHash接口，一致性hash的根对象
package com.test;
public interface ConsistentHash<T> {
    /**
     * 通过key获取最近的服务
     * @param key
     * @return
     */
    T getServerBy(int key);
    /**
     * 扩容
     * @param server  服务器
     * @param slots   服务器有多少插插
     * @return
     */
    boolean extend(T server,int slots);
    /**
     * 缩容
     * @param server
     * @return
     */
    boolean shrink(T server);
}
﻿
package com.test;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class ConsistentHashImpl implements ConsistentHash<Server>{
    private Ring<Server> ring = new Ring<Server>();
    private Random random = new Random();
    private int boud = Integer.MAX_VALUE;
    @Override
    public Server getServerBy(int key) {
        Slot<Server> res =  this.ring.getLastSlotBy(key);
        if(res == null){
            return null;
        }
        return res.getObject();
    }
    @Override
    public boolean extend(Server server, int slots) {
        List<Slot<Server>> slotList =  IntStream.rangeClosed(1,slots).boxed()
                .map(s -> random.nextInt(boud))
                .map(s -> new Slot<Server>(s,server))
                .collect(Collectors.toList());
        this.ring.addSlots(slotList);
        server.install(slotList);
        return true;
    }
    @Override
    public boolean shrink(Server server) {
        return false;
    }
}
﻿
package com.test;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ConcurrentSkipListSet;
import java.util.stream.Collectors;
public class Ring<T> {
    private ConcurrentSkipListSet<Slot<T>> slots = new ConcurrentSkipListSet<Slot<T>>();
    public Slot<T> getLastSlotBy(int value){
        Slot result =  this.slots.higher(new Slot(value));
        return result == null?this.slots.first():result;
    }
    public boolean addSlots(List<Slot<T>> slotList) {
        if(slotList == null){
            return false;
        }
        this.slots.addAll(slotList);
        return true;
    }
    public boolean addSlots(Slot<T>...slots) {
        if(slots == null){
            return false;
        }
        this.slots.addAll(Arrays.stream(slots).collect(Collectors.toList()));
        return true;
    }
    public void remove(List<Integer> args){
        this.slots.removeIf(s -> args.contains(s.getValue()));
    }
}
﻿
package com.test;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
public class Server {
    private Set<Slot<Server>> slots = new HashSet<>();
    private Map<String,String> map =  new ConcurrentHashMap<String,String>();
    public void install(Collection<Slot<Server>> slots){
        this.slots.addAll(slots);
    }
    /**
     * 模拟本地redis信息
     * @return
     */
    public Map<String,String> getServer(){
        return map;
    }
}
﻿
package com.test;
public class Slot<T> {
    private int value;
    private T obj;
    public Slot(int value){
        this.value = value;
    }
    public Slot(int value,T obj){
        this.value = value;
        this.obj = obj;
    }
    public int getValue(){
        return this.value;
    }
    public T getObject(){
        return this.obj;
    }
    @Override
    public boolean equals(Object obj) {
        if(obj == null || !obj.getClass().getName().equals(this.getClass().getName())){
            return false;
        }
        return (this.value == ((Slot)obj).value);
    }
    @Override
    public int hashCode(){
        return Integer.hashCode(value);
    }
}
﻿
此次实现存在的问题：扩容与缩容需要考虑失效节点的key的复制问题，对于扩容
2、编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性﻿
package com.test;
import junit.framework.TestCase;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class TestConsistentHashTemplate extends TestCase {
    public void test(int server,int slots){
        ConsistentHash<Server> consistentHash = new ConsistentHashImpl();
        List<Server> serverList = IntStream
                .rangeClosed(1,server)
                .boxed()
                .map(s -> new Server("test-" + s))
                .collect(Collectors.toList());
        serverList.forEach(s -> {
            consistentHash.extend(s,slots);
        });
        IntStream
                .rangeClosed(1,1000000).boxed()
                .map(s -> ThreadLocalRandom.current().nextInt(0,Integer.MAX_VALUE))
                .forEach(s -> {
                    consistentHash.getServerBy(s).getServer().put(String.valueOf(s),"test");
                });
        int total = serverList.stream().map(s -> s.getServer().size()).reduce((a,b) -> a + b).get();
        double avg = (total * 1.0) / serverList.size();
        double test = serverList.stream()
                .map(s -> s.getServer().size())
                .map(s -> Math.pow((Double.valueOf(String.valueOf(s)) - avg),2))
                .reduce((a,b) -> a + b)
                .get();
        double sqrt = Math.sqrt((test * 1.0) / server);
//        System.out.println("");
        System.out.println("sever: " + server + ",slots:" + slots + ",avg:" + avg + ",sqrt:" + sqrt);
//        serverList.forEach(s -> {
//            System.out.println(" server : " + s.name() + ",size:" + s.getServer().size());
//        });
    }
}
﻿
package com.test;
import junit.extensions.RepeatedTest;
import junit.framework.Test;
import junit.framework.TestSuite;
//import org.junit.Test
public class TestHash extends TestmianConsistentHashTemplate {
    public TestHash(String name){
        super(name);
    }
    public void test10150(){
        test(10,50);
        test(10,80);
        test(10,100);
        test(10,150);
       
        test(10,180);
        test(10,300);
        test(10,500);
        test(10,1000);
    }
    public static Test suite() {
        TestSuite suite = new TestSuite();
//        suite.addTestSuite(TestHash.class);
        suite.addTest(new RepeatedTest(new TestHash("test10150"), 5));
        return suite;
    }
}
﻿
sever: 10,slots:50,avg:99980.2,sqrt:12866.575370315133
sever: 10,slots:80,avg:99978.7,sqrt:8769.490955009875
sever: 10,slots:100,avg:99975.1,sqrt:6990.2230500893165
sever: 10,slots:150,avg:99980.1,sqrt:6885.032235944869
sever: 10,slots:180,avg:99975.2,sqrt:12323.630258978075
sever: 10,slots:300,avg:99975.7,sqrt:5426.428034167596
sever: 10,slots:500,avg:99974.1,sqrt:2654.76610834175
sever: 10,slots:1000,avg:99975.7,sqrt:3977.9919570054435
﻿
﻿
sever: 10,slots:50,avg:99976.7,sqrt:14060.74347287511
sever: 10,slots:80,avg:99976.2,sqrt:10621.502358894431
sever: 10,slots:100,avg:99976.9,sqrt:13319.230266423056
sever: 10,slots:150,avg:99976.9,sqrt:4662.1964662592245
sever: 10,slots:180,avg:99977.6,sqrt:4851.21725343238
sever: 10,slots:300,avg:99975.3,sqrt:4642.435245644251
sever: 10,slots:500,avg:99978.6,sqrt:3377.8866233193794
sever: 10,slots:1000,avg:99975.7,sqrt:2974.4742745567664
﻿
sever: 10,slots:50,avg:99975.5,sqrt:11962.584054041166
sever: 10,slots:80,avg:99977.8,sqrt:11680.795733168181
sever: 10,slots:100,avg:99977.5,sqrt:8211.524258625801
sever: 10,slots:150,avg:99975.8,sqrt:10154.13366861004
sever: 10,slots:180,avg:99977.0,sqrt:10342.977617688244
sever: 10,slots:300,avg:99976.4,sqrt:5622.732061907272
sever: 10,slots:500,avg:99976.3,sqrt:5391.493152179644
sever: 10,slots:1000,avg:99980.1,sqrt:2687.7658175518195
﻿
sever: 10,slots:50,avg:99976.2,sqrt:12259.688803554518
sever: 10,slots:80,avg:99979.7,sqrt:14968.79838898233
sever: 10,slots:100,avg:99975.4,sqrt:10147.520201507361
sever: 10,slots:150,avg:99974.7,sqrt:8438.483478090124
sever: 10,slots:180,avg:99979.9,sqrt:8620.77942473881
sever: 10,slots:300,avg:99975.8,sqrt:4497.783160624798
sever: 10,slots:500,avg:99973.9,sqrt:4418.43231135207
sever: 10,slots:1000,avg:99978.5,sqrt:2207.7366804037115
﻿
sever: 10,slots:50,avg:99978.6,sqrt:10989.908636562908
sever: 10,slots:80,avg:99975.4,sqrt:12967.501649893862
sever: 10,slots:100,avg:99977.6,sqrt:9905.221150484223
sever: 10,slots:150,avg:99979.0,sqrt:7695.901831494474
sever: 10,slots:180,avg:99977.1,sqrt:6079.045590386701
sever: 10,slots:300,avg:99978.3,sqrt:5051.480675010051
sever: 10,slots:500,avg:99976.4,sqrt:3827.9343045564406
sever: 10,slots:1000,avg:99978.7,sqrt:2171.5212202509097
﻿
﻿
发布于: 2020 年 11 月 22 日阅读数: 30
水浴清风

关注
还未添加个人签名 2018.05.16 加入
还未添加个人简介
发布
暂无评论
创作场景

五周 - 作业

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

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

水浴清风

评论
