Log-Based Storage

Log-Based Storage Overview

LOG-BASED STORAGE STRUCTURE:

Append-Only Log (Partition 0)
┌─────────┬─────────┬─────────┬─────────┬─────────┬─────────┐
│ Offset 0│ Offset 1│ Offset 2│ Offset 3│ Offset 4│ Offset 5│
│ Record A│ Record B│ Record C│ Record D│ Record E│ Record F│
│ Time: T0│ Time: T1│ Time: T2│ Time: T3│ Time: T4│ Time: T5│
└─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘
↑
New writes append here

KEY PROPERTIES:
├── Append-only: New records added to end, never modified
├── Immutable: Records never changed once written
├── Ordered: Each record has monotonically increasing offset
├── Sequential: Physical writes are sequential on disk
└── Time-indexed: Records naturally ordered by time

DISK LAYOUT (Segment-Based):

Partition Directory:
├── 00000000000000000000.log (Segment 1: offsets 0-999)
├── 00000000000000000000.index (Index for segment 1)
├── 00000000000001000000.log (Segment 2: offsets 1000-1999)
├── 00000000000001000000.index (Index for segment 2)
└── 00000000000002000000.log (Active segment, offsets 2000+)

Each segment file:

- Fixed max size (e.g., 1 GB)
- Sequential writes (O(1) append)
- Independent deletion (retention)

Traditional vs Log-Based Storage

Traditional Database (In-Place Updates):
┌──────────────┐
│ User Table   │
├──────────────┤
│ id: 123      │  ← UPDATE changes this record in place
│ name: "John" │  ← Old value lost forever
│ age: 30      │  ← No history preserved
└──────────────┘

Log-Based Storage (Append-Only):
┌────────────────────────────────────────────────┐
│ Log: User Events │
├────────────────────────────────────────────────┤
│ [0] UserCreated(id=123, name="John", age=25) │
│ [1] UserUpdated(id=123, age=26) │
│ [2] UserUpdated(id=123, age=30) │ ← New event appended
└────────────────────────────────────────────────┘
↑
Complete history preserved, can replay to any point

Disk Performance Characteristics

Operation Type          Throughput       Latency
─────────────────────────────────────────────────
Random Writes (HDD)     ~100 writes/sec  10ms
Sequential Writes (HDD) ~100,000/sec     0.01ms
Sequential Writes (SSD) ~500,000/sec     0.002ms

Sequential writes are 1000x faster! 🚀

B-Tree vs Log Storage

Traditional B-Tree Index (Random Writes):
Write "user_456" →
1. Seek to index page (random disk seek)
2. Read page into memory
3. Modify page
4. Write page back (random write)
Result: 10ms per write

Log-Based Storage (Sequential Writes):
Write "user_456" →

1. Append to end of current segment file
2. Flush to disk sequentially
 Result: 0.01ms per write

100x-1000x faster!

Why Segments

WHY SEGMENTS?

Problem with Single Log File:
┌─────────────────────────────────────┐
│ single-log-file.log (100 GB) │
│ │
│ Can't delete old data without │
│ rewriting entire file! │
└─────────────────────────────────────┘

Solution with Segments:
├── segment-0.log (1 GB) ← Delete this entire file (old data)
├── segment-1.log (1 GB) ← Keep
├── segment-2.log (1 GB) ← Keep
└── segment-3.log (500 MB, active) ← Currently writing

Deletion = O(1) file delete, no rewriting!

Indexing Challenge

Problem: How to find offset 12,345,678 quickly in a 100 GB log?

Naive approach:

- Read sequentially from beginning
- Time: O(n), could take minutes!

Sparse Index Structure

SPARSE INDEX STRUCTURE:

Segment: 00000000000010000000.log (offsets 10M-11M)

Index File: 00000000000010000000.index
┌──────────────────────────────────────┐
│ Offset → File Position │
├──────────────────────────────────────┤
│ 10,000,000 → byte 0 │ ← Index every N records
│ 10,010,000 → byte 52,428,800 │ ← (e.g., every 10K)
│ 10,020,000 → byte 104,857,600 │
│ 10,030,000 → byte 157,286,400 │
│ ... │
└──────────────────────────────────────┘

To find offset 10,025,000:

1. Binary search index → Find 10,020,000 at byte 104,857,600
2. Seek to byte 104,857,600
3. Scan sequentially 5,000 records (fast, in memory)

Result: O(log n) index lookup + small sequential scan

Time-Travel and Replay

LOG WITH TIME-INDEXED DATA:

[0] UserCreated(id=123) at 2025-01-01 10:00
[1] UserUpdated(id=123, age=26) at 2025-01-02 11:00
[2] UserUpdated(id=123, age=30) at 2025-01-03 12:00
[3] UserDeleted(id=123) at 2025-01-04 13:00

QUERIES:

- "What was user 123's state on 2025-01-02?"
→ Replay log up to offset 1 → {id=123, name="John", age=26}

- "Rebuild entire database from scratch"
→ Replay log from offset 0 → Full reconstruction

- "Reprocess last 7 days with new business logic"
→ seekToTimestamp(7 days ago) → Replay with new code

Bug Recovery with Log Storage

Bug discovered in analytics pipeline:
1. Pipeline processed 1 million events with incorrect logic
2. Traditional system: Data corrupted, hard to fix
3. Log-based system:
 - Keep log intact
 - seekToTimestamp(bug_introduced_time)
 - Replay events with corrected code
 - Output to new table
 - Validate and switch
 Result: Zero data loss, safe recovery

Time-Based Retention

Delete segments older than N days:

Day 1: [Seg 0][Seg 1][Seg 2][Seg 3]
Day 8: [Seg 1][Seg 2][Seg 3][Seg 4] ← Seg 0 deleted (> 7 days old)
Day 15: [Seg 2][Seg 3][Seg 4][Seg 5] ← Seg 1 deleted

Size-Based Retention

Keep only last 100 GB:

[Seg 0: 20GB][Seg 1: 20GB][Seg 2: 20GB][Seg 3: 20GB][Seg 4: 30GB]
Total: 110 GB → Delete Seg 0 → 90 GB ✓

Log Compaction

BEFORE COMPACTION (All events preserved):
[0] user_123: {name: "John", age: 25}
[1] user_456: {name: "Jane", age: 30}
[2] user_123: {name: "John", age: 26}  ← Update
[3] user_123: {name: "John", age: 30}  ← Update
[4] user_456: {name: "Jane", age: 31}  ← Update

AFTER COMPACTION (Only latest per key):
[2] user_123: {name: "John", age: 30} ← Latest for 123
[4] user_456: {name: "Jane", age: 31} ← Latest for 456

Result: Same final state, 60% smaller log
Use case: Changelog topics, database snapshots

High-Throughput Writes Use Case

Scenario: Ingesting millions of events per second
Why logs: Sequential writes max out disk bandwidth
Example: IoT sensor data, clickstream analytics

Audit and Compliance Use Case

Scenario: Financial transactions requiring complete audit trail
Why logs: Immutable, ordered history of all changes
Example: Banking transactions, healthcare records

Event Sourcing Use Case

Scenario: Need to rebuild state from historical events
Why logs: Natural event stream with replay capability
Example: E-commerce order processing, booking systems

Stream Processing Use Case

Scenario: Real-time data pipelines and transformations
Why logs: Natural fit for streaming frameworks
Example: Fraud detection, real-time recommendations

Point Queries Warning

Problem: "Find user by email address"
Issue: Must scan entire log or build secondary index
Alternative: Use indexed database (B-tree, hash index)

Frequent Updates Warning

Problem: Updating same sensor reading every 10ms
Issue: Millions of log entries for same key
Alternative: In-memory cache + periodic snapshots

GDPR Deletion Warning

Problem: "Delete all data for user_123"
Issue: Logs are append-only, can't delete from middle
Alternative: Tombstone records + compaction, or use mutable database