第五周 - 命题作业
发布于: 2020 年 07 月 09 日
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。
var crc32 = (function () {
function utf8encode(str) {
var utf8CharCodes = [];
for (var i = 0, len = str.length, c; i < len; ++i) {
c = str.charCodeAt(i);
if (c < 128) {
utf8CharCodes.push(c);
} else if (c < 2048) {
utf8CharCodes.push((c >> 6) | 192, (c & 63) | 128);
} else {
utf8CharCodes.push((c >> 12) | 224, ((c >> 6) & 63) | 128, (c & 63) | 128);
}
}
return utf8CharCodes;
}
var cachedCrcTable = null;
function buildCRCTable() {
var table = [];
for (var i = 0, j, crc; i < 256; ++i) {
crc = i;
j = 8;
while (j--) {
if ((crc & 1) == 1) {
crc = (crc >>> 1) ^ 0xEDB88320;
} else {
crc >>>= 1;
}
}
table[i] = crc >>> 0;
}
return table;
}
function getCrcTable() {
if (!cachedCrcTable) {
cachedCrcTable = buildCRCTable();
}
return cachedCrcTable;
}
return function (str) {
var utf8CharCodes = utf8encode(str),
crc = -1,
crcTable = getCrcTable();
for (var i = 0, len = utf8CharCodes.length, y; i < len; ++i) {
y = (crc ^ utf8CharCodes[i]) & 0xFF;
crc = (crc >>> 8) ^ crcTable[y];
}
return (crc ^ -1) >>> 0;
};
})();
function getPlaceholderCount(strSource) {
//统计字符串中包含{}或{xxXX}的个数
var thisCount = 0;
strSource.replace(/\{[xX]+\}|\{\}/g, function (m, i) {
//m为找到的{xx}元素、i为索引
thisCount++;
});
return thisCount;
}
class consistenHashing {
constructor(nodes = [], replicas = 5) {
this.nodes = nodes
this.replicas = replicas
this.ring = {}
this.sortedKey = []
this.addNode(nodes)
}
addNode(node) {
for (let i = 0; i < this.replicas; i++) {
let hashKey = Math.abs(crc32(`${node}_vnode_${i}`).toString())
this.ring[hashKey] = node
this.sortedKey.concat(hashKey)
}
this.sortedKey.sort()
}
addNodes(nodes) {
if (nodes.length > 0) {
this.nodes.forEach(node => {
this.addNode(node)
})
}
}
removeNodes(nodes = []) {
if (nodes.length > 0) {
nodes.forEach(node => {
for (let i = 0; i < this.replicas; i++) {
let hashKey = Math.abs(crc32(`${node}_vnode_${i}`).toString())
delete this.ring[hashKey]
}
})
}
}
getNode(key) {
let hashKey = Math.abs(crc32(`${key}`).toString())
let i = 0;
for (; i < this.sortedKey.length; i++) {
if (hashKey < nodehash) {
return this.ring[nodehash]
} else {
continue
}
// constole.log(`${i} Keyhash:${keyhash} Nodehash:${nodehash}`)
}
if (i == this.sortedKey.length) return this.ring[this.sortedKey[0]]
}
}
defalutServices = [
'192.168.1.1:1',
'192.168.1.1:2',
'192.168.1.1:3',
'192.168.1.1:4',
'192.168.1.1:5',
'192.168.1.1:6',
]
const ch = new consistenHashing(defalutServices)
复制代码
划线
评论
复制
发布于: 2020 年 07 月 09 日阅读数: 53
JI
关注
还未添加个人签名 2019.07.19 加入
还未添加个人简介
评论