Soft Delete & Compaction
Relevant source files
The following files were used as context for generating this wiki page:
EdgeVec implements a "Soft Delete" mechanism to manage vector removal without requiring immediate, expensive re-indexing. This approach uses a tombstone-based system where vectors are marked as logically deleted, effectively hiding them from search results while remaining in the physical storage until a compaction event occurs. This ensures O(1) deletion performance, which is critical for high-throughput edge environments.
Compaction is the process of physically reclaiming space by removing these tombstones and reorganizing the index. The system monitors the "tombstone ratio"—the proportion of deleted vectors relative to the total—and recommends compaction once a specific threshold is met. This dual strategy balances immediate write performance with long-term memory efficiency and search quality.
Sources: wasm/examples/soft_delete.js:37-41, GATE_1_COMPLETE.md:129-131
Soft Delete Architecture
The soft delete system operates by utilizing a tombstone bitmap within the vector storage layer. When a vector is deleted, its corresponding bit in the bitmap is set, and it is immediately excluded from search results and metadata queries.
Components and Invariants
- Tombstone Bitmap: A
BitVecwhere each bit represents the deletion status of a vector ID. - Metadata Cleanup: As of RFC-002, a soft delete operation also triggers the removal of associated metadata for the given vector ID to ensure data consistency and free up metadata storage.
- Invariants: The system maintains a constant relationship where
tombstones.len() == capacity. Iftombstones[i] == true, the data at indexiis considered logically deleted.
The diagram above illustrates the logical flow of a soft delete operation, showing the simultaneous update of the tombstone bit and metadata removal.
Sources: GATE_1_COMPLETE.md:129-131, tests/metadata_delete.rs:48-62, CONTRIBUTING.md:214-220
Compaction Logic
Compaction is a maintenance operation that rebuilds the index and storage to reclaim memory used by tombstones. It is typically triggered based on the tombstoneRatio.
Compaction Thresholds
The default threshold for recommending compaction is 0.3 (30%). This means if 30% or more of the index consists of tombstones, the needsCompaction() check will return true. The threshold is configurable between 0.01 and 0.99.
| Parameter | Type | Default | Constraints | Description |
|---|---|---|---|---|
compactionThreshold | float | 0.3 | 0.01 - 0.99 | Ratio of deleted/total vectors to trigger warning. |
tombstonesRemoved | integer | - | - | Number of vectors physically removed during last compact. |
newSize | integer | - | - | Total vector count after space reclamation. |
Sources: wasm/tests/compaction.test.ts:47-65, wasm/examples/soft_delete.js:352-368
Compaction Flow
When compact() is called, the system creates a new index and storage instance, migrating only "live" vectors.
Implementation Details
Metadata Integration
Integration tests confirm that re-inserting a vector after a soft delete results in fresh metadata, ensuring that old tombstones do not leak data into new insertions. The soft_delete_batch API similarly handles metadata removal for multiple IDs simultaneously, ensuring idempotency where double-deletions do not cause crashes.
Sources: tests/metadata_delete.rs:138-165, tests/metadata_delete.rs:198-215
API Methods
| Method | Environment | Description |
|---|---|---|
softDelete(id) | WASM/Rust | Marks vector as deleted and removes metadata. |
softDeleteBatch(ids) | WASM/Rust | Deletes multiple vectors efficiently. |
needsCompaction() | WASM/Rust | Returns true if tombstoneRatio > threshold. |
compact() | WASM/Rust | Reclaims memory and returns CompactionResult. |
tombstoneRatio() | WASM/Rust | Returns deletedCount / totalCount. |
Sources: wasm/examples/soft_delete.js:324-345, wasm/tests/compaction.test.ts:12-30
// Example of compaction check in Rust
if index.needs_compaction() {
if let Some(warning) = index.compaction_warning() {
println!("Warning: {}", warning);
}
let (new_index, new_storage, result) = index.compact(&storage).expect("Compaction failed");
index = new_index;
storage = new_storage;
}
Sources: examples/filter_persistence.rs:136-148
Summary
The Soft Delete and Compaction system in EdgeVec provides a robust lifecycle for vector data. By separating the logical deletion (via tombstones and metadata removal) from physical memory reclamation (compaction), the project achieves high performance for volatile datasets while maintaining the strict memory budgets required for browser-based and edge deployments. The system ensures that search quality and recall remain preserved even after significant index reorganization.
Sources: wasm/tests/compaction.test.ts:161-180, GATE_1_COMPLETE.md:89-95