Consistent Hashing — Thuật toán phân phối tải đồng đều

Hồi mới đi làm, mình có một câu hỏi: mấy cái distributed cache như Redis Cluster, sao biết key nào nằm ở node nào? Câu trả lời đơn giản là hash — nhưng hash kiểu gì để thêm server mới không làm mất hết cache cũ? Đó là lúc mình gặp Consistent Hashing.

Ảnh: Markus Spiske — Pexels

Vấn đề với Hash Modulo truyền thống

Giả sử bạn có 4 cache server, cách đơn giản nhất là:

node = hash(key) % 4

Mỗi key rơi vào đúng 1 server — ngon. Nhưng tới lúc scale lên 5 server:

• Công thức thành hash(key) % 5
• Hầu hết key sẽ rơi vào server khác
• Toàn bộ cache bị miss → database die

Đây gọi là rehash storm. Với production hệ thống lớn, hậu quả rất nặng — database chết, request timeout, khách hàng bức xúc.

Consistent Hashing giải quyết ra sao?

Ý tưởng đơn giản thôi:

1. Tạo một vòng tròn ảo (hash ring) từ 0 đến 2³²-1
2. Hash từng server vào vòng tròn đó
3. Với mỗi key, hash key rồi đi theo chiều kim đồng hồ, tới server đầu tiên gặp là chỗ lưu

Khi thêm server mới, chỉ cần re-map keys ở đoạn giữa server mới và server kế tiếp — phần còn lại không bị ảnh hưởng.

Nhìn code sẽ rõ hơn:

package main

import (
	"crypto/sha256"
	"encoding/binary"
	"fmt"
	"sort"
)

type ConsistentHash struct {
	ring     []uint32
	nodes      map[uint32]string
	replicas   int
}

func New(replicas int) *ConsistentHash {
	return &ConsistentHash{
		ring:     []uint32{},
		nodes:    make(map[uint32]string),
		replicas: replicas,
	}
}

func (ch *ConsistentHash) hash(key string) uint32 {
	h := sha256.Sum256([]byte(key))
	return binary.BigEndian.Uint32(h[:4])
}

func (ch *ConsistentHash) Add(node string) {
	for i := 0; i < ch.replicas; i++ {
		vnode := fmt.Sprintf("%s:%d", node, i)
		h := ch.hash(vnode)
		ch.ring = append(ch.ring, h)
		ch.nodes[h] = node
	}
	sort.Slice(ch.ring, func(i, j int) bool {
		return ch.ring[i] < ch.ring[j]
	})
}

func (ch *ConsistentHash) Get(key string) string {
	if len(ch.ring) == 0 {
		return ""
	}
	h := ch.hash(key)
	idx := sort.Search(len(ch.ring), func(i int) bool {
		return ch.ring[i] >= h
	})
	if idx == len(ch.ring) {
		idx = 0
	}
	return ch.nodes[ch.ring[idx]]
}

Một cải tiến quan trọng trong code trên là virtual nodes (replicas). Mỗi physical node có nhiều điểm trên vòng tròn, giúp phân phối đều hơn — không có server nào chịu tải quá lớn. Trong production, con số này thường từ 100-200.

Ảnh: Brett Sayles — Pexels

Ứng dụng thực tế

Bạn sẽ thấy Consistent Hashing ở khắp nơi trong hạ tầng backend:

• Redis Cluster — dùng hash slot (biến thể của consistent hashing) phân phối keys qua 16384 slots
• Cassandra & DynamoDB — dùng consistent hashing với partitioning
• HTTP load balancers — một số LB dùng consistent hashing để giữ session persistence
• CDN — cache phân tán trên edge nodes

Cái hay là: dù hash function có thay đổi, chỉ một phần nhỏ dữ liệu bị di chuyển. Đó là lý do các hệ thống distributed scale ngang mà không đau đầu.

Hạn chế

Dù vậy, consistent hashing không phải silver bullet:

• Load imbalance — nếu virtual nodes không đủ nhiều, một server có thể nhận nhiều traffic hơn
• Không xử lý được replication — nếu muốn mỗi key có replica, cần kết hợp thêm technique khác
• Khi thêm/bớt server, vẫn có một lượng nhỏ keys bị miss — cần kết hợp cache warming

Khi nào nên dùng? Khi bạn có số lượng node thay đổi thường xuyên, hoặc cần zero-downtime scaling. Nếu hệ thống nhỏ (< 5 nodes) và ít thay đổi, hash % N đơn giản vẫn ổn.

📋 Phụ lục thuật ngữ

• Consistent Hashing — thuật toán phân phối keys trên vòng tròn hash, chỉ di chuyển keys giữa 2 node liền kề khi thêm/xoá node
• Virtual Node — mỗi physical node được đại diện bởi nhiều điểm ảo trên vòng tròn, giúp phân phối đều hơn
• Rehash Storm — hiện tượng tất cả keys bị di chuyển khi thay đổi số node, gây áp lực lớn lên hệ thống
• Hash Ring — vòng tròn ảo với 2³²-1 điểm, nơi cả node và key đều được hash vào