Hacktoberfest 2026：维护者为十月标记出来的 issue，仍然开放、适合新手。 浏览 Hacktoberfest issue

Cache invalidation design

未关闭
  • 哪里不对？
#38 0 条评论 1 个 reaction 已指派 0 人 在 GitHub 查看

还没有人认领这个 Issue。

评估

难度
5/5
预计耗时
一周以上
新手友好度
30/100
Issue 类型
功能
描述清晰度
基本清楚
活跃度
停滞
技术栈
aws, go
领域
backend, cloud, distributed-systems

调研方向

该 issue 没有指出文件、测试或入口点。首先定位 Cachew 的缓存读取/删除路径以及 S3 集成，然后将其与所述的持久性和传播要求进行比较；要视为完成，需要就删除日志、位图墓碑和第二层流式处理达成一致的实现设计。

由索引模型根据 Issue 内容生成。

描述

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
主要语言
Go
星标
41
派生
14
平均合并
19 小时 28 分钟
30 天内合并 PR
3

环境准备

  • 没有 Dockerfile 或 Docker Compose 文件
  • 没有 Pull Request 模板
  • 阅读贡献指南

从这里开始

  1. 先读完整个 Issue，再读项目的贡献指南。
  2. 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
  3. Fork 仓库，在一个分支上完成修改。
  4. 提交 Pull Request，并在描述里引用这个 Issue 编号。

block/cachew 的其他 Issue

查看 block/cachew 的全部 Issue

相似的 Issue

更多 Go Issue

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。