BSN-1028 - Bounded In-Memory Graph Caches and LRU Eviction Under Pressure

Living Document Notice
Published 2026-09-17. The evolving architecture, revisions, and connected notes for this dispatch live in the Stax Digital Garden.

Bounded In-Memory Graph Caches and LRU Eviction Under Pressure

Summary

Traversing bidirectional link graphs in vaults containing over 100,000 Markdown documents easily exhausts process memory if entire adjacency matrices are loaded into RAM. When background daemons load unbounded graph nodes, operating systems trigger memory compaction and thrash swap space. Bosun PKM implements a two-tier graph cache: a compact in-memory path-to-slug hash index combined with a bounded Least Recently Used (LRU) node cache that caps resident graph memory below 16 MB.

Memory Topologies of Deep Note Graphs

In a mature digital garden, notes form dense, highly connected networks. A 100,000-note vault typically exhibits:

• 100,000 vertices (documents)
• 450,000 directed edges (wikilinks, transclusions, tag references)
• High-degree hub nodes (Maps of Content / MOCs) with degree > 500
• Sparse leaf nodes with degree < 3

Representing this topology as an unconstrained in-memory object graph (e.g. HashMap<PathBuf, HashSet<PathBuf>>) consumes approximately 140 MB of heap memory due to pointer overhead and hash table bucket padding:

Heap Overhead in Unbounded Graphs:
100,000 Node Structs (String allocations):       ~28 MB
450,000 Edge Objects (Arc<Node> pointers):      ~72 MB
HashMap Bucket Bucketing & Load Factor Padding:  ~40 MB
Total Heap Footprint:                           ~140 MB

On constrained devices, retaining 140 MB of graph state in a background sync process violates local-first resource budgets.

Two-Tiered Graph Cache Architecture

To achieve sub-millisecond link queries without paying the 140 MB memory penalty, the engine separates path resolution from edge traversal:

[Query: Find Backlinks for "storage-invariants"]
                      │
                      ▼
[Tier 1: In-Memory Slug-to-Path Array]  <-- 1.2 MB RAM
  - Fixed-size 64-bit FNV-1a hash map
  - Translates slug to canonical locker path in 0.004 ms
                      │
                      ▼
[Tier 2: Bounded LRU Node Cache]       <-- 8.0 MB RAM Ceiling
  - Capacity: 2,048 active node edge lists
  - Cache Hit: Returns inbound/outbound edge slices immediately
  - Cache Miss: Queries SQLite link_edges table in 0.42 ms, populates LRU

Tier 1 stores only hashes and path pointers. Tier 2 caches the edge sets of actively traversed nodes.

use std::collections::HashMap;
use std::path::PathBuf;
use lru::LruCache;
use std::num::NonZeroUsize;
 
pub struct BoundedGraphIndex {
    // Tier 1: Compact slug mapping (slug_hash -> canonical_path)
    slug_directory: HashMap<u64, PathBuf>,
    // Tier 2: Bounded active node edge cache
    edge_cache: LruCache<PathBuf, Vec<PathBuf>>,
}
 
impl BoundedGraphIndex {
    pub fn new(capacity: usize) -> Self {
        Self {
            slug_directory: HashMap::with_capacity(100_000),
            edge_cache: LruCache::new(NonZeroUsize::new(capacity).unwrap()),
        }
    }
 
    pub fn get_backlinks(&mut self, target: &PathBuf, db: &rusqlite::Connection) -> &[PathBuf] {
        if !self.edge_cache.contains(target) {
            let edges = fetch_edges_from_sqlite(db, target);
            self.edge_cache.put(target.clone(), edges);
        }
        self.edge_cache.get(target).map(|v| v.as_slice()).unwrap_or(&[])
    }
}

Eviction Dynamics and Hot-Hub Retention

Because knowledge graphs follow power-law degree distributions, a small percentage of nodes (MOCs, indexes) account for the vast majority of link queries. The LRU eviction policy naturally retains these hot hubs in memory while continuously evicting cold leaf nodes.

Benchmark measurements across 50,000 simulated graph queries on a 100k-note dataset:

Graph Cache Configuration	Cache Hit Ratio	P95 Query Latency	P99 Query Latency	Peak Memory (RSS)
Unbounded In-Memory Graph	100.0%	0.012 ms	0.024 ms	148.5 MB
Pure SQLite (Zero Cache)	0.0%	0.850 ms	2.100 ms	11.2 MB
Two-Tier Bounded LRU (2048 Nodes)	92.4%	0.038 ms	0.440 ms	14.6 MB

The bounded two-tier cache achieves a 92.4% hit rate and sub-0.04 ms latency while keeping the engine’s resident memory footprint strictly under 15 MB.

---

• Directus Target: bosun-pkm
• Garden Source Reference: MOC - Bosun PKM Tools, MOC - Bosun PKM Engine, MOC - The Plain-Text Longevity Standard, [BSN-1008 - The Limits of Plain-Text Graphs](BSN-1008 - The Limits of Plain-Text Graphs)