RC: W11 D2 — Storing and retrieving historical versions in memtables

April 23, 2024

So far, my engine was able to store only one version of each record. The goal for this week is to be able to store multiple versions for each record (identified by their sequence number) and retrieve one particular historical version when needed. Therefore, both the memtables and the SSTables should be re-designed to handle multiple versions. Today, I handled the modifications on the memtables. I will handle those on the SSTable tomorrow.

Since, in my implementation, a memtable is a wrapper around a red-black tree, I need the red-black tree to be able to store multiple versions. So far, the nodes of my red-black tree were identified with the key, and stored the encoded record as value. If a new version (i.e. a record with the same key) was inserted, the value was simply replaced by the new one and thus, each node always contained only one single record.

My first task today was to change that: instead of storing a single value for each key, I modified the nodes’ structure so that they could store multiple values (i.e. multiple versions). I stored them in an array and every time a new value comes in, it is appended at the end. Therefore, if I want to read records from newest to oldest (as all my iterators do so far), I need to read the array in reverse order. Also, since records (and specifically sequence numbers) are encoded in such a way that they will always be sorted from newest to oldest, I could store them in a sorted way (this is not necessary for now, but it might come in handy later).

Iterating on the red-black does not change: I iterate over all nodes in order. The only difference though is that the data is now a list of record versions instead of a single record. Therefore, I needed to update the memtable to handle this change. As a first step, I decided to not add snapshots, and just have everything work with the new structure. So basically, the memtable needs to select the most recent version when there are multiple ones. Since new versions are inserted at the end, I only need to take the last one, and that’s the only change I needed for the get method.

For the scan method though, things are a little trickier. To scan, I use an iterator (the MemtableIterator) which, so far, read all records in order to iterate. The MemtableIterator was used at two places:

• When scanning the memtable (scan method): in that case, only one version of each record should be outputted (the most recent one stored in the memtable);
• When flushing the memtable to disk (flush method): in that case, all versions need to be written to the SSTable (so that historical versions can later be accessed).

Therefore, the iterator should either yield all versions or only one single version (the latest) depending on its use. I thus decided to define two iterators for to distinguish the two use cases (FlushMemtableIterator and ScanMemtableIterator). Both inherit from the main one (MemtableIterator): FlushMemtableIterator yields all versions, and ScanMemtableIterator yields only the latest one.

With all of this, I should be done with all the modifications on the memtable. Tomorrow, I’ll focus on updating the SSTable.