This is the sixth day of my participation in the August Text Challenge.More challenges in August

I have introduced the buffer pool in theIn the previousThat’s it. I’m not going to do it here. Okay so let’s just get to the point.

LRU list

Lru list is essentially a bidirectional circular list with the following structure:

According to the space locality principle, the disk or database prereads the data near the data, andMysql also has a read-ahead mechanism. So if you follow a simple Lru list and put the most recently accessed page directly into the Lru list, when you read a data page, it willThe proofsmayIt is not necessary toMany data pages, these data pages mayYou won’t need it until it expires“, but it eliminated some of the most recently visited pages. This defeats the purpose of Lru lists. Of course, for this problem, mysql usesA variant of the Lru list.

Mysql lRU linked list

The Buffer Pool is managed using a variant of the LRU linked list. When space is needed to add a new page to the Buffer Pool, the least recently used page is removed and the new page is added to the middle of the list. This midpoint insertion strategy treats the list as two sublists:

  • Save the most recent recently accessed sublist in the header.
  • Save a sublist of the least recently visited pages at the end.

The specific structure is shown as follows:

New Sublist stores the recently visited pages, while old sublist stores the least recently used pages. Pages in old Sublist may be eliminated and replaced.

By default, the new sublist ratio is 5/8, and the old sublist ratio is 3/8.

Page read mechanism for LRU lists

In mysql’s LRU linked list, when a page reads a buffer pool, it is first inserted into the midpoint (the header of the old sublist). Pages are read in two ways:

  • User performing database operations (SQL query access page)
  • The storage engine automatically prereads data

Visiting a page in the old sublist moves it to the head of the new Sublist list. If the page is read in the pre-read operation, it will not be immediately accessed for the first time, and may not be accessed until the page is eliminated. Of course, under normal circumstances, reading the cached page of the old sublist will make the cached page rise to the new sublist and become hot data. However, in the case of reading a lot of data, that is, many cached pages are preread into the old sublist, and you access it in less than x seconds, the cached pages accessed during that time will not be promoted to the new sublist. This x second is controlled by the innodb_old_blocks_time parameter.

During database operations, pages in the buffer pool that are not accessed are moved toward the end of the list. Pages in both old and new sublist age as other pages are updated. Eventually, pages that are not used reach the end of old Sublist and are eliminated.

The Free list

The Free List is composed of base nodes and child nodes. The base node stores the number of description blocks in the Free List, that is, the number of Free cache pages. The child node has a control block, which is an object of the free page that is used to locate the free page.

The Free List stores Free pages. When paging from the cache pool is required, access the Free List to see if there are Free pages. If there are, get the page and assign it to the Lru List, and then delete the page from the Free List. If not, the LRU frees its trailing cached page and allocates that memory to the new page.

Flush the list

Flush List is a bidirectional linked List that holds blocks of cached page descriptions that have been modified to help us find the dirty pages that need to be flushed. (Dirty pages are cached pages whose data is inconsistent with the data on disk that needs to be flushed to disk.) Flush List also has a base node that stores the number of descriptive blocks.

Mysql has a thread that periodically searches the flush List for dirty pages, flushes cached pages from the Flush List to disk, deletes cached pages from the Flush List and adds them to the Free List. For the specific process, please refer to the following figure:

The lRU, free, and Flush lists that manage buffer pools in mysql are listed in lRU, free, and Flush lists.