大家好，我是小林。上周在群里看到一个小伙伴面试，被问到这两个问题：乍一看以为是操作系统的问题，其实这两个问题是关于如何提高LRU的算法。因为传统的LRU算法存在这两个问题：“预读失败”导致缓存命中率下降（对应第一个问题）“缓存污染”导致缓存命中率下降（对应第二个问题）问题）Redis的缓存淘汰算法是通过实现LFU算法来避免“缓存污染”导致缓存命中率下降的问题（Redis没有预读机制）。MySQL和Linux操作系统改进了LRU算法，避免了“预读失效和缓存污染”导致缓存命中率下降的问题。这一次，我们来关注一下MySQL和Linux操作系统是如何改进LRU算法的？好了，开始吧，坐稳！CacheofLinuxandMySQLLinux操作系统的缓存当应用程序读取文件的数据时，Linux操作系统会将读取到的文件数据缓存起来，缓存在文件系统中的PageCache中（如图下图中）页面缓存）。PageCache属于内存空间中的数据。因为内存访问比磁盘访问快很多，所以下次访问同样的数据时，不需要经过磁盘I/O，命中缓存就可以直接返回数据。因此PageCache起到了加速数据访问的作用。MySQL的缓存MySQL数据存储在磁盘上。Innodb存储引擎为了提高数据库的读写性能，设计了一个缓冲池（BufferPool）。BufferPool属于内存空间中的数据。带缓冲池：读取数据时，如果数据存在于BufferPool中，则客户端直接读取BufferPool中的数据，否则从磁盘中读取。修改数据时，首先修改BufferPool中数据所在的页，然后将其页设置为脏页，最后通过后台线程将脏页写入磁盘。传统的LRU是如何管理内存数据的？Linux的PageCache和MySQL的BufferPool的大小是有限的，不能无限缓存数据。对于一些经常访问的数据，我们希望一直保存在内存中，而对于一些很少访问的数据，我们希望可以在特定的时间存储。可以淘汰掉，这样可以保证内存不会因为满了而无法缓存新的数据，也可以保证常用的数据还留在内存中。要做到这一点，最容易想到的就是LRU（Leastrecentlyused）算法。LRU算法一般是使用“链表”作为数据结构来实现的。链表头部的数据是最近使用的，而链表尾部的数据是最少使用的。然后，当空间不够时，将最长时间未被使用的节点，即链表尾部的数据淘汰，以释放内存空间。因为Linux的PageCache和MySQL的BufferPoolcache的基本数据单位都是页（Page）单位，所以会用“page”这个名字来代替“data”。传统LRU算法的实现思路是：当访问的页面在内存中时，直接将该页面对应的LRU链表节点移动到链表头部。当访问的页面不在内存中时，除了将页面放入LRU链表头部外，还将LRU链表尾部的页面剔除。例如下图中，假设LRU链表的长度为5，LRU链表的页码从左到右依次为1、2、3、4、5。如果访问了page3，因为page3已经在内存中了，就把page3移动到链表的头部，说明最近访问过。而如果接下来访问page8，因为page8不在内存中，而LRU链表的长度为5，所以必须淘汰数据腾出内存空间来缓存page8，所以最后5页会被淘汰。页码，然后将页码8添加到页眉。Linux和MySQL都没有使用传统的LRU算法，因为传统的LRU算法无法避免以下两个问题：预读失败导致缓存命中率下降；缓存污染导致缓存命中率下降；预读失败，怎么办？什么是预读机制？Linux操作系统为基于PageCache的读缓存机制提供了预读机制。一个例子是：应用程序只想读取文件A在磁盘上的偏移量中0-3KB范围内的数据。由于磁盘的基本读写单位是block（4KB），所以操作系统至少会读取0-4KB的内容，一个page可以放得下。但是由于空间局部性原则（靠近当前访问的数据的数据以后大概率会被访问），操作系统会选择偏移磁盘块偏移量[4KB,8KB],[8KB,12KB)和[12KB,16KB)加载到内存中，所以在内存中申请了3个额外的页；下图表示操作系统的预读机制：上图中，应用程序使用read系统调用读取4KB数据，实际上内核是使用预读机制（ReadaHead）机制完成16KB的读取data，即通过磁盘顺序读取将多个Page数据加载到PageCache中。这样，下次读取4KB数据后面的数据时，就不需要从磁盘读取了，直接在PageCache中命中数据即可。因此，预读机制的好处是减少磁盘I/O次数，提高系统磁盘I/O吞吐量。MySQLInnodb存储引擎的BufferPool也有类似的预读机制。当MySQL从磁盘加载一个页面时，它会提前加载它的相邻页面以减少磁盘IO。预读失败会导致什么问题？如果这些预加载的页面没有被访问到，就说明预读工作白费了，这就是预读失败。如果使用传统的LRU算法，“预读页”会被放在LRU链表的头部，当内存空间不足时，需要淘汰末尾的页。如果这些“预读页面”从来没有被访问过，就会出现一个很奇怪的问题。不会被访问的预读页面占据了LRU链表的前排，最后淘汰的页面可能是Hot数据，大大降低了缓存命中率。如何避免预读失败的影响？我们不能取消预读机制，因为我们害怕预读失败。在大多数情况下，空间局部性原则仍然有效。为了避免预读失败的影响，内存中的预读页面最好尽可能的短，让真正访问的页面移动到LRU链表的头部，从而保证实际读取热数据的页面尽可能长时间地保留在内存中。那么我们该如何避免呢？Linux操作系统和MySQLInnodb通过改进传统的LRU链表来避免预读失败的影响。具体改进如下：Linux操作系统实现了两种LRU链表：活跃LRU链表（active_list）和非活跃LRU链表（inactive_list）；MySQL的Innodb存储引擎在LRU链表上分为两个区域：young区和old区。这两种改进方法的设计思路是相似的。他们将数据分为冷数据和热数据，然后分别进行LRU算法。不再像传统的LRU算法那样，所有的数据只用一个LRU算法来管理。接下来说说Linux和MySQL如何避免预读失败的影响？Linux如何避免预读失败的影响？Linux操作系统实现了两种LRU列表：活跃的LRU列表（active_list）和非活跃的LRU列表（inactive_list）。activelistactivememorypage链表，存放最近访问过的（active）内存页；inactivelistinactivememorypage链表，存放很少访问（inactive）的内存页；用这两个LRU链表创建后，只需要将预读页添加到非活动链表区的头部即可。当页面真正被访问时，该页面被插入到活动链表的头部。如果预读页面没有被访问过，则将其从非活动列表中移除，这样就不会影响活动列表中的热点数据。接下来我给大家举个例子。假设activelist和inactivelist的长度都是5，内存中已经有10页如下：现在预读了一个编号为20的页，这个页只会被插入到inactivelist的头部，而inactivelist最后一页（第10页）将被淘汰。即使编号为20的预读页从未被访问过，它也不占据活动列表的位置，它会比活动列表中的页更早被淘汰。如果预读后立即访问20页，则将其插入到活动链表的头部，活动链表末尾的页（第5页）降级为非活动链表，作为链表的头部inactivelist，在此过程中不会淘汰任何数据。MySQL如何避免预读失败的影响？MySQL的Innodb存储引擎在LRU链表上分为两个区域，young区和old区。young区在LRU链表的前半部分，old区在后半部分。这两个区有自己的头尾节点，如下图：LRU链表中young区和old区的比例不一样，不是一对一的关系，而是一个7比3（默认比率）关系。划分这两个区域后，只需要将预读页添加到old区的头部，真正访问该页时，将页插入到young区的头部。如果预读页没有被访问过，就会从old区移除，这样就不会影响young区的热点数据。接下来我给大家举个例子。假设有一个长度为10的LRU链表，其中young区占70%，old区占30%。现在先读了一个编号为20的页，这个页只会被插入到老区的头部，而老区末尾的页（编号10）会被淘汰。如果page20从未被访问过，则不占据young区的位置，会比young区的数据先被淘汰。如果预读完后立即访问20页，则将其插入到young区的头部，将young区末尾的页面（第7页）挤入old区作为头部oldarea，在此过程中不会淘汰任何页面。缓存污染，怎么办？什么是缓存污染？虽然Linux（实现了两个LRU链表）和MySQL（划分两个区域）通过改进传统的LRU数据结构来避免预读失败的影响。但是如果仍然采用“只要数据被访问过一次，就将数据添加到活跃的LRU链表（或youngarea）的头部”的方式，那么仍然存在缓存污染的问题。当我们批量读取数据时，由于数据被访问一次，这些大量的数据会被添加到“活跃的LRU链表”中，然后将之前缓存在活跃的LRU链表（或年轻区）中的所有热点数据将被删除。淘汰了，如果这些大量的数据长时间不被访问，那么整个activeLRUlist（或者youngarea）就会被污染。缓存污染会导致哪些问题？缓存污染的影响是致命的。当这些热点数据再次被访问时，会因为cachemiss而产生大量的磁盘I/O，系统性能会急剧下降。我以MySQL为例，Linux中缓存污染的现象也是类似的。当某条SQL语句扫描到大量数据时，当BufferPool空间比较有限时，可能会替换掉BufferPool中的所有页，从而导致大量热数据被淘汰。访问时，由于cachemiss，会产生大量的磁盘I/O，MySQL性能会急剧下降。请注意，缓存污染不仅仅是在查询语句查询大量数据时出现的问题。即使查询结果集很小，也会造成缓存污染。比如在一个数据量非常大的表中，执行的语句是：select*fromt_userwherenamelike"%xiaolin%";这个查询的结果可能只有几条记录，但是由于这个语句，索引会失效，所以这个查询过程是全表扫描，然后会发生下面的过程：将从磁盘读取的页添加到LRU链表old区的头部；当从页中读取行记录时，即访问该页时，应将该页放在young区的头部；接下来，对该行记录的name字段和字符串xiaolin进行模糊匹配，如果满足条件则加入到结果集中；依此类推，直到扫描完表中表中的所有记录。经过这一番折腾，由于这条SQL语句访问的页面很多，每访问一个页面，就会添加到young区的头部，替换掉young区原有的热点数据，导致缓存命中率下降。那些在批量扫描时加入到young区的页面，如果长时间不被再次访问，就会污染young区。例如，假设你需要分批扫描：21、22、23、24、25，这五个页面将被一个一个访问（读取页面中的记录）。批量访问这些页面时，会一个一个的插入到young区的头部。可以看到原本在young区的第6页和第7页已经被淘汰，批量扫描的页面基本占据了young区。如果这些页面长时间不被访问，那么年轻的区域就造成了污染。如果第6页和第7页是热点数据，淘汰后，当SQL再次读取第6页和第7页时，会因为cachemiss从磁盘读取，降低了MySQL的性能。就是缓存污染的影响。如何避免缓存污染的影响？前面的LRU算法只要数据被访问过一次，就把数据添加到活跃的LRU链表（或youngarea）中。这个LRU算法进入活跃LRU链表的门槛太低了！形式上是因为阈值太低，当缓存污染发生时，很容易淘汰掉原本在活跃LRU链表中的热点数据。因此，只要提高进入活跃LRU链表（或年轻区）的门槛，就可以有效保证活跃LRU链表（或年轻区）中的热点数据不会被轻易替换。Linux操作系统和MySQLInnodb存储引擎分别是这样提高门槛的：Linux操作系统：当内存页被第二次访问时，该页从inactivelist升级到activelist。MySQLInnodb：第二次访问内存页面时，不会立即将页面从old区升级到young区，因为要判断停留在old区的时间：如果第二次访问时间是同第一次访问的时间在1秒以内（默认值），页面不会从老区升级到年轻区；如果第二次访问时间距离第一次访问时间超过1秒，则页面会从老区升级到年轻区；提高进入activeLRU链表（或youngarea）的门槛后，就很好的避免了缓存污染的影响。在批量读取数据时，如果这些大数据只被访问过一次，那么它们就不会进入活跃的LRU链表（或者youngarea），热点数据也不会被淘汰，只会停留在不活跃的LRU链表中list（或者老区），后续很快就会被淘汰。综上所述，传统的LRU算法无法避免以下两个问题：预读失效导致缓存命中率下降；缓存污染导致缓存命中率下降；为了避免“预读失效”的影响，Linux和MySQL使用传统的LRU链表进行了改进：Linux操作系统实现了两种LRU列表：活动LRU列表（activelist）和非活动LRU列表（inactivelist）。MySQLInnodb存储引擎在LRU链表上分为两个区域：young区和old区。但是如果仍然采用“只要数据被访问过一次，就将数据添加到活跃的LRU链表（或youngarea）的头部”的方式，那么仍然存在缓存污染的问题。为了避免“缓存污染”的影响，Linux操作系统和MySQLInnodb存储引擎分别提高了升级到热点数据的门槛：Linux操作系统：只有当内存页被第二次访问时，页面从非活动列表升级到活动列表。MySQLInnodb：第二次访问内存页面时，不会立即将页面从old区升级到young区，因为要判断停留在old区的时间：如果第二次访问时间是同第一次访问的时间在1秒以内（默认值），页面不会从老区升级到年轻区；如果第二次访问时间距离第一次访问时间超过1秒，则页面会从老区升级到年轻区；通过提高进入activelist（或youngarea）的门槛，可以很好的避免缓存污染的影响。
