TOMBSTONES - Deletion Markers

What is "Deletion"?

Deletion = Removing data
Like throwing away paper: You don't want it anymore

In regular databases:
• Find the data
• Erase it immediately
• Gone forever!

In Cassandra (distributed):
• Can't delete immediately!
• Data lives on multiple servers
• Need coordination
• Use tombstones instead ✓

Why different? Multiple copies need to know!

What is a Tombstone?

Tombstone = Marker for deleted data
Like a gravestone: Shows something was here, now it's gone

Instead of erasing:
• Cassandra writes a marker
• Says "This data is deleted"
• Keeps marker for a while
• Eventually removes marker too

Why markers:
All servers need to see deletion
Marker spreads to all copies
Ensures everyone knows!

Distributed System

Distributed = Data on multiple computers

Example: 3 servers
• Server A has copy 1
• Server B has copy 2
• Server C has copy 3

Problem with deletion:
• Delete on Server A
• But Server B offline!
• When B comes back: still has data!
• Data "resurrects" (zombie data!)

Solution: Tombstones prevent resurrection!

Replication

Replication = Making copies
Like photocopying a document

Why replicate:
• Backup (if one server fails)
• Faster reads (read from nearest)
• No single point of failure

Replication Factor (RF):
• RF=3: 3 copies of every row
• Common in production

Deletion challenge:
Delete 1 copy? Other 2 remain!
Need to delete ALL copies!

Timestamp

Timestamp = When something happened
Like a clock reading

Cassandra uses microseconds:
• Example: 1735488000000000
• Very precise timing

Why important:
• Determines order of operations
• Delete at time 100
• Write at time 90
• Delete wins! (happened later)

Tombstone has timestamp:
Marks WHEN deletion happened!

Compaction

Compaction = Cleanup process
Like organizing a messy desk

What it does:
• Merges multiple files
• Removes old versions
• Deletes expired tombstones
• Frees up disk space

When tombstones removed:
• After gc_grace_seconds (10 days)
• During compaction
• When safe to delete

Compaction is the janitor!

GC Grace Seconds

GC Grace = How long to keep tombstones
"Grace period" before removal

Default: 864000 seconds
= 864000 ÷ 60 ÷ 60 ÷ 24
= 10 days

Why 10 days:
• Gives offline servers time
• Server comes back online
• Sees tombstone
• Deletes its copy too!

After 10 days:
Tombstone itself deleted!

Zombie Data

Zombie Data = Deleted data comes back!
Like a horror movie - data won't stay dead

How it happens:
1. Delete data (Server A)
2. Server B offline (missed deletion)
3. Tombstone expires (after 10 days)
4. Server B comes back online
5. Repairs: B has data, A doesn't
6. Copies data back to A!
7. Zombie! Data resurrected! 👻

Prevention: Keep tombstones long enough!

SSTable (Data File)

SSTable = Sorted String Table
File on disk with data

Immutable = Never changes!
• Once written, can't modify
• Can only create new SSTables

Why tombstones needed:
• Can't erase from SSTable
• File is immutable!
• Must write tombstone in NEW file

Compaction merges:
• Old data + tombstone = deleted
• New SSTable without data!

TTL (Time To Live)

TTL = Auto-delete after time
Like milk expiration date

Example:
INSERT ... USING TTL 3600
(Delete after 3600 seconds = 1 hour)

How it works:
• Write data with TTL
• After TTL expires
• Automatically becomes tombstone!
• No DELETE needed

Perfect for:
Session data, cache, temporary records

Definition

Tombstone = Special marker for deleted data

What it is:
• NOT actual data deletion
• A marker that says "deleted"
• Has timestamp (when deleted)
• Stored like normal data

Looks like:
Key: "user123"
Value: <TOMBSTONE>
Timestamp: 1735488000

Think: Gravestone marking deleted data!

What It Does

Tombstone overrides old data

When query reads:
• Finds data: "John" age 30
• Also finds: TOMBSTONE
• Tombstone newer? Return nothing ✓
• Data newer? Return data

Timestamp wins:
• Data written at time 100
• Tombstone at time 200
• Tombstone wins! (newer)

Prevents seeing deleted data!

Lifecycle

Tombstone has a lifespan:

Phase 1: Creation (instant)
• DELETE executed
• Tombstone written

Phase 2: Active (10 days)
• Spreads to all replicas
• Blocks old data
• Participates in queries

Phase 3: Removal (compaction)
• After gc_grace_seconds
• Compaction runs
• Tombstone deleted!

Total: ~10 days existence

The Distributed Deletion Problem

Scenario: You have data replicated on 3 servers (RF=3)

Initial State:
• Server A: user123 = "Alice"
• Server B: user123 = "Alice"
• Server C: user123 = "Alice"
All 3 servers have the same data ✓

❌ Attempt 1: Direct Deletion (BROKEN!)
• Client sends: DELETE FROM users WHERE id='user123'
• DELETE reaches Server A (deletes immediately)
• Server B is down for maintenance 🔧
• Server C has network issue 🌐

Current state:
• Server A: (nothing - deleted) ✓
• Server B: user123 = "Alice" (still has it!)
• Server C: user123 = "Alice" (still has it!)

2 days later - Server B comes back:
• Repair process runs (anti-entropy)
• B compares with A: "I have user123, you don't!"
• B thinks A lost the data
• B sends data to A: "Here, I'll restore it for you!"
• ZOMBIE! user123 = "Alice" is back on A! 👻

This is catastrophic!
• Deleted data reappears
• GDPR compliance violated (can't guarantee deletion)
• Financial records reappear (audit nightmare)
• Deleted user accounts come back

✅ Solution: Tombstones (WORKS!)
• Client sends: DELETE FROM users WHERE id='user123'
• Server A writes: user123 = TOMBSTONE(timestamp: 100)
• Server B down (missed it)
• Server C network issue (missed it)

Current state:
• Server A: user123 = TOMBSTONE(100) ✓
• Server B: user123 = "Alice" (timestamp: 50)
• Server C: user123 = "Alice" (timestamp: 50)

When Server B comes back:
• Repair process runs
• B sees: A has TOMBSTONE(100), I have Alice(50)
• Timestamp comparison: 100 > 50
• B adopts tombstone: "Oh, this was deleted!"
• B writes: user123 = TOMBSTONE(100)
• Server C also gets tombstone
• All 3 servers now know data is deleted! ✓

After 10 days (gc_grace_seconds):
• All servers have seen the tombstone
• Compaction removes tombstone
• Data truly gone
• No resurrection possible!

Key Insight: Tombstones convert "absence of data" into "presence of deletion marker" - something that can be replicated and wins timestamp battles!

Timestamp Conflicts

Tombstones use timestamps to win!

Example conflict:
• Server A: DELETE at time 100
• Server B: WRITE at time 90

Who wins?
• Tombstone(100) vs Data(90)
• 100 > 90
• Tombstone wins! ✓
• Data is deleted

Reverse scenario:
• Server A: DELETE at time 100
• Server B: WRITE at time 110
• Data(110) wins!
• Deletion overridden (intended!)

Last Write Wins (LWW) principle!

Immutable SSTables

SSTables can't be modified!

Problem:
• Data written to SSTable
• File closed (immutable)
• Can't go back and erase!

Solution:
• Write tombstone in NEW SSTable
• During compaction:
- Old SSTable: user123 = "Alice"
- New SSTable: user123 = TOMBSTONE
- Merged result: (deleted)

Tombstones work with immutability!

Eventual Consistency

Deletions take time to propagate

Timeline:
• T=0: DELETE executed
• T=1ms: Tombstone on Server A
• T=100ms: Replicated to Server B
• T=5min: Server C comes online
• T=10min: All servers have it ✓

During propagation:
• Queries might still see data
• Tombstone eventually wins
• Consistent eventually!

This is "eventual consistency"

1. Cell Tombstone

Deletes a single column value

Query:
DELETE email FROM users WHERE id='user123'

What happens:
• Only 'email' column deleted
• Other columns remain
• Tombstone for one cell only

Before:
user123: {name: "Alice", email: "alice@email.com"}

After:
user123: {name: "Alice", email: DELETED}

Most granular tombstone type!

2. Row Tombstone

Deletes entire row

Query:
DELETE FROM users WHERE id='user123'

What happens:
• Entire row deleted
• All columns gone
• Single tombstone for whole row

Before:
user123: {name: "Alice", email: "alice@email.com", age: 30}

After:
user123: ROW DELETED

Most common tombstone type!

3. Partition Tombstone

Deletes entire partition

Query:
DELETE FROM events WHERE user_id='user123'
(Partition key = user_id)

What happens:
• All rows in partition deleted
• Could be thousands of rows!
• Single partition tombstone

Example:
• user123 has 10,000 events
• One tombstone deletes all!
• Very efficient ✓

Efficient for large deletions!

4. Range Tombstone

Deletes range of clustering keys

Query:
DELETE FROM events
WHERE user_id='user123'
AND timestamp >= '2024-01-01'
AND timestamp < '2024-02-01'

What happens:
• Deletes date range
• One tombstone for whole range
• Marks start→end as deleted

Example:
Range: Jan 1 - Feb 1
Could be 1000s of rows
Single range tombstone!

Perfect for time-series data!

5. TTL Tombstone

Auto-created when TTL expires

Query:
INSERT INTO sessions (id, data)
VALUES ('session123', 'data')
USING TTL 3600; -- 1 hour

What happens:
• After 1 hour passes
• Automatically becomes tombstone
• No DELETE needed!

Perfect for:
• Session data
• Cache entries
• Temporary records

Set-it-and-forget-it deletion!

Tombstone Sizes

Different types, different overhead:

Cell Tombstone: ~10 bytes
• Column name + timestamp

Row Tombstone: ~20 bytes
• Partition key + timestamp

Partition Tombstone: ~15 bytes
• Partition key only
• Deletes 1000s of rows!

Range Tombstone: ~30 bytes
• Start + end range + timestamp

Insight: Tombstones are tiny but powerful!

What It Is

gc_grace_seconds = Tombstone lifespan

Default: 864,000 seconds
• 864000 ÷ 60 = 14,400 minutes
• 14400 ÷ 60 = 240 hours
• 240 ÷ 24 = 10 days

Purpose:
• Time for offline servers
• Come back and see deletion
• Prevents zombie data

After 10 days: safe to remove!

Why 10 Days?

Assumptions about server downtime:

Typical scenarios:
• Planned maintenance: 1-4 hours
• Network issues: Minutes to hours
• Hardware failure: 1-3 days
• Catastrophic failure: 3-7 days

10 days provides:
• Plenty of buffer ✓
• Time for weekend repairs
• Margin for errors

Conservative but safe!

Configuration

Set per table:

View current:
DESC TABLE users;

Change value:
ALTER TABLE users
WITH gc_grace_seconds = 86400;
(1 day = 86400 seconds)

Common values:
• 10 days: Default (safe)
• 1 day: Fast-moving data
• 0: Special cases only!

Too Short = Danger!

Setting gc_grace_seconds = 0:

What happens:
• Tombstone removed immediately
• Server offline for 1 hour
• Tombstone already gone!
• Server comes back with old data
• Zombie data! 👻

Only use 0 when:
• Single node cluster (testing)
• Never run repair
• Understand the risks!

Generally: DON'T DO THIS!

Too Long = Problems!

Setting gc_grace_seconds = 30 days:

What happens:
• Tombstones live 30 days
• Accumulate on disk
• Slow down queries
• Waste disk space

Problems:
• Many tombstones in reads
• Performance degradation
• Larger SSTables
• Slower compaction

Balance safety vs performance!

Best Practice

Follow these guidelines:

Default (10 days):
• Most tables ✓
• Safe and proven

Shorter (1-3 days):
• Stable cluster
• Frequent deletions
• Monitor closely

Never use 0 unless:
• Testing only
• Single node
• You're an expert

When in doubt: keep default!

The Tombstone Accumulation Problem

Worst-case scenario: Millions of tombstones!

Example: Time-series data with TTL
• Table: sensor_data (temperature readings)
• Inserts: 1 million rows/day with TTL=7 days
• After 7 days: 1M rows become tombstones
• After 10 days (gc_grace): Tombstones eligible for removal
• But compaction hasn't run yet!

State after 10 days:
• Active data: 7M rows (7 days × 1M/day)
• Tombstones: 3M+ (days 8-10)
• Ratio: 30% tombstones!

When you query:
• Must read ALL tombstones
• Filter them out
• Return only live data
• Massive overhead!

Performance impact:
• Query scans 10M rows (7M live + 3M tombstones)
• 43% waste (3M ÷ 10M)
• P99 latency: 50ms → 200ms (4x slower!)
• Disk I/O: Unnecessary reads
• Memory: Tombstones in bloom filters
• Network: Tombstones sent between nodes

Warning threshold:
Cassandra warns at 100,000 tombstones in a single query!

WARN  [ReadStage-2] Read 250000 live rows and 500000 tombstone cells
for query SELECT * FROM sensor_data LIMIT 1000

1. Read Performance

Tombstones slow queries!

Why:
• Must read tombstones from disk
• Process and filter them
• Then return live data

Example query:
SELECT * FROM users LIMIT 100

Without tombstones:
• Read 100 rows (5ms)

With 10k tombstones:
• Read 10,000 tombstones (100ms)
• Read 100 live rows (5ms)
• Total: 105ms (21x slower!)

More tombstones = slower queries!

2. Disk Space

Tombstones consume space!

Example table:
• 1B rows deleted
• Each tombstone: 20 bytes
• Total: 20GB of tombstones!

Problem:
• Disk fills up
• Can't add new data
• Expensive storage costs

Solution:
• Run compaction
• Remove expired tombstones
• Free up space ✓

3. Compaction Overhead

Many tombstones = slow compaction!

Why:
• Must process all tombstones
• Check if expired
• Merge with data

Example:
• 100GB data
• 50GB tombstones
• Compaction processes 150GB
• Takes 3x longer!

Impact:
• Higher CPU usage
• More disk I/O
• Slower overall system

A. Discord: TTL Tombstone Disaster (500M Tombstones!)

The Problem:
Discord stores message read status with TTL=30 days. Every time a user reads a message, write with TTL. 150M users × 1000 messages/day = 150 billion operations. After 30 days, massive tombstone accumulation!

What went wrong:
• Table: user_read_status (user_id, channel_id, message_id, TTL 30 days)
• Writes: 150 billion/month
• After TTL expires: All become tombstones
• gc_grace_seconds: 10 days
• Total tombstone period: 30 days (TTL) + 10 days (grace) = 40 days
• Tombstone accumulation: 150B × 40/30 = 200 billion tombstones!

Impact:
• Query: "Get unread messages for user"
• Scanned 50M tombstones per query
• P99 latency: 15ms → 3000ms (200x slower!)
• Warnings: "Read 100000 tombstones" constantly
• Disk usage: 2TB of tombstones (50% of cluster!)
• Compaction: Couldn't keep up

Solution:
1. Reduced TTL: 30 days → 7 days (less accumulation)
2. Reduced gc_grace: 10 days → 1 day (faster removal)
3. Aggressive compaction: Forced major compaction
4. Rewrote approach: Moved to time-bucketed partitions
- New partition each day
- Drop entire partition after 7 days (no tombstones!)

Results after fix:
• Tombstone count: 200B → 2M (99.999% reduction!)
• P99 latency: 3000ms → 18ms (167x faster!)
• Disk usage: 2TB freed
• Warnings: Gone ✓

Lesson learned:
"TTL creates tombstones! High-volume TTL writes = tombstone explosion. Time-bucketed partitions + partition drops avoid tombstones entirely. This saved our cluster from collapsing."

B. Instagram: Deletion Pattern Optimization

Use case:
User deletes photos/posts. 2B users, average 500 photos each. Deletion rate: 0.1% daily = 1M photo deletions/day. Need efficient deletion without tombstone accumulation.

Initial approach (WRONG):
• DELETE FROM user_photos WHERE user_id=X AND photo_id=Y
• Created cell tombstone for each photo
• 1M deletions/day = 1M tombstones/day
• After 10 days (gc_grace): 10M tombstones

Problem:
• Query: "Get user's photos"
• Some users deleted 1000s of photos
• Scan 1000s of tombstones per user
• P99: 50ms → 400ms (8x slower!)

Optimized approach:
1. Soft delete instead of hard delete:
- UPDATE photos SET deleted=true, deleted_at=now()
- No tombstone created! ✓
- Query: WHERE deleted=false
2. Async cleanup job:
- Nightly job processes deleted=true
- Batches deletions into range tombstones
- One range tombstone for 1000 photos!
3. Short gc_grace for cleanup table:
- gc_grace_seconds = 86400 (1 day)
- Rapid tombstone removal

Results:
• Tombstones per query: 1000s → 0 (live queries see no tombstones!)
• P99 latency: 400ms → 35ms (11x faster!)
• Cleanup efficiency: 1000 photos = 1 range tombstone
• Compaction load: 90% reduction

Instagram engineer quote:
"Never delete in the hot path! Soft delete + async cleanup = best of both worlds. Users see instant deletion (deleted=true), but actual tombstones created in background batches. This keeps read queries fast while still removing data."

C. Uber: Time-Series gc_grace Tuning

Scenario:
Trip location history - massive time-series writes. Table stores GPS coordinates every 4 seconds during trips. TTL=30 days for GDPR compliance. 20M trips/day × 450 points/trip × 30 days = 270 billion rows!

Challenge:
• After 30 days: 9B rows/day expire → tombstones
• gc_grace_seconds: 864000 (10 days default)
• Tombstone accumulation: 9B/day × 10 days = 90 billion tombstones!
• Queries scanning expired data regions: massive tombstone overhead

Initial problem:
• P99 read latency: 25ms → 800ms
• Disk usage: 80% tombstones
• Warning logs: 50k/day about tombstones
• Compaction: Running 24/7, still couldn't catch up

Uber's solution - Aggressive tuning:
1. Reduced gc_grace_seconds: 10 days → 1 day
- Rationale: "Our cluster is stable, nodes rarely down >24h"
- Monitoring: Alert if node down >12 hours
- Risk accepted: Worth it for performance
2. Increased repair frequency:
- Run repair every 12 hours (instead of weekly)
- Ensures deletions propagate quickly
3. Partition strategy:
- Partition by (trip_id, day_bucket)
- Old partitions naturally age out
4. Compaction tuning:
- More frequent minor compactions
- Aggressive tombstone_threshold: 0.1 (vs 0.2 default)

Results:
• Tombstone lifespan: 10 days → 1 day (90% reduction)
• Tombstone count: 90B → 9B (10x less!)
• P99 latency: 800ms → 45ms (18x faster!)
• Disk usage: 80% → 15% tombstones
• Compaction: Caught up within 48 hours

Trade-off:
• Risk: If node down >24 hours, possible zombie data
• Mitigation: Monitoring + alerts + 12h repair cycles
• Reality: In 2 years of production, zero zombie incidents

Key insight:
"Default gc_grace_seconds (10 days) is conservative. For stable clusters with good monitoring, 1-3 days is often better. The performance gain from faster tombstone removal outweighs the small zombie risk. But: requires operational excellence!"

1. Monitor Tombstone Warnings

Set up monitoring!

Watch for:
• "Read X tombstones" warnings
• Threshold: 100,000 tombstones

Alert when:
• >10 warnings/hour
• Consistent growth

Check with nodetool:
nodetool tablestats keyspace.table
(Look for "Tombstoned cells")

Early detection prevents disasters!

2. Use Time-Bucketed Partitions

For time-series data:

Instead of TTL:
❌ USING TTL 86400
(Creates tombstones)

Use partitions:
✓ Partition key: (sensor_id, day)
• One partition per day
• Drop entire partition when old
• No tombstones created!

Example:
DROP TABLE sensor_data_20241201;
(Deletes whole partition instantly)

3. Tune gc_grace Carefully

Guidelines by scenario:

Stable cluster (3 data centers):
• gc_grace: 3-5 days ✓
• Aggressive repair schedule

Volatile environment:
• gc_grace: 10 days (default) ✓
• Conservative, safe

High-delete workload:
• gc_grace: 1-2 days
• Fast tombstone removal
• Requires monitoring!

Never use 0 in production!

4. Soft Delete When Possible

Instead of DELETE:
UPDATE SET deleted=true

Benefits:
• No tombstone in hot path!
• Instant for user
• Query: WHERE deleted=false

Async cleanup:
• Background job
• Batch actual DELETEs
• Range tombstones

Perfect for:
User-facing deletions!

5. Regular Compaction

Ensure compaction runs!

Check:
nodetool compactionstats

If tombstones accumulate:
• Force compaction:
nodetool compact keyspace table

Tune strategy:
• tombstone_threshold: 0.2→0.1
• More aggressive removal

Monitor:
• Pending compactions
• Should be near 0

6. Avoid Frequent Range Deletes

Range deletes create range tombstones:

Example (BAD):
DELETE FROM events
WHERE user_id=X
AND time < '2024-01-01'

Creates:
• Large range tombstone
• Affects all queries in range

Better:
• Use time-bucketed partitions
• Drop old partitions
• Or design for no deletes!