The building blocks for the in-memory components (memtables) and for the disk components (SSTables) are ready. The only thing left to do now is to flush the former into the latter.

Flushing requires the following steps:

1. Select the oldest memtable
2. Iterate over all the records it contains (in order!)
3. Write them one by one into the new SSTable
4. Add the SSTable file to the list of files referenced by the LSM engine
5. Remove the flushed memtable to the list of memtables to parse.

So far, this is pretty straightforward and the code should be pretty simple if we stopped there.

However, one more subtle thing to think about is: how to handle concurrency? As described in a previous post, we have a mutex lock and a read-write lock available. So far, I called my mutex lock the freeze_lock and used it only for freeze operations. When doing the flush, I extended its use to both freezing and flushing. Why do that? Mostly to keep things simple: this will allow to either freeze or flush one memtable, but not both. A priori, freezing should not interfere with flushing because freezing converts a mutable memtable into an immutable one whereas flushing converts an immutable one into an SSTable. Since the input objects are not the same, there should not be any interference (or at least I don’t see any), but these two operations are logically ordered one after the other, which is why I am ensuring they are actually serialized (even though this will definitely create performance issues).

The read-write lock remains the lock associating to reading and writing to the state. So, to read the content of the memtable, we need to acquire the read lock, and to update the state (steps 4 and 5), we need to acquire the write lock.

Given all these considerations, here is what the implementation looks like:

def flush_next_immutable_memtable(self) -> None:
    with self._freeze_lock:
        # Read the oldest memtable
        with self._state_lock.read():
            memtable_to_flush = self.immutable_memtables[-1]

        # Flush it to SSTable
        path = self.compute_path()
        sstable_builder = SSTableBuilder(sstable_size=self._max_sstable_size, 
                                         block_size=self._block_size)
        for record in memtable_to_flush:
            sstable_builder.add(key=record.key, value=record.value)
        sstable = sstable_builder.build()
        sstable.write(path)

        # Update state to remove oldest memtable and add new SSTable
        with self._state_lock.write():
            self.immutable_memtables.pop()
            self.ss_tables_paths.append(path)

And with this, we are now able to flush memtables into SSTables! 🎉