Skip to content

CONCEPT Cited by 1 source

TTL-based deletion with jitter

TTL-based deletion with jitter is the deletion strategy of marking items as expired now with a per-item randomised TTL, letting background compaction / TTL-GC physically remove them later — instead of issuing immediate physical deletes. The jitter staggers GC work across time so compaction doesn't spike when many items are logically deleted together.

The technique is specifically a workaround for engines (like Cassandra) that struggle with high-volume item-level deletes because each one creates a concepts/tombstone the compactor must track, propagate, and eventually physically evict.

The problem

Cassandra item-level deletes:

  • Emit one tombstone per key.
  • Tombstones must be retained across all replicas for gc_grace_seconds (default 10 days) before physical eviction, so a partitioned replica coming back online doesn't resurrect the deleted data.
  • Each tombstone increases read amplification: scans have to filter tombstoned entries until compaction evicts them.
  • Many tombstones in one partition can cause Cassandra to log tombstone-overload warnings or outright fail reads.

So "some storage engines (any store which defers true deletion) such as Cassandra struggle with high volumes of deletes due to tombstone and compaction overhead." (Source: sources/2024-09-19-netflix-netflixs-key-value-data-abstraction-layer)

The Netflix KV DAL response

"Item-level deletes create many tombstones but KV hides that storage engine complexity via TTL-based deletes with jitter. Instead of immediate deletion, item metadata is updated as expired with randomly jittered TTL applied to stagger deletions. This technique maintains read pagination protections. While this doesn't completely solve the problem it reduces load spikes and helps maintain consistent performance while compaction catches up."

Mechanism:

  1. Client issues item-level delete.
  2. KV DAL writes a TTL-expired metadata marker — logical visibility is removed immediately from the caller's perspective.
  3. The TTL has random jitter around a base value.
  4. Compaction / TTL-GC eventually evicts the expired entries.
  5. Because different items have different TTLs, the GC work is spread across time rather than spiked.

Why jitter specifically

Without jitter: a bulk logical delete (say, delete all items under one id at time T) would give every item the same TTL — and every item would become physically-delete-eligible at T+TTL. Compaction would see a wall of work at that instant. Spiky compaction load means spiky read latency, failed reads on tombstone warnings, and operational instability.

With jitter: items age out over a window, compaction stays steady-state, and tail latency behaves.

This is the load-shaping role of jitter, identical in shape to jittered retry backoff: smoothing correlated events over time to prevent thundering-herd effects on a shared resource.

Honest framing

Netflix is upfront that this is a mitigation, not a fix — tombstones still exist, compaction still has to clear them, and the grace-period constraint (~10 days for Cassandra default) is unchanged. What's bought is:

  • No load spike at the moment of logical delete.
  • Read pagination stays protected — paginated reads over a partition being actively deleted don't suddenly skip rows out from under the caller.
  • Caller can resume normal delete QPS without fear of collapsing the compactor.
  • Soft deletes with periodic physical cleanup — the older, manual form of the same idea (application-level deleted_at column + a cron that later purges).
  • Kafka log compaction — time-based plus key-based eviction with similar spread-over-time characteristics for deletion work.
  • Lazy GC in Go / Java — jittered sweep timers so GC pauses aren't synchronized across workers.

Trade-offs

  • Physical deletion is delayed beyond what the caller might expect — "I asked for delete" doesn't mean "bytes are off disk." For legal/privacy deletion (GDPR right-to-erasure) this is not acceptable and a stronger path is needed.
  • Storage amplification in the interim — until TTL expires, the metadata-marker row occupies space.
  • Complex to debug — "item is still there on disk but not visible to reads" requires operators to understand the TTL- jitter discipline.
  • Caller can't query "is this truly gone" — the DAL hides the state.

Seen in

Last updated · 319 distilled / 1,201 read