consistent_hash.js

const crypto = require('crypto');

class ConsistentHash {
  /**
   * create new consistent hash object
   *
   * @param nodeList - node id list
   * @param vnSize - number of virtual node (default 100)
   * @param algorithm - hash algorithm (default md5)
   */
  constructor(nodeList, vnSize = 100, algorithm = 'md5') {
    this.keyNodeMap = new Map();
    this.sortedKeys = [];
    this.algorithm = algorithm
    this.vnSize = vnSize;

    for (const node of nodeList) {
      this._addNode(node);
    }

    this.sortedKeys.sort();
  }

  _addNode(node) {
    for (let i = 0; i < this.vnSize; i++) {
      const h = this.hash(node + i.toString());
      this.sortedKeys.push(h);
      this.keyNodeMap.set(h, node);
    }
  }

  addNode(node) {
    this._addNode(node);
    this.sortedKeys.sort();
  }

  removeNode(removingNode) {
    const oldKeyNodeMap = this.keyNodeMap;

    this.sortedKeys = [];
    this.keyNodeMap = new Map();

    for (const [key, node] of oldKeyNodeMap) {
      if (node !== removingNode) {
        this.sortedKeys.push(key);
        this.keyNodeMap.set(key, node);
      }
    }
    this.sortedKeys.sort();
  }

  hash(item) {
    const h = crypto.createHash(this.algorithm);
    h.update(item);
    return h.digest('hex');
  }

  getNode(item) {
    const itemKey = this.hash(item);
    let min = 0;
    let max = this.sortedKeys.length - 1;
    do {
      const mid = min + ((max - min) >> 1);
      const nodeKey = this.sortedKeys[mid];
      if (itemKey > nodeKey) {
        min = mid + 1;
      } else if (itemKey < nodeKey) {
        max = mid - 1;
      } else {
        return this.keyNodeMap.get(nodeKey);
      }
    } while(max >= min);

    if (min >= this.sortedKeys.length) {
      min = 0;
    }
    return this.keyNodeMap.get(this.sortedKeys[min]);
  }

  // this is slow, due to linear search
  getNodeSlow(item) {
    const itemKey = this.hash(item);
    for (let i = 0; i < this.sortedKeys.length; i++) {
      const nodeKey = this.sortedKeys[i];
      if (itemKey <= nodeKey) {
        return this.keyNodeMap.get(nodeKey);
      }
    }
    return this.keyNodeMap.get(this.sortedKeys[0]);
  }
}

exports.ConsistentHash = ConsistentHash;