Data Engineering & Databases

Question 1

What does a Database do?

Answer 1

Primarily 2 things: stores and retrieves data

Question 2

What are the 2 main philosophies for primary data storage

Answer 2

1. Log-structured

2. Update in place

Question 3

Log

Answer 3

An append only sequence of records

Question 4

Index

Answer 4

Additional metadata to help locate specific data

Question 5

SSTable

Answer 5

Sorted String Table

- A file in which data is sorted by key

Question 6

LSM-tree

Answer 6

Log-structured Merge Tree

Fundamental idea

• keep a cascade of SSTables that are merged in the background
• turns random writes into sequential writes

Question 7

What is the DB write path when using SSTable / LSM-tree

Answer 7

• Write to a memtable - in-memory balanced tree
• Also write to unsorted log for crash recovery
• When the memtable gets big enough (several MB) disk as SSTable file
• While SSTable is written, writes continue on new memtable
• Background merge & compaction to combine SSTable files

Question 8

What is the DB read path for a DB implemented with SSTables / LSM-trees

Answer 8

• Look for key in memtable
• Look in most recent disk segment
• Look in next older disk segment
• (Sped up by using Bloom filters to determine if it doesn’t exists, which are the most expensive reads)

Question 9

LSM-tree Compaction & Merge Strategies

Answer 9

Size-tiered - newer, smaller SSTables merged into older, larger SSTables
(HBase, supported by Cassandra, Scylla)

Levels - key range split into smaller SSTables, older data is moved into separate levels
(Used by LevelDB, RocksDB, supported by Cassandra, Scylla)

Question 10

B-Tree

Answer 10

Standard index implementation in almost all relational DBs (and many non-relational)

• Break DB into fixed-size pages (trad 4KB), and read/write one page at a time
• Each page contains keys and references to child pages (using on-disk “pointers”)
• 1st page is the root (search always begins here)
• Each child has a continuous range of keys, keys between the references indicate boundaries of those ranges
• Leaf pages contain individual keys and values inline (or in references pages)

Question 11

Branching factor

Answer 11

The number of references to child pages in one B-tree page

• Typical factor is several hundred
• Very large DBs can be stored with few levels (256 TB stored in 4 levels of 4KB w branching factor of 500)

Question 12

WAL

Answer 12

Write-ahead Log
- Append-only file where every B -tree modification is written before its written to the tree (in case of failure during hardware write, which could cause an orphan page with no parent)

Question 13

Writes/Reads for LSM-tree vs B-tree

Answer 13

LSM-tree typically faster for writes

B-tree typically fasters for reads