Tenant Quota Consistency Design

Contents

Tenant Quota Consistency Design#

Background#

Store-RS already supports tenant-scoped quota policy through metadata-backed tenant policy and runtime enforcement hooks. Today, however, quota enforcement still happens as a request-path preflight inside the client runtime.

Relevant current path:

  • StoreClient::put_object_with_policy_current(...) in crates/mooncake-store-client/src/client/runtime_io.rs

  • routed and batch write allocation / publication logic in:

    • crates/mooncake-store-client/src/client/runtime_io.rs

    • crates/mooncake-store-client/src/client/runtime_write.rs

  • tenant quota policy model in:

    • crates/mooncake-store-core/src/route.rs

  • metadata-backed tenant policy storage in:

    • crates/mooncake-store-rs-metadata

Current write flow is roughly:

  1. load current route / object state

  2. evaluate quota from that snapshot

  3. reserve local or remote capacity

  4. write bytes into storage segments

  5. publish the new route with route CAS

  6. reclaim previous route allocations

This leaves a time-of-check/time-of-use gap:

  • two writers can both read the same tenant usage snapshot

  • both can pass quota admission

  • both can write bytes

  • both can attempt route publication

  • quota correctness depends on timing rather than protocol guarantees

That is acceptable for best-effort quota, but it is not sufficient for hard multi-tenant isolation.

Goal#

Make tenant quota enforcement strongly consistent at the metadata authority level so concurrent writes cannot over-admit tenant storage usage beyond configured quota, except in explicitly bounded transitional states.

The design should:

  • preserve tenant-scoped policy as the source of truth for limits

  • work with current Store-RS architecture:

    • embedded WRH route authorities

    • metadata-backed tenant policy

    • allocator reservations and route publication

    • remote storage-owner tracking

  • correctly handle:

    • create

    • overwrite

    • delete

    • conflict retry

    • client crash during write publication

  • keep the request-path semantics understandable and debuggable

Non-Goals#

This design does not try to solve:

  • global fairness / rate limiting

  • bandwidth shaping

  • allocator-space accounting beyond quota admission correctness

  • exact real-time reconciliation of every derived usage view

  • elimination of all background reconciliation work

  • redesigning route ownership or WRH authority selection

This design is specifically about hard tenant quota admission for stored objects.

External Design References#

The research across Ceph, Kubernetes, HDFS, Swift, MinIO, SeaweedFS, JuiceFS, and transactional KV systems led to a clear conclusion:

  • systems that want hard quota semantics perform quota accounting in the same authoritative metadata transaction as object state mutation, with optimistic conflict retry

  • systems that keep quota checks outside the authoritative commit path usually become best-effort or eventual

The most relevant patterns for Store-RS are:

  1. Kubernetes ResourceQuota

    • admission-time enforcement against authoritative versioned state

    • optimistic conflict retry on concurrent updates

  2. HDFS quota enforcement

    • namespace mutation and quota accounting share a single metadata authority path

  3. FoundationDB transactional counters

    • read current counter, compute delta, update counter and entity record in one serializable transaction

  4. JuiceFS hybrid practice

    • hard admission on authoritative state, background repair only for derived accounting / cleanup

This design follows that family of solutions.

Current Architecture Constraints#

From the Store-RS architecture, the current Store-RS write path has these important properties:

  • StoreClient performs request-path admission, allocation, transfer, and route publication

  • RouteDirectory owns route lookup and route CAS

  • route authority is usually not the metadata backend directly in EmbeddedWrh mode

  • allocator reservation and data transfer can happen before the final route CAS commits

  • storage ownership and route ownership are intentionally decoupled

Those constraints matter because a strict quota design must answer:

  1. where quota usage becomes authoritative

  2. how overwrite delta is computed

  3. what happens if data bytes are written but final publication does not commit

  4. how retries avoid double-charging or double-refunding

Problem Statement#

Why the current flow is insufficient#

Today the runtime can ask “does this tenant still have room?” before writing, but that answer is based on a snapshot that may already be stale by the time route publication happens.

This creates several correctness gaps:

1. Concurrent create overshoot#

Two writers can both observe usage below limit and both admit writes that together exceed quota.

2. Incorrect overwrite accounting#

Quota should be charged on delta:

  • create: +new_size

  • overwrite larger value: +(new_size - old_size)

  • overwrite smaller value: -(old_size - new_size) or immediate refund to usage

  • delete: -old_size

A preflight check on new_size alone is not sufficient.

3. Publish-after-write crash window#

The current write path can write bytes before final route publication succeeds. If the client crashes after writing bytes but before authoritative metadata commit, quota state and stored bytes can diverge.

4. Conflict retry ambiguity#

Retries must not:

  • charge quota twice

  • leak reserved quota

  • reclaim quota for a write that never became authoritative

A correct solution needs idempotent state transitions.

Design Summary#

Introduce a new authoritative tenant quota state in metadata and move quota admission into the same metadata mutation protocol that commits object state.

The recommended model is:

  1. derive the current object accounting state from authoritative metadata

  2. compute the requested quota delta

  3. atomically update:

    • tenant quota usage state

    • authoritative object accounting state

    • route publication intent / committed object metadata

  4. only after that authoritative commit succeeds should the write become visible as committed

  5. if data bytes must be written before final commit, represent that with an explicit reservation / pending-write record rather than with an implicit preflight check

In short:

  • quota becomes part of the metadata commit protocol

  • not a separate runtime-local admission hook

Proposed Metadata Model#

1. Tenant quota state#

Add a new metadata entity per tenant scope:

TenantQuotaState {
  scope: TenantPolicyScope,
  version: u64,
  used_bytes: u64,
  used_objects: u64,
  pending_reserved_bytes: u64,
  pending_reserved_objects: u64,
  updated_at_ms: u64,
  updated_by: String,
}

Notes:

  • scope should initially be tenant-level only

  • domain/object_set quota usage can be added later if we want nested enforcement

  • version is required for optimistic concurrency / CAS

  • pending_reserved_* is only needed if we adopt the reservation-based protocol described below

2. Authoritative object accounting record#

Quota logic must know the committed size of each object.

We can satisfy that in one of two ways:

Option A: use the authoritative committed route/object record directly#

If the route record is always the committed source of object length, we can derive old size from it.

Pros:

  • less metadata duplication

Cons:

  • route ownership in EmbeddedWrh mode is authority-based rather than globally centralized in metadata

  • tying strict quota to route-authority-local state is harder to reason about

Option B: add a metadata-backed object accounting record#

TenantObjectAccounting {
  key: ObjectKey,
  tenant_scope: TenantPolicyScope,
  version: u64,
  committed_length: u64,
  route_version: Option<u64>,
  state: Active | Deleted,
  last_writer: String,
  updated_at_ms: u64,
}

Pros:

  • quota is anchored in one durable metadata plane

  • overwrite/delete delta is explicit

  • route authority remains responsible for route ownership while quota correctness remains metadata-authoritative

Cons:

  • additional metadata writes and consistency protocol

Recommendation#

Use Option B.

It cleanly separates:

  • route ownership / replica placement authority

  • tenant quota accounting authority

This matches the current Store-RS architecture better than forcing hard quota semantics into WRH route authorities.

Phase 1 status#

The Phase 1 metadata foundation now exists in the shared model and in-memory backend:

  • TenantQuotaState

  • TenantObjectAccounting

  • TenantQuotaReservation

  • TenantQuotaReservationRequest / TenantQuotaFinalizeRequest

  • backend trait methods for get/list/reserve/finalize/abort

Current implementation status:

  • in-memory backend: implemented and covered by unit tests

  • Redis backend: implemented with backend-atomic Lua reserve/finalize/abort scripts plus quota/accounting lookup helpers

  • etcd backend: implemented with multi-key compare-and-swap txn loops for reserve/finalize/abort plus quota/accounting lookup helpers

Phase 1 backend parity tests now cover:

  • create / overwrite / delete reservation state transitions

  • finalize idempotency

  • abort idempotency

  • byte and object limit admission

  • reservation listing and quota-state lookup

The first implementation remains tenant-root only. TenantPolicyScope values with domain/object-set components are rejected for quota-state mutation APIs until nested quota accounting is implemented.

Write Protocol Options#

There are two realistic protocol families.

Option 1: Atomic metadata commit before data publish#

Flow#

  1. read TenantQuotaState and TenantObjectAccounting

  2. compute delta_bytes and delta_objects

  3. CAS / transact metadata to:

    • validate limit

    • update quota usage

    • update object accounting state to new committed size/version

    • create a pending publish marker or next route intent

  4. write bytes to storage

  5. publish route

  6. mark pending publish committed

Why it is not the best fit today#

This gives strong quota semantics, but it means metadata can claim usage before data bytes are durably published. On crash/failure, we then need rollback or orphan recovery anyway.

Given Store-RS currently writes bytes before route publication, this option does not reduce protocol complexity enough.

Option 2: Reservation + finalize/abort protocol#

Summary#

This is the recommended design for Store-RS.

Instead of doing a plain preflight quota check, the writer first obtains an authoritative quota reservation in metadata. That reservation is then either finalized into committed usage or aborted.

New metadata entity#

TenantQuotaReservation {
  reservation_id: UUID,
  tenant_scope: TenantPolicyScope,
  object_key: ObjectKey,
  object_version_hint: Option<u64>,
  requested_bytes_delta: i64,
  requested_objects_delta: i64,
  state: Pending | Finalized | Aborted,
  expires_at_ms: u64,
  created_at_ms: u64,
  writer_runtime: ClientRuntimeId,
}

Flow#

Phase A: reserve quota#

  1. read committed TenantObjectAccounting for the object

  2. compute tentative delta against current committed size

  3. metadata transaction atomically:

    • verifies tenant policy limit

    • increments pending_reserved_bytes / pending_reserved_objects

    • inserts TenantQuotaReservation

    • version-checks the object accounting row used for delta calculation

If this step fails, the write is rejected before bytes are written.

Phase B: write bytes and publish route#

  1. reserve storage allocations

  2. write bytes to target segments

  3. publish the route through existing route authority flow

Phase C: finalize reservation#

  1. metadata transaction atomically:

    • verifies reservation is still Pending

    • verifies committed object accounting version still matches expected predecessor

    • applies the committed object size/version

    • moves reserved quota into committed usage

    • decrements pending_reserved_*

    • marks reservation Finalized

Abort path#

If route publication fails or the writer gives up:

  • metadata transaction marks reservation Aborted

  • decrements pending_reserved_*

  • leaves committed usage unchanged

  • local/remote allocations are released or scheduled for reclaim

Why this fits Store-RS best#

It matches the current architecture:

  • allocations and data transfer still happen before final route visibility

  • quota state becomes authoritative in metadata rather than in route authorities

  • failures become explicit protocol states instead of hidden races

  • recovery is auditable and repairable

Authoritative Semantics#

Committed usage#

used_bytes and used_objects reflect only finalized committed objects.

Pending usage#

pending_reserved_* reflects in-flight writes that passed quota admission but have not yet finalized.

Admission rule#

New reservations are allowed only if:

used_bytes + pending_reserved_bytes + requested_positive_bytes_delta <= max_bytes
used_objects + pending_reserved_objects + requested_positive_objects_delta <= max_objects

Non-positive deltas from shrink / overwrite-same / overwrite-smaller / delete should not require quota headroom on that dimension.

Why include pending reservations in admission#

Without this, concurrent in-flight writes can all reserve against the same free space and oversubscribe before finalization.

Delta Computation Rules#

Quota correctness depends on consistent delta rules.

Assume authoritative committed state for object O is:

  • old_size

  • old_exists

Then:

Create#

If object does not exist:

  • delta_bytes = new_size

  • delta_objects = +1

Overwrite same object#

If object exists:

  • delta_bytes = new_size - old_size

  • delta_objects = 0

This means:

  • larger overwrite may require headroom

  • same-size overwrite needs no quota expansion

  • smaller overwrite frees quota on finalize

Delete#

If object exists:

  • delta_bytes = -old_size

  • delta_objects = -1

Idempotent retry#

A retry of the same logical write must either:

  • reuse the same reservation id, or

  • fail version checks and recompute against latest committed state

The protocol must never assume retries are harmless without version checks.

Interaction with Route Authorities#

The current architecture deliberately keeps route control off the metadata hot path for normal reads/writes in EmbeddedWrh mode.

This design preserves that.

Principle#

  • metadata is authoritative for quota accounting

  • route authorities remain authoritative for route publication and mirrored route convergence

Implication#

Finalization must bridge both worlds:

  • route publication result determines whether the write became visible

  • metadata finalization determines whether quota usage becomes committed

Required invariant#

A route must not be treated as fully committed for quota purposes unless the matching reservation is finalized.

That means we need one of these two implementation rules:

Rule A: finalize immediately after successful route CAS, before returning success#

This is the recommended rule.

The user-visible put(...) only returns success once:

  1. route CAS succeeded

  2. reservation finalization succeeded

If finalization fails after route CAS succeeds, the client must enter repair logic instead of blindly returning success.

Rule B: return success after route CAS and reconcile finalization asynchronously#

Not recommended for the first implementation.

It creates user-visible ambiguity and can temporarily diverge committed route visibility from committed quota usage.

Failure Handling and Recovery#

This is the main reason to prefer an explicit protocol over a hidden preflight check.

Failure matrix#

1. Reservation fails#

Result:

  • write rejected

  • no bytes written

  • no route published

2. Data write fails after reservation#

Result:

  • reservation is aborted

  • pending reservation counters are released

  • allocations are released

  • no committed usage change

3. Route CAS fails after data write#

Result:

  • reservation is aborted

  • newly written allocations are released or reclaimed

  • no committed usage change

4. Client crashes after reservation, before finalize/abort#

Result:

  • reservation remains Pending

  • background reconciler inspects expired reservations

  • for each expired reservation:

    • if no matching committed route/object accounting exists, abort it

    • if route publication succeeded and object accounting can be proven, finalize it

5. Finalize transaction conflicts#

Result:

  • retry finalization if the predecessor version still matches

  • otherwise re-read current object accounting and route state

  • if another write already committed a newer object version, abort stale reservation and reclaim bytes

Background Reconciliation#

A strict protocol still needs bounded repair for crash recovery.

Add an explicit reconciliation loop or admin-triggered tool for:

  • expired pending reservations

  • orphaned written allocations with no finalized reservation

  • finalized accounting with missing route visibility

  • route visibility with stale pending reservation state

Initial implementation recommendation#

Keep reconciliation simple and operator-visible:

  • add admin inspection commands first

  • background automation can come after the protocol is stable

Suggested admin surface:

  • mooncake-store-rs-admin quota state --tenant <t>

  • mooncake-store-rs-admin quota reservations --tenant <t>

  • mooncake-store-rs-admin quota abort --tenant <t> --reservation-id <id> [--dry-run]

  • mooncake-store-rs-admin quota reconcile --tenant <t> [--dry-run]

The current implementation also exposes matching HTTP endpoints:

  • GET /v1/tenant-quotas/<scope>

  • GET /v1/tenant-quotas/<scope>/reservations?state=pending|finalized|aborted

  • POST /v1/tenant-quotas/<scope>/reservations/<reservation_id>/abort

  • POST /v1/tenant-quotas/<scope>/reconcile

Current reconcile behavior is intentionally conservative:

  • expired pending reservations are aborted

  • pending reservations whose route and object-accounting state already match an authoritative active object are finalized

  • other mismatches remain inspectable and are reported as skipped for operator review

Reservation retention is now split by lifecycle state:

  • Pending reservations are kept until they are finalized or aborted by normal write flow or explicit reconcile

  • Finalized and Aborted reservations are retained only for a bounded terminal window, then expire from Redis automatically

  • the default terminal retention window is 24h

  • terminal retention uses Redis TTL on both the reservation record and its per-tenant index entry so completed history does not accumulate indefinitely

This matches the existing admin philosophy in the multi-tenant admin design. Runtimes now also export tenant-quota reservation/finalize/abort/reconcile counters through the built-in Prometheus metrics registry.

API / Trait Changes#

Metadata traits#

Add new metadata operations in mooncake-store-core and implement them in all backends.

New operations#

get_tenant_quota_state(scope)
compare_and_swap_tenant_quota_state(scope, expected_version, next)
get_object_accounting(key)
compare_and_swap_object_accounting(key, expected_version, next)
create_quota_reservation(...)
finalize_quota_reservation(...)
abort_quota_reservation(...)
list_quota_reservations(scope, filter)

Preferred backend shape#

Where backend capabilities allow it, expose higher-level atomic methods instead of forcing multi-step client orchestration:

reserve_quota_for_object_write(...)
finalize_quota_write(...)
abort_quota_write(...)

This is especially important for Redis / etcd so the client does not emulate multi-key transactions unsafely.

Runtime changes#

StoreClient#

Current enforce_namespace_quota(...) evolves from:

  • preflight policy check

to:

  • reservation acquisition / finalize / abort coordinator

runtime_io.rs#

Single-object write path should change from:

  • check quota n- allocate

  • write

  • route CAS

  • reclaim old route

to:

  • compute predecessor state

  • reserve quota in metadata

  • allocate

  • write

  • route CAS

  • finalize quota reservation

  • reclaim old route

  • on failure: abort reservation and reclaim new allocations

runtime_write.rs#

Batch writes should not reserve quota per item independently without metadata protection.

Recommended batch rule:

  • reserve per object in a deterministic key order, or

  • add a backend-level batch reservation transaction for a set of object deltas in one tenant

The second option is preferable for throughput, but the first option is easier to ship first.

Batch Write Semantics#

Batch writes need explicit policy because quota admission can partially succeed.

Delete Path#

Delete must participate in authoritative quota accounting too.

Required flow#

  1. load authoritative object accounting

  2. route delete CAS succeeds

  3. metadata finalization applies negative delta:

    • used_bytes -= old_size

    • used_objects -= 1

    • object accounting moves to Deleted

  4. reclaim route allocations

Delete should not rely on asynchronous reclaim to refund tenant quota. The quota refund should happen when the delete becomes authoritative, not when bytes are later garbage-collected.

Overwrite Path#

Overwrite is the most important correctness case.

Required invariant#

Quota is charged on committed object delta, not on raw incoming payload size.

Example:

  • current object size = 64 MiB

  • max tenant bytes = 100 MiB

  • current committed usage = 90 MiB

  • overwrite with 65 MiB should succeed

    • delta = +1 MiB

  • overwrite with 120 MiB should fail

    • delta = +56 MiB

This is one of the main reasons an explicit object accounting row is useful.

Redis / etcd / in-memory backend implications#

Redis#

Redis can support this design if the multi-key reserve/finalize/abort steps are implemented as Lua scripts with version checks.

Needed properties:

  • atomic read-check-write across:

    • quota state key

    • object accounting key

    • reservation key

  • deterministic conflict result

  • no client-side race window between independent Redis commands

etcd#

etcd can support this design through compare-and-swap style transactions over versioned keys.

Needed properties:

  • compare object accounting version

  • compare quota state version

  • write reservation and next state in one txn

In-memory#

In-memory backend should implement the same protocol directly under a mutex for test determinism.

Observability#

Add explicit metrics and logs so quota behavior is diagnosable.

Suggested metrics#

  • store_quota_reservation_total{result=ok|conflict|error}

  • store_quota_finalize_total{result=ok|conflict|error}

  • store_quota_abort_total{reason=write_failed|route_conflict|expired|repair}

  • store_quota_pending_reservations

  • store_quota_used_bytes

  • store_quota_used_objects

  • store_quota_reconcile_total{result=finalized|aborted|error}

Suggested logs#

Every reservation/finalize/abort should log:

  • tenant

  • object key

  • reservation id

  • predecessor version

  • delta bytes / objects

  • final outcome

Rollout Plan#

Phase 0: design-only preparation#

  • add this design doc

  • align on metadata model and semantics

  • decide whether object accounting is route-derived or separate

Phase 1: metadata model and admin inspection#

  • add TenantQuotaState

  • add TenantQuotaReservation

  • add TenantObjectAccounting

  • add backend support in in-memory, Redis, and etcd

  • add admin read-only inspection commands

Phase 2: single-object strict quota path#

  • implement reserve/finalize/abort for single put

  • implement delete refund path

  • gate behind an opt-in runtime/config flag if needed during bring-up

  • add crash/retry tests

Current single-object runtime behavior#

For positive-delta writes, the current single-object path adds a bounded tenant-local recovery step on top of metadata-authoritative reserve/finalize/abort semantics:

  • quota policy resolves from LogicalObjectId.scope.tenant, not only from the writer’s default tenant

  • when reservation returns tenant quota bytes exceeded or tenant quota objects exceeded, runtime may evict one older object from the same tenant and retry

  • recovery is bounded by MAX_TENANT_LOCAL_EVICTION_ATTEMPTS

  • victim selection stays tenant-local: skip the object being written, consider only RouteState::Active, and order candidates by older version first and then larger committed length

  • if no same-tenant victim can free enough room, the original quota conflict is returned unchanged

  • cross-tenant data is never evicted to satisfy another tenant’s write

This keeps strict quota semantics intact: metadata reservation/finalize is still authoritative, and self-eviction only frees capacity inside the same tenant before the next retry.

Phase 3: batch strict quota path#

  • implement deterministic multi-object reservation flow

  • add batch rollback / abort semantics

  • add conflict-heavy tests

Phase 4: reconciliation automation#

  • background cleanup for expired reservations

  • admin-triggered repair commands

  • metrics / dashboards

Phase 5: remove legacy best-effort path#

  • stop treating runtime-local preflight quota checks as authoritative

  • keep them only as early rejection hints, or remove them entirely

Alternatives Considered#

1. Keep current preflight check and add more retries#

Rejected.

Why:

  • retry reduces visible failures

  • it does not eliminate quota TOCTOU

  • concurrent writers can still over-admit quota

2. Make route authorities own quota directly#

Rejected for now.

Why:

  • route authority in EmbeddedWrh is intentionally off-metadata and mirrored

  • quota state wants a single durable authoritative plane

  • tying quota correctness to mirrored route authority convergence adds unnecessary coupling

3. Use only periodic reconciliation/scanner-based enforcement#

Rejected.

Why:

  • this becomes best-effort quota, not strict quota

  • unsuitable for hard multi-tenant isolation

4. Use distributed local credits from day one#

Deferred.

Why:

  • improves scalability under hotspot tenants

  • but adds bounded over-reservation / debt complexity

  • premature before we prove a single tenant quota row is a bottleneck

Open Questions#

  1. Should the first strict implementation cover only tenant-level quota, or also domain/object_set scopes?

  2. Should object accounting reuse route metadata for committed length, or keep a distinct object-accounting row? This doc recommends a distinct row.

  3. Do we need a separate logical write id to make finalize/abort fully idempotent across client retries?

  4. For batch writes, do we want all-or-nothing semantics only, or eventually partial acceptance with per-item results?

  5. Should the initial reconciler be admin-driven only, or should we also run a lightweight background worker in the client/runtime?

  6. Do we want the old enforce_namespace_quota(...) hook to remain as an early fast-fail hint even after strict metadata reservation exists?

Contents