[架构师训练营第 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 日阅读数: 6
版权声明: 本文为 InfoQ 作者【猫切切切切切】的原创文章。
原文链接:【http://xie.infoq.cn/article/2660a2000437600999f76df46】。文章转载请联系作者。
猫切切切切切
关注
还未添加个人签名 2018.03.26 加入
还未添加个人简介
评论