[架构师训练营第 1 期] 第五周命题作业
发布于: 2020 年 10 月 25 日
题目
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据和 10 个服务器节点的情况下，数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
成果
第一题
使用 JavaScript 编程语言实现一致性 hash 算法代码如下：（注：虚拟节点部分的算法不理想待优化）
/*
基于一致性哈希算法的分布式缓存
说明：
分布式缓存包含三个过程： 1. 分配服务器编号 2. 查找服务器编号 3. 扩充服务器编号
基于普通哈希算法的分布式缓存对上述三个过程的具体实现如下： 1. 根据服务器数量（n）分配服务器编号 2. 根据数据的键名（key）查找服务器编号，以进行读或写 3. 根据扩充服务器数量（x）重新分配服务器编号，并迁移*所有*缓存
基于一致性哈希算法的分布式缓存对上述三个过程的具体实现如下： 1. 根据服务器配置（如 ip）分配服务器编号 2. 根据数据的键名（key）查找服务器编号，以进行读或写 3. 根据扩充服务器配置（如 ip）为新服务器分配编号，并迁移*部分*缓存
*/
const CACHE_SERVER_MAX_NUM = 2**32; // 缓存服务器最大数量
const crypto = require('crypto');
const cacheServers = []; // 缓存服务器列表let virtualNodeNo = 0; // 可用虚拟节点编号
class CacheServer { constructor({ name, ip, id, realServer, debug = false } = {}) { this.name = name; this.ip = ip; this.id = id; this.debug = debug; this.dataNumber = 0; } getCache(key) { /*具体实现略*/ this.debug && console.debug(`[cacheServer <${this.name}>] Successfully get cache by key <${key}>`); } getAllCaches() { /*具体实现略*/ this.debug && console.debug(`[cacheServer <${this.name}>] Successfully get all caches`); } setCache(key, value) { /*具体实现略*/ this.dataNumber++; this.debug && console.debug(`[cacheServer <${this.name}>] Successfully set cache <key: ${key}, value: ${value}>`); } setCaches(caches) { /*具体实现略*/ for (let { key, value } of caches) this.setCache(key, value); } removeCache(key, value) { /*具体实现略*/ this.dataNumber--; this.debug && console.debug(`[cacheServer <${this.name}>] Successfully removed cache <key: ${key}, value: ${value}>`); return { key, value }; } removeCaches(caches) { /*具体实现略*/ let removedCaches = []; for (let { key, value } of caches) removedCaches.push(this.removeCache(key, value)); return removedCaches; }}
/** * 初始化创建缓存服务器列表 * @param {Array} serversConfig 服务器配置对象列表 * @param {Array} idKey 使用服务器配置对象中的哪个或哪几个键的值作为 id * @param {String} multiIdKeySeparator 当指定 idKey 个数大于 1 时各个值之间的分隔符 * @param {Integer} virtualMultiTimes 虚拟节点的倍数 * @param {Boolean} debug 调试模式 * @returns {Array.CacheServer} 缓存服务器实例对象列表 */function createServers(serversConfig = [], { idKey = ['ip'], multiIdKeySeparator = '|', virtualMultiTimes = 0, debug = false } = {}) { serversConfig = Array.isArray(serversConfig) ? serversConfig : [String(serversConfig)]; idKey = Array.isArray(idKey) ? idKey : [String(idKey)]; multiIdKeySeparator = multiIdKeySeparator || ''; let newServers = []; // 根据配置实例化缓存服务器并编号 for (let serverConfig of serversConfig) { // 创建真实服务器节点 let serverId = idKey.map(k => serverConfig[k]).join(multiIdKeySeparator); // idKey 通常不会很多，所以此方法对整体性能没有明显影响 let serverIdHash = getHashMod(serverId); let server = new CacheServer({ ...serverConfig, id: serverIdHash, debug }); cacheServers.push(server); newServers.push(server); debug && console.debug(`Successfully assigned id <${server.id}> to server <${server.name}>`); // 创建虚拟服务器节点（TODO：可优化） for (let i = 0; i < virtualMultiTimes; i++) { let virtualServerId = `${++virtualNodeNo}@${serverId}`; let virtualServerIdHash = getHashMod(virtualServerId); let virtualServer = { isVirtual: true, id: virtualServerIdHash, realServer: server }; // let virtualServer = new CacheServer({ ...serverConfig, id: virtualServerIdHash, realServer: server, debug }); cacheServers.push(virtualServer); newServers.push(virtualServer); debug && console.debug(`Successfully assigned id <${virtualServer.id}> to virtualServer <${virtualServer.name}>`); } } // 对服务器列表升序排序，便于直接使用 find 查找 cacheServers.sort((sa, sb) => sa.id - sb.id); return newServers;}
/** * 获取指定数据键名对应的缓存服务器 * @param dataKey 数据键名 * @param keyIsHash 提供的 dataKey 是否已经是 hash 值 * @param reverse 是否逆向查找 * @returns {CacheServer|undefined} 缓存服务器实例对象 */function getServer(dataKey, { keyIsHash = false, reverse = false } = {}) { let keyHash = getHashMod(dataKey); let server = keyHash && (( reverse ? (() => { for (let server of cacheServers) { if (server.id <= keyHash) return server; } })() : cacheServers.find(server => server.id >= keyHash) ) || cacheServers[0]); // 环形查找（边界情况：没找到则返回 undefined） return server.isVirtual ? server.realServer : server;}
/** * 增加缓存服务器 * @param {Array} newServersConfig 服务器配置对象列表 * @param {Array} idKey 使用服务器配置对象中的哪个或哪几个键的值作为 id * @param {String} multiIdKeySeparator 当指定 idKey 个数大于 1 时各个值之间的分隔符 * @param {Integer} virtualMultiTimes 虚拟节点的倍数 * @param {Boolean} debug 调试模式 * @returns {Array.CacheServer} 增加后的缓存服务器实例对象列表 */function addServers(newServersConfig = [], { idKey = ['ip'], multiIdKeySeparator = '|', virtualMultiTimes = 0, debug = false } = {}) { let newCacheServers = createServers(newServersConfig, { idKey, multiIdKeySeparator, virtualMultiTimes, debug }); // 从编号最小的新服务器开始迁入相应缓存数据，避免重复迁移 newCacheServers.sort((sa, sb) => sa.id - sb.id); for (let cacheMoveTo of newCacheServers) { // 环上逆时针最靠近的一台服务器缓存迁移到这台新的服务器（边界情况：如果没有找到就不用迁移） let cacheMoveFrom = getServer(cacheMoveTo.id, { idIsHash: true, reverse: true }); cacheMoveFrom && cacheMoveTo.setCaches(cacheMoveFrom.removeCaches(cacheMoveFrom.getAllCaches())); cacheServers.push(cacheMoveTo); } return cacheServers;}
/** * 移除缓存服务器 * @param servers 缓存服务器实例 */function removeServers(servers = []) { let serversIdMap = {}; for (let { id } of servers) serversIdMap[id] = true; for (let i = 0; i < cacheServers.length;) { if(serversIdMap[cacheServers[i].id]) cacheServers.splice(i, 1); else i++; }}
/** * 获得数据的哈希值模服务器最大数量 * @param data 数据 * @returns {(number|undefined)} 哈希值模服务器最大数量 */function getHashMod(data) { return data && crypto.createHash('md5').update(data).digest('dec').readUInt32BE() % CACHE_SERVER_MAX_NUM;}
module.exports = { cacheServers, createServers, getServer, addServers, removeServers, getHashMod,};
复制代码
第二题
编写测试用例代码如下：
测试用例主体：
const { cacheServers, createServers, getServer, addServers, removeServers, getHashMod } = require('./consistent_hasing_II');const { standardDeviation } = require('./statistics');
function test({ serversConfig, data, virtualMultiTimes, debug }) { // ———————————————————————————————————————————————————————————————————————————————— // ↓↓↓↓↓↓↓↓↓↓ 初始创建缓存服务器 ↓↓↓↓↓↓↓↓↓↓ createServers(serversConfig, { virtualMultiTimes, debug }); debug && console.debug(`Created cache servers(sorted):\n${JSON.stringify(cacheServers, null, 4)}`); // ↑↑↑↑↑↑↑↑↑↑ 初始创建缓存服务器 ↑↑↑↑↑↑↑↑↑↑ // ————————————————————————————————————————————————————————————————————————————————
// ———————————————————————————————————————————————————————————————————————————————— // ↓↓↓↓↓↓↓↓↓↓ 数据存入到缓存服务器 ↓↓↓↓↓↓↓↓↓↓ for (let { key, value } of data) { let server = getServer(key); server && server.setCache(key, value); } // ↑↑↑↑↑↑↑↑↑↑ 数据存入到缓存服务器 ↑↑↑↑↑↑↑↑↑↑ // ————————————————————————————————————————————————————————————————————————————————
// ———————————————————————————————————————————————————————————————————————————————— // 检查所有 data 是否存放在正确的服务器上 // 检查通过条件：不存在任何服务器 id 落在每个 data 的 __keyHash 到 __serverId 之间 let pass = true; let showEveryTestPassLog = data.length < 10; for (let { key, value } of data) { let keyHash = getHashMod(key); let serverId = getServer(key).id; let server = cacheServers.find(s => keyHash < s.id && s.id < serverId); if (server && !server.isVirtual) { pass = false; console.error(`[test][✗] 数据 <key: ${key}, value: ${value}, __keyHash: ${keyHash}, __serverId: ${serverId}> 应存入服务器 ${server.id}`); } else { showEveryTestPassLog && console.log(`[test][✔️] 数据 <key: ${key}, value: ${value}, __keyHash: ${keyHash}, __serverId: ${serverId}> 已存入正确的服务器`); } } pass && console.log(`[test][✔️] 全部数据 <...> 已存入正确的服务器`); // ————————————————————————————————————————————————————————————————————————————————
let _cacheServers = cacheServers.filter(s => !s.isVirtual);
// ———————————————————————————————————————————————————————————————————————————————— // 展示当前服务器负载情况 let totalDataAmount = 0; console.log(`[test] 当前服务器负载情况：`); console.table(_cacheServers.map(s => { totalDataAmount += s.dataNumber; return { '服务器': `${s.name}(ip: ${s.ip}, id: ${s.id})`, '负载': s.dataNumber }; })); console.log(`总计：${totalDataAmount}`); // ————————————————————————————————————————————————————————————————————————————————
return { loadStdDev: standardDeviation(_cacheServers.map(s => s.dataNumber)) };}
// ————————————————————————————————————————————————————————————————————————————————// ↓↓↓↓↓↓↓↓↓↓ 常数 ↓↓↓↓↓↓↓↓↓↓const MOCK_SERVER_NUMBER = 10; // 模拟缓存服务器数量const MOCK_DATA_NUMBER = 1000000; // 模拟数据数量const DEBUG = false;// ↑↑↑↑↑↑↑↑↑↑ 常数 ↑↑↑↑↑↑↑↑↑↑// ————————————————————————————————————————————————————————————————————————————————
// ————————————————————————————————————————————————————————————————————————————————// ↓↓↓↓↓↓↓↓↓↓ 生成模拟数据 ↓↓↓↓↓↓↓↓↓↓const { mock } = require('./mock');const { serversConfig, data } = mock({ mockServerNum: MOCK_SERVER_NUMBER, mockDataNumber: MOCK_DATA_NUMBER });// ↑↑↑↑↑↑↑↑↑↑ 生成模拟数据 ↑↑↑↑↑↑↑↑↑↑// ————————————————————————————————————————————————————————————————————————————————
// ————————————————————————————————————————————————————————————————————————————————// ↓↓↓↓↓↓↓↓↓↓ 测试不同虚拟节点倍数下缓存服务器负载标准差 ↓↓↓↓↓↓↓↓↓↓let result = [];for (let i of [0, 1， 2]) { removeServers(cacheServers); let { loadStdDev } = test({ serversConfig, data, virtualMultiTimes: i, debug: DEBUG }); result.push(`[test]（虚拟节点倍数 = ${i}）缓存服务器集群负载标准差为：${loadStdDev}`);}console.log(result);// ↑↑↑↑↑↑↑↑↑↑ 测试不同虚拟节点倍数下缓存服务器负载标准差 ↑↑↑↑↑↑↑↑↑↑// ————————————————————————————————————————————————————————————————————————————————
复制代码
辅助函数之模拟数据生成函数
const jsf = require('json-schema-faker');function mock({ mockServerNum, mockDataNumber }) { // ———————————————————————————————————————————————————————————————————————————————— // ↓↓↓↓↓↓↓↓↓↓ 生成测试服务器配置 ↓↓↓↓↓↓↓↓↓↓ const serversConfig = []; for (let i = 0; i < mockServerNum; i++) { serversConfig.push(Object.assign(jsf.generate({ "type": "object", "properties": { "ip": { "format": "ipv4" } }, "required": ["ip"], }), { name: `缓存服务器${i + 1}号` })); } // ↑↑↑↑↑↑↑↑↑↑ 生成测试服务器配置 ↑↑↑↑↑↑↑↑↑↑ // ————————————————————————————————————————————————————————————————————————————————
// ———————————————————————————————————————————————————————————————————————————————— // ↓↓↓↓↓↓↓↓↓↓ 生成测试数据 ↓↓↓↓↓↓↓↓↓↓ const data = []; for (let i = 0; i < mockDataNumber; i++) { data.push(jsf.generate({ "type": "object", "properties": { "key": { "pattern": "^key_\\w+" }, "value": { "pattern": "^value_\\w+" } }, "required": ["key", "value"] })); } // ↑↑↑↑↑↑↑↑↑↑ 生成测试数据 ↑↑↑↑↑↑↑↑↑↑ // ———————————————————————————————————————————————————————————————————————————————— return { serversConfig, data };}
module.exports = { mock,};
复制代码
辅助函数之统计函数
function variance([...data]) { let dataLen = data.length; let avg = data.reduce((acc, curr) => acc + curr) / dataLen; let total = 0; for (let i = 0; i < dataLen; i++) { total += (data[i] - avg) ** 2; } return total / dataLen;}
function standardDeviation([...data], { digit = 2 } = {}) { return Math.sqrt(variance([...data])).toFixed(digit);}
module.exports = { variance, standardDeviation};
复制代码
运行测试用例结果如下：
————————————————————————————————————————[test] 测试虚拟节点倍数 = 0[test][✔️] 全部数据 <...> 已存入正确的服务器[test] 当前服务器负载情况：┌─────────┬──────────────────────────────────────────────────────┬────────┐│ (index) │ 服务器 │ 负载 │├─────────┼──────────────────────────────────────────────────────┼────────┤│ 0 │ '缓存服务器6号(ip: 34.129.185.8, id: 694098716)' │ 325043 ││ 1 │ '缓存服务器2号(ip: 7.201.175.183, id: 1125312438)' │ 104174 ││ 2 │ '缓存服务器10号(ip: 206.152.4.92, id: 1160301785)' │ 9052 ││ 3 │ '缓存服务器3号(ip: 87.152.215.76, id: 1372096532)' │ 48159 ││ 4 │ '缓存服务器4号(ip: 168.68.66.186, id: 2180074971)' │ 184719 ││ 5 │ '缓存服务器8号(ip: 243.78.20.189, id: 2664388158)' │ 111691 ││ 6 │ '缓存服务器5号(ip: 30.181.50.131, id: 2831417142)' │ 38233 ││ 7 │ '缓存服务器7号(ip: 21.165.100.224, id: 2957491016)' │ 29409 ││ 8 │ '缓存服务器1号(ip: 208.216.208.170, id: 3530296141)' │ 134964 ││ 9 │ '缓存服务器9号(ip: 12.204.12.131, id: 3592802040)' │ 14556 │└─────────┴──────────────────────────────────────────────────────┴────────┘总计：1000000————————————————————————————————————————————————————————————————————————————————[test] 测试虚拟节点倍数 = 1[test][✔️] 全部数据 <...> 已存入正确的服务器[test] 当前服务器负载情况：┌─────────┬──────────────────────────────────────────────────────┬────────┐│ (index) │ 服务器 │ 负载 │├─────────┼──────────────────────────────────────────────────────┼────────┤│ 0 │ '缓存服务器6号(ip: 34.129.185.8, id: 694098716)' │ 44946 ││ 1 │ '缓存服务器2号(ip: 7.201.175.183, id: 1125312438)' │ 68894 ││ 2 │ '缓存服务器10号(ip: 206.152.4.92, id: 1160301785)' │ 38818 ││ 3 │ '缓存服务器3号(ip: 87.152.215.76, id: 1372096532)' │ 113316 ││ 4 │ '缓存服务器4号(ip: 168.68.66.186, id: 2180074971)' │ 407477 ││ 5 │ '缓存服务器8号(ip: 243.78.20.189, id: 2664388158)' │ 101449 ││ 6 │ '缓存服务器5号(ip: 30.181.50.131, id: 2831417142)' │ 65633 ││ 7 │ '缓存服务器7号(ip: 21.165.100.224, id: 2957491016)' │ 23202 ││ 8 │ '缓存服务器1号(ip: 208.216.208.170, id: 3530296141)' │ 97283 ││ 9 │ '缓存服务器9号(ip: 12.204.12.131, id: 3592802040)' │ 38982 │└─────────┴──────────────────────────────────────────────────────┴────────┘总计：1000000————————————————————————————————————————————————————————————————————————————————[test] 测试虚拟节点倍数 = 2[test][✔️] 全部数据 <...> 已存入正确的服务器[test] 当前服务器负载情况：┌─────────┬──────────────────────────────────────────────────────┬────────┐│ (index) │ 服务器 │ 负载 │├─────────┼──────────────────────────────────────────────────────┼────────┤│ 0 │ '缓存服务器6号(ip: 34.129.185.8, id: 694098716)' │ 104078 ││ 1 │ '缓存服务器2号(ip: 7.201.175.183, id: 1125312438)' │ 93804 ││ 2 │ '缓存服务器10号(ip: 206.152.4.92, id: 1160301785)' │ 45564 ││ 3 │ '缓存服务器3号(ip: 87.152.215.76, id: 1372096532)' │ 105463 ││ 4 │ '缓存服务器4号(ip: 168.68.66.186, id: 2180074971)' │ 163083 ││ 5 │ '缓存服务器8号(ip: 243.78.20.189, id: 2664388158)' │ 167310 ││ 6 │ '缓存服务器5号(ip: 30.181.50.131, id: 2831417142)' │ 60634 ││ 7 │ '缓存服务器7号(ip: 21.165.100.224, id: 2957491016)' │ 117178 ││ 8 │ '缓存服务器1号(ip: 208.216.208.170, id: 3530296141)' │ 111536 ││ 9 │ '缓存服务器9号(ip: 12.204.12.131, id: 3592802040)' │ 31350 │└─────────┴──────────────────────────────────────────────────────┴────────┘总计：1000000————————————————————————————————————————————————————————————————————————————————[ '[test]（虚拟节点倍数 = 0）缓存服务器集群负载标准差为：92874.22', '[test]（虚拟节点倍数 = 1）缓存服务器集群负载标准差为：106429.74', '[test]（虚拟节点倍数 = 2）缓存服务器集群负载标准差为：42718.74']————————————————————————————————————————
复制代码
结论：标准差不如预期，虚拟节点多反而标准差小，说明虚拟节点的生成算法不够合理，需要改进。
划线
评论
复制
发布于: 2020 年 10 月 25 日阅读数: 10
版权声明: 本文为 InfoQ 作者【猫切切切切切】的原创文章。
原文链接:【http://xie.infoq.cn/article/2bfb9fa373c124b318a6fc37c】。文章转载请联系作者。
猫切切切切切
关注
还未添加个人签名 2018.03.26 加入
还未添加个人简介
![[架构师训练营第 1 期] 第五周命题作业](https://static001.infoq.cn/static/infoq/img/logo-121-75.yuij86g.png){kind=logo}
评论