Consistent Hashing

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

将 id 对 360 取模，假如一开始有3台机器，那么让3台机器分别负责0~119, 120~239, 240~359 的三个部分。那么模出来是多少，查一下在哪个区间，就去哪台机器。 当机器从 n 台变为 n+1 台了以后，我们从n个区间中，找到最大的一个区间，然后一分为二，把一半给第n+1台机器。 比如从3台变4台的时候，我们找到了第3个区间0~119是当前最大的一个区间，那么我们把0~119分为0~59和60~119两个部分。0~59仍然给第1台机器，60~119给第4台机器。 然后接着从4台变5台，我们找到最大的区间是第3个区间120~239，一分为二之后，变为 120~179, 180~239。 假设一开始所有的数据都在一台机器上，请问加到第 n 台机器的时候，区间的分布情况和对应的机器编号分别是多少？

Notice

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

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]

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]
]

S：找到workload最重的机器，把他负责的区间分一半给新机器。

    vector<vector<int>> consistentHashing(int n) {
        // Write your code here
        vector<vector<int>> result(n, vector<int>(3, 0));
        if (n < 1) return result;
        result[0][1] = 359;
        result[0][2] = 1;
        for (int i = 1; i < n; ++i) {
            int index = 0;
            for (int j = 1; j < i; ++j) {
                if (result[j][1] - result[j][0] > 
                    result[index][1] - result[index][0]) {
                    index = j;    
                }
            }
            int x = result[index][0];
            int y = result[index][1];
            result[i][0] = (x + y) / 2 + 1;
            result[i][1] = y;
            result[i][2] = i + 1;
            result[index][1] = (x + y) /2;
        }
        return result;
    }

Consistent Hashing II

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

增加一台机器之后，数据全部从其中一台机器过来，这一台机器的读负载过大，对正常的服务会造成影响。 当增加到3台机器的时候，每台服务器的负载量不均衡，为1:1:2。 为了解决这个问题，引入了 micro-shards 的概念，一个更好的算法是这样：

将 360° 的区间分得更细。从 0~359 变为一个 0 ~ n-1 的区间，将这个区间首尾相接，连成一个圆。 当加入一台新的机器的时候，随机选择在圆周中撒 k 个点，代表这台机器的 k 个 micro-shards。 每个数据在圆周上也对应一个点，这个点通过一个 hash function 来计算。 一个数据该属于那台机器负责管理，是按照该数据对应的圆周上的点在圆上顺时针碰到的第一个 micro-shard 点所属的机器来决定。 n 和 k在真实的 NoSQL 数据库中一般是 2^64 和 1000。

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

create(int n, int k) addMachine(int machine_id) // add a new machine, return a list of shard ids. getMachineIdByHashCode(int hashcode) // return machine id Notice

当 n 为 2^64 时，在这个区间内随机基本不会出现重复。 但是为了方便测试您程序的正确性，n 在数据中可能会比较小，所以你必须保证你生成的 k 个随机数不会出现重复。

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

S: map + rand()

在存储random number和machine id的对应关系时用map而不是unordered_map，因为要用到map的lower_bound来划分一个随机的random number对应的有意义的random number。

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

    // @param machine_id an integer
    // @return a list of shard ids
    vector<int> addMachine(int machine_id) {
        // Write your code here
        vector<int> rand_nums;
        for (int i = 0; i < k; ++i) {
            int index = rand() % n;
            while (idx.find(index) != idx.end()) {
                index = rand() % n;
            }
            idx.insert(index);
            rand_nums.push_back(index);
            shards[index] = machine_id;
        }
        return rand_nums;
    }

    // @param hashcode an integer
    // @return a machine id
    int getMachineIdByHashCode(int hashcode) {
        // Write your code here
        auto it = shards.lower_bound(hashcode);
        if (it == shards.end()) {
            return shards.begin()->second;
        } else {
            return it->second;
        }
    }

private:
    int n;  // virtual range
    int k;  // real machine num
    set<int> idx;
    map<int, int> shards;  // use lower_bound has to use map not hashmap
};