HNSW partitioning¶

Architecture

A single HNSW index over all time forces post-filtering that destroys recall at high temporal selectivity: "valid in May 2025" against a 3-year index returns k neighbors mostly outside May. Telha instead partitions HNSW by time bucket, keeps every partition rebuildable from the canonical vectors CF, and merges per-bucket results at query time.

Overview & purpose¶

The problem is entirely about the shape of temporal selectivity. Per the spec's Alternatives Considered (§9):

The design that survives: partition key = (tenant, org, model, time_bucket(validTimeStart)). Every partition is rebuildable from the CF (F4), so a missing file, a corrupt file, or a bucket-size reconfiguration is never an error, only a rebuild trigger.

Design¶

flowchart TB
    WRITE["vector write (VectorOps)"] --> ROUTE["PartitionManager.insert()<br/>route(bucket)"]
    ROUTE --> OPEN["open partition<br/>(in-memory usearch, dirty)"]

    QUERY["query(window, k)"] --> BUCKETS["overlapping buckets lo..=hi"]
    BUCKETS --> PERBUCKET["per-bucket search(k)<br/>full k per bucket"]
    PERBUCKET --> MERGE["merge by sim, dedup per node<br/>(keep max sim)"]
    MERGE --> VALIDATE["validate-via-primary<br/>get_as_of(vT, tx_t)"]
    VALIDATE --> TOPK["top-k out"]

    TICKER["seal ticker"] --> DUE["open partitions past grace"]
    DUE --> SEAL["serialize + manifest<br/>demote to sealed"]

Lifecycle: open, sealed-loaded, sealed-on-disk¶

A partition is in exactly one of three states at any moment:

• Open: in-memory usearch index, accepting inserts, dirty once it has unsaved content. Never evicted (it holds state no save-file has yet).
• Sealed-loaded: read-only, resident in memory, evictable under LRU.
• Sealed-on-disk: no resident state; loads lazily on first query that touches its bucket.

A write into a sealed-on-disk or sealed-loaded partition reopens it: the sealed file loads (or the resident copy is reused), the new vector is appended, and open/dirty both flip true. The next seal sweep re-seals it. There is no separate "rebuild the old file" step; the re-seal is the rebuild (spec §14 v0.2 note 4).

Why persistence lives beside the save-file, not in the schema CF¶

The spec's own §5 originally sketched the manifest as a schema-CF row. As built, it is not. Every partition writes three files to {data_dir}/vectors/{tenant}/{org}-{model_id:016x}/{bucket}:

Everything under {data_dir}/vectors is wholly derived and disposable: a corrupt manifest simply triggers rebuild like any other corruption, exactly the same as a corrupt index file (spec §14 v0.2 note 2).

Data model¶

Bucket id: a pure function¶

pub fn bucket_of(&self, valid_time_start: Ts) -> u64 {
    valid_time_start / self.config.bucket.as_us()
}

Bucket lengths are fixed, not calendar-aware, so this division stays pure and reconfiguration deterministically remaps every vector:

"Monthly" means 30-day fixed windows, not calendar months (spec §14 v0.2 note 1). Because bucket_of is pure, a bucket-size config change plus a background rebuild is the entire migration path: every vector deterministically lands in its new bucket, and rebuild-from-CF is authoritative throughout.

PartitionKey and the manifest struct¶

struct PartitionKey { tenant: Uuid, org: Uuid, model: EmbeddingModelId, bucket: u64 }

struct Manifest {
    v: u32,
    count: usize,
    dims: u32,
    hnsw_m: usize,
    hnsw_ef_construction: usize,
    file_hash: String,   // blake3 of {bucket}.usearch
    ids_hash: String,    // blake3 of {bucket}.ids
    built_at_us: Ts,
}

usearch is configured with MetricKind::IP (inner product): because vectors are L2-normalized at write time (per the model registry's normalize flag), inner product is cosine similarity, so search never needs a separate normalization step at query time beyond normalizing the query vector itself.

SearchHit¶

pub struct SearchHit {
    pub node_id: Uuid,
    pub valid_time_start: Ts,
    pub sim: f32,   // 1 - IP distance, clamped to [-1, 1]
}

Algorithms & invariants¶

Insert: route, reopen-on-write, reserve growth¶

PartitionManager::insert normalizes the vector per the registry flag (producing byte-identical content to what VectorOps::write_embedding already wrote to the CF), computes the target bucket, and either appends to a resident slot or loads-then-reopens a sealed one:

slot.open = true;   // reopen-on-write for sealed residents
slot.dirty = true;
if slot.index.capacity() <= slot.ids.len() {
    slot.index.reserve((slot.ids.len() * 2).max(1024))?;
}
slot.index.add(slot.ids.len() as u64, &vector)?;
slot.ids.push((node_id, valid_time_start));

usearch keys are dense u64 indices assigned by insertion order (slot.ids.len() at insert time); the .ids sidecar is what maps that dense key back to (Uuid, validStart).

Seal: grace period, not immediate¶

s.open && s.dirty && ((k.bucket + 1) * bucket_len).saturating_add(grace) < now_us

A partition seals only once its bucket's end plus seal_grace_secs has passed and it has unsaved content (dirty). The grace period (default 48h) exists because late-arriving backfill writes with past validTime are common in ingestion; sealing too eagerly would mean constant reopen/reseal churn. Shutdown force-seals every open partition regardless of grace (seal_all, wired to the seal ticker's shutdown hook).

Load: hash verification, corruption triggers rebuild, never an error¶

flowchart TD
    LOAD["load_from_disk(key)"] --> EXIST{"all 3 files exist?"}
    EXIST -->|none| NONE["Ok(None): no partition yet"]
    EXIST -->|partial| REBUILD1["rebuild_one(): crash mid-seal"]
    EXIST -->|all 3| MANIFEST{"manifest parses?"}
    MANIFEST -->|no| REBUILD2["rebuild_one()"]
    MANIFEST -->|yes| HASH{"blake3(index) == file_hash<br/>AND blake3(ids) == ids_hash?"}
    HASH -->|no| REBUILD3["rebuild_one()"]
    HASH -->|yes| USEARCH{"usearch .load() succeeds?"}
    USEARCH -->|no| REBUILD4["rebuild_one()"]
    USEARCH -->|yes| LOADED["Loaded (sealed, not dirty)"]

Every failure path converges on rebuild_one, which re-scans the vectors CF for (model, bucket) and rebuilds from the authoritative source. Nothing here ever surfaces a hard error to the caller for a corrupt save-file; the whole point of deriving from the CF is that save-files are disposable.

Rebuild: newest tx per (node, validStart)¶

rebuild_one scans the tenant's full vectors CF prefix and keeps only rows whose model_id and bucket_of(valid_time_start) match the target partition. Because CF keys sort [node][model][inv valid][inv tx], the first row seen per (node, validStart) pair carries the newest transaction time; subsequent rows for the same pair are older versions and are skipped:

let slot_id = (decoded.node_logical_id, decoded.valid_time_start);
if last == Some(slot_id) { continue; }
last = Some(slot_id);

Search: per-bucket full k, merge, validate-via-primary¶

pub fn search(&self, scope, model_name, query, window: (Ts, Ts), tx_t, k, ef_search) -> Vec<SearchHit>

1. Bucket range: bucket_lo = bucket_of(window.0), bucket_hi = bucket_of(window.1); every bucket lo..=hi is searched.
2. Per-bucket k is the full k, not k / num_buckets (cheap insurance against skewed windows where one bucket holds most of the relevant mass, spec §6).
3. Merge: hits are deduped per node, keeping the maximum similarity seen across buckets (a node's vector should only ever appear in one bucket, but the dedup is defensive).
4. Validate-via-primary: every surviving hit is checked against the primary CF via get_as_of(scope, node_id, valid_time_start, tx_t), requiring non-tombstone and interval overlap with the query window (v.valid_time.start < hi && v.valid_time.end > lo). This is the same validate-via-primary doctrine the global temporal scan uses: a sealed bucket may contain vectors whose validity was later capped by a correction, and validation makes that harmless without a second index.

Eviction: LRU over sealed-loaded, budget-bounded¶

fn evict_over_budget(&self, state: &mut HashMap<PartitionKey, Loaded>) {
    let budget = (self.config.memory_budget_mb as usize) * 1024 * 1024;
    loop {
        let resident: usize = state.values().filter(|s| !s.open).map(|s| s.bytes).sum();
        if resident <= budget { return; }
        let Some(victim) = state.iter()
            .filter(|(_, s)| !s.open && !s.dirty)
            .min_by_key(|(_, s)| s.last_used)
            .map(|(k, _)| *k) else { return };
        state.remove(&victim);
    }
}

Only sealed, non-dirty partitions are eviction candidates. Open partitions (unsaved inserts) and dirty sealed-loaded partitions (about to be re-sealed) are never evicted; eviction runs after every search and after every admin rebuild. A subsequent query against an evicted bucket simply reloads it from disk, at the cost of one load.

Configuration¶

CLI¶

telha vector rebuild --tenant <uuid> --org <uuid> --model <name> [--bucket <id>] discovers every bucket present in the tenant's vectors CF for that model (or just the named bucket) and rebuilds each one, replacing any resident state and reporting RebuildReport { partitions, vectors }.

As-built notes¶

From spec §14 (Changelog v0.2, PR-039 as built), reconciled against core-engine/src/vector/partitions.rs:

• Fixed bucket lengths, not calendar months: confirmed in BucketLen::as_us(). "Monthly" is 30 days exactly.
• Manifests are JSON files beside the save-files, not schema-CF rows, a deliberate deviation from the spec's original §5 sketch. Confirmed: Manifest serializes via serde_json::to_vec_pretty to {bucket}.manifest.json, never touching the schema CF.
• The .ids sidecar is MessagePack Vec<(Uuid, Ts)>, confirmed via rmp_serde::to_vec / from_slice in seal_one / load_from_disk.
• Reopen-on-write is the rebuild path for late backfill: confirmed, no separate code path exists for "rebuild an old sealed file"; the next seal_due sweep re-seals whatever is open and dirty.
• Startup is fully lazy: there is no boot-time manifest sweep in PartitionManager::new; partitions load on first search or insert that touches their bucket, satisfying the spec's "startup loads manifests" on-demand rather than eagerly.
• Shutdown seals all open partitions: confirmed, spawn_seal_ticker calls manager.seal_all() on its shutdown-signal branch.
• The look-back deviation (vectors starting before the query window are not found) is confirmed in the code as described above and is an explicitly recorded open item in the spec, not a silent bug.
• Not directly verifiable from this code alone: the spec's success metric "recall ≥0.95@10 vs brute force (100k vectors)" is exercised by recall_vs_brute_force_at_10, but the test's default n is 2,000 vectors, scaled down from the spec's 100k; the full-scale run is gated behind TELHA_TEST_RECALL_N for nightly CI and was not run as part of writing this page. The "1000-partition load test" and "24-hour fuzz run" style success metrics are process/CI claims not verifiable from partitions.rs alone.

Related¶

• Vector storage, the canonical vectors CF and model registry this layer derives from.
• Confidence decay, how sim from this search feeds score fusion.
• Global temporal scan, the validate-via-primary doctrine this search reuses.
• Storage engine & key layout, the vectors CF key shape.