A Data Mesh from Scratch in Rust — Part 3— MemTable
If you missed my ramblings in Part 1 and the definition of events and actions in this store in Part 2, I strongly encourage you look up my motivation there. Anyhow, in this part, I am going to explain how I built the MemTable.
My first thought was a Red Black Tree (RBT). It strikes a nice balance between the extreme rebalancing of a completely balanced tree (AVL) versus guaranteeing roughly a O(lg n) search time. I spent quite a bit of time with blogs and YouTube videos to understand the RBT. Turns out, the trouble is not the understanding part but the implementation. Some of the tutorials that helped (unfortunately I did not keep track of some of the amazing YouTube videos) are here, here and here. And you can find my implementation here.
However, at the end of the day, I was not confident of my implementation of the Red Black Tree. Plus I realized that an ordered skiplist lets me reuse the structure as I go to the write-ahead log and the SSTable (Sorted String Table?). Life would just be easier. Anyway, I had by now lost the enthusiasm to implement my own data structure. Thankfully, there was this in the Rust crates.
So now my MemTable looks like this (the implementation is here):
The OrderedSkipList does not seem to support a key-value pair. So I put the event IDs into it, which are now going to be sorted. And then the actual events are in a hashmap for ease of access.
Again, there is not much special going on with the insert , get and so on. Please look up the code if you are interested. However, the Iterator for the MemTable , I found interesting.
The generic idea in implementing an Iterator for your structure is to define a secondary structure:
In this case, we are implementing an Iterator for a reference to a MemTable . The second step is to implement the Iterator trait for the secondary struct .
Now since we already held an Iterator to the MemTable skiplist and a reference to the MemTable , this was really easy. We simply had to look up the next element on the skiplist and pull it out of the hashmap. Frankly, I wouldn’t be able to do this any other way.
Note that the MemTableIterator generates a sorted (by event id) stream of events.
Then implement the IntoIter for the reference to the MemTable . Remember that this implements the into_iter() method for MemTable which consumes the MemTable . You can also implement, fn iter() in impl MemTable to get the reference based iterator. I have not done this for MemTable , yet.
And that is pretty much the crux of the MemTable . You are welcome to look up the rest of the code.
Next time, we will talk about implementing the SSTable in this series.
