Vector Tombstone

A vector tombstone marks a record for deletion without immediately removing its data from disk. This is a logical deletion. The actual physical deletion of the underlying vector data occurs later during a compaction or garbage collection process. This separation is essential for systems using Log-Structured Merge-Trees (LSM-Trees) or write-ahead logs (WAL), where data is immutable after being written.

• Logical Deletion: Fast, in-place update of metadata.
• Physical Deletion: Asynchronous, batched operation that reclaims storage.

A tombstone is a compact metadata record inserted into the index or log. It typically contains:

• A unique identifier (e.g., vector ID) for the deleted record.
• A deletion timestamp.
• A special flag or operation type (e.g., OP_DELETE).

During a query, the database checks for a tombstone before returning a vector. If a tombstone exists for a given ID, the system treats the vector as non-existent, even if its data is still physically present on disk. This structure is minimal to reduce storage overhead.

Compaction is the background process that merges sorted data files (SSTables in an LSM-tree) and permanently removes data marked by tombstones. This process:

• Reads active data files and their associated tombstones.
• Skips writing any data that has a valid, newer tombstone.
• Drops tombstones themselves once they are older than all possible instances of the deleted data. This garbage collection cycle is crucial for controlling storage growth and maintaining query performance by limiting the number of obsolete records the system must scan.

In a distributed vector database, tombstones are replicated across nodes to ensure eventual consistency or strong consistency, depending on the model. When a delete operation is issued:

1. A tombstone is written to the write-ahead log (WAL) on the coordinating node.
2. The tombstone is propagated to replicas.
3. Queries on any node will respect the tombstone once it is applied. This prevents a deleted vector from reappearing after a network partition heals (resurrection) and is a key component of CRDTs (Conflict-Free Replicated Data Types) for managing state in distributed systems.

Tombstones introduce a performance trade-off:

• Write/Delete Performance: Excellent. Inserting a tombstone is as fast as writing a new record.
• Read/Query Performance: Can degrade over time if compaction lags. A query must scan past tombstones in sorted runs, adding overhead. An accumulation of tombstones can lead to read amplification.
• Compaction Overhead: The system consumes CPU and I/O resources during background compaction to merge files and purge tombstones. Proper tuning of compaction strategies (size-tiered, leveled) is required to balance these factors.

Time-To-Live (TTL) policies for vectors are often implemented using tombstones. Instead of a background job scanning for expired records, the system can:

1. Calculate the expiry timestamp when a vector is written.
2. Periodically, or during compaction, generate tombstones for all vectors whose expiry time has passed.
3. The standard tombstone compaction process then physically removes the data. This approach is efficient and integrates seamlessly with the existing storage engine's deletion pathway, making it a common feature in vector databases like Redis (with modules) and Cassandra.

A fundamental durability mechanism where all data modifications, including the insertion of a vector tombstone, are first written to a persistent, append-only log before being applied to the main index. This ensures that logical deletions are recorded and can be recovered even after a system crash, guaranteeing data integrity during the tombstoning process.

• Key Role: Provides the atomicity and durability for tombstone operations.
• Recovery: During database restart, the WAL is replayed to reconstruct the state of the index, including pending deletions.

An adaptation of the Log-Structured Merge-Tree storage architecture optimized for high-throughput vector ingestion. Vector tombstones are a core component of its compaction process.

• Memtable & SSTables: New vectors and tombstones are first written to an in-memory memtable. When full, it is flushed to disk as a sorted string table (SSTable).
• Compaction: Background processes merge SSTables, and during this merge, a tombstone physically removes the corresponding vector from the new SSTable, reclaiming space.
• Advantage: Enables fast writes and efficient background garbage collection of deleted vectors.

Techniques like Product Quantization (PQ) or Scalar Quantization (SQ) that reduce the storage footprint of vectors. Tombstoning interacts with compression at the storage layer.

• Compressed Storage: Vectors are often stored in a compressed format on disk to save space.
• Tombstone Overhead: The tombstone marker itself is a minimal record, but the space occupied by the compressed vector it marks for deletion is only freed after compaction.
• Trade-off: Compression reduces I/O and storage costs, making the management of tombstones and compaction more efficient overall.

The overarching discipline governing the lifecycle of embeddings. Vector tombstoning is a critical operational procedure within this lifecycle for handling deletions.

• Lifecycle Stages: Includes ingestion, versioning, updates, deletions (tombstoning), and archival.
• Policy Enforcement: Data retention policies and Time-To-Live (TTL) settings can automatically generate tombstones for expired vectors.
• Orchestration: Requires careful coordination with ingestion pipelines and index rebuild schedules to ensure query consistency.

The formal guarantee a distributed vector database provides about when a vector tombstone becomes visible across the system. This dictates the user-observed behavior of a delete operation.

• Strong Consistency: A tombstone is immediately visible to all subsequent reads, ensuring a deleted vector never appears after the delete command succeeds.
• Eventual Consistency: The tombstone propagates asynchronously; a deleted vector may briefly be returned from a replica that hasn't yet received the tombstone.
• Choice Impact: Determines the system's latency, availability, and the perceived correctness of delete operations.

An architecture that automatically moves vector data between performance/cost tiers (e.g., SSD, HDD, object storage). Tombstoning and compaction are often tier-aware processes.

• Hot/Cold Data: Frequently accessed vectors reside on fast SSDs, while older, less-queried data moves to cheaper HDDs.
• Compaction Strategy: Compaction jobs that process tombstones may run with different priorities or frequencies depending on the storage tier to optimize cost.
• Archival: Vectors marked with tombstones in the hottest tier may be skipped during migration to colder tiers, as they are slated for deletion.