前文有提到，缓存其中一种实施方式是利用硬件的读取速度的差异来做缓存加速，但是更高速的存储介质往往受限于成本（价格贵）或硬件限制（CPU缓存物理大小），其容量相较硬盘要小很多。
再加上根据二八原则，热点数据可认为只占20%，因此无论是处于实用还是成本考量，缓存容量都会比持久化的存储容量小很多，这就带来了一个问题：当缓存容量使用完时，再有新数据尝试写入缓存，应当如何处理？这就涉及到缓存的淘汰算法了。
swap
swap严格来说并不算淘汰数据，只是作为一个知识扩展点介绍一下。swap是操作系统层的一种策略：在物理内存不足时，使用磁盘的一部分区域当做内存使用。当要使用到被swap到磁盘上的数据时，再把数据读取到内存。
当然我们知道硬盘IO是比较耗时的操作，尤其相较内存的速率来说，因此swap会严重影响性能，再加上我们使用缓存其实就是想加速访问磁盘，所以缓存系统正常来说不会主动使用这个策略。但如果缓存宿主机的物理内存不足，可能会引发这个策略，算是缓存异常的一种考虑场景。
LRU（Least Recently Used）
这个应该是耳熟能详的一种淘汰算法了，个人最早了解是在学习操作系统原理的时候。其名为最近最少使用，实际策略就是淘汰最久未使用的数据。
Java里的 LinkedHashMap就提供了LRU的简单实现，下面我们用一个链表来简单说明。
head tail↓ ↓A -> B -> C -> D -> E
假设缓存容量为5, 此时数据按照上图排列，LRU的策略是：如果有新数据插入，会将新数据插入到头部，同时淘汰掉尾部数据；如果访问的数据已有，将其移动到头部，如下所示：
(访问已有数据D之后的情况)head tail↓ ↓D -> A -> B -> C -> E (插入新数据F之后的情况) head tail↓ ↓F -> A -> B -> C -> D
LRU算法，简单易理解，其设计依据就是被访问的数据，很可能再次被访问。LRU在很多场景都有实际的应用，但有一个较大的缺陷：大范围扫描数据时，缓存命中率会急剧下降。
假如我要做数据全量扫描，可以想象，LRU算法下，缓存内数据会被快速扫描到的数据替换掉，此时真正业务要读取的热点数据都无法命中缓存，只能重新从磁盘加载数据，而且很可能加载到缓存后，后又被扫描的数据顶替。
这个过程会持续到扫描完成，业务重新加载好对应的热点数据为止。
理论上使用LRU算法管理缓存时，如果有进行大范围扫描数据时，服务响应会剧烈抖动，这种价值较小的数据加载到缓存里，称之为缓存污染。在MySQL和Redis里，我们可以学习到大佬们是如何解决缓存污染的：
MySQL的策略：双段链表
MySQL作为持久化的关系型数据库，也使用了内存缓存来加速数据的读取，因此也需要考虑到内存的淘汰策略。其针LRU算法的缺陷，改进了扫描大量数据的情况下热点数据淘汰的问题。具体做法如下：
young old tail↓ ↓ ↓A -> B -> C -> D -> E -> F -> G -> H
MySQL将LRU链表分成两部分，young和old，实际上还在同一个链表处，但是有两个指针young和old。其具体算法策略如下：
1. young和old的长度为5:32. young、old 区域和LRU算法一样3. 新缓存数据只能存放在old处，不能直接进入young区域4. 如果old中的数据再次访问，并且距离上次访问已过去指定的时间（默认1s）， 则允许移动到young头部
这个策略就是为数据库的大范围扫描量身定制：young区域就是有价值的热点数据区域，old区域则是做一个缓冲：当有大范围数据扫描时，数据会短暂停留在old区域并且不停地被新数据替换，真正的热点数据并不受影响，从而保证了业务查询的缓存命中率。
Redis的策略：LFU（Least Frequently Used）
LFU即最少使用频率，这个算法里数据的权重，不是访问时间的先后，而是数据的访问次数，当次数一样时，才像LRU一样对比访问时间。
具体来说，Redis内部在LRU的基础上，为每个数据还增加了访问计数器，淘汰时，访问次数少的数据会优先淘汰。当然Redis为了节约存储空间，只用了8bit的空间(最大值255)存储访问次数，如果运行一段时间后，大量的数据都访问了255次以上，这个算法就退化为LRU算法了，为了让次数不那么快地达到上限，Redis采用了概率增加的方案：即每次访问发生时，计算一个概率值，如果概率通过则加1，否则不变，这个增长的概率也可以通过配置调整，这个设计也非常有意思。
需要说明的是，Redis提供了多种数据淘汰策略供配置选择，LFU只是其中一种，用户可以按需选择符合业务的淘汰策略。
上面的内容基本上都是在讲单机或者将缓存作为一个整体黑盒来讨论，接下来就来简单地讨论一下分布式缓存，其实分布式缓存也就是多个单体缓存通过一定的协作方式组成缓存集群，来保证缓存服务的高可用及支撑高性能的缓存服务。
数据分片
由于现如今业务的不断发展和摩尔定律的逐渐失效，单体的缓存无论是性能、容量可用性等方面都很难满足很多业务的需要。更何况像Redis这样的典型缓存，在大容量下也会引入一些新问题：例如故障恢复时间较长，fork操作阻塞时间过长等等问题，因此引入缓存集群，将数据分布到多个缓存节点就是一个更优的方案了。
而且由于缓存服务是存储数据，属于有状态的服务，不能像无状态的请求负载均衡器一样，采用随机分发或者顺序等分发策略。对于一份数据我们只能到特定的节点上去获取，而这是典型的哈希分布算法。
哈希算法，针对缓存的key取hashCode, 用hashCode对节点总个数取模，得到该数据所在节点，例如哈希值为93，缓存集群有5个，则93 % 5 = 3，去标号为3的节点取数据 。
但这种策略有个很大的问题，就是节点数量一旦变化，所有数据的分布可能都会重新调整。也即，调整节点数导致缓存全部失效，引发雪崩。为了解决这个问题，比较流行的办法是采用的是一致性Hash算法。
一致性Hash算法
普通的Hash算法，是按服务节点分配哈希槽，哈希槽和服务节点一一对应。一致性Hash算法，哈希槽和节点是多对一的关系，通过预先分配大量的哈希槽（例如2的32次方个槽）组成环形，然后再配置这些槽对节点的映射关系。
如下图所示：
图中由2的32次方个点组成的圆环上，每一个点是一个哈希槽，然后我们假设有A,B,C,D四个服务节点，我们将这些节点 映射在如图所示的位置上。我们可以约定，每个哈希槽的所属数据节点是顺时针查找到的第一个节点，因此图中K1, K2的数据应当去B节点上读写。
根据这个算法，当我们减少一个节点时，仅有归属到这个节点的数据会迁移到其下一个节点，如下图：
当B节点下掉之后，原本归属在B节点的K1,K2数据顺势迁移到了下一个节点C上。这样，就把减少节点的数据迁移控制在了一个较小的范围，即：原A~B这段范围的数据。增加一个节点的情况也容易推论，当我们节点数较多时，增减节点的数据影响范围就很小。
这样，通过增加一层哈希槽到数据节点的映射，将增减节点的影响由全量失效，优化为了部分失效。这就是一致性hash的优势所在。但是，一致性hash也有其缺陷：雪崩效应和数据倾斜。
雪崩效应则是由于节点失效后，数据转移至下一节点，造成下一个节点承受双倍数据量和访问量，可能造成下一个节点的崩溃，这样，再下一个节点将承担三倍的压力，从而全部宕机。当然，高可用架构下每个节点还会配备从库，宕机的情况下可以通过从库选主来恢复服务，从而减小雪崩发生的概率。
数据倾斜不算一致性hash特有的问题，就算是普通集群也会有这个问题，而在一致性hash里，解决这个问题的思路，是再加一层映射层：哈希环上某个槽顺时针找到的节点仍旧是虚拟节点，虚拟节点再映射到实际节点。这样，我们可以虚拟多个节点数据出来，通过配置虚拟节点到实际节点的映射关系，甚至是动态调整映射关系来维护节点负载的均衡。读者可以自行推导一下这个情况。
那么至此，缓存相关的知识点暂时介绍完成了。需要补充说明的是，任何方案都会有其优势及缺陷，即使我们在引入业界通用的技术方案时，也不应只盯着其优点，也需要考虑这个方案的缺陷及负面问题。
