Cấu trúc dữ liệu và Giải thuật Bài 57: Băm nhất quán (Consistent Hashing) - Cân bằng tải và phân phối dữ liệu trong hệ thống phân tán.

Trong các bài học trước, Bảng băm (Hash Table) và hàm băm truyền thống đóng vai trò định vị dữ liệu dựa trên công thức:

Index = Hash(Key) % N (với $N$ là số lượng server hoặc số bucket).

Công thức này hoạt động hoàn hảo trong môi trường đơn máy (Single-node). Tuy nhiên, khi hệ thống backend phát triển thành một cụm Hệ thống phân tán (Distributed System) gồm nhiều cụm Redis, nhiều Shard Database, hay các cụm Cache Server chịu tải cao, phép toán chia lấy dư % N bộc lộ một gót chân Achilles chí mạng: Khi một server bị sập hoặc khi bạn cần scale-up thêm server mới ( $N$ thay đổi), toàn bộ cấu trúc phân phối dữ liệu sẽ bị phá vỡ.

Toàn bộ hàng triệu bản ghi sẽ bị lệch vị trí, dẫn đến hiện tượng Cache Stampede hoặc sập hệ thống Database vì dữ liệu cũ không còn tìm thấy đúng địa chỉ cũ. Để giải quyết bài toán định hướng dữ liệu ổn định trong hệ thống phân tán, các kỹ sư hệ thống sử dụng thuật toán vĩ đại mang tên Băm nhất quán (Consistent Hashing).

1. Thảm họa của Phép toán Modulo truyền thống

Giả sử bạn đang có cụm 3 Server (N = 3). Một Key có Hash(Key) = 10.

Theo công thức: 10 % 3 = 1 $\rightarrow$ Dữ liệu được lưu ở Server 1.

Bây giờ, Server số 3 bị quá tải hoặc hỏng phần cứng, hệ thống cắt giảm còn 2 Server (N = 2).

Bây giờ tính lại: 10 % 2 = 0 $\rightarrow$ Dữ liệu chạy sang Server 0.

Kết quả: Chỉ vì mất đi một server, hầu như toàn bộ dữ liệu trên toàn hệ thống bị sai lệch vị trí. Các request đọc cache sẽ liên tục thất bại (Cache Miss), dội ngược toàn bộ tải xuống Database gốc và làm sập toàn bộ hệ thống. Consistent Hashing ra đời để xóa bỏ sự phụ thuộc hoàn toàn vào biến số $N$ này.

2. Vòng tròn Không gian Băm (The Hash Ring)

Consistent Hashing giải quyết bài toán bằng cách thay đổi không gian định vị từ một mảng tuyến tính thành một Vòng tròn băm khép kín (Hash Ring).

Không gian vòng tròn: Tưởng tượng một hàm băm chuẩn (như MD5 hoặc SHA-1) tạo ra một khoảng giá trị số nguyên khổng lồ từ 0 cho đến $2^{32} - 1$ (hoặc $2^{64} - 1$ ). Các giá trị này được uốn cong thành một vòng tròn liên tục, nơi điểm cuối ( $2^{32} - 1$ ) nối liền trực tiếp với điểm đầu (0).
Định vị Server: Lấy địa chỉ IP hoặc tên của các Server (ví dụ: Server_A, Server_B, Server_C), đem băm chúng qua hàm băm để lấy ra một vị trí độc nhất nằm đâu đó trên vòng tròn khép kín này.
Định vị Dữ liệu (Key): Khi một Key mới đi vào hệ thống (ví dụ: user_session_123), ta cũng đem Key đó đi băm để lấy ra một vị trí trên vòng tròn. Từ vị trí của Key, hệ thống đi theo chiều kim đồng hồ cho đến khi gặp chiếc Server đầu tiên. Server đó chính là chủ nhân chịu trách nhiệm lưu trữ Key này.

3. Bản chất của sự Ổn định khi Scale-up / Scale-down

Khi một Server mới (ví dụ Server_D) được thêm vào vòng tròn:

Nó chỉ chiếm một khoảng không gian nhỏ trên vòng tròn.
Chỉ có các Key nằm ngay phía trước Server_D (tính theo chiều ngược kim đồng hồ) bị dịch chuyển sang Server_D mới.
Toàn bộ phần dữ liệu còn lại trên các Server khác được giữ nguyên vẹn hoàn toàn. Không có chuyện xáo trộn toàn hệ thống như phép toán Modulo % N.
Khi một Server bị sập, dữ liệu của nó chỉ việc chạy sang Server tiếp theo theo chiều kim đồng hồ, hệ thống vẫn duy trì sự ổn định.

4. Giải quyết điểm yếu "Phân bố không đều" bằng Virtual Nodes (vNodes)

Mô hình Consistent Hashing cơ bản gặp phải một rủi ro vật lý: Do hàm băm ngẫu nhiên, các Server có thể bị gom cục lại một góc trên vòng tròn, khiến một Server phải gánh 80% tải của toàn hệ thống trong khi các Server khác rảnh rỗi.

Để giải quyết triệt để vấn đề này, các kiến trúc sư áp dụng kỹ thuật Nút ảo (Virtual Nodes - vNodes):

Thay vì ánh xạ 1 Server thành 1 điểm trên vòng tròn, mỗi Server thực tế sẽ được nhân bản thành hàng trăm "nút ảo" rải rác đều khắp vòng tròn (ví dụ: Server_A#1, Server_A#2, Server_A#3...).
Khi một Key rơi vào vùng của vNode nào, nó sẽ được điều hướng về Server thật tương ứng.
Nhờ có vNodes, dữ liệu được rải đều hoàn toàn cân bằng cho tất cả các Server trong cụm phân tán.

5. Triển khai Consistent Hashing cơ bản bằng Golang

Dưới đây là mô hình cấu trúc Consistent Hashing sử dụng một Slice đã sắp xếp kết hợp tìm kiếm nhị phân (sort.Search) để định vị Server theo chiều kim đồng hồ với tốc độ $O(\log K)$ (với $K$ là số lượng vNodes):

package main

import (
    "fmt"
    "hash/crc32"
    "sort"
    "strconv"
)

type HashRing struct {
    circle   []uint32 // Mảng lưu trữ các hash code của vNodes (đã được sắp xếp)
    nodeMap  map[uint32]string // Ánh xạ từ hash code vNode về tên Server thực tế
    replicas int      // Số lượng vNodes cho mỗi Server thực tế
}

func NewHashRing(replicas int) *HashRing {
    return &HashRing{
        nodeMap:  make(map[uint32]string),
        replicas: replicas,
    }
}

// Hàm băm CRC32 chuẩn
func (hr *HashRing) hash(key string) uint32 {
    return crc32.ChecksumIEEE([]byte(key))
}

// Thêm Server thực tế vào vòng tròn kèm theo vNodes
func (hr *HashRing) AddNode(node string) {
    for i := 0; i < hr.replicas; i++ {
        // Tạo tên định danh cho vNode (ví dụ: "Server_A#0", "Server_A#1"...)
        virtualKey := node + "#" + strconv.Itoa(i)
        hashVal := hr.hash(virtualKey)
        
        hr.circle = append(hr.circle, hashVal)
        hr.nodeMap[hashVal] = node
    }
    // Bắt buộc phải sắp xếp lại mảng circle để phục vụ tìm kiếm nhị phân
    sort.Slice(hr.circle, func(i, j int) bool {
        return hr.circle[i] < hr.circle[j]
    })
}

// Tìm kiếm Server chịu trách nhiệm cho Key theo chiều kim đồng hồ
func (hr *HashRing) GetNode(key string) string {
    if len(hr.circle) == 0 {
        return ""
    }

    hashVal := hr.hash(key)

    // Sử dụng tìm kiếm nhị phân (Binary Search) để tìm vNode >= hashVal đầu tiên theo chiều kim đồng hồ
    idx := sort.Search(len(hr.circle), func(i int) bool {
        return hr.circle[i] >= hashVal
    })

    // Nếu chạy quá vòng tròn, quay vòng lại phần tử đầu tiên (Tính chất vòng tròn khép kín)
    if idx == len(hr.circle) {
        idx = 0
    }

    return hr.nodeMap[hr.circle[idx]]
}

6. Ứng dụng thực tế trong Hạ tầng Distributed Systems

Consistent Hashing là xương sống định hình nên kiến trúc của hầu hết các công nghệ lưu trữ phân tán hiện đại:

Cassandra & Amazon DynamoDB: Sử dụng Consistent Hashing làm nền tảng cốt lõi để phân phối dữ liệu phân mảnh (sharding) trên hàng ngàn node lưu trữ mà không cần một máy chủ điều phối trung tâm (Master Node).
Memcached & Redis Cluster: Các Client thư viện kết nối Redis/Memcached sử dụng thuật toán này ở tầng ứng dụng để tự động phân phối các key cache vào đúng cụm Redis node, đảm bảo khi scale cluster không làm sập tầng cache.
Content Delivery Networks (CDNs): Các hệ thống CDN toàn cầu định tuyến yêu cầu tải tài nguyên tĩnh (hình ảnh, video) của người dùng đến các Edge Server gần nhất thông qua băm nhất quán.

cấu trúc dữ liệu