Skip to content

armgit / xerj

Public Imported from GitHub
0

AI search engine and MCP server for bots and agents. One Rust binary indexes code, docs, logs, JSONL/CSV and PDFs for BM25 full-text, vector and hybrid search, code search without grep, agent memory and RAG. Elasticsearch-compatible API; Corpus Hub serves hundreds of reference memory corpora.

49.3 KB
Raw Blame
//! Lock-free document version tracking.
//!
//! Every indexed document has an entry in the version map that records the
//! highest sequence number seen for that `doc_id` and the segment (or
//! "in-memory" sentinel) that owns the latest version.
//!
//! ## Design
//!
//! The core data structure is a [`DashMap`], which is a concurrent hash map
//! that shards its lock space — reads and writes on disjoint key ranges do not
//! block each other.
//!
//! ### Conflict detection (optimistic concurrency)
//!
//! When a document arrives with `if_seq_no` / `if_primary_term` constraints
//! (Elasticsearch's optimistic concurrency), [`VersionMap::check_and_set`]
//! performs an atomic compare-and-swap:
//!
//! 1. Acquire the shard lock for the key.
//! 2. Read the current `(seq_no, segment_id)`.
//! 3. If the caller's expected seq_no matches, update and return `Ok(new_seq)`.
//! 4. Otherwise return `Err(VersionConflict)`.
//!
//! Because `DashMap::entry` holds the shard guard for the duration of the
//! closure, steps 2-3 are atomic with respect to other writers on the same key.
//!
//! ## Cleanup
//!
//! After a merge, call [`VersionMap::remove_segment`] to drop all entries whose
//! `segment_id` points to one of the now-deleted segments.  The merged segment's
//! ID is already written into the map during the merge process, so this removes
//! only stale / duplicate references.

use std::sync::atomic::{AtomicI64, AtomicUsize, Ordering};
use std::sync::Arc;

use dashmap::DashMap;
use tracing::debug;

use crate::segment::SegmentId;
use crate::{Result, SeqNo, StorageError};

/// Sentinel segment ID used for documents that are in the in-memory write buffer
/// (not yet flushed to any segment file).
pub const IN_MEMORY_SEGMENT_ID: &str = "__memtable__";

// ── VersionEntry ──────────────────────────────────────────────────────────────

/// Per-document version record.
///
/// `segment_id` is `Arc<str>` rather than `String` so that `VersionMap::get`
/// returns a cheap-to-clone view (one atomic increment) — the entry is read on
/// every doc lookup in the search/index hot path, and the same handful of
/// segment IDs (`__memtable__` + active segment IDs) is shared by millions of
/// entries.  Hoisting an `Arc::from(IN_MEMORY_SEGMENT_ID)` once per ingest
/// batch and `Arc::clone`-ing per doc replaces a per-doc `String` allocation
/// with one atomic.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct VersionEntry {
    /// The latest sequence number for this document.
    pub seq_no: SeqNo,
    /// The segment that owns the latest version (`IN_MEMORY_SEGMENT_ID` while
    /// the document is buffered in memory).
    pub segment_id: Arc<str>,
    /// `true` if the document has been deleted (tombstoned).
    pub deleted: bool,
    /// ES `_version`: per-document write counter, starting at 1 on first
    /// index and incremented by every subsequent index or delete of the
    /// same `doc_id` (deletes bump it too — the tombstone carries the
    /// bumped version, matching ES delete responses).
    ///
    /// Physical repoints (flush moving a doc from the memtable to its
    /// segment, merges repointing surviving docs) do NOT bump it: they
    /// re-record the same logical write.
    ///
    /// Restart caveat: the map is rebuilt from segments + WAL tail on
    /// open, so the counter restarts from the recovered history rather
    /// than the true lifetime write count (CAS is unaffected — it
    /// compares `seq_no`, which is durable).
    pub version: u64,
}

// ── VersionMap ───────────────────────────────────────────────────────────────

/// Owned doc-id key stored in every bucket of the map (#2427).
///
/// 24 B, and in the common cases the id needs no heap allocation at all:
/// - a 32-char lowercase hex id (what `xerj autoindex` and many content
///   hash schemes write) packs into 16 raw bytes;
/// - a lowercase hyphenated UUID packs the same way;
/// - anything else is a `CompactString`, inline up to 24 bytes (ES auto
///   ids are 20 chars) and heap-allocated only beyond that.
///
/// A `Box<str>` key (16 B) always paid a separate allocation on top of the
/// bucket: one 48 B allocator size class for a 32-char id. The encoding is
/// canonical (an id has exactly one form), so the derived `Hash`/`Eq` match
/// string equality, and [`MapKey::to_id`] round-trips the exact string.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
enum MapKey {
    Hex32([u8; 16]),
    Uuid([u8; 16]),
    Str(compact_str::CompactString),
}

const UUID_DASHES: [usize; 4] = [8, 13, 18, 23];
const HEX_DIGITS: &[u8; 16] = b"0123456789abcdef";

#[inline]
fn hex_nibble(c: u8) -> Option<u8> {
    match c {
        b'0'..=b'9' => Some(c - b'0'),
        b'a'..=b'f' => Some(c - b'a' + 10),
        _ => None,
    }
}

/// Pack 32 lowercase hex digits (yielded in order) into 16 bytes.
#[inline]
fn pack_hex(mut digits: impl Iterator<Item = u8>) -> Option<[u8; 16]> {
    let mut out = [0u8; 16];
    for byte in &mut out {
        let hi = hex_nibble(digits.next()?)?;
        let lo = hex_nibble(digits.next()?)?;
        *byte = hi << 4 | lo;
    }
    Some(out)
}

impl MapKey {
    fn new(id: &str) -> Self {
        let b = id.as_bytes();
        if b.len() == 32 {
            if let Some(packed) = pack_hex(b.iter().copied()) {
                return MapKey::Hex32(packed);
            }
        } else if b.len() == 36 && UUID_DASHES.iter().all(|&i| b[i] == b'-') {
            let digits = b
                .iter()
                .enumerate()
                .filter(|(i, _)| !UUID_DASHES.contains(i))
                .map(|(_, &c)| c);
            if let Some(packed) = pack_hex(digits) {
                return MapKey::Uuid(packed);
            }
        }
        MapKey::Str(compact_str::CompactString::new(id))
    }

    /// The original id string.
    fn to_id(&self) -> String {
        fn hex(bytes: &[u8; 16], dashes: bool) -> String {
            let mut out = String::with_capacity(36);
            for (i, byte) in bytes.iter().enumerate() {
                if dashes && matches!(i, 4 | 6 | 8 | 10) {
                    out.push('-');
                }
                out.push(HEX_DIGITS[(byte >> 4) as usize] as char);
                out.push(HEX_DIGITS[(byte & 0xf) as usize] as char);
            }
            out
        }
        match self {
            MapKey::Hex32(b) => hex(b, false),
            MapKey::Uuid(b) => hex(b, true),
            MapKey::Str(s) => s.to_string(),
        }
    }

    /// Bytes this key holds outside its bucket (0 unless a long `Str`).
    #[inline]
    fn heap_len(&self) -> usize {
        match self {
            MapKey::Str(s) if s.is_heap_allocated() => s.len(),
            _ => 0,
        }
    }
}

/// High bit of [`Slot::version_deleted`]: the tombstone flag.
const DELETED_BIT: u64 = 1 << 63;

/// In-map representation of a [`VersionEntry`] (#2427).
///
/// The tombstone flag is folded into the high bit of the version counter,
/// so a slot is 32 B instead of the 40 B `VersionEntry` (whose `bool` pads
/// out to a full word). Converted to/from `VersionEntry` only at the
/// public API boundary; callers never see this type.
#[derive(Debug, Clone, PartialEq, Eq)]
struct Slot {
    seq_no: SeqNo,
    segment_id: Arc<str>,
    version_deleted: u64,
}

impl Slot {
    #[inline]
    fn new(seq_no: SeqNo, segment_id: Arc<str>, deleted: bool, version: u64) -> Self {
        let flag = if deleted { DELETED_BIT } else { 0 };
        Self {
            seq_no,
            segment_id,
            version_deleted: (version & !DELETED_BIT) | flag,
        }
    }

    #[inline]
    fn deleted(&self) -> bool {
        self.version_deleted & DELETED_BIT != 0
    }

    #[inline]
    fn version(&self) -> u64 {
        self.version_deleted & !DELETED_BIT
    }

    #[inline]
    fn set_version(&mut self, version: u64) {
        self.version_deleted = (self.version_deleted & DELETED_BIT) | (version & !DELETED_BIT);
    }

    #[inline]
    fn to_entry(&self) -> VersionEntry {
        VersionEntry {
            seq_no: self.seq_no,
            segment_id: Arc::clone(&self.segment_id),
            deleted: self.deleted(),
            version: self.version(),
        }
    }
}

impl From<VersionEntry> for Slot {
    fn from(e: VersionEntry) -> Self {
        Slot::new(e.seq_no, e.segment_id, e.deleted, e.version)
    }
}

/// Concurrent, lock-free document version map.
pub struct VersionMap {
    /// doc_id → VersionEntry
    ///
    /// Buckets are `(MapKey, Slot)` = 56 B (#2427): hex, UUID and short
    /// ids live inside the key with no separate allocation, and the
    /// tombstone flag shares a word with the version counter. An incoming `String` is copied to its exact length,
    /// never kept with spare capacity for the life of the index.
    inner: DashMap<MapKey, Slot>,
    /// Sum of out-of-line key bytes ([`MapKey::heap_len`]) in the map: the
    /// key heap half of
    /// [`VersionMap::heap_bytes`] (#2427). Maintained on every insert of a
    /// new key and every removal.
    key_heap: AtomicUsize,
    /// Maintained count of live (non-deleted) entries.
    ///
    /// `live_count()` used to iterate the whole map (`O(entries)`), which
    /// put an ~80 ms fixed cost on EVERY search over a 1 M-doc index — the
    /// query path calls it for the `deletes_present` gate and the shortcut
    /// guards.  Each mutating method applies its delta from the entry state
    /// it atomically displaced (the `DashMap` shard lock linearises
    /// per-key updates, so concurrent writers each observe a distinct
    /// old-value and the deltas sum exactly).  `i64` (not `u64`) so a
    /// transiently-interleaved reader can never underflow the type;
    /// `live_count()` clamps at 0.
    live: AtomicI64,
    /// Monotonic count of "ghost-producing" events: overwrites of an
    /// existing doc id and deletes.  Each such event leaves a physically
    /// present but superseded/tombstoned copy in the memtable or a
    /// segment until a merge purges it.
    ///
    /// The search fast paths (`deletes_present` gates in `search_inner` /
    /// `fast_aggs`) used to INFER this state from
    /// `live_count() < Σ segment doc_count + memtable doc_count` — but
    /// that arithmetic also trips on any unrelated physical-count drift
    /// (live-verified: two duplicate docs per merged segment flipped the
    /// gate permanently on a pure append-only workload, forcing every
    /// size>0 term/range/bool query into a full O(N) stored scan — the
    /// core of the read-under-write collapse).  This counter is the
    /// exact signal: zero ⇔ no update/delete has ever produced a ghost.
    ///
    /// Monotonic by design (never decremented on merge): once an index
    /// has seen updates, the delete-aware slow paths stay on.  That is
    /// conservative but always correct.
    ghost_events: std::sync::atomic::AtomicU64,
}

#[derive(Debug)]
struct VersionRepointChange {
    doc_id: String,
    previous: Option<Slot>,
    installed: Slot,
}

/// Panic- and cancellation-safe group of physical version-map repoints.
///
/// Merge output identities are repointed before snapshot publication. Unless
/// publication commits this transaction, drop restores only entries that
/// still exactly match values installed by the transaction. A concurrent
/// newer write or delete therefore always wins over rollback.
pub struct VersionRepointTransaction {
    map: Arc<VersionMap>,
    changes: Vec<VersionRepointChange>,
    committed: bool,
}

impl VersionRepointTransaction {
    /// Reserve the complete rollback log before mutating the map.
    pub fn with_capacity(map: Arc<VersionMap>, capacity: usize) -> Self {
        Self {
            map,
            changes: Vec::with_capacity(capacity),
            committed: false,
        }
    }

    /// Conditionally repoint an entry and remember the exact displaced value.
    pub fn repoint_if_latest(
        &mut self,
        doc_id: &str,
        seq_no: SeqNo,
        segment_id: Arc<str>,
        deleted: bool,
    ) {
        debug_assert!(
            self.changes.len() < self.changes.capacity(),
            "merge rollback log must be reserved before repoint"
        );
        use dashmap::mapref::entry::Entry;
        let (previous, installed) = match self.map.inner.entry(MapKey::new(doc_id)) {
            Entry::Occupied(mut occupied) => {
                if seq_no < occupied.get().seq_no {
                    return;
                }
                let previous = occupied.get().clone();
                let installed = Slot::new(seq_no, segment_id, deleted, previous.version());
                occupied.insert(installed.clone());
                if previous.seq_no != seq_no || (deleted && !previous.deleted()) {
                    self.map.ghost_events.fetch_add(1, Ordering::Relaxed);
                }
                self.map.live_delta(!previous.deleted(), !deleted);
                (Some(previous), installed)
            }
            Entry::Vacant(vacant) => {
                self.map.key_added(vacant.key());
                let installed = Slot::new(seq_no, segment_id, deleted, 1);
                vacant.insert(installed.clone());
                if deleted {
                    self.map.ghost_events.fetch_add(1, Ordering::Relaxed);
                }
                self.map.live_delta(false, !deleted);
                (None, installed)
            }
        };
        self.changes.push(VersionRepointChange {
            doc_id: doc_id.to_owned(),
            previous,
            installed,
        });
    }

    /// Keep all repoints after the snapshot publication succeeds.
    pub fn commit(mut self) {
        self.committed = true;
    }

    fn rollback(&mut self) {
        use dashmap::mapref::entry::Entry;
        for change in self.changes.drain(..).rev() {
            let Entry::Occupied(mut occupied) = self.map.inner.entry(MapKey::new(&change.doc_id))
            else {
                continue;
            };
            if occupied.get() != &change.installed {
                continue;
            }
            let current_live = !occupied.get().deleted();
            match change.previous {
                Some(previous) => {
                    let previous_live = !previous.deleted();
                    occupied.insert(previous);
                    self.map.live_delta(current_live, previous_live);
                }
                None => {
                    let (key, _) = occupied.remove_entry();
                    self.map.key_removed(&key);
                    self.map.live_delta(current_live, false);
                }
            }
        }
    }
}

impl Drop for VersionRepointTransaction {
    fn drop(&mut self) {
        if !self.committed {
            self.rollback();
        }
    }
}

impl VersionMap {
    /// Create an empty version map.
    pub fn new() -> Self {
        Self {
            // #873 — one of these exists per open index, and dashmap's default
            // shard array is sized from the host core count (128 shards ×
            // 128 B on a 32-core box, resident from construction). Cap it: the
            // concurrency this map sees is the write concurrency on ONE index.
            inner: DashMap::with_shard_amount(xerj_common::resource::per_index_map_shards()),
            key_heap: AtomicUsize::new(0),
            live: AtomicI64::new(0),
            ghost_events: std::sync::atomic::AtomicU64::new(0),
        }
    }

    #[inline]
    fn key_added(&self, key: &MapKey) {
        self.key_heap.fetch_add(key.heap_len(), Ordering::Relaxed);
    }

    #[inline]
    fn key_removed(&self, key: &MapKey) {
        self.key_heap.fetch_sub(key.heap_len(), Ordering::Relaxed);
    }

    /// Estimated heap held by this map, in bytes (#2427): the hash tables
    /// (buckets derived from capacity at hashbrown's 7/8 load factor, one
    /// control byte each) plus the doc-id key strings. O(shards). Reported
    /// as the `version_map` ingest-memory category; on a search node with
    /// ~2.6 M docs open this was ~0.5 GB that no budget saw.
    pub fn heap_bytes(&self) -> usize {
        let slot = std::mem::size_of::<(MapKey, Slot)>() + 1;
        let buckets = self.inner.capacity().saturating_mul(8) / 7;
        buckets.saturating_mul(slot) + self.key_heap.load(Ordering::Relaxed)
    }

    /// Apply a live-count delta for an entry transition.
    #[inline]
    fn live_delta(&self, old_live: bool, new_live: bool) {
        let delta = new_live as i64 - old_live as i64;
        if delta != 0 {
            self.live.fetch_add(delta, Ordering::Relaxed);
        }
    }

    /// Return the current version entry for `doc_id`, if any.
    pub fn get(&self, doc_id: &str) -> Option<VersionEntry> {
        self.inner
            .get(&MapKey::new(doc_id))
            .map(|e| e.value().to_entry())
    }

    /// Unconditionally record a new version for `doc_id`.
    ///
    /// Used when indexing without optimistic concurrency control (most writes).
    ///
    /// `segment_id` accepts anything convertible to `Arc<str>` — a `&str`
    /// allocates a fresh shared buffer, a `String` is consumed in place, and
    /// an existing `Arc<str>` performs a single atomic increment with no
    /// allocation.  Hot-path callers (per-doc loops in `wal_append_batch_*`)
    /// should hoist the conversion above the loop and pass `Arc::clone` per
    /// iteration.
    pub fn set(
        &self,
        doc_id: impl Into<String>,
        seq_no: SeqNo,
        segment_id: impl Into<Arc<str>>,
        deleted: bool,
    ) -> u64 {
        let doc_id = doc_id.into();
        debug!(?doc_id, seq_no, "version_map::set");
        use dashmap::mapref::entry::Entry;
        // Per-doc `_version`: a STRICTLY newer seq is a new logical write
        // (bump); an equal seq is a physical repoint of the same write
        // (keep); an older seq only occurs on replay/recovery re-sets of
        // an already-superseded copy (keep — the newer write already
        // counted itself).  Computed and written under the dashmap shard
        // guard so racing writers on the same key each derive from the
        // exact entry they displace.
        let (version, was_overwrite, old_was_live) = match self.inner.entry(MapKey::new(&doc_id)) {
            Entry::Occupied(mut occ) => {
                let old_seq = occ.get().seq_no;
                let old_live = !occ.get().deleted();
                let version = if seq_no > old_seq {
                    occ.get().version() + 1
                } else {
                    occ.get().version()
                };
                occ.insert(Slot::new(seq_no, segment_id.into(), deleted, version));
                (version, old_seq != seq_no, old_live)
            }
            Entry::Vacant(vac) => {
                self.key_added(vac.key());
                vac.insert(Slot::new(seq_no, segment_id.into(), deleted, 1));
                (1, false, false)
            }
        };
        // Overwrite or delete — a superseded/tombstoned physical copy now
        // exists somewhere until merged away.  A same-seq_no re-set is NOT
        // an overwrite: the flush path repoints every drained doc's entry
        // from `__memtable__` to its segment id with the seq_no unchanged
        // (live-verified: counting those flipped the gate ON for every
        // flushed doc and re-disabled all fast paths under pure appends).
        if was_overwrite || deleted {
            self.ghost_events.fetch_add(1, Ordering::Relaxed);
        }
        self.live_delta(old_was_live, !deleted);
        version
    }

    /// Record `doc_id → (seq_no, segment_id)` only if `seq_no` is >= the
    /// currently recorded seq_no (or the doc is unknown).
    ///
    /// Used by the merge task to repoint surviving docs at the merged
    /// segment with their REAL per-doc seq_nos:
    /// - `>=` (not `>`): the surviving doc's entry currently points at a
    ///   merged-away INPUT segment with the SAME seq_no — equality must
    ///   win or `apply_merge → remove_segment` would drop the entry (and
    ///   the doc) entirely.
    /// - guarded (not unconditional `set`): a doc updated concurrently
    ///   while the merge ran has a NEWER entry pointing at the memtable /
    ///   another segment — clobbering it with the merged copy would
    ///   resurrect the stale version.
    ///
    /// Atomic per key via the dashmap entry API.
    ///
    /// Live/ghost accounting (RC4 W2 #14): applies the same deltas as
    /// [`set`](Self::set) whenever it actually replaces/creates an entry.
    /// For the historical merge-repoint caller this is a no-op delta
    /// (same seq, live→live), so behavior is unchanged there; the
    /// tombstone-persistence paths (flush repoint, segment-tombstone
    /// rebuild apply) rely on the accounting being correct for
    /// live→deleted transitions.
    pub fn set_if_latest(
        &self,
        doc_id: impl Into<String>,
        seq_no: SeqNo,
        segment_id: impl Into<Arc<str>>,
        deleted: bool,
    ) {
        let doc_id = doc_id.into();
        use dashmap::mapref::entry::Entry;
        match self.inner.entry(MapKey::new(&doc_id)) {
            Entry::Occupied(mut occ) => {
                if seq_no >= occ.get().seq_no {
                    // Physical repoint of an already-counted write — the
                    // per-doc `_version` is carried over unchanged (A1-A3).
                    let version = occ.get().version();
                    // Capture the displaced entry for live/ghost accounting
                    // (RC4 W2 #14).
                    let old = occ.insert(Slot::new(seq_no, segment_id.into(), deleted, version));
                    // Mirror `set`: a same-seq repoint is NOT an overwrite
                    // (see the flush-repoint note there); a tombstone that
                    // REPLACES a live entry is a ghost event.
                    let is_overwrite = old.seq_no != seq_no;
                    if is_overwrite || (deleted && !old.deleted()) {
                        self.ghost_events.fetch_add(1, Ordering::Relaxed);
                    }
                    self.live_delta(!old.deleted(), !deleted);
                }
            }
            Entry::Vacant(vac) => {
                self.key_added(vac.key());
                vac.insert(Slot::new(seq_no, segment_id.into(), deleted, 1));
                if deleted {
                    self.ghost_events.fetch_add(1, Ordering::Relaxed);
                }
                self.live_delta(false, !deleted);
            }
        }
    }

    /// Attempt an atomic compare-and-set.
    ///
    /// - If `expected_seq_no` is `None`, succeeds only if the document does NOT
    ///   exist yet (create-only semantics).
    /// - If `expected_seq_no` is `Some(n)`, succeeds only if the current seq_no
    ///   equals `n`.
    ///
    /// On success, updates the entry and returns the new seq_no.
    /// On failure, returns [`StorageError::VersionConflict`].
    pub fn check_and_set(
        &self,
        doc_id: impl Into<String>,
        expected_seq_no: Option<SeqNo>,
        new_seq_no: SeqNo,
        new_segment_id: impl Into<Arc<str>>,
        deleted: bool,
    ) -> Result<SeqNo> {
        let doc_id = doc_id.into();
        let new_segment_id = new_segment_id.into();

        use dashmap::mapref::entry::Entry;

        match self.inner.entry(MapKey::new(&doc_id)) {
            Entry::Occupied(mut occ) => {
                let current = occ.get().seq_no;
                match expected_seq_no {
                    None => {
                        // create-only: document must not already exist (or must be deleted)
                        if !occ.get().deleted() {
                            return Err(StorageError::VersionConflict {
                                doc_id,
                                expected: 0,
                                actual: current,
                            });
                        }
                    }
                    Some(expected) => {
                        if current != expected {
                            return Err(StorageError::VersionConflict {
                                doc_id,
                                expected,
                                actual: current,
                            });
                        }
                    }
                }
                let was_live = !occ.get().deleted();
                // A CAS write is a genuine new logical write.
                let version = occ.get().version() + 1;
                occ.insert(Slot::new(new_seq_no, new_segment_id, deleted, version));
                self.ghost_events.fetch_add(1, Ordering::Relaxed);
                self.live_delta(was_live, !deleted);
                Ok(new_seq_no)
            }
            Entry::Vacant(vac) => {
                if let Some(expected) = expected_seq_no {
                    // Caller expected a specific version but the doc doesn't exist
                    return Err(StorageError::VersionConflict {
                        doc_id,
                        expected,
                        actual: 0,
                    });
                }
                self.key_added(vac.key());
                vac.insert(Slot::new(new_seq_no, new_segment_id, deleted, 1));
                if deleted {
                    self.ghost_events.fetch_add(1, Ordering::Relaxed);
                }
                self.live_delta(false, !deleted);
                Ok(new_seq_no)
            }
        }
    }

    /// Mark a document as deleted (tombstone) at `seq_no`.
    ///
    /// Returns `Ok(true)` if the document existed and was marked deleted.
    /// Returns `Ok(false)` if the document was not found (idempotent delete).
    pub fn delete(
        &self,
        doc_id: &str,
        seq_no: SeqNo,
        segment_id: impl Into<Arc<str>>,
    ) -> Result<bool> {
        match self.inner.get_mut(&MapKey::new(doc_id)) {
            Some(mut entry) => {
                if entry.deleted() {
                    return Ok(false); // already deleted
                }
                // ES bumps `_version` on delete: the tombstone carries the
                // bumped value (surfaced in the delete response, and a
                // subsequent re-index continues from it).
                let version = entry.version() + 1;
                *entry = Slot::new(seq_no, segment_id.into(), true, version);
                self.ghost_events.fetch_add(1, Ordering::Relaxed);
                self.live_delta(true, false);
                Ok(true)
            }
            None => Ok(false),
        }
    }

    /// Repoint a document's entry at a new segment WITHOUT counting a new
    /// logical write.  Used by the flush path: a drained memtable doc keeps
    /// its seq_no and `_version`, only its physical home changes.
    ///
    /// - Entry present with the SAME `seq_no` → swap `segment_id`, keep
    ///   `version` / `deleted` / counters untouched.
    /// - Entry present with a DIFFERENT `seq_no` → no-op.  Covers both a
    ///   superseded duplicate in the drained batch (an older copy of a doc
    ///   that was overwritten in the same memtable generation) and a doc
    ///   that was updated or deleted after the drain — clobbering either
    ///   would resurrect a stale version (the old unconditional `set` here
    ///   transiently did exactly that).
    /// - No entry → record it (recovery parity with the old `set` call).
    pub fn repoint(&self, doc_id: &str, seq_no: SeqNo, segment_id: impl Into<Arc<str>>) {
        use dashmap::mapref::entry::Entry;
        match self.inner.entry(MapKey::new(doc_id)) {
            Entry::Occupied(mut occ) => {
                if occ.get().seq_no == seq_no {
                    occ.get_mut().segment_id = segment_id.into();
                }
            }
            Entry::Vacant(vac) => {
                self.key_added(vac.key());
                vac.insert(Slot::new(seq_no, segment_id.into(), false, 1));
                self.live_delta(false, true);
            }
        }
    }

    /// Roll back a physical repoint iff the entry still names the failed
    /// segment and sequence. Concurrent newer writes are therefore never
    /// overwritten. `prior=None` removes an entry created solely by the
    /// failed publication; `Some` restores the exact logical version.
    pub(crate) fn rollback_repoint(
        &self,
        doc_id: &str,
        seq_no: SeqNo,
        failed_segment: &str,
        prior: Option<VersionEntry>,
    ) {
        use dashmap::mapref::entry::Entry;
        let Entry::Occupied(mut occupied) = self.inner.entry(MapKey::new(doc_id)) else {
            return;
        };
        if occupied.get().seq_no != seq_no || occupied.get().segment_id.as_ref() != failed_segment {
            return;
        }
        let old_live = !occupied.get().deleted();
        match prior {
            Some(prior) => {
                let new_live = !prior.deleted;
                occupied.insert(Slot::from(prior));
                self.live_delta(old_live, new_live);
            }
            None => {
                let (key, _) = occupied.remove_entry();
                self.key_removed(&key);
                self.live_delta(old_live, false);
            }
        }
    }

    /// Bump the `_version` of an EXISTING tombstone and return the bumped
    /// value.  ES semantics for `DELETE` of an already-deleted document:
    /// the delete reports `result: not_found` (404) but still increments
    /// the document's version, and a later re-index continues from it.
    /// Returns `None` when the doc is unknown or live.
    pub fn bump_tombstone_version(&self, doc_id: &str) -> Option<u64> {
        let mut entry = self.inner.get_mut(&MapKey::new(doc_id))?;
        if !entry.deleted() {
            return None;
        }
        let bumped = entry.version() + 1;
        entry.set_version(bumped);
        Some(bumped)
    }

    /// Remove all entries whose `segment_id` is in `stale_segment_ids`.
    ///
    /// Called after a merge to clean up references to segments that no longer
    /// exist.  The merged segment's entries are already updated before this
    /// call, so this only removes genuinely stale entries (e.g. for documents
    /// that were deleted and tombstone-purged during the merge).
    pub fn remove_segment(&self, stale_segment_ids: &[SegmentId]) {
        let stale: std::collections::HashSet<&str> =
            stale_segment_ids.iter().map(String::as_str).collect();

        let mut removed_live: i64 = 0;
        let mut removed_key_bytes = 0usize;
        self.inner.retain(|k, v| {
            let keep = !stale.contains(&*v.segment_id);
            if !keep {
                removed_key_bytes += k.heap_len();
                if !v.deleted() {
                    removed_live += 1;
                }
            }
            keep
        });
        self.key_heap
            .fetch_sub(removed_key_bytes, Ordering::Relaxed);
        if removed_live != 0 {
            self.live.fetch_sub(removed_live, Ordering::Relaxed);
        }
        debug!(
            stale_count = stale.len(),
            "version_map: cleaned up stale segments"
        );
    }

    /// Bulk-load entries from a segment during recovery / replay.
    pub fn bulk_load<I>(&self, entries: I)
    where
        I: IntoIterator<Item = (String, SeqNo, SegmentId, bool)>,
    {
        for (doc_id, seq_no, segment_id, deleted) in entries {
            // Only update if the incoming entry is newer
            let (should_insert, version) = match self.inner.get(&MapKey::new(&doc_id)) {
                Some(existing) => (seq_no > existing.seq_no, existing.version() + 1),
                None => (true, 1),
            };
            if should_insert {
                let key = MapKey::new(&doc_id);
                let key_len = key.heap_len();
                let old = self.inner.insert(
                    key,
                    Slot::new(seq_no, Arc::from(segment_id), deleted, version),
                );
                if old.is_none() {
                    self.key_heap.fetch_add(key_len, Ordering::Relaxed);
                }
                self.live_delta(old.is_some_and(|e| !e.deleted()), !deleted);
            }
        }
    }

    /// Return the total number of tracked documents (including deleted ones).
    pub fn len(&self) -> usize {
        self.inner.len()
    }

    /// Return `true` if the map is empty.
    pub fn is_empty(&self) -> bool {
        self.inner.is_empty()
    }

    /// Live document ids, sorted by id.
    ///
    /// Tombstones are left out. The order is the id string, not sequence
    /// number, so two copies of the same primary agree on the list.
    pub fn live_ids(&self) -> Vec<String> {
        let mut ids: Vec<String> = self
            .inner
            .iter()
            .filter(|entry| !entry.value().deleted())
            .map(|entry| entry.key().to_id())
            .collect();
        ids.sort();
        ids
    }

    /// Return the count of live (non-deleted) documents.
    ///
    /// O(1) — reads the maintained counter instead of iterating the map
    /// (which cost ~80 ms per call at 1 M entries and was invoked on every
    /// search request via the `deletes_present` gate).
    pub fn live_count(&self) -> usize {
        self.live.load(Ordering::Relaxed).max(0) as usize
    }

    /// Number of overwrite/delete events ever seen (see `ghost_events`
    /// field docs).  Zero ⇔ append-only history ⇔ physical postings and
    /// stored copies are 1:1 with live docs (barring storage-level bugs,
    /// which corrupt the brute counting paths identically).
    pub fn ghost_events(&self) -> u64 {
        self.ghost_events.load(Ordering::Relaxed)
    }

    /// Conservatively mark the index as containing ghosts.  Called once at
    /// open time when the at-rest arithmetic (`live < physical`) indicates
    /// superseded copies from a pre-restart history the WAL replay cannot
    /// see.
    pub fn force_ghost_event(&self) {
        self.ghost_events.fetch_add(1, Ordering::Relaxed);
    }
}

impl Default for VersionMap {
    fn default() -> Self {
        Self::new()
    }
}

// ── Tests ─────────────────────────────────────────────────────────────────────

#[cfg(test)]
mod tests {
    use super::*;

    /// #2427: the version map was ~0.5 GB of untracked heap on the 1 GB
    /// gate's search node (hash tables 406 MB + keys 95 MB in the heap
    /// profile). Each bucket must stay compact (Box<str> key: 56 B, not
    /// 64 B with a String), and `heap_bytes` must cover tables + keys and
    /// fall back to zero key bytes when every entry is removed.
    #[test]
    fn version_map_bucket_is_compact_and_heap_is_accounted_2427() {
        let bucket = std::mem::size_of::<(MapKey, Slot)>();
        assert!(
            bucket <= 56,
            "version map bucket is {bucket} B, want <= 56 B"
        );

        let vm = VersionMap::new();
        let n = 10_000usize;
        for i in 0..n {
            vm.set(format!("doc-{i:08}"), i as u64 + 1, "seg-a", false);
        }
        // 12-byte ids are stored inline in the key: no key heap.
        let keys = 0;
        let heap = vm.heap_bytes();
        assert!(heap >= n * bucket + keys, "heap_bytes {heap} below floor");
        assert!(
            heap <= n * 4 * (bucket + 1) + keys,
            "heap_bytes {heap} above bound"
        );

        vm.remove_segment(&["seg-a".to_string()]);
        assert_eq!(vm.len(), 0);
        assert_eq!(vm.key_heap.load(Ordering::Relaxed), 0);
    }

    /// #2427: the common id shapes must not cost a separate heap
    /// allocation per entry, and the tombstone flag must not pad the entry
    /// out by a word. On the cap-2048 autoindex run the map was ~190 MB of
    /// heap, every id a 32-char hex string that a `Box<str>` key stored in
    /// a 48 B allocation beside the 56 B bucket. Packed ids must round-trip
    /// exactly, and near misses must stay distinct strings.
    #[test]
    fn version_map_common_ids_need_no_key_heap_2427() {
        assert!(std::mem::size_of::<MapKey>() <= 24);
        assert!(std::mem::size_of::<Slot>() <= 32);
        assert!(std::mem::size_of::<(MapKey, Slot)>() <= 56);

        let vm = VersionMap::new();
        let hex = |i: u64| format!("{:016x}{:016x}", i.wrapping_mul(0x9E37_79B9_7F4A_7C15), i);
        for i in 0..1_000u64 {
            vm.set(hex(i), i + 1, "seg-a", i % 3 == 0);
            // 20 bytes, the length of an ES auto-generated id.
            vm.set(format!("auto-id-{i:012}"), i + 1, "seg-a", false);
        }
        let uuid = "1b4e28ba-2fa1-11d2-883f-0016d3cca427";
        vm.set(uuid, 9_000, "seg-a", false);
        assert_eq!(vm.key_heap.load(Ordering::Relaxed), 0);
        assert!(matches!(MapKey::new(&hex(7)), MapKey::Hex32(_)));
        assert!(matches!(MapKey::new(uuid), MapKey::Uuid(_)));

        // Near misses are plain strings and never collide with packed ids.
        let upper = hex(1).to_uppercase();
        let dashed_wrong = "1b4e28ba2-fa1-11d2-883f-0016d3cca427";
        for id in [upper.as_str(), &hex(1)[..31], dashed_wrong] {
            assert!(matches!(MapKey::new(id), MapKey::Str(_)), "{id}");
            assert!(vm.get(id).is_none(), "{id} must not alias a packed id");
        }
        vm.set(upper.as_str(), 9_001, "seg-b", false);
        assert_eq!(vm.key_heap.load(Ordering::Relaxed), 32);

        // Exact round-trip through the packed forms.
        let mut want: Vec<String> = (0..1_000u64)
            .filter(|i| i % 3 != 0)
            .map(hex)
            .chain((0..1_000u64).map(|i| format!("auto-id-{i:012}")))
            .chain([uuid.to_string(), upper.clone()])
            .collect();
        want.sort();
        assert_eq!(vm.live_ids(), want);

        let tomb_id = hex(3);
        let tomb = vm.get(&tomb_id).unwrap();
        assert!(tomb.deleted);
        assert_eq!(tomb.version, 1);
        assert_eq!(vm.bump_tombstone_version(&tomb_id), Some(2));
        let tomb = vm.get(&tomb_id).unwrap();
        assert!(
            tomb.deleted,
            "bumping the version must keep the tombstone flag"
        );
        assert_eq!(tomb.version, 2);
        let live = vm.get(&hex(1)).unwrap();
        assert!(!live.deleted);
        assert_eq!((live.seq_no, live.segment_id.as_ref()), (2, "seg-a"));

        vm.remove_segment(&["seg-b".to_string()]);
        assert_eq!(vm.key_heap.load(Ordering::Relaxed), 0);
    }

    /// #2427: key-heap accounting balances across conflict and rollback
    /// paths that create no entry or remove the one they created.
    #[test]
    fn version_map_key_heap_balances_on_conflict_and_rollback_2427() {
        let vm = Arc::new(VersionMap::new());
        assert!(vm
            .check_and_set("missing", Some(7), 8, "seg", false)
            .is_err());
        assert_eq!(vm.len(), 0);
        assert_eq!(vm.key_heap.load(Ordering::Relaxed), 0);
        // Ids longer than the 24-byte inline CompactString and not packable
        // as hex or UUID, so they hold key heap and exercise its accounting.
        // A short id is stored inline and adds nothing to the key heap.
        const FRESH: &str = "fresh-doc-with-a-heap-allocated-key";
        const KEPT: &str = "kept-doc-with-a-heap-allocated-key";
        let empty = vm.heap_bytes();
        {
            let mut tx = VersionRepointTransaction::with_capacity(Arc::clone(&vm), 1);
            tx.repoint_if_latest(FRESH, 3, Arc::from("seg-m"), false);
            assert_eq!(vm.len(), 1);
            assert_eq!(vm.key_heap.load(Ordering::Relaxed), FRESH.len());
            assert!(vm.heap_bytes() >= empty + FRESH.len());
        }
        assert_eq!(vm.len(), 0);
        assert_eq!(vm.key_heap.load(Ordering::Relaxed), 0);
        vm.set(KEPT, 1, "seg", false);
        vm.set(KEPT, 2, "seg", false);
        assert_eq!(vm.key_heap.load(Ordering::Relaxed), KEPT.len());
        assert!(vm.heap_bytes() >= KEPT.len());
        vm.remove_segment(&["seg".to_string()]);
        assert_eq!(vm.len(), 0);
        assert_eq!(vm.key_heap.load(Ordering::Relaxed), 0);
    }

    #[test]
    fn live_ids_skips_tombstones_and_is_sorted() {
        let vm = VersionMap::new();
        vm.set("b", 1, "s", false);
        vm.set("a", 2, "s", false);
        vm.set("c", 3, "s", false);
        assert!(vm.delete("b", 4, "s").unwrap());
        assert_eq!(vm.live_ids(), vec!["a".to_string(), "c".to_string()]);
    }

    #[test]
    fn basic_set_and_get() {
        let vm = VersionMap::new();
        vm.set("doc-1", 10, "seg-a", false);
        let e = vm.get("doc-1").unwrap();
        assert_eq!(e.seq_no, 10);
        assert_eq!(&*e.segment_id, "seg-a");
        assert!(!e.deleted);
        assert_eq!(e.version, 1);
    }

    #[test]
    fn version_bumps_on_newer_seq_only() {
        let vm = VersionMap::new();
        assert_eq!(vm.set("d", 1, "__memtable__", false), 1);
        // Overwrite with a newer seq bumps.
        assert_eq!(vm.set("d", 5, "__memtable__", false), 2);
        // Same-seq repoint (flush) keeps the version.
        assert_eq!(vm.set("d", 5, "seg-a", false), 2);
        // Stale replay of an older copy keeps the version.
        assert_eq!(vm.set("d", 1, "seg-a", false), 2);
    }

    #[test]
    fn delete_bumps_version_and_reindex_continues() {
        let vm = VersionMap::new();
        vm.set("d", 1, "s", false); // v1
        vm.set("d", 2, "s", false); // v2
        vm.delete("d", 3, "s").unwrap(); // tombstone carries v3
        assert_eq!(vm.get("d").unwrap().version, 3);
        assert_eq!(vm.set("d", 4, "s", false), 4); // recreate → v4
    }

    #[test]
    fn bump_tombstone_version_only_on_tombstones() {
        let vm = VersionMap::new();
        assert_eq!(vm.bump_tombstone_version("ghost"), None);
        vm.set("d", 1, "s", false);
        assert_eq!(vm.bump_tombstone_version("d"), None); // live
        vm.delete("d", 2, "s").unwrap(); // v2 tombstone
        assert_eq!(vm.bump_tombstone_version("d"), Some(3));
        assert_eq!(vm.bump_tombstone_version("d"), Some(4));
        // A recreate continues from the bumped tombstone version.
        assert_eq!(vm.set("d", 3, "s", false), 5);
    }

    #[test]
    fn repoint_swaps_segment_without_bumping() {
        let vm = VersionMap::new();
        vm.set("d", 1, "__memtable__", false);
        vm.set("d", 2, "__memtable__", false); // v2 (overwrite in memtable)
        let ghosts_before = vm.ghost_events();

        // Flush replays BOTH drained copies; only the live seq repoints.
        vm.repoint("d", 1, "seg-a"); // superseded duplicate → no-op
        let e = vm.get("d").unwrap();
        assert_eq!(
            (&*e.segment_id, e.seq_no, e.version),
            ("__memtable__", 2, 2)
        );
        vm.repoint("d", 2, "seg-a");
        let e = vm.get("d").unwrap();
        assert_eq!((&*e.segment_id, e.seq_no, e.version), ("seg-a", 2, 2));
        assert_eq!(vm.ghost_events(), ghosts_before);

        // A doc deleted after the drain is NOT resurrected by the repoint.
        vm.delete("d", 3, "__memtable__").unwrap();
        vm.repoint("d", 2, "seg-b");
        assert!(vm.get("d").unwrap().deleted);
        assert_eq!(vm.get("d").unwrap().seq_no, 3);

        // Unknown doc → recorded live (recovery parity with the old set()).
        vm.repoint("x", 7, "seg-a");
        let e = vm.get("x").unwrap();
        assert_eq!((e.seq_no, e.version, e.deleted), (7, 1, false));
        assert_eq!(vm.live_count(), 1); // "x" live, "d" tombstoned
    }

    #[test]
    fn merge_repoint_transaction_rolls_back_exact_previous_entries() {
        let vm = Arc::new(VersionMap::new());
        vm.set("live", 7, "input-a", false);
        vm.set("tomb", 8, "input-b", true);
        let live_before = vm.live_count();
        {
            let mut transaction = VersionRepointTransaction::with_capacity(Arc::clone(&vm), 3);
            transaction.repoint_if_latest("live", 7, Arc::from("output"), false);
            transaction.repoint_if_latest("tomb", 8, Arc::from("output"), true);
            transaction.repoint_if_latest("new-tomb", 9, Arc::from("output"), true);
            assert_eq!(&*vm.get("live").unwrap().segment_id, "output");
            assert_eq!(&*vm.get("tomb").unwrap().segment_id, "output");
        }
        assert_eq!(&*vm.get("live").unwrap().segment_id, "input-a");
        assert_eq!(&*vm.get("tomb").unwrap().segment_id, "input-b");
        assert!(vm.get("new-tomb").is_none());
        assert_eq!(vm.live_count(), live_before);
    }

    #[test]
    fn merge_repoint_rollback_preserves_concurrent_update_and_delete() {
        let vm = Arc::new(VersionMap::new());
        vm.set("updated", 1, "input", false);
        vm.set("deleted", 2, "input", false);
        {
            let mut transaction = VersionRepointTransaction::with_capacity(Arc::clone(&vm), 2);
            transaction.repoint_if_latest("updated", 1, Arc::from("output"), false);
            transaction.repoint_if_latest("deleted", 2, Arc::from("output"), false);
            vm.set("updated", 10, IN_MEMORY_SEGMENT_ID, false);
            vm.delete("deleted", 11, IN_MEMORY_SEGMENT_ID).unwrap();
        }
        let updated = vm.get("updated").unwrap();
        assert_eq!(
            (updated.seq_no, &*updated.segment_id, updated.deleted),
            (10, IN_MEMORY_SEGMENT_ID, false)
        );
        let deleted = vm.get("deleted").unwrap();
        assert_eq!(
            (deleted.seq_no, &*deleted.segment_id, deleted.deleted),
            (11, IN_MEMORY_SEGMENT_ID, true)
        );
    }

    #[test]
    fn merge_repoint_transaction_is_panic_safe_and_commit_is_final() {
        let vm = Arc::new(VersionMap::new());
        vm.set("doc", 1, "input", false);
        let panic_result = std::panic::catch_unwind(std::panic::AssertUnwindSafe({
            let vm = Arc::clone(&vm);
            move || {
                let mut transaction = VersionRepointTransaction::with_capacity(Arc::clone(&vm), 1);
                transaction.repoint_if_latest("doc", 1, Arc::from("failed-output"), false);
                panic!("injected merge worker panic after repoint");
            }
        }));
        assert!(panic_result.is_err());
        assert_eq!(&*vm.get("doc").unwrap().segment_id, "input");

        let mut transaction = VersionRepointTransaction::with_capacity(Arc::clone(&vm), 1);
        transaction.repoint_if_latest("doc", 1, Arc::from("committed-output"), false);
        transaction.commit();
        assert_eq!(&*vm.get("doc").unwrap().segment_id, "committed-output");
    }

    #[test]
    fn check_and_set_success() {
        let vm = VersionMap::new();
        vm.set("doc-1", 5, "seg-a", false);
        let new_seq = vm
            .check_and_set("doc-1", Some(5), 10, "seg-b", false)
            .unwrap();
        assert_eq!(new_seq, 10);
        assert_eq!(vm.get("doc-1").unwrap().seq_no, 10);
    }

    #[test]
    fn check_and_set_conflict() {
        let vm = VersionMap::new();
        vm.set("doc-1", 5, "seg-a", false);
        let result = vm.check_and_set("doc-1", Some(3), 10, "seg-b", false);
        assert!(matches!(
            result,
            Err(StorageError::VersionConflict {
                actual: 5,
                expected: 3,
                ..
            })
        ));
    }

    #[test]
    fn create_only_rejects_existing() {
        let vm = VersionMap::new();
        vm.set("doc-1", 1, "seg-a", false);
        let result = vm.check_and_set("doc-1", None, 2, "seg-b", false);
        assert!(matches!(result, Err(StorageError::VersionConflict { .. })));
    }

    #[test]
    fn create_only_on_deleted_succeeds() {
        let vm = VersionMap::new();
        vm.set("doc-1", 1, "seg-a", true); // deleted
        let result = vm.check_and_set("doc-1", None, 2, "seg-b", false);
        assert!(result.is_ok());
    }

    #[test]
    fn delete_marks_tombstone() {
        let vm = VersionMap::new();
        vm.set("doc-1", 1, "seg-a", false);
        let found = vm.delete("doc-1", 2, "seg-a").unwrap();
        assert!(found);
        assert!(vm.get("doc-1").unwrap().deleted);
    }

    #[test]
    fn delete_nonexistent_is_ok() {
        let vm = VersionMap::new();
        let found = vm.delete("ghost", 1, "seg-a").unwrap();
        assert!(!found);
    }

    #[test]
    fn remove_stale_segment() {
        let vm = VersionMap::new();
        vm.set("doc-1", 1, "seg-a", false);
        vm.set("doc-2", 2, "seg-b", false);
        vm.set("doc-3", 3, "seg-a", false);

        vm.remove_segment(&["seg-a".to_string()]);
        assert!(vm.get("doc-1").is_none());
        assert!(vm.get("doc-2").is_some());
        assert!(vm.get("doc-3").is_none());
    }

    #[test]
    fn live_count_excludes_deleted() {
        let vm = VersionMap::new();
        vm.set("a", 1, "s", false);
        vm.set("b", 2, "s", true);
        vm.set("c", 3, "s", false);
        assert_eq!(vm.live_count(), 2);
        assert_eq!(vm.len(), 3);
    }

    #[test]
    fn bulk_load_uses_newer_seq_no() {
        let vm = VersionMap::new();
        vm.set("doc-1", 5, "seg-a", false);
        vm.bulk_load(vec![
            ("doc-1".into(), 3, "seg-b".into(), false), // older — ignored
            ("doc-2".into(), 7, "seg-c".into(), false), // new
        ]);
        assert_eq!(vm.get("doc-1").unwrap().seq_no, 5); // unchanged
        assert_eq!(vm.get("doc-2").unwrap().seq_no, 7);
    }

    #[test]
    fn concurrent_set() {
        use std::sync::Arc;
        let vm = Arc::new(VersionMap::new());
        let mut handles = Vec::new();
        for i in 0..8u64 {
            let vm = Arc::clone(&vm);
            handles.push(std::thread::spawn(move || {
                vm.set(format!("doc-{i}"), i, "seg-x", false);
            }));
        }
        for h in handles {
            h.join().unwrap();
        }
        assert_eq!(vm.len(), 8);
    }
}