架构师训练营 第 5 课作业

发布于: 2020 年 07 月 06 日

作业内容:

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

  • 编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。

一致性Hash算法及其测试用例的代码实现:

import assert from 'assert'
class ConsistencyHash {
private servers = []
public addServer(s: string, virtualNodesNum: number) {
assert(virtualNodesNum > 0, `virtualNodesNum > 0`)
for (let i = 0; i < virtualNodesNum; i += 1) {
const hashCode = this._getHashCode(`${s}-vi-${i}`)
this.servers.push({ s, h: hashCode })
this.servers.sort((p, n) => p.h - n.h)
}
}
public getServerForValue(value: string) {
const hashCode = this._getHashCode(value)
for (const v of this.servers) {
if (hashCode <= v.h) {
return v.s
}
}
return this.servers[0].s
}
// 32位的 Fowler-Noll-Vo 哈希算法
// https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function
private _getHashCode(key: string) {
let hash = 0x811C9DC5 /* offset_basis */
const data = Buffer.from(key)
for (var i = 0; i < data.length; i++) {
hash = hash ^ data[i]
/* 32 bit FNV_Prime = 2**24 + 2**8 + 0x93 */
hash += (hash << 24) + (hash << 8) + (hash << 7) + (hash << 4) + (hash << 1)
}
hash = hash & 0xffffffff
return hash > 0 ? hash : Math.abs(hash)
}
}
class Test {
private hash = new ConsistencyHash()
public run(virtualNodesNum: number) {
const servers = [
'192.168.1.0',
'192.168.1.1',
'192.168.1.2',
'192.168.1.3',
'192.168.1.4',
'192.168.1.5',
'192.168.1.6',
'192.168.1.7',
'192.168.1.8',
'192.168.1.9'
]
for (const s of servers) {
this.hash.addServer(s, virtualNodesNum)
}
const total = 100 * 10000
const values = Array(total).fill(0).map((v, i) => i.toString())
const serversOfCount = Array(servers.length).fill(0)
for (const v of values) {
const s = this.hash.getServerForValue(v)
serversOfCount[servers.indexOf(s)] += 1
}
// 标准差:sqrt((节点被hash到的数量-平均值)**2/服务器数量)
const svg = total / servers.length
let sum = 0
for (const c of serversOfCount) {
sum += Math.pow((c - svg), 2)
}
const res = Math.sqrt(sum / servers.length)
console.log(`虚拟节点数:${virtualNodesNum},标准差:${res}\n`)
}
}
async function main() {
const test = new Test()
test.run(1)
test.run(5)
test.run(100)
test.run(200)
}
main()

测试用例的结果:

虚拟节点数:1,标准差:90297.65832954917

虚拟节点数:5,标准差:88019.59732468674

虚拟节点数:100,标准差:75327.12365144445

虚拟节点数:200,标准差:50203.197645169974

用户头像

Glowry

关注

还未添加个人签名 2019.02.13 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 第5课作业