Database Internals

The roadmap

Database Internals · 1 of 91 sections studied

Study any section by name, in any order. Not authored yet? Generate it with author. · Read all lessons on one page →

1 Introduction and Overview

DBMS Architecture / Memory- Versus Disk-Based DBMSstudying
pages 21–24 · 0/14 facts mastered ·
Durability in Memory-Based Stores / Column- Versus Row-Oriented DBMS / Row-Oriented Data Layoutyou are here
pages 24–27 · 13 questions ·
·
Column-Oriented Data Layout / Distinctions and Optimizations / Wide Column Storesready
pages 27–30 · 13 questions ·
·
Data Files and Index Files / Data Files / Index Filesready
pages 30–33 · 14 questions ·
·
Primary Index as an Indirection / Buffering, Immutability, and Orderingready
pages 33–36 · 13 questions ·
·
Summaryready
pages 36–38 · 7 questions ·
·

2 B-Tree Basics

Binary Search Trees / Tree Balancing / Trees for Disk-Based Storagenot authored
pages 38–42 ·
·
Disk-Based Structures / Hard Disk Drives / Solid State Drives / On-Disk Structuresnot authored
pages 42–46 ·
·
Ubiquitous B-Trees / B-Tree Hierarchynot authored
pages 46–49 ·
·
Separator Keys / B-Tree Lookup Complexity / B-Tree Lookup Algorithmnot authored
pages 49–51 ·
·
Counting Keys / B-Tree Node Splitsnot authored
pages 51–54 ·
·
B-Tree Node Merges / Summarynot authored
pages 54–58 ·
·

3 File Formats

Motivation / Binary Encoding / Primitive Typesnot authored
pages 58–61 ·
·
Strings and Variable-Size Data / Bit-Packed Data: Booleans, Enums, and Flags / General Principlesnot authored
pages 61–65 ·
·
Page Structure / Slotted Pages / Cell Layoutnot authored
pages 65–69 ·
·
Combining Cells into Slotted Pages / Managing Variable-Size Data / Versioningnot authored
pages 69–72 ·
·
Checksumming / Summarynot authored
pages 72–75 ·
·

4 Implementing B-Trees

Page Header / Magic Numbers / Sibling Links / Rightmost Pointers / Node High Keysnot authored
pages 75–79 ·
·
Overflow Pages / Binary Searchnot authored
pages 79–81 ·
·
Binary Search with Indirection Pointers / Propagating Splits and Merges / Breadcrumbs / Rebalancingnot authored
pages 81–85 ·
·
Right-Only Appends / Bulk Loading / Compressionnot authored
pages 85–88 ·
·
Vacuum and Maintenance / Fragmentation Caused by Updates and Deletes / Page Defragmentation / Summarynot authored
pages 88–93 ·
·

5 Transaction Processing and Recovery

Buffer Management / Caching Semanticsnot authored
pages 94–98 ·
·
Cache Eviction / Locking Pages in Cache / Page Replacementnot authored
pages 98–103 ·
·
Recovery / Log Semanticsnot authored
pages 103–106 ·
·
Operation Versus Data Log / Steal and Force Policies / ARIESnot authored
pages 106–109 ·
·
Concurrency Control / Serializability / Transaction Isolation / Read and Write Anomaliesnot authored
pages 109–112 ·
·
Isolation Levels / Optimistic Concurrency Controlnot authored
pages 112–115 ·
·
Multiversion Concurrency Control / Pessimistic Concurrency Control / Lock-Based Concurrency Control (1)not authored
pages 115–125 ·
·
Multiversion Concurrency Control / Pessimistic Concurrency Control / Lock-Based Concurrency Control (2)not authored
pages 115–125 ·
·
Summarynot authored
pages 125–128 ·
·

6 B-Tree Variants

Copy-on-Write / Implementing Copy-on-Write: LMDB / Abstracting Node Updatesnot authored
pages 128–131 ·
·
Lazy B-Trees / WiredTiger / Lazy-Adaptive Tree / FD-Treesnot authored
pages 131–135 ·
·
Fractional Cascading / Logarithmic Runs / Bw-Treesnot authored
pages 135–138 ·
·
Update Chains / Taming Concurrency with Compare-and-Swap / Structural Modification Operationsnot authored
pages 138–141 ·
·
Consolidation and Garbage Collection / Cache-Oblivious B-Trees / van Emde Boas Layoutnot authored
pages 141–144 ·
·
Summarynot authored
pages 144–147 ·
·

7 Log-Structured Storage

LSM Treesnot authored
pages 148–150 ·
·
LSM Tree Structurenot authored
pages 150–154 ·
·
Updates and Deletes / LSM Tree Lookups / Merge-Iterationnot authored
pages 154–158 ·
·
Reconciliation / Maintenance in LSM Treesnot authored
pages 158–162 ·
·
Read, Write, and Space Amplification / RUM Conjecture / Implementation Details / Sorted String Tablesnot authored
pages 162–165 ·
·
Bloom Filtersnot authored
pages 165–168 ·
·
Skiplist / Disk Accessnot authored
pages 168–170 ·
·
Compression / Unordered LSM Storage / Bitcask / WiscKeynot authored
pages 170–175 ·
·
Concurrency in LSM Trees / Log Stacking / Flash Translation Layernot authored
pages 175–178 ·
·
Filesystem Logging / LLAMA and Mindful Stackingnot authored
pages 178–181 ·
·
Open-Channel SSDs / Summarynot authored
pages 181–184 ·
·

8 Introduction and Overview

Concurrent Execution / Shared State in a Distributed Systemnot authored
pages 189–192 ·
·
Fallacies of Distributed Computing / Processingnot authored
pages 192–195 ·
·
Clocks and Time / State Consistency / Local and Remote Executionnot authored
pages 195–197 ·
·
Need to Handle Failures / Network Partitions and Partial Failures / Cascading Failuresnot authored
pages 197–200 ·
·
Distributed Systems Abstractions / Linksnot authored
pages 200–206 ·
·
Two Generals’ Problem / FLP Impossibilitynot authored
pages 206–209 ·
·
System Synchrony / Failure Models / Crash Faultsnot authored
pages 209–211 ·
·
Omission Faults / Arbitrary Faults / Handling Failures / Summarynot authored
pages 211–215 ·
·

9 Failure Detection

Heartbeats and Pings / Timeout-Free Failure Detector / Outsourced Heartbeatsnot authored
pages 216–219 ·
·
Phi-Accural Failure Detector / Gossip and Failure Detection / Reversing Failure Detection Problem Statementnot authored
pages 219–222 ·
·
Summarynot authored
pages 222–224 ·
·

10 Leader Election

Bully Algorithm / Next-In-Line Failover / Candidate/Ordinary Optimizationnot authored
pages 225–229 ·
·
Invitation Algorithm / Ring Algorithm / Summarynot authored
pages 229–233 ·
·

11 Replication and Consistency

Achieving Availability / Infamous CAP / Use CAP Carefullynot authored
pages 234–237 ·
·
Harvest and Yield / Shared Memory / Orderingnot authored
pages 237–240 ·
·
Consistency Models / Strict Consistency / Linearizabilitynot authored
pages 240–247 ·
·
Sequential Consistency / Causal Consistencynot authored
pages 247–252 ·
·
Session Models / Eventual Consistency / Tunable Consistencynot authored
pages 252–256 ·
·
Witness Replicas / Strong Eventual Consistency and CRDTsnot authored
pages 256–260 ·
·
Summarynot authored
pages 260–263 ·
·

12 Anti-Entropy and Dissemination

Read Repair / Digest Reads / Hinted Handoffnot authored
pages 264–267 ·
·
Merkle Trees / Bitmap Version Vectorsnot authored
pages 267–270 ·
·
Gossip Dissemination / Gossip Mechanics / Overlay Networksnot authored
pages 270–273 ·
·
Hybrid Gossip / Partial Viewsnot authored
pages 273–275 ·
·
Summarynot authored
pages 275–278 ·
·

13 Distributed Transactions

Making Operations Appear Atomic / Two-Phase Commitnot authored
pages 279–282 ·
·
Cohort Failures in 2PC / Coordinator Failures in 2PC / Three-Phase Commitnot authored
pages 282–286 ·
·
Coordinator Failures in 3PC / Distributed Transactions with Calvinnot authored
pages 286–289 ·
·
Distributed Transactions with Spanner / Database Partitioningnot authored
pages 289–293 ·
·
Consistent Hashing / Distributed Transactions with Percolatornot authored
pages 293–297 ·
·
Coordination Avoidancenot authored
pages 297–299 ·
·
Summarynot authored
pages 299–303 ·
·

14 Consensus

Broadcast / Atomic Broadcast / Virtual Synchronynot authored
pages 304–307 ·
·
Zookeeper Atomic Broadcast (ZAB)not authored
pages 307–309 ·
·
Paxos / Paxos Algorithmnot authored
pages 309–312 ·
·
Quorums in Paxos / Failure Scenariosnot authored
pages 312–315 ·
·
Multi-Paxos / Fast Paxosnot authored
pages 315–318 ·
·
Egalitarian Paxosnot authored
pages 318–321 ·
·
Flexible Paxos / Generalized Solution to Consensusnot authored
pages 321–326 ·
·
Raft / Leader Role in Raftnot authored
pages 326–330 ·
·
Failure Scenarios / Byzantine Consensusnot authored
pages 330–332 ·
·
PBFT Algorithmnot authored
pages 332–335 ·
·
Recovery and Checkpointing / Summarynot authored
pages 335–339 ·
·

← Back to studying · Progress and finish date →

The roadmap

1 Introduction and Overviewskip chapter

2 B-Tree Basicsauthor chapter skip chapter

3 File Formatsauthor chapter skip chapter

4 Implementing B-Treesauthor chapter skip chapter

5 Transaction Processing and Recoveryauthor chapter skip chapter

6 B-Tree Variantsauthor chapter skip chapter

7 Log-Structured Storageauthor chapter skip chapter

8 Introduction and Overviewauthor chapter skip chapter

9 Failure Detectionauthor chapter skip chapter

10 Leader Electionauthor chapter skip chapter

11 Replication and Consistencyauthor chapter skip chapter

12 Anti-Entropy and Disseminationauthor chapter skip chapter

13 Distributed Transactionsauthor chapter skip chapter

14 Consensusauthor chapter skip chapter

1 Introduction and Overview

2 B-Tree Basics

3 File Formats

4 Implementing B-Trees

5 Transaction Processing and Recovery

6 B-Tree Variants

7 Log-Structured Storage

8 Introduction and Overview

9 Failure Detection

10 Leader Election

11 Replication and Consistency

12 Anti-Entropy and Dissemination

13 Distributed Transactions

14 Consensus