Consistent Hashing

Vấn đề

Với 1000 keys và 3 nodes, làm sao quyết định node nào lưu key nào?

Cách đơn giản: key % N

key "user:1001" → hash("user:1001") % 3 = 0 → Node 0
key "user:1002" → hash("user:1002") % 3 = 1 → Node 1
key "user:1003" → hash("user:1003") % 3 = 2 → Node 2

Vấn đề: Khi thêm/bớt node, phần lớn keys phải di chuyển.

3 nodes → 4 nodes: 66% keys bị redistribute!

Giải pháp: Hash Ring

Consistent hashing xếp các nodes trên một vòng (0 đến 2^32):

          Node 0 (hash: 150)
            ↓
    ┌───────────────────┐
    │                   │
    │      ● Node 1     │
    │     (hash: 800)   │
    │                   │
    └───────────────────┘
            ↑
          Node 2 (hash: 500)

Cách hoạt động:

1. Hash ID của mỗi node → đặt lên ring
2. Hash mỗi key → đi theo chiều kim đồng hồ đến khi tìm thấy node
3. Key nằm giữa Node 0 và Node 1 → lưu trên Node 1

Lợi ích: Thêm node chỉ di chuyển ~1/N keys.

3 nodes → 4 nodes: chỉ 25% keys bị redistribute!

Virtual Nodes

Các node vật lý tạo nhiều virtual nodes để phân phối tốt hơn:

Node 0: virtual nodes tại hash 150, 1150, 2150
Node 1: virtual nodes tại hash 800, 1800, 2800
Node 2: virtual nodes tại hash 500, 1500, 2500

Virtual nodes càng nhiều = phân phối càng đều.

Triển khai

import { ConsistentHash } from "distributed-cache";

const hash = new ConsistentHash({ virtualNodes: 150 });

hash.addNode({ id: "node-0" });
hash.addNode({ id: "node-1" });
hash.addNode({ id: "node-2" });

// Tìm node chịu trách nhiệm cho key
const node = hash.getNode("user:123");
console.log(node?.id); // "node-1"

// Thêm node mới — chỉ ~25% keys di chuyển
hash.addNode({ id: "node-3" });

// Xóa node — keys redistribute sang các node lân cận
hash.removeNode("node-1");

Sử dụng trong thực tế

Hệ thống	Sử dụng Hash Ring
Redis Cluster	16384 hash slots
Amazon DynamoDB	Consistent hashing cho partitioning
Apache Cassandra	Token ring cho phân phối dữ liệu
Memcached	Client-side consistent hashing