A brief analysis of MySQL's lru linked list

1. Briefly describe the traditional LRU linked list

LRU：Least Recently Used

I believe everyone is familiar with the LRU linked list. It is a basic data structure. I believe you have been asked what an LRU linked list is during an interview, or even asked to write an LRU linked list by hand.

If you read the previous article: Are you confused between query cache and BufferPool? Let’s talk about it!

You must have known about MySQL's Buffer Pool mechanism and that the smallest unit of MySQL data organization is the data page. And you also know that data pages are organized together in the Buffer Pool using the LRU linked list data structure.

In fact, the so-called LRU linked list is essentially a bidirectional circular linked list, as shown below:

Next, we describe the mechanism of MySQL loading data by combining the LRU linked list and data page mechanism:

We call the data page read from the disk a young page, and the young page will be placed directly at the head of the linked list. If a data page that already exists in the LRU linked list is used, the data page is also considered a young page and is moved to the head of the linked list. In this way, the data at the end of the linked list is the least recently used data. When the Buffer Pool capacity is insufficient or the background thread actively refreshes the data page, the data page at the end of the linked list will be refreshed first.

2. Disadvantages of Traditional LRU Link List

I'm sure you've heard of the principle of spatial locality at the operating system level before:

Spatial locality: This means that when you read a piece of data, the data stored in the memory addresses around it is also likely to be read, so the operating system will help you pre-read part of the data.

MySQL also has a pre-reading mechanism!

1. When the Buffer Pool stores 13 consecutive data pages in a zone, when you read from this zone, MySQL will load all the data pages in this zone into the LRU linked list in the Buffer Pool. (And then maybe you won't use these pre-read data pages at all)
2. When you sequentially access more than innndb_read_ahead_threshold=56 data pages in a zone, MySQL will automatically help you read the data pages in the next adjacent zone into the LRU linked list. (This mechanism is disabled by default)
3. When you execute select * from xxx;, if there are a lot of data pages in the table, these data pages will squeeze out the frequently used cache pages in the Buffer Pool one by one, and all that may remain in the LRU linked list are data that you do not use frequently.

From the above, you can see that the advantage of the so-called pre-reading mechanism actually goes against the original design intention of LRU to flush the least recently used data pages to disk.

3. MySQL LRU linked list

Next, let's take a look at how MySQL's Buffer Pool customizes the LRU linked list and what problems LRU has helped InnoDB solve.

When the business performs a large amount of CRUD, it is necessary to continuously read data pages into the LRU linked list in the buffer pool.

The length of MySQL's LRU linked list is as follows.

The LRU linked list is divided into two parts: New Sublist and Old Sublist by MidPoint.

Among them, the New Sublist accounts for about 5/8, and the Old Sublist accounts for 3/8.

New Sublist stores young pages, and Old Sublist stores old pages.

We can view the default value of MidPoint as follows.

Users can adjust this parameter according to their business dynamics!

This is actually a design idea of ​​separating hot and cold data. It has great advantages over the traditional LRU linked list.

4. Advantages of MySQL customized LRU linked list <br /> For MySQL LRU linked list, the linked list is divided into two parts through MidPoint.

The newly read data from the disk will be placed at the head of the Old Sublist. In this way, even if you really use select * from t;, the frequently accessed data pages in the New Sublist will not be flushed to the disk.

Under normal circumstances, when a cache page in the Old Sublist is accessed, the cache page will be promoted to the New Sublist and become hot data.

But when you load a large amount of data into Old Sublist by select * from t, and then access it again in less than 1 second, the cached pages accessed during this period will not be promoted to hot data. This 1s is controlled by the parameter innodb_old_blocks_time.

In addition: New SubList is also optimized. If you access the first 1/4 of the data in New SubList, it will not be moved to the head of the LRU linked list.

The above is a brief analysis of the details of MySQL's lru linked list. For more information about MySQL's lru linked list, please pay attention to other related articles on 123WORDPRESS.COM!