Database Storage Engine Internals — System Design Guide
In this tutorial, you'll learn about Database Storage Engine Internals. We cover key concepts, practical examples, and best practices.
A database storage engine manages how data is organized on disk, indexed, queried, and recovered after crashes — the foundation of every relational and NoSQL database.
What You'll Learn
You'll master database internals: B-tree and LSM-tree data structures, page layout, MVCC for concurrency, write-ahead logging (WAL), checkpointing, and buffer pool management.
Why This Problem Matters
Understanding storage engines helps you choose the right database (PostgreSQL vs MySQL vs RocksDB), tune query performance, and debug production issues. Every engineer working with data benefits from knowing what happens under the hood.
Real-World Use
Durga Antivirus Pro's signature database stores millions of malware hashes using an LSM-tree engine for high write throughput. DodaZIP's cloud sync service uses MVCC for conflict-free concurrent file versioning.
Storage Engine Architecture
flowchart TB
Client[Client Query] --> Parser[SQL Parser]
Parser --> Optimizer[Query Optimizer]
Optimizer --> Executor[Query Executor]
Executor --> Storage[Storage Engine]
subgraph StorageEngine
BP[Buffer Pool]
PageMgr[Page Manager]
WAL[Write-Ahead Log]
Check[Checkpointer]
MVCC[MVCC Visibility]
end
Storage --> BP
BP --> PageMgr
PageMgr --> Disk[(Disk Pages)]
WAL --> Disk
Check --> Disk
BP --> MVCC
Page Layout
Data is stored in fixed-size pages (typically 8KB or 16KB). Each page contains a header, slot array, and row data:
import struct
from typing import Optional
class Page:
HEADER_SIZE = 24 # page_id, free_start, free_end, slot_count
def __init__(self, page_id: int, page_size: int = 8192):
self.page_id = page_id
self.page_size = page_size
self.data = bytearray(page_size)
self.slots = []
self.free_pointer = page_size
def insert_record(self, record: bytes) -> int:
record_len = len(record) + 4 # length prefix
if self.free_pointer - self._header_end() < record_len:
raise MemoryError("Page full, need split")
self.free_pointer -= record_len
slot_id = len(self.slots)
self.slots.append(self.free_pointer)
struct.pack_into(">I", self.data, self.free_pointer, len(record))
self.data[self.free_pointer + 4:self.free_pointer + 4 + len(record)] = record
return slot_id
def get_record(self, slot_id: int) -> bytes:
offset = self.slots[slot_id]
rec_len = struct.unpack_from(">I", self.data, offset)[0]
return bytes(self.data[offset + 4:offset + 4 + rec_len])
def _header_end(self) -> int:
return self.HEADER_SIZE + (len(self.slots) * 4)
page = Page(page_id=1)
page.insert_record(b"Hello, World!")
page.insert_record(b"Database internals")
print(page.get_record(0))
print(page.get_record(1))
Expected output:
b'Hello, World!'
b'Database internals'
B-Tree Index
A B-tree maintains sorted keys with fanout to minimize disk seeks:
class BTreeNode:
def __init__(self, is_leaf: bool = True):
self.is_leaf = is_leaf
self.keys = []
self.values = [] if is_leaf else None
self.children = [] if not is_leaf else None
class BTree:
def __init__(self, order: int = 3):
self.order = order
self.root = BTreeNode()
def insert(self, key: int, value: str):
root = self.root
if len(root.keys) == 2 * self.order - 1:
new_root = BTreeNode(is_leaf=False)
new_root.children.append(root)
self._split_child(new_root, 0)
self.root = new_root
self._insert_non_full(self.root, key, value)
def _insert_non_full(self, node: BTreeNode, key: int, value: str):
if node.is_leaf:
i = len(node.keys) - 1
node.keys.append(None)
node.values.append(None)
while i >= 0 and key < node.keys[i]:
node.keys[i + 1] = node.keys[i]
node.values[i + 1] = node.values[i]
i -= 1
node.keys[i + 1] = key
node.values[i + 1] = value
else:
i = len(node.keys) - 1
while i >= 0 and key < node.keys[i]:
i -= 1
i += 1
if len(node.children[i].keys) == 2 * self.order - 1:
self._split_child(node, i)
if key > node.keys[i]:
i += 1
self._insert_non_full(node.children[i], key, value)
def search(self, key: int, node: BTreeNode = None) -> Optional[str]:
node = node or self.root
i = 0
while i < len(node.keys) and key > node.keys[i]:
i += 1
if i < len(node.keys) and key == node.keys[i]:
return node.values[i] if node.is_leaf else node.children[i]
if node.is_leaf:
return None
return self.search(key, node.children[i])
def _split_child(self, parent: BTreeNode, i: int):
mid = self.order - 1
child = parent.children[i]
new_child = BTreeNode(is_leaf=child.is_leaf)
new_child.keys = child.keys[mid + 1:]
new_child.values = child.values[mid + 1:] if child.is_leaf else None
new_child.children = child.children[mid + 1:] if not child.is_leaf else None
child.keys = child.keys[:mid]
child.values = child.values[:mid] if child.is_leaf else None
child.children = child.children[:mid + 1] if not child.is_leaf else None
parent.keys.insert(i, child.keys[mid])
parent.children.insert(i + 1, new_child)
btree = BTree(order=3)
btree.insert(10, "ten")
btree.insert(20, "twenty")
btree.insert(5, "five")
print(btree.search(10))
print(btree.search(15))
Expected output:
ten
None
Write-Ahead Log (WAL)
Every write goes to the WAL before the data page. This ensures durability without flushing pages on every transaction:
import os
import time
import struct
class WAL:
def __init__(self, path: str = "/tmp/wal.log"):
self.path = path
self.fd = open(path, "ab")
def log_insert(self, page_id: int, slot: int, data: bytes):
record = struct.pack(">BII", 1, page_id, slot) + data
self._write_record(record)
def log_checkpoint(self, lsn: int):
record = struct.pack(">BQ", 2, lsn)
self._write_record(record)
def _write_record(self, record: bytes):
length = len(record)
self.fd.write(struct.pack(">I", length))
self.fd.write(record)
self.fd.flush()
os.fsync(self.fd.fileno())
def replay(self, callback):
self.fd.close()
with open(self.path, "rb") as f:
while True:
header = f.read(4)
if not header:
break
length = struct.unpack(">I", header)[0]
record = f.read(length)
record_type = record[0]
if record_type == 1:
_, page_id, slot = struct.unpack(">BII", record[:9])
data = record[9:]
callback(page_id, slot, data)
def close(self):
self.fd.close()
MVCC (Multi-Version Concurrency Control)
MVCC keeps old versions of rows so readers don't block writers:
import time
import threading
class MVCCRecord:
def __init__(self, key: str, value: str, tx_id: int):
self.key = key
self.value = value
self.created_at = tx_id
self.deleted_at = None
class MVCCStore:
def __init__(self):
self.records = {}
self.lock = threading.Lock()
self.tx_counter = 0
def begin_transaction(self):
self.tx_counter += 1
return self.tx_counter
def put(self, key: str, value: str, tx_id: int):
with self.lock:
for rec in self.records.get(key, []):
rec.deleted_at = tx_id
if key not in self.records:
self.records[key] = []
self.records[key].append(MVCCRecord(key, value, tx_id))
def get(self, key: str, tx_id: int) -> str:
with self.lock:
for rec in reversed(self.records.get(key, [])):
if rec.created_at <= tx_id and \
(rec.deleted_at is None or rec.deleted_at > tx_id):
return rec.value
return None
def vacuum(self, oldest_active_tx: int):
with self.lock:
for key in list(self.records.keys()):
self.records[key] = [
r for r in self.records[key]
if r.deleted_at is None
or r.deleted_at >= oldest_active_tx
or r.created_at >= oldest_active_tx
]
if not self.records[key]:
del self.records[key]
store = MVCCStore()
tx1 = store.begin_transaction()
tx2 = store.begin_transaction()
store.put("name", "Alice", tx1)
store.put("name", "Bob", tx2)
print(store.get("name", tx1))
print(store.get("name", tx2))
Expected output:
Alice
Bob
LSM-Tree (Log-Structured Merge-Tree)
LSM-trees buffer writes in memory, then flush to immutable SSTables:
class SSTable:
def __init__(self, level: int, data: list):
self.level = level
self.data = sorted(data, key=lambda x: x[0])
def lookup(self, key: int) -> int:
for k, v in self.data:
if k == key:
return v
return None
class LSMTree:
def __init__(self):
self.memtable = {}
self.sstables = []
def put(self, key: int, value: int):
self.memtable[key] = value
if len(self.memtable) >= 3:
self._flush()
def _flush(self):
data = list(self.memtable.items())
self.sstables.append(SSTable(0, data))
self.memtable = {}
def get(self, key: int) -> int:
if key in self.memtable:
return self.memtable[key]
for table in reversed(self.sstables):
val = table.lookup(key)
if val is not None:
return val
return None
lsm = LSMTree()
lsm.put(1, 100)
lsm.put(2, 200)
lsm.put(3, 300)
print(lsm.get(2))
print(lsm.get(99))
Expected output:
200
None
Common Mistakes
1. Full Page Writes
Without the full page image in WAL, a torn page (partial write during crash) corrupts the database. Always log the full page image before modifying it.
2. No Buffer Pool Eviction Policy
Without LRU or Clock-sweep eviction, frequently accessed pages get evicted while cold pages remain. Implement a proper page replacement algorithm.
3. Ignoring the Doublewrite Buffer
InnoDB uses a doublewrite buffer to prevent partial page writes. Writing to a secondary location before the main location ensures atomic page writes.
4. B-Tree Page Split Storm
When many concurrent inserts hit the same leaf page, repeated splits cause contention. Use page-level locking or append-optimized B-tree variants.
5. Not Tuning Fill Factor
A B-tree with 100% fill factor requires splitting on every insert. Use 70-90% fill factor to leave room for future insertions.
6. Over-Flushing the WAL
Calling fsync after every single insert destroys throughput. Batch WAL flushes at transaction commit intervals (1-10ms).
7. No LSM Compaction Strategy
Without compaction, the number of SSTables grows unboundedly, slowing reads. Use size-tiered or leveled compaction to merge tables in the background.
Practice Questions
1. What is the difference between a B-tree and a B+tree?
A B+tree stores values only in leaf nodes and links leaf nodes for range scans. A B-tree stores values in all nodes. B+tree is more common in databases because range queries only scan leaf nodes.
2. Why does PostgreSQL use a B-tree while Cassandra uses an LSM-tree?
PostgreSQL is optimized for reads and point queries (OLTP). Cassandra is optimized for write-heavy workloads with sequential writes and compaction in the background.
3. What happens during database recovery after a crash?
The database reads the last checkpoint, then replays all WAL records after that checkpoint. Undo logs roll back transactions that were in progress but not committed. This is called ARIES recovery.
4. How does the buffer pool improve performance?
It caches frequently accessed pages in memory, avoiding expensive disk I/O. The hit ratio (cache hits / total reads) directly determines query performance. A warm buffer pool can achieve 99%+ hit rates.
5. Challenge: Design a time-travel query system.
Allow querying the database as of any past timestamp. Design a storage engine that retains historical versions and supports queries at any time point without storing full snapshots.
Mini Project: Simple Storage Engine
class SimpleStorageEngine:
def __init__(self):
self.pages = {}
self.next_page = 0
self.next_record = 0
def insert(self, data: dict) -> int:
page_id = self.next_page // 100
if page_id not in self.pages:
self.pages[page_id] = Page(page_id)
record_bytes = str(data).encode()
slot = self.pages[page_id].insert_record(record_bytes)
rid = self.next_record
self.next_record += 1
return rid
def read(self, rid: int) -> dict:
page_id = rid // 100
slot = rid % 100
data = self.pages[page_id].get_record(slot)
return eval(data.decode())
engine = SimpleStorageEngine()
rid1 = engine.insert({"user": "Alice", "score": 42})
rid2 = engine.insert({"user": "Bob", "score": 99})
print(engine.read(rid1))
print(engine.read(rid2))
Expected output:
{'user': 'Alice', 'score': 42}
{'user': 'Bob', 'score': 99}
FAQ
What's Next
Congratulations on completing this database internals design! Here's where to go from here:
- Practice daily — Implement a B-tree from scratch
- Build a project — Build a toy database with WAL and MVCC
- Explore related topics — LSM compaction strategies, ARIES recovery, index-organized tables
- Join the community — Share your storage engine experiments and get feedback
Remember: every expert was once a beginner. Keep building!
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro