Mysql学习笔记 - LRU算法

1.什么是LRU？

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“最近使用的页面数据会在未来一段时期内仍然被使用,已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用”。

2.LRU的实现

LRU算法最常见的实现是使用链表来保存数据，该链表是双向链表，然后利用先进先出的特性，最新写入的数据会最快被获取。

• 访问不存在的数据时，缓存数据则会写入链表的头部，链表写满时会淘汰掉尾部的缓存数据。
• 当缓存数据被访问时，则将该缓存数据向链表头部移动。

优点：面对频繁访问的热点数据，查询效率高

缺点：如果一次查询扫描全表，那么LRU列表会被污染

3.Mysql LRU算法有何不同？

Mysql（InnoDB）的缓冲池（buffer pool）使用了LRU算法的变体，将链表分为三个部分：young、midpoint、old。链表比例(5、3)分配给young、old。其中young占据5/8，old占据3/8，此比例受参数innodb_old_blocks_pct控制。

young是链表中最近访问过的新子表。

old是链表中最近访问的旧子表。

midpoint是介于新子表 & 旧子表的边界中间位置（也可以理解为旧子表的头部）。

• 数据库刚启动LRU链表为空时，此时会检查Free List中是否有空闲的数据页，如果有则从Free List中删除并且在LRU链表中写入相同的数据页。
• 访问不存在的数据页时，数据页不会直接写入链表的头部，而是写入中间位置，如果链表满了则会从旧子表尾部淘汰数据页。
• 当数据页被访问时，则判断访问数据页的时间是否大于设定innodb_old_blocks_time（默认：1000ms），如果大于则向链表头部移动，如果小于其位置不变。

改进优点：能够防止单次大量的全表扫描污染整个LRU链表。

4.Mysql LRU相关查询命令

>show engine innodb status\G;
----------------------
BUFFER POOL AND MEMORY
----------------------
Total memory allocated 137756672; in additional pool allocated 0
Total memory allocated by read views 88
Internal hash tables (constant factor + variable factor)
    Adaptive hash index 2217584         (2213368 + 4216)
    Page hash           139112 (buffer pool 0 only)
    Dictionary cache    593780  (554768 + 39012)
    File system         83536   (82672 + 864)
    Lock system         333248  (332872 + 376)
    Recovery system     0       (0 + 0)
Dictionary memory allocated 39012
Buffer pool size        8191
Buffer pool size, bytes 134201344
Free buffers            8048
Database pages          143
Old database pages      0
Modified db pages       0
Pending reads 0
Pending writes: LRU 0, flush list 0, single page 0
Pages made young 0, not young 0
0.00 youngs/s, 0.00 non-youngs/s
Pages read 143, created 0, written 0
0.00 reads/s, 0.00 creates/s, 0.00 writes/s
No buffer pool page gets since the last printout
Pages read ahead 0.00/s, evicted without access 0.00/s, Random read ahead 0.00/s
LRU len: 143, unzip_LRU len: 0
I/O sum[0]:cur[0], unzip sum[0]:cur[0]

Buffer pool size                    |   innodb_buffer_pool的大小
Free buffers                        |   当前Free List中数据页数量
Database pages                      |   LRU链表中数据页数量
Old database pages                  |   LRU链表中旧子表数据页数量
Modified db pages                   |   LRU链表中脏页数量
Pages made young 0, not young 0     |   数据页从old移至young的行为：page made young,数据页因为innodb_old_blocks_time导致没有从old移至young的行为：page not young。后面的数值是该行为发生的次数。