The Annex

Chapter 03Oct 25, 2026NUMAFurrballs

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.

same 24-access Zipfian stream · capacity 5

ARC

70.8%

LRU

66.7%

S3-FIFO

66.7%

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

T1 · recency

T2 · frequency

B1 · ghosts of T1

B2 · ghosts of T2

0/32

boundarywhere the policy story stops

§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.

Chapter 04Oct 25, 2026NUMAFurrballsRDMA

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).

OwnerReaderreal ring: 131,072 slots (2^17) · viz: 24

W = writePos (next reserve) · R = readPos (next drain), per node · rows are one ring per node, 2^17 slots live, 24 shown

press Run trace

—

design-noterdmauntested; proposed, not built

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.

Appendix

Glossary

NUMA

Non-Uniform Memory Access: memory sits in domains (sockets), and a core reaches its own domain faster than the others. The latency ladder (1.2–2× cross-socket, 3–5× for CXL tiers) is what Furrballs' placement strategy tries to flatten.

CXL

Compute Express Link: a cache-coherent interconnect for attaching memory and devices beyond the socket. It turns "far memory" into a deployable tier, which is why NUMA-style asymmetry keeps getting worse, not better.

Page (Furrballs)

The atomic NUMA locality unit: one physical block per node, subdivided by the bump allocator. Every key's bytes share the page's domain affinity, and eviction reclaims whole pages, never single values.

Bump allocator

Append-only allocation: an atomic pointer bumps forward, values pack consecutively with 8-byte alignment. No per-value free; pages are recycled wholesale.

Eviction boundary

The moment pages are flushed or reclaimed, the cheapest point in the system to move or drop data. Furrballs defers cross-node migration to exactly this boundary (track-and-defer, §2.1.2).

Bloom filter

A probabilistic membership test: "definitely not present" or "maybe present". False positives are possible, false negatives are not. Furrballs keeps one per node to skip remote nodes during the Get() walk; a false positive costs one wasted remote probe.

MPSC ring

Multi-producer, single-consumer queue: many writers append, one reader drains. The Annex's inbound ring is an MPSC ring: positions reserved with fetch_add, each slot carrying its own ready flag so the consumer never sees a torn entry.

The Annex

Furrballs' cross-node announce ring (source-only, absent from the whitepaper): every Set() announces where a value lives via per-target batches; readers drain their inbound ring into an index and serve values with one directed remote read. See Chapter 3.

Seqlock

Lock-free read pattern: an even/odd counter guards a value. Readers acquire → copy → verify; if the counter moved mid-copy, the value was torn; discard and retry. CMap runs one per slot; the CAS on the counter is the entire write lock.

CAS

Compare-and-swap: a CPU atomic that writes only if the target still holds the expected value. The primitive behind CMap's ctrl-byte publish and the seqlock's even/odd transitions.

ARC

Adaptive Replacement Cache: keeps recency (T1) and frequency (T2) in separate lists, with ghost lists remembering what was just evicted. The ghost hits drive an adaptive point p that decides which side a miss steals room from. Furrballs' Phase 2a policy, validated at 34.96% hit rate vs LRU's 24.77% on the report's Zipfian workload.

Ghost list

A list of recently evicted keys: metadata only, no value. A hit on a ghost is free information: the workload just asked for something the cache threw away too early, and the adaptive point moves.

Adaptive p

ARC's split point: the capacity budget assigned to T1 (recency). Ghost hits in B1 push it up (the workload favors recency), hits in B2 pull it down (the workload favors frequency).

LRU

Least-Recently-Used: one recency list, evict from the tail. Fast and simple, and on the report's Zipfian workload it gives up ~10 points of hit rate to ARC's adaptive filter.

S3-FIFO

A FIFO queue with one frequency bit per entry: a hit sets the bit; on eviction, a flagged head is demoted to the tail instead of evicted. Furrballs benchmarked it with a per-slot atomic frequency counter.

RDMA

Remote Direct Memory Access: one-sided network reads/writes that skip the remote CPU entirely. The design note at the end of Chapter 4 maps the Annex onto RDMA's (rkey, addr, length) model; the NUMA build is the same indirection over a coherent interconnect.

Notebook complete

More chapters land as they are finished; back to Numa & Furrballs.