[Feature Request]: Hierarchical Eviction with Assign / Evict / Fallback

### Describe your feature request

# Discussion Draft: Hierarchical Eviction with Assign / Evict / Fallback

## Background

The current [type-aware eviction PR](https://github.com/kvcache-ai/Mooncake/pull/2746) shows that Mooncake Store needs a way to distinguish eviction semantics across object data types. For example, Hidden State and KV Cache differ in cache granularity, reuse interval, recomputation cost, and serving impact. They should not always be ranked by the same global lease-time ordering.

However, if each new policy is implemented directly inside `MasterService`, the master service will become increasingly complex as we add tenant-aware, type-aware, cost-aware, or other future eviction policies.

One possible direction is to model eviction policy as a small set of composable operations rather than as policy-specific branches embedded in `MasterService`.

## Core Idea

The policy layer can be expressed using three basic operations:

```text
Assign
Evict
Fallback
```

These operations are policy-side planning operations. They do not directly mutate metadata or remove replicas. `MasterService` remains responsible for safe execution.

### Assign

`Assign` partitions a candidate set by some dimension and assigns an eviction target to each child scope.

The partition dimension can be tenant, object data type, model, priority, namespace, or another future policy dimension.

For example:

```text
global_scope
-> Assign(by tenant)
-> tenant A scope + A_evict_ratio + A_evict_ratio_lowerbound
-> tenant B scope + B_evict_ratio + B_evict_ratio_lowerbound
```

Inside each tenant, the policy can continue partitioning by object data type:

```text
tenant B scope
-> Assign(by type)
-> tenant B / KV Cache scope + KV_evict_ratio + KV_evict_ratio_lowerbound
-> tenant B / Hidden State scope + Hidden_evict_ratio + Hidden_evict_ratio_lowerbound
```

In this model, tenant and type are not hard-coded hierarchy levels in the framework. They are just different ways to use `Assign`.

The assigned target can be represented as a ratio or as bytes. For memory pressure, bytes are often the more natural responsibility unit, while ratios are useful for compatibility with the current `BatchEvict` semantics.

### Evict

`Evict` selects victims within the current scope according to that scope's ranking policy.

It does not cross the scope boundary. For example, when running inside `tenant B / Hidden State`, it only selects victims from Hidden State candidates belonging to tenant B.

Different scopes can use different ranking policies:

- KV Cache can use a lease/LRU-like policy.
- Hidden State can use a policy that accounts for longer reuse intervals and higher recomputation cost.
- Unknown or general types can use the default lease-based policy.

`Evict` only produces a planned victim list. It does not modify metadata, release quota, remove replicas, or interact with offload state.

### Fallback

`Fallback` is used when child scopes fail to satisfy the lowerbound target of their parent scope. It selects additional victims inside the parent scope while relaxing the child partition boundaries.

For example, if type-scoped eviction inside a tenant cannot satisfy that tenant's lowerbound target, the policy should first fall back within that tenant rather than immediately shifting pressure to other tenants:

```text
tenant B scope
-> Fallback(tenant scope)
```

This means the policy can select from all remaining candidates in tenant B, without strictly preserving the original type-level split.

If all tenant scopes together still cannot satisfy the global lowerbound target, the policy can then use a global fallback:

```text
global_scope
-> Fallback(global scope)
```

Global fallback should not degenerate into raw lease-time ordering. It should still be able to consider tenant pressure and type pressure, so that fallback does not systematically punish scopes that are not the main source of memory pressure.

Fallback only relaxes policy partition boundaries. It does not relax execution safety boundaries. Hard pin, soft pin, group semantics, offload behavior, replica refcount, quota accounting, and metadata correctness are still enforced by `MasterService` during execution.

## Composed Flow

Using these three operations, a hierarchical eviction policy can be expressed as:

```text
global_scope
-> Assign(by tenant)
-> for each tenant_scope:
-> Assign(by type)
-> for each type_scope:
-> Evict(type policy)
-> Fallback(tenant scope)
-> Fallback(global scope)
```

This flow expresses several principles:

1. Assign responsibility before selecting victims.
2. Prefer eviction inside more specific scopes first.
3. If child scopes cannot satisfy the parent target, fall back within the parent scope first.
4. Only when the parent scope still cannot satisfy the target should the policy fall back to a higher-level scope.

## Relationship With MasterService

`MasterService` does not need to understand each policy's internal rules. It only needs to provide the mechanism around policy planning:

1. Build a lightweight candidate view.
2. Execute the policy's plan with revalidation.
3. Report actual eviction progress back to the policy flow.

The candidate view can be produced by the existing metadata scan. It should contain object identity and a small set of policy-relevant attributes, such as tenant, data type, memory footprint, lease state, and pin state.

The candidate view should not be a full metadata snapshot. It should not copy complete `ObjectMetadata`, replica lists, group membership, or segment state.

When executing eviction, `MasterService` uses the candidate reference to locate the real metadata again, revalidates whether the object is still evictable, and then handles group eviction, offload-on-evict, quota release, replica removal, metrics, and metadata erase.

Therefore, the policy layer owns decision-making, while `MasterService` owns mutation and correctness.

## Execution Feedback

Whether `Fallback` is needed should be based on actual execution progress, not only on the policy's estimated plan.

A planned victim may fail during execution because:

- the object no longer exists;
- the lease was renewed;
- the object became hard pinned or soft pinned;
- the memory replica is no longer evictable;
- a group member prevents safe group eviction;
- offload-on-evict defers immediate memory release.

For this reason, `MasterService` should execute each planned stage and report the actual evicted bytes or objects. If the actual result of child scopes does not satisfy the parent lowerbound, the policy flow proceeds to the corresponding `Fallback`.

This preserves the current revalidation model while allowing the policy layer to express hierarchical responsibility.

## Why This Abstraction May Be Useful

This abstraction is more general than hard-coding a tenant/type hierarchy.

If a future policy needs a new dimension such as model, priority, object group, or business namespace, it can be expressed as another `Assign` rule rather than a new top-level eviction framework.

If a future object type needs a new ranking strategy, it can be expressed as a different `Evict` policy for that scope.

If a child scope cannot satisfy its target, the same `Fallback` semantics can be reused instead of creating separate special cases for type fallback, tenant fallback, and global fallback.

## Summary

`Assign / Evict / Fallback` can serve as a minimal abstraction for hierarchical eviction policy.

It can express:

```text
global -> tenant -> type -> victim
```

while also supporting future dimensions.

More importantly, it separates policy decision-making from `MasterService`, while preserving `MasterService` as the owner of metadata correctness and safe eviction execution.

### Before submitting a new issue...

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