Consistent Hashing

1. Introduction

Consistent Hashing is used for horizontal sharding, check here for mode details

2.Simple Version

• Idea: Check the description in LintCode

• Implementation: Lintcode Consistent Hashing

    public List<List<Integer>> consistentHashing(int n) {
        List<Integer> machine = new ArrayList<>();
        machine.add(0);
        machine.add(359);
        machine.add(1);
        res.add(machine);

        for (int i = 1; i < n; i++) {
            List<Integer> nextMachine = new ArrayList<>();
            int index = 0;

            // Look for the largest interval
            for (int j = 1; j < i; j++) {
                int nextInterval = res.get(j).get(1) - res.get(j).get(0) + 1;
                int curInterval = res.get(index).get(1) - res.get(index).get(0) + 1;

                if (curInterval < nextInterval) {
                    index = j;
                }
            }

            // Divide the largest interval into havles
            int start = res.get(index).get(0);
            int end = res.get(index).get(1);
            res.get(index).set(1, (start + end)/2);

            // The other half will be assigned to the new machine
            nextMachine.add((start + end)/2 + 1);
            nextMachine.add(end);
            nextMachine.add(i + 1);
            res.add(nextMachine);
        }
        return res;
    }

3. Better version

• Idea: Check the description in LintCode

• Implementation: Lintcode Consistent Hashing II

import java.util.*;

public class ConsistentHashing {
    // Number of interval
    private int n;
    // Number of virtual nodes for each machine
    private int k;
    // Set to store k distinct virtual nodes for a new mahine 
    private Set<Integer> ids = null;
    // Map to store a list of virtual nodes for a machine
    private Map<Integer, List<Integer>> machines = null;

    public ConsistentHashing(int n, int k) {
        this.n = n;
        this.k = k;
        ids = new HashSet<>();
        machines = new HashMap<>();
    }

    public List<Integer> addMachine(int machineId) {
        Random rand = new Random();
        List<Integer> virtualNodes = new ArrayList<>();
        int nodeId = 0;

        //Randomly create k distinct virtual nodes
        for (int i = 0; i < k; i++) {
            nodeId = rand.nextInt(n);

            while(ids.contains(nodeId)) {
                nodeId = rand.nextInt(n);
            }
            ids.add(nodeId);
            virtualNodes.add(nodeId);
        }

        Collections.sort(virtualNodes);
        machines.put(machineId, virtualNodes);

        System.out.print("virtual nodes for machine " + machineId + " : ");
        for (int node : virtualNodes) {
             System.out.print(node + " ");
        }
        System.out.println();
        return virtualNodes;
    }

    public int getMachineIdByHashCode(int hashCode) {
        // Initialize distance with max possible value (the distance on the circle will be no more than n)
        int distance = n + 1;
        int diff = 0;
        int machineId = 0;

        for (Map.Entry<Integer, List<Integer>> entry : machines.entrySet()) {
            int key = entry.getKey();
            List<Integer> virtualNodes = entry.getValue();

            for (int nodeId : virtualNodes) {
                diff = nodeId - hashCode;

                // Offset diff by n since we will route data to closest machine clockwise
                if (diff < 0) {
                    diff += n;
                }

                // Update the distance and the closet clockwise machine in that distance
                if (diff < distance) {
                    distance = diff;
                    machineId = key;
                }
            }
        }
        System.out.println("Data is routed to machine " + machineId);
        // Return the closest clockwise machine given the hashCode
        return machineId;
    }


    public static void main(String[] args) {
        ConsistentHashing hash = new ConsistentHashing(100, 3);
        hash.addMachine(1);
        hash.addMachine(2);
        hash.addMachine(3);
        hash.getMachineIdByHashCode(60);
        hash.getMachineIdByHashCode(95);
    }
}