[RFC]: Reliable per-object deletion and watermarked Bucket GC for LOCAL_DISK

## Changes proposed

### Background

Today, `MasterService::Remove` and `BatchRemove` primarily remove logical metadata from the Master, but they do not reliably propagate per-object deletion to remote `LOCAL_DISK` holders.

For the Bucket backend, multiple objects share the same `.bucket` data file, so deleting one object cannot be implemented by simply unlinking the whole file. After logical deletion, the system still needs to:

1. reliably deliver the delete intent to the correct SSD;

2. persist an object tombstone so the object cannot reappear after holder restart;

3. reclaim tombstoned dead bytes in the background;

4. prioritize reclaim when SSD usage reaches the high watermark;

5. remain correct across Master failover, holder restart, retries, and duplicate tasks.

This RFC only covers per-object deletion and space reclamation for `LOCAL_DISK` replicas in the Bucket backend through `Remove` and `BatchRemove`.

### Current behavior

A simplified failure scenario is:

```text
1. Put object A
2. A is offloaded to a remote LOCAL_DISK bucket
3. Remove(A) is called
4. Master removes the logical metadata for A
5. The holder still retains A in bucket metadata and the bucket data file
6. The holder restarts and scans persisted metadata
7. Old LOCAL_DISK state may be reloaded, while the physical bytes remain on SSD
```

Even when the object does not become user-visible again, dead bytes may remain indefinitely and cannot be reclaimed ahead of live data.

## Goals

This proposal aims to provide the following guarantees:

1. `Remove/BatchRemove` creates a delete task for each completed `LOCAL_DISK` replica that supports per-object deletion.

2. In HA + OpLog mode, delete intents and ACKs survive primary failure and standby promotion.

3. A holder sends ACK only after the tombstone has been durably persisted.

4. A delayed or duplicated delete task cannot delete a new object created with the same tenant/key.

5. A tombstoned object disappears immediately from read paths and live indexes and does not reappear after holder restart.

6. Fully dead buckets can be unlinked directly, while partially dead buckets can be reclaimed through bounded copy-on-write compaction.

7. When SSD usage reaches the high watermark, dead-byte reclaim is prioritized until usage moves toward the low watermark.

8. Physical GC does not run synchronously on the `Remove/BatchRemove` RPC path or the heartbeat critical path.

## Non-goals

This RFC does not include:

- changing `RemoveAll` or `RemoveByRegex`;

- adding per-object physical deletion to FilePerKey, OffsetAllocator, DFS, NoF, P2P, or other backends;

- changing the existing eviction policy;

- implementing the disconnected/grace state machine for LOCAL_DISK warm re-adoption;

- implementing drain migration;

- introducing a generic workflow/task scheduler;

- adding multiple parallel GC workers per backend;

- performing unbounded global bucket bin packing;

- synchronously copying bucket data inside `Remove/BatchRemove`.

## Design overview

```text
Remove / BatchRemove
│
▼
Master creates durable local-delete intent
│
▼
holder fetches bounded tasks
│
▼
validate storage identity, mount epoch, and object incarnation
│
▼
persist bucket tombstone
│
▼
holder sends ACK
│
▼
Master removes pending task after durable ACK
│
▼
background Bucket GC reclaims dead bytes
```

A successful `Remove/BatchRemove` does not mean SSD space has already been synchronously reclaimed. It means the logical deletion and the delete intent supported by the current deployment mode have been accepted.

## 1. Object identity and storage identity

The design uses four identities with different lifetimes:

| Identity | Lifetime | Purpose |
| --- | --- | --- |
| `client_id` | holder process lifetime | identifies the current RPC / heartbeat owner |
| `local_disk_segment_id` | persisted SSD directory lifetime | routes tasks to the same persistent storage |
| `mount_epoch` | changes when ownership changes | fences stale holder processes |
| `ObjectIncarnation` | logical object version lifetime | prevents stale tasks from deleting a newly recreated key |

Each Bucket data directory persists:

```text
.mooncake_local_disk_segment_id
```

A new immutable `ObjectIncarnation` is generated for every newly created logical object and propagated through:

- Master metadata;

- primary/standby snapshots;

- OpLog;

- offload tasks;

- LOCAL_DISK descriptors;

- bucket metadata;

- local-delete tasks.

Fetch and ACK validate:

```text
client_id
local_disk_segment_id
mount_epoch
delete capability
```

Deletion also validates the tenant-scoped key and `ObjectIncarnation`.

## 2. Delete task lifecycle

The Master maintains a bounded pending-task registry.

Before mutating the logical object state, the Master reserves enough task slots for all affected `LOCAL_DISK` replicas. If reservation fails, the corresponding Remove fails closed instead of deleting logical metadata without recording the required physical-delete work.

```mermaid
stateDiagram-v2
[*] --> Reserved: reserve before Remove
Reserved --> Pending: REMOVE intent durable
Reserved --> [*]: Remove fails, release reservation
Pending --> Pending: Fetch or response lost
Pending --> Pending: RetryableFailure
Pending --> AckPending: tombstone durable
AckPending --> Pending: ACK not durable
AckPending --> [*]: ACK durable
```

Key rules:

- Fetch does not remove pending tasks.

- No ephemeral `inflight` state is required for correctness.

- Lost Fetch responses, holder restart, and repeated Fetch only cause redelivery.

- A task is removed only after durable ACK.

- Duplicate tasks, duplicate tombstones, and duplicate ACKs must be idempotent.

- The same object incarnation on the same storage identity produces at most one pending task.

- `BatchRemove` keeps its current per-key result semantics rather than becoming a batch-wide transaction.

## 3. HA durability

In HA + OpLog mode, this adds:

- a versioned `REMOVE` payload containing object incarnation and delete intents;

- a versioned `LOCAL_DELETE_ACK` operation;

- primary durable callbacks;

- standby replay;

- pending tasks in primary and standby snapshots.

The publication order is:

```text
REMOVE intent durable
↓
task becomes visible to holder
```

The ACK order is:

```text
LOCAL_DELETE_ACK durable
↓
remove task from primary pending registry
```

Unknown or corrupted versions must fail closed:

- they must not be interpreted as legacy REMOVE;

- they must not be silently skipped;

- they must not advance standby sequence state.

## 4. Holder-side durable tombstone

The holder fetches a bounded batch and groups tasks by bucket.

For each affected bucket:

1. convert the user key into the tenant-scoped storage key;

2. locate the object and validate the incarnation;

3. copy bucket metadata;

4. set the record to `tombstoned=true`;

5. write a temporary `.meta` file in the same directory;

6. `fsync` the temporary file;

7. atomically rename it over the committed `.meta`;

8. `fsync` the parent directory;

9. remove the exact incarnation from the live index;

10. ACK terminal tasks.

Task results are:

| Result | Meaning | ACK |
| --- | --- | --- |
| `Removed` | tombstone was durably persisted | yes |
| `AlreadyRemoved` | the same incarnation was already tombstoned | yes |
| `StaleVersion` | the object is absent or belongs to another incarnation | yes |
| `RetryableFailure` | file write, fsync, rename, or similar operation failed | no |

`StaleVersion` must only be returned after confirming that the object is truly absent or belongs to a different incarnation.

If GC relocates the same incarnation from a source bucket to a replacement bucket while deletion is in progress, the delete path must re-resolve the current mapping and retry the tombstone against the replacement instead of treating an inactive source bucket as terminal.

## 5. Watermarked Bucket GC

Each `BucketStorageBackend` runs at most one background GC worker.

Under normal conditions, a bucket becomes a GC candidate only when its dead-byte ratio reaches a configurable threshold.

When SSD usage reaches the existing high watermark:

- the normal dead-byte ratio threshold is bypassed;

- buckets containing dead bytes are prioritized;

- reclaim continues until usage moves toward the low watermark, no candidates remain, or an error occurs;

- when no reclaimable dead bytes remain, the existing live-bucket eviction fallback is preserved.

GC behavior:

- fully dead buckets are deleted without creating a replacement;

- partially dead buckets use copy-on-write replacement;

- only live and non-tombstoned records are copied;

- live records are copied using a fixed-size streaming buffer;

- replacements remain subject to existing bucket key/count and size limits;

- source files are deleted only after old readers have drained;

- physical storage accounting decreases only after files are actually removed;

- GC never copies data synchronously on the Remove RPC path or heartbeat critical path.

## 6. Bounded multi-bucket merge

Rewriting only one bucket at a time is simpler, but it cannot consolidate multiple low-utilization buckets and may leave many small files and underutilized buckets after dead-byte reclaim.

This proposal allows bounded multi-source compaction with the following hard limits:

- at most 8 source buckets per GC round;

- sources are locked in bucket-ID order;

- one GC worker per backend;

- the replacement must obey existing bucket key/count and size limits;

- copying uses a fixed-size buffer;

- one GC intent describes the selected sources and a single target.

This is not unbounded bin packing and does not globally reorganize the SSD.

## 7. GC crash recovery

The holder uses a local intent file:

```text
.bucket_gc_intent
```

This records which file set is authoritative while source buckets are being replaced.

### PREPARED

The replacement has not been committed yet:

```text
sources are authoritative
uncommitted target must be removed or ignored
```

Recovery:

1. keep the source buckets;

2. remove the uncommitted target;

3. clear the intent;

4. retry GC later.

### COMMITTED

The replacement has been fully persisted and is now authoritative:

```text
target is authoritative
sources are retired files waiting for cleanup
```

Recovery:

1. validate the target;

2. keep the target;

3. remove the sources;

4. clear the intent.

A missing or corrupted committed target fails closed.

The three durability layers serve different purposes:

- OpLog records which objects must be deleted;

- tombstones record which holder-local objects are logically deleted;

- GC intent records whether source or replacement files are authoritative.

### Runtime cleanup limitation

If GC reaches `COMMITTED` but source unlink, directory fsync, or reader drain fails or times out:

- the replacement target remains authoritative;

- deleted objects do not become visible again;

- physical source cleanup may remain incomplete;

- later GC may require holder restart and recovery before reclaim continues.

This is a space-reclamation liveness limitation rather than an object-consistency violation. Runtime retry of committed intents can be added as follow-up work.

## 8. Guarantees by deployment mode

| Deployment mode | Delete-task guarantee |
| --- | --- |
| HA + OpLog | REMOVE intents and ACKs are recoverable through OpLog and snapshots |
| non-HA | pending tasks are in memory; Master crash relies on holder remount/reconciliation |
| HA without OpLog | the initial version does not provide reliable asynchronous physical deletion |

## 9. Compatibility and rollout

- Legacy bucket metadata is read as zero incarnation with `tombstoned=false`.

- The new snapshot reader remains compatible with the previous snapshot version.

- Backends that do not advertise the tombstone capability do not receive local-delete tasks.

- Reliable deletion requires participating primary, standby, and Bucket holders to understand the corresponding RPC, OpLog, snapshot, and capability semantics.

- The current implementation uses a persistent LOCAL_DISK identity marker for storage fencing and task routing.

- For an existing non-empty LOCAL_DISK directory without this marker, the current implementation fails closed unless the directory is explicitly adopted by the administrator.

The final rollout policy for legacy unmarked directories is intentionally left open for review. Possible directions include keeping explicit adoption or allowing a compatibility mode that mounts legacy directories without enabling the new reliable-deletion capability.

Similarly, the final default policy for background Bucket GC should be decided separately from the deletion-correctness protocol.

## 10. Capacity and permanently lost storage

Pending tasks do not use an automatic TTL because silently expiring them would violate the deletion guarantee.

If a storage identity is permanently lost:

- its pending tasks remain in the registry;

- when the registry reaches its configured capacity, new Remove operations may fail closed;

- the initial implementation does not automatically determine whether a storage device is permanently gone.

Possible follow-up work includes:

- explicit storage retirement;

- administrator force-drop;

- audit logs;

- pending task count/age metrics;

- per-storage task limits.

## 11. Performance boundaries

- `Remove/BatchRemove` does not copy bucket data.

- Heartbeat work is limited to bounded Fetch, tombstone, ACK, and GC wakeup.

- Each backend has one GC worker.

- Each GC round uses at most 8 source buckets.

- Copying uses a fixed-size buffer.

- Long-running data copies and reader draining do not hold the global bucket mutex.

- Reclaimable bytes are maintained through O(1) accounting.

Bucket GC still introduces additional live-byte copy I/O when reclaiming partially dead buckets.

Representative SSD validation should measure:

- Get p99;

- GC throughput;

- write amplification;

- RSS;

- interference with foreground reads, writes, and offload.

The initial implementation provides the GC mechanism and bounds its work. Whether normal ratio-based GC should be enabled by default, enabled only under storage pressure, or initially remain opt-in is a rollout-policy question rather than part of the deletion correctness contract.

## 12. Relationship to existing work

- #2676 handles whole-store cleanup for `RemoveAll`; this RFC addresses per-object `Remove/BatchRemove`.

- #2306 and #2777 address LOCAL_DISK warm re-adoption. This RFC does not implement the disconnected/grace state machine, but it shares stable storage identity and mount plumbing.

- If #2777 lands first, this implementation should rebase and reuse its identity/mount foundation. If this foundation lands first, #2777 may reuse the marker, mount epoch, and descriptor fields.

- #3085 handles LOCAL_DISK migration during drain; source-disk cleanup may later reuse this delete-task protocol.

- #2827 covers same-key SSD races. `ObjectIncarnation` prevents stale delete tasks from deleting a newly recreated key, but this RFC does not claim to solve every offload race discussed there.

- If #2901 lands first, the new tests should be rebased into the updated semantic test structure.

## 13. Implementation scope

This RFC proposes implementing the feature as one end-to-end change rather than splitting it into stacked PRs.

Reliable per-object `LOCAL_DISK` deletion depends on the following pieces working together:

```text
ObjectIncarnation
↓
stable LOCAL_DISK identity / mount fencing
↓
durable delete intent
↓
holder Fetch / durable tombstone / ACK
↓
background Bucket GC
↓
crash recovery
```

These components jointly form the complete deletion lifecycle.

For example:

- without `ObjectIncarnation`, a delayed task may delete a newly recreated object with the same tenant/key;

- without durable delete intents, pending deletions may be lost after Master failover;

- without holder-side tombstones, logical deletion is not durably reflected on SSD;

- without GC, tombstoned dead bytes cannot be physically reclaimed;

- without crash recovery, a holder cannot reliably determine whether source or replacement buckets are authoritative after a failure.

The implementation is therefore intended to be submitted and reviewed as one complete LOCAL_DISK deletion lifecycle.

The PR and implementation are organized by subsystem—identity, Master deletion protocol, holder tombstone, GC, and recovery—to keep review manageable while preserving an end-to-end implementation.

## 14. Questions for maintainers

1. What default rollout policy would be preferred for Bucket GC: always-on ratio-based GC, opt-in normal GC with automatic high-watermark reclaim, or another policy?

2. Is there a preferred reuse or merge order between the stable LOCAL_DISK identity work here and #2777?

- I have searched existing issues and pull requests to avoid submitting a duplicate proposal.

### Before submitting a new issue...

- [x] Make sure you already searched for relevant issues and read the [documentation](https://kvcache-ai.github.io/Mooncake/)

Start by tracing MasterService::Remove and BatchRemove, then inspect BucketStorageBackend and the LOCAL_DISK holder paths. Read how .meta files, bucket metadata, live indexes, and .bucket_gc_intent are currently handled. Done means the proposed durable delete-task, tombstone, ACK, failover, restart, and watermarked GC guarantees are implemented without synchronous RPC-path reclamation.

Written by the indexing model from the issue text.