Hacktoberfest 2026: những issue maintainer đã đánh dấu cho tháng Mười, đang mở và phù hợp người mới. Xem issue Hacktoberfest

Cache invalidation design

Đang mở
  • Có gì không ổn?
#38 0 bình luận 1 reaction 0 người được giao Xem trên GitHub

Chưa có ai nhận issue này.

Đánh giá

Độ khó
5/5
Thời gian dự kiến
Hơn một tuần
Mức phù hợp với người mới
30/100
Loại issue
Tính năng
Độ rõ ràng
Khá rõ ràng
Mức độ hoạt động
Đình trệ
Công nghệ
aws, go
Lĩnh vực
backend, cloud, distributed-systems

Hướng nghiên cứu

Issue không nêu tên tệp, bài kiểm thử hay các điểm vào. Hãy bắt đầu bằng cách xác định các đường dẫn đọc/xóa cache của Cachew và phần tích hợp S3, sau đó đối chiếu chúng với các yêu cầu đã nêu về độ bền và khả năng lan truyền; để được xem là hoàn tất, cần có thiết kế triển khai đã được thống nhất cho nhật ký xóa, các bitmap tombstone và streaming của tầng hai.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

Cache Invalidation in Cachew

This is a one-pager for cache invalidation in cachew.

We need a way to reliably remove objects from the cache, across replicas and tiers. Our requirements are that a single API call will delete an object from all caches. Deletion need not be immediate but it must be guaranteed.

Architecture

At the top level are the tier one replicas. Except for S3, these are stateless and do not coordinate at all.

S3 <- Disk <- Tier1 Replica1  |
S3 <- Disk <- Tier1 Replica2  +-- Tier1 Load Balancer
S3 <- Disk <- Tier1 Replica3  |

Tier two caches run on each worker node, backed by disk then the upstream tier one load balancer endpoint:

Worker1
Tier1 LB <- Disk <- Tier2 Service <- Apps

Worker2
Tier1 LB <- Disk <- Tier2 Service <- Apps

A delete request can arrive at any node, tier one or tier two.

Problems

The first problem is that the tier one replicas don't communicate. A delete request arriving at one replica must be propagated to the others.

The second problem is that deletes arriving at tier one must also propagate to all tier two nodes.

Solution

Deletion Log

We use S3 as a durable, append-only log of deletion requests. The log is partitioned by day for efficient listing:

deletes/2025-01-15/43200000000-0.json
deletes/2025-01-15/43200000123-1.json
deletes/2025-01-16/00000012345-2.json

Each filename is <microseconds-since-2025>-<node-id>. This ensures uniqueness: a node can only collide with itself, and self-collision at microsecond resolution is effectively impossible.

Each file contains the key to delete:

{"key": "5d0c39b872a86528c12ddd96410dbb8b06c2379dc11a3b44a25b8472bec11e77"}
Writing a Deletion

When a delete request arrives:

  1. Generate the filename as <microseconds-since-2025>-<node-id>
  2. Write to S3 with If-None-Match: * header
  3. On 412 (collision with self, extremely rare), increment microsecond and retry
  4. Return success to caller once S3 write succeeds

The delete is now guaranteed to be processed by all replicas.

Processing Deletions and Tombstone Lookups

Each replica maintains a single roaring bitmap that serves as both the processing cursor and the tombstone set. On startup, the replica scans the entire deletion log and populates the bitmap.

The bitmap maps each deletion entry to a 64-bit integer:

bitmap_key = (microseconds_since_2025 * max_nodes) + node_id

Where max_nodes is a fixed constant (e.g., 256). Roaring bitmaps handle sparse 64-bit keyspaces efficiently — roughly 8 bytes per deletion.

Deletes Memory
100,000 ~800 KB
1,000,000 ~8 MB
10,000,000 ~80 MB

Periodically, each replica:

  1. Scans the current day's partition and the previous day's partition (to handle clock skew)
  2. Parses each filename to extract the timestamp and node ID
  3. Computes the bitmap key and skips if already set
  4. Deletes the corresponding cache key from local disk
  5. Sets the bit in the bitmap and persists it

On every cache read, the replica checks the bitmap. If the key's bitmap index is set, the replica returns a cache miss. This prevents serving deleted content even if the local disk cache hasn't been purged yet.

Deletions are idempotent, so reprocessing an entry is harmless.

Tier Two Propagation

Tier two replicas maintain their own bitmap on local disk. They connect to an SSE endpoint on the tier one load balancer, sending their last-seen event ID. Tier one streams back deletion entries from that point forward.

On startup, the tier two node loads its bitmap from disk, then connects to tier one and catches up. The bitmap serves the same dual purpose: tracking processed deletions and providing tombstone lookups.

If a tier two node restarts, it resumes from its last persisted bitmap state.

Failure Modes

Failure Outcome
S3 write fails API returns error, caller retries
Replica crashes mid-processing Restarts, scans log, rebuilds bitmap
Replica offline for extended period Catches up by scanning all partitions
Network partition Resumes processing when connectivity restored

Guarantees

  • Every deletion is durably logged before the API returns success
  • Every replica eventually processes every deletion
  • Bitmap is updated only after successful local deletion
  • Log entries are never garbage collected
  • Tombstone lookups prevent serving deleted content even before local purge
Ngôn ngữ chính
Go
Star
42
Fork
14
Merge trung bình
11 giờ 59 phút
Pull request đã merge (30 ngày)
5

Chuẩn bị môi trường

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của block/cachew

Tất cả issue của block/cachew

Issue tương tự

Thêm issue về Go

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.