MEMTABLE - The In-Memory Speed Demon

Complete Answer:

A memtable is Cassandra's in-memory write buffer - a sorted data structure that temporarily holds recent writes before they're flushed to disk as SSTables.

What is Memtable:

• Structure: Concurrent skip list (lock-free sorted tree)
• Location: JVM heap memory (or off-heap)
• Per-table: Each Cassandra table has its own memtable
• Size: Typically 64-128MB before flush
• Sorted: Maintains order by partition key → clustering key
• Volatile: Data lost on crash (protected by commit log)

Why Critical for Write Performance:

1. RAM is 100,000x faster than disk:

• RAM access: 100 nanoseconds = 0.0001ms
• SSD access: 100 microseconds = 0.1ms (1,000x slower)
• HDD access: 10 milliseconds (100,000x slower!)
• Writing to memtable = writing to RAM = instant!

2. Batches writes to amortize disk I/O:

• Instead of writing each mutation to disk individually
• Accumulate many writes in memtable (64-128MB)
• Flush all at once to SSTable
• One big sequential write >> many small random writes
• Reduces disk I/O overhead by 100-1000x!

3. Provides sorted structure:

• Skip list maintains sort order automatically
• When flushed, SSTable is already sorted
• No need to sort on flush (would be slow!)
• Makes range queries fast

Write Path Flow:

1. Write arrives at coordinator
2. Write to commit log (durability) - 1ms
3. Write to memtable (performance) - 0.1ms
4. Return SUCCESS to client - total ~3ms
5. Later: Flush memtable to SSTable (async)

Performance Impact:

Without memtable: Every write = disk I/O = 10-50ms latency

With memtable: Every write = RAM access = 0.1ms latency

Result: 100-500x faster writes!

Flush Process:

• When memtable reaches 64-128MB threshold
• Freeze current memtable (make read-only)
• Create new empty memtable (1ms operation)
• Flush frozen memtable to SSTable in background (2-5 seconds)
• Writes never blocked - go to new memtable immediately!

Key Insight: The memtable is the foundation of Cassandra's write performance. By buffering writes in RAM and batching disk I/O, Cassandra achieves sub-5ms write latency even at 500,000 writes/second. This is what makes Cassandra suitable for write-heavy workloads like time-series data, logging, and real-time analytics!

Complete Answer:

Cassandra uses a concurrent skip list for memtable because it provides O(log n) operations with lock-free concurrency - critical for high-throughput writes.

Skip List Basics:

• Structure: Multiple levels of sorted linked lists
• Bottom level: All elements in sorted order
• Higher levels: "Express lanes" that skip ahead
• Search: Start at top level, drop down when needed
• Probabilistic: Random promotion to higher levels
• Complexity: O(log n) average for insert, search, delete

Why Skip List vs Alternatives:

Skip List vs Red-Black Tree:

• Skip list advantage: Lock-free concurrent updates!
• Red-black tree requires locking for rebalancing
• Lock contention kills throughput at high concurrency
• Skip list: Use Compare-And-Swap (CAS) operations
• Multiple threads can insert simultaneously without waiting
• Throughput scales linearly with CPU cores
• Skip list advantage: Simpler implementation
• No complex rotation/rebalancing logic
• Easier to reason about correctness

Skip List vs Hash Table:

• Skip list: Maintains sorted order
• Hash table: No inherent order
• Critical: Cassandra needs sort order for clustering keys
• Range queries require sorted structure
• SSTable flush requires sorted data
• Skip list: Range scan is O(log n + k)
• Hash table: Range scan would be O(n)

Skip List vs B-tree:

• Skip list advantage: Better for in-memory
• B-tree optimized for disk (minimize seeks)
• In memory, simpler structure wins
• Skip list advantage: Lock-free possible
• B-tree difficult to make lock-free (complex balancing)
• Skip list: Lower constant factors
• Fewer pointer chases than B-tree

Lock-Free Concurrency Deep Dive:

This is THE critical reason Cassandra uses skip list!

Problem with locks:

• Thread A acquires lock, inserts data
• Threads B, C, D wait for lock
• At high concurrency (100+ threads), massive contention
• Throughput degrades as threads increase

Skip list lock-free approach:

• Use atomic CAS (Compare-And-Swap) operations
• Insert attempts: CAS(node.next, NULL, new_node)
• If CAS fails (another thread inserted), retry
• No waiting, no blocking
• All threads make progress simultaneously
• Throughput scales linearly with cores!

Real Performance Impact:

Benchmark: 16-core server, concurrent inserts:

Red-black tree (locked): 50,000 inserts/sec (lock contention)

Skip list (lock-free): 400,000 inserts/sec (8x faster!)

Scaling: Skip list throughput increases with cores, locked structure plateaus

Trade-offs:

• Skip list downside: Probabilistic (not guaranteed O(log n))
• In practice: Very rare to degrade
• Skip list downside: Pointer overhead
• Each node needs multiple next pointers (for levels)
• ~20-30 bytes overhead per entry
• Acceptable for in-memory structure

Key Insight: The skip list's lock-free property is what enables Cassandra to handle 500,000 writes/second on a single node. Any locked data structure would become a bottleneck at that scale. The combination of O(log n) operations, sorted order, and lock-free concurrency makes skip list the perfect choice for memtable!