kvcache-ai/Mooncake

Fork 0

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

[GH-ISSUE #3124] [RFC][Store] Selective candidate materialization for BatchEvict #800

New issue

Open

opened 2026-10-29 21:19:41 +00:00 by bsakaguchi · 2 comments

bsakaguchi commented

2026-10-29 21:19:41 +00:00

Owner

Originally created by @jacklin78911-collab on GitHub (Jul 26, 2026).
Original GitHub issue: https://github.com/kvcache-ai/Mooncake/issues/3124

Changes proposed

A draft implementation is available in #3118. This RFC documents the design, correctness boundaries, alternatives, and complexity trade-offs for review.

Background

MasterService::BatchEvict materializes a full candidate — including tenant identity and key — for every eviction-eligible object, and only then selects the oldest requested subset.

When the requested eviction target is a small fraction of the eligible population, most of that identity construction is discarded without being used. For example, with 1M eligible objects and a 1% target, roughly 1M full candidates are constructed in order to evict roughly 10K objects. The cost of preparing candidates is therefore governed by the eligible population rather than by the amount of work actually performed.

Because BatchEvict holds a snapshot_mutex_ shared lock for its duration, this preparation cost is also exported to control-plane operations that need the unique lock.

Related performance investigation: #2560.

Proposal

Keep the existing O(N) metadata census, but materialize full candidate identity only for:

the requested eviction frontier;
a bounded reserve absorbing execution-time revalidation failures;
additional candidates found through refill if that reserve is exhausted.

For high eviction ratios the existing single-pass full-materialization path is retained, since most eligible candidates would be needed anyway and the two-phase approach would otherwise add a census without reducing materialization. The ratio at which the implementation switches is not a tuned constant: it is the analytic point at which the reserve would already exceed the frontier limit, so it follows from the reserve-slack and frontier-limit parameters rather than being chosen independently.

Correctness

The change affects when full candidate identity is constructed, not eviction eligibility or execution semantics. The eligibility conditions used by the census are identical to those used when materializing, so the selected set matches what the census counted. Preserved unchanged:

oldest-first candidate selection;
execution-time lease revalidation;
soft-pin fallback;
whole-group eviction semantics;
replica constraints;
target and lower-bound behavior;
offload behavior.

Because metadata is read twice on the selective path, an object may stop being eligible between the census and materialization. Two guards cover this: if the frontier holds fewer objects than the target requires, the implementation falls back to full candidate collection so the eviction count is still derived from the requested target; and if the reserve is exhausted during execution, refill continues past the cutoff until the target is met.

Relation to prior work

Deferring construction of expensive full records until a selection has narrowed the candidate set is the late-materialization strategy studied in column-store query execution (Abadi et al., Materialization Strategies in a Column-Oriented DBMS, ICDE 2007). The same principle is widely used for top-K queries in analytical engines, which sort on lightweight keys or row identifiers and fetch wide columns only for the final rows, and which commonly disable the optimization when the requested fraction of rows is large.

This proposal claims no novelty in that principle. What is specific here is its adaptation to mutable eviction metadata: candidates can become ineligible between selection and execution, so the design adds a bounded reserve, execution-time revalidation, and refill, and it must preserve group, soft-pin, and replica semantics that have no counterpart in query execution.

Alternatives considered

Lease-timeout-ordered auxiliary index or expiration structure (the longer-term direction suggested in #2560, and feasible in principle given the auxiliary-index precedent in #1998). This would make candidate discovery approximately O(K log N) instead of O(N) per round. It is not proposed here because it moves cost onto the metadata write path: every Put, lease refresh, and removal would pay index maintenance, and consistency, shard lock ordering, and snapshot/recovery would all need to be addressed. Whether that trade is favorable depends on the per-object lease-update rate, which has not been measured; the ordered structure becomes attractive only when updates are infrequent relative to eviction rounds. This RFC deliberately keeps the change confined to BatchEvict and leaves that direction open.

Random sampling of candidates (as used by approximate-LRU caches to avoid maintaining a full ordering). This would avoid the census entirely and run in near-constant memory, but it changes observable behavior: exact oldest-first selection, exact target attainment, and reproducibility would all become approximate. Since existing behavior and tests depend on those semantics, sampling is not a drop-in alternative.

Single-pass bounded heap over the scan, materializing identity only on insertion. This needs one traversal instead of two and O(K + R) memory instead of O(N) timestamps, but it materializes more identities than the frontier approach (every object that transiently enters the heap), and per-thread heaps under the existing parallel scan would multiply that bound by the thread count. Which side wins depends on key width and on the cost ratio between an identity copy and a second traversal; this is an open empirical question rather than a settled one, and I would be glad to benchmark it if reviewers consider it worth resolving before merge.

Complexity

The metadata census remains O(N); this proposal does not reduce the scan, and the selective path traverses metadata twice.

What is reduced is full tenant/key identity materialization, from O(N) toward O(K + R) at low eviction ratios, where K is the requested eviction frontier and R is the bounded reserve.

Two cases limit that bound, and both fall back to existing behavior rather than failing:

if many objects share the cutoff timestamp, the frontier can hold more than K + R objects, so materialization degrades toward the current path;
if execution-time invalidation exhausts the reserve, a refill scan is performed, and under heavy churn the total materialization can likewise approach the current path.

Validation

The implementation adds deterministic tests that call BatchEvict directly, covering:

exact oldest-first selection;
exact target and lower-bound behavior;
soft-pin fallback;
whole-group eviction and group safety;
high-ratio full-materialization bypass;
execution-stage failures absorbed by the reserve;
reserve exhaustion followed by refill.

I could not find direct tests for these semantics in the upstream suite; existing eviction tests appear to reach BatchEvict indirectly through segment pressure and the background eviction thread. The added fixture therefore provides focused coverage for oldest-first ordering, target and lower-bound attainment, and candidate loss during execution-time revalidation, independently of the optimization itself.

Scope

This RFC intentionally does not change:

the eviction policy;
the ordering metric (lease_timeout);
the metadata layout;
the eviction target semantics.

The change only reduces unnecessary construction of full candidate identities after the eviction frontier has been identified.

Related implementation: #3118.

Originally created by @jacklin78911-collab on GitHub (Jul 26, 2026). Original GitHub issue: https://github.com/kvcache-ai/Mooncake/issues/3124 ### Changes proposed A draft implementation is available in #3118. This RFC documents the design, correctness boundaries, alternatives, and complexity trade-offs for review. ## Background `MasterService::BatchEvict` materializes a full candidate — including tenant identity and key — for every eviction-eligible object, and only then selects the oldest requested subset. When the requested eviction target is a small fraction of the eligible population, most of that identity construction is discarded without being used. For example, with 1M eligible objects and a 1% target, roughly 1M full candidates are constructed in order to evict roughly 10K objects. The cost of preparing candidates is therefore governed by the eligible population rather than by the amount of work actually performed. Because `BatchEvict` holds a `snapshot_mutex_` shared lock for its duration, this preparation cost is also exported to control-plane operations that need the unique lock. Related performance investigation: #2560. ## Proposal Keep the existing O(N) metadata census, but materialize full candidate identity only for: - the requested eviction frontier; - a bounded reserve absorbing execution-time revalidation failures; - additional candidates found through refill if that reserve is exhausted. For high eviction ratios the existing single-pass full-materialization path is retained, since most eligible candidates would be needed anyway and the two-phase approach would otherwise add a census without reducing materialization. The ratio at which the implementation switches is not a tuned constant: it is the analytic point at which the reserve would already exceed the frontier limit, so it follows from the reserve-slack and frontier-limit parameters rather than being chosen independently. ## Correctness The change affects *when* full candidate identity is constructed, not eviction eligibility or execution semantics. The eligibility conditions used by the census are identical to those used when materializing, so the selected set matches what the census counted. Preserved unchanged: - oldest-first candidate selection; - execution-time lease revalidation; - soft-pin fallback; - whole-group eviction semantics; - replica constraints; - target and lower-bound behavior; - offload behavior. Because metadata is read twice on the selective path, an object may stop being eligible between the census and materialization. Two guards cover this: if the frontier holds fewer objects than the target requires, the implementation falls back to full candidate collection so the eviction count is still derived from the requested target; and if the reserve is exhausted during execution, refill continues past the cutoff until the target is met. ## Relation to prior work Deferring construction of expensive full records until a selection has narrowed the candidate set is the late-materialization strategy studied in column-store query execution (Abadi et al., *Materialization Strategies in a Column-Oriented DBMS*, ICDE 2007). The same principle is widely used for top-K queries in analytical engines, which sort on lightweight keys or row identifiers and fetch wide columns only for the final rows, and which commonly disable the optimization when the requested fraction of rows is large. This proposal claims no novelty in that principle. What is specific here is its adaptation to mutable eviction metadata: candidates can become ineligible between selection and execution, so the design adds a bounded reserve, execution-time revalidation, and refill, and it must preserve group, soft-pin, and replica semantics that have no counterpart in query execution. ## Alternatives considered **Lease-timeout-ordered auxiliary index or expiration structure** (the longer-term direction suggested in #2560, and feasible in principle given the auxiliary-index precedent in #1998). This would make candidate discovery approximately O(K log N) instead of O(N) per round. It is not proposed here because it moves cost onto the metadata write path: every `Put`, lease refresh, and removal would pay index maintenance, and consistency, shard lock ordering, and snapshot/recovery would all need to be addressed. Whether that trade is favorable depends on the per-object lease-update rate, which has not been measured; the ordered structure becomes attractive only when updates are infrequent relative to eviction rounds. This RFC deliberately keeps the change confined to `BatchEvict` and leaves that direction open. **Random sampling of candidates** (as used by approximate-LRU caches to avoid maintaining a full ordering). This would avoid the census entirely and run in near-constant memory, but it changes observable behavior: exact oldest-first selection, exact target attainment, and reproducibility would all become approximate. Since existing behavior and tests depend on those semantics, sampling is not a drop-in alternative. **Single-pass bounded heap** over the scan, materializing identity only on insertion. This needs one traversal instead of two and O(K + R) memory instead of O(N) timestamps, but it materializes more identities than the frontier approach (every object that transiently enters the heap), and per-thread heaps under the existing parallel scan would multiply that bound by the thread count. Which side wins depends on key width and on the cost ratio between an identity copy and a second traversal; this is an open empirical question rather than a settled one, and I would be glad to benchmark it if reviewers consider it worth resolving before merge. ## Complexity The metadata census remains O(N); this proposal does not reduce the scan, and the selective path traverses metadata twice. What is reduced is full tenant/key identity materialization, from O(N) toward O(K + R) at low eviction ratios, where K is the requested eviction frontier and R is the bounded reserve. Two cases limit that bound, and both fall back to existing behavior rather than failing: - if many objects share the cutoff timestamp, the frontier can hold more than K + R objects, so materialization degrades toward the current path; - if execution-time invalidation exhausts the reserve, a refill scan is performed, and under heavy churn the total materialization can likewise approach the current path. ## Validation The implementation adds deterministic tests that call `BatchEvict` directly, covering: - exact oldest-first selection; - exact target and lower-bound behavior; - soft-pin fallback; - whole-group eviction and group safety; - high-ratio full-materialization bypass; - execution-stage failures absorbed by the reserve; - reserve exhaustion followed by refill. I could not find direct tests for these semantics in the upstream suite; existing eviction tests appear to reach `BatchEvict` indirectly through segment pressure and the background eviction thread. The added fixture therefore provides focused coverage for oldest-first ordering, target and lower-bound attainment, and candidate loss during execution-time revalidation, independently of the optimization itself. ## Scope This RFC intentionally does not change: - the eviction policy; - the ordering metric (`lease_timeout`); - the metadata layout; - the eviction target semantics. The change only reduces unnecessary construction of full candidate identities after the eviction frontier has been identified. Related implementation: #3118.

bsakaguchi added the

RFC

stale

labels

2026-10-29 21:19:41 +00:00

bsakaguchi commented

2026-10-29 21:19:41 +00:00

Author

Owner

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

Thanks for opening this issue, @jacklin78911-collab!

Field	Value
Issue	#3124
GitHub user ID	`251732545`
Reporter	@jacklin78911-collab

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 26, 2026): Thanks for opening this issue, @jacklin78911-collab! | Field | Value | |-------|-------| | **Issue** | #3124 | | **GitHub user ID** | `251732545` | | **Reporter** | @jacklin78911-collab | 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:19:42 +00:00

Author

Owner

@github-actions[bot] commented on GitHub (Oct 25, 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 25, 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 referenced this issue

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

[PR #800] [CLOSED] [Store] Zero copy for Mooncake store get_tensor API #1832