The idea: a page cache that a big scan can't flush out
InnoDB reads and changes rows only inside the buffer pool: a large area of memory (innodb_buffer_pool_size, often 50–75% of RAM) cut into frames of 16 KB, one page each. A page found there is a hit and costs no I/O. A page not there is a miss: InnoDB needs a frame for it, and if none is free it must throw a page out. Which page goes is decided by an LRU list with a twist: it is cut in two at a midpoint, so that pages read once by a big scan never push out the pages that are used all the time.
The canvas has 8 frames. Seven hold pages of a hot table ord, one is free. A second table logs is read only by a full table scan. The user thread runs your SELECT or UPDATE; the page cleaner writes changed pages in the background.
Page hash and free list
A page is named by its tablespace and page number (space_id, page_no; ord/3 on the canvas). The page hash maps that name to the frame holding it. Every access starts there (Demo: hit and a miss from the free list). Frames that hold no page sit on the free list. At startup every frame is free; a miss takes one from the free list and needs no eviction. Only when the free list is empty does a miss evict a page from the tail of the LRU list. In SHOW ENGINE INNODB STATUS these are the lines Free buffers and Database pages, like the counters at the top of the canvas.
The LRU list and its midpoint
Every frame that holds a page is on the LRU list, from the head (most recently used) to the tail (evicted first). InnoDB splits it at the midpoint into a young sublist (the first 5/8) and an old sublist (the last 3/8, innodb_old_blocks_pct = 37). A page read from disk is not put at the head. It goes in at the midpoint, the head of the old sublist. From there it has two ways to go:
- it is used again later: it is made young and moves to the LRU head;
- it is not: newer pages push it down the old sublist until it leaves by the tail.
When a page moves to the head, every page behind it shifts one place towards the tail, so the young page at the end of the young sublist slips across the midpoint into the old sublist. The canvas narrates each crossing.
innodb_old_blocks_time and full scans
"Used again" needs care. A full table scan reads one page and then reads all its rows, one after another: it touches the same page many times within a millisecond. If any second touch made a page young, every scanned page would become young and the scan would push the hot pages out. So an access to an old page makes it young only if it comes at least innodb_old_blocks_time after the page's first access (1000 ms by default). Otherwise the page stays old; the status output counts it under pages not made young (Demo: old page made young after 1 s).
Run both scans. With 1000 ms the scanned pages enter the old sublist, are touched again 1 ms later, stay old, and push each other out of the tail; the five hot young pages are untouched (Demo: full scan, old_blocks_time = 1000). With 0 every scanned page is made young at its second touch, and after 5 pages the young sublist holds only logs pages (Demo: full scan, old_blocks_time = 0). The cost is paid later: the next queries on ord miss.
| Event | Page in young sublist | Page in old sublist |
|---|---|---|
| read from disk | — | inserted at the old head |
access < innodb_old_blocks_time after the first | stays young | stays old ("not young") |
access ≥ innodb_old_blocks_time after the first | stays young | made young: to the LRU head |
| not accessed | drifts into the old sublist | drifts to the tail, evicted |
PostgreSQL solves the same problem differently: a big scan gets a small private ring of buffers (see PostgreSQL Shared Buffers and the Clock Sweep). The general policies are compared on Cache Eviction: LRU vs LFU vs FIFO vs CLOCK vs OPT; this LRU-with-two-parts idea is close to the 2Q and LRU-K algorithms.
The flush list and the page cleaner
An UPDATE changes the page in its frame and writes a redo record; the page is now dirty and is written to its .ibd file later. Each dirty page remembers oldest_modification: the LSN of its first change since it was last written. Dirty pages are also on the flush list. A page that turns dirty joins the list's head, so the list is ordered by oldest_modification, newest to oldest. Changing an already dirty page again does not move it.
Page cleaner threads (innodb_page_cleaners) wake about once a second and write a batch of pages from the oldest end of the flush list. The batch size follows innodb_io_capacity and grows with adaptive flushing when the redo log fills up. A written page stays cached, now clean, at the same LRU place (Demo: UPDATE, page cleaner flushes oldest first). Flushing oldest first matters for the redo log: the checkpoint can only move up to the smallest oldest_modification still on the list, and redo before the checkpoint can be reused. See InnoDB Redo Log for checkpoint age, and the doublewrite buffer for how a page write is made safe against a torn page.
No free frame: the single page flush
A miss with an empty free list evicts the page at the LRU tail. If that page is clean it is simply dropped from the page hash. If it is dirty, the user thread must write it first and wait for the write: a single page flush. Your query now pays for a random write as well as a read (Demo: no free frame, dirty tail (single page flush)). This is what the page cleaner tries to avoid. Besides the flush list, it also scans the tail of the LRU list (innodb_lru_scan_depth pages per buffer pool instance), writes dirty pages it finds there and puts clean ones back on the free list, so that a user thread finds a free frame waiting.
Read-ahead
InnoDB groups pages into extents of 64 pages (1 MB). Linear read-ahead watches the access pattern: when innodb_read_ahead_threshold pages of an extent (56 by default) have been read in order, it reads the whole next extent in the background, before the scan asks. Those pages, too, go in at the midpoint, and if nobody touches them they leave by the tail; the status line evicted without access counts them. Random read-ahead (innodb_random_read_ahead, off by default) fetches the rest of an extent when 13 of its pages are already in the pool. The canvas does not show read-ahead; its 8 frames are smaller than one extent.
Settings and status that matter
innodb_buffer_pool_sizeandinnodb_buffer_pool_instances: the pool and how many independent parts (each with its own lists and mutex) it is split into.innodb_old_blocks_pct(37) andinnodb_old_blocks_time(1000): the midpoint and the promotion delay. Raise the time if scans still hurt; lower the percent if the hot set is large.innodb_io_capacity,innodb_max_dirty_pages_pct,innodb_lru_scan_depth,innodb_page_cleaners: how hard the page cleaners work.SHOW ENGINE INNODB STATUS(BUFFER POOL AND MEMORY) andinformation_schema.INNODB_BUFFER_POOL_STATS: free buffers, old database pages, modified pages, pages made young / not young, the hit rate.
See also How MySQL Runs a Query for where the buffer pool sits in a query, the 16 KB InnoDB page for what is inside a frame, the change buffer for writes to secondary index pages that are not in the pool, the adaptive hash index built on hot pages, and Page Replacement for the operating system's version of the same problem.
What the page leaves out
Real InnoDB keeps the old/young split only once the LRU list has at least 512 pages, and lets the old sublist drift by a few pages before adjusting it; a hit on a young page moves it to the head only if it has fallen out of the first quarter of the young sublist. The search for a victim looks at up to innodb_lru_scan_depth pages from the tail for a clean one before it does a single page flush; here it looks only at the tail page. The page leaves out buffer pool instances and their mutexes, page and block latches, pinned (buffer-fixed) pages that can't be evicted, compressed pages and the buddy allocator, read-ahead, the doublewrite buffer, adaptive flushing's formula, and dumping and loading the pool at shutdown and startup (innodb_buffer_pool_dump_at_shutdown).