[RFC]: Multi-Replica Reliability in Mooncake Store Data Plane

### Changes proposed

## Background

Mooncake Store ensures data reliability through a **Multi-Replica** mechanism: `replica_num` controls the number of Memory replicas and `nof_replica_num` controls the number of NoF SSD replicas. Multi-replication (`replica_num` + `nof_replica_num`) provides cross-node fault tolerance — the same object is replicated across multiple physical nodes, so that if one node fails, other replicas remain readable. This document analyzes the current state of the multi-replica mechanism, including allocation logic, failure handling behavior, and potential gaps.

---

## 1. Replica Allocation Mechanism

### 1.1 Allocation Entry Point

Replica counts are specified via `ReplicateConfig` in `PutStart` / `UpsertStart` requests:

- `replica_num` — number of Memory replicas
- `nof_replica_num` — number of NoF (NVMe-oF) SSD replicas

Core allocation function `AllocateAndInsertMetadata` (`master_service.cpp:2838`):

```cpp
// Step 1: Allocate Memory replicas
if (config.replica_num > 0) {
auto allocation_result = allocation_strategy_->Allocate(
allocator_manager, value_length, config.replica_num,
preferred_segments, {}, ReplicaType::MEMORY, ssd_provider);
replicas = std::move(allocation_result.value());
}

// Step 2: Allocate NoF SSD replicas (optional)
if (config.nof_replica_num > 0) {
auto allocation_result = allocation_strategy_->Allocate(
allocator_manager, value_length, config.nof_replica_num,
preferred_segments, {}, ReplicaType::NOF_SSD);
// Merge into replicas
}
```

### 1.2 Cross-Node Placement Guarantee

`AllocationStrategy::Allocate()` uses a `used_segments` set to ensure different replicas of the same object are placed on different segments:

> "replicas are guaranteed to be placed on different segments to ensure redundancy"
> — `allocation_strategy.h:130-138`

The allocation strategy achieves physical dispersion by distributing memory blocks across different segments. `GetReplicaSegmentNames()` returns the list of segment names where all replicas reside.

Two built-in strategies:
- `RandomAllocationStrategy` — random selection, up to 100 retries
- `FreeRatioFirstAllocationStrategy` — prefers segments with the highest free ratio, balancing load

### 1.3 Three Write Modes (`ReplicaWriteMode`)

| Mode | Condition | Semantics |
|------|-----------|-----------|
| `SINGLE_REPLICA` | `replica_num=1 && nof_replica_num=0` | Single replica — fails on error |
| `FLEXIBLE_DUAL_REPLICA` | `replica_num=1 && nof_replica_num=1` | Memory + NoF dual-write — at least one success is sufficient |
| `RELIABLE_MULTI_REPLICA` | All other cases | Must fully satisfy the requested count — strict mode |

`FLEXIBLE_DUAL_REPLICA` is an interesting degradation design: Memory and NoF back each other up; if only one can be allocated, it still counts as success.

---

## 2. Replica Handling on Node Failure

### 2.1 Core Function: `ClearInvalidHandles`

`master_service.cpp:1904` — triggered when a client expires (TTL timeout) or a segment is unmounted:

```
CleanupStaleHandles filter criteria (any one matches, and status must be COMPLETE):
1) has_invalid_mem_handle() — the owning Memory segment has been unmounted
2) has_invalid_nof_handle() — the owning NoF segment has been unmounted
3) has_stale_local_disk_client(alive_clients) — client is no longer alive
```

`ClearInvalidHandles` iterates over all tenant metadata, calling `CleanupStaleHandles` for each object:
- Removes invalid replicas
- If the object has no valid replicas remaining (`!metadata.IsValid()`), **the entire object metadata is also deleted**

### 2.2 Key Behavior: Delete-Only, No Replenishment

After removing invalid replicas, the replica count drops from N to N-1 (or 0). **No automatic rebuild is triggered.**

On node failure:
- `replica_num=2`, one replica on the failed node, one on a healthy node
→ invalid replica deleted, 1 replica remains in service (not reduced to 0)
- `replica_num=1`, the only replica is on the failed node
→ invalid replica deleted, 0 remain → object metadata deleted → **data loss**

### 2.3 Absence of Automatic Repair

A full search of the `mooncake-store` source tree:

| Keyword | Result |
|---------|--------|
| `auto_repair` | Not found |
| `replenish` | SPDK pool replenishment only, unrelated to replicas |
| `rebalance` | Memory pool slab rebalancing only, unrelated to replicas |
| `repair` | LRU index lazy repair for storage backend only, unrelated to replicas |

**There is no logic anywhere for automatic replica replenishment.**

### 2.4 `ReplicaStatus::FAILED` Defined but Unused

`replica.h:51` defines `ReplicaStatus::FAILED` with the comment "can be used for reassignment", yet no code in the current codebase marks a replica as FAILED or triggers reallocation based on this state. The existence of this enum value suggests the author reserved an entry point for replica reassignment at design time, but it was never implemented.

### 2.5 Practical Impact

- Replica count = 1, no offload: node failure → immediate data loss
- Replica count = 2, one node fails: remaining replica is readable, but replica count permanently drops to 1; a subsequent second node failure causes data loss
- **The system never automatically restores the desired replica count**; the upper layer must detect this and re-issue Put/Upsert

---

## 3. Summary — Current Reliability Gap

The current multi-replica mechanism provides "static allocation + passive deletion" but lacks an "active repair" step:

```
┌──────────────────┐
│ PutStart │ replica_num=2 → allocate 2 replicas on different nodes
│ replica_num=2 │ ✅ Dispersed placement
└────────┬─────────┘
▼
┌──────────────────┐
│ Normal │ 2 replicas both COMPLETE
│ operation │
└────────┬─────────┘
▼ Node A crashes
┌──────────────────┐
│ TTL timeout │ ClientMonitorFunc detects the failure
│ (10s) │
└────────┬─────────┘
▼
┌──────────────────┐
│ ClearInvalid- │ Replica on Node A deleted → 1 replica remains
│ Handles │ Data still readable, but replica count permanently drops to 1
└──────────────────┘
❌ Stops here — the 2nd replica is never automatically replenished
```

---

## 4. Discussion Topics

The following improvement directions are proposed based on the analysis above:

1. **Automatic Replica Repair**: When `ClearInvalidHandles` causes the replica count to fall below the desired level, should the system automatically trigger replica rebuild (allocate a new replica on a healthy node + copy data from an existing healthy replica)?

2. **Implementing `ReplicaStatus::FAILED`**: The FAILED status is defined but unused — the comment "can be used for reassignment" suggests it was intended as a reassignment entry point. Should it serve as the starting state for an automatic repair state machine?

3. **Recording the Desired Replica Count**: Currently, metadata stores only the actual `replicas_` list with no record of the "desired replica count", meaning the system does not know how many replicas were originally requested after a failure. Should this be persisted?

4. **`--replica_num` Global Default**: Currently, `replica_num` in `PutStart` / `UpsertStart` is entirely caller-specified, and the Master has no command-line global default. Should startup flags `--replica_num` / `--nof_replica_num` be added as a fallback?

Semantics: "default value + per-request override":

```
Request-specified value > CLI --replica_num > Hard-coded fallback (1)
(highest priority) (second priority) (lowest priority)
```

- `PutStart` without `replica_num` → uses CLI default
- `PutStart` with `replica_num=3` → uses the request's own value

---

## 5. Key Source Code Index

| Concern | File | Location |
|---------|------|----------|
| `ReplicaStatus` enum | `mooncake-store/include/replica.h` | Lines 51-58 |
| `ReplicaWriteMode` modes | `mooncake-store/include/replica.h` | Lines 150-165 |
| Replica allocation | `mooncake-store/src/master_service.cpp` | `AllocateAndInsertMetadata` (line 2838) |
| Allocation validation | `mooncake-store/src/master_service.cpp` | `HasExpectedReplicaAllocation` (line 121) |
| Failure cleanup | `mooncake-store/src/master_service.cpp` | `ClearInvalidHandles` (line 1904) |
| Stale handle filtering | `mooncake-store/src/master_service.cpp` | `CleanupStaleHandles` (line 4797) |
| Object validity check | `mooncake-store/include/master_service.h` | `ObjectMetadata::IsValid` (line 1141) |
| Segment name retrieval | `mooncake-store/include/master_service.h` | `GetReplicaSegmentNames` (line 1148) |
| Allocation strategy base | `mooncake-store/include/allocation_strategy.h` | Cross-node guarantee comment (line 130) |
| Random allocation | `mooncake-store/include/allocation_strategy.h` | `RandomAllocationStrategy::Allocate` (line 226) |
| Free-ratio-first | `mooncake-store/include/allocation_strategy.h` | `FreeRatioFirstAllocationStrategy::Allocate` (line 406) |
| PutStart | `mooncake-store/src/master_service.cpp` | Line 3055 |
| UpsertStart replica swap | `mooncake-store/src/master_service.cpp` | Line 3761 |

### 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 mooncake-store/include/replica.h and the allocation and cleanup paths in mooncake-store/src/master_service.cpp: AllocateAndInsertMetadata, ClearInvalidHandles, CleanupStaleHandles, PutStart, and UpsertStart. Review ObjectMetadata in mooncake-store/include/master_service.h and the allocation strategies in allocation_strategy.h. The issue presents several design options, so the implementation scope and acceptance criteria must be decided before “done” can be defined.

Written by the indexing model from the issue text.