Cấu trúc dữ liệu và Giải thuật Bài 94: System Design Thực chiến - Kiến trúc hệ thống Flash Sale chống sập.

Xin chúc mừng bạn đã đi đến cột mốc Bài 94. Trong 93 bài học vừa qua, chúng ta đã mổ xẻ mọi cấu trúc dữ liệu từ cơ bản đến siêu việt, từ RAM cho đến Ổ cứng, từ thuật toán đơn luồng đến hệ thống phân tán.

Bây giờ là lúc lắp ghép tất cả những mảnh vỡ đó lại. Trận chiến thực sự của một Backend Engineer không nằm ở việc đảo ngược một chuỗi hay duyệt một cái cây trên LeetCode, mà là đối mặt với C10K/C1M Problem (Hàng triệu kết nối đồng thời).

Hãy thử tưởng tượng một chiến dịch Flash Sale tại Hasaki: 10,000 chai serum giảm giá sốc lúc 0h00. Ngay khoảnh khắc kim đồng hồ điểm 12 giờ, hàng triệu request từ khắp cả nước sẽ ập thẳng vào server. Nếu thiết kế theo mô hình truyền thống (Request -> PHP/Laravel -> Query MySQL -> Trả kết quả), hệ thống của bạn sẽ sập trong đúng 1 giây đầu tiên do cạn kiệt Connection Pool và tràn RAM.

Để hệ thống đứng vững, chúng ta sẽ thiết kế một kiến trúc High-Concurrency bằng Golang, áp dụng trực tiếp 6 cấu trúc dữ liệu đã học.

1. Mổ xẻ Kiến trúc Flash Sale qua lăng kính Cấu trúc dữ liệu

Bí quyết tối thượng của Flash Sale là: Tuyệt đối không cho phép Request chạm vào Database (MySQL) ngay lập tức. Mọi thứ phải được xử lý trên RAM và Message Queue.

Tầng 1: API Gateway & Định tuyến (Radix Tree)

Hàng triệu request POST /api/v1/flashsale/buy đổ về. Golang API Gateway (sử dụng Gin hoặc Echo) sẽ dùng Radix Tree (Bài 84) để phân giải URL siêu tốc trong thời gian $O(K)$ . Không có bất kỳ độ trễ CPU nào bị lãng phí cho việc parse chuỗi regex.

Tầng 2: WAF & Rate Limiting (Count-Min Sketch + Consistent Hashing)

Trong hàng triệu request, có rất nhiều bot hoặc các script "săn sale" cố tình gửi 1000 request/giây từ một IP.

Bộ cân bằng tải sử dụng Consistent Hashing (Bài 92) để băm IP của người dùng và điều hướng các request từ cùng một người về cùng một Node xử lý, tối ưu hóa tỷ lệ Cache Hit.
Tại Node đó, ta duy trì một mảng Count-Min Sketch (Bài 82) trên RAM để đếm tần suất request của từng IP. Nếu hàm Estimate(IP) > 5 req/s, hệ thống lập tức ném ra lỗi 429 Too Many Requests và chặt đứt luồng đi tiếp chỉ tốn $1\text{MB}$ RAM thay vì phải lưu hash map hàng triệu IP.

Tầng 3: Chống Cache Penetration (Bloom Filter)

Hacker có thể cố tình gửi request mua các mã sản phẩm (ProductID) không hề tồn tại để ép hệ thống đâm thủng Cache và query thẳng xuống DB.

Hệ thống tải toàn bộ ProductID hợp lệ vào một Bloom Filter (Bài 80).
Nếu BloomFilter.Query(ProductID) == false, request bị block ngay lập tức với chi phí thuật toán $O(1)$ .

Tầng 4: Trái tim Xử lý Hàng tồn kho (In-memory Cache / Skip List)

Không thể dùng MySQL với InnoDB (B+ Tree) để trừ tồn kho lúc này vì các lệnh UPDATE đồng thời sẽ tạo ra Row Lock (Khóa dòng), gây hiện tượng nghẽn cổ chai (Deadlock).

Tồn kho phải được đẩy lên Redis trước giờ G.
Redis sử dụng kiến trúc đơn luồng (Single-threaded Event Loop) đảm bảo mọi lệnh đều tuần tự.
Nếu bạn cần một bảng xếp hạng (Leaderboard) xem ai là 100 người mua nhanh nhất để trao quà đặc biệt, Redis ZSET với cấu trúc Skip List (Bài 83) sẽ chèn và duy trì thứ hạng người dùng trong $O(\log N)$ cực kỳ mượt mà.

Tầng 5: Hàng đợi Bất đồng bộ (Message Queue / LSM-Tree concept)

Khi trừ tồn kho trên Redis thành công, ta không gọi MySQL ngay.

Golang API sẽ ném thông tin đơn hàng vào Kafka hoặc RabbitMQ.
Kafka lưu trữ tin nhắn bằng cách Append-only (Ghi nối tiếp) ra ổ đĩa giống hệt cơ chế WAL của LSM-Tree (Bài 79), giúp tốc độ ghi đạt mức hàng triệu tin nhắn/giây mà không bị Random I/O cản bước.
Lúc này, server lập tức trả về 200 OK: Đơn hàng đang được xử lý cho người dùng. Request kết thúc sớm, giải phóng Goroutines (Bài 93) để đón khách mới.

Tầng 6: Persist xuống Database (B+ Tree)

Một nhóm các Background Workers (Goroutines) chạy ngầm, từ từ kéo (Pull) các tin nhắn từ Kafka xuống và thực hiện lệnh INSERT INTO orders vào MySQL. Lúc này, MySQL được ghi với tốc độ ổn định, không bao giờ bị quá tải, và dữ liệu được lưu vĩnh viễn trên cấu trúc B+ Tree (Bài 78).

2. Giải quyết bài toán Overselling (Bán lố) bằng Lua Script & Golang

Điểm chết nguy hiểm nhất của Flash Sale là Overselling (Kho có 100 cái nhưng bán thành 105 cái do Race Condition). Nếu bạn gọi GET inventory ra Go app, kiểm tra > 0 rồi mới gọi DECR inventory, hai Goroutines chạy song song có thể cùng đọc được tồn kho là 1 và cùng trừ, dẫn đến tồn kho bị âm (-1).

Giải pháp hoàn hảo là gói gọn logic kiểm tra và trừ tồn kho vào một khối Lua Script chạy nguyên tử (Atomic) trên Redis.

package main

import (
	"context"
	"fmt"
	"github.com/go-redis/redis/v8"
	"sync"
	"time"
)

var ctx = context.Background()

// Lua script: Kiểm tra tồn kho, nếu còn thì trừ 1, nếu hết thì trả về 0.
// Redis đảm bảo script này chạy Atomic (không bị ngắt quãng bởi request khác).
const decrementScript = `
local inventory = tonumber(redis.call("GET", KEYS[1]))
if inventory and inventory > 0 then
    redis.call("DECR", KEYS[1])
    return 1
end
return 0
`

func flashSaleHandler(rdb *redis.Client, productID string, userID int, wg *sync.WaitGroup) {
	defer wg.Done()

	// Chạy Lua script trên Redis
	result, err := rdb.Eval(ctx, decrementScript, []string{productID}).Result()
	if err != nil {
		fmt.Printf("[User %d] Lỗi hệ thống: %v\n", userID, err)
		return
	}

	if result.(int64) == 1 {
		fmt.Printf("[User %d] Đặt hàng THÀNH CÔNG! Bắn event vào Kafka...\n", userID)
		// Thực tế: Bắn message chứa thông tin {UserID, ProductID} vào Kafka ở đây
	} else {
		fmt.Printf("[User %d] Thất bại: Đã hết hàng!\n", userID)
	}
}

func main() {
	rdb := redis.NewClient(&redis.Options{
		Addr: "localhost:6379",
	})

	productKey := "flashsale:product_101:inventory"

	// Pre-warm: Set tồn kho bằng 10 trước giờ G
	rdb.Set(ctx, productKey, 10, 0)
	fmt.Println("Đã thiết lập tồn kho: 10 sản phẩm. Bắt đầu Flash Sale!")

	var wg sync.WaitGroup
	start := time.Now()

	// Mô phỏng luồng request khổng lồ: 100 người dùng giành giật 10 sản phẩm cùng lúc
	// Sử dụng Goroutines để tạo Concurrency cao
	for i := 1; i <= 100; i++ {
		wg.Add(1)
		go flashSaleHandler(rdb, productKey, i, &wg)
	}

	wg.Wait()
	
	// Kiểm tra lại tồn kho cuối cùng
	finalInventory, _ := rdb.Get(ctx, productKey).Result()
	fmt.Printf("Thời gian chạy: %v\n", time.Since(start))
	fmt.Printf("Tồn kho còn lại: %s (Đảm bảo không bao giờ bị âm)\n", finalInventory)
}

3. Tổng kết Kiến trúc

Kiến trúc System Design trên cho thấy sự hòa quyện tuyệt đẹp của khoa học máy tính:

Dữ liệu tĩnh (Static Data): Ở tầng cao nhất (CDN, Gateway) được chặn lại bằng xác suất (Bloom Filter, Count-Min).
Dữ liệu nóng (Hot Data - Inventory): Xử lý tuyến tính trong RAM (Redis Lua).
Dòng chảy dữ liệu (Data Stream): Chuyển đổi trạng thái từ Đồng bộ (Sync) sang Bất đồng bộ (Async) thông qua Kafka.
Dữ liệu bền vững (Cold Data - Orders): Ghi chốt hạ vào ổ đĩa (MySQL B+ Tree) với tốc độ được kiểm soát.

Tất cả các thuật toán, từ những vòng lặp mảng đơn giản ở Bài 1, cho đến các khái niệm Hàng đợi, Cây tìm kiếm, Đồ thị, Xác suất, và Hệ thống phân tán, không phải là những mảnh rời rạc. Chúng là những bánh răng của một cỗ máy công nghiệp khổng lồ.

cấu trúc dữ liệu