GC Sweep & Eviction

[flyingrobots]

Migrated from Method backlog

This issue was created from a legacy filesystem backlog card. GitHub Issues are now the live work tracker; repository docs remain Method evidence.

Source backlog: docs/method/backlog/cool-ideas/PLATFORM_deep-storage-gc-sweep-eviction.md
Original lane: cool-ideas
Original legend: PLATFORM

Original backlog card

Milestone: Deep Storage | Priority: P2

Status: active cool idea. crates/echo-cas currently has synchronous
BlobStore and in-memory MemoryTier only; no DiskTier, TieredStore,
listing/metadata API, deletion path, GcSweep, EvictionPolicy, or
GcRunner exists yet. This remains operational as the GC follow-up after
disk tier and enumeration support land.

GC Sweep & Eviction

Pin/unpin lifecycle management with mark-sweep reachability and eviction policies for managing blob lifetime.

---

T-5-2-1: Mark-sweep reachability analysis

User Story: As a developer, I want the CAS to identify unreachable blobs so that disk space can be reclaimed.

Requirements:

• R1: GcSweep::mark(roots: &[BlobHash]) traverses from pinned roots and marks all reachable blobs.
• R2: Reachability follows blob references embedded in a configurable RefExtractor trait: fn extract_refs(blob: &[u8]) -> Vec<BlobHash>.
• R3: GcSweep::sweep() returns the set of hashes that are stored but not marked (garbage).
• R4: Sweep does NOT delete -- it returns candidates. Deletion is a separate explicit step.

Acceptance Criteria:

• AC1: A blob reachable from a pinned root is never in the sweep set.
• AC2: An unpinned blob with no inbound references appears in the sweep set.
• AC3: Transitive reachability: A -> B -> C, only A is pinned; B and C are marked as reachable.
• AC4: sweep() on an empty store returns an empty set.

Definition of Done:

• Code reviewed and merged
• Tests pass (CI green)
• Documentation updated (if applicable)

Scope: Mark-sweep algorithm, RefExtractor trait, sweep candidate collection.
Out of Scope: Actual deletion/eviction (T-5-2-2). Incremental/generational GC. Concurrent marking.

Test Plan:

• Goldens: N/A (set-based output, order-independent).
• Failures: RefExtractor returns a hash that does not exist in the store (treated as already collected, not an error).
• Edges: Cycle: A -> B -> A (both reachable if either is pinned). Blob that references itself. 0-ref blob that is pinned (reachable).
• Fuzz/Stress: Property test: for any random DAG of blobs, sweep set + reachable set = full store set.

Blocked By: T-5-1-1
Blocking: T-5-2-2

Est. Hours: 5h
Expected Complexity: ~200 LoC

---

T-5-2-2: Eviction policy and background sweep task

User Story: As an operator, I want the CAS to automatically evict cold unpinned blobs so that memory and disk usage stay bounded.

Requirements:

• R1: EvictionPolicy enum: Lru, SizeBased(max_bytes), AgeBased(max_age).
• R2: GcRunner struct accepts a TieredStore + EvictionPolicy + RefExtractor.
• R3: GcRunner::run_sweep() performs mark, sweep, then evicts candidates according to the policy (demote from memory, or delete from disk for AgeBased/SizeBased).
• R4: GcRunner can be driven manually (run_sweep()) or spawned as a background tokio::task with a configurable interval.
• R5: Eviction never removes pinned blobs regardless of policy.

Acceptance Criteria:

• AC1: After run_sweep() with SizeBased(1024), total stored bytes are at or below 1024 (unpinned blobs evicted by LRU within the size policy).
• AC2: Pinned blobs survive eviction even when over budget.
• AC3: Background task runs at the configured interval and produces a sweep report.
• AC4: Metrics: sweep duration, blobs evicted count, bytes freed.

Definition of Done:

• Code reviewed and merged
• Tests pass (CI green)
• Documentation updated (if applicable)

Scope: Eviction policies, GcRunner, background sweep, metrics.
Out of Scope: Distributed GC coordination. Multi-process locking on DiskTier. Custom policy plugins.

Test Plan:

• Goldens: N/A (behavioral).
• Failures: Sweep with no garbage (returns zero evictions). Sweep when all blobs are pinned (zero evictions).
• Edges: Exactly at budget boundary. Single blob store. Policy switch between sweeps.
• Fuzz/Stress: Concurrent puts during sweep (sweep must not cause data races or double-free).

Blocked By: T-5-2-1, T-5-1-2
Blocking: none

Est. Hours: 6h
Expected Complexity: ~300 LoC

[coderabbitai]

🔗 Related PRs

#121 - rmg-core/scheduler: fail-fast drain; u32 radix histogram; keep PendingTx private [merged]
#263 - feat(echo-cas): content-addressed blob store (Phase 1) [merged]
#371 - feat(core): advance v0.1 contract evidence and retention [merged]
#385 - docs(backlog): two follow-ups from the 2026-05-30 merge session [merged]
#388 - docs(method): add backlog cards and hook failure note [merged]

---

📝 Issue Planner

_{Check the box below or use the @coderabbitai plan command to generate an implementation plan and prompts that you can use with your favorite coding assistant.}

• Create Plan

---

🧪 Issue enrichment is currently in open beta.

You can configure auto-planning by selecting labels in the issue_enrichment configuration.

To disable automatic issue enrichment, add the following to your .coderabbit.yaml:

issue_enrichment:
  auto_enrich:
    enabled: false

💬 Have feedback or questions? Drop into our discord!