[RFC] Stable Multi-Disk Placement and Stale KV Cache GC for fs_native

What PR #4260 Already Provides

LMCache PR #4260 introduced StripedStorePolicy and StripedPrefetchPolicy for multiprocess (MP) mode.

Store and Lookup use the same BLAKE3-based routing rule:

sorted(active_adapters)[BLAKE3(key) % N]

where N is the number of active adapters. This selects exactly one fs_native adapter as the owner of each key, instead of replicating writes to all L2 adapters through the default policy.

This RFC takes PR #4260 as its baseline and does not revisit single-owner routing itself.

Open Problems

• Mapping stability: When the configured disk set changes after a restart, N also changes. With the current % N scheme, adding a ninth disk to an eight-disk setup remaps approximately 88.9% of all keys, while the ideal remapping ratio is approximately 11.1%. Removing a disk similarly remaps many keys that are still stored on healthy disks.

• Stale files and GC: After a key changes owner, the file at its old location is no longer reachable through Lookup. The current eviction index only receives Store, Access, and Delete events observed by the current process, so these stale files do not automatically become eviction candidates.

• Restart recovery: After fs_native restarts, its key-size metadata, capacity accounting, and eviction order start from an empty state. Existing files on disk are not automatically registered again.

Scope

• Each configured directory corresponds to one independently mounted disk.
• All disks have the same capacity and performance class. Weighted placement is out of scope.
• Disks are added or removed by updating the configuration and restarting LMCache. Online disk addition/removal and automatic failed-disk removal are out of scope.
• Stale files are reclaimed through regular LRU eviction.

Option A: Rendezvous Hash

A stable disk UUID is persisted in each disk's mount directory.

At startup, LMCache calculates the following score for every key and every configured disk:

score = H(key, disk_uuid)

The disk with the highest score becomes the owner. All disks have equal weight. This design does not require virtual nodes and does not depend on configuration order.

Adding a Disk

After adding the new disk to the configuration and restarting LMCache, its disk UUID joins the candidate set.

Ideally, only approximately 1/(N+1) of all keys change owner. The first access to each remapped key results in a cache miss on the new owner, after which the cache is rebuilt through the normal flow. The file on the old owner becomes stale.

Removing a Disk

After removing the disk from the configuration and restarting LMCache, its disk UUID no longer participates in owner selection.

Only keys previously owned by the removed disk select a new owner. Keys on the remaining healthy disks retain their existing owners. Cache data on the removed disk becomes unavailable, and subsequent accesses are handled as cache misses.

GC and Restart Recovery

At startup, LMCache rebuilds the routing state from the current configuration and the stable disk UUIDs. It also scans each disk directory to recover per-disk key, size, last_access, and eviction metadata.

Stale files left on an old owner after adding a disk remain visible to the regular LRU eviction process after the scan.

Main Trade-offs

• Advantages: Small routing state, no authoritative placement table, minimal key remapping when the disk set changes, and an even steady-state I/O distribution.
• Disadvantages: Adding a disk causes first-access misses for the remapped keys and leaves stale files on their previous owners until regular eviction reclaims them.

Option B: Per-file Placement Index

The disk ID is stored together with the per-file eviction metadata. Lookup uses the placement index as the source of truth for determining the owner.

Store and Lookup

When a new key is stored for the first time, LMCache selects a target disk based on per-disk utilization or round-robin placement. The disk ID is registered only after the file has been written atomically.

Lookup first queries the placement index and then accesses the corresponding disk. If the index entry exists but the file is missing, the request is handled as a cache miss and the index entry is corrected.

Adding a Disk

After adding the new disk to the configuration and restarting LMCache, existing records continue to point to their original disks. Adding a disk therefore does not change the location of existing cache objects.

The new disk accepts subsequent writes and gradually receives capacity and I/O load as new cache entries are created and old entries are naturally evicted.

Removing a Disk

After removing the disk from the configuration and restarting LMCache, recovery marks records that reference the removed disk UUID as invalid. All other records continue to point to their original disks.

Cache data on the removed disk becomes unavailable. Invalid records are removed during recovery or when they are subsequently accessed.

GC and Restart Recovery

At restart, LMCache scans each disk directory and rebuilds both object-placement and eviction metadata.

Adding a disk does not change the location of existing objects, so it does not create stale files caused by remapping.

Main Trade-offs

• Advantages: Adding a disk does not affect the location of existing cache entries, and removing a disk does not change object locations on healthy disks.
• Disadvantages: LMCache must persist and recover a per-file placement index.

Comparison

Comparison	Option A: Rendezvous Hash	Option B: Per-file Placement Index
Owner source	Deterministically calculated from the key and stable disk UUIDs	Read from the disk ID stored in each per-file record
Adding a disk	The new disk UUID joins the candidate set; approximately 1/(N+1) of keys change owner	Existing records remain unchanged; the new disk only accepts subsequent writes
Removing a disk	The disk UUID is removed; only keys previously owned by that disk select a new owner	Only records pointing to the removed disk become invalid; other object locations remain unchanged
Misses after changing the disk set	Remapped keys may miss after adding a disk; keys on the removed disk miss after removing one	Adding a disk introduces almost no additional misses; keys on the removed disk miss after removing one
Stale files and GC	Adding a disk leaves stale files on old owners; directory scanning makes them visible to regular LRU eviction	Adding a disk creates no remapping-related stale files; records for a removed disk are cleaned during recovery or access
Per-file memory usage	Stores per-file eviction metadata without an owner field	Adds a disk ID to the same metadata; the theoretical incremental cost is approximately 12–32 MiB at the example scale
Capacity and bandwidth	Even steady-state distribution makes it easier to utilize aggregate disk bandwidth	Existing object locations remain stable; new writes can be distributed across disks through round-robin placement
Consistency and recovery	Persisting stable disk identities is sufficient to recalculate owners; a directory scan rebuilds the eviction index	A directory scan at restart rebuilds both the placement and eviction indexes

Decision Requested from the Community

The main decision is whether the approximately 1/(N+1) cache-miss ratio caused by adding a disk is acceptable.

If it is acceptable, Option A provides a simpler implementation based on Rendezvous Hash. If it is not acceptable, Option B keeps existing cache locations unchanged, but requires more complex maintenance and recovery of per-file placement metadata.

Both options have the same impact when removing a disk: only cache entries stored on the removed disk are lost.

Start by reviewing PR #4260 and the fs_native placement, eviction, and restart-recovery paths described in this RFC. Compare rendezvous hashing with a per-file placement index against the stated disk-addition, disk-removal, GC, and recovery requirements. Done means the community selects an option and the implementation scope and acceptance criteria are agreed.