All
Fav

Basics

Non-functional Requirements

Stateless Services

Resource Estimation

API Design

Data Structures Behind Databases

Storage

Data Replication

Data Partitioning

Caching

Dataflow

Message Queue

Batch Processing

Stream Processing

Patterns

Template

Data Structures Behind Databases

Note that this section is optional and provides an in-depth exploration of the data structures utilized in the construction of modern databases. It is not mandatory to possess this level of knowledge in order to solve system design questions. However, acquiring an understanding of these concepts will enhance your appreciation of various technologies and facilitate your comprehension of their documentations and learning new technologies.

Understanding the storage engine, the underlying technology that powers databases, may seem like an endeavor meant only for database developers. However, as a software engineer or a system designer, knowing these intricacies has significant benefits and often gives you a greater appreciation of the technology. It'll help you with:

  1. Database Selection: A wide variety of databases are available in the market, each catering to different needs and use-cases. Understanding the fundamental principles of how these databases store, retrieve, and manage data can help you make an informed decision when selecting a database for your specific needs. For instance, if your application requires heavy write operations, you might opt for a database that uses Log-Structured Merge (LSM) trees, which are optimized for write operations.
  2. Performance Tuning: Databases offer a myriad of configuration options that can significantly impact their performance. Having a solid understanding of the underlying storage engine can guide you in tuning these settings for optimal performance. For instance, understanding the principles of B-Trees and how they affect read and write operations can help you optimize the page size or the fill factor of your database.

In the following sections, we will build a database from scratch (!) and cover the most important data structures powering your databases: hash index, SSTable, LSM tree, and B-tree.

Sequential Writes vs Random Writes

First of all, I want to stress one key point when we discuss in storage design: Sequential writes are generally faster than random writes due to several factors. In hard disk drives (HDDs), sequential writes minimize the need for the read/write head to move, reducing seek time and rotational latency. For solid-state drives (SSDs), sequential writes allow for more efficient wear leveling and are easier to optimize, as they do not require the frequent changing of write locations that random writes do. File systems are also optimized for sequential writes, allowing for contiguous storage allocation and reducing fragmentation. Additionally, caching and buffering mechanisms are more effective with predictable sequential write patterns, enabling faster data processing. Lastly, storage controllers are designed to handle sequential data flows more efficiently than random ones, further enhancing performance.

The differential performance characteristics between sequential and random writes have significant implications for database design.

Building a database from scratch

Simply speaking, a database stores data, either on the disk or in memory. You can implement a simple key-value database in a few lines of bash scripting.

#!/bin/bash

DB_DIR="$HOME/db"

# Check if the database directory exists, and if not, create it
if [ ! -d "$DB_DIR" ]; then
  mkdir "$DB_DIR"
fi

# Function to set a key-value pair
set_key() {
  key=$1
  value=$2
  # Check if the key already exists, and if so, overwrite the value
  echo "$value" > "$DB_DIR/$key"
}

# Function to get the value for a key
get_value() {
  key=$1
  # Check if the key exists, and if not, return an error message
  if [ ! -f "$DB_DIR/$key" ]; then
    echo "Error: Key $key does not exist"
    return 1
  fi
  cat "$DB_DIR/$key"
}

# Function to delete a key-value pair
delete_key() {
  key=$1
  # Check if the key exists, and if not, return an error message
  if [ ! -f "$DB_DIR/$key" ]; then
    echo "Error: Key $key does not exist"
    return 1
  fi
  rm "$DB_DIR/$key"
}

This creates a directory called db. For each key value pair, it writes a file in the directory with file name being the key and content being the value. To look up a key, it scans the directory for a file whose name is the same as the key.

Example commands to use it:

# Set a key-value pair
./db.sh set_key key1 value1

# Get the value for a key
./db.sh get_value key1

# Delete a key-value pair
./db.sh delete_key key1

This is neither efficient nor elegant but it offers a view of how a database fundamentally works: we serialize the data into a storage media and retrieve it afterward. The devil is in the details of how to serialize, where to store it, and how to read it back so it's most efficient.

←
↑TA 👨‍🏫