Planet MySQL :: Planet MySQL - Archives - What Is InnoDB History List Length?

Houston, we have a problem. Google search for “What is innodb history list length?” and you get a bunch of nonsense mixed in with correct information, and it’s hard to tell which information is right. Let’s fix this.

What is InnoDB History, Anyway?

InnoDB is an MVCC storage engine, which means you can start a transaction and continue to see a consistent snapshot even as the data changes. This is implemented by keeping old versions of rows as they are modified.

They’re kept in a linked list. The most recent version points to the previous one, which points to the previous one, and so on. Each version has a transaction ID with it so when InnoDB goes looking for a row, it compares your current transaction ID to the row version and selects the right one for you. This can be done without locking.

MVCC is complicated and I’m simplifying, but that’s the essence of what happens.

What Is The History List?

The InnoDB history list is the undo logs which are used to store these modifications. They are a fundamental part of InnoDB’s transactional architecture.

How Can I Inspect The History List?

In classic InnoDB, you had to look at the InnoDB transaction “monitor” which is best-known as the SHOW ENGINE INNODB STATUS command. There’s a little section of it that looks like this:

------------
TRANSACTIONS
------------
Trx id counter 26168770192
Purge done for trx's n:o < 26168770192 undo n:o < 0 state: running but idle
History list length 1839

This shows which transactions have been purged and how long the history list length is.

In some variants of MySQL, such as Percona Server, there’s a SHOW STATUS variable called Innodb_history_list_length which makes this a lot more accessible to monitor.

What Are The Units Of The History List?

So if the history list length is 1839, what exactly does that mean?

Various sources online claim that this is in different units:

unpurged old row versions
unpurged transactions in the undo space
modifications to the database
undo segments (huh?)
unflushed segments in the undo log (not clearing things up…)
undo pages, or number of pages in the undo log (what?)
undo logs (you mean, like log files?)

So what is it, really?

Let’s go to the source:

So as you can see, the call stack is a bit twisty if you’re not familiar with the InnoDB internals!

The best name for the unit is undo logs, which are “update undo logs for committed transactions”, to quote the source. But an “undo log” is a special term with specific meaning in InnoDB. An undo log is a single set of atomic changes a transaction makes, which may actually modify multiple records.

Naming is hard. This is one of the 10 hard things in computer science, we all know that. (The other thing is cache invalidation. Binary arithmetic is not a third hard thing.) Most of the confusion around the history list comes from how the terms are defined and used in InnoDB’s source code. To understand these terms you have to understand a lot of the foundations of InnoDB.

In layman’s terms, to be a bit hand-wavy, the history list length is in units of changes. If you are a Git user, you might think of it as analogous to the commit history of the database. (Note, however, that the entire history isn’t retained forever as it is in Git.)

How Does The History List Interact With InnoDB’s Internals?

In very complicated ways.

Old row versions are eventually deleted. What does “eventually” mean?

When they’re not needed anymore – no currently running transaction could possibly see them anymore. Hence the advice that “long running transactions are bad” because they delay purge. InnoDB’s purge, by the way, is analogous to PostgreSQL’s VACUUM, although it is considerably more sophisticated. (This may not be a good thing. It’s really hard to understand, and has edge cases that are difficult to manage.)
When the background purge thread(s) get around to it. The purge subsystem in InnoDB is really confusing for anyone not intimately familiar with the source code. It’s a bunch of algorithms that try to purge fast enough to keep up, but steadily enough not to cause serious performance problems. The algorithms have varied significantly over time. There are also variations on the number of purge threads (there used to not even be a dedicated thread for this, it was just catch-as-catch-can in a “main thread”). All kinds of difficult-to-balance things are traded off against each other.
It’s not just about long-running transactions, but also about long-running statements.
The transaction isolation levels influence which old row versions need to be kept, too.
The history list can, with some nuances I can’t dive into here, actually cause InnoDB to delay DML operations.

The history list is actually unflushed changes, by the way. This means that as the history list grows, the amount of flushing (writing pages from the buffer pool to disk) the server has to do in the future grows.

What Is The Relationship To Purge Lag?

This is quite complicated and is explained in more details than I can include here, in some of the references at the end of this article.

However, in high-level terms, purge lag is closely related to the history list. To quote the fine manual,

The InnoDB transaction system maintains a list of transactions that have index records delete-marked by UPDATE or DELETE operations. The length of this list represents the purge_lag value. When purge_lag exceeds innodb_max_purge_lag, each INSERT, UPDATE, and DELETE operation is delayed…. The lag value is displayed as the history list length

Where Is The History Stored in InnoDB?

There’s a special “undo space” which is page-organized in InnoDB. Like all other pages, it is kept in the buffer pool short-term and written to disk long-term. The undo space is transactional itself – any modifications to it are ACID.

This is really important for performance. It means that finding old row versions has to, in general terms:

look at the row and see if it’s the right version to be used
if not, go to the undo space and find an old version
if the appropriate page in the undo space isn’t in the buffer pool, load it from disk
if there’s no space for it, remove pages to make room in the buffer pool
if there’s no “clean” pages to remove, flush pages to disk to make them clean to let them be removed to make room.
if there’s too much flushing scheduled, get in line and wait your turn…

And so on.

And undo logs are different sizes; inserts can be small, but updates and deletes require storing more data to recreate the old row version correctly.

In other words, accessing old row versions can be, in certain circumstances, a very expensive operation.

Percona Server (XtraDB) has some features that can help you examine the composition of your buffer pool, which can be helpful for understanding edge-case situations.

I am not going to mention rollback segments, because that explodes the complexity of this topic even further.

Conclusions

Databases are complicated. Naming is hard. InnoDB’s history list is the array of changes transactions have performed, stored as undo logs that can be used for rollback, as well as recreating history for MVCC purposes.

Unfortunately, as I discovered halfway through writing this article, it’s difficult to explain without explaining all of InnoDB :-(

How did I do? Can it be explained more simply? Did I even get this right? Let me know in the comments.

References

Here are some references that are written by people in their left minds.

Pic credits: cat, birds

MySQL Links