Consistent Hashing

Consistent Hashing - I

一般的数据库进行horizontal shard的方法是指，把 id 对 数据库服务器总数 n 取模，然后来得到他在哪台机器上。这种方法的缺点是，当数据继续增加，我们需要增加数据库服务器，将 n 变为 n+1 时，几乎所有的数据都要移动，这就造成了不 consistent。为了减少这种 naive 的 hash方法(%n) 带来的缺陷，出现了一种新的hash算法：一致性哈希的算法——Consistent Hashing。这种算法有很多种实现方式，这里我们来实现一种简单的 Consistent Hashing。

1. 将 id 对 360 取模，假如一开始有3台机器，那么让3台机器分别负责0~119, 120~239, 240~359 的三个部分。那么模出来是多少，查一下在哪个区间，就去哪台机器。

2. 当机器从 n 台变为 n+1 台了以后，我们从n个区间中，找到最大的一个区间，然后一分为二，把一半给第n+1台机器。

3. 比如从3台变4台的时候，我们找到了第3个区间0~119是当前最大的一个区间，那么我们把0~119分为0~59和60~119两个部分。0~59仍然给第1台机器，60~119给第4台机器。

4. 然后接着从4台变5台，我们找到最大的区间是第3个区间120~239，一分为二之后，变为 120~179, 180~239。

假设一开始所有的数据都在一台机器上，请问加到第 n 台机器的时候，区间的分布情况和对应的机器编号分别是多少？

Example

for n = 1, return

[
  [0,359,1]
]
represent 0~359 belongs to machine 1.

for n = 2, return

[
  [0,179,1],
  [180,359,2]
]
for n = 3, return

[
  [0,89,1]
  [90,179,3],
  [180,359,2]
]
for n = 4, return

[
  [0,89,1],
  [90,179,3],
  [180,269,2],
  [270,359,4]
]
for n = 5, return

[
  [0,44,1],
  [45,89,5],
  [90,179,3],
  [180,269,2],
  [270,359,4]
]

Clarification

If the maximal interval is [x, y], and it belongs to machine id z, when you add a new machine with id n, you should divide [x, y, z] into two intervals:

[x, (x + y) / 2, z]and[(x + y) / 2 + 1, y, n]

Notice

你可以假设 n <= 360. 同时我们约定，当最大区间出现多个时，我们拆分编号较小的那台机器。 比如0~119， 120~239区间的大小都是120，但是前一台机器的编号是1，后一台机器的编号是2, 所以我们拆分0~119这个区间。

Solution

public class Solution {
    /*
     * @param n: a positive integer
     * @return: n x 3 matrix
     */
    public List<List<Integer>> consistentHashing(int n) {
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        List<Integer> machine = new ArrayList<Integer>();
        machine.add(0);
        machine.add(359);
        machine.add(1);
        results.add(machine);
        for (int i = 1; i < n; i++) {
            List<Integer> newMachine = new ArrayList<Integer>();
            int maxIntervalIndex = 0;
            for (int j = 0; j < i; j++) {
                if (results.get(j).get(1) - results.get(j).get(0) > results.get(maxIntervalIndex).get(1) - results.get(maxIntervalIndex).get(0)) {
                    maxIntervalIndex = j;
                }
            }
            int x = results.get(maxIntervalIndex).get(0);
            int y = results.get(maxIntervalIndex).get(1);
            results.get(maxIntervalIndex).set(1, (x + y) / 2);

            newMachine.add((x + y) / 2 + 1);
            newMachine.add(y);
            newMachine.add(i + 1);
            results.add(newMachine);
        }
        return results;
    }

}

Consistent Hashing - II

Description

在 Consistent Hashing I 中我们介绍了一个比较简单的一致性哈希算法，这个简单的版本有两个缺陷：

1. 增加一台机器之后，数据全部从其中一台机器过来，这一台机器的读负载过大，对正常的服务会造成影响。

2. 当增加到3台机器的时候，每台服务器的负载量不均衡，为1:1:2。

为了解决这个问题，引入了 micro-shards 的概念，一个更好的算法是这样：

1. 将 360° 的区间分得更细。从 0~359 变为一个 0 ~ n-1 的区间，将这个区间首尾相接，连成一个圆。

2. 当加入一台新的机器的时候，随机选择在圆周中撒 k 个点，代表这台机器的 k 个 micro-shards。

3. 每个数据在圆周上也对应一个点，这个点通过一个 hash function 来计算。

4. 一个数据该属于那台机器负责管理，是按照该数据对应的圆周上的点在圆上顺时针碰到的第一个 micro-shard 点所属的机器来决定。

n 和 k在真实的 NoSQL 数据库中一般是 2^64 和 1000。

请实现这种引入了 micro-shard 的 consistent hashing 的方法。主要实现如下的三个函数：

1. create(int n, int k)

2. addMachine(int machine_id) // add a new machine, return a list of shard ids.

3. getMachineIdByHashCode(int hashcode) // return machine id

当 n 为 2^64 时，在这个区间内随机基本不会出现重复。
但是为了方便测试您程序的正确性，n 在数据中可能会比较小，所以你必须保证你生成的 k 个随机数不会出现重复。
LintCode并不会判断你addMachine的返回结果的正确性（因为是随机数），只会根据您返回的addMachine的结果判断你getMachineIdByHashCode结果的正确性。

Example

create(100, 3)
addMachine(1)
>> [3, 41, 90]  => 三个随机数
getMachineIdByHashCode(4)
>> 1
addMachine(2)
>> [11, 55, 83]
getMachineIdByHashCode(61)
>> 2
getMachineIdByHashCode(91)
>> 1

Solution

Using HashMap (machine_id as key, random numbers as value)

public class Solution {

    public int n, k;
    public Set<Integer> ids = null;
    public Map<Integer, List<Integer>> machines = null;

    // @param n a positive integer
    // @param k a positive integer
    // @return a Solution object
    public static Solution create(int n, int k) {
        // Write your code here
        Solution solution = new Solution();
        solution.n = n;
        solution.k = k;
        solution.ids = new TreeSet<Integer>();
        solution.machines = new HashMap<Integer, List<Integer>>();
        return solution;
    }

    // @param machine_id an integer
    // @return a list of shard ids
    public List<Integer> addMachine(int machine_id) {
        // Write your code here
        Random ra =new Random();
        List<Integer> random_nums = new ArrayList<Integer>();
        for (int i = 0; i < k; ++i) {
            int index = ra.nextInt(n);
            while (ids.contains(index))
                index = ra.nextInt(n);
            ids.add(index);
            random_nums.add(index);
        }

        Collections.sort(random_nums);
        machines.put(machine_id, random_nums);
        return random_nums;
    }

    // @param hashcode an integer
    // @return a machine id
    public int getMachineIdByHashCode(int hashcode) {
        // Write your code here
        int distance = n + 1;
        int machine_id = 0;
        for (Map.Entry<Integer, List<Integer>> entry : machines.entrySet()) {
            int key = entry.getKey();
            List<Integer> random_nums = entry.getValue();
            for (Integer num : random_nums) {
                int d = num - hashcode;
                if (d < 0)
                    d += n;
                if (d < distance) {
                    distance = d;
                    machine_id = key;
                }
            }
        }
        return machine_id;
    }
}

https://www.jiuzhang.com/solution/consistent-hashing-ii/#tag-highlight

Using TreeMap (random numbers as key, machine_id as value in the treemap)

public class Solution {

    private TreeMap<Integer, Integer> tm = new TreeMap<>();

    private int[] nums;
    private int size = 0;
    private int k;

    public Solution(int n, int k) {
        this.nums = new int[n];
        for(int i = 0; i < n; i++) this.nums[i] = i;

        Random random = new Random();
        for(int i = 0; i < n; i++) {
            int j = random.nextInt(i + 1);
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
        this.k = k;
    }

    // @param n a positive integer
    // @param k a positive integer
    // @return a Solution object
    public static Solution create(int n, int k) {
        // Write your code here
        return new Solution(n, k);
    }

    // @param machine_id an integer
    // @return a list of shard ids
    public List<Integer> addMachine(int machine_id) {
        // Write your code here
        List<Integer> ids = new ArrayList<>();
        for(int i = 0; i < this.k; i++) {
            int id = this.nums[size++ % this.nums.length];
            ids.add(id);
            this.tm.put(id, machine_id);
        }
        return ids;
    }

    // @param hashcode an integer
    // @return a machine id
    public int getMachineIdByHashCode(int hashcode) {
        // Write your code here
        if (tm.isEmpty()) return 0;
        Integer ceiling = tm.ceilingKey(hashcode);
        if (ceiling != null) return tm.get(ceiling);
        return tm.get(tm.firstKey());
    }
}
--------------------- 
作者：jmspan 
来源：CSDN 
原文：https://blog.csdn.net/jmspan/article/details/51749521 
版权声明：本文为博主原创文章，转载请附上博文链接！

Reference

Consistent Hashing - Toptal BY JUAN PABLO CARZOLIO

Tom White' Consistent Hashing

"面试必备：什么是一致性Hash算法？"

每天进步一点点——五分钟理解一致性哈希算法(consistent hashing) CSDN Blog - cywosp

System Design Interview Concepts – Consistent Hashing by A Coder's Journey - Deb Haldar

Distributed Systems in One Lesson - O'reily Safari Online

The Simple Magic of Consistent Hashing by Mathias Meyer