Load Balancing: Từ Round Robin đến Consistent Hashing | Blog

Khi một server chịu không nổi, cách giải quyết quen thuộc nhất là scale ngang — thêm vài con server nữa. Nhưng việc phân phối request cho đám server đó chia đều hay không lại là chuyện khác. Đó chính là lúc load balancer lên tiếng.

Trong bài này, mình sẽ đi từ thuật toán đơn giản nhất tới Consistent Hashing — loại "hot" nhất hay gặp trong phỏng vấn system design — kèm kinh nghiệm thực chiến của mình.

Round Robin — đơn giản nhưng phải hiểu giới hạn

Thuật toán Round Robin cũng giống như chia bài: request đầu tới server 1, request thứ hai tới server 2, rồi quay vòng lại. Cài đặt rất dễ, trên Nginx chỉ cần vài dòng:

upstream api_servers {
    server 10.0.0.1 weight=3;
    server 10.0.0.2 weight=1;
}

server {
    location /api {
        proxy_pass http://api_servers;
    }
}

Round Robin hoạt động tốt khi các request có độ nặng tương đương nhau và server cùng cấu hình. Nhưng đời thực hiếm được vậy: request /upload nặng gấp chục lần request /ping. Khi đó sẽ có con server nhận toàn bài "nặng" mà mình không kiểm soát được.

Least Connections — để ý tới server đang rảnh

Thay vì đếm lượt, Least Connections đo số kết nối đang active. Server nào đang rảnh nhất thì nhận request tiếp theo. Hiệu quả hơn với workload không đều. Nhược điểm là load balancer phải theo dõi trạng thái kết nối — tốn chút bộ nhớ, nhưng chấp nhận được.

Vấn đề của caching hạ tầng

Cả hai thuật toán trên đều gặp một vấn đề chung khi đi cùng cache: cùng một request (như theo userId) có thể bị đẩy tới server khác nhau mỗi lần. Mỗi server cache riêng thì cache hit rate sụt thảm hại, database phải gánh thêm.

Consistent Hashing — cache hit mới là king

Ý tưởng cốt lõi: đặt toàn bộ server lên một vòng tròn (hash ring), và hash request theo một key ổn định (ví dụ userId). Mỗi key rơi vào điểm nào trên vòng thì thuộc server kế đó. Khi thêm/xoá server, chỉ một phần nhỏ key bị dịch chuyển, còn lại giữ nguyên — điều mà hash đơn giản key % n không làm được.

type HashRing struct {
    ring   map[uint32]string // hash -> node
    sorted []uint32
}

func (h *HashRing) AddNode(node string, vNodes int) {
    for i := 0; i < vNodes; i++ {
        hash := crc32.ChecksumIEEE([]byte(fmt.Sprintf("%s#%d", node, i)))
        h.ring[hash] = node
        h.sorted = append(h.sorted, hash)
    }
    sort.Slice(h.sorted, func(i, j int) bool { return h.sorted[i] < h.sorted[j] })
}

func (h *HashRing) Get(key string) string {
    hash := crc32.ChecksumIEEE([]byte(key))
    idx := sort.Search(len(h.sorted), func(i int) bool { return h.sorted[i] >= hash })
    if idx == len(h.sorted) {
        idx = 0
    }
    return h.ring[h.sorted[idx]]
}

Lưu ý số virtual node (vNodes): vì node thật chỉ nằm vài điểm trên vòng, số ít node sẽ bị ai đó gánh nặng hơn. Thêm virtual node (nhân mỗi node lên vòng nhiều lần) giúp phân phối đều hơn — càng nhiều vNode thì càng đều nhưng tốn thêm bộ nhớ.

Kinh nghiệm thực tế của mình

Đừng tự viết Consistent Hashing nếu không cần. Nginx, Envoy, Redis Cluster đều hỗ trợ sẵn. Tự code lại dễ sai chỗ hash ring và edge case.
Load balancer có thể thành điểm nghẽn duy nhất. Luôn tăng số replica, chạy active-passive.
Theo dõi skew. Mình từng vài con server cấu hình khác nhau, Round Robin vẫn hoạt động nhưng latency chênh lệch rõ. Least Connections + health check giúp đỡ nhiều.
Health check là bắt buộc. Load balancer không nhận request tới server đang chết — nếu không làm, một con "ngất xỉu" vẫn bị chia tài nguyên.

Nếu hệ thống của bạn nhỏ, Round Robin là đủ. Lớn dần và có cache, hãy nghĩ tới Consistent Hashing. Chọn đúng thuật toán đỡ tốn tiền hạ tầng hơn nhiều. Chúc anh chạy được hệ thống mượt!