An implementation of a "hash ring" for partitioning with consistent hashes.

hash-ring.md

Usage

const hashRing = createHashRing({
  clients: [
    { address: 'localhost:5001' },
    { address: 'localhost:5002' },
    { address: 'localhost:5003' }
  ]
})

const client = hashRing.getClientForKey('some-key')
// returns => { address: 'localhost:5001' }

Implementation

import { createHash } from 'crypto'

export type Client = {
  address: string
}

/**
 * A HashRing for ConsistentHashingPartitioning.
 * 
 * Inspired by:
 * 
 * - https://blog.hltbra.net/2019/02/18/consistent-hashing.html
 * - https://github.com/redis-essentials/book/blob/master/chapter%208/consistenthashing.js
 * - https://michaelnielsen.org/blog/consistent-hashing/
 */
export function createHashRing (params: { clients: Client[], vnodes?: number }) {
  const vnodes = params.vnodes || 256
  const ring: { [key: string]: Client } = {}
  const ringHashes: string[] = []
  const md5 = (str: string) => {
    return createHash('md5').update(str).digest('hex')
  }
  const addClient = (client: Client) => {
    for (let i = 0; i < vnodes; i++) {
      const hash = md5(client.address + ':' + i)
      ring[hash] = client
    }
    ringHashes.splice(0, ringHashes.length, ...Object.keys(ring).sort())
  }
  const removeClient = (client: Client) => {
    for (let i = 0; i < vnodes; i++) {
      const hash = md5(client.address + ':' + i)
      delete ring[hash]
    }
    ringHashes.splice(0, ringHashes.length, ...Object.keys(ring).sort())
  }
  const getClientForKey = (key: string) => {
    const keyHash = md5(key)
    for (const ringHash of ringHashes) {
      if (ringHash >= keyHash) return ring[ringHash]
    }
    return ring[ringHashes[0]]
  }
  for (const client of params.clients) {
    addClient(client)
  }
  return {
    addClient,
    removeClient,
    getClientForKey
  }
}

Alternate implementation

This presents a simplified implementation of consistent hashing, but without the "hash ring".

export function consistentHash (key: string, buckets: number) {
  const hash = createHash('md5').update(key).digest('hex')
  return parseInt(hash, 16) % buckets
}