[RFC]: Introduce a Masterless Rust Store into Mooncake

### Changes proposed

- **Status:** Draft for discussion
- **Target:** `kvcache-ai/Mooncake`
- **Component:** `mooncake-store/store-rs`
- **Proposed PR prefix:** `[Store]`

cc: @zxpdemonio @Bo-Vincent @YiXR @XucSh @stmatengss

## Summary

This RFC proposes upstreaming Store-RS as an opt-in, Rust-native, masterless implementation of Mooncake Store.

Store-RS removes the dedicated store master from the normal object request path. Clients discover live peers through durable metadata, select route authorities with embedded weighted rendezvous hashing, allocate storage on participating peers, and move payloads through Mooncake Transfer Engine or TENT. Redis or etcd remains the durable coordination plane for leases, cluster policy, lifecycle state, and tenant quota accounting; “masterless” does not mean “metadata-free.”

The first release operates within a trusted Store-RS runtime boundary. Its tenant guarantees cover namespace correctness, resource accounting, and noisy-neighbor controls.

The first upstream scope includes:

- the in-memory masterless object-store capabilities enumerated below;
- routing, membership, allocation, replication, reclaim, and lifecycle handling;
- Rust and Python client surfaces needed to use that path;
- tenant and optional domain namespaces;
- hard tenant isolation through authoritative quota accounting and tenant-local eviction;
- soft tenant isolation through local request fairness, batch/inflight shaping, and placement preferences;
- DRAM-first cold tier storage with asynchronous offload, cold-only routes, and restore-on-read;
- runtime metrics, tracing, health, and diagnostic endpoints.

## Scope Boundaries

The initial scope of Mooncake Store-RS is defined by the following boundaries:

1. Store-RS is an additional opt-in store implementation alongside the existing default Mooncake Store.
2. The implementation lives in `mooncake-store/store-rs` as its own Cargo workspace.
3. The default masterless route mode is `EmbeddedWrh`; `MetadataOnly` remains a bring-up and debugging mode.
4. The first release supports tenant and optional domain isolation.
5. Tenant policy is supplied by runtime configuration and bootstrapped into versioned metadata records.
6. Cold tier targets are supplied by runtime configuration and participate in metadata-backed capacity accounting, offload, restore, and reclaim.

## Motivation

The current Mooncake Store architecture uses a dedicated master service to manage object metadata and storage allocation. The data path already moves bytes directly between clients, but object operations depend on the master control path.

Store-RS explores a different operating point:

- remove a dedicated master from steady-state object operations;
- keep route lookup and compare-and-swap on a peer authority mesh;
- keep allocation and reclaim responsibility with storage-owning runtimes;
- use local snapshots and exact indexes rather than backend scans on request paths;
- preserve Mooncake Transfer Engine and TENT as the data plane;
- make tenant isolation and runtime observability first-class rather than deployment-specific add-ons.

This is useful for deployments that value peer-based control, independent storage runtimes, explicit lifecycle transitions, and the ability to scale route and allocation ownership with the clients themselves.

## Terminology

- **Runtime:** A Store-RS process or embedded client with a stable identity and a metadata-assigned epoch.
- **Storage owner:** A runtime that contributes registered memory and owns local allocation and reclaim state.
- **Route authority:** A runtime selected for an object key by weighted rendezvous hashing and responsible for route lookup or compare-and-swap.
- **Metadata backend:** Redis, etcd, or an in-memory backend used for durable coordination and tests.
- **Hard isolation:** Namespace and resource-accounting correctness among trusted runtimes: no cross-tenant visibility through supported APIs and no quota over-admission through the authoritative quota protocol.
- **Soft isolation:** Per-runtime scheduling and placement controls that reduce noisy-neighbor effects.
- **Tenant root:** The tenant-level scope at which strict quota state is authoritative in the first release.

## Goals

### Masterless object-store path

- Support put, get, remove, existence, size, and route queries.
- Support batch operations and registered-buffer I/O.
- Support local and remote placement, replication, and replica failover.
- Support runtime membership, leases, epochs, graceful drain, handoff, and storage resizing.
- Keep steady-state route lookup and route publication off the metadata backend in `EmbeddedWrh` mode.
- Reuse Mooncake Transfer Engine and TENT instead of introducing another data plane.

### Multi-tenant isolation

- Give each object a deterministic tenant-scoped identity.
- Permit an optional domain below the tenant.
- Prevent reads, writes, route lookup, local caches, and accounting from crossing tenant or domain boundaries.
- Enforce tenant-root byte and object quotas with metadata-authoritative signed accounting operations.
- Evict only objects belonging to the tenant that needs quota recovery.
- Apply per-tenant request fairness, batch shaping, inflight-byte limits, and placement preferences.
- Apply these properties within the trusted Store-RS runtime boundary.

### Hot/cold storage

- Keep DRAM replicas as the normal serving tier.
- Represent durable cold backing separately from hot replicas in object routes.
- Materialize cold backing asynchronously after a successful DRAM write.
- Evict the last hot replica only after the matching cold backing is materialized and readable.
- Restore from cold backing on a hot miss and re-promote into DRAM best-effort.
- Support runtime-configured SSD and NFS targets with bounded capacity, queueing, staging, and retry behavior.
- Reclaim superseded cold objects after overwrite or delete becomes authoritative.

### Operability

- Export Prometheus metrics for requests, routes, metadata, transport, allocation, eviction, replication, membership, process state, and tenant quota outcomes.
- Export cold device capacity/health plus offload, restore, staging, backpressure, reclaim, and backend I/O metrics.
- Export structured tracing for API, control-plane, data-plane, and metadata stages.
- Provide health, statistics, breakdown, and tracing-control endpoints from the runtime process.
- Keep object keys and other high-cardinality values out of Prometheus labels.

### Upstream maintainability

- Preserve clear crate and module ownership boundaries.
- Keep all list-style APIs bounded, paginated, or backed by maintained indexes.
- Keep the default upstream build free from a Rust requirement unless Store-RS is enabled.
- Establish one explicit source-of-truth and synchronization policy before the first implementation PR is merged.

## Proposed Architecture

```mermaid
graph LR
App[Application] --> Client[StoreClient]
Client --> Route[RouteOperations]
Client --> Alloc[Allocator]
Client --> Control[Peer control plane]
Client --> Transport[TE / TENT]
Client --> Cold[Cold tier coordinator]
Client --> Obs[Metrics and tracing]

Route --> Authorities[WRH route authorities]
Alloc --> Owners[Storage owners]
Control --> Authorities
Control --> Owners
Transport --> Owners
Cold --> Backends[SSD / NFS backends]
Owners --> Cold

Client -. leases / quota / policy .-> Metadata[Redis / etcd]
Authorities -. leases / policy .-> Metadata
Owners -. segments / lifecycle .-> Metadata
Cold -. devices / capacity / usage .-> Metadata
```

### Component responsibilities

| Component | Responsibility | Request hot path |
| --- | --- | --- |
| `mooncake-store-core` | Shared identities, routes, leases, tenant policy, quota contracts, cold backing records, and public traits | Types only |
| `mooncake-metadata` | Redis, etcd, and in-memory coordination; atomic tenant quota and cold device capacity state | No in normal `EmbeddedWrh` routing, except quota and cold lifecycle operations; yes in `MetadataOnly` mode |
| `mooncake-store-route` | Local authority tables, WRH authority selection, route lookup/CAS, mirroring, and repair | Yes |
| `mooncake-transport-sys` | Dynamic FFI bindings and native shims for TE/TENT | Yes |
| `mooncake-transport` | Safe Rust transport wrapper | Yes |
| `mooncake-store-transport-core` | Shared client/transport contracts | Yes |
| `mooncake-store-client` | Public API, membership snapshots, placement, allocation, replication, reclaim, tenant enforcement, cold offload/restore, and observability | Yes |
| `mooncake-store-py` | Python native binding and Store-RS-specific entry points | API boundary |
| `mooncake-tensor` | Tensor layout and range planning used by the Python client | Optional request path |
| `mooncake-store-test-utils` | Test fixtures and fake transports/backends | No |

### Hot-path invariant

In normal `EmbeddedWrh` operation, steady-state get, put, remove, route lookup, and allocation must not perform an unbounded metadata operation or a full namespace scan.

- Membership is read from a locally maintained live-client snapshot.
- The snapshot is refreshed asynchronously from metadata leases; metadata remains the durable membership source but is not queried by each object operation.
- Route authorities are selected from that snapshot using weighted rendezvous hashing.
- Route reads and CAS operations use peer control-plane RPC.
- Storage allocation uses exact runtime and segment identities.
- Owner-wide route enumeration is paginated and backed by an owner-to-key index.
- Tenant policy is cached per tenant root and refreshed outside the normal request path.
- Cold device placement reads a bounded cached device view; background workers perform capacity accounting and backend I/O.

Strict quota admission is the deliberate exception: when a tenant quota is configured, writes execute an atomic reservation/finalize/abort protocol against the metadata authority. The object data path and route lookup path remain peer-based.

## Route and Data Paths

### Route control

The default `EmbeddedWrh` mode ranks compatible live route-capable runtimes for each object key.

- The highest-ranked runtime is the primary CAS authority.
- Additional top-ranked runtimes mirror the route.
- Reads may query lower-ranked authorities when the mirrored set does not resolve the key.
- Route repair is asynchronous and does not turn metadata into the route hot path.

`MetadataOnly` stores routes directly in Redis or etcd for bring-up, debugging, and compatibility testing. `EmbeddedWrh` is the normal performance mode.

### Route consistency and failure model

The first release uses a fenced single-writer protocol per logical route shard. It prefers correctness over write availability during partitions.

- Object keys map deterministically to a fixed number of logical route shards.
- Metadata stores one versioned shard-authority record containing the membership generation, ranked authority set, current primary, lease expiry, and monotonically increasing fencing token.
- The highest-ranked compatible runtime may acquire or renew the shard lease. Lease acquisition and failover use metadata CAS, but normal object CAS operations do not.
- Only the current fenced primary accepts route CAS. Secondary authorities reject writes; callers never fall through to a secondary writer merely because the primary is slow or unreachable.
- Every route read and CAS request carries the caller's shard membership generation and fencing token.
- A route version is the ordered pair `(fencing_token, primary_sequence)`. A primary increments its local sequence for each applied mutation under that token.
- The primary synchronously mirrors an applied route mutation to every authority in the shard's current top-k set before reporting success. A partial mirror returns an indeterminate failure and is repaired before the next mutation for that key.
- The generation lease is a read and write lease for the complete authority set. Every authority uses a conservative local deadline and stops serving authoritative reads or writes when that lease expires.
- An authority that observes a request-generation mismatch returns `stale_generation` with its newest known generation/token instead of returning route data. The client refreshes membership and retries before accepting a route.
- Reads query only the current generation's read-valid authorities, reject records from older fencing tokens, select the highest valid version, and repair missing copies.
- A membership transition receives a new fencing token and becomes writable only after the new authority set has imported the highest route state from the previous generation. If that state cannot be established safely, the shard remains unavailable.
- Every old-generation authority stops serving reads and writes before its locally conservative lease deadline. A replacement cannot acquire a higher fencing token until metadata considers the old lease expired.
- Runtime epochs separately fence stale process incarnations inside one authority generation.

```mermaid
sequenceDiagram
participant Client
participant Metadata
participant Primary as Fenced primary
participant Mirrors as Route mirrors

Client->>Client: Read cached generation and fencing token
Client->>Primary: CAS(generation, token, expected, next)
alt Stale generation
Primary-->>Client: stale_generation
Client->>Metadata: Refresh shard generation
Metadata-->>Client: Generation, fencing token, authority set
Client->>Primary: Retry CAS
end
Primary->>Primary: Validate lease and apply mutation
loop Every mirror in the current top-k set
Primary->>Mirrors: Replicate fenced route version
Mirrors-->>Primary: Acknowledge
end
Primary-->>Client: CAS applied
```

This protocol prevents two authorities from acknowledging concurrent mutations for the same key and prevents a stale client from accepting an old-generation read after rollover. During a partition, authorities lose read/write eligibility when their generation lease expires; the side without the fenced primary cannot write, and a new primary is not activated without a safe state transfer. Equal-version/different-value records are protocol corruption: reads fail conservatively, emit a conflict metric, and do not choose by arrival order.

### Write path

1. Resolve the tenant/domain object identity and effective policy.
2. Reserve the per-object accounting operation and tenant quota when a hard quota is configured.
3. Select storage owners and reserve local or remote segment space.
4. Transfer the payload through TE/TENT.
5. The fenced primary atomically claims `Pending -> Publishing`, then publishes the new route and accounting operation ID with CAS and synchronous mirroring.
6. Finalize the accounting operation and schedule obsolete replicas for reclaim.
7. Abort and release allocations only while the accounting operation is still `Pending`; a `Publishing` timeout is indeterminate and goes through reconciliation.

The user-visible write succeeds only after route publication and quota finalization succeed.

### Read path

1. Resolve the tenant/domain object identity.
2. Read the route from the authority mesh.
3. Prefer a healthy local replica when available; otherwise select a remote replica.
4. Transfer into an owned or caller-registered buffer.
5. Report a best-effort access hit to the storage owner for eviction quality.

### Delete and reclaim

- Delete reserves a signed accounting operation, then publishes a fenced tombstone carrying that operation ID before quota is refunded.
- Replica memory is reclaimed after the route no longer references it.
- Duplicate cleanup is idempotent.
- The tombstone remains until delete accounting is finalized and its bounded retention window expires.
- Owner-wide reconciliation is bounded and must not infer absence from a partial scan.

## Hot/Cold Storage

### Route model

DRAM remains the serving tier. `ObjectRoute.replicas` contains only hot replicas that can be read directly through TE/TENT. The route contains at most one active cold backing for its current logical content, represented as a tagged state:

```text
ActiveColdBacking::PendingOffload {
cold_operation_id,
content_operation_id,
owner,
cold_tier_id,
expected_length,
expected_checksum
}

ActiveColdBacking::Materialized {
cold_operation_id,
content_operation_id,
owner,
cold_tier_id,
object_locator,
length,
checksum
}
```

This separation keeps hot serviceability distinct from cold durability. A cold-only object has an active route with `replicas = []` and a materialized active cold backing.

Obsolete locators are tracked independently from the active route in durable, indexed reclaim records:

```text
ColdReclaimRecord {
reclaim_operation_id,
content_operation_id,
cold_operation_id,
cold_tier_id,
object_locator,
length,
state
}
```

One route can therefore describe the new content's pending or materialized backing while an old locator proceeds through reclaim.

Each route carries two distinct identities:

- the accounting/content operation ID identifies the logical object value and remains stable while that value moves between hot and cold tiers;
- the fenced route version changes on placement, offload, eviction, restore, and cleanup CAS.

Cold lifecycle mutations preserve the accounting/content operation ID. Tenant quota accounting follows logical content changes, while cold device accounting follows backend capacity changes.

### Cold capacity operation protocol

Every offload has a unique `cold_operation_id` tied to the content operation and selected device. Its durable metadata state advances monotonically:

```mermaid
stateDiagram-v2
[*] --> Planned: pending cold intent is authoritative
Planned --> Reserved: reserve device capacity
Planned --> Released: content replaced before reserve
Reserved --> PayloadWritten: idempotent backend put
Reserved --> Released: cancel before payload write
PayloadWritten --> RouteCommitted: materialized route CAS
PayloadWritten --> Reclaiming: route no longer references operation
RouteCommitted --> UsageCommitted: commit device usage
RouteCommitted --> Released: reclaim consumes reserved usage
UsageCommitted --> Released: reclaim decrements committed usage
Reclaiming --> Released: delete/mark-dead and release reservation
Released --> [*]
```

- Capacity reserve, commit, and release are idempotent metadata operations keyed by `cold_operation_id`.
- Backend put is idempotent by the same ID. LocalDir uses a deterministic operation-derived object path; ExtentStore journals the operation ID so recovery can find the assigned extent locator.
- `PayloadWritten` durably records the final locator, length, checksum, reservation, and payload fingerprint before route CAS.
- If route CAS materializes the same cold operation, restart reconciliation advances to `UsageCommitted`.
- A materialization CAS conflict reloads the route. If the same content operation and pending cold operation remain authoritative, the worker rebases and retries with the persisted payload fingerprint and current fenced route version.
- Reconciliation enters `Reclaiming` only after exact lookup proves that the authoritative route no longer references the cold operation or a different materialized backing won.
- Due operations are read from a maintained state/deadline index in bounded pages.

Cold reclaim uses a separate durable state machine:

```text
Planned -> BackendDeleted -> UsageReleased
```

A reclaim record is created before overwrite/delete route CAS. Cleanup verifies by exact route lookup that the locator is no longer authoritative and performs idempotent backend delete/mark-dead. It then calls one metadata-atomic handoff keyed by `(cold_operation_id, reclaim_operation_id)`:

- `RouteCommitted -> Released` consumes the outstanding capacity reservation without first exposing committed usage;
- `UsageCommitted -> Released` decrements committed usage;
- `PayloadWritten/Reclaiming -> Released` releases the reservation after payload cleanup;
- repeating the handoff returns the existing terminal result.

The reclaim record advances to `UsageReleased` only with that correlated cold-operation transition, preventing underflow and double release.

### Lifecycle

#### Write and offload

1. Select the cold device and allocate a unique cold operation ID.
2. The original content/accounting route mutation publishes the requested DRAM replicas and `PendingOffload` together under one fenced route version.
3. Finalize tenant accounting against that exact route version and return write success.
4. The offload worker creates or resumes the durable cold operation and verifies the current content operation, route state, and device eligibility.
5. Reserve cold capacity in metadata.
6. Read a valid hot replica and perform an idempotent backend write keyed by the cold operation ID.
7. Persist `PayloadWritten` with the final locator and payload fingerprint.
8. CAS the active cold backing from matching `PendingOffload` to `Materialized` while preserving the content operation ID.
9. Commit cold capacity usage. A materialization CAS conflict retries while the same cold operation remains authoritative and moves to reclaim only after exact lookup proves it is obsolete.

Pending work is rebuilt from active routes and the indexed cold-operation state after restart.

#### DRAM eviction

The storage-owner CLOCK scheduler continues to select hot replicas under DRAM pressure. A replica becomes eligible for last-hot eviction only when its active cold backing is materialized, the cold operation is `UsageCommitted`, and the backing owner/device remains readable.

- Route CAS verifies the expected fenced route version, content operation ID, cold operation ID, materialized locator fingerprint, and hot replica identity before removing the replica.
- Allocator bytes are released only after that CAS succeeds.
- Removing the final hot replica preserves the cold-only route.
- Capacity-pressure eviction may force materialization first when the configured offload mode is eviction-triggered.

#### Read and restore

1. Resolve the route and try healthy hot replicas first.
2. On a cold-only route, resolve the materialized cold backing and its owner.
3. Read and verify the backend payload.
4. Return the verified payload to the caller.
5. Allocate a normal hot replica and CAS it into the route best-effort.

Read success depends on payload validation, while DRAM re-promotion runs independently. Concurrent restores use singleflight keyed by cold backing identity and route version. Batch restores group requests by owner, cold device, and backend so the backend can issue native batch/read-into operations.

#### Overwrite and delete

Overwrite and delete reclaim both tiers:

- obsolete DRAM replicas enter normal route-aware reclaim;
- a durable `ColdReclaimRecord` for the old materialized locator is created before the content route mutation;
- the new content route carries its own active cold backing state;
- cleanup begins only after exact route lookup proves the old locator is no longer authoritative;
- backend delete/mark-dead and usage decrement advance idempotently through the reclaim state machine.

### Local and remote restore

A local reader resolves and reads a locally owned cold backend directly. A remote reader asks the cold-backing owner to stage the verified payload into bounded, transport-registered DRAM.

```mermaid
sequenceDiagram
participant Reader
participant Route as Route authority
participant Owner as Cold-backing owner
participant Backend as SSD / NFS backend
participant Staging as Bounded staging pool
participant Hot as Normal hot allocation

Reader->>Route: Resolve cold-only route
Route-->>Reader: Materialized cold backing
Reader->>Owner: ReadFromCold(route version, locator)
Owner->>Backend: Read and verify payload
Backend-->>Owner: Payload
Owner->>Staging: Allocate slot acquire reader and transfer pins
Owner-->>Reader: Segment, offset, transport metadata
par Remote read
Reader->>Staging: Read through TE/TENT
Reader->>Owner: TransportComplete(transfer token)
Owner->>Staging: Release transfer pin
Reader->>Owner: AckColdReadComplete
Owner->>Staging: Release reader pin
and Hot promotion
Owner->>Staging: Acquire promotion pin
Owner->>Hot: Allocate and copy verified payload
Owner->>Route: Best-effort hot promotion CAS
Owner->>Staging: Release promotion pin
end
Owner->>Staging: Recycle when all pins are released
```

The remote lifecycle is bounded:

- staging slots come from a fixed-capacity registered pool;
- owner validation checks route namespace, cold owner, route version, locator, length, and checksum;
- saturation returns explicit backpressure so the caller can retry;
- the reader ACK releases its reader pin; terminal transport completion releases the transfer pin; promotion holds an independent pin while copying;
- the slot is recycled only after reader, transfer, and promotion pin counts all reach zero;
- on expiry, the owner atomically fences the transfer token, rejects new or late transfers, cancels or observes terminal transport completion, releases the abandoned reader lease and transfer pin, and waits for any promotion pin before recycling; late completion and ACK messages are idempotent.

### Backends, devices, and scheduling

`ColdTierTargetConfig` supplies one or more runtime cold targets. SSD targets support directory/UUID resolution and select either:

- `LocalDir`: binary objects stored under a resolved directory;
- `ExtentStore`: append-oriented segment files with extent locators, batched I/O, liveness accounting, delete journaling, recovery, and bounded cleaning.

NFS targets use a validated NFS/NFS4 directory mount. Every resolved target becomes a metadata-backed device record with stable identity, owner epoch, kind, root, lifecycle, schedulability, capacity, used bytes, reserved bytes, tags, and health state.

Placement considers only healthy, schedulable devices with sufficient capacity. Capacity uses reserve/commit/release accounting around every backend write. Device caches are refreshed in the background, and queue scans, retry queues, route rebuilds, and cleanup work remain bounded or indexed.

Two offload modes are supported:

- `Passthrough`: a hot write publishes `PendingOffload` and the background queue materializes it;
- `EvictTriggered`: the eviction path claims a selected victim and materializes cold backing before releasing DRAM.

Passthrough scheduling supports FIFO and size-aware ordering. Eviction uses CLOCK and bounded coldest/largest selection. Rate limits, queue capacity, watermarks, retry backoff, and shutdown behavior are explicit runtime configuration.

### Cold tier invariants

- DRAM bytes are released only after route CAS removes the hot replica.
- Last-hot eviction requires `UsageCommitted` and CAS-matches the content operation, cold operation, locator fingerprint, route version, and hot replica being removed.
- Materialized cold reads verify length and checksum before returning data or publishing promotion.
- Restore promotion failure does not invalidate a verified read.
- Backend writes that lose their route CAS become reclaimable orphans.
- Cold usage advances through the durable cold operation before backend write and reaches exactly one committed or released terminal outcome.
- Remote staging memory remains protected until all reader, transfer, and promotion pins are released; expiry fences the transfer token and reaches terminal transport state before retiring abandoned pins.
- Delete and overwrite cleanup never remove a locator still referenced by an authoritative route.

## Multi-Tenant Isolation

### Trust and runtime tenancy model

Store-RS v1 uses a trusted-runtime model. Applications and gateways validate tenant identity before requests enter Store-RS; the runtime treats tenant/domain values as trusted logical selectors, and metadata credentials scope one Store-RS deployment.

One runtime may serve requests for multiple tenants. Its configured `default_tenant` is only the fallback request scope and the default process-level observability view; it is not an exclusive ownership boundary. All runtimes in one Store-RS deployment share a versioned deployment keyspace for membership and route policy. Object routes, quota records, accounting records, caches, and scheduling keys include the request tenant and optional domain explicitly.

This model permits a shared multi-tenant gateway while keeping object identity deterministic.

### Namespace model

The first release uses this hierarchy:

```text
tenant
tenant / domain
```

`tenant` is required and `domain` is optional.

The same logical key may exist independently in different tenants or domains. Its canonical route identity includes the complete supported scope, so visibility cannot depend on caller-side filtering.

### Hard isolation

Hard isolation covers:

1. **Namespace isolation**
- Tenant/domain identity participates in route and accounting keys.
- Exact lookups never list a global namespace and filter in process.
- Local caches and request batching include tenant/domain in their isolation key.

2. **Metadata isolation**
- Runtime control metadata is bound to a versioned deployment keyspace.
- Tenant policy, quota, and object accounting use exact tenant-root keys and maintained indexes inside that deployment keyspace.

3. **Strict quota admission**
- Limits are `max_bytes` and `max_objects` at the tenant root.
- Metadata stores authoritative used, pending, and committed accounting.
- Concurrent writers cannot independently pass a stale read-only preflight and over-admit the quota.
- Overwrites charge the committed byte delta.
- Deletes refund quota only after authoritative route deletion.

4. **Tenant-local quota recovery**
- A write that needs quota recovery may evict an older object from the same tenant.
- It never evicts another tenant's object to admit the write.
- An object larger than the configured tenant limit fails without destructive recovery attempts.

Strict quota is tenant-root only in the first release. Domains isolate object identity but do not receive independent sub-quotas.

### Tenant policy and quota protocol

The hard-isolation contract requires one canonical effective policy. Runtime-local quota values cannot remain independent hints.

#### Policy bootstrap

- Deployment configuration supplies a finite set of tenant-root policies.
- On bootstrap, a runtime creates each missing policy in metadata with create-if-absent semantics.
- A stored policy has a schema version, policy version, and deterministic configuration fingerprint.
- A later runtime must match the stored hard-isolation policy or fail startup for that tenant.
- Policy changes use a controlled restart and the same metadata version/fingerprint validation applied at bootstrap.
- Soft-isolation fields may differ only when explicitly documented as runtime-local; they are never used to make quota-admission decisions.

#### Quota state machine

For each tenant root, metadata stores versioned quota state, per-object committed accounting, and signed accounting-operation records. Create, overwrite, and delete use the same operation protocol. An operation is identified by the writer runtime epoch plus a unique sequence and contains:

- tenant and canonical object key;
- operation kind (`create`, `overwrite`, or `delete`);
- expected predecessor route version and expected object-accounting version;
- intended next length and signed byte/object deltas;
- once publishing begins, the intended bounded route or tombstone mutation payload and its fingerprint;
- expiry, writer identity, and operation ID.

Metadata permits at most one non-terminal accounting operation per canonical object key. An operation moves monotonically through this state machine:

```mermaid
stateDiagram-v2
[*] --> Pending: reserve
Pending --> Aborted: abort or expiry wins
Pending --> Publishing: fenced primary claims publish token
Publishing --> Publishing: publish, reconcile, or replay route/tombstone
Publishing --> Finalized: finalize matching published version
Aborted --> [*]
Finalized --> [*]
```

- `reserve` reads the committed object-accounting row, verifies the expected accounting and predecessor route versions, derives the signed delta from committed state, checks `used + pending + positive_delta` against the stored policy, and atomically records the pending operation plus its per-object lock.
- Clients do not supply a trusted negative delta. Metadata derives overwrite and delete refunds from the committed accounting row, so two writers cannot both refund the same predecessor.
- Repeating the same operation ID is idempotent and returns its current state.
- `Pending` means no route authority is allowed to publish the mutation. The writer may abort it before requesting route publication.
- Immediately before applying route CAS, the fenced route primary atomically changes the metadata operation from `Pending` to `Publishing` and records its shard generation, fencing token, bounded route/tombstone mutation payload and fingerprint, and publish token.
- If an expiry worker races that transition, metadata serialization chooses one winner: an already `Aborted` operation cannot enter `Publishing`, and a `Publishing` operation cannot be aborted by the ordinary expiry path.
- The route CAS publishes an active route for create/overwrite or a retained tombstone for delete. Both carry `accounting_operation_id`, predecessor version, and the new fenced route version.
- `finalize` requires the matching operation ID and new route version, atomically moves the positive pending delta into committed usage, applies the derived negative delta, updates object accounting, and releases the per-object lock.
- `abort` is valid only from `Pending`; it atomically releases the positive pending delta and per-object lock. Route primaries reject CAS for `Pending` or `Aborted` operations.
- Finalize and abort are idempotent; a finalized operation cannot later be aborted, and an aborted operation cannot later be finalized.
- Batch operations acquire per-object locks and reservations in canonical scoped-key order. If any item fails admission, already acquired operations are aborted before data transfer starts.

The route CAS and metadata quota transaction are separate authorities, so a process can crash between them. A runtime reconciliation worker closes those crash windows.

#### Crash recovery

- Pending and publishing operations have bounded deadlines and are indexed by `(tenant, state, deadline, operation_id)`.
- The reconciliation worker reads only due entries from that maintained index in bounded pages.
- Expired `Pending` operations are aborted atomically. A delayed route request must first perform `Pending -> Publishing`; after abort wins, that transition and the route CAS are rejected.
- `Publishing` is an irrevocable in-doubt state in v1. It is never automatically aborted, because a route CAS may already be applied or in flight.
- For each due `Publishing` operation, reconciliation performs an exact route/tombstone lookup and exact object-accounting lookup.
- If the active route or delete tombstone carries the same operation ID, predecessor version, and fenced next version, reconciliation finalizes idempotently.
- If object accounting already records the operation ID and next version, reconciliation treats it as finalized.
- If the predecessor is still authoritative and the stored shard generation remains valid, reconciliation asks the current fenced primary to replay the same publish token and intended mutation; it does not create a new accounting operation.
- If replay cannot be proven safe, the operation remains `Publishing`, charged, and object-locked. It is reported through metrics/tracing and retried; the runtime never frees quota based on a partial route scan.
- Delete tombstones and terminal operation history have bounded retention and are removed only after committed accounting proves finalization.
- Ambiguous recovery retries with capped exponential backoff. A persistent ambiguity keeps quota unavailable for that object and raises a health degradation signal while preserving the conservative charge.

This worker supplies correctness recovery for the quota protocol.

### Soft isolation

Soft isolation uses local scheduling and submission caps to reduce interference between tenants sharing one runtime.

- `max_remote_batch_items_per_tenant` limits one tenant's occupancy in a remote batch.
- `max_remote_batch_bytes` bounds bytes in a remote batch.
- `max_remote_batch_burst_items` bounds short bursts.
- `max_inflight_bytes_per_batch` bounds inflight batch bytes.
- Tenant placement policy may prefer storage owners or active segments.
- Preferred placement is a hint unless a request explicitly asks for a hard pin.

These controls are enforced by the runtime that plans and submits the work. The fairness key is the canonical tenant ID. A runtime groups queued remote work by tenant, takes no more than the configured item/byte budget from one tenant in a scheduling turn, and rotates across non-empty tenant queues. Inflight limits are enforced before transport submission and released only after completion or terminal failure. This provides local weighted round-robin fairness within each runtime.

### Policy bootstrap and consumption

- `StoreClientBuilder` accepts a finite tenant-policy configuration plus default fairness, bandwidth, routing, replication, and placement settings.
- Equivalent Store-RS-specific Python and standalone runtime configuration may supply the same finite policy set.
- The runtime bootstraps missing durable tenant policies and rejects hard-policy mismatches.
- The runtime reads policy by exact tenant-root scope and caches it for request planning; the metadata backend revalidates the stored policy/version during quota admission.

## Observability

Observability is part of the first release because a distributed peer control plane cannot be operated safely as a black box.

### Metrics

The runtime exports:

- request totals, errors, bytes, inflight work, and latency histograms;
- route lookup, route CAS, repair, and replication publication outcomes;
- allocation, segment capacity, eviction, and reclaimed bytes;
- metadata backend operation counts and latency;
- transport operation counts, bytes, and failures;
- membership refresh and heartbeat health;
- tenant quota reserve, finalize, abort, conflict, and tenant-local eviction outcomes;
- cold device capacity, used/reserved bytes, schedulability, and health;
- offload queue depth, materialization, retry, orphan cleanup, and latency;
- restore backend I/O, singleflight, staging usage, backpressure, ACK, promotion, and latency;
- ExtentStore queue, I/O lane, batching, direct/buffered fallback, journal, and cleaning activity;
- process CPU, resident memory, and file-descriptor usage.

Metrics use bounded label sets. Object keys, domain values, route versions, runtime-generated request IDs, and peer addresses are not Prometheus labels. Request-path Prometheus counters aggregate across request tenants by default. Operators diagnose one tenant through an exact, bounded `/stats?tenant=` lookup and through sampled traces; the metrics endpoint does not create a new time series merely because a previously unseen tenant ID appeared in a request. A deployment may opt into per-tenant metric labels only for its finite bootstrap policy set, with a configured cardinality cap and an overflow aggregate.

### Tracing and diagnostics

- API spans use `store.*` names.
- Control-plane spans use `control.*` names.
- Data-plane spans use `data.*` names.
- Metadata spans use `metadata.*` names.
- OTLP export and local JSONL capture are supported.
- Per-item debug records are opt-in and default to hashed keys.
- `/healthz`, `/metrics`, `/stats`, `/breakdown`, and runtime-local tracing control are available.

`/stats` and `/breakdown` use fixed response schemas, bounded top-N sections, and no full route, reservation, or keyspace traversal. Exact tenant diagnostics use maintained accounting indexes. Numeric page sizes, top-N defaults, cache TTLs, and reservation TTLs are implementation constants documented with the first code PR rather than mutable, unbounded API inputs.

## Public Interfaces

### Rust

The initial Rust API includes:

- `StoreClientBuilder` and lifecycle configuration;
- single and batch object operations;
- tenant and optional domain request builders;
- replication and placement policy;
- registered-buffer and multi-buffer I/O;
- cold tier target, watermark, rate-limit, offload-mode, priority, and shutdown configuration;
- runtime metrics and tracing initialization.

### Python

The first release ships the `mooncake-store-rs` distribution with the `mooncake_store_rs` import package and `mooncake_store_rs._store_rs` native extension. The supported initial wheel target is Linux x86_64 for the Python versions exercised by upstream CI. It exposes real and standalone-client modes, single and batch operations, registered buffers, tenant/domain configuration, cold tier targets, metrics, and tracing.

The package coexists with the upstream Mooncake wheel without overwriting files owned by that wheel.

### Build integration

- Store-RS is disabled by default in top-level CMake.
- Enabling Store-RS requires Cargo and builds the nested Cargo workspace.
- The build reuses the enclosing Mooncake native build outputs and must not configure a second copy of Mooncake.
- Standalone-repository and nested-monorepo layouts are both supported by explicit path resolution.
- `Cargo.lock` is regenerated on the target upstream base rather than copied from a development environment.

## Source Ownership and Synchronization

The existing standalone Store-RS repository may continue to exist, but the same source files must not have two informal sources of truth.

Before implementation merges, maintainers must select one model:

1. **Upstream-first:** Mooncake is canonical; the standalone repository mirrors selected commits.
2. **Standalone-first with mechanical import:** Store-RS is canonical; Mooncake imports reviewed revisions through a documented, reproducible process.
3. **Single home:** Development moves to Mooncake and the standalone repository becomes archival.

Manual copy-and-fix synchronization is not acceptable because build-path fixes, security changes, and protocol updates would diverge silently.

## Delivery Plan

The RFC intentionally does not make crate boundaries the only PR boundaries. Each implementation PR must leave its branch buildable and independently testable.

1. **Foundation and build gate**
- Nested Cargo workspace, build integration, regenerated lockfile, formatting, clippy, and path-filtered CI.
- Core identities and native transport FFI sufficient for a real build target.

2. **Transport, metadata, and route authority mesh**
- Safe transport wrapper, Redis/etcd/in-memory metadata, WRH route table, exact indexes, and bounded pagination.

3. **Minimal masterless client path**
- Membership, allocation, put/get/remove, replication, reclaim, registered-buffer I/O, and component tests.

4. **Tenant hard isolation**
- Tenant/domain identity, metadata-authoritative quota protocol, bounded runtime reconciliation, delete refund, tenant-local eviction, and concurrency tests.

5. **Tenant soft isolation and observability**
- Fairness, shaping, placement hints, metrics, tracing, health, and diagnostic endpoints.

6. **Hot/cold storage**
- Cold backing route schema, device/capacity metadata, SSD/NFS backends, offload, cold-only eviction, restore, staging/ACK, cleanup, recovery, and cold tier metrics.

7. **Python package and documentation**
- Store-RS-specific Python binding and wheel, coexistence checks, Rust/Python user documentation, and strict documentation build.

## Validation and Acceptance Criteria

The first upstream scope is acceptable when all of the following hold:

### Build and quality

- Top-level CMake configures successfully with Store-RS disabled and does not require Cargo.
- Enabling Store-RS builds the Rust workspace against the enclosing Mooncake native artifacts.
- `cargo fmt --check`, clippy with warnings denied, and all included unit/property/component tests pass.
- The strict upstream documentation build succeeds.

### Masterless correctness

- Two or more in-process runtimes can publish membership, select route authorities, allocate replicas, and complete put/get/remove without a dedicated master service.
- Route lookup and route CAS use the authority mesh in `EmbeddedWrh` mode.
- Metadata calls on steady-state non-quota object paths are demonstrated not to include route reads or full scans.
- A failed replica can be bypassed when another valid replica remains.
- Deterministic simulated-peer tests cover primary authority loss, shard-lease expiry, fencing-token rollover, membership refresh, stale runtime epochs, partial synchronous mirroring, authority-set state transfer, protocol-conflict detection, and read repair.
- Two callers with different membership snapshots or different primary reachability cannot both receive successful CAS results for the same predecessor version.
- Partition tests prove fail-closed write behavior: only the fenced primary side may progress, and failover does not activate a new primary until the old lease expires and route state is transferred safely.
- After fencing-token rollover and a new-generation mutation, stale clients cannot obtain a successful route read from either an old primary or an old secondary; they receive `stale_generation`, refresh, and retry.
- Owner-route enumeration is bounded and cannot prove absence from a partial result.

### Hard tenant isolation

- Identical logical keys in two tenants, and in two domains of one tenant, remain independent.
- Cross-tenant and cross-domain reads, route queries, deletes, caches, and accounting do not leak.
- Concurrent quota reservations cannot exceed configured tenant-root byte or object limits.
- Failed writes abort pending quota; successful overwrite and delete apply the correct delta.
- Crash-window tests cover failure before route CAS, after route CAS but before accounting finalize, after finalize but before reply, and during delete refund.
- Concurrent overwrite/delete/retry tests prove that one predecessor accounting row can be refunded only once and that reconciliation correlates route/tombstone state by operation ID.
- Deterministic race tests delay route CAS while explicit abort and expiry reconciliation run. Either `Pending -> Aborted` wins and CAS is rejected, or `Pending -> Publishing` wins and the operation remains non-abortable until finalize/reconciliation.
- Bounded runtime reconciliation converges or conservatively leaves ambiguous state charged and health-degraded.
- Quota recovery evicts only from the requesting tenant.
- Redis and etcd backends pass real-process atomicity tests.

### Soft tenant isolation

- Batch item, byte, burst, and inflight limits are enforced at runtime planning boundaries.
- Tenant placement preferences are tried first and fall back only when configured as soft.
- Tests verify the local scheduling guarantees.
- A deterministic scheduler test shows that one continuously backlogged tenant cannot consume more than its configured per-turn budget while another tenant remains runnable.

### Observability

- Request, route, metadata, transport, allocation, eviction, membership, and quota metrics are exported.
- A sampled request produces a connected API/control/data/metadata trace where applicable.
- Health and breakdown endpoints return bounded responses.
- Prometheus output contains no object key or request-ID labels.
- Exact tenant diagnostics do not scan all routes or reservations.

### Hot/cold storage

- Foreground writes return after authoritative DRAM publication and continue cold materialization asynchronously.
- Successful offload transitions `PendingOffload` to `Materialized` and advances its cold operation to `UsageCommitted`.
- Crash-window tests cover capacity reserve, backend write, locator persistence, materialized route CAS, and usage commit; reconciliation resumes idempotently from every state.
- A materialization CAS racing a hot-placement mutation rebases and retries when the same content/cold operation remains authoritative; it enters reclaim only when exact lookup proves obsolescence.
- DRAM eviction never removes the final hot replica before the matching materialized backing is readable.
- A race between last-hot eviction and overwrite/delete succeeds for at most one expected route/content/cold identity and never removes the only readable copy.
- Last-hot eviction produces a readable cold-only route.
- Local restore returns checksum-verified bytes and publishes hot promotion best-effort.
- Remote restore validates owner/namespace, uses the bounded staging pool, preserves backpressure, and recycles slots after ACK or fenced expiry only when reader, transfer, and promotion pins are all released.
- Staging tests cover late transfer, late ACK, transport cancellation/terminal completion, and promotion overlapping expiry.
- Concurrent restore singleflight does not reuse payloads across route versions or cold backing identities.
- Batch restore uses backend batch/read-into paths for requests sharing an owner and cold device.
- Overwrite and delete create durable reclaim records before route mutation, then advance `Planned -> BackendDeleted -> UsageReleased` through the correlated metadata-atomic cold-operation handoff.
- A race between overwrite/delete and `RouteCommitted -> UsageCommitted` reaches exactly one `Released` outcome, consuming either reserved or committed bytes without underflow.
- Restart reconciliation rebuilds pending offload operations, reclaim operations, device usage, ExtentStore state, and route work from bounded indexes and durable records.
- Cold tier metrics expose device capacity, queue pressure, offload/restore latency, staging occupancy, backpressure, retries, and cleanup outcomes.

### Python packaging

- The wheel installs into a clean environment and imports its native extension.
- Installing it alongside the upstream Mooncake wheel produces no overlapping package files.
- Python tenant/domain behavior matches the Rust runtime.

## Compatibility and Rollout

- The existing Mooncake Store remains the default implementation.
- Store-RS is selected explicitly at build and runtime boundaries.
- No existing C++, Go, or Python API silently changes implementation.
- Metadata keys use a Store-RS-specific prefix/version that isolates them from existing Store metadata.
- Runtime compatibility descriptors admit peers that advertise the required route and quota protocol versions.
- Runtime compatibility descriptors include the cold backing, remote restore, staging ACK, and cold device accounting protocol versions.
- Rolling upgrade behavior is validated at the component and protocol levels.

## Open Questions

1. Is a Store-RS-specific Python import path sufficient initially, or is a reviewed explicit backend factory required?
2. Which metadata backend is required for the first supported deployment: Redis, etcd, or both?
3. Should `MetadataOnly` be public in the first release or retained only for tests and debugging?
4. Initial code volume is too large to review.

### 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 with the RFC's `mooncake-store/store-rs` scope and proposed component responsibilities, then compare them with the existing Mooncake Store architecture. Review the listed Store-RS crates and the Redis/etcd coordination requirements; this RFC is ready for implementation only after its source-of-truth and synchronization policy are explicitly agreed.

Written by the indexing model from the issue text.