写点什么

一致性哈希算法实现

用户头像
John
关注
发布于: 2020 年 07 月 13 日
  • 用你熟悉的编程语言实现一致性 hash 算法。

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


实现一致性哈希算法,哈希算法和路由算法可插拔

public class ConsistenceHashClient {    private int virtualNodeCount = 100;    private Router router;    private Hash hash;    private List<Machine> machineList = new ArrayList<>();
public ConsistenceHashClient(Router router, Hash hash, List<Machine> machineList){ this.hash = hash; this.router = router; for (Machine machine : machineList){ addMachine(machine); } }
public void addMachine(Machine machine){ machineList.add(machine); for (int i = 0; i < virtualNodeCount; i++) { int hashcode = hash.hash(machine.getMachineId() + i); router.addNode(new Node(machine, hashcode)); } }
public void removeMachine(Machine machine){ machineList.remove(machine); for (int i = 0; i < virtualNodeCount; i++) { int hashcode = hash.hash(machine.getMachineId() + i); router.removeNode(new Node(machine, hashcode)); } }
public Machine route(String key){ Node node = router.route(hash.hash(key)); return node.getMachine(); }
public void set(String key, String value) { Node node = router.route(hash.hash(key)); node.set(key, value); }
public double variance() { double variance = 0; double aver = average(); for (Machine machine : machineList) { variance += Math.pow(machine.countKey() - aver, 2); } return variance / machineList.size(); }
public double average(){ int total = 0; for (Machine machine : machineList) { System.out.println(machine.countKey()); total += machine.countKey(); } return (double)total / machineList.size(); }
}
public class Machine { private String machineId; private List<Node> nodes;
public Machine(String machineId) { this.machineId = machineId; nodes = new ArrayList<>(); } public String getMachineId(){ return machineId; }
public void setMachineId(String machineId){ this.machineId = machineId; }
public void addNode(Node node) { nodes.add(node); }
public int countKey(){ int count = 0; for (Node node : nodes) { count += node.size(); } return count; }
public boolean equals(Machine machine){ return machine.getMachineId().equals(this.machineId); }}
public class Node implements Comparable<Node>{ private int hashcode; private Machine machine; private Map<String, String> cache = new HashMap<>();;
public Node(Machine machine, int hashcode) { this.machine = machine; this.hashcode = hashcode; machine.addNode(this); }
public int getHashcode(){ return hashcode; }
public Machine getMachine(){ return machine; }
public void set(String key, String value){ cache.put(key, value); }
public void remove(String key){ cache.remove(key); }
public int size(){ return cache.size(); }
public int compareTo(Node node){ return this.hashcode - node.hashcode; }}

复制代码

哈希算法

public interface Hash {    public int hash(String key);}
public class FNV132Hash implements Hash{ public int hash(String key) { final int p = 16777619; int hash = (int) 2166136261L; for (byte b : key.getBytes()) hash = (hash ^ b) * p; hash += hash << 13; hash ^= hash >> 7; hash += hash << 3; hash ^= hash >> 17; hash += hash << 5; return hash; }}
复制代码

路由算法

public interface Router {    public Node route(int hashcode);
public void addNode(Node node);
public void removeNode(Node node);}
public class RedBlackTreeRouter implements Router { private TreeMap<Integer, Node> nodes = new TreeMap<>();
public RedBlackTreeRouter(){ }
public Node route(int hashcode){ Map.Entry<Integer, Node> entry = nodes.ceilingEntry(hashcode); if (entry == null) { entry = nodes.firstEntry(); } return entry.getValue(); }
public void addNode(Node node){ nodes.put(node.getHashcode(), node); }
public void removeNode(Node node){ nodes.remove(node.getHashcode()); }}
复制代码


测试程序

public class Test {    public static void main(String[] args) {        Router router = new BinarySearchRouter();        Hash hash = new FNV132Hash();        List<Machine> machineList = new ArrayList<>();        for (int i = 0; i < 10; i++){            String machineId = "machine" + i;            machineList.add(new Machine(machineId));        }        ConsistenceHashClient client = new ConsistenceHashClient(router, hash, machineList);        for (int i  = 0; i < 1000000; i++) {            String key = "key" + i;            String value = "Value" + i;            client.set(key, value);         }        double var = client.variance();        System.out.println(var);    }}
复制代码

方差:8.38164538E7

用户头像

John

关注

还未添加个人签名 2018.04.29 加入

还未添加个人简介

评论

发布
暂无评论
一致性哈希算法实现