写点什么

[架构师训练营第 1 期] 第五周命题作业

发布于: 2020 年 10 月 25 日

题目

  1. 用你熟悉的编程语言实现一致性 hash 算法。

  2. 编写测试用例测试这个算法,测试 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 日阅读数: 6
用户头像

还未添加个人签名 2018.03.26 加入

还未添加个人简介

评论

发布
暂无评论
[架构师训练营第 1 期] 第五周命题作业