[LintCode][System Design] Consistent Hashing II - 简书
在 Consistent Hashing I 中我们介绍了一个比较简单的一致性哈希算法,这个简单的版本有两个缺陷:
请实现这种引入了 micro-shard 的 consistent hashing 的方法。主要实现如下的三个函数:
文/chk(简书作者)
原文链接:http://www.jianshu.com/p/4b39053a7a24
著作权归作者所有,转载请联系作者获得授权,并标注“简书作者”。
class Solution {
private:
static int shardNum;
static int microShardNum;
static vector<int> shard2mach;
public:
// @param n a positive integer
// @param k a positive integer
// @return a Solution object
static Solution create(int n, int k) {
shardNum = n;
microShardNum = k;
shard2mach.resize(n);
for(int i = 0; i < n; i++) {
shard2mach[i] = -1;
}
}
// @param machine_id an integer
// @return a list of shard ids
vector<int> addMachine(int machine_id) {
srand(time(NULL));
int count = 0;
vector<int> ret;
while(count < microShardNum) {
int number = rand() % shardNum;
if (shard2mach[number] == -1) {
count++;
shard2mach[number] = machine_id;
ret.push_back(number);
}
}
return ret;
}
// @param hashcode an integer
// @return a machine id
int getMachineIdByHashCode(int hashcode) {
int i = hashcode;
while(true) {
if (i == shardNum) {
i = 0;
}
if (shard2mach[i] != -1) {
return shard2mach[i];
}
i++;
}
}
};
int Solution::shardNum;
int Solution::microShardNum;
vector<int> Solution::shard2mach;
Read full article from [LintCode][System Design] Consistent Hashing II - 简书
在 Consistent Hashing I 中我们介绍了一个比较简单的一致性哈希算法,这个简单的版本有两个缺陷:
- 增加一台机器之后,数据全部从其中一台机器过来,这一台机器的读负载过大,对正常的服务会造成影响。
- 当增加到3台机器的时候,每台服务器的负载量不均衡,为1:1:2。
- 将 360° 的区间分得更细。从 0~359 变为一个 0 ~ n-1 的区间,将这个区间首尾相接,连成一个圆。
- 当加入一台新的机器的时候,随机选择在圆周中撒 k 个点,代表这台机器的 k 个 micro-shards。
- 每个数据在圆周上也对应一个点,这个点通过一个 hash function 来计算。
- 一个数据该属于那台机器负责管理,是按照该数据对应的圆周上的点在圆上顺时针碰到的第一个 micro-shard 点所属的机器来决定。
请实现这种引入了 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
当 n 为 2^64 时,在这个区间内随机基本不会出现重复。
当 n 为 2^64 时,在这个区间内随机基本不会出现重复。
但是为了方便测试您程序的正确性,n 在数据中可能会比较小,所以你必须保证你生成的 k 个随机数不会出现重复。
当 n 为 2^64 时,在这个区间内随机基本不会出现重复。
但是为了方便测试您程序的正确性,n 在数据中可能会比较小,所以你必须保证你生成的 k 个随机数不会出现重复。
LintCode并不会判断你addMachine的返回结果的正确性(因为是随机数),只会根据您返回的addMachine的结果判断你getMachineIdByHashCode结果的正确性。
Examplecreate(100, 3)
addMachine(1)
>> [3, 41, 90] => 三个随机数
getMachineIdByHashCode(4)
>> 1
addMachine(2)
>> [11, 55, 83]
getMachineIdByHashCode(61)
>> 2
getMachineIdByHashCode(91)
>> 1
原文链接:http://www.jianshu.com/p/4b39053a7a24
著作权归作者所有,转载请联系作者获得授权,并标注“简书作者”。
class Solution {
private:
static int shardNum;
static int microShardNum;
static vector<int> shard2mach;
public:
// @param n a positive integer
// @param k a positive integer
// @return a Solution object
static Solution create(int n, int k) {
shardNum = n;
microShardNum = k;
shard2mach.resize(n);
for(int i = 0; i < n; i++) {
shard2mach[i] = -1;
}
}
// @param machine_id an integer
// @return a list of shard ids
vector<int> addMachine(int machine_id) {
srand(time(NULL));
int count = 0;
vector<int> ret;
while(count < microShardNum) {
int number = rand() % shardNum;
if (shard2mach[number] == -1) {
count++;
shard2mach[number] = machine_id;
ret.push_back(number);
}
}
return ret;
}
// @param hashcode an integer
// @return a machine id
int getMachineIdByHashCode(int hashcode) {
int i = hashcode;
while(true) {
if (i == shardNum) {
i = 0;
}
if (shard2mach[i] != -1) {
return shard2mach[i];
}
i++;
}
}
};
int Solution::shardNum;
int Solution::microShardNum;
vector<int> Solution::shard2mach;
Read full article from [LintCode][System Design] Consistent Hashing II - 简书