Consistent hashingni Node.jsda noldan yozamiz (benchmark)

Assalamu Alaykum bugun consistent hashingni Nodejsda implimentatsiya qilishga harakat qilamiz va uni benchmark bilan tekshiramiz. Bu shunchaki oddiy prototype bo'ladi mukammal emas.

Bu maqolani o'qishdan oldin Consistent hashing maqolasini o'qishni tavsiya qilaman.

Unda qani boshladik :)

Consistent hashing Class

Birinchi bo'lib consistent hashing uchun class yaratib olamiz :

class ConsistentHashing {
  constructor() {
    this.ring = new Map();
    this.sortedNodeHashes = [];
  }
}

classda 2 ta property bor ring — bu circularlik uchun, sortedNodeHashes — bu bizga serverlarni tez topishga yordam beradi. Time complexity O(n*log(n)) .

Hash funksiya

Endi classga keylarni hashlash uchun hash funksiya qo'shamiz.

const crypto = require('crypto');
class ConsistentHashing {
  constructor() {
    this.ring = new Map();
    this.sortedNodeHashes = [];
  }
  hash(value) {
    const hex = crypto.createHash('sha256').update(value).digest('hex');
    return parseInt(hex.substring(0, 8), 16);
  }
}
module.exports = ConsistentHashing;

Biz sha256 bilan hashlangan qiymatni faqat boshidagi 8ta beligini olib Int ga o'tkazamiz bu bizga 0 dan 2³² — 1 = 4,294,967,295 bo'lgan oraliq qiymatini beradi.

Yangi Node qo'shish

Endi classga yangi node qo'shish metodini qo'shamiz:

const crypto = require("crypto");
class ConsistentHashing {
  constructor() {
    this.ring = new Map();
    this.sortedNodeHashes = [];
  }
  _hash(value) {
    const hex = crypto.createHash("sha256").update(value).digest("hex");
    return parseInt(hex.substring(0, 8), 16);
  }
  addNode(node) {
    const nodeHash = this._hash(node);
    if (!this.ring.has(nodeHash)) {
      this.ring.set(nodeHash, node);
      this.sortedNodeHashes.push(nodeHash);
      this.sortedNodeHashes.sort((a, b) => a - b);
    }
  }
}
module.exports = ConsistentHashing;

Bu metod nodeni hashlab uni ringga va arrayga qo'shadi. Ammo agar bu hash oldin ringda bo'lsa shunchaki e'tibor bermay tashlab ketadi , bizda bunaqa collision bo'lishi mumkin (kam sonli nodelar uchun bo'lmaydi odatda) .

Key uchun Nodeni aniqlash

Endi har bir keladigan key uchun u qaysi serverga tushishi kerakligini aniqlovchi metod yozamiz:

const crypto = require("crypto");
class ConsistentHashing {
  constructor() {
    this.ring = new Map();
    this.sortedNodeHashes = [];
  }
  _hash(value) {
    const hex = crypto.createHash("sha256").update(value).digest("hex");
    return parseInt(hex.substring(0, 8), 16);
  }
  addNode(node) {
    const nodeHash = this._hash(node);
    if (!this.ring.has(nodeHash)) {
      this.ring.set(nodeHash, node);
      this.sortedNodeHashes.push(nodeHash);
      this.sortedNodeHashes.sort((a, b) => a - b);
    }
  }
  getNode(key) {
    const keyHash = this._hash(key);
    for (let i = 0; i < this.sortedNodeHashes.length; i++) {
      if (keyHash <= this.sortedNodeHashes[i]) {
        return this.ring.get(this.sortedNodeHashes[i]);
      }
    }
    return this.ring.get(this.sortedNodeHashes[0]);
  }
}
module.exports = ConsistentHashing;

Ushbu funksiya keyni hashlab uni tartiblangan serverlar hashining qaysi oraliqda ekanini qidiradi. Agarda u hech qaysi oraliqda bo'lmasa unga 1-chi server javobgar bo'ladi bu circularlikni taminlaydi.

Nodeni olib tashlash

Endi funksiyamizda Nodeni olib tashlash uchun metod yozamiz:

const crypto = require("crypto");
class ConsistentHashing {
  constructor() {
    this.ring = new Map();
    this.sortedNodeHashes = [];
  }
  _hash(value) {
    const hex = crypto.createHash("sha256").update(value).digest("hex");
    return parseInt(hex.substring(0, 8), 16);
  }
  addNode(node) {
    const nodeHash = this._hash(node);
    if (!this.ring.has(nodeHash)) {
      this.ring.set(nodeHash, node);
      this.sortedNodeHashes.push(nodeHash);
      this.sortedNodeHashes.sort((a, b) => a - b);
    }
  }
  getNode(key) {
    const keyHash = this._hash(key);
    for (let i = 0; i < this.sortedNodeHashes.length; i++) {
      if (keyHash <= this.sortedNodeHashes[i]) {
        return this.ring.get(this.sortedNodeHashes[i]);
      }
    }
    return this.ring.get(this.sortedNodeHashes[0]);
  }
  removeNode(node) {
    const nodeHash = this._hash(node);
    if (this.ring.has(nodeHash)) {
      this.ring.delete(nodeHash);
      const index = this.sortedNodeHashes.indexOf(nodeHash);
      if (index !== -1) {
        this.sortedNodeHashes.splice(index, 1);
      }
    }
  }
}
module.exports = ConsistentHashing;

U ringdan va array ichidan ushbu nodening hash qiymatini o'chirib yuboradi.

Endi ring deyarli tayyor bo'ldi unga benchmark yozib ko'ramiz.

const ConsistentHashing = require("./consistent-hashing");
const NUM_NODES = 100;
const NUM_KEYS = 1_000_000;
const ring = new ConsistentHashing();
for (let i = 0; i < NUM_NODES; i++) {
  ring.addNode(`Node${i}`);
}
const keyToNodeBefore = {};
const distributionBefore = {};
for (let i = 0; i < NUM_KEYS; i++) {
  const key = `user${i}`;
  const node = ring.getNode(key);
  keyToNodeBefore[key] = node;
  distributionBefore[node] = (distributionBefore[node] || 0) + 1;
}
const randomIndex = Math.floor(Math.random() * NUM_NODES);
const removedNode = `Node${randomIndex}`;
console.log(`Removing Node: Node${randomIndex}`);
ring.removeNode(removedNode);
const distributionAfter = {};
let reassigned = 0;
for (let i = 0; i < NUM_KEYS; i++) {
  const key = `user${i}`;
  const newNode = ring.getNode(key);
  const oldNode = keyToNodeBefore[key];
  if (oldNode === removedNode) {
    reassigned++;
  }
  distributionAfter[newNode] = (distributionAfter[newNode] || 0) + 1;
}
function analyzeDistribution(distribution, expectedNodeCount) {
  const counts = Object.values(distribution);
  const total = counts.reduce((a, b) => a + b, 0);
  const average = total / expectedNodeCount;
  const max = Math.max(...counts);
  const min = Math.min(...counts);
  const stdDev = Math.sqrt(
    counts.reduce((sum, c) => sum + (c - average) ** 2, 0) / expectedNodeCount
  );
  return { total, average, max, min, stdDev };
}
const statsBefore = analyzeDistribution(distributionBefore, NUM_NODES);
const statsAfter = analyzeDistribution(distributionAfter, NUM_NODES - 1);
console.log(distributionAfter);
console.log("\n------ BEFORE Removal ------");
console.log(`- Total keys: ${statsBefore.total}`);
console.log(`- Avg per node: ${statsBefore.average.toFixed(2)}`);
console.log(`- Max per node: ${statsBefore.max}`);
console.log(`- Min per node: ${statsBefore.min}`);
console.log(`- Std deviation: ${statsBefore.stdDev.toFixed(2)}`);
console.log(`\n Removed Node: ${removedNode}`);
console.log(` Keys Reassigned: ${reassigned} / ${NUM_KEYS}`);
console.log(` Reassigned: ${((reassigned / NUM_KEYS) * 100).toFixed(2)}%`);
console.log("\n------ AFTER Removal ------");
console.log(`- Total keys: ${statsAfter.total}`);
console.log(`- Avg per node: ${statsAfter.average.toFixed(2)}`);
console.log(`- Max per node: ${statsAfter.max}`);
console.log(`- Min per node: ${statsAfter.min}`);
console.log(`- Std deviation: ${statsAfter.stdDev.toFixed(2)}`);

Bu benchmark 100 ta key uchun key distribution va 1 ta node o'chirilgandan so'ng keyingi key distributionlarni logda ko'rsatib beradi.

41-Node o'chirilgandan so'ng undagi keylar qayta taqsimlandi lekin ular bir xil emas har xil miqdorda va 41ning hamma keylari undan keyingi serverga tushdi(unda load oshib ketadi).

Virtual Nodes

Endi bir xil miqdorda taqsimlash uchun serverlar uchun virtual nodelar qo'shamiz :

const crypto = require("crypto");
class ConsistentHashing {
  constructor(replicas = 100) {
    this.replicas = replicas;
    this.ring = new Map();
    this.sortedNodeHashes = [];
    this.nodes = new Set();
  }
  _hash(value) {
    const hex = crypto.createHash("sha256").update(value).digest("hex");
    return parseInt(hex.substring(0, 8), 16);
  }
  addNode(node) {
    if (this.nodes.has(node)) return;
    this.nodes.add(node);
    for (let i = 0; i < this.replicas; i++) {
      const vnodeId = `${node}#${i}`;
      const vnodeHash = this._hash(vnodeId);
      if (!this.ring.has(vnodeHash)) {
        this.ring.set(vnodeHash, node);
        this.sortedNodeHashes.push(vnodeHash);
      }
    }
    this.sortedNodeHashes.sort((a, b) => a - b);
  }
  removeNode(node) {
    if (!this.nodes.has(node)) return;
    this.nodes.delete(node);
    for (let i = 0; i < this.replicas; i++) {
      const vnodeId = `${node}#${i}`;
      const vnodeHash = this._hash(vnodeId);
      this.ring.delete(vnodeHash);
      const index = this.sortedNodeHashes.indexOf(vnodeHash);
      if (index !== -1) {
        this.sortedNodeHashes.splice(index, 1);
      }
    }
  }
  getNode(key) {
    if (this.sortedNodeHashes.length === 0) return null;
    const keyHash = this._hash(key);
    for (let i = 0; i < this.sortedNodeHashes.length; i++) {
      if (keyHash <= this.sortedNodeHashes[i]) {
        return this.ring.get(this.sortedNodeHashes[i]);
      }
    }
    return this.ring.get(this.sortedNodeHashes[0]);
  }
}
module.exports = ConsistentHashing;

tepada bir necha o'zgarishlar kiritdik replicalar soni boshlang'ich 100 va nodes bu haqiqiy serverlarni saqlab turadi hamda duplicate yoki yo'q serverni o'chirishda bizga keraksiz CPU ishlatmasligimiz uchun tekshirishga yordam beradi . Bundan tashqari bizda addNode da server qo'shilganda uning virtual nodelari ringga qo'shiladi , removeNode da esa o'chiriladi.

Benchmark

Ko'rib turganingizdek natijalar ancha yaxshilandi keylar deyarli teng taqsimlanmoqda biz faqatgina 100 virtual node ishlatdik bu real dasturlarda ancha katta bo'ladi.

Barcha kodlarni bu yerdan topishingiz mumkin. REPO

Xulosa

Xulosa qilib aytadigan bo'lsak sizda high load va ma'lumotlaringiz serverlar o'rtasida taqsimlangan bo'lsa consistent hashingdan foydalanish yaxshi fikr.