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.
Rust agent-memoryai-agentsbm25claude-codeclicode-searchcursordatabaseelasticsearchfull-text-searchhybrid-searchjsonllocal-firstmcpmcp-servermodel-context-protocolragrustsearch-enginevector-search
//! 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);
}
}