聊聊Mysql中的LRU算法

record-2

6

我们在有记录的时候继续插入新记录

4

record-9

这个时候来了一个新的record-x，那么这record-x按照我们定的规矩，应该放到首位！但是bp已经满了啊！所以record-10应该删除

record-4

record-8

3

record-7

我们总是将新插入的缓存放到队列的最前面，因为这条刚插入的记录最有可能接下来被查询使用到

record-y

record-6

record-1

5

这个时候我们查找record-1

1

record-3

0

其头部浅色的缓存是年轻代很活跃，而尾部深色的缓存是老年代，要死不活的样子。。。随时被干掉

7

8

record-10

如果我们查到了老年代的一条记录呢？

select n1

2

record-n1

可以看到普通的缓存更新其实还是和之前没什么区别，我们正常对待！

insert

如果更新一批记录（select * from t）

9

record-5

select r1

record-x

可以看到，查询到老年代的缓存的时候，处理方式是一样的，会放到首部位置并标记为年轻代，而原来处于年轻代末尾的record-4则后移并且降级为老年代了

可以看到record-1由于被查询后，使用次数加1，所以优先级提高，放到了首位，而record-2也退到第二的位置

record-n2

这个时候我们记录新的缓存record-x

record-n3

到这里，其实普通的LRU算法已经实现完成了！就是这么简单，不过简单却好用！但是，事情往往总是和我们预想的不一样，当你把这个逻辑更新到生产环境期待着一波性能飞跃，跑一段时间后，就会发现这特么不对劲啊！为啥感觉mysql还是这么慢呢？然后你辛苦的检查同事写的程序发现，有一个人写了这么一个sql：select * from table！然后你去检查一下这个表的数据量，发现竟然达到了2000w数量。。。这按照我们的理解，岂不是每次执行这个sql的时候都将这2000w的数据全部刷到bp里面？？？？wtf ？？？这样不就有可能把我们原本高频使用的缓存给淘汰了？？？所以mysql的作者早就想到了这些，就像mysql的作者从来不相信那些开发写的sql一样，你把sql发送到mysql服务器，人家会先优化一波你的sql，真正执行的sql甚至有可能和你给的完全不同！嘿嘿嘿，实事就是这样，别不服气，优化后的sql肯定更合理（毕竟mysql都是别人写出来的），用什么索引人家也会替你想好。。。扯远了。。。那么，mysql的作者这么处理这个问题呢？=》将LRU链表划分区域！(冷热分离)1. 一部分存储使用频率很高的缓存，这些数据叫热数据也叫做 young区域（特别像jvm里面的年轻代）2. 一部分存储使用频率不是很高的缓存，这些数据叫冷数据也叫做 old区域（特别像jvm里面的老年代）

我们主要目的是减少bp的移动次数，减少不必要的链表移动的开销，所以我们可以稍微保持整个缓存靠前的的数据不动，啥意思呢？比如图中年轻代有5个位置，我们规定：1. 如果缓存命中前三个位置，不去移动到头部，反正都已经很靠前了。2. 如果在靠后的缓存被查询命中了，那么就再往前提，这样就可以减少一部分移动的开销了吧。当然，关于lru算法的优化，太多了。。。网上也是各种五花八门的优化方案，大家感兴趣自己去搜着看看。。。

这个时候我们记录新的缓存record-y（这里只是一条）

       各位老哥，是不是以为到这里就结束了？！年轻！这里隐藏了一个问题，我们知道数据库的访问频率是很高的，如果来一次查询就更新一次buffer pool的话那开销是很大的！估计cpu很高！所以还能不能再继续优化一把呢？！我都这么说了，肯定是能的！那还有什么优化办法呢！->

   mysql也是一个普通的应用，它也有自己的缓存，那么mysql是如何使用lru算法来处理自己的缓存的呢，这其中又有哪些     优化呢？这里做一下记录，顺便学习下优秀的设计和巧妙的处理方式！

呐，区别来了！这种大批量的更新，我们并不会动年轻代，会在老年代上搞动作！这样就避免上面我们说的大批量的将活跃缓存给搞了

假设我们的队列这个时候已经塞满了

经过分代后的缓存实际是这样的

当缓存为空的时候，我们插入一条记录

LRU(Least Recently Used)算法在很多应用中都有实现，当然主要还是用于清理缓存。这个算法很简单，一句话总结就是：最近越少使用的数据越优先被清理，某个数据你在最近使用的越频繁，那么它的优先级越高！

batch

首先，我们说mysql的缓存其实是buffer pool，这个东西十分重要！mysql本身是一个io密集型的应用，我们执行sql进行crud的时候其实都是磁盘操作，但是如果真的全是磁盘操作的话，那估计会慢疯了！所以mysql的设计者也搞了一个缓存叫：buffer pool。我们对数据的处理都是在这个bp中处理的，有了这个bp之后就可以很大的程度上减少磁盘操作，这样不就提升了性能嘛！不过怎么使用buffer pool的这里我们按下不表，因为不是我们的重点！单说buffer pool本身它肯定是有大小的，像我的应用使用的mysql服务器内存是8g，dba给buffer pool分配了4g的大小。看上去很大，也确实很大，但是经不住疯狂的刷啊，是缓存总有耗尽的一天，如果耗尽了之后，新的缓存来了，那么要如何处理呢？我们先看看根据标准的lru算法，会如何处理呢？！（如右图，我们假设有一个10块大小的缓存空间）

可以看到，处于末尾的record-10就这样被我无情的删除了，等下次如果10被检索的时候才有机会重新入队列里面。