Have you ever wanted to learn more about Databases but did not know where to start? This is a book just for you.

We can treat databases and other infrastructure components as black boxes, but it doesn’t have to be that way. Sometimes we have to take a closer look at what’s going on because of performance issues. Sometimes databases misbehave, and we need to find out what exactly is going on. Some of us want to work in infrastructure and develop databases. This book’s main intention is to introduce you to the cornerstone concepts and help you understand how databases work.

The book consists of two parts: Storage Engines and Distributed Systems since that’s where most of the differences between the vast majority of databases is coming from.

In Storage Engines, we start with taxonomy and terminology, then explore In-Place Update storage and discuss several B-Tree variants and their structure. Then we talk about binary data formats and file organization and explore the ways to compose efficient on-disk structures. After that, we go into the detail on what techniques different databases use when implementing B-Trees and talk about related data structures such as Page Buffer, Write-Ahead Log, how to implement compression and perform defragmentation and compaction. Finally, we discuss Log-Structured storage and explore a few different storage engine approaches, such as Bw-Trees, FD-Trees, CoW B-Tress, Bitcask, WiscKey, 2/3 Component LSM, and some other ones.

In Distributed Systems, we start with basic concepts such as processes and links and start building more complex communication patterns. We quickly discover that communication is unreliable and discuss which guarantees we have and how to achieve those. We cover the Important concepts such as Failure Detection, Leader Election and Gossip Dissemination. After that, we explore different Consistency Models and talk about ways to achieve them. After covering Atomic Commitment and Broadcast, we move to the pinnacle of Distributed Systems research: Consensus Algorithms.

This book includes references to 100+ papers, 10+ books several open source database implementations and other sources you can refer to for further study.

What’s Inside

Taxonomy and Terminology

We discuss the precise definitions, use-cases, applications and differences between the existing databases and storage engines sorts and classes: Column vs Row Oriented Stores, Memory and Disk based databases, In-Place Update and Immutable storage engines.

In-Place Update Storage Engines

Many modern databases such as PostgeSQL, MySQL and many others implement variants of the mutable in-place update data structure: B-Tree. We’ll discuss its origins, binary on-disk layout, organisation and popular variants such as Blink-Trees, B*-Trees, Copy-On-Write B-Trees and many others.

Auxiliary Structures

Storage Engines consists of a primary storage data structure and several auxiliary subsystems that take care of garbage collection, maintenance, compression. Many modern databases use Write-Ahead Log for restore and recovery and implement buffer management in a form of Page Cache.

Log-Structured Storage

With advent of SSDs, we’ve seen many databases implementing and using Log-Structured storage. We’ll explore the whole spectrum of immutable data structures, ranging from B-Tree like LSM-Trees and Bw-Trees to unsorted variants such as LLAMA, Bitcask, WiscKey.

Problems with Distributed Systems

How are the Distributed Systems different from the single-node ones? What is FLP Impossibility and Two-Generals problems. How network and communication using message passing puts limits on what we can and not do and how we can build reliable systems despite these complications.

Consistency Models

In a replicated systems, where we have multiple copies of data, we have to make to keep nodes in sync to return consistent results. We talk about concepts of Linearizability, Serializability, Eventual and Causal Consistency, their guarantees and limitations.

Leader Election and Failure Detection

Many distributed databases use a concept of Leadership to have a single point of reference and make some of the decisions locally. However, both the leader and participant may fail. We explore several Failure Detection algorithms that help us to detect these failures and react to them.

Broadcast and Consensus

With Atomic Commitment, Total Broadcast and Consensus algorithms, distributed systems can make cluster-wide decisions and communicate them to the participants preserving strong consistency guarantees. We discuss both traditional and cutting-edge algorithms used for that.

About the Author

Alex is an Infrastructure Engineer, Apache Cassandra Committer and PMC Member, working on building data infrastructure and processing pipelines. He’s interested in algorithms, Databases, Distributed Systems, understanding how things work and sharing it with others through blog posts, articles and conference talks.

Feedback, Reviews and Testimonies

FAQ

Where do I get a DRM-free version of the book?

Most definitely, just as any O’Reilly book, you can get it from ebooks.com.

Is this book about NoSQL/Distributed or Traditional/Relational Databases?

This book does not dissect any specific database. Instead, it takes several of them apart to understand what’s inside. B-Trees can be used both in relational databases, say, PostgreSQL and in document databases such as, for example MongoDB (WiredTiger). Similarly, there was an attempt to add LSM Trees to SQLite, while it’s used in Apache Cassandra.

Distributed systems concepts such as Two-Phase commit, Gossip, Leader Election and Failure Detection are not specific to NoSQL movement and can be (and are) used in many databases. Moreover, we witness a new generation of databases working at scale while offering rich query API and strong (or configurable) consistency guarantees. The book is about concepts that are seen in databases, all kinds of databases.