In the previous two articles, the author explained some knowledge points of InnoDB’s core component Buffer Pool and had a certain understanding of the internal structure of the Buffer Pool.
The first lecture mainly introduced the concept of cached pages.
InnoDB Buffer Pool InnoDB Buffer Pool
The second lecture introduces three linked lists: free linked list, Flush linked list and LRU linked list.
InnoDB Buffer Pool InnoDB Buffer Pool
Now we know that when you perform a CRUD operation InnoDB loads data from the data page on disk into the cache page. To load, find a free cache page from the free list, and load the data page from disk into that free cache page. If the free list does not have any free cache pages, you can go to the end of the LRU list to find the least recently used cache page, flush it to disk, free the free cache page, and load the required disk data pages into the free cache page.
If you read the article, you might think that the LRU linked list is different from what I read in the tech blog. Is the writer wrong?
In fact, it is not, usually share a technology, especially more complex technology, are from the shallow to the deep, first introduce the simple point, slowly introduce more in-depth principle. You can’t just throw all the core knowledge at you.
The proofs
The mechanism of the LRU list is very simple. As long as there are no free cached pages, some cached pages are removed from the end of the list and the newly loaded cached pages are placed in the head of the LRU list.
But such a mechanism of operation, there will be great hidden dangers.
The first is the pre-read mechanism!
Preread, when you load a page of data from disk, it may load other pages of data adjacent to that page into the cache.
The designers take into account that when we access a cached page, we are likely to continue to access data from other cached pages adjacent to it.
However, sometimes only one of the cached pages is accessed, and the other loaded cached pages are accessed once and never accessed again, all of which are at the top of the LRU list.
Figure 1 LRU linked list and prefetch
As figure 1 shows, the first two cache pages are just loaded in, but the second cache page is preloaded and loaded in, and it is also placed at the head of the list, ahead of the previously loaded cache page, but no one accesses it.
If there are no free cached pages at this point, you need to flush some cached pages from the end of the LRU list. However, if you empty the two cache pages at the end of Figure 1, do you think it makes sense? It’s the same cached page that was accessed all the time, but it’s just crowded to the end by the new cached page that’s been loaded in.
At this point, it would not make sense for you to flush the cached pages at the end of the LRU list to disk. Instead, you should flush the cached pages that were preloaded to disk, since they are rarely accessed.
What would trigger the prefetch mechanism?
InnoDB has a parameter, Innodb_read_ahead_threshold. Its default value is 56, which means that if multiple data pages in an area are accessed sequentially and the number of data pages accessed exceeds this value, the prefetch will be triggered and the data pages in adjacent areas will be loaded into the memory area.
(2) The Buffer Pool caches 13 consecutive data pages in an area, which triggers the prefetch mechanism. This mechanism is controlled by the innodb_random_read_ahead parameter, which is turned off by default.
Therefore, in general, only the first case will trigger the prefetch mechanism, loading many adjacent data pages into the cache at a time. If these cache pages are placed at the front of the LRU list at a time, the cache pages that were frequently accessed will be put at the end of the LRU list. When weeding out is needed, these heavily accessed cached pages are weeded out. This is unreasonable!
In fact, the most common scenario that triggers the first scenario is a full table scan.
For example, execute SQL: SELECT * FROM USER.
All the data in the query table will load the data pages from disk into the Buffer Pool. Then there will be a large number of cached pages in the head of the LRU list, which will hardly be accessed after this SQL query.
How to optimize prefetch?
In order to solve the prefetch problem mentioned above, MySQL does not simply use Least Recently Userd when designing LRU linked list, but adopts the idea of separating hot and cold data.
The MySQL LRU list is divided into two parts, one is hot data, and the other is cold data. The ratio of cold data to hot data is controlled by innodb_old_blocks_pct. The default value is 37, which means that cold data accounts for 37% by default.
FIG. 2 Separation of hot and cold data in cache
Operation principle of hot and cold data area
When the data page is first loaded into the Buffer Pool, it is placed at the head of the cold data area, as shown in Figure 3.
Figure 3. Cache page loading data for the first time
This threshold is controlled by the innodb_old_blocks_time parameter. The default value is 1000 milliseconds.
This means that after a data page is loaded into the cache page, it will be moved to the head of the hot data area after you visit the cache page a second later.
Since you load a data page into the cache and return to the page a second later, you will be accessing it frequently, so put it in the hot data area. If it is accessed within 1 second, it will determine that you will not visit the cached page frequently in the future and will not move to the hot data area.
If an SQL query triggers a full table scan and loads a large number of cache pages into the Buffer Pool, how does the hot and cold data separation solution solve the previous problem?
In this case, the pre-loaded data page is placed in front of the cold data area. The hot data area is not affected, and the data pages that were frequently accessed by the hot data area can still be accessed.
Now after a second, if a bunch of cached pages are accessed, they move to the hot data head.
Under the idea of separating hot and cold data, how to eliminate data?
Suppose we run out of cached pages and need to flush out some of them?
Directly eliminate the cache page at the end of the cold data area!
Since they are only loaded into the Buffer Pool and used for 1s, they are no longer used, so they can be eliminated directly.
Based on the cache page cold and hot data separation scheme, coupled with the time limit of cold data to hot data area, as well as the priority to eliminate cold data area scheme, it perfectly solves the previous problem.
Most of the data pages loaded by the prefetch mechanism and full table scan will be accessed within 1s, and then will not be accessed. Therefore, such data will basically remain in the cold data area, while the data pages with high access frequency in the hot data area will not be affected. When weeding out, it is also weeding out cache pages with cold data to the tail.
This is how InnoDB’s LRU linked list separates hot and cold data.
What other optimizations InnoDB has for LRU lists?
Does the hot data area move to the header as soon as it accesses a cached page inside?
There’s no need! Keep in mind that cached pages in hot data areas are accessed frequently.
InnoDB states that only cached pages in the bottom three quarters of the hot data area are accessed before they are moved to the head of the list.
If you access the first quarter of the hot data page, you won’t move to the top of the list.
If you are accessing the first 25 cached pages, you will not move to the head of the list. If you are accessing the last 75 cached pages, you will move to the head of the list.
By now, the core mechanism of Buffer Pool is basically finished. After reading these three articles, I believe you will have a complete operation flow chart in your mind.
Please long press the QR code to pay attention to the architecture notes of Nanshan