CHAPTER 5: DESIGN CONSISTENT HASHING — WRAP UP

Mục tiêu bài viết

  • Tổng kết toàn bộ Chapter 5: từ rehashing problem → hash ring → virtual nodes → affected keys.
  • Nắm rõ ba lợi ích chính của consistent hashing trong production.
  • Biết các hệ thống thực tế lớn đang dùng consistent hashing ở đâu và để làm gì.
  • Có checklist để áp dụng consistent hashing đúng lúc, đúng chỗ.

1) Context

Toàn bộ Chapter 5 xây dựng theo trình tự:

Rehashing Problem (hash % N)
        ↓
Hash Ring (hash space → vòng tròn)
        ↓
Hash Servers + Hash Keys lên ring
        ↓
Server Lookup (clockwise)
        ↓
Add / Remove Server (chỉ k/n key remap)
        ↓
Two Issues: uneven partition + non-uniform distribution
        ↓
Virtual Nodes (nhiều điểm/server → cân bằng partition + key)
        ↓
Find Affected Keys (anticlockwise để xác định vùng remap)
        ↓
Wrap Up ← bài này

2) Kiến trúc tổng quan

Tổng quan Consistent Hashing — Full Picture

                   [Hash Ring — SHA-1, 0..2^160-1]

                    s0_1 (virtual)
                 /
    s1_2 ────── s0_0 ────── s1_0
     |      (server 0)        |
     |                        |
    s0_2                    s1_1
     |      (server 1)        |
    s1_2 ────────────────── s0_1

Key Lookup:
  hash(key) → vị trí trên ring
  → đi clockwise → gặp virtual node đầu tiên
  → map về server vật lý

Add server:
  → đi anticlockwise từ server mới → tìm affected range
  → chỉ remap keys trong affected range

Remove server:
  → đi anticlockwise từ server cũ → tìm affected range
  → chỉ remap keys trong affected range → server CW kế tiếp

3) Ba Lợi Ích Chính

Lợi ích 1 — Minimized Key Redistribution

Khi thêm hoặc bớt server, chỉ k/n key trung bình phải remap:

Truyền thống (hash % N):
  Thêm/bớt 1 server → gần như TẤT CẢ key phải tính lại
  → Cache miss storm, DB quá tải đột biến

Consistent Hashing:
  Thêm/bớt 1 server → chỉ keys trong affected range bị remap
  → Tác động cục bộ, hệ thống ổn định

Lợi ích 2 — Horizontal Scaling dễ dàng hơn

Virtual nodes đảm bảo data phân bố đều:

Với 200 virtual nodes/server:
  Standard deviation ≈ 5% of mean
  → Mỗi server nhận xấp xỉ cùng lượng data và traffic
  → Thêm server mới vào cluster không gây mất cân bằng đột ngột

Lợi ích 3 — Mitigate Hotspot Key Problem

Không để một shard chịu toàn bộ traffic của “celebrity data”:

Ví dụ thực tế:
  Data của Katy Perry, Justin Bieber, Lady Gaga
  → Nếu cả 3 hash vào cùng 1 shard → server đó quá tải

Consistent hashing + virtual nodes:
  → Data được phân tán đều trên nhiều shard
  → Không có shard nào bị "celebrity overload"

4) Request/Data flow

Flow tổng quát của một hệ thống cache dùng consistent hashing:

1) Client gọi get(key) / set(key, value)
2) Client-side library tính hash(key) → vị trí trên ring
3) Tìm server bằng cách đi clockwise → gặp virtual node đầu tiên
4) Map virtual node → server vật lý
5) Gửi request đến server đó
6) [Cache hit]  → trả về data ngay
   [Cache miss] → fallback DB → populate cache → trả về data

Khi topology thay đổi (add/remove server):
7) Ring được cập nhật (chèn/xóa virtual nodes)
8) Background job xác định affected range (anticlockwise lookup)
9) Remap chỉ các key trong affected range
10) Các key còn lại hoàn toàn không bị ảnh hưởng

5) API / Data contract

Ví dụ API lấy thông tin tổng quan ring (dùng cho monitoring/ops):

GET /api/v1/consistent-hash/ring/overview

Ví dụ response:

{
  "algorithm": "consistent-hashing",
  "hashFunction": "SHA-1",
  "totalPhysicalServers": 4,
  "virtualNodesPerServer": 200,
  "totalVirtualNodes": 800,
  "estimatedStdDev": "~5% of mean",
  "partitionBalance": "even",
  "servers": [
    {
      "id": "server0",
      "virtualNodes": 200,
      "keyCount": 24850,
      "loadPercent": 24.85
    },
    {
      "id": "server1",
      "virtualNodes": 200,
      "keyCount": 25100,
      "loadPercent": 25.1
    },
    {
      "id": "server2",
      "virtualNodes": 200,
      "keyCount": 24930,
      "loadPercent": 24.93
    },
    {
      "id": "server3",
      "virtualNodes": 200,
      "keyCount": 25120,
      "loadPercent": 25.12
    }
  ],
  "totalKeys": 100000
}

6) Real-World Usage

Consistent hashing được dùng rộng rãi trong các hệ thống production lớn:

Hệ thống Công ty Dùng cho
Amazon Dynamo Amazon Partitioning component — phân tán data trên các node trong Dynamo DB
Apache Cassandra Apache/DataStax Data partitioning across cluster — mỗi node chịu một vùng trên ring
Discord Discord Chat infrastructure — phân tán message data trên nhiều server
Akamai CDN Akamai Content delivery network — routing request đến edge server phù hợp
Maglev Google Network load balancer — consistent mapping connection đến backend

7) Trade-offs

Tiêu chí Consistent Hashing Ghi chú
Key redistribution khi đổi topology Rất thấp (~k/n) Lợi thế chính so với hash % N
Load balancing Tốt với đủ virtual nodes Cần tune số VN phù hợp
Memory overhead Tăng theo số virtual nodes VN × server entries cần lưu
Lookup complexity O(log N×V) Binary search trên sorted ring
Hotspot mitigation Tốt Phụ thuộc vào phân bố hash
Implementation complexity Trung bình Cần sorted map + anticlockwise lookup

8) Tóm tắt + bài học

Consistent hashing giải quyết ba vấn đề cốt lõi của distributed systems:

  1. ✅ Minimized redistribution: thêm/bớt server chỉ ảnh hưởng k/n key.
  2. ✅ Even distribution: virtual nodes phân tán data đều, dễ horizontal scaling.
  3. ✅ Hotspot mitigation: không để một shard chịu toàn bộ traffic của data nóng.

Khi nào dùng consistent hashing:

  • Distributed cache (Redis Cluster, Memcached)
  • Database sharding (Cassandra, Dynamo-style)
  • Load balancing với session affinity
  • CDN routing, network load balancer

Khi nào KHÔNG cần:

  • Hệ thống nhỏ, server pool cố định, ít thay đổi
  • Đơn giản hóa là ưu tiên hàng đầu (hash % N đủ dùng)

Chapter 5 kết thúc tại đây. Chapter 6 sẽ tiếp tục với Design a Key-Value Store — nơi consistent hashing được áp dụng trực tiếp như một building block.