In the last article, introduced the LRU algorithm in Redis application, this continues to introduce to you friends in Mysql InnobDB engine, is how to use LRU algorithm.

InnoDB buffer pool

Introduction to the cache pool and its memory structure

Let’s start with InnoDB’s buffer pool. A buffer pool is simply an area of memory where InnoDB accesses data and index information stored on disk. Buffer pools have two functions: one is to improve the efficiency of bulk read operations, and the other is to improve the efficiency of cache management. Tuning the cache pool parameters so that frequently accessed parameters remain in the cache pool is an important Mysql optimization tool.

The memory structure of an InnoDB cache pool is shown below:

Figure from inside Mysql Tech: InnoDB Storage Engine

Cache pool status

We can use the SHOW ENGINE INNODB STATUS command to see how the cache pool looks in the INNODB ENGINE:

---------------------- BUFFER POOL AND MEMORY ---------------------- Total memory allocated 6593445888; Dictionary memory allocated 7687783 // Total memory allocated to InnoDB data Dictionary Buffer pool size 393208 // Database pages 40485 // Total size of the LRU list of the buffer pool. Modified DB Pages 4 // The number of pages currently Modified in the buffer pool. Pending reads 0 // Number of buffer pool pages waiting to be read into the buffer pool. Pending writes: LRU 0, Flush list 0, single Page 0 // Number of old dirty pages in buffer pool written from bottom of LRU list. // The number of buffer pool pages to refresh during checkpoint. // The number of independent page writes pending in the buffer pool. Pages made Young 5, not young 0 // Pages made Young 5, not young 0Copy the code

The complete cache pool status information can be found here: Cache Pool Status Information

The number and size of the cache pool

To avoid concurrency conflicts caused by multiple threads reading and writing to the cache pool, InnoDB can configure multiple cache pools, specified by the parameter Innodb_buffer_POOL_Instances, which are allocated and managed internally using hash tables.

In general, the larger the cache pool size, the more Mysql behaves like an in-memory database. We can dynamically resize the cache pool at startup or run time with the innodb_buffer_pool_size parameter, Note that the size of innodb_buffer_pool_size is automatically adjusted to an integer multiple of the InnoDB buffer pool block Innodb-buffer-pool-chunk-size (default: 128 MB).

To avoid potential performance problems, the number of cache pool sizes/cache pool block sizes (Innodb_buffer_pool_size/Innodb_buffer_pool_chunk_size) should not exceed 1000.

Flush the cache pool

When it comes to caching, there must be a cache flush mechanism, that is, the removal of dirty pages from the cache (pages that have been modified but not flushed to disk).

In versions 5.7 and up, InnoDB starts the default four threads concurrently to clean dirty pages from the cache pool. There are two modes for cleaning dirty pages:

  1. Normal mode, when the proportion of dirty pages in the cache pool exceedsinnodb_max_dirty_pages_pct_lwm(low horizontal defaults to 25%), the normal mode is enabled to flush dirty pages to disk.
  2. aggressively flushes(Radical model?) , when the proportion of dirty pages in the cache pool exceedsinnodb_max_dirty_pages_pct(default: 75%), enable the faster refresh mode to flush dirty pages to disk as quickly as possible.

Prefetch of cache pool

InnoDB cache pools not only cache passively, but also asynchronously read data pages from disk in advance in two ways:

  • Linear: Prereads are performed according to the order in which the cache pool accesses data. When the number of pages read in an area exceeds innodb_read_ahead_threshold, all remaining pages in that area are loaded into the cache pool.

  • Randomness: Preread pages from the cache pool regardless of their order. If the number of pages in a section of the cache pool exceeds innodb_random_read_ahead, all remaining pages in the section are loaded into the cache pool.

Cache pool LRU algorithm

Now that we know about InnoDB’s cache pool concept, let’s take a look at the algorithms behind it that allow it to work.

When we use the naive LRU algorithm, we will find that if there are batch operations, the cache data will be scrambled, greatly reducing the cache hit ratio. In Mysql, there are a lot of prereads and full table scans. In order to keep real hot data in memory, InnoDB cache pool uses a variant of LRU algorithm, similar to the LRU-K algorithm I wrote about in this article.

Instead of going directly to the head of the LRU list, new pages are inserted 3/8 away from the end of the list (which can be configured by the innodb_old_blocks_pct parameter). We call the places above 3/8 away from the end of the list new sublists, and the places below the end of the list old sublists. The data in the linked list from the bottom up is called getting younger, and vice versa is called getting older. Here’s a schematic:

  • younger

    There are two cases of youth. The first is when the page is read from the user’s action, which moves the page directly to the head of the new child list. The second type is a pre-read operation from within the database, which does not move the page to the head of the LRU list even if it is accessed within the time between innodb_olD_blocks_time insertion (default: 1000ms).

    In other words, if the action is from the user, it takes at least two actions to become young. In the case of a prefetch operation, a waiting period is required.

  • Grow old

    As the linked list data is replaced and accessed, the data in the entire list will naturally age. Eventually the oldest page is ejected from the tail.

conclusion

This paper introduces the concept of the cache pool of Mysql InnoDB engine and the transformation of LRU algorithm. Another solution to LRU list contamination is introduced.