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

Trong Bài 91, chúng ta đã học cách một cụm máy chủ (Cluster) đạt được sự đồng thuận thông qua thuật toán Raft. Tuy nhiên, Raft chủ yếu giải quyết bài toán Tính khả dụng (High Availability) bằng cách nhân bản (Replicate) cùng một tập dữ liệu ra nhiều máy.

Nhưng điều gì sẽ xảy ra nếu lượng dữ liệu tại Hasaki phình to lên mức hàng Terabytes, vượt qua sức chứa của một ổ cứng đơn lẻ? Hoặc khi hệ thống có hàng chục triệu lượng truy cập đồng thời khiến một máy chủ không thể xử lý nổi? Lúc này, chúng ta buộc phải "chia để trị" — băm nhỏ dữ liệu hoặc chia đều luồng truy cập ra nhiều máy chủ khác nhau. Quá trình này được gọi là Sharding (Phân mảnh dữ liệu) hoặc Load Balancing (Cân bằng tải).

1. Vấn đề của hàm Hash thông thường (Modulo Hashing)

Cách chia dữ liệu ngây thơ nhất mà các kỹ sư backend thường nghĩ tới là sử dụng phép chia lấy dư (Modulo).

Giả sử bạn có 4 máy chủ Cache (Redis) được đánh số $0, 1, 2, 3$. Khi cần lưu một ảnh sản phẩm có key = "product_123", bạn băm cái key đó ra một con số, rồi chia lấy dư cho 4:

$$\text{Server\_Index} = \text{Hash(key)} \pmod 4$$

Bi kịch xảy ra khi hệ thống cần mở rộng:

Đến ngày lễ hội mua sắm, tải tăng đột biến, bạn quyết định mua thêm 1 máy chủ nữa (tổng cộng $N = 5$).

Lúc này, công thức biến thành $\text{Hash(key)} \pmod 5$.

Đột nhiên, tất cả các phép toán Modulo đều trả về một kết quả hoàn toàn khác so với trước đây. Hơn 80% dữ liệu đang nằm trên các Cache Server lập tức bị "trượt" (Cache Miss). Hàng triệu request không tìm thấy dữ liệu trên Cache sẽ ập thẳng vào Database (MySQL), gây ra hiện tượng Cache Avalanche (Bão Cache) và đánh sập toàn bộ hệ thống chỉ trong vài giây.

Để giải quyết bài toán mở rộng (Scale In/Out) mà không làm xáo trộn toàn bộ hệ thống, Consistent Hashing (Băm nhất quán) đã ra đời.

2. Vòng tròn Băm (Hash Ring) - Lời giải thanh lịch

Consistent Hashing không chia lấy dư theo số lượng máy chủ hiện có. Thay vào đó, nó băm mọi thứ (cả Key của dữ liệu và IP/ID của Máy chủ) vào một không gian khổng lồ và cuộn không gian đó lại thành một Vòng tròn (Hash Ring).

Giả sử ta dùng hàm băm SHA-1 (đầu ra 160-bit), không gian giá trị sẽ đi từ $0$ đến $2^{160}-1$. Hai đầu $0$ và $2^{160}-1$ được nối liền với nhau tạo thành một vòng khép kín.

Cơ chế hoạt động:

1. Chèn Máy chủ (Nodes): Băm địa chỉ IP của các máy chủ (VD: Node_A, Node_B) và đặt chúng lên các tọa độ tương ứng trên vòng tròn.

2. Định tuyến Dữ liệu (Routing Keys): Khi có một yêu cầu đọc/ghi dữ liệu (VD: key="product_123"), ta băm Key đó để tìm tọa độ của nó trên vòng tròn.

3. Quy tắc đi tìm Máy chủ: Từ tọa độ của Key, ta đi xuôi theo chiều kim đồng hồ trên vòng tròn. Máy chủ đầu tiên mà ta đụng trúng chính là máy chủ sẽ chịu trách nhiệm lưu trữ Key đó.

Sức mạnh của Consistent Hashing khi hệ thống thay đổi:

• Khi THÊM một Node mới: Giả sử bạn thêm Node_C xen vào giữa Node_A và Node_B. Chỉ có các Key nằm trên cung tròn ngay trước Node_C mới phải chuyển từ Node_B sang Node_C. Tuyệt đối không ảnh hưởng đến dữ liệu của các máy chủ khác.

• Khi XÓA một Node: Nếu Node_A bị cháy ổ cứng, toàn bộ các Key đang trỏ vào Node_A sẽ tự động đi tiếp theo chiều kim đồng hồ và rơi vào Node_B. Các khu vực khác trên vòng tròn vẫn an toàn.

Nhờ cơ chế này, khi số lượng máy chủ là $N$, số lượng Key phải di chuyển khi có thay đổi chỉ là $\frac{1}{N}$, thay vì gần như 100% như phép Modulo ngây thơ.

3. Ảo ảnh (Virtual Nodes) - Giải quyết sự mất cân bằng

Vòng tròn băm có một điểm yếu: Việc băm IP máy chủ là ngẫu nhiên, nên rất dễ xảy ra tình trạng các Node nằm tụm lại một chỗ trên vòng tròn. Kết quả là một máy chủ vô tình kiểm soát một cung tròn quá lớn và gánh toàn bộ tải, trong khi các máy khác thì ngồi không (Data Skew).

Để cân bằng tải đều tăm tắp, chúng ta sử dụng kỹ thuật Virtual Nodes (Node Ảo).

Thay vì băm Node_A đúng 1 lần, ta sẽ băm nó 100 lần với các tên gọi khác nhau (VD: Node_A#1, Node_A#2, ..., Node_A#100) và rải đều 100 điểm đó lên vòng tròn. Dữ liệu rơi vào bất kỳ Node ảo nào của Node_A đều sẽ được chuyển về máy chủ vật lý Node_A. Node ảo càng nhiều, phân phối dữ liệu càng đồng đều.

4. Trực quan hóa Cơ chế Consistent Hashing

Mô phỏng dưới đây cho thấy cách các Keys được phân phối vào các máy chủ dọc theo Hash Ring. Khi một máy chủ bị sập hoặc thêm mới, bạn sẽ thấy giới hạn ảnh hưởng chỉ khoanh vùng ở một cung tròn lân cận.

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

Golang rất mạnh trong việc xử lý các mảng sắp xếp. Dưới đây là cài đặt cốt lõi của Consistent Hashing sử dụng Tìm kiếm nhị phân (Binary Search) trên một mảng vòng (Ring):

Go

package main

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

// Cấu trúc Consistent Hash
type ConsistentHash struct {
	hashRing []uint32           // Mảng đã sắp xếp lưu trữ tọa độ của các Virtual Nodes
	hashMap  map[uint32]string  // Map mapping từ Tọa độ Virtual Node -> Tên Máy chủ vật lý (VD: Node_A)
	replicas int                // Số lượng Node Ảo (Virtual Nodes) cho mỗi máy chủ vật lý
}

func NewConsistentHash(replicas int) *ConsistentHash {
	return &ConsistentHash{
		hashRing: make([]uint32, 0),
		hashMap:  make(map[uint32]string),
		replicas: replicas,
	}
}

// Hàm băm (sử dụng CRC32 để nhanh, trong thực tế có thể dùng MurmurHash)
func hashFunc(data []byte) uint32 {
	return crc32.ChecksumIEEE(data)
}

// Thêm một Máy chủ vật lý vào Vòng tròn
func (c *ConsistentHash) AddNode(node string) {
	for i := 0; i < c.replicas; i++ {
		// Tạo tên cho Node ảo (VD: "Node_A#1")
		virtualNodeName := node + "#" + strconv.Itoa(i)
		hashVal := hashFunc([]byte(virtualNodeName))

		c.hashRing = append(c.hashRing, hashVal)
		c.hashMap[hashVal] = node
	}
	
	// Sắp xếp lại vòng tròn để phục vụ tìm kiếm nhị phân
	sort.Slice(c.hashRing, func(i, j int) bool {
		return c.hashRing[i] < c.hashRing[j]
	})
}

// Xóa một Máy chủ vật lý khỏi Vòng tròn
func (c *ConsistentHash) RemoveNode(node string) {
	for i := 0; i < c.replicas; i++ {
		virtualNodeName := node + "#" + strconv.Itoa(i)
		hashVal := hashFunc([]byte(virtualNodeName))

		// Tìm và xóa khỏi mảng hashRing
		idx := sort.Search(len(c.hashRing), func(i int) bool { return c.hashRing[i] >= hashVal })
		if idx < len(c.hashRing) && c.hashRing[idx] == hashVal {
			c.hashRing = append(c.hashRing[:idx], c.hashRing[idx+1:]...)
		}
		
		// Xóa khỏi hashMap
		delete(c.hashMap, hashVal)
	}
}

// Định tuyến Key tìm Máy chủ đích (Get)
func (c *ConsistentHash) GetNode(key string) string {
	if len(c.hashRing) == 0 {
		return ""
	}

	hashVal := hashFunc([]byte(key))

	// Tìm kiếm nhị phân xem Key này rơi vào sau Node ảo nào
	idx := sort.Search(len(c.hashRing), func(i int) bool {
		return c.hashRing[i] >= hashVal
	})

	// Đặc tính Vòng tròn: Nếu Key lớn hơn tọa độ của Node cuối cùng, nó sẽ đi vòng lại Node số 0
	if idx == len(c.hashRing) {
		idx = 0
	}

	// Trả về tên máy chủ vật lý chứa dữ liệu
	return c.hashMap[c.hashRing[idx]]
}

func main() {
	// Khởi tạo vòng băm với 3 Node ảo cho mỗi máy chủ
	ch := NewConsistentHash(3)

	ch.AddNode("Redis_Server_A")
	ch.AddNode("Redis_Server_B")
	ch.AddNode("Redis_Server_C")

	// Phân luồng dữ liệu
	fmt.Printf("Data 'User_101' -> %s\n", ch.GetNode("User_101"))
	fmt.Printf("Data 'User_102' -> %s\n", ch.GetNode("User_102"))
	fmt.Printf("Data 'User_103' -> %s\n", ch.GetNode("User_103"))

	// Giả lập Server B bị sập
	fmt.Println("\n[Hệ thống] Redis_Server_B bị sập!")
	ch.RemoveNode("Redis_Server_B")

	fmt.Printf("Data 'User_101' -> %s\n", ch.GetNode("User_101"))
	fmt.Printf("Data 'User_102' -> %s\n", ch.GetNode("User_102"))
	fmt.Printf("Data 'User_103' -> %s\n", ch.GetNode("User_103"))
}

6. Phân tích Hiệu năng và Ứng dụng Thực tế

• Thời gian Truy vấn (Routing Query): $O(\log(V \cdot K))$ (với $V$ là số Virtual Nodes trên mỗi máy, $K$ là số máy chủ). Phép toán sử dụng Binary Search trên mảng tuyến tính nên phản hồi trong vài nano-giây.

• Thời gian Cập nhật (Add/Remove Server): $O(V \cdot K \log(V \cdot K))$ do phải sort lại mảng (có thể tối ưu thành $O(V \log(V \cdot K))$ nếu chèn mảng thông minh).

Ứng dụng cốt lõi ở tầng Enterprise:

1. Amazon DynamoDB & Apache Cassandra: Sử dụng Consistent Hashing làm cốt lõi để Sharding dữ liệu ra hàng trăm ngàn máy chủ trên Cloud.

2. API Gateway & Load Balancers (HAProxy, Nginx): Khi Client có yêu cầu duy trì phiên đăng nhập (Sticky Sessions), Nginx sẽ băm IP của Client bằng Consistent Hashing để đảm bảo người dùng đó luôn kết nối đúng vào một Backend Server cố định, kể cả khi hệ thống vừa autoscale thêm máy chủ mới.

3. Distributed Caching (Memcached, Redis Cluster): Ngăn chặn bão Cache khi các Pod Cache bị restart hoặc scale down trong Kubernetes.

Chúng ta đã sở hữu vũ khí để phân phối tải và dữ liệu khổng lồ. Tuy nhiên, trong các bài toán thiết kế backend thực tế, có một câu hỏi mang tính nền tảng luôn chia rẽ giới kỹ sư: Khi nhận hàng ngàn Request cùng lúc, làm sao để CPU không bị khóa chết?