# Consistent Hashing

### [Consistent Hashing - I](https://www.lintcode.com/problem/consistent-hashing)

一般的数据库进行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

```java
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)

```java
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)

```java
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](https://www.toptal.com/big-data/consistent-hashing) - Toptal BY JUAN PABLO CARZOLIO

[Tom White' Consistent Hashing](http://www.tom-e-white.com/2007/11/consistent-hashing.html)

["面试必备：什么是一致性Hash算法？"](https://zhuanlan.zhihu.com/p/34985026)

[每天进步一点点——五分钟理解一致性哈希算法(consistent hashing)](https://blog.csdn.net/cywosp/article/details/23397179) CSDN Blog - cywosp

[System Design Interview Concepts – Consistent Hashing](https://www.acodersjourney.com/system-design-interview-consistent-hashing/) by A Coder's Journey - Deb Haldar

[Distributed Systems in One Lesson](https://learning.oreilly.com/videos/distributed-systems-in/9781491924914/9781491924914-video215265) - O'reily Safari Online

[The Simple Magic of Consistent Hashing](https://www.paperplanes.de/2011/12/9/the-magic-of-consistent-hashing.html) by Mathias Meyer


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/system-design/distributed-systems/consistent-hashing.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.