No. 02Storage
Memtable
The inbox before the filing cabinet.
Published
A database usually doesn't rewrite a sorted disk file every time you change one key. That would turn a small update into an enthusiastic amount of work.
Try it: fill the memtable, then flush it
Write three keys, then move a full memory table to an SSTable.
Write-ahead log
- c=3
- a=1
- b=2
Active memtable
- (empty)
Frozen memtable
- a=1
- b=2
- c=3
SST on disk
- (none)
Next writed=4
Three records filled the toy table, so it froze. It is read-only now, but still in memory: frozen is not flushed.
Write-ahead log
- c=3
- a=1
- b=2
- d=4
Active memtable
- d=4
Frozen memtable
- a=1
- b=2
- c=3
SST on disk
- (none)
Next writeAll four writes done
The write went to the log and the active table, which keeps keys sorted however they arrive.
Write-ahead log
- d=4
Active memtable
- d=4
Frozen memtable
- (none)
SST on disk
- SST 1: a=1, b=2, c=3
Next writeAll four writes done
Flush wrote the frozen table as a sorted SST. Its log records are no longer needed for recovery.
Three-record capacity is a toy. Crash recovery replays the log; that is a separate story.
Why?
Freezing swaps in a fresh table so writes never wait for disk. Flushing happens afterwards, in the background. Until it finishes, the log is what makes the frozen records survive a crash.
A memtable holds recent writes in memory. In our little example, writing c, a, then b gives us a sorted view of a, b, c. When this table reaches its limit, it becomes read-only. New writes enter a fresh table while the old contents are flushed into an SSTable: a sorted file on disk.
Try filling the memory table, then writing one more key before flushing the old one. Freezing and flushing are two different events.
The important catch: RAM is fast, but it has a short memory. Literally. A write-ahead log can provide recovery; putting something in a memtable alone does not make it durable. And a memtable is a job, not a requirement to use one particular data structure.