Một câu hỏi system design hay bị xem nhẹ: phát hiện thiết bị “chết” khi nó ngừng gửi heartbeat. Bài này đi từ yêu cầu tới cấu trúc dữ liệu (Redis sorted set, timing wheel), rồi tới bài toán chia việc cho nhiều thread và hàng đợi Disruptor. Đọc xong, bạn biết cách phân tích một cấu trúc dữ liệu theo đúng tải của bài toán, không chỉ theo big-O. Cùng đề nhưng nhìn từ kiến trúc (Kafka theo partition, chống báo động giả khi consumer trễ, cảnh báo không trùng): Case study: hệ thống liveness cho 1 triệu thiết bị IoT.
1. Phân tích một cấu trúc dữ liệu thế nào
Ý chính: hỏi năm câu: dùng cho việc gì, đọc một phần tử và đọc một khoảng tốn bao nhiêu, ghi tốn bao nhiêu, chiếm bao nhiêu bộ nhớ và nằm liền hay rải rác, giới hạn là gì.
| Câu hỏi | Ví dụ với ZSET của Redis |
|---|---|
| Use case | xếp hạng, timer, hàng đợi theo thời gian |
| Đọc một (random read) | ZSCORE O(1) |
| Đọc khoảng (range read) | ZRANGE ... BYSCORE O(log n + m) |
| Ghi (insert/update/remove) | ZADD/ZREM O(log n) |
| Bộ nhớ | skiplist + hash, rải rác trong heap, vài chục byte mỗi phần tử |
| Giới hạn | một key nằm trên một node, không chia được qua cluster |
Không cần thuộc mọi cấu trúc. Giữ một bảng tra cứu (cheat sheet), khi cần thì học sâu đúng cái đó. Khi đã hiểu cách cài đặt, tự suy ra giới hạn của nó.
Big-O chỉ là một chiều. Một thao tác O(1) qua mạng (≈0,5 ms) chậm hơn O(log n) trong RAM (≈100 ns) hàng nghìn lần. Mảng liền nhau thân thiện CPU cache hơn linked list rải rác, dù cùng O(n).
Bảng tra cứu: cấu trúc dữ liệu hay gặp trong system design
| Cấu trúc | Dùng cho | Giới hạn cần nhớ |
|---|---|---|
| Consistent hashing | chia key cho các node, thêm/bớt node chỉ dời ~1/n key | cần virtual node để chia đều |
| Geohash | tìm địa điểm gần đây (prefix chung = gần nhau) | điểm sát biên ô có thể khác prefix, phải xét 8 ô kề |
| Token bucket / leaky bucket | rate limit | token bucket cho phép burst, leaky bucket làm phẳng tốc độ |
| Bloom filter | trả lời “chắc chắn không có” để tránh tra cứu đắt | có false positive, không xoá được (bản thường) |
| Trie | gợi ý tự động (autocomplete) | tốn bộ nhớ, thường lưu sẵn top-k ở mỗi node |
| Rsync (rolling checksum) | đồng bộ file, chỉ gửi phần khác | checksum yếu phải xác nhận bằng checksum mạnh |
| Raft | đồng thuận phân tán (etcd, KRaft) | cần đa số node sống |
| Merkle tree | tìm chỗ lệch giữa các replica | phải dựng lại cây khi dữ liệu đổi nhiều |
| HyperLogLog | đếm phần tử duy nhất xấp xỉ, 12 KB | sai số ~0,81% |
| Inverted index | tìm kiếm full-text | cập nhật đắt, thường theo lô |
| Hierarchical timing wheels | scheduler, timeout, heartbeat | độ chính xác bằng một tick |
| Lossy counting / Count-min sketch | phần tử xuất hiện nhiều (heavy hitter), đếm tần suất xấp xỉ | chỉ ước lượng, count-min luôn đếm dư |
| Operational transformation | soạn thảo cộng tác | phức tạp, nhiều hệ chuyển sang CRDT |
| Frugal streaming | ước lượng trung vị, percentile trên luồng dữ liệu | chỉ xấp xỉ |
Mình đã viết chi tiết về ZSET và HyperLogLog trong Redis và Bloom filter chống cache penetration.
2. Bài toán liveness
Ý chính: 1 triệu thiết bị IoT gửi heartbeat mỗi 3 giây. Thiết bị nào im lặng quá ngưỡng timeout (cấu hình theo loại thiết bị) thì báo “mất kết nối”; báo trễ một chút được chấp nhận.
Yêu cầu chức năng:
- Quá ngưỡng timeout không có heartbeat thì phát cảnh báo thiết bị mất kết nối.
- Ngưỡng timeout cấu hình theo loại thiết bị (đèn đường 30 giây, cảm biến giao thông 10 giây…).
Yêu cầu phi chức năng: mở rộng được, chấp nhận trễ nhỏ giữa lúc hết hạn và lúc cảnh báo (ví dụ ≤ 1 giây).
Ước lượng nhanh:
- Heartbeat: 10⁶ / 3 giây ≈ 333K lần/giây. Mỗi lần là một thao tác “reset timer”.
- Số timer sống cùng lúc: 10⁶. Mỗi timer ~64 byte (id, thời điểm hết hạn, con trỏ) → ~64 MB, vừa RAM một máy.
- Lượng hết hạn: bình thường gần 0; khi một trạm phát sóng mất điện, có thể 100K thiết bị hết hạn cùng một giây.
Ba câu hỏi quyết định thiết kế: reset timer rẻ thế nào, tìm timer hết hạn rẻ thế nào (quét bao lâu một lần), và xử lý một đợt hết hạn lớn ra sao.
3. Cách 1: Redis sorted set
Ý chính: mỗi loại thiết bị một ZSET, member là device_id, score là thời điểm hết hạn. Heartbeat thì ZADD ghi đè score; một job định kỳ lấy và xoá các member có score nhỏ hơn hiện tại.
# heartbeat: ghi đè score, O(log n)
ZADD timeout:street_lamp <now + 30000> lamp-42
# mỗi giây: lấy và xoá timer hết hạn, O(log n + m)
ZRANGE timeout:street_lamp -inf <now> BYSCORE LIMIT 0 1000
ZREM timeout:street_lamp lamp-17 lamp-99 ...
ZADDcho member đã có chỉ cập nhật score, nên “thêm timer mới” và “xoá timer cũ” thật ra là một lệnh.ZREMRANGEBYSCOREcũng O(log n + m) nhưng chỉ trả số lượng đã xoá, không trả danh sách, nên không dùng để cảnh báo được. Phải đọc rồi xoá.- Key theo loại thiết bị giúp chia tải: mỗi ZSET có thể nằm trên một node Redis Cluster khác nhau.
Biến thể trên slide (gọi là 1.2): không xoá timer cũ, lưu thêm device_id → expiry dạng string; lúc quét thì so lại với string để bỏ timer lỗi thời. Cách này thêm I/O và không gói được vào một script Lua khi các key nằm ở slot khác nhau trong cluster. Thực ra không cần: ZADD đã ghi đè score.
Script Lua lấy và xoá nguyên tử, và chi phí thực tế
-- KEYS[1] = timeout:street_lamp, ARGV[1] = now, ARGV[2] = limit
local expired = redis.call('ZRANGE', KEYS[1], '-inf', ARGV[1], 'BYSCORE', 'LIMIT', 0, ARGV[2])
if #expired > 0 then
redis.call('ZREM', KEYS[1], unpack(expired))
end
return expired
Lua chạy nguyên tử trên một node, nên không heartbeat nào chen giữa. Giới hạn LIMIT để script không chặn Redis quá lâu khi có đợt hết hạn lớn (Redis đơn luồng).
Chi phí: 333K ZADD/giây vượt sức một node Redis (~100K–200K lệnh đơn/giây, nhiều hơn nếu pipeline). Cần chia theo loại thiết bị và thêm hậu tố shard (timeout:street_lamp:{0..15}, chọn theo hash(device_id) % 16). Mỗi heartbeat vẫn là một lượt mạng từ server nhận heartbeat tới Redis.
Bù lại, Redis cho persistence và replication sẵn: restart service không mất timer.
4. Cách 2: timing wheel
Ý chính: một mảng vòng cố định gồm các bucket; mỗi bucket chứa các timer hết hạn ở tick đó. Reset timer là gỡ khỏi bucket cũ và gắn vào bucket mới, O(1). Mỗi tick chỉ quét đúng một bucket.
Cấu tạo:
- Bánh xe: mảng vòng kích thước cố định, ví dụ 60 ô, mỗi tick 1 giây (kích thước ~ ngưỡng timeout).
- Bucket: mỗi ô là một danh sách timer (thường là danh sách liên kết đôi để gỡ O(1)).
- Timer:
device_id, chỉ số ô, số vòng còn lại (khi timeout dài hơn một vòng bánh xe). Map<deviceId, Timer>: tìm timer cũ của thiết bị trong O(1).
flowchart LR
HB[Heartbeat lamp-42] --> M["Map: lamp-42 -> timer (ô 7)"]
M --> R[Gỡ khỏi ô 7]
R --> A["Gắn vào ô (hiện tại + 30) mod 60"]
T[Tick mỗi giây] --> S[Quét đúng ô kim đang chỉ]
S --> X{Số vòng còn lại = 0?}
X -->|có| AL[Cảnh báo mất kết nối]
X -->|không| D[Giảm số vòng]
Khi heartbeat tới: lấy timer từ map, gỡ khỏi bucket cũ, tính ô mới (tick hiện tại + timeout) mod kích thước, gắn vào bucket mới. Tất cả O(1), chạy trong RAM.
Timer dài thì sao? Bánh xe 60 ô 1 giây chỉ phủ 60 giây; timeout 1 giờ phải dùng “số vòng còn lại”, và mỗi lần kim qua ô đó lại phải xét timer chưa tới hạn. Kafka giải bằng hierarchical timing wheels: bánh giây, bánh phút, bánh giờ xếp tầng. Timer xa nằm ở bánh thô; khi gần tới hạn thì được hạ xuống bánh mịn hơn.
Code Java: timing wheel tối giản cho heartbeat
final class TimingWheel {
private final int size; // số ô, ví dụ 60
private final List<Set<String>> buckets;
private final Map<String, Integer> slotOf = new HashMap<>();
private final Map<String, Integer> roundsOf = new HashMap<>();
private int cursor = 0;
TimingWheel(int size) {
this.size = size;
this.buckets = new ArrayList<>(size);
for (int i = 0; i < size; i++) buckets.add(new HashSet<>());
}
// gọi trong thread của bánh xe (một thread duy nhất sở hữu cấu trúc này)
void heartbeat(String deviceId, int timeoutTicks) {
Integer old = slotOf.get(deviceId);
if (old != null) buckets.get(old).remove(deviceId); // O(1)
int slot = (cursor + timeoutTicks) % size;
buckets.get(slot).add(deviceId);
slotOf.put(deviceId, slot);
roundsOf.put(deviceId, timeoutTicks / size);
}
// gọi mỗi tick, trả danh sách thiết bị hết hạn
List<String> tick() {
cursor = (cursor + 1) % size;
List<String> expired = new ArrayList<>();
Iterator<String> it = buckets.get(cursor).iterator();
while (it.hasNext()) {
String id = it.next();
int rounds = roundsOf.get(id);
if (rounds == 0) { it.remove(); slotOf.remove(id); roundsOf.remove(id); expired.add(id); }
else roundsOf.put(id, rounds - 1);
}
return expired;
}
}
Cấu trúc này không thread-safe, và đó là chủ ý: một thread duy nhất sở hữu bánh xe, các thread nhận heartbeat đẩy sự kiện vào hàng đợi cho nó. Đây là đúng chỗ mục 5 bàn tới. HashSet cho gỡ O(1) trung bình; Netty dùng danh sách liên kết đôi và đánh dấu huỷ để tránh băm.
5. Bucket lớn: chia việc cho nhiều thread
Ý chính: khi 100K thiết bị cùng hết hạn trong một tick, một thread vừa quét vừa gửi cảnh báo sẽ trễ tick sau. Tách ra: thread chính chỉ quét, đẩy timer hết hạn vào hàng đợi; nhiều worker thread lấy ra kiểm tra và gửi cảnh báo.
Việc cho mỗi timer hết hạn: kiểm tra lại, ghi trạng thái, gửi cảnh báo (gọi Kafka hay HTTP, tốn I/O). Phần I/O là chậm nhất nên đáng chia cho nhiều thread.
Câu hỏi mới: thread chính giao việc cho worker bằng gì, và nếu thread chính đẩy nhanh hơn worker xử lý thì sao? Câu trả lời là một hàng đợi có giới hạn ở giữa.
flowchart LR
P["Thread quét (producer)"] --> Q[Hàng đợi]
Q --> W1[Worker 1]
Q --> W2[Worker 2]
Q --> W3[Worker 3]
Hàng đợi trong môi trường nhiều thread có các vấn đề riêng:
- Mảng: cố định kích thước, phải xử lý khi đầy (chặn producer, tức backpressure).
- Danh sách liên kết: không giới hạn thì có thể ăn hết bộ nhớ; node rải rác, không thân thiện CPU cache.
- Tranh chấp ghi lên
head,tail,size: producer và consumer cùng sửa, phải khoá hoặc CAS. - Rác cho GC: mỗi phần tử là một object mới, xong việc thì thành rác.
ArrayBlockingQueue của Java dùng một ReentrantLock chung cho cả put và take. LinkedBlockingQueue dùng hai lock nhưng tạo node mới mỗi lần put. Ở hàng triệu sự kiện mỗi giây, lock và GC thành nút cổ chai.
6. LMAX Disruptor: hàng đợi giữa các thread không dùng lock
Ý chính: Disruptor là thư viện truyền thông điệp giữa các thread trong một JVM. Nó dùng ring buffer cấp phát sẵn, mỗi bên tự giữ con trỏ thứ tự (sequence) của mình, đồng bộ bằng CAS và memory barrier thay vì lock.
Các ý làm nó nhanh:
- Ring buffer cấp sẵn lúc khởi động: producer chỉ ghi đè trường của ô có sẵn, không tạo object mới, gần như không sinh rác.
- Tách producer và consumer: mỗi consumer có sequence riêng, producer chỉ đọc sequence của consumer chậm nhất để biết còn chỗ không. Không có biến
sizechung để tranh nhau. - CAS thay lock: một producer thì không cần cả CAS; nhiều producer thì giành ô bằng CAS.
- Memory barrier (volatile) đảm bảo consumer thấy dữ liệu đã ghi xong trước khi thấy sequence mới.
- Xử lý theo lô: consumer chậm có thể lấy cả đoạn từ sequence của mình tới sequence mới nhất trong một lần.
- Chỉnh được: chọn wait strategy (busy spin, yield, blocking) tuỳ đổi CPU lấy latency.
Số đo từ tài liệu của LMAX (pipeline 3 tầng): latency trung bình 52 ns so với 32.757 ns của ArrayBlockingQueue; p99 128 ns so với ~2,1 ms. Throughput một producer một consumer: ~160 triệu so với ~21 triệu thao tác/giây.
Code Java: Disruptor cho thread quét và worker gửi cảnh báo
final class ExpiredSlot { String deviceId; long expiredAt; } // ô có sẵn, được ghi đè
Disruptor<ExpiredSlot> disruptor = new Disruptor<>(
ExpiredSlot::new,
1 << 16, // 65.536 ô, luỹ thừa của 2
Thread.ofPlatform().factory(),
ProducerType.SINGLE, // chỉ thread quét ghi
new BlockingWaitStrategy()); // tiết kiệm CPU, latency cao hơn spin
// 4 worker chia nhau sự kiện (mỗi sự kiện chỉ 1 worker xử lý)
WorkHandler<ExpiredSlot>[] workers = IntStream.range(0, 4)
.mapToObj(i -> (WorkHandler<ExpiredSlot>) e -> alertService.send(e.deviceId, e.expiredAt))
.toArray(WorkHandler[]::new);
disruptor.handleEventsWithWorkerPool(workers);
RingBuffer<ExpiredSlot> ring = disruptor.start();
// thread quét
for (String id : wheel.tick()) {
ring.publishEvent((slot, seq, dev, ts) -> { slot.deviceId = dev; slot.expiredAt = ts; }, id, now);
}
publishEvent sẽ chờ nếu ring đầy: đó là backpressure tự nhiên. Ở bản Disruptor 4, WorkerPool bị bỏ; dùng nhiều EventHandler và mỗi handler chỉ xử lý sự kiện có sequence % n == i của mình, hoặc dùng BatchEventProcessor.
Thêm hai chi tiết “mechanical sympathy”: các sequence được đệm thêm byte để mỗi cái nằm riêng một cache line 64 byte (tránh false sharing, khi hai core sửa hai biến khác nhau nhưng chung cache line và phải giành nhau line đó); và ring buffer là mảng liền nên CPU prefetch tốt.
Nền tảng cần có trước: race condition, volatile và deadlock và ExecutorService.
7. Thiết kế tổng thể và cách trình bày
Ý chính: nhiều instance nhận heartbeat, thiết bị được định tuyến theo hash(device_id) để mỗi thiết bị luôn về một instance; mỗi instance giữ timing wheel của mình, lưu last_seen theo lô để khôi phục, và đẩy cảnh báo qua Kafka.
flowchart LR
D[1M thiết bị] --> LB[Load balancer, hash theo device_id]
LB --> I1[Instance 1: timing wheel]
LB --> I2[Instance N: timing wheel]
I1 --> K[Kafka: device-offline]
I2 --> K
I1 -.->|last_seen theo lô| S[(Redis / Cassandra)]
K --> N[Notification, dashboard]
Thứ tự trình bày trong phỏng vấn (khoảng 45 phút):
- 5 phút: hỏi yêu cầu. Số thiết bị, chu kỳ heartbeat, ngưỡng timeout, độ trễ cảnh báo chấp nhận được, có cần bền khi restart không.
- 5 phút: ước lượng. 333K heartbeat/giây, 1M timer, ~64 MB.
- 10 phút: phương án đơn giản trước (Redis ZSET), nêu chi phí mạng và giới hạn một key.
- 15 phút: timing wheel, phân vùng theo device, khôi phục sau restart, đợt hết hạn lớn và hàng đợi cho worker.
- 5 phút: lỗi và vận hành. Instance chết (thiết bị chuyển instance, chờ một chu kỳ trước khi cảnh báo), mạng chập chờn (cảnh báo sau 2–3 lần lỡ heartbeat), metric độ trễ cảnh báo.
- 5 phút: tóm tắt ba quyết định chính và điều bạn sẽ làm nếu có thêm thời gian.
Ghi nhớ
- Phân tích được một cấu trúc dữ liệu theo năm câu hỏi, và giải thích vì sao O(1) qua mạng có thể chậm hơn O(log n) trong RAM.
- Viết được lệnh Redis cho heartbeat và job quét, và biết vì sao phải gói đọc-xoá trong Lua.
- Vẽ được timing wheel, giải thích reset timer O(1) và vai trò của hierarchical timing wheels.
- Biết khi nào Disruptor đáng dùng và khi nào
ArrayBlockingQueuelà đủ. - Biết cách khôi phục timer sau restart và tránh báo động giả khi rebalance.
Câu hỏi phỏng vấn
Mid
Thiết kế cơ chế phát hiện thiết bị mất kết nối đơn giản nhất bằng Redis.
Mỗi loại thiết bị một ZSET, member là device_id, score là thời điểm hết hạn; heartbeat thì ZADD ghi đè, job mỗi giây lấy và xoá member có score ≤ now bằng một script Lua.
ZADD O(log n); lấy hết hạn O(log n + m). Giới hạn số phần tử mỗi lần quét để không chặn Redis, và chia key theo shard khi tải vượt một node.
Vì sao không dùng TTL của key Redis và keyspace notification để phát hiện hết hạn?
Vì Redis xoá key hết hạn theo kiểu lười và lấy mẫu ngẫu nhiên, nên sự kiện expired có thể đến trễ đáng kể, và notification là pub/sub “bắn rồi quên”: subscriber mất kết nối là mất sự kiện.
Muốn chắc chắn thì phải có cấu trúc mình quét được (ZSET) hoặc timer trong service.
Timing wheel là gì, và vì sao reset timer chỉ tốn O(1)?
Mảng vòng các bucket, mỗi bucket chứa timer hết hạn ở tick đó; reset là tra map lấy timer cũ, gỡ khỏi bucket cũ, gắn vào bucket (cursor + timeout) mod size.
Mỗi tick chỉ quét một bucket. Đổi lại độ chính xác bị làm tròn tới một tick.
Senior
Timing wheel không phù hợp với timer dài. Bạn xử lý thế nào?
Dùng hierarchical timing wheels: nhiều bánh xe với tick khác nhau (giây, phút, giờ); timer xa nằm ở bánh thô và được hạ dần xuống bánh mịn khi gần tới hạn.
Kafka dùng cách này cho purgatory. Cách khác là đếm vòng còn lại trong một bánh, nhưng mỗi lần kim qua phải duyệt cả timer chưa tới hạn.
Heartbeat 333K/giây vào Redis ZSET có ổn không?
Không ổn trên một node; phải chia key thành nhiều shard theo hash(device_id), và vẫn tốn một lượt mạng mỗi heartbeat.
Ở tải này, timing wheel trong RAM của chính service (thiết bị định tuyến theo hash) rẻ hơn nhiều, chỉ cần thêm cơ chế lưu last_seen theo lô để khôi phục.
Vì sao LMAX Disruptor nhanh hơn ArrayBlockingQueue?
Không lock (CAS và memory barrier), ring buffer cấp sẵn nên gần như không tạo rác, mỗi bên giữ sequence riêng nên không tranh một biến size, và consumer đọc theo lô.
Thêm padding để tránh false sharing và mảng liền thân thiện CPU cache. Đổi lại: kích thước cố định, busy-spin đốt CPU, chỉ dùng trong một JVM.
Một đợt 100K thiết bị cùng hết hạn trong một tick. Hệ thống của bạn phản ứng thế nào?
Thread quét chỉ lấy timer và đẩy vào hàng đợi có giới hạn; worker pool gửi cảnh báo, gộp theo lô và theo khu vực; hàng đợi đầy thì thread quét chờ (backpressure) thay vì làm sập bộ nhớ.
Với đợt lớn cùng lúc, thường là sự cố hạ tầng (mất điện, mất sóng), nên gộp thành một cảnh báo khu vực thay vì 100K tin nhắn.
Service giữ timing wheel bị restart. Làm sao không bỏ sót thiết bị chết?
Lưu last_seen của mỗi thiết bị ra storage bền theo lô, lúc khởi động nạp lại và đặt timer last_seen + timeout, kèm một khoảng ân hạn để tránh báo động giả do dữ liệu hơi cũ.
Định tuyến thiết bị bằng consistent hashing để khi thêm bớt instance chỉ một phần thiết bị phải chuyển.
Từ vựng tiếng Anh
| Term | Phát âm | Nghĩa | Ví dụ câu tiếng Anh dùng trong phỏng vấn |
|---|---|---|---|
| heartbeat | /ˈhɑːrt.biːt/ | tín hiệu “tôi còn sống” | “Each device sends a heartbeat every three seconds.” |
| liveness | /ˈlaɪv.nəs/ | trạng thái còn sống | “The liveness service raises an alert when a device goes quiet.” |
| timing wheel | /ˈtaɪ.mɪŋ wiːl/ | bánh xe hẹn giờ | “A timing wheel resets a timer in constant time.” |
| bucket | /ˈbʌk.ɪt/ | ô chứa | “On each tick we only scan one bucket.” |
| tick | /tɪk/ | một nhịp đồng hồ | “Precision is limited to one tick.” |
| sorted set | /ˈsɔːr.tɪd set/ | tập có thứ tự (Redis ZSET) | “The score is the expiry timestamp.” |
| backpressure | /ˈbæk.preʃ.ɚ/ | đẩy ngược khi bên nhận quá tải | “A bounded queue gives us backpressure for free.” |
| ring buffer | /rɪŋ ˈbʌf.ɚ/ | bộ đệm vòng | “The Disruptor pre-allocates its ring buffer at startup.” |
| false sharing | /fɔːls ˈʃer.ɪŋ/ | hai biến chung cache line gây tranh chấp | “Padding the sequence avoids false sharing.” |
| contention | /kənˈten.ʃən/ | tranh chấp tài nguyên | “Lock contention on the queue became the bottleneck.” |
Ghi chép dựa trên khoá System Design (Ronin Engineer), viết lại theo cách hiểu của mình.