Data gravity
Placement sets the bill up front; remote reads collect it. A Get() that crosses a domain pays the latency ratio on every access, and nothing in a traditional cache even counts that. Systems usually answer with replication or eager migration. Each is correct and immediate, and each is expensive: the data moves the moment the access appears.
Furrballs defers the move instead. Every remote Get() bumps a per-key atomic counter (CrossNodeAccesses, relaxed ordering, because it is a hint rather than a lock). Only when the counter crosses a threshold does the key become a migration candidate, and it moves at the eviction boundary, where pages are already being reshuffled and one more memcpy costs effectively nothing (§2.1.2). Data still gravitates toward its readers; the counter decides the pace.
The walk that finds remote keys is made cheap on purpose: the reading node tries home first, then a per-node probe order where bloom filters skip the nodes that never saw the key. False positives still cost one full remote probe, which is the price of a probabilistic skip.
Watch for
- · The walk: home node first, then probeOrder with bloom-filter skips.
- · CrossNodeAccesses is a hint, not a lock; relaxed ordering is deliberate.
- · Migration happens at the eviction boundary, where movement is cheapest (§2.1.2).
Eviction
Placement decides where keys arrive; eviction decides what the cache forgets when memory runs out. Furrballs' Phase 2a answer was ARC, the adaptive replacement policy that keeps recency (T1) and frequency (T2) in separate lists, with ghost lists remembering what was just evicted so the filter between the two can learn.
On the report's own Zipfian workload the adaptation pays measurably: PolicyBench puts ARC at 34.96% hits vs LRU's 24.77%, about ten points earned by the adaptive filter. The cost is mechanics: the reference lists are slow, and the flat-list rewrite recovers the throughput (§5.22 documents it; the same optimization was rediscovered here, same wall, same fix).
Inside Furrballs the policy doesn't own its keys: tracking is hash-keyed (no strings in the ARC lists, §3.13), promotions arrive through a deferred MPSC buffer (§3.14), and eviction runs through FindAndEraseByHash, the same shape as the Annex. And when a key dies, it can't simply be deleted: bump-allocated pages reclaim space by migrating cold keys and evicting whole pages.
Watch for
- · Ghost hits are the adaptation signal: watch p move as recency vs frequency demand shifts.
- · The victim rule is p-driven: T1 pays when it outgrew its target, T2 otherwise.
- · Same access stream through every policy; the hit-rate bars are the comparison.
synthetic stream above (24 ops, capacity 5); real PolicyBench run below
| PolicyBench · Zipf θ=0.99 | hit rate | throughput |
|---|---|---|
| LRU | 24.77% | 9.7M/s |
| ARC | 34.96% | 4.9M/s |
| ARC-FLATLL2 | 34.96% | 9.5M/s |
§3.28 draws the line this chapter walks up to: recency and locality are orthogonal axes, and ARC's single-axis model cannot express "this key is hot but on the wrong node." The REMARC framework attempted the reduction, collapsing recency, frequency, and locality into one score.
The attempt is kept in the report as a documented negative result: most REMARC variants land at LRU-level hit rates with as many or more evictions, because page-management fought the policy for the same keys. The salvage, running the scorer as the cache itself, matched ARC's hit rate exactly with better tails, and that variant is what the whitepaper ships.
The multi-node policy comparison itself is deferred (§5.20): the data was collected but held back, because page-level eviction smothers policy differentiation. At page granularity the differences between per-key policies smooth out, and measuring what each mechanism contributes requires a benchmark redesign. The limitation is reported as a result rather than hidden.
The Annex
The chapters before this one cover what the whitepaper documents. The Annex exists only in the source, and it is the most recent idea in Furrballs. The problem it answers: once values live on specific nodes, a reader on the wrong node either probes every node or stays blind.
The Annex is a control/data plane split. Every Set() announces the entry ({ nodeId, dataOffset, dataSize }) into the calling node's outbound batches, one per remote target, spinlock-guarded and purely local; a full batch of 16 flushes into the target's inbound ring. That ring is an MPSC queue: fetch_add reserves contiguous positions, each slot carries its own ready flag (release on write, acquire on read), and a single consumer drains until the first gap. A Get() drains first, indexes what it drained, and if the key's hash is in the index, the value is served with one directed remote read, no probe walk and no per-node CMap queries.
Two behaviors matter in the trace: announce batching means the index lags behind writes, and out-of-order producers mean the drain can stop at a gap. Both frames below show the real behavior, not an idealization.
Watch for
- · Announce is batched (×16) and purely local; Set() never waits for a remote node.
- · The index lags behind writes: a Get before the flush falls back to the walk.
- · The drain stops at gaps left by out-of-order producers: FIFO preserved at a latency cost.
- · Directed hit: one remote memcpy, no probe walk (AnnexDirectedHit).
W = writePos (next reserve) · R = readPos (next drain), per node · rows are one ring per node, 2^17 slots live, 24 shown
The Annex beyond one machine
The Annex's entry ({ nodeId, dataOffset, dataSize }) is, structurally, an (rkey, remote_addr, length) tuple: the exact triple a one-sided RDMA READ consumes. The directed hit's memcpy from a remote address is RDMA semantics emulated over the memory interconnect. That makes the Annex a credible indirection layer for a distributed Furrballs: register the per-node page blocks as memory regions (the page-granular allocator already provides stable, registrable units), replace the directed memcpy with a one-sided READ, and let the announce rings ride the network. A batch of 16 entries becomes a single RDMA write, cheaper on the wire than the shared-memory version.
Three problems stand between the idea and a system:
1 · Entry lifetime. Announces hold addresses into owner pages; eviction, compaction, and migration all invalidate them. Across a network, a stale entry does not fault; it silently reads garbage. The design needs generation counters in announces, invalidation announces on evict/migrate, or epoch-scoped registration.
2 · Torn reads. The directed read bypasses the CMap seqlock. Within a node, cache coherence papers over concurrent in-place updates; between machines there is no coherence at all. The seqlock problem reappears one level up: version-in-announce plus read-then-validate, or writer-side copy-on-write pages.
3 · Registration and failure. Pinning policy (per page vs per-node arena) trades pageable memory for stability; a NIC error mid-read, or a directed read that outlives its owner, needs explicit retry and generation checks.
What it buys if those hold: Furrballs as a cluster cache where topology distance generalizes from socket to node to rack, with the same locality logic at every scale, and the same Swiss table, seqlock, and Annex machinery underneath. None of this has been run; there is no RDMA hardware in reach, and the note is written as design, not result.