Consistent Hashing 算法实现 - JavaScript

Total data num: 1000000, server num: 10, nodes per server: 5, standard deviation: 36095.806687203985
Total data num: 1000000, server num: 10, nodes per server: 10, standard deviation: 38127.204471348276
Total data num: 1000000, server num: 10, nodes per server: 50, standard deviation: 17082.357518796987
Total data num: 1000000, server num: 10, nodes per server: 100, standard deviation: 13637.17885048077
Total data num: 1000000, server num: 10, nodes per server: 150, standard deviation: 5072.066896246539
Total data num: 1000000, server num: 10, nodes per server: 200, standard deviation: 6572.201564164021

/**
 * Implementation of Consistent Hashing
 *
 * Create 1 million key-value pair and distributed across 10 servers. Evaluate implementaion by calculating standard error with 50, 100, 150, 200 nodes per server.
 *
 */
// Implementation
const crypto = require('crypto')
const { performance } = require('perf_hooks')
const ringSize = 2_000_000
class ConsistentHashing {
    constructor(servers = []) {
        this.servers = servers
        // { [nodeName]: [serverName] }
        this.serversMap = {}
        // { [nodePosition]: [nodeName] }
        this.nodesMap = {}
    }
    addServer(name, nodesNum) {
        const server = new ConsistentHashingServer(name, nodesNum)
        server.generateNodes(this.serversMap, this.nodesMap)
        this.servers.push(server)
    }
    // Get server for key
    serverFor(key) {
        return this.serversMap[this.nodeFor(key)]
    }
    // Get node for key
    nodeFor(key) {
        const position = this.getPosition(key)
        const closestPosition = this.findClosestPosition(position, Object.keys(this.nodesMap))
        return this.nodesMap[closestPosition]
    }
    getPosition(key) {
        const hashCode = crypto.createHash('md5').update(key).digest('hex')
        // Get position in the ring from has code
        return parseInt(hashCode, 16) % ringSize
    }
    findClosestPosition(position, arr) {
        let left = 0
        let right = arr.length - 1
        let mid
        while (left <= right) {
            mid = Math.floor((right - left) / 2 + left)
            if (arr[mid] < position) {
                left = mid + 1
            } else if (arr[mid] > position) {
                right = mid - 1
            } else {
                return arr[mid]
            }
        }
        let target = 0
        if (arr[right] >= position) {
            target = right
        } else if ((right + 1 <= arr.length - 1) && arr[right + 1] >= position) {
            target = right + 1
        }
        return arr[target]
    }
    evaluate(keys) {
        const result = {}
        for (let key of keys) {
            const serverName = this.serverFor(key)
            if (!result[serverName]) {
                result[serverName] = 0
            }
            result[serverName] += 1
        }
        return this.standardDeviation(Object.values(result))
    }
    standardDeviation(array) {
        const n = array.length
        const mean = array.reduce((a, b) => a + b) / n
        return Math.sqrt(array.map(x => Math.pow(x - mean, 2)).reduce((a, b) => a + b) / n)
    }
}
class ConsistentHashingServer {
    constructor(name, nodesNum) {
        this.name = name
        this.nodesNum = nodesNum
    }
    // Generate n (nodesNum) virtual nodes distributed across the ring
    generateNodes(serversMap, nodesMap) {
        for (let i = 0; i < this.nodesNum; i++) {
            const nodeName = this.generateNodeName(i)
            while (true) {
                const rand = Math.floor(Math.random() * ringSize)
                if (!nodesMap[rand]) {
                    serversMap[nodeName] = this.name
                    nodesMap[rand] = nodeName
                    break
                }
            }
        }
    }
    generateNodeName(i) {
        // Node name: <serverName>-<i>
        return `${this.name}-${i}`
    }
}
/**
 * Test
 */
let consistentHashing = new ConsistentHashing()
// Add servers
let serversNum
let nodesPerServer = 5
consistentHashing.addServer('A', nodesPerServer)
consistentHashing.addServer('B', nodesPerServer)
consistentHashing.addServer('C', nodesPerServer)
console.log(consistentHashing.serverFor('foo'))
console.log(consistentHashing.serverFor('bar'))
console.log(consistentHashing.serverFor('hello'))
console.log(consistentHashing.nodeFor('foo'))
console.log(consistentHashing.nodeFor('bar'))
console.log(consistentHashing.nodeFor('hello'))
console.log(consistentHashing)
/**
 * Evaluate: return standard deviation
 *
 * Data / keys count: 1,000,000
 * Server number: 10
 * Node number per server: [50, 100, 150, 200]
 */
const totalDataCount = 1_000_000
serversNum = 10
for (let nodesNumPerServer of [5, 10, 50, 100, 150, 200]) {
    evaluate(totalDataCount, serversNum, nodesNumPerServer)
}
function evaluate(dataNum, serversNum, nodesPerServer) {
    const randomKeys = generateRandomKeys(dataNum)
    consistentHashing = new ConsistentHashing()
    const serverNames = Array.from(new Array(serversNum), (_, i) => `Server-${i + 1}`)
    for (let name of serverNames) {
        consistentHashing.addServer(name, nodesPerServer)
    }
    const sd = consistentHashing.evaluate(randomKeys)
    console.log(`Total data num: ${dataNum}, server num: ${serversNum}, nodes per server: ${nodesPerServer}, standard deviation: ${sd}`)
}
// Generate random data
function generateRandomKeys(num) {
    // > 900 millions possible string
    const stringLength = 5
    let keys = []
    for (let i = 0; i < num; i++) {
        keys.push(randomString(stringLength))
    }
    return keys
}
// Generate random string
function randomString(length) {
    let result = ''
    let characters = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789'
    let charactersLength = characters.length
    for ( var i = 0; i < length; i++ ) {
        result += characters.charAt(Math.floor(Math.random() * charactersLength))
    }
    return result
}