架构师训练营 第 5 课作业

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()