LSM trees in write-heavy systems in Data Structures Theory - Step-by-Step Execution

Concept Flow - LSM trees in write-heavy systems

Write request arrives

↓

Write to in-memory structure (MemTable)

↓

MemTable full?

No→Wait for next write

Yes↓

Flush MemTable to disk as SSTable

↓

Merge/Compaction of SSTables

↓

Optimized disk storage for reads

↓

Next write request

Writes first go to fast memory, then flush to disk when full, followed by merging files to keep reads efficient.

Execution Sample

Data Structures Theory

write(data)
  memtable.add(data)
  if memtable.is_full():
    flush_to_disk(memtable)
    compact_sstables()

This shows how data is written to memory, flushed to disk when full, and then compacted.

Analysis Table

Step	Action	MemTable State	Disk SSTables	Notes
1	Write data1	data1	empty	MemTable stores data1
2	Write data2	data1, data2	empty	MemTable stores data2
3	MemTable full check	data1, data2	empty	MemTable not full yet
4	Write data3	data1, data2, data3	empty	MemTable stores data3
5	MemTable full check	data1, data2, data3	empty	MemTable full now
6	Flush MemTable	empty	SSTable1(data1, data2, data3)	Data moved to disk
7	Write data4	data4	SSTable1(data1, data2, data3)	New MemTable starts
8	Write data5	data4, data5	SSTable1(data1, data2, data3)	MemTable stores data5
9	MemTable full check	data4, data5	SSTable1(data1, data2, data3)	MemTable not full
10	Write data6	data4, data5, data6	SSTable1(data1, data2, data3)	MemTable stores data6
11	MemTable full check	data4, data5, data6	SSTable1(data1, data2, data3)	MemTable full again
12	Flush MemTable	empty	SSTable1(data1, data2, data3), SSTable2(data4, data5, data6)	Second flush to disk
13	Compaction	empty	SSTable_merged(data1..data6)	Merge SSTables for efficiency
14	Wait for next write	empty	SSTable_merged(data1..data6)	Ready for new writes

💡 Process repeats as new writes come in, keeping memory fast and disk organized.

State Tracker

Variable	Start	After Step 1	After Step 5	After Step 6	After Step 12	After Step 13	Final
MemTable	empty	data1	data1, data2, data3	empty	empty	empty	empty
Disk SSTables	empty	empty	empty	SSTable1(data1, data2, data3)	SSTable1(data1, data2, data3), SSTable2(data4, data5, data6)	SSTable_merged(data1..data6)	SSTable_merged(data1..data6)

Key Insights - 3 Insights

Why do writes go first to memory (MemTable) instead of directly to disk?

Writing to memory is much faster than disk. The execution_table shows steps 1-5 where data accumulates in MemTable before flushing, improving write speed.

What happens when the MemTable becomes full?

As seen in steps 5 and 11, once MemTable is full, it is flushed to disk as an SSTable. This prevents memory overflow and organizes data on disk.

Why is compaction needed after multiple SSTables are created?

Compaction merges multiple SSTables into one (step 13) to reduce disk reads and improve read performance by keeping data organized.

Visual Quiz - 3 Questions

Look at the execution_table at step 6. What is the state of the MemTable?

A Contains data4

B Empty

C Contains data1, data2, data3

D Contains data4, data5, data6

💡 Hint

Check the 'MemTable State' column at step 6 in the execution_table.

At which step does the first flush of MemTable to disk happen?

A Step 6

B Step 5

C Step 12

D Step 13

💡 Hint

Look for the action 'Flush MemTable' in the execution_table.

If the MemTable size limit was larger, how would the execution_table change?

A Compaction would not be needed

B Flush steps would happen earlier with less data

C Flush steps would happen later with more data in MemTable

D MemTable would never flush

💡 Hint

Consider how MemTable fullness triggers flush in steps 5 and 11.

Concept Snapshot

LSM trees handle many writes by first storing data in fast memory (MemTable).
When full, MemTable is flushed to disk as sorted files (SSTables).
Multiple SSTables are merged (compacted) to keep reads efficient.
This design optimizes write speed and manages disk storage well.

Full Transcript

LSM trees are designed for systems with many writes. When data is written, it first goes into an in-memory structure called MemTable. This is fast and efficient. When the MemTable fills up, it is saved to disk as a sorted file called an SSTable. Over time, many SSTables accumulate, so the system merges them in a process called compaction. This keeps the disk organized and makes reading data faster. The process then repeats for new writes, balancing fast memory writes and efficient disk storage.

Practice

1. What is the main advantage of using an LSM tree in write-heavy systems?

easy

A. It speeds up write operations by batching writes in memory before saving to disk

B. It stores all data only in memory for faster access

C. It uses random writes directly to disk for faster updates

D. It avoids any data merging to keep files separate

Solution

1. Step 1: Understand LSM tree write process

   LSM trees first write data to a fast in-memory structure to avoid slow disk writes immediately.

2. Step 2: Explain batching and disk saving

   Data is later saved to disk in sorted files in batches, which improves write speed overall.

3. Final Answer:

   It speeds up write operations by batching writes in memory before saving to disk -> Option A

4. Quick Check:

   Write speed improved by memory batching [OK]

Hint: LSM trees use memory first, then batch writes to disk [OK]

Common Mistakes:

• Thinking LSM trees store all data only in memory
• Assuming LSM trees write directly to disk randomly
• Believing LSM trees never merge files

2. Which of the following correctly describes the structure of an LSM tree?

easy

A. A single sorted file on disk with no in-memory component

B. Multiple sorted files on disk plus a memory table for new writes

C. A hash table stored entirely in memory

D. A balanced binary search tree stored only on disk

Solution

1. Step 1: Recall LSM tree components

   LSM trees have a memory table (memtable) for fast writes and multiple sorted files (SSTables) on disk.

2. Step 2: Match options to structure

   Only Multiple sorted files on disk plus a memory table for new writes describes both memory and disk components correctly.

3. Final Answer:

   Multiple sorted files on disk plus a memory table for new writes -> Option B

4. Quick Check:

   Memory + sorted disk files [OK]

Hint: LSM trees combine memory table and sorted disk files [OK]

Common Mistakes:

• Confusing LSM trees with pure in-memory structures
• Thinking LSM trees use only one file on disk
• Mixing LSM trees with hash tables

3. Consider an LSM tree system where writes are very frequent. What happens during the compaction process?

medium

A. New data is discarded to keep files small

B. Memory table is cleared without saving to disk

C. Multiple sorted files are merged to reduce read overhead

D. Data is randomly shuffled to balance disk usage

Solution

1. Step 1: Understand compaction purpose

   Compaction merges multiple sorted files on disk to reduce the number of files and improve read speed.

2. Step 2: Analyze options

   Only Multiple sorted files are merged to reduce read overhead correctly describes merging files to reduce read overhead.

3. Final Answer:

   Multiple sorted files are merged to reduce read overhead -> Option C

4. Quick Check:

   Compaction merges files [OK]

Hint: Compaction merges files to speed up reads [OK]

Common Mistakes:

• Thinking compaction discards new data
• Believing compaction shuffles data randomly
• Assuming memory table is cleared without saving

4. A developer notices that their LSM tree system is slowing down reads over time. Which issue is most likely causing this?

medium

A. The memory table is too large and never flushed

B. The system uses a balanced tree instead of LSM

C. Writes are too slow due to frequent disk flushes

D. Compaction is not running, causing many small files to accumulate

Solution

1. Step 1: Identify cause of slow reads

   Many small files increase read overhead because the system must check multiple files for data.

2. Step 2: Link to compaction role

   If compaction is not running, files accumulate without merging, causing slow reads.

3. Final Answer:

   Compaction is not running, causing many small files to accumulate -> Option D

4. Quick Check:

   Missing compaction causes slow reads [OK]

Hint: No compaction means many files, slowing reads [OK]

Common Mistakes:

• Blaming memory table size for slow reads
• Confusing slow writes with slow reads
• Thinking balanced trees cause this issue

5. In a write-heavy system using LSM trees, which strategy best balances write speed and read efficiency as data grows?

hard

A. Increase memory table size and run compaction frequently

B. Keep memory table small and avoid compaction to save CPU

C. Write directly to disk without memory buffering

D. Use only one large sorted file on disk

Solution

1. Step 1: Consider memory table size impact

   Larger memory tables allow more writes to be batched, improving write speed.

2. Step 2: Understand compaction frequency

   Frequent compaction merges files, reducing read overhead and improving read efficiency.

3. Step 3: Evaluate options

   Increase memory table size and run compaction frequently combines both strategies to balance write speed and read performance effectively.

4. Final Answer:

   Increase memory table size and run compaction frequently -> Option A

5. Quick Check:

   Big memtable + frequent compaction = balanced speed [OK]

Hint: Big memtable + frequent compaction balances speed [OK]

Common Mistakes:

• Avoiding compaction to save CPU hurts reads
• Keeping memory table too small slows writes
• Writing directly to disk slows writes drastically