Chapter 3: Design Data Intensive Application

Storage and Retrieval

On the most fundamental level, we use database for two things

1. To store data
2. To retrieve data

As an application developer, we should know how database handles storage and retrieval internally.

We are not going to implement your own storage engine from scratch, but you need to select a storage engine that is appropriate for your applicaiton, from the many that are available. In order to tune a storage engine to perform well on your kind of workload, you need to have a rough idea of what the storage engine is doing under the hood.

There is a big difference between storage engines that are optimized for transactional workloads and those that are optimized for analytics

There are two families of storage engines

1. Log-structured storage engines
2. Page-oriented storage engines

Data Structures that Power your Database

Lets talk about simple database

#!/bin/bash

db_set() {
  echo "$1,$2" >> database
}

db_get() {
  grep ^$1," database | sed -e "s/^$1.//" | tail -n 1
}

using bash we have implemented simple database.

How it works:

$ db_set 12345 '{"name":"uday", "state":"Telangana"}

$ db_get 42

there can be duplicates keys in above database, so if you add new data with same key, it will be added at the bottom of the log, so that is the reason we added “tail -n 1” to get the new data with key

The above database has pretty good performance. Write operation takes O(1), but the real problem is when we read, which takes O(n), so if our data doubles, the time to get the data is also doubles.

Also forgot to mention, our this simple database does not handle concurrency, reclaiming disc space, durability, handling errors).

As discussed our writes are slow, in regular databases they have functionality called indexes. Indexes helps to improve our read speed, but the problem is it adds write overhead. So, it is our responsibility to choose which whether we need indexes or not, if needed how many indexes are needed. We have to make a tradeoff between read and write efficiency by using our knowledge based on requirements.

Hash Indexes

Assume our database is key-value database. We will store these key & value in a file. For every key we store in a file, we will keep an in-memory hashmap, Where every key in the hashmap is mapped to the byte offset in the datafile. Whenever you append or update the data you will also update the hashmap accordingly. This method is used in a database called Bitcask.

Bitcask offers high-performance reads and writes, subject to the requirement that all the keys fit in the available, RAM, since the hash map is kept completely in memory. The values can use more space than there is available RAM memory, since they can be loaded from disk with just one disk seek.

A storage engine like Bitcask is well suited to situations where they value of each key is updated frequently. For example, the key might be the URL of a cat video, and the value might be the number of times it has been played. In this kind of workload, there are a lot of writes, but there are not too many distinct keys — you have a large number of writes per key, but it’s feasible to keep all the keys in memory.

But did you observe one problem here? We are only appending to the file, eventually we might even end up consuming the disk space.

The solution could be, we will break files into segments. And perform compaction eventually. Compaction means throwing away the duplicate keys in logs and keeping the most recent update for each key.

So, when we compact, segments size decreases, so we merge them together. But in datbase we cannot update the data, so we will write the merge in new file segment. This will run in background process. Till this background copying is not completed, our database still points to the segments. Once complete copying is done, we will point it to the latest segments & delete the old ones.

Each segment has its own in memory hash table, If we want to find the value of a key, we first check the hash map of most recent segment, if it is not found, then we go for the next recent hash table and so on.

Lot of details goes into making this simple idea work in practice. Briefly, some of the issues that are important in a real implementation are:

1. File format: CSV is not the best format for a log. It’s faster and simpler to use a binary format that first encodes the length of a string in bytes, followed by the raw string
2. Deleting records: If we want to delete a key & its value, We have to append a special deletion record to the datafile. When log segments are merged, the tombstone tells the merging process to discard any previous values for the deleted key.
3. Crash recovery: If we restart our database the entire in-memory hash tables are gone. To get them again, we have to go through all the segments again & create each hash table for each segment again. But Bitcask speeds up recovery by storing a snapshot of each segment’s hash map on disk, which can be loaded into memory more quickly.
4. Partially written records: The database may crash at any time, including halfway through appending a record to the log. Bitcask files include checksums, allowing such corrupted parts of the log to be detected and ignored.
5. Concurrency control: Single thread to write, multiple threads to read

But But But… why don’t we update value rather than appending ?

1. Append only logs don’t need random access to disk, they need sequential access. Especially when we use magnetic tapes, random access slows down the write operation.
2. Concurrency & crash recovery are much simpler if segment files are append only. We are not left with part of value new & part of the value old sliced together.
3. Merging old segments avoids the problem of data files getting fragmented over time.

However, the hash table index also has limitations:

1. The hash table must fit in memory. So if you have many keys that does not fit in RAM, you are out of luck. In theory you can store hash table in disk, but random access requests to disk reduces its performance.
2. Range queries are not efficient. For example: to get all keys with name 1 to 1000, we have to use hash table for each key.

For B-Trees & LSM trees -> Watch Jordan has no life videos, he explained better

Comparing B-Trees and LSM-Trees:

As a rule of thumb, LSM-trees are faster for writes, B-trees are faster for reads. Reads are slower in LSM because they have to check several different data structures and SSTables at different stages of compaction.

Advantages of LSM-trees:

LSM-trees can be compressed better, and thus often produce smaller files on disk than B-trees. B-trees storage engine leave some disk space unused due to fragmentation.

Downsides of LSM-trees:

Downside of Log structured storage is that the compaction process can sometimes interfere with the performance of ongoing reads and writes.