Cache phân tán
Hiểu đề
Yêu cầu chức năng
- Service có thể get/set/delete một key với TTL, và mget nhiều key một lần
- Cụm tự chia key lên nhiều node; thêm hoặc bớt node mà không phải dừng hệ thống
- Node chết thì cụm tự chuyển sang bản sao và client tự biết node mới
- Hết RAM thì node tự loại bỏ key ít dùng nhất (LRU), key hết TTL tự bị xóa
Yêu cầu phi chức năng
- get p99 < 1 ms phía server, < 2 ms tính cả mạng trong cùng AZ
- Chịu được 1,5 triệu ops/s ở mức lớn nhất, scale ngang bằng cách thêm shard
- Thêm một node chỉ làm khoảng 1/N số key đổi chỗ
- Một node chết: failover xong dưới 10 s, độ sẵn sàng 99,99%
- Hit rate ≥ 95%; chấp nhận dữ liệu cũ tối đa bằng TTL (nhất quán sau)
Ngoài phạm vi: Lưu trữ bền vững như database (cache được phép mất dữ liệu); Cấu trúc dữ liệu phức tạp (sorted set, stream), chỉ nói key-value; Transaction nhiều key, Lua script; Đồng bộ mạnh giữa nhiều region.
Thực thể và API
| Method | Endpoint | Ghi chú |
|---|---|---|
| GET | cache.get(key) | Trả value hoặc miss. Client hash key để chọn đúng shard, không cần hop trung gian. |
| SET | cache.set(key, value, ttlSec) | Ghi vào primary của shard, replica nhận bất đồng bộ. Luôn nên có TTL. |
| DEL | cache.delete(key) | Dùng khi DB thay đổi để bỏ bản cũ (cache-aside: ghi DB rồi xóa cache). |
| MGET | cache.mget(keys[]) | Client gom key theo shard, gửi song song, ghép kết quả. |
| GET | /admin/v1/shard-map?since={version} | Client lấy ShardMap mới khi version đổi hoặc khi node trả lỗi MOVED. |
| POST | /admin/v1/shards/{id}/failover | Chuyển primary thủ công khi bảo trì; bình thường health checker tự làm. |
Thiết kế tổng thể
Đi lần lượt từng yêu cầu chức năng. Mục tiêu ở đây là chạy đúng, việc tối ưu để dành cho phần đào sâu.
1) Service có thể get/set/delete key với TTL
Service dùng mẫu cache-aside: đọc cache trước, miss thì đọc DB rồi set lại. Cache client trong service tự chọn node nên mỗi lệnh chỉ đi một hop qua TCP.
- 1Service gọi cache.get('user:42')
- 2Client tính hash(key), tra ShardMap ra shard 7, gửi lệnh đến primary của shard 7
- 3Hit: node tra hash map O(1), đưa entry lên đầu danh sách LRU, trả value
- 4Miss: service đọc DB, gọi cache.set(key, value, 300)
- 5Khi DB đổi: service ghi DB xong thì cache.delete(key)
Nguồn: Grokking Modern System Design · ch.16 Distributed Cache ↗ · mục "Writing policies" (write-around tương ứng cache-aside) và "Cache client"
2) Cụm tự chia key lên nhiều node và thêm/bớt node không dừng
Key được chia bằng consistent hashing với virtual node, ShardMap lưu ở configuration service. Thêm node thì chỉ một phần vòng hash chuyển sang node mới, dữ liệu được chuyển dần.
- 1Admin thêm node mới, config service gán cho nó một số virtual node trên vòng
- 2Node mới kéo key của các đoạn vòng được giao từ node cũ (hoặc để trống và nạp dần qua miss)
- 3Chuyển xong: ShardMap tăng version, config service báo cho mọi client
- 4Client dùng map cũ gửi nhầm thì node trả MOVED, client tải map mới rồi gửi lại
Nguồn: Grokking Modern System Design · ch.16 Distributed Cache ↗ · mục "Sharding in cache clusters" và "Maintain cache servers list" ; Grokking Modern System Design · ch.10 Key-value Store ↗ · mục "Consistent hashing" và "Use virtual nodes"
3) Node chết thì cụm tự chuyển sang bản sao
Mỗi shard có primary và replica ở AZ khác. Health checker theo dõi theo đa số; khi đa số thấy primary chết thì đưa replica lên và cập nhật ShardMap.
- 1Health checker (3 instance) ping mỗi node mỗi 1 s
- 2Primary shard 7 không trả lời 5 s, ít nhất 2/3 checker đồng ý là chết
- 3Chọn replica có offset replication mới nhất, đổi thành primary, tăng epoch của shard
- 4Config service phát ShardMap mới, client chuyển request sang primary mới
- 5Node cũ quay lại thì thành replica, không nhận request cho đến khi đồng bộ xong
Nguồn: Grokking Modern System Design · ch.16 Distributed Cache ↗ · mục "Improve availability" ; Redis in Action ↗ · ch.4 · §4.2 Replication (tr. 70)
4) Hết RAM thì tự loại key ít dùng
Mỗi node có giới hạn maxmemory. Khi set làm vượt giới hạn, node loại key ở cuối danh sách LRU cho đến khi đủ chỗ; key hết TTL bị xóa khi đọc trúng và bởi một vòng quét nền.
- 1set mới làm RAM vượt maxmemory
- 2Node lấy entry ở đuôi danh sách LRU, xóa khỏi hash map và danh sách
- 3Lặp đến khi RAM dưới giới hạn rồi mới ghi entry mới
- 4Vòng quét nền mỗi 100 ms lấy mẫu key có TTL, xóa key đã hết hạn
Nguồn: Grokking Modern System Design · ch.16 Distributed Cache ↗ · mục "Eviction policies" và "Cache invalidation" (active/passive expiration)
Hạ tầng theo quy mô
Cùng một sản phẩm, ba mức người dùng. Chọn từng mức để xem sơ đồ, phép tính và cấu hình server thay đổi thế nào.
Một node Redis managed cạnh một Postgres. Toàn bộ dữ liệu nóng vừa 1 GB RAM, chưa cần chia shard hay replica; mất cache thì DB vẫn tự đỡ được.
Ước lượng
- Lệnh cache: 10.000 × 100 req × 5 lệnh = 5 triệu/ngày / 86.400 ≈ 58 ops/s, đỉnh ×10 ≈ 579 ops/s
- RAM: 200.000 key × (50 + 1.000 + 100 B) × 1,3 ≈ 299 MB
- Hit rate 95%: DB chỉ nhận 579 × 5% ≈ 29 đọc/s
- Độ trễ trung bình (EAT): 0,95 × 1 ms + 0,05 × 20 ms = 0,95 + 1 = 1,95 ms
- API: 10.000 × 100 / 86.400 ≈ 11,6 req/s, đỉnh ×10 ≈ 116 req/s → ceil(116 / 600) = 1, lấy tối thiểu 2
Nguồn con số: Grokking Modern System Design · ch.5 Back-of-the-envelope Calculations ↗ · mục "Standard numbers to remember" và "Requests estimation" ; Grokking Modern System Design · ch.16 Distributed Cache ↗ · mục "High performance" (EAT) ; Quy tắc ước lượng của khoá học · /hoc/chon-server
Bảng hạ tầng
| Thành phần | Chọn | Số lượng | Cấu hình | Vì sao |
|---|---|---|---|---|
| App | Node.js + ioredis, Cloud Run | 2 | 2 vCPU · 4 GB RAM | 116 req/s chỉ cần 1 instance, chạy 2 để dự phòng; client nối thẳng 1 node Redis. |
| Cache | Redis managed (Memorystore Basic / ElastiCache) | 1 node | 1 GB RAM, maxmemory-policy allkeys-lru | 299 MB dữ liệu, 579 ops/s, rất xa mức 100.000 ops/s của một node. |
| Database | PostgreSQL managed | 1 | 2 vCPU · 8 GB · 50 GB SSD | Cả khi cache chết, 579 đọc/s vẫn vừa một Postgres; cache ở mức này chủ yếu để giảm độ trễ. |
| Monitoring | Cloud Monitoring / CloudWatch | 1 | Dịch vụ managed | Theo dõi hit rate, RAM, số key bị loại để biết khi nào cần lớn hơn. |
- Điểm xuất phát: cache-aside với một node Redis, mọi key có TTL
- Chưa có shard, replica hay config service vì mất cache không làm sập DB
Khi dữ liệu nóng lên hàng chục GB, một node không đủ RAM; và khi DB phụ thuộc vào cache để sống, một node chết là sự cố lớn.
Cấu hình và chi phí là ước lượng để học và trình bày trong phỏng vấn. Xem cách tính ở bài Chọn server.
So sánh nhanh ba mức
| Thành phần | Mức 1 | Mức 2 | Mức 3 |
|---|---|---|---|
| Người dùng | Sản phẩm 10.000 DAU | Sản phẩm 1 triệu DAU | Nền tảng 50 triệu DAU, nhiều team dùng chung |
| Chi phí | ≈ 50–100 USD/tháng (ước lượng) | ≈ 1.000–2.500 USD/tháng (ước lượng) | ≈ 25.000–50.000 USD/tháng (ước lượng, chủ yếu là 60 node RAM lớn) |
| App | Node.js + ioredis, Cloud Run 2 × 2 vCPU · 4 GB RAM | Node.js + ioredis (Cluster mode), autoscale 10 (autoscale) × 2 vCPU · 4 GB RAM | Chưa cần |
| Cache | Redis managed (Memorystore Basic / ElastiCache) 1 node × 1 GB RAM, maxmemory-policy allkeys-lru | ElastiCache / Memorystore Redis Cluster 4 shard × (1 primary + 1 replica) = 8 node × 2 vCPU · 13 GB mỗi node | Chưa cần |
| Database | PostgreSQL managed 1 × 2 vCPU · 8 GB · 50 GB SSD | PostgreSQL managed (HA) 1 primary + 1 read replica × 4 vCPU · 16 GB · 500 GB SSD | Chưa cần |
| Monitoring | Cloud Monitoring / CloudWatch 1 × Dịch vụ managed | Prometheus + Grafana 1 × 2 vCPU · 8 GB | Prometheus + Grafana + cảnh báo 2 × 4 vCPU · 16 GB |
| Định tuyến | Chưa cần | Smart client: 16.384 slot, CRC16(key) Trong mỗi app × Tự cập nhật map khi nhận MOVED | Smart client (Node/Go/Java), sidecar Envoy cho ngôn ngữ khác Trong mỗi pod service × Theo dõi ShardMap qua watch của etcd |
| Cache node | Chưa cần | Chưa cần | Redis (engine) trên VM/Kubernetes, 3 AZ 30 shard × (1 primary + 1 replica) = 60 node × 8 vCPU · 32 GB mỗi node, maxmemory 26 GB |
| Config service | Chưa cần | Chưa cần | etcd 3 node × 2 vCPU · 8 GB mỗi node |
| Health checker | Chưa cần | Chưa cần | Go service, bỏ phiếu theo đa số 3 instance (mỗi AZ một) × 2 vCPU · 4 GB |
| L1 cache | Chưa cần | Chưa cần | LRU trong process + count-min sketch Trong mỗi pod service × 256 MB, TTL 2 s cho key nóng |
| Service gọi cache | Chưa cần | Chưa cần | Các service của công ty trên Kubernetes ≈ 483 pod × 2 vCPU · 4 GB mỗi pod |
| Xóa cache qua CDC | Chưa cần | Chưa cần | Debezium + Kafka + Invalidator 3 broker Kafka, 6 pod Invalidator × Topic invalidations 12 partition; Invalidator 2 vCPU · 4 GB |
Đào sâu
Mỗi câu hỏi đi từ cách đơn giản đến cách người phỏng vấn mong đợi ở cấp senior.
1) Chia key lên nhiều node thế nào để thêm/bớt node không làm cả cụm mất cache?
Đơn giản và chia đều. Nhưng đổi N từ 10 lên 11 thì khoảng 10/11 ≈ 91% key đổi node, gần như toàn bộ cache miss cùng lúc và DB nhận hết tải.
Đánh đổi: Chỉ ổn khi số node cố định mãi; mỗi lần scale là một sự cố.
Nguồn: Grokking Modern System Design · ch.9 Databases ↗ · mục "Avoid hash mod n"
Key thuộc node đầu tiên đi theo chiều kim đồng hồ trên vòng. Thêm một node chỉ lấy một đoạn của node kề bên, khoảng 1/N key đổi chỗ. Tìm node bằng tìm kiếm nhị phân trên vòng, O(log N) (Grokking ch.16).
Đánh đổi: Mỗi node chỉ một điểm trên vòng nên đoạn to đoạn nhỏ, tải lệch; node chết thì toàn bộ tải dồn sang đúng một node kế tiếp.
Nguồn: Grokking Modern System Design · ch.16 Distributed Cache ↗ · mục "High performance" (consistent hashing O(log N))
Mỗi node máy thật giữ 100-200 virtual node rải khắp vòng, máy mạnh giữ nhiều hơn (Grokking ch.10 Key-value Store). Tải chia đều, node chết thì phần của nó rải ra nhiều node. Cách tương đương là 16.384 slot cố định như Redis Cluster: chuyển slot từng cái một, trong lúc chuyển node trả ASK/MOVED để client đi đúng chỗ. ShardMap có version lưu trong etcd/ZooKeeper để mọi client nhìn cùng một bản.
Đánh đổi: Cần config service và quy trình chuyển dữ liệu; client phải xử lý MOVED và cập nhật map, map lệch giữa các client sẽ gây miss tạm thời.
Nguồn: Grokking Modern System Design · ch.10 Key-value Store ↗ · mục "Use virtual nodes" ; Grokking Modern System Design · ch.16 ↗ · mục "Maintain cache servers list" (configuration service) ; Chưa có nguồn trong thư viện: 16.384 slot và ASK/MOVED của Redis Cluster không có trong sách
2) Node chết thì sao? Replication và failover cho cache nên làm thế nào?
Đúng là cache được phép mất dữ liệu. Nhưng với 4 shard và hit rate 95%, mất một shard là khoảng 6.900 đọc/s dồn thêm vào DB trong vài phút cache nóng lại.
Đánh đổi: Rẻ nhất, nhưng một máy chết có thể kéo sập DB phía sau (cache stampede).
Nguồn: Grokking Modern System Design · ch.16 Distributed Cache ↗ · mục "Improve availability" và "Find and remove limitations"
Primary ghi xong trả lời ngay rồi đẩy lệnh sang replica (Redis in Action §4.2). Vài tiến trình giám sát bỏ phiếu, đa số đồng ý thì đưa replica lên làm primary.
Đánh đổi: Write vừa ghi ở primary có thể mất khi failover; nếu mất đúng lệnh DEL thì service đọc bản cũ đến khi hết TTL.
Nguồn: Redis in Action ↗ · ch.4 · §4.2 Replication (tr. 70) ; Chưa có nguồn trong thư viện: Sentinel không có trong Redis in Action bản này
Mỗi shard có 1-2 replica ở AZ khác, replication bất đồng bộ vì đồng bộ qua AZ làm tăng độ trễ (Grokking ch.16 chọn async giữa các data center). Health checker theo đa số đưa replica mới nhất lên, tăng epoch; node cũ có epoch thấp hơn bị từ chối ghi để tránh hai primary. Node vừa khởi động lại không nhận request đến khi đồng bộ xong. Mọi key đều có TTL để giới hạn thời gian sai khi mất DEL, và client gộp các miss trùng key (request coalescing) để DB không bị dồn.
Đánh đổi: Gấp đôi số máy và phải vận hành health checker + config service; vẫn có khoảng vài giây dữ liệu có thể mất khi failover.
Nguồn: Grokking Modern System Design · ch.16 ↗ · mục "High availability" và "Consistency" (async giữa data center) ; Chưa có nguồn trong thư viện: epoch và request coalescing là thực hành chung
3) Cài đặt LRU trong một node cache thế nào để get/set vẫn O(1)?
Mỗi entry có last_access. Khi cần chỗ thì duyệt toàn bộ key để tìm cái nhỏ nhất. Với 20 triệu key mỗi lần loại là một lần quét O(N).
Đánh đổi: Dễ viết, nhưng mỗi lần đầy RAM node đứng hình hàng trăm ms.
Nguồn: Grokking Modern System Design · ch.16 Distributed Cache ↗ · mục "Linked list" (thao tác O(1) ở đầu/đuôi)
Hash map trỏ thẳng tới node trong danh sách. get: tìm trong map rồi chuyển node lên đầu. Loại: bỏ node ở đuôi. Mọi thao tác O(1), đúng như thiết kế trong Grokking ch.16.
Đánh đổi: Tốn 16 B con trỏ mỗi key; mỗi lần đọc cũng là một lần ghi vào danh sách nên khó chạy nhiều luồng mà không khóa.
Nguồn: Grokking Modern System Design · ch.16 Distributed Cache ↗ · mục "Internals of cache server" (hash map + doubly linked list)
Mỗi entry chỉ giữ đồng hồ truy cập 24 bit, không có danh sách. Khi cần loại, node lấy ngẫu nhiên khoảng 5 key, đưa vào một pool nhỏ và loại key lâu chưa dùng nhất, giống cách Redis làm. Đọc không phải sửa con trỏ nên nhanh và tiết kiệm RAM, kết quả rất gần LRU thật. Nếu có job quét nhiều key một lần làm trôi key nóng thì dùng LRU chia 2 đoạn (mới/được dùng lại) hoặc LFU. Hit rate quyết định độ trễ trung bình: 95% hit với 1 ms/20 ms cho 1,95 ms, 90% hit cho 2,9 ms.
Đánh đổi: Không chính xác tuyệt đối; phải đo hit rate thực tế để chọn chính sách (allkeys-lru, volatile-lru, LFU) cho từng loại tải.
Nguồn: Grokking Modern System Design · ch.16 ↗ · mục "High performance" (công thức EAT) ; Chưa có nguồn trong thư viện: LRU lấy mẫu của Redis, LFU, LRU chia segment không có trong sách
4) Một key bị đọc quá nhiều (hot key) và câu hỏi định tuyến: client tự tính shard hay đi qua proxy?
Service chỉ cần biết địa chỉ proxy, proxy giữ ShardMap. Nhưng thêm một hop mạng và một tầng phải scale, còn key nóng vẫn dồn về đúng một shard.
Đánh đổi: Dễ cho service, nhưng proxy thành điểm nghẽn và hot key vẫn làm sập một node.
Nguồn: Grokking Modern System Design · ch.16 Distributed Cache ↗ · mục "Cache client" và "Find and remove limitations" (hotkey)
Client giữ ShardMap và nói thẳng với node, mỗi lệnh một hop (thiết kế của Grokking ch.16). Với key đọc nhiều, client chia đọc lên primary và replica nên tải một shard giảm theo số bản sao.
Đánh đổi: Mỗi ngôn ngữ cần một thư viện đúng chuẩn; đọc từ replica có thể cũ vài ms; một key 72.000 ops/s vẫn vượt 2 node.
Nguồn: Grokking Modern System Design · ch.16 ↗ · mục "Cache client" và "Improve availability" (hot shard đọc từ replica)
Service Node/Go/Java dùng smart client; ngôn ngữ khác dùng sidecar (Envoy, twemproxy) trên localhost nên không thêm hop mạng. Client đếm tần suất key bằng count-min sketch, key vượt ngưỡng được giữ trong L1 cache trong process vài giây. Key nóng mà vẫn cần đọc từ cache cụm thì nhân bản thành key#0..key#7 trên 8 shard, client đọc ngẫu nhiên một bản, ghi thì xóa cả 8. Grokking ch.16 gợi ý nhân bản động cho key nóng như hướng xử lý.
Đánh đổi: L1 làm dữ liệu cũ thêm vài giây và mỗi pod giữ bản riêng; nhân bản key làm thao tác ghi/xóa đắt gấp 8 lần nên chỉ dùng cho key đọc rất nhiều, ít đổi.
Nguồn: Grokking Modern System Design · ch.16 ↗ · mục "Scalability" (dynamic replication cho key nóng) ; Chưa có nguồn trong thư viện: count-min sketch và sidecar proxy không có trong sách
Trong phỏng vấn
- “Tôi chia key bằng consistent hashing có virtual node, ShardMap có version trong config service để thêm node chỉ dời khoảng 1/N key.”
- “Replication bất đồng bộ là đủ cho cache; tôi chấp nhận mất vài giây ghi khi failover và giới hạn hậu quả bằng TTL.”
- “Mỗi node dùng hash map cộng LRU, thực tế dùng LRU xấp xỉ bằng lấy mẫu để tiết kiệm RAM và tránh khóa.”
- “Hot key xử lý ở phía client: L1 cache vài giây và nhân bản key, vì thêm shard không giúp một key duy nhất.”
- Dùng hash(key) % N rồi thêm node, toàn bộ cache miss cùng lúc.
- Quên rằng DB phía sau phải chịu được tải khi một shard mất, không có request coalescing.
- Set key không có TTL, mất lệnh DEL khi failover là dữ liệu cũ vĩnh viễn.
- Nghĩ thêm shard giải quyết được hot key.
Đọc thêm
Sách trong thư viện của bạn. Số chương có thể lệch nhẹ so với bản PDF.