DDIA - Chapter 3 - Storage and Retrieval (till LSM-tree) - thoughts and notes

Spoiler Alert - eheheh - just kidding!

So databases need to do 2 things perfectly, store things and then retrieve them, now all the difference is how fast a database can do this and how efficiently.

Okay, there is something called log, which is an append-only data file. So lets say we store our data here, but how do we fetch it efficiently without performing a full log file search? We use an additional data structure called the index. Indexes speed up reads but slow down writes - so choose what to index carefully.

Log + index = database! Yay.

A hash map is a data structure used for indexing. (key, value)

The book then talks about bitcask which is basically the above thing. This is a summary so I am not going to go into a lot of details, hash tables might not be always suitable as you have to have data that can fit in RAM, and range queries are inefficient.

The book talks about compaction and segmenting data for an append only data database to store it on the disk.

A more efficient approach here can be of SSTables and LSM tree.

SSTable is Sorted String Table. We here require that the key, value pair be sorted by key. This has multiple advantages.

• Merging segments is easier as keys are sorted.

• No need to keep an index of all the keys in memory.

• Easy to group and compress blocks to write to the disk.

Now the question arises, how do we sort the data as it hits our storage engine? We can use red-black trees or AVL trees.

We can now change our storage engine work as follows:

• When a write comes in, add it to an in-memory balanced tree data structure. This in-memory tree is sometimes called a memtable.

• When the memtable gets bigger than some threshold, we write it out to disk as an SSTable file.

• In order to serve a read request, first try to find the key in the memtable → then in the most recent on-disk segment → then in the next-older segment so on and so forth.

• From time to time, we run a merging and compaction process in the background to combine segment files and to discard overwritten or deleted values.

And voila, we have a fairly good database engine and now we can do Saas sales.

The above approach is often termed as LSM-tree - Log Structure Merge Trees. If a key doesn't exist in our db then this approach has a difficult time confirming so, to optimise for this we use bloomfilters.

I am stopping here because this chapter has a lot to unpack. We are going to talk about B-tree, OLTP, OLAP, other indexing ways in the next blog.

Tata, Ciao!