CUBRID Bestspace (next version) — Sharded Lock-free Free-space Index

Contents:

• Theoretical Background
• Common DBMS Design
• Motivation
• CUBRID’s Approach
  • Design at a glance
  • Data structures: tiers and the three-level bitmap
  • The find path — lock-free descent
  • The allocate path — victims, candidates, new pages
  • Candidates queue and page recycling
  • Registry and the thread-local cache
  • On-disk persistence and recovery
  • Integration points
  • Legacy vs. next-version
• Source Walkthrough
• Cross-check Notes
• Open Questions
• Sources

Theoretical Background

A heap file answers one question on every INSERT: which page has enough free space for this record? This is the free-space management sub-problem of row-oriented storage. The broader heap substrate — slotted pages, record identifiers, forwarding records, overflow files — is covered in cubrid-heap-manager.md §“Theoretical Background”; this document zooms into free-space tracking specifically.

Database Internals (Petrov, Ch. 3–4) frames the slotted page as the unit: a fixed header, a slot directory growing from one end, record bodies from the other, and a free-space gap in the middle that is the only place an insert can land. So “find a page with room” reduces to “find a page whose free-space gap is at least record_length + slot_overhead.” Scanning the whole heap for that on every insert is prohibitive, so every engine keeps an auxiliary free-space structure — a map or cache of pages and their approximate free space — and consults it first.

Three properties are inherent to the problem and shape every implementation:

1. Approximation is acceptable, by design. A free-space hint may be stale (another transaction filled the page since it was recorded). The cost of a wrong hint is a wasted page fix — fix the page, discover it is full, try another — never a data error. Because a wrong hint is cheap and exact tracking is expensive, the structure is deliberately lossy and self-healing.
2. Reuse versus growth. Deletes and vacuum free space on existing pages. An engine that always allocates fresh pages for new inserts would let a bulk-deleted table’s storage leak; one that eagerly reuses every freed byte re-dirties just-emptied pages. The structure must decide when a page has enough reclaimed room to be worth offering back — a per-engine admission policy.
3. Concurrency is the hard axis. Under many transactions inserting into the same table, the free-space structure is touched on every insert. If it is a single shared object protected by one latch, it becomes the serialization point — the engine inserts one row at a time regardless of hardware parallelism. The design tension is therefore accuracy versus contention: a precise, centralized structure serializes; a distributed, approximate one scales but must tolerate staleness.

The next-version bestspace is a response to property 3 in particular — the legacy CUBRID design was accurate and centralized, and the redesign trades a little more distribution and approximation for the removal of a single hot latch.

Common DBMS Design

The textbook gives the model; this section names the engineering conventions that row-oriented engines converge on for free-space tracking. CUBRID’s next-version choices in §“CUBRID’s Approach” are best read as one set of dials within this shared space, not as inventions. (The legacy CUBRID design and its cross-engine peers are also summarized in cubrid-heap-manager.md §“Common DBMS Design” → Free-space hint cache; this section goes deeper on the concurrency dimension, which is what the redesign targets.)

The structure is per-object, not global

PostgreSQL keeps a Free Space Map (FSM) per relation (a separate fork <relfilenode>_fsm), not one global map. Oracle tracks free space per segment. The convention is that free-space metadata is owned by the table (or its storage segment), so unrelated tables never contend for it. The legacy CUBRID heap_Bestspace cache is the outlier here: a single process-global hash shared by every heap — one of the two things the redesign changes.

A hierarchy of free-space summaries makes “find a page ≥ N” cheap

PostgreSQL’s FSM is a binary tree stored in FSM pages: each leaf holds one page’s free space quantized to a single byte (1/256 granularity), and each internal node holds the max of its children, so a search for “a page with ≥ N free” descends the tree touching O(log pages) nodes instead of scanning. Oracle’s Automatic Segment Space Management (ASSM) replaced the older freelist with a hierarchy of bitmap blocks — L1, L2, and L3 — where an L1 block tracks the fullness of a run of data blocks in a few states (e.g. 0–25%, 25–50%, 50–75%, 75–100% free), an L2 block indexes L1 blocks, and an L3 block indexes L2 blocks. The recurring idea: a multi-level summary keyed by free-space class turns the search into a short descent. CUBRID’s next-version bestspace adopts exactly this shape — a three-level (L3/L2/L1) bitmap keyed by a free-space tier — and the naming is a deliberate echo of ASSM.

Free space is bucketed into coarse classes, not tracked to the byte

Neither FSM (1/256) nor ASSM (four/five fullness states) tracks exact free space. Coarse classes are enough to answer “big enough?” without fixing the page, and they make the summary compact (a bitmap bit per class). The engine then fixes the chosen page and reads the true free space, correcting the estimate on the way. CUBRID’s tiers FS0..FS8 (nine free-space classes) are this convention.

An admission floor filters out barely-free pages

A page that is 95% full is not worth offering to an inserter — the record probably will not fit, and indexing it churns the structure. Engines apply a floor: PostgreSQL’s FSM effectively ignores pages below one quantum; CUBRID’s legacy design used a single 30% floor (HEAP_DROP_FREE_SPACE). The next-version design keeps a floor but expresses it as a tier (a page is nominated as a reuse candidate only at tier ≥ FS3, ~25%).

Contention avoidance is a first-class goal — the freelist lesson

The canonical cautionary tale is Oracle’s original freelist: a linked list of free blocks anchored in the segment header. Under concurrent insert it became a hot block — every inserter serialized on the segment header — and Oracle’s fixes were, first, FREELIST GROUPS (shard the freelist into N independent lists) and, ultimately, ASSM (replace the list with per-block bitmaps so inserters spread across the segment without a shared mutable head). The lesson generalizes: the free-space structure must not have a single mutable serialization point on the insert path. The next-version CUBRID design applies both remedies at once — sharding (like freelist groups) and a lock-free bitmap (like ASSM) — to a design whose legacy form serialized on the heap-header latch.

Theory ↔ CUBRID mapping

Free-space concept	PostgreSQL	Oracle	CUBRID (next version)
Per-object ownership	per-relation FSM fork	per-segment	per-(class_oid, HFID) bestspace
Multi-level summary	FSM binary tree	ASSM L1/L2/L3 bitmap blocks	L3/L2/L1 in-memory bitmaps
Free-space classes	1/256 byte quantum	4–5 fullness states	9 tiers FS0..FS8
Admission floor	one quantum	segment PCTFREE	tier ≥ FS3 (candidate)
Contention remedy	per-relation isolation	FREELIST GROUPS + ASSM	sharding + lock-free CAS
Reuse reservoir	FSM re-marks freed pages	ASSM bitmaps	candidates queue

Motivation

The heap-header latch bottleneck

CUBRID’s legacy free-space selection routes the whole insert-page search through the heap header page, under a WRITE latch held for the entire operation. From the legacy heap_stats_find_best_page (dissected in cubrid-heap-manager-detail.md Chapter 9): the header is fixed PGBUF_LATCH_WRITE before any estimate is touched and released only at the single exit — estimate mutation, hint scan, bounded re-sync, and even page allocation all happen under that one latch. That invariant keeps two inserters from corrupting the head / best[] ring, but it also serializes them:

To find best space, most of the insert path holds a WRITE latch on the heap header page. This structure is a bottleneck that lets only one thread insert at a time. — CBRD-26176 (paraphrased from Korean)

For many transactions inserting into the same table, the header page is a single hot latch, and concurrency collapses to roughly one inserter per heap at a time — the “centralized metadata contention” pattern CBRD-26806 tracks more broadly, and the exact freelist lesson from §“Common DBMS Design.”

The legacy mechanism being replaced (baseline)

The legacy design is a two-tier, approximate, unlogged hint system (full treatment: heap-manager-detail Chapter 9), summarized here as the baseline:

• On-disk hints in the heap header’s estimates sub-struct: a best[10] ring of HEAP_BESTSPACE {VPID; int freespace;}, a second_best[10] reservoir ring, a head cursor, and aggregate counters.
• In-memory cache heap_Bestspace — a process-global hash keyed by HFID+VPID, bounded by PRM_ID_HF_MAX_BESTSPACE_ENTRIES, guarded by bestspace_mutex, shared across all heaps.
• heap_stats_find_best_page orchestrates under the header WRITE latch: scan cache then disk ring (LK_FORCE_ZERO_WAIT to skip busy pages), else heap_stats_sync_bestspace (a bounded rebuild of min(20% of pages, 100)), else heap_vpid_alloc.
• HEAP_DROP_FREE_SPACE = 30% is the single admission floor; second_best admits one evicted page per 1000 substitutions to spread writes.
• Nothing is logged for correctness — a wrong hint costs at most a wasted page fix.

Its strengths — approximate, self-healing, crash-tolerant — are kept in spirit. Its weakness for INSERT-heavy load — a global cache plus a per-heap header latch across the whole selection — is what the redesign targets.

Status and scope

This document analyzes PR #7353 — [CBRD-26176] bestspace (author hyahong, base develop, head branch CBRD-26858). At the time of writing the PR is a draft and is not merged into develop; this analysis is deliberately ahead of the merge. Every symbol, line hint, and struct field reflects PR head commit 81061660a5 and may drift before the PR lands (see §“Cross-check Notes”). The work sits under EPIC CBRD-26857 (Sharded Lock-free Bestspace Index); the design sub-task CBRD-26858 surveyed Oracle and PostgreSQL free-space management (the source of §“Common DBMS Design”), and CBRD-26176 is this implementation, whose acceptance criterion is a measured throughput gain under INSERT-heavy load.

CUBRID’s Approach

The next-version bestspace lives in a new C++ translation unit, src/storage/bestspace.{hpp,cpp}, namespace cubstorage. It replaces the global cache and the header ring with a per-heap-file, sharded, lock-free index plus a candidate queue and a durable snapshot.

Design at a glance

Three nested levels of structure plus a global registry:

Figure 1: the four structural levels. The registry resolves a heap file to its bestspace; the bestspace spreads pages across shards and holds a concurrent queue of candidate pages; each shard is a three-level bitmap index over 64 page slots.

The load-bearing ideas, mapped to the conventions of §“Common DBMS Design”:

• Per-heap-file isolation. A bestspace exists per (class_oid, HFID) — the per-object convention. Two tables never contend.
• Sharding. Each bestspace holds bestspace_shard_count shards (default 8, 1–28) — the freelist-groups remedy.
• Lock-free within a shard. Every node (L1, L2, L3) is an 8-byte value in a 64-byte-aligned std::atomic, updated by compare_exchange_strong; static_asserts enforce lock-free and cache-line sizing (no false sharing) — the ASSM remedy.
• Tiered free space. Nine tiers FS0..FS8 replace the single 30% floor — the coarse-classes convention.
• Candidate recycling. A concurrent queue feeds pages that recently gained free space back into the index — the reuse-reservoir convention.
• Durable, cheaply. A compact form (shard count, L1 entries, a candidate list) is persisted in the heap header and a few dedicated pages and rebuilt on demand after restart.

Data structures: tiers and the three-level bitmap

bestspace_entry — one page’s hint, packed to exactly 8 bytes so it fits a lock-free atomic word:

// bestspace_entry — src/storage/bestspace.hpp
struct bestspace_entry
{
  std::uint16_t freespace;   // bytes free (offset 0)
  short         volid;       // (offset 2)
  int32_t       pageid;      // (offset 4)
};
static_assert (sizeof (bestspace_entry) == 8, "bestspace_entry must be 8 bytes");

freespace is first on purpose: the L1 leaf shares the layout, so a page is pre-filtered on free space with a single load.

Figure 2 — the 8-byte page hint. freespace occupies the first two bytes so the L1 leaf, which shares this exact layout, can be pre-filtered on free space with a single atomic load before the page is ever fixed.

Tiers FS0–FS8 — size_to_tier maps a byte count to one of nine classes by percentage of the page:

Tier	Free space	Role
FS0 (−1)	1–7%	Too small to index — never gets a bitmap bit
FS1 (0)	8–15%
FS2 (1)	16–24%
FS3 (2)	25–34%
FS4 (3)	35–45%
FS5 (4)	46–57%
FS6 (5)	58–70%
FS7 (6)	71–84%
FS8 (7)	85–100%	A (near-)empty page
FSEND (8)	—	Loop sentinel

// bestspace::size_to_tier — src/storage/bestspace.cpp
static constexpr std::int16_t threshold[] = { 7, 15, 24, 34, 45, 57, 70, 84 };
percentage = size * 100 / DB_PAGESIZE;
for (i = 0; i < (int) tier::FS8 + 1; i++)
  if (percentage <= threshold[i])
    return static_cast<tier> (i - 1);   // FS0..FS7
return tier::FS8;

The FS1..FS8 range (8 tiers) is exactly the 8 bits of a byte-sized bitmap — the structure is built around that identity.

Figure 3 — the nine free-space tiers. size_to_tier buckets a page by percent free; FS0 is too small to index, and the candidate admission floor sits at FS3 (~25%). The eight indexable tiers FS1..FS8 map one-to-one onto the eight bits of a byte-sized bitmap.

L1 — the leaf (one page). Same 8-byte layout as bestspace_entry, in a 64-byte atomic_wrapper<L1> so each of the 64 slots in a shard sits on its own cache line.

// bestspace::L1 — src/storage/bestspace.hpp  (accessors elided)
class L1 {
  std::uint16_t m_freespace;
  short         m_volid;
  int32_t       m_pageid;
};
static_assert (sizeof (L1) == 8 && std::atomic<L1>::is_always_lock_free, "...");

L2 and L3 — the summary bitmaps. Each is an 8-byte value = std::array<bitmap, 8>, one 1-byte bitmap per tier FS1..FS8:

• L2[k] summarizes the 8 L1 slots in group k. Bit j of the FSt bitmap is set when L1[k*8 + j] sits in tier FSt.
• L3 summarizes the 8 L2 groups. Bit k of the FSt bitmap is set when group k has any page in tier FSt.

One shard indexes L3_FANOUT (8) × L2_FANOUT (8) = 64 pages (ENTRIES_PER_SHARD). A search for tier FSt reads one L3 word (which groups have such a page), then one L2 word per candidate group (which slots), then only those L1 leaves — two summary loads and a handful of leaves. Clearing a tier bit across all 8 tiers is one masked 64-bit write (val &= ~(0x0101010101010101ULL << index)).

Figure 4 — how one shard indexes 64 pages. L3 fans out to eight L2 groups, each fanning out to eight L1 leaves (8 × 8 = 64). Each L2/L3 word is eight one-byte bitmaps stacked by tier: within a word, bit j of the FSt byte marks that child j holds a page in tier FSt, so a find for tier t is two summary loads plus a few leaf reads.

shard and bestspace — the containers:

// bestspace::shard — src/storage/bestspace.hpp  (fields, condensed)
class alignas (64) shard {
  atomic_wrapper<bool> m_allocating;               // single-allocator gate
  atomic_wrapper<L3>   m_L3;
  atomic_wrapper<L2>   m_L2[L3_FANOUT];             // 8
  atomic_wrapper<L1>   m_L1[L3_FANOUT * L2_FANOUT]; // 64
  std::atomic<std::uint64_t> m_recs_num, m_recs_sumlen;
  bestspace           &m_parent;
  struct { /* per-shard debug stats */ } m_stats;
};
static_assert (sizeof (shard) == 4800 && alignof (shard) == 64, "...");

// bestspace — src/storage/bestspace.hpp  (fields, condensed)
class bestspace {
  std::deque<shard>                        m_shards;       // shard_count of them
  tbb::concurrent_queue<bestspace_entry>   m_candidates;   // recycle queue
  std::uint16_t                            m_unfill_space; // per-heap update headroom
};

A shard is 4800 bytes; a bestspace at the default 8 shards is ~38 KB of index plus its candidate queue — the memory cost of the per-class, per-shard design, paid once per open heap file.

The find path — lock-free descent

bestspace::find is the hot path an INSERT calls. Given the record size it returns a fixed, WRITE-latched page with room, having already reserved the space in the index.

// bestspace::find — src/storage/bestspace.cpp  (control flow, condensed)
consume_space = size + SPAGE_SLOT_SIZE;                 // what the record takes
needed_space  = consume_space + m_unfill_space;         // plus update headroom
if (needed_space > heap_nonheader_page_capacity ())
  needed_space = consume_space;                          // headroom would never fit
while (true) {
  for (i = 0; i < m_shards.size (); i++) {
    error = m_shards[(shard + i) % m_shards.size ()]
              .find (class_oid, hfid, needed_space, consume_space, bias, page_watcher);
    if (error == FOUND)   return NO_ERROR;
    if (error == FAILURE) return er_errid ();
    // else ALLOCATING: this shard is mid-allocation, try the next
  }
  // every shard was ALLOCATING: yield / short sleep, check interrupt, retry
}

Two request sizes are threaded down: needed_space (record + slot + unfill_space headroom) decides tier eligibility, while consume_space (record + slot only) is subtracted from the page’s recorded free space on success. The unfill_space reserve keeps room for a later in-place update to grow without migrating.

Inside a shard the descent is L3_find → L2_find → L1_find:

flowchart TD
  A["shard::find(needed_size)"] --> B["minimum = size_to_tier(needed_size);\nif minimum < FS8: minimum++"]
  B --> C["L3_find: for tier t from minimum up to FS8\nload L3, list groups with a page at t"]
  C --> D["L2_find: for each candidate group\nload L2, list L1 slots at tier t"]
  D --> E["L1_find: load L1 slot"]
  E --> F{"recorded freespace\n>= needed_size?"}
  F -- no --> C
  F -- yes --> G["ordered_fix page\n(LK_FORCE_ZERO_WAIT)"]
  G -- timeout --> H["CONTENDED: skip this page"]
  G -- bad pageid --> I["stale: L1_remove, roll up"]
  G -- ok --> J{"still this class? actual\nspage free space >= needed?"}
  J -- no --> I
  J -- yes --> K["CAS L1 freespace -= consume_size\nL2_update / L3_update rollup"]
  K --> L["FOUND: return fixed page"]

Figure 5: the intra-shard descent. minimum is bumped one tier above the exact fit so a chosen page comfortably clears the request; the search still walks upward through richer tiers if the first is empty.

The subtle, load-bearing details:

• Advance one tier for headroom. minimum = size_to_tier(needed_size) then minimum++ (unless already FS8). Picking from a strictly richer tier avoids repeatedly landing on pages that just barely fit.
• Bias for fairness (scaffolded, inert at head). The structure threads a bias (used as pos[(i + bias) % length] at each level) and a rotating start shard so concurrent inserters descending the same bitmap would not all stampede the same first slot. At head 81061660a5, bestspace::find sets shard = 0; bias = 0; once and never advances them, so this anti-stampede rotation is present in the code but not yet active — worth re-checking as the PR evolves.
• The recorded free space can lie. L1_find first pre-filters on the atomic freespace word; only if that clears does it fix the page and read the truth via spage_max_space_for_new_record. If the truth is short, it CAS-corrects the L1 word (and rolls the correction up through L2/L3) and returns NOT_FOUND — a self-heal, echoing the legacy “recheck and repair.”
• Ownership check. After fixing, it verifies the page is still PAGE_HEAP and still belongs to class_oid; if not, the entry is removed. A page can have been deallocated and reused elsewhere since it was indexed.
• Contention is skip, not wait. L1_fix uses pgbuf_ordered_fix with LK_FORCE_ZERO_WAIT; a latch timeout becomes CONTENDED (try the next candidate), not a block — the same non-blocking discipline as legacy, now without any header latch above it.
• Reserve via CAS. On success the winning thread CASes the page’s L1 freespace down by consume_size. Only the thread that fixed the page and still sees the same VPID performs the update, so the reservation is single-writer per slot even though the structure is lock-free.
• pgbuf_ordered_fix everywhere. The whole path uses ordered fix so multiple page latches cannot deadlock — an explicit PR fix (“use ordered fix to avoid deadlock in bestspace path”).

If no shard yields a page and none is allocating, the outer loop yields (or sleeps 10 µs after 20 spins) and retries, honoring interrupts. A shard mid-allocation returns ALLOCATING and the caller simply advances — allocation never blocks a find.

The allocate path — victims, candidates, new pages

When a shard’s descent finds no page with room, shard::find calls allocate. This refills the index: it evicts the poorest slots and installs better pages, preferring recycled candidates over freshly allocated storage.

flowchart TD
  A["shard::allocate(consume_size)"] --> B{"allocate_mark:\nCAS m_allocating false to true"}
  B -- already set --> Z["ALLOCATING: caller advances\nto next shard"]
  B -- won --> C["allocate_pick_victims:\n4 L1 slots with least free space\n(also snapshot resident VPIDs)"]
  C --> D["allocate_pick_candidates:\npop from candidates queue,\nkeep those richer than the RICHEST victim,\ndedup vs residents  (up to 3)"]
  D --> E["allocate_new_pages:\nheap_alloc_new_pages for the remainder\n(batch of ALLOC_BATCH_SIZE = 4)"]
  E --> F["reserve one page for the caller\n(candidate[last].freespace -= consume_size)"]
  F --> G["allocate_replace_pages:\nstore new entries into victim L1 slots,\nL2_update / L3_update rollup"]
  G --> H["allocate_unmark; FOUND"]

Figure 6: refilling a shard. One allocator per shard at a time (the m_allocating gate); everyone else keeps searching other shards meanwhile.

• One allocator per shard. allocate_mark is a CAS on m_allocating; a loser returns ALLOCATING immediately, so the expensive allocation work is never duplicated or serialized across shards.
• Batch of four. ALLOC_BATCH_SIZE == 4. The shard refreshes up to its four weakest slots per allocation — three unconditionally, the fourth (richest of the victims) only if the replacement beats it — amortizing the cost and leaving several fresh pages, not one.
• Recycle before allocate. allocate_pick_candidates drains the candidates queue for pages richer than the richest of the four victims (with a MAX_POP_TRIES cap and dedup against resident pages); only allocate_new_pages allocates new storage for the shortfall via the batch primitive heap_alloc_new_pages. If the biggest victim is already very rich (>= FS8), candidate picking is skipped — better to allocate clean pages than shuffle.
• Guaranteed forward progress. allocate_new_pages always allocates at least the pages needed to reach the batch, so allocate returns with at least one usable page (the last, reserved for the caller).

Candidates queue and page recycling

The candidates queue (tbb::concurrent_queue<bestspace_entry> m_candidates) is the new home for “this page just gained free space.” It replaces the legacy second_best reservoir with a lock-free MPMC queue:

• Producers. Any path that frees space nominates the page via heap_add_bestpage(thread_p, hfid, page, prev_freespace) — the direct replacement for the legacy heap_stats_update, wired at the same call families: vacuum reclaiming space, the physical record-delete path (heap_delete_physical), and recovery undo of an insert (heap_rv_undo_insert). Candidates also enter from the heap header on rebuild.
• Admission floor (tier FS3). heap_add_bestpage enqueues a page only when its free space reaches tier FS3 (~25%) — the tier-based analogue of the legacy 30% HEAP_DROP_FREE_SPACE.
• Consumer. Only allocate drains the queue, and only as much as it needs (MAX_POP_TRIES), so a bulk vacuum that frees thousands of pages does not force a burst of index churn — pages wait until a shard actually refills. This is the new analogue of the legacy 1-in-1000 write-spreading, achieved structurally instead of by a sampling counter.
• Dedup. allocate skips candidates whose VPID already resides in the shard.

Registry and the thread-local cache

A bestspace must be found by (class_oid, HFID) on every insert, so the lookup itself must not become the new bottleneck. bestspace_registry (global singleton cubstorage::bestspaces) is a mutex-guarded global list fronted by a per-thread cache:

// bestspace_registry::find — src/storage/bestspace.cpp
bestspace *bestspace_registry::find (OID *class_oid, HFID *hfid) {
  bestspace *entry = find_from_cache (class_oid, hfid);  // thread-local, no lock
  if (entry) return entry;
  return find_from_global (class_oid, hfid);             // std::mutex, then cache it
}

• Thread-local first. Each thread keeps an LRU list of up to TLS_MAX_SIZE (20) recent (class_oid, HFID) → bestspace* entries; a hit takes no lock and moves to the front.
• Generation-stamped invalidation. The registry holds an atomic m_generation; destroy bumps it. On the next find, a thread whose cached generation differs invalidates its whole thread-local list in one comparison — a dropped table is never reachable through a stale cache pointer.
• Global fallback under mutex. A miss takes the registry mutex, finds the entry in the global list, releases the mutex, and installs the pointer in the thread-local cache.
• Lifecycle. create when a heap file’s bestspace is first needed or built; destroy(class_oid, vfid|hfid) when the heap file is dropped (see vacuum_rv_notify_dropped_file → bestspaces.destroy).

The mutex is touched only on cold lookups and lifecycle events; steady-state inserts resolve their heap file entirely in thread-local memory.

Figure 7 — resolving a heap file to its bestspace. A thread-local LRU cache answers the common case with no lock; a miss takes the registry mutex, resolves against the global list, and installs the pointer back into the cache. An atomic m_generation bumped by destroy drops a whole thread-local list in one comparison, so a dropped table is never reached through a stale pointer.

On-disk persistence and recovery

The in-memory index is derived state, but rebuilding it from a full heap scan after every restart would be prohibitive, so a compact, reconstructable form is persisted. The heap header’s old estimates block is gone; in its place is a bestspace sub-struct:

// heap_hdr_stats — src/storage/heap_file.c  (next-version, condensed)
struct heap_hdr_stats {
  OID   class_oid;
  VFID  ovf_vfid;
  VPID  next_vpid, last_vpid;
  int   unfill_space;
  int   num_pages;  uint64_t num_recs;  uint64_t recs_sumlen;  // aggregate estimates kept
  struct {
    int  num_candidates;
    cubstorage::bestspace_entry candidates[128];  // pending candidates, persisted inline
    int  num_shards;
    int  num_pages;
    VPID pages[4];                                 // up to 4 dedicated storage pages
  } bestspace;
  int reserve0, reserve1, reserve2;
};

• Aggregate counters survive. num_pages, num_recs, recs_sumlen remain (promoted out of estimates) to feed average-record-size estimates. The best[10] / second_best[10] rings and cursors are deleted outright.
• Serialized L1 entries. The shards’ num_shards × 64 L1 entries serialize to up to four dedicated heap pages (bestspace.pages[4]), each flagged HEAP_PAGE_FLAG_BESTSPACE. Header helpers (heap_create_bestspace, heap_update_bestspace) allocate, write, and update them.
• Inline candidates. Up to 128 pending candidates live in the header (candidates[128], num_candidates), managed by heap_bestspace_add_candidate / heap_bestspace_clear_candidates.
• Logged updates. On-disk entry updates are redo-logged under a new recovery index RVHF_UPDATE_BESTSPACE_ENTRIES (redo handler heap_rv_redo_update) — unlike the legacy hints, the persisted form participates in recovery so a rebuilt index starts from a consistent snapshot.
• Rebuild on demand. With no in-memory bestspace (first access or after restart), heap_build_bestspace reads the header, loads entries and candidates from the storage pages, and calls bestspaces.create(class_oid, hfid, entries, num_entries, candidates, num_candidates, num_shards, unfill_space). compactdb refreshes the persisted form.

Figure 8 — the durable form. The heap header carries aggregate estimates, up to 128 inline candidates, and up to four VPIDs pointing at dedicated storage pages (flagged HEAP_PAGE_FLAG_BESTSPACE) that hold the serialized L1 entries; updates are redo-logged under RVHF_UPDATE_BESTSPACE_ENTRIES. After a restart, heap_build_bestspace reconstructs the in-memory index, and heap scans skip the flagged pages so metadata is never read as records.

Because the L1 entries and candidates live in real heap pages, heap scans must skip them. A predicate heap_page_is_bestspace() (backed by HEAP_PAGE_FLAG_BESTSPACE) is checked at the ~15 heap-scan sites that must not treat a metadata page as a record page — e.g. the parallel heap scan (px_scan_input_handler_heap) and partition redistribution (redistribute_partition_data) — which advance past bestspace storage pages.

Integration points

Beyond the two new files, PR #7353 touches ~20 files:

Area	File	Change
System parameter	system_parameter.c/.h	New bestspace_shard_count (PRM_ID_BESTSPACE_SHARD_COUNT, server, user-changeable, default 8, min 1, max 28). PRM_ID_HF_MAX_BESTSPACE_ENTRIES marked PRM_OBSOLETED.
Vacuum	vacuum.c	Freed pages nominated via heap_add_bestpage; on drop, cubstorage::bestspaces.destroy(class_oid, vfid).
Parallel scan	px_scan_input_handler_heap.cpp	Skip pages where heap_page_is_bestspace is true.
Partitioning	locator_sr.c	redistribute_partition_data skips bestspace storage pages.
Slotted page	slotted_page.c/.h, storage_common.h	Remove the need_update_best_hint header bit, spage_set_need_update_best_hint, the need_update out-param of spage_get_free_space_without_saving, and HEAP_PAGE_INFO_UPDATE_BEST.
SHOW meta	show_meta.c	SHOW HEAP HEADER drops the whole Estimates_* column set; now exposes Last_vpid, Unfill_space, Num_pages, Num_recs, Avg_rec_len. Slotted-header show drops Need_update_best_hint.
Recovery	recovery.c/.h	New RVHF_UPDATE_BESTSPACE_ENTRIES = 130 (RV_LAST_LOGID bumped).
Heap API	heap_file.h	Remove HEAP_DROP_FREE_SPACE, HEAP_BESTSPACE, heap_stats_update. Add heap_add_bestpage, heap_alloc_new_pages (batch), heap_page_is_bestspace.
Build	CMakeLists.txt (×2)	Compile bestspace.cpp; link TBB.

Within heap_file.c (a ~2600/2770 line rewrite), the legacy heap_stats_* machinery (heap_stats_find_page_in_bestspace, heap_stats_sync_bestspace, heap_stats_put/get_second_best, heap_Bestspace) is removed, and a new heap_find_bestpage / heap_find_bestspace / heap_build_bestspace layer delegates to cubstorage::bestspaces.

Legacy vs. next-version

Dimension	Legacy heap_Bestspace	Next-version cubstorage::bestspace
Scope	One process-global hash for all heaps	One structure per heap file (class_oid, HFID)
Concurrency control	Heap-header WRITE latch across the whole selection + a global bestspace_mutex	Sharded, lock-free (per-node CAS on 64B-aligned atomics); mutex only on registry cold path
Parallelism unit	One inserter per heap at a time	bestspace_shard_count (default 8) independent shards per heap
Index structure	Global hash + on-disk best[10] / second_best[10] rings	3-level bitmap (L3/L2/L1) over 64 slots per shard
Free-space classes	One 30% floor (HEAP_DROP_FREE_SPACE)	9 tiers (FS0–FS8)
Page reuse	second_best reservoir, 1-in-1000 admission	Lock-free candidates queue, drained on demand
Fed by	Delete/update/vacuum → heap_stats_update	Delete / vacuum / insert-undo → heap_add_bestpage (candidate, ≥ FS3)
Lookup cost	Hash probe under mutex, then disk ring under header latch	Thread-local registry hit (no lock) → shard bitmap descent
Persistence	Header estimates ring, unlogged	Header sub-struct + dedicated pages, redo-logged (RVHF_UPDATE_BESTSPACE_ENTRIES)
Recovery	Stale hints, re-synced by next insert	Rebuilt from persisted snapshot via heap_build_bestspace
Tuning knob	bestspace_max_entries (now obsolete)	bestspace_shard_count (1–28)
Scan interaction	Hints reference normal pages	Storage pages flagged HEAP_PAGE_FLAG_BESTSPACE, skipped by scans

Both remain approximate — a recorded free space may be wrong, and the code rechecks the real page and self-heals. The change is not accuracy; it is where the coordination happens: from a central latched header ring to a distributed lock-free per-class index.

Source Walkthrough

Symbols grouped by role.

New free-space index (src/storage/bestspace.hpp, src/storage/bestspace.cpp):

• cubstorage::bestspace_entry — 8-byte page hint.
• bestspace::tier, bestspace::size_to_tier — the FS0–FS8 tiering.
• bestspace::bitmap, bestspace::L1, bestspace::L2, bestspace::L3 — the three-level bitmap and its leaf.
• bestspace::atomic_wrapper<T> — 64-byte-aligned lock-free wrapper.
• bestspace::shard and its methods: find, L3_find/L2_find/L1_find, L1_fix/L1_remove, L2_update/L3_update, allocate, allocate_mark/allocate_unmark, allocate_pick_victims, allocate_pick_candidates, allocate_new_pages, allocate_replace_pages, initialize_by_entries.
• bestspace (top): find, initialize_by_entries, add_candidates, pop_candidate, size_to_tier, show_stats.
• bestspace_registry and cubstorage::bestspaces: find, find_from_cache/find_from_global, create (×2), destroy (×2), TLS_cache, m_generation.

Heap-manager integration (src/storage/heap_file.c, heap_file.h):

• heap_find_bestpage — hot-path entry: resolve heap file → bestspace, call bestspace::find.
• heap_find_bestspace, heap_build_bestspace — resolve-or-build against the registry.
• heap_create_bestspace, heap_update_bestspace, heap_update_bestspace_chain — persist / update the on-disk form.
• heap_bestspace_add_candidate, heap_bestspace_clear_candidates — header candidate list.
• heap_add_bestpage — nominate a page as a candidate (delete / vacuum / insert-undo paths; enqueues only at tier ≥ FS3).
• heap_alloc_new_pages — batch page allocator used by shard::allocate.
• heap_page_is_bestspace — predicate over HEAP_PAGE_FLAG_BESTSPACE.
• heap_hdr_stats.bestspace — the header sub-struct.

Other files: PRM_ID_BESTSPACE_SHARD_COUNT (system_parameter.c); RVHF_UPDATE_BESTSPACE_ENTRIES (recovery.h); heap_page_is_bestspace call sites in px_scan_input_handler_heap.cpp and locator_sr.c.

Source verification (as of 2026-07-08)

Line hints are from PR #7353 head 81061660a5 (the CBRD-26858 branch), not from develop. They will not match the base branch and will drift as the PR evolves. Anchor on the symbol names.

Symbol	File	Line (PR head 81061660a5)
bestspace_entry	src/storage/bestspace.hpp	49
bestspace::tier (enum)	src/storage/bestspace.hpp	83
bestspace::shard (class)	src/storage/bestspace.hpp	237
bestspace (class)	src/storage/bestspace.hpp	69
bestspace_registry	src/storage/bestspace.hpp	357
bestspace::shard::find	src/storage/bestspace.cpp	302
bestspace::shard::L3_find	src/storage/bestspace.cpp	341
bestspace::shard::L1_find	src/storage/bestspace.cpp	490
bestspace::shard::L1_fix	src/storage/bestspace.cpp	574
bestspace::shard::allocate	src/storage/bestspace.cpp	789
bestspace::shard::allocate_pick_candidates	src/storage/bestspace.cpp	680
bestspace::find	src/storage/bestspace.cpp	892
bestspace::size_to_tier	src/storage/bestspace.cpp	986
bestspace_registry::find	src/storage/bestspace.cpp	1150
bestspace_registry::find_from_cache	src/storage/bestspace.cpp	1163
cubstorage::bestspaces (global)	src/storage/bestspace.cpp	1345
RVHF_UPDATE_BESTSPACE_ENTRIES	src/transaction/recovery.h	187
heap_page_is_bestspace (decl)	src/storage/heap_file.h	(added)
heap_add_bestpage (decl)	src/storage/heap_file.h	(added)
heap_alloc_new_pages (decl)	src/storage/heap_file.h	(added)

Cross-check Notes

This doc analyzes an unmerged draft; the usual version-drift caveats apply, plus a few specific to that state:

• Line hints are PR-branch, not develop. The position-hint table is anchored to head 81061660a5 on branch CBRD-26858. When the PR merges (squash), all line numbers change; re-verify against the merge commit and re-anchor.
• heap_file.c line hints omitted. The heap-side integration symbols are named but not line-pinned — the file is a ~2600/2770-line rewrite still in flux, so per-symbol lines would be stale on the next force-push. Anchor on the symbol names until the PR stabilizes.
• Bias/round-robin scaffolding is inert at head. bestspace::find fixes shard = 0; bias = 0, so the anti-stampede rotation described in §“The find path” is present but not active. If a later commit wires it, the “divergence comes only from a skipped mid-allocation shard” claim becomes obsolete.
• Legacy contrast pinned to Chapter 9. The legacy baseline and comparison table are cross-checked against cubrid-heap-manager-detail.md Chapter 9 as of its updated: date. If that doc is revised, re-check the comparison table.
• show_stats via printf. The debug stats print to stdout, and the registry destructor prints per-class stats — development-time instrumentation likely to change or be removed before merge; do not treat as a stable observability surface.
• ASSM L1/L2/L3 analogy is illustrative, not a claim of shared code. The parallel to Oracle ASSM in §“Common DBMS Design” is a design-family observation (per-block bitmap hierarchy keyed by fullness), not an assertion that CUBRID ported Oracle’s structure.

Open Questions

1. Performance validation is pending. CBRD-26176’s acceptance criterion — measured load distribution and throughput gain under INSERT-heavy load — is the point of the change but not something this static analysis can confirm. How it scales with bestspace_shard_count needs the benchmark.
2. Shard-count tuning and migration. Default 8, max 28. What guides the choice — core count, per-table insert concurrency, memory (≈ 4800 B/shard)? On rebuild, heap_build_bestspace takes the shard count from the live parameter, not the persisted bestspace.num_shards (which only sizes how many L1 entries to deserialize; surplus entries spill into the candidate queue), so after a parameter change plus restart a heap adopts the new shard count.
3. Candidate-queue and header-candidates[128] overflow. If producers outrun allocate, does the concurrent queue grow unbounded, and how are more than 128 pending candidates handled at persist time?
4. Memory footprint. ~38 KB per open heap file at default shard count, per class_oid+HFID; there is no global cap analogous to the obsoleted bestspace_max_entries. Worth measuring for schemas with many tables / partitions.
5. Recovery correctness of the lock-free rollup. The L2_update/L3_update CAS retry loops re-derive summaries under concurrent mutation; the interaction between an in-flight allocate and a crash deserves scrutiny once the code stabilizes.
6. Interaction with Direct I/O. CBRD-26176 is linked as a regression of CBRD-26141 [POC] Direct I/O 지원 — whether bestspace-page I/O assumes buffered semantics is unresolved here.

Sources

• PR / issues.
  • PR #7353 [CBRD-26176] bestspace — head 81061660a5, base develop (draft).
  • CBRD-26857 [EPIC] — 힙 파일 여유 공간(best space) 관리 구조 개선 (Sharded Lock-free Bestspace Index).
  • CBRD-26858 [조사/설계] — 타사 여유 공간 정책 조사 및 개선 설계 (Oracle freelist/ASSM, PostgreSQL FSM); the survey behind §“Common DBMS Design”.
  • CBRD-26176 — 다수 트랜잭션 동시 INSERT 시 best space 정책 성능 병목 해결.
  • Related: CBRD-26806 (중앙 집중형 metadata 경합 분석), CBRD-26141 ([POC] Direct I/O).
• Source (PR head 81061660a5). src/storage/bestspace.{hpp,cpp}, src/storage/heap_file.{c,h}, src/storage/slotted_page.{c,h}, src/storage/storage_common.h, src/query/vacuum.c, src/query/parallel/px_scan/px_scan_input_handler_heap.cpp, src/transaction/locator_sr.c, src/transaction/recovery.{c,h}, src/base/system_parameter.{c,h}, src/parser/show_meta.c.
• Textbook. Petrov, Database Internals, Ch. 3–4 (slotted page, free space) — see ../../research/dbms-general/ captures.
• Related KB docs. cubrid-heap-manager.md (heap fundamentals, free-space intent), cubrid-heap-manager-detail.md Chapter 9 (the legacy bestspace machinery in full), cubrid-lockfree-overview.md (CUBRID’s lock-free building blocks), cubrid-disk-manager.md (page allocation).