kvcache-ai/Mooncake

Fork 0

mirror of https://github.com/kvcache-ai/Mooncake.git synced 2026-11-05 01:17:55 +00:00

Fallback #725

New issue

Closed

opened 2026-10-29 21:18:44 +00:00 by bsakaguchi · 3 comments

bsakaguchi commented

2026-10-29 21:18:44 +00:00

Owner

Originally created by @kanceler on GitHub (Jul 8, 2026).
Original GitHub issue: https://github.com/kvcache-ai/Mooncake/issues/2791

Originally assigned to: @kanceler on GitHub.

Describe your feature request

Discussion Draft: Hierarchical Eviction with Assign / Evict / Fallback

Background

The current type-aware eviction PR 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:

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:

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:

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:

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:

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:

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:

Assign responsibility before selecting victims.
Prefer eviction inside more specific scopes first.
If child scopes cannot satisfy the parent target, fall back within the parent scope first.
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:

Build a lightweight candidate view.
Execute the policy's plan with revalidation.
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:

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

Originally created by @kanceler on GitHub (Jul 8, 2026). Original GitHub issue: https://github.com/kvcache-ai/Mooncake/issues/2791 Originally assigned to: @kanceler on GitHub. ### 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/)

bsakaguchi

2026-10-29 21:18:44 +00:00

closed this issue
added the
stale

auto-closed
labels

bsakaguchi commented

2026-10-29 21:18:45 +00:00

Author

Owner

@github-actions[bot] commented on GitHub (Jul 8, 2026):

Thanks for opening this issue, @kanceler!

Field	Value
Issue	#2791
GitHub user ID	`156038601`
Reporter	@kanceler

A maintainer will triage this when possible. To help us respond faster, please include:

Mooncake version or commit SHA
Environment (OS, CUDA/driver, RDMA stack if relevant)
Steps to reproduce and expected vs. actual behavior

Useful links: Documentation · Contributing guide

This message was posted automatically by the issue bot.

@github-actions[bot] commented on GitHub (Jul 8, 2026): Thanks for opening this issue, @kanceler! | Field | Value | |-------|-------| | **Issue** | #2791 | | **GitHub user ID** | `156038601` | | **Reporter** | @kanceler | A maintainer will triage this when possible. To help us respond faster, please include: - Mooncake version or commit SHA - Environment (OS, CUDA/driver, RDMA stack if relevant) - Steps to reproduce and expected vs. actual behavior Useful links: [Documentation](https://kvcache-ai.github.io/Mooncake/) · [Contributing guide](https://github.com/kvcache-ai/Mooncake/blob/main/CONTRIBUTING.md) > This message was posted automatically by the issue bot.

bsakaguchi commented

2026-10-29 21:18:45 +00:00

Author

Owner

@github-actions[bot] commented on GitHub (Oct 7, 2026):

This issue has had no activity for 90 days and will be closed in 7 days if there is no further activity. Please comment or react if it should stay open.

@github-actions[bot] commented on GitHub (Oct 7, 2026): This issue has had no activity for 90 days and will be closed in 7 days if there is no further activity. Please comment or react if it should stay open.

bsakaguchi commented

2026-10-29 21:18:45 +00:00

Author

Owner

@github-actions[bot] commented on GitHub (Oct 15, 2026):

Closing due to 3 months of inactivity. If this is still relevant, please comment and we can reopen.

@github-actions[bot] commented on GitHub (Oct 15, 2026): Closing due to 3 months of inactivity. If this is still relevant, please comment and we can reopen.

bsakaguchi referenced this issue

2026-10-29 21:30:13 +00:00

[PR #725] [CLOSED] [TransferEngine] Add cudaDeviceSynchronize after first address mapping #1773