Consistent Hashing: Scale-out Redis Cache và Database Sharding không mất dữ liệu

Bài toán của phép chia modulo

Cách phân phối key đơn giản nhất là:

Với 3 node, user:42 có thể nằm ở node 1. Khi tăng từ 3 lên 4 node, mẫu số thay đổi và phần lớn key có thể trỏ sang node khác. Hậu quả:

Cache miss hàng loạt và cache stampede.
Network, CPU và disk bị bão hòa vì rehydrate/migration.
Router mới đọc shard mới trong khi dữ liệu vẫn ở shard cũ.
Có thể đọc thiếu hoặc ghi sai nơi nếu topology không được version hóa.
Scale-out trở thành một sự kiện rủi ro cao.

Mục tiêu của consistent hashing là giữ phần lớn key ở nguyên vị trí khi membership thay đổi.

Consistent Hashing hoạt động thế nào?

1function fnv1a32(input: string): number {2 let hash = 0x811c9dc5;34 for (let i = 0; i < input.length; i++) {5 hash ^= input.charCodeAt(i);6 hash = Math.imul(hash, 0x01000193);7 }89 return hash >>> 0;10}1112type Token = {13 point: number;14 nodeId: string;15};1617class ConsistentHashRing {18 private tokens: Token[] = [];1920 constructor(private readonly virtualNodes = 128) {}2122 addNode(nodeId: string): void {23 for (let i = 0; i < this.virtualNodes; i++) {24 this.tokens.push({25 point: fnv1a32(`${nodeId}#${i}`),26 nodeId,27 });28 }2930 this.tokens.sort((a, b) => a.point - b.point);31 }3233 removeNode(nodeId: string): void {34 this.tokens = this.tokens.filter((token) => token.nodeId !== nodeId);35 }3637 getNode(key: string): string {38 if (this.tokens.length === 0) {39 throw new Error("Hash ring has no nodes");40 }4142 const point = fnv1a32(key);43 let low = 0;44 let high = this.tokens.length;4546 while (low < high) {47 const mid = Math.floor((low + high) / 2);48 if (this.tokens[mid].point < point) low = mid + 1;49 else high = mid;50 }5152 return this.tokens[low % this.tokens.length].nodeId;53 }5455 getReplicas(key: string, replicationFactor: number): string[] {56 if (replicationFactor < 1 || this.tokens.length === 0) return [];5758 const point = fnv1a32(key);59 let low = 0;60 let high = this.tokens.length;6162 while (low < high) {63 const mid = Math.floor((low + high) / 2);64 if (this.tokens[mid].point < point) low = mid + 1;65 else high = mid;66 }6768 const replicas: string[] = [];69 const seen = new Set<string>();7071 for (let offset = 0; offset < this.tokens.length; offset++) {72 const token = this.tokens[(low + offset) % this.tokens.length];73 if (seen.has(token.nodeId)) continue;7475 seen.add(token.nodeId);76 replicas.push(token.nodeId);77 if (replicas.length === replicationFactor) break;78 }7980 return replicas;81 }82}8384const ring = new ConsistentHashRing(128);85ring.addNode("cache-a");86ring.addNode("cache-b");87ring.addNode("cache-c");8889console.log(ring.getNode("user:42"));90console.log(ring.getReplicas("user:42", 2));

Bài toán của phép chia modulo

Consistent Hashing hoạt động thế nào?

Comments

Virtual Nodes: vì sao một node vật lý cần nhiều điểm?

TypeScript: xây dựng hash ring có virtual nodes

Complexity

Scale-out distributed cache an toàn

Khi thêm cache node

Cache replication

Redis Cluster không dùng consistent-hash ring

Hash tags

Reshard Redis đúng cách

Database Sharding: placement không đồng nghĩa durability

Chọn shard key

Quy trình online resharding không mất write

1. Chuẩn bị và bất biến

2. Capture write đang diễn ra

3. Backfill idempotent

4. Catch up và validation

5. Cutover theo range/token

6. Rollback và cleanup

Routing record trong giai đoạn chuyển shard

Consistent Hashing, Hash Slots và Directory-based Sharding

Rendezvous Hashing: lựa chọn thay thế

Failure modes cần thiết kế trước

Node chết đột ngột

Topology split-brain

Hot key

Node capacity không đồng đều

Scale-in quá nhanh

Cross-shard operation

Test bằng key thật trước production

Observability khi reshard

Cache

Database

Anti-patterns

Production checklist

Kết luận

Tài liệu tham khảo

Related posts

Event Sourcing và CQRS trong Core Banking: Vì sao Ledger là nguồn sự thật?

Consensus Algorithms với Mermaid: Raft, Paxos và cách máy chủ thống nhất dữ liệu

LRU và LFU Cache: Tự thiết kế In-Memory Cache bằng Doubly Linked List + Hash Map