写点什么

第五周 - 命题作业

用户头像
JI
关注
发布于: 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)
复制代码


用户头像

JI

关注

还未添加个人签名 2019.07.19 加入

还未添加个人简介

评论

发布
暂无评论
第五周-命题作业