The Ingenuity of LSM Trees
Elegance is not the abundance of detail, but the absence of the superfluous ~Dieter Rams
There is something very elegant about the design of LSM Trees.
Well there are actually many things involved in it like Memtables, SSTables, WALs, compaction and may others, but let us not worry much and go with them easily one by one. By the end of this we can talk about LSM Trees more properly.
LSM Trees are very elegant and beautiful when we deal with them they are very useful and solve very difficult issues.
To put it very clearly LSM Trees dont eliminate the cost of storing data. They simply find a better place to pay for it.
So what led to the idea of LSM Trees ? Well the initial idea that led to it was random writes. Wait what are Random writes ?
So now let us first discuss about random writes. Random writes are storage operations where data is written to scatter locations rather than being written in a continuous sequence.
The Problem with Random writes
So the definition of random writes might make us understand why random writes are an issue but let us talk about it more.
So think if an user updates multiple data in the database and now if the data base stores everything directly on disk and the updates may be in different locations. Which will make the database perform many different scattered writes. So this is manageable what is the issue even ? Well there are much more operations happening in the database the scattered writes are not just one or two it is many many may be even billions.
And the main issue or the thing we know about scattered writes is that Random operations are always more costly than sequential operations.
This is where for heavy write based databases where constantly modifying the data and writing them sequentially the idea of LSM Trees came.
But wait this is understandable but can we not just instead of doing this sequential thing we can just keep the writes in memory. Well this is interesting and actually a very good thing to think about in this case. So why dont we just do this?
The thing is writes can accumulate in the memory and as we talked about it that we do not want our database to perform random disk writes we can just append the write to a sequential log and keep the latest state in memory, which is called Memtable.
Memtable
So what is a memtable? A memtable is a structure that holds recents writes.
What it mainly does is it takes the writes quickly without immediately organizing them on disk.
Then this solves the issue right ? Well no it does a very good job as it accepts writes without repeatedly modifying random locations but eventually the memtable becomes full.
Which leads us to another very beautiful idea of SSTables.
SSTables
Get Sankalp’s stories in your inbox
Join Medium for free to get updates from this writer.
So memtable after reaching a certain seze is flushed to a disk by the database but the records does not go to the disk. The data is written in sorted order in a file called SSTables wihch are also immutable.
So the very useful feature of SSTables are actually its immutability. After writting once we dont have to go back and modify individual records inside it. We can just create more SSTables with more writes.
So before talking about other topics here let us talk about immutability and why is it so very useful for LSM Trees.
So write becomes very simple now but the read has now much more work to do as the database now need to check the newest structures first.
If there is no key there then the older structures are also searched. So now the difficulty for the database has gone to read.
Every write has more data , there are multiple same keys in SSTables, reads have to search multiple files. So there are issues with it which leads us to another very useful idea Compaction.
Compaction
So what does Compaction do ? It takes multiple SSTables and merges their contents and gives a much more organized SSTable. So the modification is properly done in a single SSTable now.
But with larger systems compaction also needs structure.
Now we are finally going to discuss about LSM Trees
But the important thing to be talked about LSM Trees before hand is that LSM Trees dont make costs disappear they move costs around.
LSM Trees
Suppose there is a very expensive operation going on we have many things to consider like we have to make it faster, do it less often, move it somewhere cheaper.
LSM Trees use all those ideas. The random writes now become sequential writes. Immediate organization now becomes compaction.
How does write happen in LSM Trees
So first the write request goes to the memtable as it is very fast but because of storage issues it moves to disk from where it goes to SSTables but before going to SSTables from the memtables it also goes to the WALs.
LSM Trees thinks when should this work be done and what is the cheapest way to do it?
Now ingenuity of LSM Trees
The thing about LSM Trees or the beauty of them is not that they are very simple. Infact the complete system can be very difficult.
The beauty of it is in the sequence of its ideas.
The ingenuity lies in how all those ideas fit together.
Thank you, hope you had a good read 😊.
