System Design — Bài 14: Cấu trúc dữ liệu và concurrency qua bài toán một triệu heartbeat

Một triệu thiết bị gửi heartbeat mỗi 3 giây tạo khoảng 333.333 cập nhật mỗi giây nếu phân bố đều. Nhưng tải lớn chỉ là một nửa bài toán: timeout cũ không được đánh dấu offline một thiết bị vừa gửi heartbeat mới. Ta cần chọn cả cấu trúc dữ liệu lẫn cách kiểm soát đồng thời.

Khóa học System Design: mục lục 21 bài — bạn đang đọc bài 14.

Phân tích một cấu trúc dữ liệu thế nào

Hãy liệt kê thao tác thật: tìm một phần tử, quét khoảng, thêm, sửa và xóa. Không thể nói một cấu trúc “nhanh” nếu nó tối ưu thao tác ta hiếm dùng nhưng chậm ở thao tác chiếm phần lớn tải.

Time complexity cho xu hướng khi dữ liệu tăng. Space complexity, locality và số lượt I/O giúp hiểu chi phí thực tế. Hai giải pháp cùng O(N) có thể rất khác nếu một giải pháp đọc bộ nhớ liên tiếp còn giải pháp kia đi qua nhiều con trỏ rải rác.

Sau đó xét concurrency: có cần lock chung không, có phân vùng được không, và iterator nhìn thấy gì khi dữ liệu thay đổi? Cũng cần biết giới hạn như sai số, kích thước hoặc hành vi khi đầy. Chọn cấu trúc là chọn toàn bộ tập đánh đổi này.

Cheat sheet — cấu trúc nào cho bài toán nào

Consistent hashing hỗ trợ ánh xạ phân tán; geohash giúp chia vùng không gian; token bucket điều tiết tốc độ; trie phù hợp tìm theo tiền tố. Inverted index nối token với tài liệu chứa nó, khác với một index thông thường chỉ tìm theo khóa đã biết.

HyperLogLog ước lượng số phần tử khác nhau. Count-min sketch ước lượng tần suất với giới hạn sai số theo giả định của thuật toán. Bloom filter sàng lọc tồn tại. Những cấu trúc gần đúng dùng ít tài nguyên hơn nhưng phải kiểm tra nghiệp vụ có chấp nhận sai số không.

Merkle tree giúp tìm vùng dữ liệu khác nhau qua hash. Timing wheel tổ chức timer theo thời điểm gần đúng. Raft là giao thức đồng thuận, không đơn thuần là một cấu trúc dữ liệu; danh sách này là bản đồ cơ chế để biết hướng tìm khi gặp vấn đề.

Case Liveness System — sợi chỉ đỏ của khóa

Một triệu thiết bị gửi heartbeat mỗi ba giây tạo khoảng 333.000 lượt cập nhật mỗi giây trung bình, nếu phân bố đều. Nếu cùng khởi động và gửi một nhịp, burst có thể lớn hơn, nên cần xem phân bố thực tế.

Với sorted set, member là thiết bị và score là thời điểm hết hạn. Heartbeat cập nhật score; worker lấy các timer đã tới hạn. Khi xử lý timeout phải kiểm tra heartbeat mới có thay đổi hạn hay không để tránh cảnh báo từ dữ liệu cũ. Cũng phải shard các tập nếu một tập trở thành điểm nóng.

Timing wheel đưa timer vào các bucket theo vòng thời gian. Add hoặc cancel có thể rất rẻ với cấu trúc phù hợp, nhưng bucket có k timer vẫn cần xử lý tương ứng k công việc. Cần giới hạn độ trễ chấp nhận, phân chia worker và khôi phục trạng thái sau restart.

Race condition, lock và deadlock

Race condition thường bắt đầu từ “đọc, kiểm tra, rồi ghi” trong khi người khác có thể chen vào. Hai request cùng thấy còn một sản phẩm rồi đều mua là ví dụ. Cần gộp điều kiện với cập nhật nguyên tử hoặc dùng concurrency control phù hợp.

Pessimistic lock giữ quyền trước khi sửa. Optimistic lock kiểm tra version lúc ghi và yêu cầu retry khi xung đột. Nếu xung đột quá nhiều, retry có thể tốn hơn chờ có kiểm soát. Deadlock giữa chuyển A sang B và B sang A có thể giảm bằng thứ tự khóa thống nhất.

Với distributed lock có TTL, owner cũ có thể tạm dừng rồi tỉnh lại sau khi lease đã hết. Token ngẫu nhiên giúp không xóa nhầm khóa của người khác; fencing token tăng dần cần được tài nguyên đích kiểm tra để từ chối thao tác cũ. Hai loại token giải hai vấn đề khác nhau.

Queue và LMAX Disruptor

Queue dùng chung có thể tạo tranh chấp ở vị trí ghi và đọc, cấp phát object hoặc làm dữ liệu thiếu locality. Không có nghĩa mọi queue đều chậm; cần đo đúng mức tải và mô hình producer–consumer.

Disruptor dùng ring buffer cấp phát trước, sequence và cơ chế đồng bộ để producer, consumer phối hợp. Tái sử dụng ô giúp giảm một phần cấp phát; payload và logic người dùng vẫn có thể tạo rác. Khi vòng quay lại, producer phải tôn trọng tiến độ consumer để không ghi đè dữ liệu chưa được đọc.

Wait strategy ảnh hưởng cả latency lẫn CPU. Busy spin có thể đổi nhiều CPU lấy độ trễ thấp hơn trong điều kiện phù hợp. Không dùng một hệ số “nhanh hơn” cố định: benchmark phải cùng payload, số thread, phần cứng và mục tiêu p99. Đây là tối ưu có điều kiện, không phải lựa chọn mặc định cho mọi queue.

Timeout phải xác nhận lại deadline hoặc version

Heartbeat(device):
  cập nhật deadline mới và tăng version nguyên tử
  lên lịch timeout(device, deadline, version)

Timeout(device, deadline, version):
  đọc trạng thái hiện tại
  nếu version khác hoặc deadline chưa tới: bỏ timer cũ
  ngược lại: chuyển online -> offline bằng CAS
  chỉ phát cảnh báo nếu CAS thành công

Sorted Set: score = deadline; member = device_id
Timing Wheel: bucket thời gian + handle hủy/thay timer

Đây là pseudocode để diễn đạt race. CAS là compare-and-set, cập nhật chỉ khi version/trạng thái còn khớp. Bản production còn cần clock policy, chống cảnh báo trùng và phục hồi sau restart. Bucket có k timer vẫn tốn O(k) để xử lý hết.

Thuật ngữ cần nhớ

• TTL — Time To Live: Thời gian sống còn hiệu lực của dữ liệu, bản ghi tên miền hoặc lease. Hết hạn không tự thực hiện nghiệp vụ như hoàn tồn kho; cần luồng xử lý tương ứng.

• CAS — Compare-And-Swap: So sánh và đổi nguyên tử: chỉ thay giá trị nếu giá trị hiện tại khớp kỳ vọng; dùng trong thuật toán đồng thời, có thể phải retry khi tranh chấp.

• I/O — Input/Output: Vào/ra: trao đổi dữ liệu với đĩa, mạng hoặc thiết bị; I/O-bound là tải dành nhiều thời gian chờ các thao tác này.

Bài tập tự thực hành

Timeout cũ tới sau heartbeat mới.

Gợi ý kiểm tra lời giải

Kiểm tra deadline/version hoặc cập nhật có điều kiện; không phát offline chỉ vì lấy được timer cũ.

Tự kiểm tra sau bài học

• Đo memory locality và I/O bên cạnh Big-O.

• Timer cũ không được thắng heartbeat mới.

• Phân biệt token sở hữu khóa với fencing token được tài nguyên đích kiểm tra.

Đọc thêm từ tài liệu gốc

Redis: Distributed Locks

Tiếp tục lộ trình

Bài trước — Microservices hay Modular Monolith? Chọn ranh giới và tính chi phí

Bài tiếp — Framework phỏng vấn System Design trong 40 phút

Xem toàn bộ khóa học System Design 21 bài