Introduction to MySQL Internals

In this article, we will talk about database internals at a high level. We focus on MySQL, but most of it applies to many other databases too.

We will talk about architecture, concurrency, transactions, ACID, deadlocks, and MVCC.

What is a database?

A database is an organized collection of data, stored and accessed electronically. It is controlled by a database management system, the DBMS. Together, the data, the DBMS, and the applications around them are what we call a database.

MySQL architecture

Enlarge

Connections and threads

This layer handles network connections, authentication, security, and more. By default, MySQL runs one thread per client connection. With many connections, this leads to performance problems. There are thread pool plugins that improve this by making better use of multi core machines.

Parser and optimizer

This is where most of MySQL's work happens. When a query arrives, MySQL parses it into a parse tree, then optimizes it, then executes it. Optimization means, for example, choosing which index to use. MySQL tries to use the most selective index, so it eliminates more rows early. It also removes dead code, like a condition that is always true or always false.

Older MySQL versions also had a query cache in this layer, which returned cached results for identical queries. It was deprecated in MySQL 5.7 and removed in MySQL 8.0.

Storage engines

Storage engines are the components responsible for storing and retrieving the data. Each engine has its own characteristics, and you need to know them to decide which engine fits your data. Today InnoDB is the default and the right choice for almost everything.

Concurrency

Concurrency is when multiple readers and writers try to read and write at the same time. When multiple processes write the same piece of data, the data can end up in an inconsistent state. To solve this, we can lock that piece of data so nobody else can change it while someone is already changing it.

Locks

Locks make shared data safe for concurrent access. When many processes read and write the same data, we restrict access to it while it is being changed, so it doesn't get corrupted.

InnoDB has two main kinds of row locks:

• Shared lock (S): taken by a locking read, for example SELECT ... FOR SHARE (or LOCK IN SHARE MODE in older versions). Multiple transactions can hold a shared lock on the same row. Note that a normal SELECT does not take any lock in InnoDB. It reads from an MVCC snapshot, so readers don't block each other.
• Exclusive lock (X): taken when you update or delete a row, or with SELECT ... FOR UPDATE. While a transaction holds it, other transactions can't lock or change that row. Normal non locking reads still see the last committed version through MVCC.

Lock granularity

Lock granularity means how much data we lock at once: a whole table or single rows. Each choice is a tradeoff between concurrency and overhead.

Table locks

This locks the whole table. It's the most basic kind of locking. It has the lowest overhead, but also the lowest concurrency.

A special case is the auto inc lock: a table level lock taken when inserting into a table with an AUTO_INCREMENT column, so the generated values stay in order.

Row locks

This locks only one or more rows. MySQL uses the available indexes to decide which rows to lock. There are several kinds:

• Record locks: lock an index record. If the table has no index, InnoDB creates a hidden clustered index and uses it to lock the records.
• Gap locks: lock the gap between index records. For example, while a transaction runs SELECT x FROM t WHERE x BETWEEN 1 AND 10 FOR UPDATE;, nobody can insert 5.
• Next key locks: a record lock plus a gap lock on the gap before it. This is what InnoDB uses by default in REPEATABLE READ.

Locking strategies are different from one storage engine to another, so get an overview of what each engine offers before you choose one.

Transactions

A transaction is a set of queries that form a single unit of work. Either all of them are applied, or none. If a transaction has 4 queries and one fails, the others are rolled back as if they never happened.

A transactional database must meet the ACID properties.

Atomicity

A transaction is one atomic unit of work. When it makes multiple changes, either all of them are applied on success, or all of them are rolled back on any failure.

Consistency

A transaction takes the database from one valid state to another valid state. All the rules, like constraints and foreign keys, must hold before and after the transaction.

Isolation

Transactions are protected from each other while they are not committed. They don't interfere with each other, and depending on the isolation level, they don't see each other's uncommitted data.

Durability

Once a transaction is committed, its changes are saved permanently and survive failures like a crash or a power cut.

Isolation levels

The isolation level controls the I in ACID. Each level is a tradeoff between performance, consistency, and how reproducible your reads are in a concurrent system.

READ UNCOMMITTED

This gives the least consistency and protection, but also the least overhead. A transaction can see the uncommitted changes of other transactions, which are called dirty reads. Use it with caution, and only if you really know what you are doing.

READ COMMITTED

A transaction only sees changes from other transactions after they are committed. This is the default in many database systems, like PostgreSQL. But it allows non repeatable reads: if you read the same row at the beginning and at the end of your transaction, and another transaction committed a change in between, the second read returns different values.

Non repeatable reads come from UPDATE statements.

REPEATABLE READ

This is the default in MySQL. It solves non repeatable reads. In InnoDB, all normal reads in the same transaction see the same snapshot, the one taken at the first read. So if the transaction reads the same data multiple times, it gets the same result.

In the SQL standard, this level still allows phantom reads: running the same query twice in one transaction and getting a different set of rows. InnoDB avoids most phantoms with its snapshot for normal reads and next key locks for locking reads.

Phantom reads come from INSERT statements.

SERIALIZABLE

This is the highest isolation level. It uses the most conservative locking, so no other transaction can insert or change data that this transaction has read until it finishes. In InnoDB, it basically turns every normal SELECT into a locking read, placing a shared lock on every row it reads.

Deadlock

A deadlock happens when two transactions each hold a lock the other one needs, so both wait for each other forever. InnoDB detects deadlocks and rolls back one of the transactions, so your application should be ready to retry.

Enlarge

Multi version concurrency control (MVCC)

MySQL uses MVCC to increase concurrency, so it only needs locks for writes. It keeps older versions of the data, so a transaction can see a consistent view of the data as it was at a point in time. Each engine implements MVCC differently, but all of them use versioning to keep a consistent view during the transaction. In InnoDB, MVCC is used in the REPEATABLE READ and READ COMMITTED isolation levels.

MVCC with a SELECT transaction

Enlarge

The next sections describe a simplified model, the one used in the book High Performance MySQL. In reality, InnoDB stores a transaction ID in each row and keeps the older versions of rows in the undo log, but the idea is the same.

MVCC with INSERT

The engine stores the current system version number with the new row.

MVCC with DELETE

The engine sets the row's deletion version to the current system version number.

MVCC with UPDATE

The engine writes a new copy of the row with the current system version number, and sets the old row's deletion version to the current system version.