Cheat Sheet
Tham chiếu một trang cho cả 46 pattern. In ra, đánh dấu, hoặc ctrl-F để tìm trong đây.
Chọn theo bài toán
Chưa rõ cần pattern nào? Bắt đầu từ đây.
| Tôi cần... | Hãy dùng | Vì sao |
|---|---|---|
| Giới hạn truy cập đồng thời | Semaphore | Dùng bộ đếm, đã chứng minh trong kernel OS |
| Xử lý consumer chậm | Backpressure | Đừng bỏ — đẩy ngược lại |
| Cache có loại bỏ | LRU Cache | get/put O(1), tự loại cái nguội nhất |
| Tra cứu tiền tố nhanh | Trie | O(k) theo độ dài key, không phụ thuộc kích thước tập |
| Kiểm tra có-thể-thuộc-tập | Bloom Filter | Không âm tính giả, ít bộ nhớ |
| Truy vấn khoảng đã sắp xếp | B+ Tree hoặc Skip List | B+ Tree cho đĩa, Skip List cho bộ nhớ |
| Ghi an toàn khi crash | WAL + Checkpointing | Log-trước-rồi-apply + snapshot định kỳ |
| Chặn lỗi lan truyền | Circuit Breaker | Fail nhanh, khôi phục dần |
| Retry cuộc gọi thất bại | Retry with Backoff | Delay theo cấp số nhân + jitter |
| Kiểm soát throughput | Rate Limiter | Token bucket, refill đều |
| Xác minh toàn vẹn dữ liệu | Merkle Tree | Bằng chứng O(log n) qua chuỗi hash |
| Giảm bộ nhớ qua chia sẻ | Flyweight hoặc Interning | Chia sẻ giá trị bất biến |
| Tránh áp lực GC | Object Pool hoặc Arena | Tái sử dụng hoặc giải phóng hàng loạt |
| Phát hiện thay đổi rẻ | Dirty Flag | Bỏ qua tính lại nếu sạch |
| Sắp xếp sự kiện phân tán | Logical Clock | Lamport hoặc vector clock |
| Đánh giá lười | Iterator | Kiểu pull, không cấp phát trung gian |
| Xử lý nhiều kiểu | Tagged Union hoặc Vtable | Tag cho tập đóng, vtable cho tập mở |
| Tải nặng ghi | LSM Tree | Buffer → flush → merge |
| Ghép middleware | Middleware Chain | Mô hình hành tây, mỗi handler bọc cái kế |
| Cân bằng việc giữa các thread | Work Stealing | Rảnh lấy trộm từ bận |
| Theo dõi nhiều flag | Bitmask | N flag trong một số nguyên |
| Lập lịch theo ưu tiên | Min Heap | Peek O(1), push/pop O(log n) |
| FIFO kích thước cố định | Ring Buffer | Vòng quanh, không cấp phát |
| Diff tối thiểu giữa hai trạng thái | Diff / Patch | Tính + áp dụng thay đổi |
| Tách producer/consumer | Observer | Mô hình subscribe |
| Phân bố key qua các node | Consistent Hashing | Thêm/bớt node remap ~1/n |
| Thứ tự build từ dependency | Dependency Graph | DAG + sắp xếp topo |
| Chuyển trạng thái nguyên tử | State Machine | Trạng thái rõ ràng, chuyển bất hợp lệ không biểu diễn được |
| Xoá mềm và dọn sau | Tombstone | Đánh dấu đã xoá, dồn nén sau |
| Chia sẻ với copy khi đổi | Copy-on-Write | Chia sẻ cho đến khi có người ghi |
| Dọn dẹp xác định | Reference Counting | Giải phóng khi rc=0, không tạm dừng GC |
| Đăng ký/khám phá service | Registry | Map name → handler |
| Hoán đổi trạng thái nguyên tử | Double Buffering | Ghi vào back, hoán đổi sang front |
| Đọc không block | MVCC | Snapshot có phiên bản |
| Main thread phản hồi nhanh | Cooperative Scheduling | Yield giữa các khối |
| I/O đơn luồng | Event Loop | Ghép kênh không cần thread |
| Tích luỹ rồi flush | Batch Processing | Phân bổ chi phí mỗi thao tác |
| Cô lập kiểu actor | Actor Model | State riêng + truyền thông điệp |
| Dispatch khi duyệt cây | Visitor | Callback đặc thù theo kiểu |
| Cấp phát O(1) từ slot đã giải phóng | Free List | Linked list các block tự do |
| Gộp các luồng đã sắp xếp | Merge Iterator | Gộp k-luồng qua min-heap |
Tham chiếu độ phức tạp
Cấu trúc dữ liệu
| Pattern | Thêm | Tra | Xoá | Bộ nhớ | Đánh đổi chính |
|---|---|---|---|---|---|
| Bitmask | O(1) | O(1) | O(1) | O(1) | Giới hạn số flag bằng độ rộng word |
| Min Heap | O(log n) | O(1) peek | O(log n) | O(n) | Chỉ peek-min là nhanh |
| Ring Buffer | O(1) | O(1) | O(1) | O(n) cố định | Sức chứa cố định |
| Trie | O(k) | O(k) | O(k) | O(SIGMA * n) | Tốn bộ nhớ với key thưa |
| Skip List | O(log n) trung bình | O(log n) trung bình | O(log n) trung bình | O(n) trung bình | Theo xác suất, đơn giản hơn cây |
| Bloom Filter | O(k) | O(k) | N/A | O(m) bit | Có thể có dương tính giả |
| LRU Cache | O(1) | O(1) | O(1) | O(n) | Loại bỏ khi đầy |
| B+ Tree | O(log n) | O(log n) | O(log n) | O(n) | Tối ưu cho đĩa, fanout cao |
| Tagged Union | N/A | O(1) dispatch | N/A | O(variant lớn nhất) | Tập kiểu đóng |
| Merkle Tree | O(log n) | O(log n) | O(log n) | O(n) | Để xác minh, không phải tìm kiếm |
| Merge Iterator | N/A | O(log k) next | N/A | O(k) | k = số luồng |
Pattern hệ thống
| Pattern | Throughput | Độ trễ | Cách lỗi |
|---|---|---|---|
| Circuit Breaker | Bình thường khi đóng | +0 đóng, fail-fast khi mở | Chặn mọi cuộc gọi khi mở |
| Rate Limiter | Bị chặn ở tốc độ token | +0 nếu có token | Từ chối quá tải (429) |
| Retry with Backoff | Giảm khi retry | Tăng theo cấp số nhân | Khuếch đại nếu không có jitter |
| WAL | Tốc độ ghi tuần tự | +1 ghi (log trước) | An toàn — replay từ log |
| Batch Processing | Cao hơn (phân bổ) | Cao hơn (chờ lô) | Mất lô khi crash |
| Consistent Hashing | Như nền bên dưới | +chi phí hash | ~1/n key remap khi đổi node |
Pattern bộ nhớ
| Pattern | Cấp phát | Giải phóng | Overhead | Tốt nhất cho |
|---|---|---|---|---|
| Object Pool | O(1) phân bổ | O(1) trả về | Kích thước pool | Object cùng kiểu thay đổi nhiều |
| Arena Allocator | O(1) bump | O(1) hàng loạt | Phí canh chỉnh | Vòng đời theo pha |
| Free List | O(1) | O(1) | Con trỏ next mỗi slot | Block kích thước cố định |
| Flyweight | O(1) tra | Chia sẻ, không giải phóng | Bảng tra | Nhiều object nhỏ giống nhau |
| Copy-on-Write | O(1) chia sẻ | O(n) khi ghi đầu | Ref count mỗi page | Dữ liệu chia sẻ nặng đọc |
| Reference Counting | O(1) clone | O(1) khi rc=0 | Bộ đếm mỗi object | Dọn dẹp xác định |
| Interning | O(k) lần đầu, O(1) sau | Pool | Hash table | Khử trùng lặp chuỗi/symbol |
Bộ combo pattern
Các pattern hiếm khi xuất hiện đơn lẻ. Đây là các combo production phổ biến nhất:
| Combo | Dùng trong | Vì sao kết hợp |
|---|---|---|
| WAL + Checkpointing | PostgreSQL, etcd | WAL cho an toàn, checkpoint giới hạn replay |
| Bloom Filter + LSM Tree | LevelDB, RocksDB | Bỏ qua đọc đĩa không cần |
| Min Heap + Merge Iterator | Compaction LevelDB | Gộp hiệu quả K luồng đã sắp xếp |
| Circuit Breaker + Retry | gRPC, Hystrix | Retry lỗi thoáng qua, ngắt khi kéo dài |
| Rate Limiter + Backpressure | API gateway | Giới hạn đầu vào, tín hiệu quá tải |
| Ring Buffer + Event Loop | libuv, io_uring | Queue kích thước cố định cho event I/O |
| Object Pool + Free List | Go runtime | Pool quản lý slab, free list theo dõi slot |
| MVCC + B+ Tree | PostgreSQL | Row có phiên bản trong index tối ưu cho đĩa |
| Dirty Flag + Double Buffering | React Fiber | Đánh dấu dirty, gom vào frame tiếp theo |
| Bitmask + State Machine | Reconciler React | Flag mã hoá state, chuyển tiếp qua phép bitwise |
| Consistent Hashing + Registry | Service mesh | Hash để định vị, registry để khám phá |
| Trie + Interning | Compiler | Intern chuỗi, tra theo prefix |
Cây quyết định
"Cache nào?"
Need eviction?
- YesNeed O(1) ops?
- NoNeed probabilistic filter?
- YesBloom FilterNot a cache, but saves cache misses
- NoHash mapA hash map is fine
"Chiến lược bộ nhớ nào?"
All objects same size?
- YesObject Pool / Free List
- NoPhase-based lifetime?
- YesArena Allocator
- NoShared immutable?
"Mô hình concurrency nào?"
Shared state?
- NoActor ModelMessage passing
- YesRead-heavy?
- YesMVCCReaders never block
- NoNeed limit on concurrency?
- YesSemaphore
- NoNeed to split work?