[RFC]: Dynamic hot replication and heat-aware scheduling

## Summary

This RFC proposes dynamic hot replication with heat-aware scheduling for Mooncake Store.

The target problems are:

1. A hot object can make a single memory node the bottleneck when many consumers repeatedly read the same immutable object.
2. Repeated cross-domain reads can pay avoidable remote access cost when the same immutable object is consumed many times from another domain.

The first stage provides dynamic multi-replica fanout for hot immutable MEMORY objects. The second stage adds domain-aware placement and cross-domain warmup. The first-stage control model is centralized admission with distributed execution: Master owns the heat-admission decision, while Store workers execute copy tasks asynchronously.

## Goals

- Add a dynamic multi-replica mechanism for hot immutable objects stored in MEMORY segments.
- Use access frequency over a bounded Master-side time window as the first admission signal.
- Keep Master as the admission authority for heat threshold, metadata, leases, version fences, source selection, target selection, and copy task creation. Quota is reserved by the source-side `CopyStart` path and must roll back dynamic pending state on failure.
- Keep actual data copy distributed and asynchronous through Store-side `REPLICA_COPY` workers.
- Keep foreground read latency as the highest-priority constraint.
- Keep the feature off by default and provide observe/enforce modes for safe rollout.
- Reserve domain-aware fields in the proposal/lease API for the second stage.

## Non-goals

- TCP or transport-layer optimization.
- RL weight transport or mutable weight fanout.
- Compute-to-store cross-domain placement as an independent scheduling problem.
- A user-configured cross-domain cost matrix.
- Reader-local promotion in the first-stage PR.
- A separate shrink controller or active reclaim policy change in the first stage.
- Serving-layer P/D/RLD handoff or request routing.
- External framework integration contract for submitting expansion intents.
- A new general data-copy protocol.

## Target Scenarios

1. **Hot-node fanout in one domain.** Multiple consumers repeatedly read the same immutable object and overload one MEMORY segment or host.
2. **Cross-domain reusable cache reads.** Prefill and Decode may be explicitly deployed in different domains, or a Kubernetes cluster may naturally span zones, racks, or network domains without strict P/D placement. If a consumer domain repeatedly reads the same immutable KV / prefix cache / chunk from another domain, Mooncake should place a dynamic replica in the consumer domain.
3. **Cross-domain cold start.** When a new domain or store pool joins, Mooncake may warm selected hot objects into that domain so the first wave of traffic does not turn into a large number of remote misses.

For explicit cross-domain P/D deployments, this RFC only handles reusable hot data. A one-shot P-to-D KV handoff is still on the request critical path and should be handled by serving-layer latency masking or transfer-layer optimization.

## Decision Model

The first-stage design uses **centralized admission with distributed execution**.

Master observes reads from the `Get` / `BatchGet` path through `GetReplicaList` / `BatchGetReplicaList` and maintains a lightweight bounded heat window keyed by tenant and object key. A reader can trigger the flow by reading an object, but it is not the hotness authority. The foreground read path only records heat and queues a lightweight admission trigger; admission, placement, and task creation run in a Master background worker. Proposal-supplied hit count or QPS is not trusted as the admission signal.

When the heat threshold is crossed:

1. The foreground read path queues a lightweight, deduplicated admission trigger.
2. The background admission worker checks pending action, cooldown, replica limit, object version, object size, and placement.
3. The background admission worker selects the source replica and target segment.
4. The background admission worker grants a bounded lease and queues a `REPLICA_COPY` task.
5. The selected source Store worker executes the copy asynchronously.

This keeps the read-path Master work small: update a bounded counter and enqueue a deduplicated trigger. The heavier proposal path runs in the background, and actual data copy remains distributed so Master does not become a data-copy bottleneck.

`SubmitReplicaActionProposal` remains an internal MasterService control-plane entry for Mooncake Store. It is not exposed as an external MasterClient/RPC contract in the first PR. If upper-layer frameworks need to participate later, that should be a separate phase with an explicit external contract.

## Executor, Source, And Destination Policy

Dynamic replication uses source-side asynchronous copy in the first stage. Foreground reads may trigger admission, but replica creation must run in the background.

A replica plan is:

```text
plan = (source_replica, target_segment)
```

Master installs the pending lease/version state first, then creates the existing `REPLICA_COPY` task assigned to the selected source client. If task creation fails, Master rolls back the pending state. Dynamic `CopyStart` also verifies that the caller is the selected source client, and clears pending state if the dynamic start fails before a replication task is created. The source-side Store worker runs:

```text
CopyStart -> source -> target transfer -> CopyEnd
```

Reader-local promotion is intentionally excluded from the first-stage PR. It may avoid a second transfer in some cases, but it requires careful async buffer lifetime, version/integrity fencing, and failure handling. Since foreground read latency has the highest priority, this path should not be enabled until it has a separate design.

### Source Selection

The source-side copy policy is:

1. Prefer a readable MEMORY replica in the target domain if one exists, so further fanout stays domain-local.
2. Otherwise choose among readable MEMORY replicas by domain cost.
3. Under equal domain cost, prefer lower source/edge in-flight pressure when this signal is available.
4. Under equal pressure, use a stable tie-breaker so proposals do not always use the first replica returned by metadata iteration.

The first PR implements the stable tie-breaker for same-cost source candidates. Domain cost and in-flight pressure are second-stage extensions.

### Destination Selection

Destination selection is always done by Master.

The policy is:

1. In the domain-aware stage, the destination must belong to `target_domain`; if no valid target exists in that domain, reject the proposal.
2. Respect `preferred_target_segment` only if it is valid, allocatable, has enough free capacity, and belongs to the target domain when domain-aware placement is enabled.
3. Avoid placing a dynamic replica on a host that already has a readable replica when another valid target exists.
4. Prefer lower utilization among valid targets.
5. Use a stable tie-breaker for equal-score targets.

## End-To-End Flow

```mermaid
sequenceDiagram
participant Reader as "Reader / Store client"
participant Master as "Mooncake Master"
participant Source as "Source Store worker"
participant Target as "Target segment"

Reader->>Master: "Get / BatchGet"
Master->>Master: "Update bounded per-key heat window"
Master-->>Reader: "Replica list"

alt "Heat threshold not reached"
Master->>Master: "No expansion"
else "Heat threshold reached"
Master->>Master: "Queue lightweight admission trigger"
Master->>Master: "Background worker: admission / source / target"
Master->>Source: "Queue REPLICA_COPY task"
Source->>Master: "FetchTasks"
Source->>Master: "DynamicReplicaCopyStart(lease, version)"
Source->>Target: "Async source -> target transfer"
Source->>Master: "DynamicReplicaCopyEnd(lease, version)"
Master->>Master: "Mark dynamic replica readable"
end
```

```mermaid
flowchart LR
A["Get / BatchGet"] --> B["Master updates heat window"]
B --> C{"Threshold crossed?"}
C -->|"no"| D["Return replica list only"]
C -->|"yes"| E["Queue background admission trigger"]
E --> F{"Background admission accepted?"}
F -->|"no"| G["Reject / suppress by reason"]
F -->|"yes"| H["Background worker queues source-side REPLICA_COPY"]
H --> K["Source Store worker copies asynchronously"]
K --> J["Dynamic replica becomes readable"]
```

## Proposal Contract

A proposal contains:

- action type, currently `ADD`
- proposal id for idempotency
- tenant id and object key
- requester domain, reserved for the domain-aware stage and rejected when non-empty in the first PR
- observed object version
- expected object size
- target domain hint, reserved for the domain-aware stage and rejected when non-empty in the first PR
- optional preferred target segment
- proposal expiration timestamp

The proposal does not carry trusted hit count or QPS. Master admits expansion only from its own heat window.

Master rejects proposals that are expired, contain first-stage unsupported domain hints, are below Master-side admission threshold, inconsistent with the current object version or size, already in-flight, above the dynamic replica limit, under recreate cooldown, or impossible to place.

Repeated submissions with the same proposal id return the same lease only when the request content matches. Conflicting reuse of a proposal id is rejected.

## Lease And Version Fence

An accepted proposal returns a `ReplicaActionLease` binding proposal id, lease id, tenant id, key, source segment, target segment, target domain, object version, expiration timestamp, and task id.

The dynamic `REPLICA_COPY` task payload carries the accepted lease id and object version. Master publishes the task only after the pending lease state is installed. The Store task worker uses dynamic-specific copy RPCs so ordinary copy RPC compatibility is preserved.

`DynamicReplicaCopyStart` validates the lease, target, source, expiration, and object version before reserving target quota. If quota reservation fails, dynamic pending state is cleared so the key is not stuck behind a failed copy. This prevents stale proposals from creating replicas after the object has changed.

`DynamicReplicaCopyEnd` and `DynamicReplicaCopyRevoke` must present the same lease id and version recorded in the in-flight replication task. A stale task therefore cannot complete or revoke a newer pending copy for the same object.

## Admission Policy

The first-stage admission policy is intentionally simple:

- Use access frequency over a sliding Master-side heat window.
- Accept when the derived hit count reaches `dynamic_replication_admission_qps_threshold * dynamic_replication_heat_window_seconds`.
- Keep the minimum hit count at least one so very short windows do not replicate from invalid arithmetic.
- Limit dynamic MEMORY replicas per object with `dynamic_replication_max_memory_replicas`.

Default values are conservative:

- mode: `off`
- heat window: 10 seconds
- admission threshold: 0.8 QPS
- max dynamic memory replicas: 2

The second-stage admission key becomes `tenant + key + requester_domain`. A key that is globally hot is not enough to create a cross-domain replica; it must be hot from the consumer domain that would receive the replica.

## Domain Model

The second stage keeps the topology model to two layers:

```text
same domain < cross domain
```

`same host` is not a separate topology level. It is used only as an anti-affinity hint inside one domain: if another valid target exists in the target domain, Mooncake should avoid placing a dynamic replica on the same host as an existing hot replica because that does not relieve the host NIC or memory bottleneck.

Each MEMORY segment belongs to a domain. Empty or unset domains map to `default`.

The initial user-facing configuration only needs a domain identity, such as:

```text
MOONCAKE_STORE_DOMAIN=domain-a
```

Mooncake may keep an internal `DomainCost(requester_domain, candidate_domain)` helper for future extension, but the initial policy is fixed:

```text
same domain = 0
cross domain = 1
```

There is no user-configured N-by-N cost matrix in this stage.

## Shrink And Eviction Interaction

Dynamic replication does not introduce an independent shrink controller. Replica reduction is delegated to Mooncake's existing MEMORY eviction/reclaim path, using the existing eviction ratio and high-watermark controls.

When eviction or durable eviction-finalize removes a dynamic replica id, Master removes the corresponding dynamic replica record and records a short recreate-after timestamp on the object. During that interval, new hotness admission for the same object is rejected so admission does not immediately rebuild the capacity that reclaim just freed.

In the second stage, this cooldown should become domain-scoped. Evicting a dynamic replica from `domain-b` should block immediate recreation in `domain-b`, but it should not block another domain that still needs its own local replica.

## Existing Remote Replica Selection

Mooncake already has an opt-in remote replica scoring path for client-side read selection. Local MEMORY still wins first. When no local MEMORY replica exists, remote MEMORY replicas keep Master return order by default; setting `MC_STORE_REPLICA_SCORING=1` enables the built-in scorer, which prefers RDMA over TCP. Equal-score replicas still keep Master return order, so this is remote-replica preference rather than equal-cost load spreading.

This RFC does not change that read-side policy. Deployments that validate remote dynamic replicas should enable `MC_STORE_REPLICA_SCORING=1` when they rely on remote-replica preference. Same-tier load spreading can be added later through the existing scorer hook or a dedicated selection policy.

## Configuration

The first stage adds:

- `dynamic_replication_mode`: `off`, `observe`, or `enforce`
- `dynamic_replication_heat_window_seconds`
- `dynamic_replication_admission_qps_threshold`
- `dynamic_replication_max_memory_replicas`

The second stage should avoid adding a user-visible cost matrix or many placement knobs. Domain identity is the only planned new configuration surface.

## Observability

The first stage should expose:

- hot-read observations and would-propose count in observe mode
- admission accepted, rejected, and rejection reason
- dynamic copy task created, completed, failed, and revoked
- current dynamic replica count
- recreate cooldown hit count

The second stage should add domain-aware labels where useful:

- requester domain and target domain on proposals
- same-domain vs cross-domain copy count and bytes
- target-domain already-has-replica suppressions
- cross-domain copy inflight count

Metrics should stay aggregated; the system should not expose high-cardinality per-key metrics by default.

## Test Plan

The initial PR adds focused unit coverage for:

- Master-side hot admission queues a copy
- enforce-mode `Get` path auto expansion after threshold crossing
- enforce-mode `BatchGet` path auto expansion after threshold crossing
- observe mode does not queue a copy
- max replica limit suppresses fanout
- below-threshold admission is rejected
- proposal idempotency returns the same lease
- conflicting idempotency requests are rejected
- non-empty requester/target domain hints are rejected before domain-aware placement lands
- short proposal deadlines clamp the returned lease deadline
- copy lifecycle marks dynamic replica completion
- invalid target cleanup removes incomplete dynamic replica state
- heat-window cleanup is bounded at the entry limit and avoids a full read-path scan
- stale dynamic task without pending state is rejected
- non-source clients cannot execute dynamic `CopyStart`
- dynamic `CopyStart` failure clears pending state before ordinary Copy retry
- stale `CopyStart` does not clear a newer pending action
- expired dynamic pending state does not block ordinary Copy
- expired pending dynamic leases retire unconsumed pending copy tasks
- expired dynamic copy task cleanup removes dynamic state and enters recreate cooldown
- version mismatch rejects `DynamicReplicaCopyStart`
- expired lease rejects `DynamicReplicaCopyStart`
- mismatched lease/version rejects `DynamicReplicaCopyEnd` and `DynamicReplicaCopyRevoke`
- evicted dynamic replica blocks immediate recreate
- source selection uses stable tie-breaking instead of always choosing the first readable replica
- target selection avoids an existing replica host when another valid host exists

Second-stage tests should cover:

- requester-domain admission is independent across domains
- target selection chooses a segment in the requester or target domain
- invalid preferred target outside the target domain falls back to another valid target
- proposal is rejected when the target domain has no valid segment
- an existing readable replica in the target domain suppresses cross-domain copy
- same-domain fanout still works after a target-domain replica exists
- eviction cooldown is scoped to the evicted domain
- concurrent proposals for the same key/domain are single-flight
- warmup skips objects that already exist in the target domain and respects copy limits

ACK validation should include both explicitly separated P/D pools and a naturally cross-domain Kubernetes layout across zones or racks.

## Rollout

1. Merge disabled by default.
2. Upgrade Master and Store clients before enabling `enforce`; mixed deployments where old Store workers consume dynamic `REPLICA_COPY` payloads are not supported by this first-stage PR.
3. Enable `observe` mode in test clusters to validate heat signal quality and would-propose volume.
4. Enable `enforce` mode for selected tenants or domains with source-side async copy baseline.
5. Add domain-aware target scoring and domain-scoped cooldown after deployment data confirms the basic proposal/lease lifecycle.
6. Add controlled cross-domain warmup after the domain-aware placement path is stable.
7. Consider external framework integration only after a separate contract is designed.

## Related Work

- #2516 discusses topology- and load-aware remote replica selection.
- #2509 discusses bounded proactive promotion.
- PDD focuses on explicit cross-domain P/D serving and request-path KV handoff. This RFC does not implement PDD-style RLD or serving routing; it keeps Mooncake focused on reusable hot data placement and warmup.

## Checklist

- [x] I have searched existing issues and documentation before opening this RFC.

Start with the RFC’s Decision Model and Executor, Source, And Destination Policy, then trace Get/BatchGet, GetReplicaList/BatchGetReplicaList, SubmitReplicaActionProposal, and the Store-side CopyStart/CopyEnd flow. Done means the first-stage, off-by-default dynamic MEMORY replication behavior matches the specified admission, lease/version, quota-rollback, asynchronous REPLICA_COPY, and placement rules.

Written by the indexing model from the issue text.