Hello, I'm Maneshwar. I'm working on FreeDevTools online currently building **one place for all dev tools, cheat codes, and TLDRs* — a free, open-source hub where developers can quickly find and use tools without any hassle of searching all over the internet.*
Yesterday, we looked at how mini-pages and pinned inner nodes reshape the execution path of a B-Tree absorbing writes, keeping hot records close to the CPU, and removing contention from the critical path.
Today, we zoom in on a less visible but equally critical piece:
How Bf-Tree manages mini-page memory.
Once mini-pages exist, the real challenge begins:
they are variable-sized, mutable, and highly concurrent.
A traditional page-based buffer pool simply doesn’t fit.
This post walks through how Bf-Tree designs a specialized buffer pool for mini-pages, and why a circular buffer turns out to be the right abstraction.
Why Mini-Pages Need a Different Buffer Pool
Mini-pages are not fixed size disk pages.
They:
- Grow and shrink dynamically
- Are frequently accessed and modified
- Exist purely in memory until eviction
This introduces three fundamental challenges:
- Memory management Tracking the exact memory location of every mini-page while avoiding fragmentation.
- Hotness-aware eviction Deciding which mini-pages should stay in memory and which should be flushed to disk.
- Concurrency at scale Allowing many threads to allocate, evict, and reclaim memory safely—while still saturating SSD bandwidth.
Traditional allocators and LRU-style buffer pools struggle here.
Bf-Tree takes a different route.
The Core Idea: A Circular Buffer for Mini-Pages
Bf-Tree manages all mini-pages inside a large circular buffer.
The idea is simple but powerful:
- Mini-pages are appended at the tail
- Memory is reclaimed from the head
- When the buffer fills up, eviction moves forward linearly
This design is inspired by FASTER’s hybrid log, but adapted for mini-pages and B-Tree semantics.
At a high level:
- Allocation is fast and sequential
- Eviction is predictable
- Fragmentation is minimized
But a circular buffer would evict hot mini-pages too aggressively.
Bf-Tree refines the design further.
Three Regions, Not One: Protecting Hot Mini-Pages
To avoid evicting frequently accessed mini-pages, the circular buffer is divided using three moving pointers:
- Tail address
- Second-chance address
- Head address
These divide memory into two logical regions:
1. In-Place Update Region (~90%)
- Mini-pages here can be modified directly
- Hot mini-pages tend to stay in this region
- Most updates happen here
2. Copy-on-Access Region (~10%)
- Mini-pages nearing eviction live here
- On access, they are copied to the tail
- This effectively gives them a “second chance”
This mechanism prevents hot mini-pages from drifting toward the head and getting evicted, without requiring complex LRU bookkeeping.
Handling Growth, Shrinkage, and Reuse
Mini-pages frequently resize as they absorb writes.
Bf-Tree handles this via:
- Multiple free lists, grouped by size class
- Reuse of recently deallocated memory
When a mini-page grows or shrinks:
- A new mini-page is allocated
- Contents are copied over
- Old memory is returned to the appropriate free list
This keeps allocation fast and reduces fragmentation over time.
Circular Buffer API: Minimal but Sufficient
The buffer pool exposes a tight API tailored for mini-pages:
Allocation
Memory is allocated from:
- A free list (if available)
- Otherwise, from the tail (by advancing it)
If the tail is too close to the head, allocation fails and eviction is triggered.
Eviction
Eviction always starts near the head:
- Dirty records are merged back into the leaf page on disk
- The mapping table is updated
- The head pointer advances
Multiple threads can evict concurrently, but pointer advancement remains ordered.
Deallocation
Freed memory is returned to size-specific free lists for reuse.
No paging, no per-page locks, no LRU queues.
Performance-Critical Optimizations
Because this buffer sits on the hot path, several low-level optimizations matter.
1. Minimal Fragmentation
- Mini-pages are packed back-to-back
- Each allocation has just 8 bytes of metadata
- No alignment to page boundaries is required
This keeps memory dense and predictable.
2. Huge Pages for TLB Efficiency
Without paging, mini-pages may cross 4KB boundaries.
To avoid excessive page-table walks:
- The circular buffer is backed by huge pages
- This dramatically reduces TLB pressure
3. Parallel Eviction with Ordered Progress
Eviction must advance the head sequentially, but the work doesn’t have to be serial.
Bf-Tree allows:
- Threads to evict mini-pages in parallel
- Head advancement only after all earlier evictions complete
This preserves correctness while still exploiting parallel IO.
Why This Design Works
Mini-pages already changed how leaf nodes behave.
This buffer pool ensures they scale.
Together, the design:
- Avoids allocator fragmentation
- Keeps hot mini-pages resident without LRU overhead
- Supports massive concurrency
- Streams cold data efficiently to disk
Most importantly, it aligns with Bf-Tree’s philosophy:
Separate concerns and optimize each path independently.
- Inner nodes: fast, pinned, contention-free traversal
- Leaf pages: stable on-disk structure
- Mini-pages: flexible, adaptive, in-memory working set
The buffer pool is what makes that separation viable in practice.
👉 Check out: FreeDevTools
Any feedback or contributors are welcome!
It’s online, open-source, and ready for anyone to use.
⭐ Star it on GitHub: freedevtools
Top comments (0)