[Performance]: segment utilization imbalance with heterogeneous segment sizes

### Describe your performance question

## Summary

When mooncake-store is deployed with segments of different sizes, the larger segments consistently show lower utilization than the smaller ones. After digging into the allocation and eviction code, we believe this is structural: **allocation is capacity-blind (uniform per segment), and eviction is segment-blind (global watermark + global LRU-by-lease)**. Neither side has a feedback mechanism to balance utilization across heterogeneous segments.

We don't have a solution we're fully happy with (see "What we considered" below — including `free_ratio_first`, which helps but has its own issues), so we'd like to open this up for discussion.

## Our deployment & observation

Mooncake Version: v0.3.9

10 memory segments across 5 nodes, two different sizes (node IPs anonymized):

| Segment | Allocated | Capacity | Used |
|---|---|---|---|
| node-A:1 | 366.52 GiB | 400 GiB | 91.6% |
| node-A:2 | 366.33 GiB | 400 GiB | 91.6% |
| node-B:1 | 366.41 GiB | 400 GiB | 91.6% |
| node-B:2 | 366.31 GiB | 400 GiB | 91.6% |
| node-C:1 | 366.38 GiB | 400 GiB | 91.6% |
| node-C:2 | 366.46 GiB | 400 GiB | 91.6% |
| node-D:1 | 366.41 GiB | 400 GiB | 91.6% |
| node-D:2 | 366.30 GiB | 400 GiB | 91.6% |
| node-E:1 | 867.53 GiB | 1000 GiB | 86.8% |
| node-E:2 | 867.54 GiB | 1000 GiB | 86.8% |

Global: 4.56 TiB / 5.08 TiB (90%). Workload is an LLM prefix-KV-cache pool (SGLang HiCache L3 backend), default `random` allocation strategy, eviction parameters (`eviction_high_watermark_ratio=0.9`, `eviction_ratio=0.05`).

The 1000 GiB segments are **always** ~5 percentage points below the 400 GiB ones, not just transiently. Note also that the eight 400 GiB segments sit at a suspiciously tight 91.6% — this appears to be their practical fill ceiling (allocation failures from fragmentation), not a coincidence of timing.

## Why this happens (code analysis)

### 1. Allocation is capacity-blind

`RandomAllocationStrategy::Allocate` (mooncake-store/include/allocation_strategy.h) picks a segment **uniformly at random over segment names**, regardless of capacity or free space. A 1000 GiB segment gets exactly the same write inflow as a 400 GiB one. The only way a large segment absorbs more data is *spillover*: a random pick lands on a full segment, fails, and the retry loop walks to the next segment that still has space.

The steady-state dynamics that follow: small segments fill up and pin at their ceiling; large segments spend most of the time "catching up" via spillover, so any snapshot shows them at lower utilization.

### 2. Eviction is segment-blind

`MasterService::BatchEvict` (mooncake-store/src/master_service.cpp) evicts by lease age across all metadata shards, with no awareness of which segment a replica lives on. There is no per-segment watermark and no way to relieve pressure on a specific segment. The trigger is also global-only:

- the global watermark path fires when `global_used_ratio > eviction_high_watermark_ratio`;
- otherwise eviction waits for `need_eviction_`, which is only set after a `PutStart` fails to allocate on **every** segment.

### 3. The two interact badly

With our topology the small segments cap out at ~91.6%, so the global used ratio mathematically cannot reach the default 0.95 watermark (`(8×366 GiB + 2×1000 GiB) / 5200 GiB ≈ 94.8%`). The watermark path therefore **never fires**, and eviction is driven entirely by the allocation-failure fallback. Each cycle ends with a window of client-visible `NO_AVAILABLE_HANDLE` write failures, followed by a bulk eviction of ~5% of all objects (~250 GiB of cache dropped at once in our case), then refill — a sawtooth in both write success rate and hit rate.

## Why this matters

1. **RDMA traffic imbalance / network pressure.** Since the small segments are pinned at their ceiling most of the time, nearly all spillover writes concentrate on whichever node hosts the remaining free space. In our deployment both 1000 GiB segments are on the same node, so that single node's NIC absorbs the bulk of cluster write bandwidth for most of each cycle — and since it holds the freshest data, read traffic skews there too.
2. **Lower achievable utilization.** The large segments structurally idle below their ceiling, and the unreachable global watermark means the cluster oscillates around 90% instead of its actual allocatable maximum.
3. **Periodic write-failure windows and bulk cache eviction**, as described above — particularly painful for a KV-cache workload where hit rate is the whole point.

## What we considered

- **Operational workaround: make all segments the same size** (e.g. mount the 1000 GiB nodes as multiple smaller segments). This fixes the inflow share by construction, but it's a per-deployment workaround, not a fix — heterogeneous fleets are common (mixed RAM configs, partial reservations on some nodes).
- **`FreeRatioFirstAllocationStrategy`** (already in the codebase): sorts sampled candidates by free ratio and greedily picks the emptiest. This does equalize utilization percentages in steady state, but the greedy choice introduces a new problem: **the emptiest segment wins almost every allocation until it catches up**. A freshly (re)mounted segment — e.g. after a node restart — has free ratio 1.0 and absorbs nearly the entire cluster write bandwidth until it reaches parity, which is a single-node write storm on exactly the node that just came back. The strategy comment frames "new empty segments naturally win" as a feature, but for large segments this is a long, severe transient. It also does nothing for the eviction side (the unreachable watermark and segment-blind eviction remain).
- **Lowering `eviction_high_watermark_ratio` / `eviction_ratio`** so the watermark path fires before allocation failures and evicts in smaller steps. This mitigates the sawtooth but requires knowing each deployment's fragmentation ceiling, and still does nothing for the utilization/traffic imbalance.

## Possible directions (for discussion)

None of these is obviously right; we'd love input from the community:

1. **Weighted-random allocation** — pick segments with probability proportional to free bytes (or power-of-two-choices: sample two, take the one with more free space). Smooths the hotspot problem that greedy free-ratio-first has, while still converging to balanced utilization. Could be a new strategy or a fix to `free_ratio_first`.
2. **Inflow cap / ramp-up for (re)mounted segments**, so an empty segment doesn't absorb the whole cluster's write bandwidth regardless of strategy.
3. **Per-segment eviction watermark** — let the eviction thread also react to individual segments above a threshold, and/or make `BatchEvict` prefer evicting replicas on pressured segments (the candidate selection currently ignores placement entirely).
4. **Make the global watermark meaningful under heterogeneity** — e.g. compute used ratio against *practically allocatable* capacity, or trigger on `max(per-segment ratio)` instead of the global average, so eviction doesn't degenerate to the allocation-failure path.

### Before submitting a new issue...

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