什么是缓存污染？由于缓存的读取速度比非缓存要快上许多，所以在高性能场景下，系统在读取数据时，是首先从缓存中查找需要的数据，如果找到了则直接读取效果，如果找不到的话，则从内存或者硬盘中查找，再将查找到的效果存入缓存，以备下次使用。实际上，对于一个系统来说，缓存的空间是有限且名贵的，我们不行能将所有的数据都放入缓存中举行操作，即便可以数据宁静性也得不到保证，而且，如果缓存的数据量过大大，其速度也会变得越来越慢。

这个时候就需要思量缓存的淘汰机制，可是淘汰哪些数据，又保留哪些数据，这是一个问题。如果处置惩罚不恰当，就会造成“缓存污染”问题。而缓存污染，是指系统将不常用的数据从内存移到缓存，造成常用数据的挤出，降低了缓存效率的现象。

解决缓存污染的算法LFU算法LFU，英文名Least Frequently Used，字面意思就是最不经常使用的淘汰掉算法，是通过数据被会见的频率来判断一个数据的热点情况。其焦点理念是“历史上这个数据被会见次数越多，那么未来其被会见的次数也多”。LFU中每个数据块都有一个引用计数器，所有数据块根据引用数从大到小的排序。

步骤：1.新数据插入到尾部，并将计数设置为1；2.当行列中的数据被会见后，引用计数+1，然后重新排序，保持引用次数从大到小排序；3.当空间不足，需要淘汰数据时，将尾部引用计数最小的数据块删除。分析：由于是凭据频数举行热点判断和淘汰，所以先天具备制止偶发性、周期性批量操作导致暂时非热点数据大量涌入缓存，挤出热点数据的问题。虽然具备这种先天优势，但依旧存在另一种缓存污染问题，即历史热点数据污染当前热点数据，如果系统会见模式发生了改变，新的热点数据需要计数累加凌驾旧热点数据，才气将旧热点数据举行淘汰，造成热点效应滞后的问题。

庞大度与价格：每次操作都需要举行计数和排序，而且需要维护每个数据块计数情况，会占用较高的内存与cpu。一个小思考，凭据LFU算法，如何以O(1)时间庞大度实现get和put操作缓存？ LFU-Aging算法LFU-Aging是基于LFU的革新算法，目的是解决历史热点数据对当前热点数据的污染问题。有些数据在开始时使用次数许多，但以后就不再使用，这类数据将会长时间留在缓存中，所以“除了会见次数外，还要思量会见时间”，这也是LFU-Aging的焦点理念。虽然算法将时间纳入了考量规模，但LFU-Aging并不是直接记载数据的会见时间，而是增加了一个最大平均引用计数的阈值，然后通过当前平均引用计数来标识时间，换句话说，就是将当前缓存中的平均引用计数值看成当前的生命年月，当这个生命年月凌驾了预设的阈值，就会将当前所有计数值减半，形成指数衰变的生命年月。

分析：优点是当会见模式发生改变的时候，生命年月的指数衰变会使LFU-Aging能够更快的适用新的数据会见模式，淘汰旧的热点数据。庞大度与价格：在LFU的基础上又增加平均引用次数判断和统计处置惩罚，对cpu的消耗更高，而且当平均引用次数凌驾指定阈值（Aging）后，还需要遍历每一个数据块的引用计数，举行指数衰变。

Window-LFU算法Window-LFU顾名思义叫做窗口期LFU，区别于原义LFU中记载所有数据的会见历史，Window-LFU只记载已往一段时间内（窗口期）的会见历史，相当于给缓存设置了有效期限，逾期数据不再缓存。当需要淘汰时，将这个窗口期内的数据根据LFU算法举行淘汰。

分析：由于是维护一段窗口期的记载，数据量会比力少，所以内存占用和cpu消耗都比LFU要低。而且这段窗口期相当于给缓存设置了有效期，能够更快的适应新的会见模式的变化，缓存污染问题基本不严重。

庞大度与价格：维护一段时期内的数据会见记载，并对其排序。LRU算法LRU算法，英文名Least Recently Used，意思是最近最少使用的淘汰算法，凭据数据的历史会见记载来举行淘汰数据，焦点思想是“如果数据最近被会见过1次，那么未来被会见的概率会更高”，类似于就近优先原则。步骤：1.新数据插入到链表头部；2.每当掷中缓存，便将掷中的缓存数据移到链表头部；3.当链表满的时候，将链表尾部的数据抛弃。分析：偶发性的、周期性的批量操作会使暂时数据涌入缓存，挤出热点数据，导致LRU热点掷中率急剧下降，缓存污染情况比力严重。

庞大度与价格：数据结构庞大度较低；每次需要遍历链表，找到掷中的数据块，然后将数据移到头部。LRU-K算法LRU-K是基于LRU算法的优化版，其中K代表最近会见的次数，从某种意义上，LRU可以看作是LRU-1算法，引入K的意义是为相识决上面所提到的缓存污染问题。其焦点理念是从“数据最近被会见过1次”蜕酿成“数据最近被会见过K次，那么未来被会见的概率会更高”。LRU-K与LRU区别是，LRU-K多了一个数据会见历史记载行列（需要注意的是，会见历史记载行列并不是缓存行列，所以是不生存数据自己的，只是生存对数据的会见记载，数据此时依旧在原始存储中），行列中维护着数据被会见的次数以实时间戳，只有当这个数据被会见的次数大于即是K值时，才会从历史记载行列中删除，然后把数据加入到缓存行列中去。

步骤： 数据第一次被会见时，加入到历史会见记载行列中，会见次数为1，初始化会见时间戳；如果数据会见次数没有到达K次，则会见次数+1，更新时间戳。当行列满了时，根据某种规则（LRU或者FIFO）将历史记载淘汰。为了制止历史数据污染未来数据的问题，还需要加上一个有效期限，对凌驾有效期的会见记载，举行重新计数。

（可以使用懒处置惩罚，即每次对会见记载做处置惩罚时，先将记载中的会见时间与当前时间举行对比，如果时间距离凌驾预设的值，则会见次数重置为1并更新时间戳，表现重新开始计数）当数据会见计数大于即是K次后，将数据从历史会见行列中删除，更新数据时间戳，生存到缓存行列头部中（缓存行列时间戳递减排序，越到尾部距离当前时间越长）；缓存行列中数据被再次会见后，将其移到头部，并更新时间戳；缓存行列需要淘汰数据时，淘汰缓存行列中排在末尾的数据，即：淘汰“倒数第K次会见离现在最久”的数据。分析：LRU-K降低了“缓存污染”带来的问题，掷中率比LRU要高。

实际应用中LRU-2是综合种种因素后最优的选择，LRU-3或者更大的K值掷中率会高，但适应性差，一旦会见模式发生变化，需要大量的新数据会见才气将历史热点会见记载清除掉。庞大度与价格：LRU-K行列是一个优先级行列。

由于LRU-K需要记载那些被会见过，但还没有放入缓存的工具，导致内存消耗会许多。URL-Two queues算法URL-Two queues算法类似于LRU-2，差别点在于URL-Two queues将LRU-2算法中的会见历史行列（注意这不是缓存数据的）改为一个FIFO缓存行列，即：URL-Two queues算法有两个缓存行列，一个是FIFO行列（First in First out，先进先出），一个是LRU行列。当数据第一次会见时，URL-Two queues算法将数据缓存在FIFO行列内里，当数据第二次被会见时，则将数据从FIFO行列移到LRU行列内里，两个行列各自根据自己的方法淘汰数据。步骤：新会见的数据先插入到FIFO行列中；如果数据在FIFO行列中一直没有被再次会见，则最终根据FIFO规则淘汰；如果数据在FIFO行列中被再次会见，则将数据从FIFO删除，加入到LRU行列头部；如果数据在LRU行列再次被会见，则将数据移到LRU行列头部；LRU行列淘汰末尾的数据。

分析：URL-Two queues算法和LRU-2算法掷中率类似，可是URL-Two queues会淘汰一次从原始存储读取或盘算数据的操作。掷中率要高于LRU。庞大度与价格：需要维护两个行列，价格是FIFO和LRU价格之和。

五三LRU算法emmmm...这个名字其实是我取的，或许是这种算法还没有被命名？固然，这是一个玩笑话。我是在mysql底层实现里发现这个算法的，mysql在处置惩罚缓存淘汰时是用的这个方法，有点像URL-Two queues的变体，只是我们只需要维护一个行列，然后将行列根据5:3的比例举行支解，5的那部门叫做young区，3的那部门叫做old区。

详细是怎么样的请先看我把图画出来：步骤：第一次会见的数据从行列的3/8处位置插入；如果数据再次被会见，则移动到行列头部；如果数据没有被再会见，会逐步被热点数据驱逐向下移；淘汰尾部数据。分析：五三LRU算法算作是URL-Two queues算法的变种，原理其实是一样的，只是把两个行列合二为一个行列举行数据的处置惩罚，所以掷中率和URL-Two queues算法一样。庞大度与价格：维护一个行列，价格较低，可是内存占用率和URL-Two queues一样。

Multi Queue算法Multi Queue算法凭据会见频率将数据划分为多个行列，差别的行列具有差别的会见优先级，其焦点思想是“优先缓存会见次数多的数据”。Multi Queue算法将缓存划分为多个LRU行列，每个行列对应差别的会见优先级。会见优先级是凭据会见次数盘算出来的，例如：Q0，Q1....Qn代表差别的优先级行列，Q-history代表从缓存中淘汰数据，但记载了数据的索引和引用次数。

步骤：新插入的数据放入Q0；每个行列根据LRU治理数据，再次会见的数据移动到头部；当数据的会见次数到达一定次数，需要提升优先级时，将数据从当前行列删除，加入到高一级行列的头部；为了防止高优先级数据永远不被淘汰，当数据在指定的时间里会见没有被会见时，需要降低优先级，将数据从当前行列删除，加入到低一级的行列头部；需要淘汰数据时，从最低一级行列开始根据LRU淘汰；每个行列淘汰数据时，将数据从缓存中删除，将数据索引加入Q-history头部；如果数据在Q-history中被重新会见，则重新盘算其优先级，移到目的行列的头部；Q-history根据LRU淘汰数据的索引。分析：Multi Queue降低了“缓存污染”带来的问题，掷中率比LRU要高。庞大度与价格：Multi Queue需要维护多个行列，且需要维护每个数据的会见时间，庞大度比LRU高。Multi Queue需要记载每个数据的会见时间，需要定时扫描所有行列，价格比LRU要高。

虽然Multi Queue的行列看起来数量比力多，但由于所有行列之和受限于缓存容量的巨细，因此这里多个行列长度之和和一个LRU行列是一样的，因此行列扫描性能也相近。

本文来源：ROR体育首页-www.beijingmba.com