一致性哈希算法实现

发布于: 22 小时前

  • 用你熟悉的编程语言实现一致性 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 加入

还未添加个人简介

评论

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