[LintCode][System Design] Consistent Hashing - 简书
一般的数据库进行horizontal shard的方法是指，把 id 对 数据库服务器总数 n 取模，然后来得到他在哪台机器上。这种方法的缺点是，当数据继续增加，我们需要增加数据库服务器，将 n 变为 n+1 时，几乎所有的数据都要移动，这就造成了不 consistent。为了减少这种 naive 的 hash方法(%n) 带来的缺陷，出现了一种新的hash算法：一致性哈希的算法――Consistent Hashing。这种算法有很多种实现方式，这里我们来实现一种简单的 Consistent Hashing。
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:
for n =
for n =
// Write your code here
vector<vector<int>> ret;
vector<int> range;
range.push_back(0);
range.push_back(359);
range.push_back(1);
ret.push_back(range);
for(int i = 2; i <= n; i++) {
int maxRange = INT_MIN;
int index = -1;
for(int j = 0; j < ret.size(); j++) {
if (maxRange < ret[j][1] - ret[j][0]) {
maxRange = ret[j][1] - ret[j][0];
index = j;
}
}
int mid = (ret[index][1] + ret[index][0]) / 2;
int end = ret[index][1];
ret[index][1] = mid;
range[0] = mid + 1;
range[1] = end;
range[2] = i;
ret.push_back(range);
}
return ret;
}
Read full article from [LintCode][System Design] 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。
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]for n =
1, return[
[0,359,1]
]for n =
2, return[
[0,179,1],
[180,359,2]
]3, return[
[0,89,1]
[90,179,3],
[180,359,2]
]4, return[
[0,89,1],
[90,179,3],
[180,269,2],
[270,359,4]
]5, return[
[0,44,1],
[45,89,1],
[90,179,3],
[180,269,2],
[270,359,4]
]
模拟的方法，每次选取最大的range，然后插入新的range。
vector<vector<int>> consistentHashing(int n) {// Write your code here
vector<vector<int>> ret;
vector<int> range;
range.push_back(0);
range.push_back(359);
range.push_back(1);
ret.push_back(range);
for(int i = 2; i <= n; i++) {
int maxRange = INT_MIN;
int index = -1;
for(int j = 0; j < ret.size(); j++) {
if (maxRange < ret[j][1] - ret[j][0]) {
maxRange = ret[j][1] - ret[j][0];
index = j;
}
}
int mid = (ret[index][1] + ret[index][0]) / 2;
int end = ret[index][1];
ret[index][1] = mid;
range[0] = mid + 1;
range[1] = end;
range[2] = i;
ret.push_back(range);
}
return ret;
}
Read full article from [LintCode][System Design] Consistent Hashing - 简书
