Tuần 10: Consistent Hashing

“Khi thêm một server mới vào cluster 100 nodes, traditional hashing phải di chuyển 99% data. Consistent hashing chỉ di chuyển 1%. Đó là sự khác biệt giữa ‘hệ thống chết 2 tiếng’ và ‘người dùng không biết gì đã xảy ra’.”

Tags: system-design consistent-hashing distributed-systems alex-xu Student: Hieu Prerequisite: Tuan-07-Database-Sharding-Replication · Tuan-05-Load-Balancer Liên quan: Tuan-06-Cache-Strategy · Tuan-07-Database-Sharding-Replication · Tuan-05-Load-Balancer · Tuan-11-Key-Value-Store

1. Context & Why

Analogy đời thường

Hieu, tưởng tượng em có một bàn xoay chia đồ ăn (lazy Susan) ở giữa bàn tiệc. Có 4 người ngồi quanh bàn, mỗi người phụ trách ăn những món nào gần mình nhất — đĩa nào gần ai thì người đó lấy.

Bây giờ thêm 1 người nữa ngồi vào bàn:

Cách truyền thống (modulo hashing): Chia lại tất cả đĩa cho 5 người. Mọi người phải đổi hết đồ ăn trên tay → hỗn loạn, lãng phí thời gian.
Cách consistent hashing: Người mới chỉ nhận những đĩa gần chỗ họ ngồi. Những người khác giữ nguyên đĩa của mình → êm ả, nhanh gọn.

Tương tự, khi bớt 1 người rời bàn:

Cách truyền thống: Chia lại hết.
Consistent hashing: Đĩa của người rời đi chỉ được chia cho người ngồi kế bên → ảnh hưởng tối thiểu.

Consistent hashing (băm nhất quán) chính là cách phân phối data/request sao cho khi thêm hoặc bớt server, chỉ một phần nhỏ data cần di chuyển, không phải chia lại toàn bộ.

Tại sao Alex Xu đặt nó ở Chapter 5?

Vì đây là building block cho mọi hệ thống phân tán. Trước khi thiết kế Key-Value Store, Database Sharding, hay CDN, em phải hiểu cách phân phối data đều giữa các node. Consistent hashing xuất hiện lại ở hầu hết các chương sau — từ Cassandra đến DynamoDB đến Memcached.

2. Deep Dive — Khái niệm cốt lõi

2.1 The Rehashing Problem — Bài toán modulo

Cách hoạt động của Simple Hashing

Cách đơn giản nhất để phân phối key vào N server:

ser v er I n d e x = ha s h (k ey) mod N

Ví dụ: 4 servers (N=4), dùng hash function đơn giản:

Key	hash(key)	hash(key) % 4	Server
”user_1”	1234567	3	Server 3
”user_2”	2345678	2	Server 2
”user_3”	3456789	1	Server 1
”user_4”	4567890	2	Server 2
”user_5”	5678901	1	Server 1
”user_6”	6789012	0	Server 0
”user_7”	7890123	3	Server 3
”user_8”	8901234	2	Server 2

Hoạt động tốt… cho đến khi N thay đổi.

Khi thêm 1 server (N: 4 → 5)

Key	hash(key)	hash % 4 (cũ)	hash % 5 (mới)	Cần di chuyển?
“user_1”	1234567	3	2	Di chuyển
”user_2”	2345678	2	3	Di chuyển
”user_3”	3456789	1	4	Di chuyển
”user_4”	4567890	2	0	Di chuyển
”user_5”	5678901	1	1	Giữ nguyên
”user_6”	6789012	0	2	Di chuyển
”user_7”	7890123	3	3	Giữ nguyên
”user_8”	8901234	2	4	Di chuyển

Kết quả: 6/8 keys (75%) phải di chuyển! Với hệ thống lớn, tỉ lệ di chuyển tiệm cận:

Fraction moved \approx 1 - \frac{1}{N _{n e w}} \approx \frac{N _{n e w} - 1}{N _{n e w}}

Với N=100 servers, thêm 1 server → ~99% data phải di chuyển. Đây là thảm hoạ:

Cache bị invalidate hàng loạt → cache stampede (tất cả request đổ về DB)
DB overload → cascading failure
Downtime kéo dài

2.2 Hash Ring — Vòng tròn băm

Khái niệm cốt lõi

Thay vì dùng modulo, consistent hashing đặt cả server và key lên cùng một vòng tròn (hash ring):

Hash space: Dùng hash function (ví dụ SHA-1) với output range $[0, 2^{160} - 1]$ . Nối đầu với cuối → tạo thành vòng tròn.
Đặt server lên ring: Hash địa chỉ IP hoặc tên server → vị trí trên ring.

p os i t i o n (ser v e r_{i}) = ha s h (ser v e r_{i} . ip) mod 2^{160}

Đặt key lên ring: Hash key → vị trí trên ring.

p os i t i o n (k e y_{j}) = ha s h (k e y_{j}) mod 2^{160}

Quy tắc phân công: Mỗi key được phục vụ bởi server đầu tiên gặp được khi đi theo chiều kim đồng hồ (clockwise) trên ring.

Khi thêm server

Khi thêm server mới vào ring, chỉ có các key nằm giữa server mới và server trước đó (ngược chiều kim đồng hồ) cần di chuyển. Tất cả key khác giữ nguyên server.

Fraction moved \approx \frac{1}{N _{n e w}}

Với N=100 servers, thêm 1 server → chỉ ~1% data di chuyển. So với 99% của modulo hashing!

Khi bớt server

Khi một server bị xoá hoặc chết, chỉ có các key thuộc server đó cần được chuyển sang server kế tiếp (clockwise). Các server khác không bị ảnh hưởng.

2.3 Virtual Nodes (Vnodes) — Node ảo

Vấn đề: Phân bố không đều

Với số lượng server ít (ví dụ 3-4 servers), vị trí trên ring có thể không đều nhau, dẫn đến:

Server A phụ trách 60% key space
Server B phụ trách 10% key space
Server C phụ trách 30% key space

Giải pháp: Virtual Nodes

Thay vì mỗi server chỉ có 1 vị trí trên ring, mỗi server có V vị trí (virtual nodes):

p os i t i o n s (ser v e r_{i}) = {ha s h (ser v e r_{i} -vnode- k) ∣ k = 0, 1, ..., V - 1}

Ví dụ: Với V=150, server A có 150 điểm rải đều trên ring. Server B cũng có 150 điểm. Tổng cộng ring có 300 điểm → phân bố đều hơn nhiều.

Số Virtual Nodes (V)	Standard Deviation (% load)	Nhận xét
1	~50-80%	Rất không đều
10	~20-30%	Vẫn lệch đáng kể
100	~5-10%	Chấp nhận được
150	~3-5%	Khá đều (Cassandra default)
200+	~1-3%	Rất đều, nhưng tốn memory

Trade-off: Nhiều vnodes hơn → phân bố đều hơn, nhưng tốn nhiều memory hơn cho ring metadata.

Cassandra mặc định sử dụng num_tokens = 256 (256 vnodes/node). DynamoDB cũng dùng virtual nodes nhưng với cơ chế partition riêng.

Weighted Virtual Nodes

Khi các server có cấu hình khác nhau (server mạnh vs yếu), có thể gán số vnodes khác nhau:

V_{i} = V_{ba se} \times \frac{c a p a c i t y _{i}}{c a p a c i t y _{a vg}}

Ví dụ: Server A (32GB RAM) được gán 200 vnodes, Server B (16GB RAM) được gán 100 vnodes → Server A nhận gấp đôi traffic, tương xứng với capacity.

2.4 Jump Consistent Hashing

Google giới thiệu Jump Consistent Hash (2014) — một thuật toán đơn giản hơn, không cần ring:

int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
    int64_t b = -1, j = 0;
    while (j < num_buckets) {
        b = j;
        key = key * 2862933555777941757ULL + 1;
        j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
    }
    return b;
}

Ưu điểm:

O(1) memory — không cần lưu ring
Phân bố gần như hoàn hảo
Code cực ngắn (5 dòng)

Nhược điểm:

Chỉ hỗ trợ thêm/bớt node ở cuối (sequential). Không hỗ trợ xoá node ở giữa.
Không phù hợp cho cluster mà node có thể chết bất kỳ lúc nào.

Use case: Phù hợp cho hệ thống mà node được thêm tuần tự và ít khi bị xoá (ví dụ: sharding chiến lược).

2.5 Rendezvous Hashing (Highest Random Weight)

Một cách tiếp cận khác — thay vì ring, mỗi key tính score cho tất cả server rồi chọn server có score cao nhất:

ser v er = ar g s_{i} max (ha s h (k ey, s_{i}))

Ưu điểm:

Không cần ring hay virtual nodes
Khi bớt 1 server, chỉ key thuộc server đó phải di chuyển (giống consistent hashing)
Đơn giản, dễ hiểu

Nhược điểm:

O(N) cho mỗi lookup (phải tính hash với tất cả N servers)
Không phù hợp khi N lớn (hàng nghìn servers)

Use case: Khi số lượng server nhỏ (< 50), ví dụ: DNS routing, CDN node selection.

2.6 Applications — Ứng dụng thực tế

Ứng dụng	Mô tả	Hệ thống sử dụng
Cache Distribution (phân phối cache)	Xác định request được cache ở server nào	Memcached, Redis Cluster
Database Sharding (phân mảnh database)	Xác định data nằm ở shard nào	Cassandra, DynamoDB, CockroachDB
Load Balancing (cân bằng tải)	Phân phối request đến backend server	Nginx, HAProxy, Envoy
CDN Routing (định tuyến CDN)	Xác định edge server nào phục vụ content	Akamai, CloudFlare
Distributed File System	Xác định chunk được lưu ở node nào	GFS, HDFS, Ceph
Service Discovery	Phân phối service instance cho client	Consul, etcd

2.7 Consistent Hashing trong Real Systems

Cassandra

Dùng Murmur3Partitioner (default) — hash key thành 64-bit token
Token range: $[- 2^{63}, 2^{63} - 1]$
Mỗi node sở hữu num_tokens virtual nodes (default 256)
Khi node mới join, Cassandra tự động stream data từ các node lân cận
Replication: Mỗi key được replicate tới N node tiếp theo trên ring (replication factor)

Amazon DynamoDB

Sử dụng consistent hashing có cải tiến (virtual nodes + controlled partitioning)
Partition key được hash bằng MD5 → xác định partition
Khi split partition, chỉ di chuyển data trong partition bị split
Auto-scaling: DynamoDB tự động chia/gộp partition dựa trên throughput

Memcached (Client-side)

Consistent hashing được implement ở client (libmemcached, ketama)
Client tự xây dựng hash ring từ danh sách server
Khi thêm/bớt memcached node, chỉ ~1/N key bị cache miss
ketama algorithm: Mỗi server có 100-200 points trên ring

Nginx (upstream hashing)

upstream backend {
    hash $request_uri consistent;
    server backend1.example.com;
    server backend2.example.com;
    server backend3.example.com;
}

Nginx dùng ketama consistent hashing cho upstream. Khi backend node chết, chỉ traffic của node đó được redistribute.

2.8 Implementation Details — Chi tiết triển khai

Cấu trúc dữ liệu: TreeMap / SortedMap

Hash ring được implement hiệu quả nhất bằng balanced binary search tree (TreeMap trong Java, SortedContainers trong Python):

Thêm node: Insert V entries vào TreeMap → O(V log M), với M = tổng entries trên ring
Lookup key: Tìm entry đầu tiên có hash >= hash(key) → O(log M)
Xoá node: Remove V entries → O(V log M)

Trong Java, TreeMap.ceilingEntry(hash) cho ta server tiếp theo theo chiều clockwise. Nếu null (vượt quá max), wrap around bằng TreeMap.firstEntry().

Hash Function Choice

Hash Function	Output Size	Tốc độ	Collision Resistance	Use Case
MD5	128-bit	Nhanh	Yếu (broken)	Legacy systems
SHA-1	160-bit	Trung bình	Yếu (broken)	Legacy systems
SHA-256	256-bit	Chậm hơn	Mạnh	Security-critical
MurmurHash3	32/128-bit	Rất nhanh	Non-cryptographic	Cassandra, general use
xxHash	32/64/128-bit	Cực nhanh	Non-cryptographic	Performance-critical
SipHash	64/128-bit	Nhanh	Keyed hash, anti-DoS	Hash table protection

Best practice: Dùng MurmurHash3 hoặc xxHash cho consistent hashing (nhanh, phân bố tốt). Dùng SipHash khi cần chống hash flooding attack.

2.9 Data Migration khi thêm/bớt Node

Thêm node mới

Xác định phạm vi ảnh hưởng: Node mới nhận key từ node kế tiếp (clockwise)
Stream data: Copy data thuộc phạm vi từ node cũ sang node mới
Cập nhật routing: Cập nhật hash ring ở tất cả client/coordinator
Verify: Kiểm tra data integrity sau migration
Cleanup: Xoá data đã migrate ở node cũ (sau grace period)

Bớt node (decommission)

Announce: Đánh dấu node sắp bị xoá
Stream data: Chuyển tất cả data sang node kế tiếp (clockwise)
Drain connections: Chờ in-flight requests hoàn thành
Remove from ring: Xoá node khỏi hash ring
Shutdown: Tắt node

Zero-downtime migration

Trong production, data migration phải diễn ra trong khi hệ thống vẫn phục vụ request:

Read path: Read cả node cũ lẫn node mới trong giai đoạn migration
Write path: Write vào cả hai node (dual-write) hoặc chỉ write vào node mới
Consistency: Dùng vector clock hoặc timestamp để resolve conflict

3. Estimation — Ước lượng

3.1 Data Movement: Modulo vs Consistent Hashing

Scenario: Cluster có N=100 nodes, mỗi node chứa 500GB data. Thêm 1 node mới.

Modulo Hashing

Data moved = Total data \times \frac{N _{n e w} - 1}{N _{n e w}}

= 100 \times 500 GB \times \frac{100}{101} \approx 49, 505 GB \approx 48.3 TB

Thời gian = \frac{48.3 TB}{1 Gbps} = \frac{48 , 300 \times 8}{1} \approx 386, 400 s \approx 4.5 ng \overset{a}{ˋ} y

4.5 ngày downtime hoặc degraded performance!

Consistent Hashing

Data moved = Total data \times \frac{1}{N _{n e w}}

= 100 \times 500 GB \times \frac{1}{101} \approx 495 GB

Thời gian = \frac{495 GB \times 8}{1 Gbps} = 3, 960 s \approx 66 ph \overset{u}{ˊ} t

Chỉ 66 phút, có thể chạy background mà user không biết!

Metric	Modulo Hashing	Consistent Hashing	Cải thiện
Data moved	48.3 TB	495 GB	~100x ít hơn
Thời gian (1Gbps)	~4.5 ngày	~66 phút	~100x nhanh hơn
Cache miss spike	~99%	~1%	Hệ thống ổn định

3.2 Memory cho Hash Ring với Virtual Nodes

Scenario: 100 physical nodes, mỗi node có V=200 virtual nodes.

Total entries tr \overset{e}{ˆ} n ring = N \times V = 100 \times 200 = 20, 000

Mỗi entry trên ring cần lưu:

Hash value: 8 bytes (64-bit)
Node identifier: 32 bytes (IP + port + metadata)
TreeMap overhead: ~48 bytes (Java TreeMap.Entry: key, value, left, right, parent, color)

Memory per entry = 8 + 32 + 48 = 88 bytes

Total ring memory = 20, 000 \times 88 = 1, 760, 000 bytes \approx 1.7 MB

Kết luận: Ring metadata cực kỳ nhỏ! Ngay cả với 1,000 nodes × 200 vnodes = 200,000 entries → chỉ ~17 MB. Memory không phải bottleneck.

3.3 Lookup Performance

Lookup time = O (lo g (Total entries)) = O (lo g (N \times V))

= O (lo g (20, 000)) \approx O (15)

Mỗi comparison ~10ns → lookup ~150ns. Nhanh hơn nhiều so với một network round trip (0.5ms = 500,000ns).

4. Security First — Bảo mật Consistent Hashing

4.1 Hash Collision Attacks

Threat: Attacker cố tình tạo các key có cùng hash value → tất cả key đổ vào cùng một server → server đó bị overload (DoS).

Ví dụ: Nếu dùng hash function yếu (MD5), attacker có thể craft hàng triệu key khác nhau mà hash ra cùng vùng trên ring.

Impact:

Một node bị quá tải → timeout → cascading failure
Cache hit rate giảm mạnh
Hệ thống mất availability

Mitigation:

Dùng keyed hash function (HMAC-SHA256, SipHash) với secret key
Server-side key transformation: internal_key = HMAC(secret, user_key)
Attacker không biết secret → không thể predict hash position

4.2 Hash Flooding DoS Attack

Threat: Attacker gửi lượng lớn request với key được thiết kế để tập trung vào một vùng trên hash ring → overload subset of servers.

Scenario thực tế:

Năm 2011, hash collision DoS attack ảnh hưởng PHP, Java, Python, Ruby
Attacker gửi HTTP POST với hàng nghìn parameters có cùng hash → hash table degenerate thành O(n) linked list
CPU usage 100% chỉ với vài request

Mitigation:

# BAD: Dùng hash() mặc định Python (dễ bị predict)
server = ring.get_node(hash(user_key))
 
# GOOD: Dùng SipHash với random secret key
import siphash
SECRET_KEY = os.urandom(16)  # Random key, khởi tạo khi server start
 
def secure_hash(key: str) -> int:
    return siphash.SipHash_2_4(SECRET_KEY, key.encode()).hash()
 
server = ring.get_node(secure_hash(user_key))

Python 3.3+ mặc định đã dùng SipHash cho hash() built-in, với random seed mỗi lần khởi động (PYTHONHASHSEED). Nhưng trong consistent hashing, ta cần deterministic hash across tất cả client → phải dùng explicit keyed hash.

4.3 SipHash — Hash function chống DoS

SipHash (2012, Jean-Philippe Aumasson & Daniel J. Bernstein) được thiết kế đặc biệt cho hash table protection:

Thuộc tính	SipHash	MD5	MurmurHash3
Keyed	Có (128-bit key)	Không	Không
Speed	Nhanh (~1GB/s)	Trung bình	Rất nhanh (~5GB/s)
Anti-DoS	Có	Không	Không
Collision resistance	PRF-secure	Broken	Non-crypto

Khi nào dùng SipHash cho consistent hashing:

Hệ thống chấp nhận request từ untrusted client (public API)
Key space có thể bị attacker kiểm soát (user-generated key)
Cần defense-in-depth cho critical infrastructure

Khi nào dùng MurmurHash3:

Hệ thống nội bộ, key không bị attacker kiểm soát
Cần maximum performance
Internal service-to-service communication

4.4 Ring Metadata Security

Hash ring metadata (danh sách node, vị trí trên ring) là sensitive information:

Attacker biết ring topology → biết server nào phục vụ key nào → targeted attack
Nên encrypt ring metadata khi truyền giữa các node
Dùng mTLS cho giao tiếp giữa các coordinator node

5. DevOps — Vận hành Consistent Hashing

5.1 Implementing Consistent Hashing trong Nginx

# /etc/nginx/conf.d/consistent-hash-upstream.conf
 
upstream cache_backend {
    # Consistent hashing dựa trên request URI
    hash $request_uri consistent;
 
    server cache1.internal:11211 weight=3;  # Máy mạnh → weight cao
    server cache2.internal:11211 weight=2;
    server cache3.internal:11211 weight=1;
    server cache4.internal:11211 weight=2;
 
    # Khi server down, chỉ key của server đó bị redistribute
    # Không ảnh hưởng key của server khác
}
 
upstream app_backend {
    # Consistent hashing dựa trên client IP (session affinity)
    hash $remote_addr consistent;
 
    server app1.internal:8080;
    server app2.internal:8080;
    server app3.internal:8080;
}
 
server {
    listen 80;
 
    location /api/ {
        proxy_pass http://app_backend;
        proxy_next_upstream error timeout http_502 http_503;
    }
 
    location /cache/ {
        proxy_pass http://cache_backend;
    }
}

Lưu ý: hash ... consistent trong Nginx sử dụng ketama algorithm. Nếu không có từ khoá consistent, Nginx dùng modulo hashing thông thường.

5.2 Monitoring Key Distribution — Phát hiện mất cân bằng

# prometheus-alerts.yml
groups:
  - name: consistent_hashing_alerts
    rules:
      # Alert khi node có quá nhiều key so với trung bình
      - alert: HashRingHotspot
        expr: |
          (
            node_keys_total / ignoring(instance) group_left
            avg(node_keys_total)
          ) > 1.5
        for: 10m
        labels:
          severity: warning
        annotations:
          summary: "Node {{ $labels.instance }} has {{ $value }}x average keys — possible hotspot"
          description: "Kiểm tra virtual node distribution hoặc hot key pattern"
 
      # Alert khi node mới join nhưng chưa nhận đủ data
      - alert: HashRingMigrationStalled
        expr: |
          node_migration_bytes_remaining > 0
          and
          rate(node_migration_bytes_transferred[5m]) == 0
        for: 15m
        labels:
          severity: critical
        annotations:
          summary: "Data migration to {{ $labels.instance }} stalled"
 
      # Alert khi cache hit rate giảm sau node change
      - alert: CacheHitRateDropAfterRebalance
        expr: |
          (
            rate(cache_hits_total[5m]) /
            (rate(cache_hits_total[5m]) + rate(cache_misses_total[5m]))
          ) < 0.7
          and
          changes(hash_ring_version[15m]) > 0
        for: 5m
        labels:
          severity: warning
        annotations:
          summary: "Cache hit rate dropped to {{ $value | humanizePercentage }} after ring change"
 
      # Alert khi phân bố key quá lệch (standard deviation cao)
      - alert: HashRingUnbalanced
        expr: |
          stddev(node_keys_total) / avg(node_keys_total) > 0.3
        for: 30m
        labels:
          severity: warning
        annotations:
          summary: "Key distribution stddev/mean = {{ $value }} — consider increasing virtual nodes"

5.3 Grafana Dashboard cho Hash Ring

Panel	PromQL Query	Mục đích
Keys per Node	`node_keys_total`	Bar chart, phát hiện imbalance
Key Distribution Heatmap	`rate(node_requests_total[5m])`	Xem request distribution realtime
Migration Progress	`node_migration_bytes_transferred / node_migration_bytes_total`	Gauge, theo dõi data migration
Ring Change History	`changes(hash_ring_version[1h])`	Timeline, correlate với anomalies
P99 Latency per Node	`histogram_quantile(0.99, rate(request_duration_bucket[5m]))`	Phát hiện node chậm
Cache Hit Rate Trend	`rate(cache_hits_total[5m]) / rate(cache_requests_total[5m])`	Phát hiện cache miss spike

5.4 Detecting & Handling Hotspots

Hotspot xảy ra khi một key (hoặc nhóm key) nhận quá nhiều traffic:

Cách phát hiện:

# Kiểm tra request distribution trên Memcached nodes
for node in cache{1..4}.internal; do
  echo "=== $node ==="
  echo "stats" | nc $node 11211 | grep -E "cmd_get|cmd_set|bytes_read"
done

Cách xử lý:

Key replication: Hot key được cache ở nhiều node (ví dụ: thêm random suffix key_v1, key_v2)
Local cache: Thêm L1 cache (in-process) trước consistent hash ring
Tăng virtual nodes cho node bị hotspot → giãn traffic ra
Key splitting: Chia hot key thành nhiều sub-key

6. Code Implementation

6.1 Python: Consistent Hashing with Virtual Nodes

"""
Consistent Hashing Implementation
Full-featured with virtual nodes, weighted nodes, and key migration analysis.
"""
 
import hashlib
from bisect import bisect_right, insort
from collections import defaultdict
from typing import Optional
 
 
class ConsistentHashRing:
    """
    Consistent Hash Ring with virtual nodes.
 
    Hash ring sử dụng MD5 (cho demo) hoặc có thể thay bằng
    MurmurHash3/xxHash cho production.
    """
 
    def __init__(self, num_virtual_nodes: int = 150):
        """
        Args:
            num_virtual_nodes: Số virtual nodes mặc định cho mỗi physical node.
                Cassandra dùng 256. Giá trị 100-200 là hợp lý cho hầu hết use case.
        """
        self.num_virtual_nodes = num_virtual_nodes
        self._sorted_hashes: list[int] = []       # Sorted list các hash position
        self._ring: dict[int, str] = {}            # hash_position → node_name
        self._nodes: dict[str, int] = {}           # node_name → num_vnodes
        self._key_count: dict[str, int] = defaultdict(int)  # node_name → key count
 
    def _hash(self, key: str) -> int:
        """Hash function: MD5 → 32-bit integer."""
        digest = hashlib.md5(key.encode("utf-8")).hexdigest()
        return int(digest[:8], 16)  # Lấy 32-bit đầu
 
    def add_node(self, node: str, num_vnodes: Optional[int] = None) -> list[str]:
        """
        Thêm node vào ring.
 
        Args:
            node: Tên hoặc IP của node (ví dụ: "cache-server-1")
            num_vnodes: Số virtual nodes (None = dùng default).
                        Dùng giá trị cao hơn cho server mạnh hơn.
 
        Returns:
            List các node bị ảnh hưởng (mất một phần key space)
        """
        vnodes = num_vnodes or self.num_virtual_nodes
        self._nodes[node] = vnodes
        affected_nodes = set()
 
        for i in range(vnodes):
            vnode_key = f"{node}#vnode{i}"
            h = self._hash(vnode_key)
 
            # Tìm node hiện tại sở hữu vùng này (sẽ bị mất key)
            idx = bisect_right(self._sorted_hashes, h) % len(self._sorted_hashes) \
                if self._sorted_hashes else 0
            if self._sorted_hashes:
                affected_node = self._ring.get(self._sorted_hashes[idx])
                if affected_node and affected_node != node:
                    affected_nodes.add(affected_node)
 
            self._ring[h] = node
            insort(self._sorted_hashes, h)
 
        return list(affected_nodes)
 
    def remove_node(self, node: str) -> list[str]:
        """
        Xoá node khỏi ring.
 
        Returns:
            List các node sẽ nhận thêm key (kế tiếp clockwise)
        """
        if node not in self._nodes:
            raise ValueError(f"Node '{node}' not found in ring")
 
        vnodes = self._nodes[node]
        receiving_nodes = set()
 
        for i in range(vnodes):
            vnode_key = f"{node}#vnode{i}"
            h = self._hash(vnode_key)
 
            # Tìm node kế tiếp sẽ nhận key
            idx = self._sorted_hashes.index(h)
            self._sorted_hashes.remove(h)
            del self._ring[h]
 
            if self._sorted_hashes:
                next_idx = idx % len(self._sorted_hashes)
                receiving_node = self._ring[self._sorted_hashes[next_idx]]
                if receiving_node != node:
                    receiving_nodes.add(receiving_node)
 
        del self._nodes[node]
        self._key_count.pop(node, None)
        return list(receiving_nodes)
 
    def get_node(self, key: str) -> Optional[str]:
        """
        Tìm node phục vụ key này.
        Đi clockwise trên ring từ vị trí hash(key).
 
        Time complexity: O(log N) với N = tổng virtual nodes.
        """
        if not self._sorted_hashes:
            return None
 
        h = self._hash(key)
        idx = bisect_right(self._sorted_hashes, h)
 
        # Wrap around: nếu vượt quá cuối ring, quay lại đầu
        if idx == len(self._sorted_hashes):
            idx = 0
 
        node = self._ring[self._sorted_hashes[idx]]
        self._key_count[node] += 1
        return node
 
    def get_nodes_for_replication(self, key: str, replicas: int = 3) -> list[str]:
        """
        Tìm N node cho replication (dùng trong Cassandra-style replication).
        Chọn N physical node khác nhau theo chiều clockwise.
        """
        if not self._sorted_hashes:
            return []
 
        h = self._hash(key)
        idx = bisect_right(self._sorted_hashes, h)
        nodes = []
        seen = set()
 
        for i in range(len(self._sorted_hashes)):
            current_idx = (idx + i) % len(self._sorted_hashes)
            node = self._ring[self._sorted_hashes[current_idx]]
 
            if node not in seen:
                nodes.append(node)
                seen.add(node)
 
            if len(nodes) == replicas:
                break
 
        return nodes
 
    def get_distribution(self) -> dict[str, float]:
        """Tính phần trăm key space mỗi node sở hữu."""
        if not self._sorted_hashes:
            return {}
 
        distribution: dict[str, int] = defaultdict(int)
        total_space = 2**32  # 32-bit hash space
 
        for i in range(len(self._sorted_hashes)):
            current_hash = self._sorted_hashes[i]
            prev_hash = self._sorted_hashes[i - 1] if i > 0 else self._sorted_hashes[-1]
            node = self._ring[current_hash]
 
            if i == 0:
                # Vùng từ prev_hash đến cuối + đầu đến current_hash
                space = (total_space - prev_hash) + current_hash
            else:
                space = current_hash - prev_hash
 
            distribution[node] += space
 
        return {node: (space / total_space) * 100
                for node, space in distribution.items()}
 
    def stats(self) -> str:
        """In thống kê phân bố."""
        dist = self.get_distribution()
        if not dist:
            return "Ring is empty"
 
        avg = 100.0 / len(dist)
        lines = [
            f"{'Node':<20} {'Key Space %':>12} {'Deviation':>12} {'VNodes':>8}",
            "-" * 55,
        ]
        for node in sorted(dist):
            pct = dist[node]
            dev = pct - avg
            vnodes = self._nodes.get(node, 0)
            lines.append(f"{node:<20} {pct:>11.2f}% {dev:>+11.2f}% {vnodes:>8}")
 
        lines.append("-" * 55)
        lines.append(f"{'Total nodes':<20} {len(dist):>12}")
        lines.append(f"{'Total vnodes':<20} {len(self._sorted_hashes):>12}")
        lines.append(f"{'Ideal per node':<20} {avg:>11.2f}%")
 
        import statistics
        values = list(dist.values())
        lines.append(f"{'Std deviation':<20} {statistics.stdev(values):>11.2f}%")
 
        return "\n".join(lines)
 
 
# === Demo & Visualization ===
 
def demo_migration_analysis():
    """Demo: phân tích data movement khi thêm node."""
    print("=" * 60)
    print("DEMO: Data Migration Analysis")
    print("=" * 60)
 
    ring = ConsistentHashRing(num_virtual_nodes=150)
 
    # Setup initial cluster: 4 nodes
    for i in range(4):
        ring.add_node(f"node-{i}")
 
    # Assign 10,000 keys
    key_to_node_before: dict[str, str] = {}
    for i in range(10_000):
        key = f"user:{i}"
        node = ring.get_node(key)
        key_to_node_before[key] = node
 
    print("\n--- Before adding node-4 ---")
    print(ring.stats())
 
    # Thêm node mới
    affected = ring.add_node("node-4")
    print(f"\nAffected nodes: {affected}")
 
    # Đếm key phải di chuyển
    moved = 0
    for key, old_node in key_to_node_before.items():
        new_node = ring.get_node(key)
        if old_node != new_node:
            moved += 1
 
    print(f"\n--- After adding node-4 ---")
    print(ring.stats())
    print(f"\nKeys moved: {moved}/{len(key_to_node_before)} "
          f"({moved/len(key_to_node_before)*100:.1f}%)")
    print(f"Ideal movement: {100/5:.1f}% (1/N_new)")
 
 
def demo_vnode_impact():
    """Demo: ảnh hưởng của số virtual nodes lên phân bố."""
    print("\n" + "=" * 60)
    print("DEMO: Impact of Virtual Node Count")
    print("=" * 60)
 
    import statistics
 
    for vnodes in [1, 10, 50, 100, 150, 200, 500]:
        ring = ConsistentHashRing(num_virtual_nodes=vnodes)
        for i in range(5):
            ring.add_node(f"node-{i}")
 
        dist = ring.get_distribution()
        values = list(dist.values())
        std = statistics.stdev(values)
        min_v = min(values)
        max_v = max(values)
 
        print(f"VNodes={vnodes:>4} | StdDev={std:5.2f}% | "
              f"Min={min_v:5.1f}% | Max={max_v:5.1f}% | "
              f"Range={max_v-min_v:5.1f}%")
 
 
if __name__ == "__main__":
    demo_migration_analysis()
    demo_vnode_impact()

6.2 Java: TreeMap-based Implementation

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.*;
 
/**
 * Consistent Hash Ring sử dụng Java TreeMap.
 *
 * TreeMap (Red-Black Tree) cho phép:
 * - ceilingEntry(): tìm node kế tiếp clockwise → O(log N)
 * - put/remove: thêm/xoá vnode → O(log N)
 */
public class ConsistentHashRing<T> {
 
    private final TreeMap<Long, T> ring = new TreeMap<>();
    private final Map<T, Integer> nodeVnodeCount = new HashMap<>();
    private final int defaultVnodes;
 
    public ConsistentHashRing(int defaultVnodes) {
        this.defaultVnodes = defaultVnodes;
    }
 
    /**
     * Hash function: MD5 → long (64-bit).
     * Production nên dùng MurmurHash3 hoặc xxHash.
     */
    private long hash(String key) {
        try {
            MessageDigest md = MessageDigest.getInstance("MD5");
            byte[] digest = md.digest(key.getBytes());
            // Lấy 8 bytes đầu → long
            long h = 0;
            for (int i = 0; i < 8; i++) {
                h = (h << 8) | (digest[i] & 0xFF);
            }
            return h;
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException(e);
        }
    }
 
    /** Thêm node vào ring với số vnodes mặc định. */
    public void addNode(T node) {
        addNode(node, defaultVnodes);
    }
 
    /** Thêm node vào ring với số vnodes tuỳ chỉnh. */
    public void addNode(T node, int vnodes) {
        nodeVnodeCount.put(node, vnodes);
        for (int i = 0; i < vnodes; i++) {
            long h = hash(node.toString() + "#vnode" + i);
            ring.put(h, node);
        }
    }
 
    /** Xoá node khỏi ring. */
    public void removeNode(T node) {
        Integer vnodes = nodeVnodeCount.remove(node);
        if (vnodes == null) return;
 
        for (int i = 0; i < vnodes; i++) {
            long h = hash(node.toString() + "#vnode" + i);
            ring.remove(h);
        }
    }
 
    /**
     * Tìm node phục vụ key.
     * Dùng TreeMap.ceilingEntry() → O(log N).
     */
    public T getNode(String key) {
        if (ring.isEmpty()) return null;
 
        long h = hash(key);
 
        // ceilingEntry: entry nhỏ nhất >= h (clockwise)
        Map.Entry<Long, T> entry = ring.ceilingEntry(h);
 
        // Wrap around nếu vượt quá cuối ring
        if (entry == null) {
            entry = ring.firstEntry();
        }
 
        return entry.getValue();
    }
 
    /**
     * Tìm N node cho replication (distinct physical nodes).
     */
    public List<T> getNodesForReplication(String key, int replicas) {
        if (ring.isEmpty()) return Collections.emptyList();
 
        long h = hash(key);
        List<T> nodes = new ArrayList<>();
        Set<T> seen = new HashSet<>();
 
        // Lấy tail map từ h trở đi (clockwise)
        NavigableMap<Long, T> tailMap = ring.tailMap(h, false);
        Iterator<T> iter = tailMap.values().iterator();
 
        // Duyệt từ h đến cuối ring
        collectNodes(iter, nodes, seen, replicas);
 
        // Wrap around: duyệt từ đầu ring
        if (nodes.size() < replicas) {
            collectNodes(ring.values().iterator(), nodes, seen, replicas);
        }
 
        return nodes;
    }
 
    private void collectNodes(Iterator<T> iter, List<T> nodes,
                              Set<T> seen, int replicas) {
        while (iter.hasNext() && nodes.size() < replicas) {
            T node = iter.next();
            if (seen.add(node)) {
                nodes.add(node);
            }
        }
    }
 
    /** Trả về thống kê phân bố. */
    public Map<T, Double> getDistribution() {
        Map<T, Long> spaceMap = new HashMap<>();
        long totalSpace = Long.MAX_VALUE;  // Simplified
 
        Long prevHash = null;
        for (Map.Entry<Long, T> entry : ring.entrySet()) {
            long currentHash = entry.getKey();
            T node = entry.getValue();
 
            if (prevHash != null) {
                long space = currentHash - prevHash;
                spaceMap.merge(node, space, Long::sum);
            }
            prevHash = currentHash;
        }
 
        // Tính percentage
        long totalAllocated = spaceMap.values().stream()
                .mapToLong(Long::longValue).sum();
        Map<T, Double> result = new HashMap<>();
        for (Map.Entry<T, Long> e : spaceMap.entrySet()) {
            result.put(e.getKey(), (double) e.getValue() / totalAllocated * 100);
        }
        return result;
    }
 
    public int size() {
        return ring.size();
    }
 
    public int nodeCount() {
        return nodeVnodeCount.size();
    }
 
    // === Demo ===
    public static void main(String[] args) {
        ConsistentHashRing<String> ring = new ConsistentHashRing<>(150);
 
        // Add nodes
        ring.addNode("cache-1");
        ring.addNode("cache-2");
        ring.addNode("cache-3");
        ring.addNode("cache-4");
 
        System.out.println("Ring size: " + ring.size() + " vnodes, "
                + ring.nodeCount() + " physical nodes");
 
        // Lookup
        String[] keys = {"user:1001", "user:1002", "session:abc", "product:42"};
        for (String key : keys) {
            String node = ring.getNode(key);
            List<String> replicas = ring.getNodesForReplication(key, 3);
            System.out.printf("Key %-20s → Node: %-10s | Replicas: %s%n",
                    key, node, replicas);
        }
 
        // Distribution
        System.out.println("\nDistribution:");
        ring.getDistribution().forEach((node, pct) ->
                System.out.printf("  %-10s: %.2f%%%n", node, pct));
    }
}

6.3 Key Distribution Visualization (Python)

"""
Visualization: Key distribution trên Consistent Hash Ring.
Chạy: pip install matplotlib
"""
 
import hashlib
import math
from collections import defaultdict
 
 
def visualize_ring_ascii(nodes: dict[str, int], num_keys: int = 1000):
    """
    ASCII visualization của hash ring distribution.
 
    Args:
        nodes: {node_name: num_vnodes}
        num_keys: Số key để simulate
    """
    # Build ring
    ring_points = []  # (hash_position, node_name)
    for node, vnodes in nodes.items():
        for i in range(vnodes):
            h = int(hashlib.md5(f"{node}#vnode{i}".encode()).hexdigest()[:8], 16)
            ring_points.append((h, node))
    ring_points.sort()
 
    # Assign keys
    key_assignment = defaultdict(int)
    for i in range(num_keys):
        key_hash = int(hashlib.md5(f"key-{i}".encode()).hexdigest()[:8], 16)
        # Binary search for next clockwise node
        idx = 0
        for j, (h, _) in enumerate(ring_points):
            if h >= key_hash:
                idx = j
                break
        else:
            idx = 0  # wrap around
        _, node = ring_points[idx]
        key_assignment[node] += 1
 
    # Print distribution
    max_keys = max(key_assignment.values()) if key_assignment else 1
    ideal = num_keys / len(nodes)
 
    print(f"\nKey Distribution ({num_keys} keys across {len(nodes)} nodes)")
    print(f"Ideal: {ideal:.0f} keys/node ({100/len(nodes):.1f}%)")
    print("-" * 65)
 
    for node in sorted(key_assignment, key=lambda n: key_assignment[n], reverse=True):
        count = key_assignment[node]
        pct = count / num_keys * 100
        bar_len = int(count / max_keys * 40)
        bar = "█" * bar_len + "░" * (40 - bar_len)
        deviation = ((count - ideal) / ideal) * 100
        print(f"  {node:<12} {bar} {count:>5} ({pct:5.1f}%) [{deviation:>+6.1f}%]")
 
    print("-" * 65)
    values = list(key_assignment.values())
    import statistics
    print(f"  Std Dev: {statistics.stdev(values):.1f} keys "
          f"({statistics.stdev(values)/ideal*100:.1f}% of ideal)")
    print(f"  Min/Max ratio: {min(values)/max(values):.2f}")
 
 
if __name__ == "__main__":
    print("=" * 65)
    print("Case 1: Few virtual nodes (V=3) — BAD distribution")
    print("=" * 65)
    visualize_ring_ascii(
        {"node-A": 3, "node-B": 3, "node-C": 3, "node-D": 3},
        num_keys=10_000,
    )
 
    print("\n" + "=" * 65)
    print("Case 2: Many virtual nodes (V=150) — GOOD distribution")
    print("=" * 65)
    visualize_ring_ascii(
        {"node-A": 150, "node-B": 150, "node-C": 150, "node-D": 150},
        num_keys=10_000,
    )
 
    print("\n" + "=" * 65)
    print("Case 3: Weighted nodes (V=200 for strong, V=100 for weak)")
    print("=" * 65)
    visualize_ring_ascii(
        {"strong-1": 200, "strong-2": 200, "weak-1": 100, "weak-2": 100},
        num_keys=10_000,
    )

7. System Design Diagrams

7.1 Hash Ring — Cơ bản

graph TD
    subgraph "Hash Ring (0 → 2³² − 1)"
        direction TB
        A["🟢 Server A<br/>hash = 0x1A..."]
        B["🔵 Server B<br/>hash = 0x5F..."]
        C["🟠 Server C<br/>hash = 0x9B..."]
        D["🟣 Server D<br/>hash = 0xD2..."]
    end

    K1["Key 'user:1'<br/>hash = 0x0E..."] -->|clockwise| A
    K2["Key 'user:2'<br/>hash = 0x3C..."] -->|clockwise| B
    K3["Key 'user:3'<br/>hash = 0x7A..."] -->|clockwise| C
    K4["Key 'user:4'<br/>hash = 0xA5..."] -->|clockwise| D
    K5["Key 'user:5'<br/>hash = 0xDF..."] -->|clockwise → wrap| A

    style A fill:#4caf50,color:#fff
    style B fill:#2196f3,color:#fff
    style C fill:#ff9800,color:#fff
    style D fill:#9c27b0,color:#fff

7.2 Before/After Adding Node — So sánh

flowchart LR
    subgraph BEFORE["BEFORE: 4 Nodes"]
        direction TB
        B_A["Server A"] --- B_K1["key1 ✓"]
        B_A --- B_K2["key2 ✓"]
        B_B["Server B"] --- B_K3["key3 ✓"]
        B_B --- B_K4["key4 ✓"]
        B_C["Server C"] --- B_K5["key5 ✓"]
        B_C --- B_K6["key6 ✓"]
        B_D["Server D"] --- B_K7["key7 ✓"]
        B_D --- B_K8["key8 ✓"]
    end

    subgraph AFTER["AFTER: 5 Nodes (Node E added)"]
        direction TB
        A_A["Server A"] --- A_K1["key1 ✓"]
        A_A --- A_K2["key2 ✓"]
        A_B["Server B"] --- A_K3["key3 ✓"]
        A_B --- A_K4["key4 ✓"]
        A_C["Server C"] --- A_K5["key5 ✓"]
        A_D["Server D"] --- A_K7["key7 ✓"]
        A_D --- A_K8["key8 ✓"]
        A_E["Server E 🆕"] --- A_K6["key6 ↩ từ C"]
    end

    BEFORE -->|"Thêm Server E<br/>Chỉ key6 di chuyển<br/>(~1/5 = 20%)"| AFTER

    style A_E fill:#e91e63,color:#fff
    style A_K6 fill:#ffcdd2
    style B_C fill:#ff9800,color:#fff

7.3 Virtual Nodes — Visualization

flowchart TD
    subgraph RING["Hash Ring với Virtual Nodes"]
        direction TB
        V_A1["A-vnode0<br/>0x0A"] ~~~ V_B1["B-vnode0<br/>0x15"]
        V_B1 ~~~ V_C1["C-vnode0<br/>0x28"]
        V_C1 ~~~ V_A2["A-vnode1<br/>0x3F"]
        V_A2 ~~~ V_C2["C-vnode1<br/>0x55"]
        V_C2 ~~~ V_B2["B-vnode1<br/>0x6A"]
        V_B2 ~~~ V_A3["A-vnode2<br/>0x82"]
        V_A3 ~~~ V_B3["B-vnode2<br/>0x99"]
        V_B3 ~~~ V_C3["C-vnode2<br/>0xB0"]
    end

    subgraph MAPPING["Physical Node Mapping"]
        SA["Physical Server A<br/>3 vnodes → ~33% keys"]
        SB["Physical Server B<br/>3 vnodes → ~33% keys"]
        SC["Physical Server C<br/>3 vnodes → ~33% keys"]
    end

    V_A1 & V_A2 & V_A3 --> SA
    V_B1 & V_B2 & V_B3 --> SB
    V_C1 & V_C2 & V_C3 --> SC

    style V_A1 fill:#4caf50,color:#fff
    style V_A2 fill:#4caf50,color:#fff
    style V_A3 fill:#4caf50,color:#fff
    style V_B1 fill:#2196f3,color:#fff
    style V_B2 fill:#2196f3,color:#fff
    style V_B3 fill:#2196f3,color:#fff
    style V_C1 fill:#ff9800,color:#fff
    style V_C2 fill:#ff9800,color:#fff
    style V_C3 fill:#ff9800,color:#fff
    style SA fill:#4caf50,color:#fff
    style SB fill:#2196f3,color:#fff
    style SC fill:#ff9800,color:#fff

7.4 Data Migration Flow

sequenceDiagram
    participant Coord as Coordinator
    participant New as New Node (E)
    participant Old as Affected Node (C)
    participant Client as Client

    Note over Coord: Node E joins cluster

    Coord->>Coord: Tính key range cho Node E<br/>(dựa trên vị trí trên ring)
    Coord->>Old: Request: stream data<br/>trong key range [x, y]
    Old->>New: Stream data chunks<br/>(background, throttled)

    Note over Client: Trong thời gian migration

    Client->>Coord: GET key "user:500"
    Coord->>Coord: Hash ring lookup → Node E
    alt Data đã migrate xong
        Coord->>New: Forward request
        New-->>Client: Response (từ Node E)
    else Data chưa migrate
        Coord->>Old: Forward request (fallback)
        Old-->>Client: Response (từ Node C)
    end

    Old-->>New: Migration complete
    New->>Coord: Confirm: ready to serve full range
    Coord->>Coord: Update ring: Node E fully active
    Coord->>Old: Cleanup: delete migrated data<br/>(after grace period)

8. Aha Moments & Pitfalls

Aha Moments

#1: Consistent hashing giảm data movement từ O(N) xuống O(1/N) khi cluster thay đổi. Với 100 nodes, đó là giảm từ 99% xuống 1%. Sự khác biệt giữa “hệ thống sập 4 ngày” và “không ai biết gì”.

#2: Virtual nodes là magic ingredient biến consistent hashing từ lý thuyết thành thực tế. Không có vnodes, consistent hashing vẫn bị skewed distribution.

#3: Hash ring lookup chỉ mất O(log N) — cỡ 150ns cho 20,000 vnodes. Nhanh hơn 3,000 lần so với một network call. Ring lookup không bao giờ là bottleneck.

#4: Consistent hashing không chỉ là thuật toán — nó là architecture pattern. Xuất hiện ở Cassandra (data partitioning), Nginx (load balancing), Memcached (cache distribution), DynamoDB (partition routing), Akamai CDN (content routing).

#5: Khi dùng consistent hashing cho replication, đi tiếp clockwise để tìm N distinct physical nodes — không phải N vnodes tiếp theo (vì nhiều vnodes có thể thuộc cùng physical node).

Pitfalls — Sai lầm thường gặp

Pitfall 1: Quá ít Virtual Nodes → Phân bố lệch

Sai: Dùng 1-5 vnodes/node → node A nhận 60% key, node B nhận 5%. Đúng: Dùng 100-200 vnodes/node cho production. Cassandra default là 256. Trade-off: nhiều vnodes = nhiều memory hơn cho ring metadata (nhưng chỉ vài MB, không đáng kể).

Pitfall 2: Chọn sai Hash Function

Sai: Dùng String.hashCode() trong Java (chỉ 32-bit, phân bố kém, dễ predict). Đúng: Dùng MurmurHash3 (nhanh, phân bố tốt) cho internal system, SipHash cho system có untrusted input. Tuyệt đối không dùng hash function yếu (CRC32, DJB2) cho consistent hashing.

Pitfall 3: Nghĩ Consistent Hashing luôn cần thiết

Sai: Mọi hệ thống phân tán đều cần consistent hashing. Đúng: Chỉ cần khi thêm/bớt node thường xuyên và data movement là vấn đề. Nếu cluster cố định (ít thay đổi), simple modulo hashing đơn giản hơn và cũng hoạt động tốt. Ví dụ: database sharding strategy thường dùng range-based hoặc directory-based khi shard ít thay đổi.

Pitfall 4: Quên handle data migration

Sai: Thêm node mới vào ring xong bỏ đó → key mới đi đúng node mới nhưng key cũ vẫn nằm ở node cũ → data inconsistency, cache miss. Đúng: Phải có migration process stream data từ node cũ sang node mới. Cassandra làm điều này tự động (nodetool decommission/bootstrap).

Pitfall 5: Không monitor key distribution

Sai: Setup consistent hashing rồi quên. Sau 6 tháng phát hiện 1 node chịu 40% traffic vì hot key. Đúng: Monitor key distribution và request rate per node liên tục. Dùng Prometheus + Grafana như section 5. Set alert khi deviation > 30%.

Pitfall 6: Hash function khác nhau giữa client và server

Sai: Client dùng MurmurHash3, server dùng MD5 → key hash ra vị trí khác nhau → request đi sai node. Đúng: Tất cả participant trong hệ thống phải dùng cùng hash function và cùng ring configuration. Đây là lý do Memcached implement consistent hashing ở client side (libmemcached/ketama).

9. Internal Links — Liên kết kiến thức

Consistent Hashing trong các tuần khác

Tuần	Chủ đề	Liên hệ với Consistent Hashing
Tuan-05-Load-Balancer	Load Balancer	Consistent hashing là một thuật toán LB (session affinity, cache-friendly routing)
Tuan-06-Cache-Strategy	Cache Strategy	Consistent hashing phân phối cache key → giảm cache stampede khi node thay đổi
Tuan-07-Database-Sharding-Replication	DB Sharding & Replication	Consistent hashing dùng cho hash-based sharding + replica placement
Tuan-08-Message-Queue	Message Queue	Kafka partition assignment dùng consistent hashing-like mechanism
Tuan-09-Rate-Limiter	Rate Limiter	Distributed rate limiter cần consistent hashing để route counter tới đúng node
Tuan-11-Key-Value-Store	Key-Value Store	DynamoDB, Cassandra dùng consistent hashing làm nền tảng partitioning
Tuan-13-Monitoring-Observability	Monitoring	Monitor key distribution, detect hotspot, track migration
Tuan-15-Data-Security-Encryption	Security	SipHash, hash collision protection, ring metadata encryption

Tham khảo

Alex Xu, System Design Interview — Chapter 5: Design Consistent Hashing
Karger et al., Consistent Hashing and Random Trees (1997) — paper gốc
Lamping & Veach, A Fast, Minimal Memory, Consistent Hash Algorithm (Google, 2014) — Jump Consistent Hash
sdi.anhvy.dev — Vietnamese System Design Reference
Tuan-09-Rate-Limiter — Tuần trước
Tuan-11-Key-Value-Store — Tuần sau: ứng dụng consistent hashing vào Key-Value Store

Tuần sau: Tuan-11-Key-Value-Store — Thiết kế Key-Value Store dùng consistent hashing làm nền tảng phân phối data

lthieu's notes

Explorer

Tuan-10-Consistent-Hashing