[RFC] Replication-aware rank-based KV eviction for P2P and PD

[GentleCold]

Summary

This RFC proposes replication-aware KV-cache eviction for PegaFlow. Each resident block receives an eviction rank, and blocks are maintained in per-rank LRU lists:

higher rank -> evict earlier
same rank   -> evict by LRU

The goal is to reduce P2P/RDMA replica expansion while preserving the decode-side Pega cache in PD-separated deployments.

Related background: #389.

Motivation

Production observations show that MetaServer redundancy can rise substantially while owner count grows faster than unique block entries. RDMA block requests, cache insertions, and registrations increase in the same periods, which is consistent with P2P/RDMA-fetched blocks becoming additional resident owners.

D-side Pega save_only should remain available because decode-side memory is intended to be used as a cache tier.

Rank Semantics

rank is an eviction-pressure score, not an exact or continuously synchronized owner count.

New local resident

After InsertBlockHashes, initialize the new resident with:

rank = max(1, owner_count_hint - 1)

The -1 reserves one level for the newly admitted resident, which is important for the P/D case. If MetaServer is unavailable or the hint is missing, use rank = 1 and do not block cache admission.

The hint initializes a new resident only. It must not overwrite the rank of an already resident block.

Pega P2P transfer

For a source block transferred to a new destination:

destination.rank = source.rank
source.rank += 1

The source records the destination for (namespace, block_hash). A repeated transfer of the same block to the same destination does not increment the source again.

This gives a move-like behavior:

A=1
B <- A  => A=2, B=1
C <- B  => A=2, B=2, C=1

NIXL PD transfer

NIXL is not modified and PegaFlow does not receive the destination node identity.

On the P side, the existing vLLM MultiConnector aggregated finished_sending signal is used as an idempotent hint:

P rank = max(P rank, 2)

This is applied once per resident state, not once per request, so repeated finished_sending events cannot increase rank indefinitely.

On the D side, a new Pega save_only resident uses the MetaServer owner hint and the owner_count - 1 rule. In the simple case:

P save                 -> P=1
P finished_sending     -> P=2
D save_only, owners=2  -> D=1

If a Pega P2P path later transfers from a rank-2 P/D node, the normal P2P rule applies and produces source=3, destination=2.

AlreadyExists recovery

When local cache insertion returns AlreadyExists, apply a saturating local recovery:

rank = max(1, rank - 1)

This covers both:

• P/D NIXL GDR followed by D-side save_only when D already has the block.
• Pega P2P/prefetch batches where some requested blocks already exist locally.

This is local state only; it does not send a rollback RPC. Repeated recovery stops at rank 1.

Example:

P=2, D1=1
P is evicted
P <- D1 via Pega P2P -> P=1, D1=2
P -> D1 via NIXL, D1 already has the block
P finished_sending -> P=2
D1 AlreadyExists -> D1=1

Eviction Data Structures

The cache keeps one block payload and two key-level indexes:

Hash -> block payload
Hash -> set/list of seen Pega-P2P destination addresses
rank -> LRU list<Hash>

Rank changes move only the key between rank LRU lists; block payloads are not copied.

When reclaiming blocks, always select the LRU victim from the highest non-empty rank list. Within one rank, use LRU order. No global candidate scan is required.

This deliberately prioritizes replication pressure over local recency. A hot, highly replicated block can be evicted and fetched again. The design assumes cache-aware routing can move hot blocks toward nodes where their replicas are useful.

Failure and Staleness Model

The design does not add eviction-to-source rollback communication. If a source or destination disappears, rank can remain temporarily high. This is acceptable because PegaFlow cache is not authoritative; the effect is replacement quality, not data correctness.

A state such as A=2, B=2, C=1 may become A=2, B=2 after C is evicted. The absence of a rank-1 anchor is accepted in the first version.

Scope

In scope:

• MetaServer Insert owner hint returned per block/batch position.
• Rank-aware resident admission and replacement.
• Pega P2P source/destination rank propagation with destination de-duplication.
• P/D NIXL handling through existing finished_sending, without changing NIXL.
• Saturating AlreadyExists rank recovery.
• Fixed per-rank LRU lists.

Out of scope:

• NIXL protocol changes or peer identity propagation.
• Per-eviction rollback RPCs.
• MetaServer background full scans or owner push protocol.
• Canonical owner or exact replica-count synchronization.
• Backpressure, delayed registration, or new configuration switches.

Metrics and Validation

Track at least:

• rank distribution and maximum rank;
• evictions by rank;
• RDMA/P2P fetches after eviction;
• cache AlreadyExists recovery count;
• MetaServer redundancy;
• cache hit/miss and reclaimed bytes.

The main risk to validate is hot-block churn: high-rank local hot blocks may be evicted and fetched repeatedly if routing is not sufficiently cache-aware.

Open Questions

1. Confirm the exact MetaServer Insert response shape for owner hints per block.
2. Confirm the stable destination identity used by Pega P2P de-duplication.
3. Benchmark per-rank LRU bookkeeping under the observed eviction rate.

[xiaguan]

Thanks for the RFC — the direction (soft replication-aware demotion, no new RPCs, conservative failure model) matches what we need. A few concerns with the multi-rank design, then a counter-proposal for the first version.

1. In the motivating deployment, rank degenerates to a binary

There are three rank sources: NIXL saturates at 2 (max(rank, 2)), Pega P2P can grow beyond 2, and the owner hint can initialize above 2. But the motivating scenario is PD separation with NIXL, where P2P is not the dominant path — so in practice the rank distribution collapses to {1, 2}. That is exactly a two-segment LRU (probation/protected), and most of the spec surface (per-destination dedup sets, source +1 propagation, saturating recovery, hint precedence) buys ordering precision among rank values that rarely occur, derived from a hint that drifts.

2. Missing hit-promotion is a regression vs #389

#389's acceptance criteria included "a P-side hit on a demoted block refreshes/promotes it". #398 drops it: rank has only one decrease path (AlreadyExists). But the scheduler-side connector queries and skips already-cached prefixes before saving, so a locally hot block never re-triggers a save, AlreadyExists never fires for it, and its rank never recovers.

For globally hot blocks (shared system prompts) this is a guaranteed churn loop rather than a risk to validate: high owner count everywhere → high rank everywhere → preferred victim everywhere → evict → re-fetch → owner hint re-initializes a high rank → evict again. "Cache-aware routing moves hot blocks toward nodes where their replicas are useful" doesn't hold for a prefix that is hot on every node.

Minimal fix regardless of the rest of the design: a local load hit also applies saturating rank = max(1, rank - 1), symmetric with the AlreadyExists rule, still zero RPCs.

3. Owner hint: answers to OQ1/OQ2, plus a precedence gap

• OQ2: the stable destination identity already exists — QueryBlocksForTransferRequest.requester_id (the peer's advertise address). The source has it when serving the P2P read.
• OQ1: InsertBlockHashesResponse currently returns only inserted_count, and client-side registration is a fire-and-forget batched queue (errors are only logged). Using the hint means adding per-block owner counts to the response (positionally aligned) and plumbing the async batched response back into the read cache as a retroactive rank init ("set rank iff untouched since admission"). That's a real state machine the RFC currently glosses over.
• Spec gap: when a P2P-fetched block is admitted, both the destination rule (dest.rank = source.rank) and the owner hint fire on the same admission. Which one wins must be specified.

4. Unspecified interactions

• TinyLFU admission (already in the codebase behind a flag) compares the candidate's frequency against "the LRU victim". With per-rank lists that victim becomes the tail of the highest non-empty rank, which distorts admission semantics. Rank and frequency are orthogonal signals; the spec should say which dominates.
• AlreadyExists conflates three sources: repeated P2P/NIXL transfer, prefetch batches with partial local hits, and concurrent duplicate saves (which we've measured to be a major redundancy source). One -1 rule serving three different signals makes rank noisy.

Counter-proposal for v1: segmented LRU, entry class decided locally

Compress the rank integer into one bit that never needs cross-node maintenance:

evict direction ←  [ cold (probation) | hot (protected) ]

• Entry class is known locally at insert time, no MetaServer round-trip:
  • locally computed save → hot (likely the first replica in the cluster)
  • RDMA/P2P fetched block → cold (by definition the ≥2nd replica)
• Only two transitions:
  • P-side aggregated finished_sending (same signal as Proposal: NIXL pull-aware eviction demotion for P-side Pega blocks #389) → demote to cold
  • local hit → promote to hot (standard LRU touch)
• Eviction always drains the cold tail first.

With no memory pressure, replicas are retained and registered exactly as today — metadata stays truthful and the D-side cache tier keeps working. Under pressure, every node first drops the replicas it never used locally, so cluster redundancy converges without any protocol.

Implementation stays confined to the cache layer. The current cache exposes get / contains_key / insert / remove_lru / remove_all; swapping one LRU list for two keeps every signature except insert (gains an entry-class param), plus one new demote_blocks passthrough for the finished_sending hook. The reclaim loop, MetaServer removal, transfer locks, and metrics are untouched.

What this gives up vs multi-rank: distinguishing a 5-owner block from a 2-owner block at admission time. But that ordering rests on a drifting hint; I'd rather buy it back later with data than pay for it up front.

Suggested sequencing

1. Ship the two-segment version (no proto change). A/B it on MetaServer redundancy, segment/rank distribution, evict-then-refetch rate (the direct churn evidence), and TTFT.
2. If the data shows two segments are insufficient specifically because replica-count granularity matters, revisit multi-rank — the segmented structure generalizes to per-rank lists naturally.