# Day 28/100

# Designing Data-Intensive Applications [Book Highlights]
### [Part I : Chapter III] Storage and Retrieval

#### SSTables and LSM-Trees
- Sorted String Table, or SSTable for short, requires that each key only appears once within each merged segment file
- Merging segments is simple and efficient, even if the files are bigger than the
available memory.
- like in the mergesort algorithm, you start reading the input files side by side, look at the first key in each file, copy the lowest key to the output file, and repeat.


![image.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1650217015342/A9lufd-N3.png)
Merging several SSTable segments, retaining only the most recent value
for each key.

- When multiple segments contain the same key, we can keep the value from the most recent segment and discard the values in older segments
- To search any key we need a sparse in-memory index to tell you the offsets for some of the keys, may be not all.
- one key for every few kilobytes of segment file is sufficient, because a few kilobytes can be scanned very quickly
- read requests need to scan over several key-value pairs, we can group those records into a block and compress it before writing it to disk
- Each entry of the sparse in-memory index then points at the start of a compressed block
- save's disk space as well as reduces the I/O bandwidth use.

#### Constructing and maintaining SSTables
- When a write comes in, add it to an in-memory balanced tree data structure (for example, a red-black tree). This in-memory tree is sometimes called a memtable.
- When the memtable gets bigger than some threshold—typically a few megabytes write it out to disk as an SSTable file.
- The new SSTable file becomes the most recent segment of the database
- on 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, etc.
- From time to time, run a merging and compaction process in the background to combine segment files and to discard overwritten or deleted values.
- It only suffers from one problem: if the database crashes, the most recent writes are lost.
- to avoid that problem, we can keep a separate log on disk to which every write is immediately appended
- Every time the memtable is written out to an SSTable, the corresponding log can be discarded

#### Performance Improvements
- One more problem is you have to look a lot for a key that does not exists in the db before we can be sure that the key does not exist. In order to optimize this kind of access, storage engines often use additional [Bloom filters](https://rawdatareaders.hashnode.dev/day-25).
- In size-tiered compaction, newer and smaller SSTables are successively merged into older and larger SSTables.
- In leveled compaction, the key range is split up into smaller SSTables and older data is moved into separate “levels,” which allows the compaction to proceed more incrementally and use less disk space.
- the basic idea of LSM-trees—keeping a cascade of SSTables that are merged in the background—is simple and effective
- Since data is stored in sorted order, you can efficiently perform range queries
- the disk writes are sequential the LSM-tree can support remarkably high write throughput