关键词：
前提概要
无论是浏览器缓存(如果是chrome浏览器，可以通过chrome:://cache查看)，还是服务端的缓存(通过memcached或者redis等内存数据库)。缓存不仅可以加速用户的访问，同时也可以降低服务器的负载和压力。那么了解常见的缓存淘汰算法的策略和原理就显得特别重要。
常见的缓存算法
- LRU (Least recently used) 最近最少使用，如果数据最近被访问过，那么将来被访问的几率也更高。
- LFU (Least frequently used) 最不经常使用，如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小。
- FIFO (Fist in first out) 先进先出， 如果一个数据最先进入缓存中，则应该最早淘汰掉。
LRU缓存
像浏览器的缓存策略、memcached的缓存策略都是使用LRU这个算法，LRU算法会将近期最不会访问的数据淘汰掉。LRU如此流行的原因是实现比较简单，而且对于实际问题也很实用，良好的运行时性能，命中率较高。下面谈谈如何实现LRU缓存：
新数据插入到链表头部：
每当缓存命中（即缓存数据被访问），则将数据移到链表头部，当链表满的时候，将链表尾部的数据丢弃。
LRU Cache具备的操作：
set(key,value)：如果key在hashmap中存在，则先重置对应的value值，然后获取对应的节点cur，将cur节点从链表删除，并移动到链表的头部；
如果key在hashmap不存在，则新建一个节点，并将节点放到链表的头部。当Cache存满的时候，将链表最后一个节点删除即可。
get(key)：如果key在hashmap中存在，则把对应的节点放到链表头部，并返回对应的value值；如果不存在，则返回-1。
LRU的c++实现
LRU实现采用双向链表 + Map 来进行实现。这里采用双向链表的原因是：如果采用普通的单链表，则删除节点的时候需要从表头开始遍历查找，效率为O(n)，采用双向链表可以直接改变节点的前驱的指针指向进行删除达到O(1)的效率。
使用Map来保存节点的key、value值便于能在O(logN)的时间查找元素,对应get操作。
双链表节点的定义：
struct CacheNode
int key; // 键
int value; // 值
CacheNode *pre, *next; // 节点的前驱、后继指针
CacheNode(int k, int v) : key(k), value(v), pre(NULL), next(NULL)
;
对于LRUCache这个类而言，构造函数需要指定容量大小:
LRUCache(int capacity)
size = capacity; // 容量
head = NULL; // 链表头指针
tail = NULL; // 链表尾指针
双链表的节点删除操作：
void remove(CacheNode *node)
if (node -> pre != NULL)
node -> pre -> next = node -> next;
else
head = node -> next;
if (node -> next != NULL)
node -> next -> pre = node -> pre;
else
tail = node -> pre;
将节点插入到头部的操作：
void setHead(CacheNode *node)
node -> next = head;
node -> pre = NULL;
if (head != NULL)
head -> pre = node;
head = node;
if (tail == NULL)
tail = head;
get(key)操作的实现比较简单，直接通过判断Map是否含有key值即可，如果查找到key，则返回对应的value，否则返回-1;
int get(int key)
map<int, CacheNode *>::iterator it = mp.find(key);
if (it != mp.end())
CacheNode *node = it -> second;
remove(node);
setHead(node);
return node -> value;
else
return -1;
set(key, value)操作需要分情况判断。如果当前的key值对应的节点已经存在，则将这个节点取出来，并且删除节点所处的原有的位置，并在头部插入该节点；如果节点不存在节点中，这个时候需要在链表的头部插入新节点，插入新节点可能导致容量溢出，如果出现溢出的情况，则需要删除链表尾部的节点。
void set(int key, int value)
map<int, CacheNode *>::iterator it = mp.find(key);
if (it != mp.end())
CacheNode *node = it -> second;
node -> value = value;
remove(node);
setHead(node);
else
CacheNode *newNode = new CacheNode(key, value);
if (mp.size() >= size)
map<int, CacheNode *>::iterator iter = mp.find(tail -> key);
remove(tail);
mp.erase(iter);
setHead(newNode);
mp[key] = newNode;
至此，LRU算法的实现操作就完成了，完整的源码参考：https://github.com/cpselvis/leetcode/blob/master/solution146.cpp
补充：
LRU和LFU的区别：
- LRU是最近最少使用页面置换算法(Least Recently Used),也就是首先淘汰最长时间未被使用的页面!
- LFU是最近最不常用页面置换算法(Least Frequently Used),也就是淘汰一定时期内被访问次数最少的页!
若按LRU算法,应换页面1(1页面最久未被使用)
但按LFU算法应换页面3(十分钟内,页面3只使用了一次)
- LRU关键是看页面最后一次被使用到发生调度的时间长短,
- LFU关键是看一定时间段内页面被使用的频率!
参考资料
学习资料
分布式技术专题「分布式缓存专题」针对性分析缓存与数据库一致性如何解决
数据缓存由来在实际的业务场景中，一定有很多需要做数据缓存的场景，比如售卖商品页面，包括了许多并发访问量很大的数据，它们可以称作是是"热点”数据，这些数据有一个特点，就是更新频率低，读取频率高，这些数据... 查看详情
分布式技术专题「分布式技术架构」一文带你厘清分布式事务协议及分布式一致性协议的算法原理和核心流程机制（上篇）
...了，要不就是把门槛抬的很高，所以针对于一些分布式角度而言的技术知识点，更是必备条件以及重中之重了。那么今天笔者就针对于分布式协议以及一些算法原理进行详细的分析和原理介绍。分布式体系分布式体系... 查看详情
分布式技术专题「架构实践于案例分析」总结和盘点目前常用分布式技术特别及问题分析
分布式架构互联⽹架构演进单体应⽤架构定义⼀个归档包（例如war格式）包含所有功能的应⽤程序，我们通常称为单体应⽤。⽽架构单体应⽤的⽅法论，就是单体应⽤架构。架构示意图优缺点分析初期：架构简单，统一化管理真... 查看详情
分布式缓存一致性hash算法理解
今天阅读了一下大型网络技术架构这本苏中的分布式缓存一致性hash算法这一节，针对大型分布式系统来说，缓存在该系统中必不可少，分布式集群环境中，会出现添加缓存节点的需求，这样需要保障缓存服务器中对缓存的命中... 查看详情
分布式技术专题「架构实践于案例分析」总结和盘点目前常用分布式技术特别及问题分析
分布式架构互联⽹架构演进单体应⽤架构定义⼀个归档包（例如war格式）包含所有功能的应⽤程序，我们通常称为单体应⽤。⽽架构单体应⽤的⽅法论，就是单体应⽤架构。架构示意图优缺点分析初期：架构... 查看详情
kafka专题
...提供一个统一、高通量、低等待的平台。 3、Kafka是一个分布式消息队列。 消息根据Topic来 查看详情
分布式技术专题「架构实践于案例分析」盘点分布式服务的（无状态有状态）认证实现方案
⽆状态vs有状态有状态、⽆状态是什么有状态：服务器端需要保存请求的相关信息，每个请求可以默认地使⽤以前的请求信息⽆状态：服务器端不记录请求的相关信息，服务器处理的内容完全来⾃请求所携带的信息，以及其他服... 查看详情
分布式技术专题「架构实践于案例分析」总结和盘点目前常用分布式事务特别及问题分析（下）
...一个计算机问题最简单的方法：“恰好”不需要解决它！分布式事务方案设计实际运用理论时进行架构设计时，许多人容易犯“手里有了锤子，看什么都觉得像钉子”的错误，设计方案时考虑的问题场景过多，各种重试，各种补... 查看详情
分布式技术专题「架构实践于案例分析」总结和盘点目前常用分布式事务特别及问题分析（上）
分布式事务分布式事务的场景什么场景下会出现分布式事务？TX协议⼀种分布式事务协议，包含⼆阶段提交（2PC），三阶段提交（3PC）两种实现。二阶段提交方案：强一致性事务的发起者称协调者，事务的执行者称参与者。处理... 查看详情
分布式技术专题「架构实践于案例分析」总结和盘点目前常用分布式事务特别及问题分析（中）
基于MQ的分布式事务（MQ事务最终一致性）方案简介基于MQ的分布式事务方案其实是对本地消息表的封装，将本地消息表基于MQ内部，其他方面的协议基本与本地消息表一致。本地消息表：最终一致性方案简介本地消息表的方案最... 查看详情
分布式技术专题「架构实践于案例分析」总结和盘点目前常用分布式事务特别及问题分析（中）
基于MQ的分布式事务（MQ事务最终一致性）方案简介基于MQ的分布式事务方案其实是对本地消息表的封装，将本地消息表基于MQ内部，其他方面的协议基本与本地消息表一致。本地消息表：最终一致性方案简介本... 查看详情
分布式技术专题「架构实践于案例分析」总结和盘点目前常用分布式事务特别及问题分析（上）
分布式事务分布式事务的场景什么场景下会出现分布式事务？TX协议⼀种分布式事务协议，包含⼆阶段提交（2PC），三阶段提交（3PC）两种实现。二阶段提交方案：强一致性事务的发起者称协调者&#x... 查看详情
分布式技术专题「lvs负载均衡」全面透析web基础架构负载均衡lvs机制的原理分析指南
前提概要在大规模互联网应用中，负载均衡设备是必不可少的组成部分，源于互联网应用的高并发和大流量的冲击压力场景下，通常会在服务端部署多个无状态的应用服务器和若干有状态的存储服务器（数据库、缓存等等）实现... 查看详情
大厂java高级多套面试专题整理集合，已获万赞
...明白你就上不去呀。再看美团亿级流量Redis实战，Redis分布式锁、session、缓存与数据库一致性问题、缓存雪崩等之类的都是重中之重的技术点，必须掌握，没得商量。看 查看详情
分布式技术专题「lvs负载均衡」全面透析web基础架构负载均衡lvs机制的原理分析指南(代码片段)
前提概要在大规模互联网应用中，负载均衡设备是必不可少的组成部分，源于互联网应用的高并发和大流量的冲击压力场景下，通常会在服务端部署多个无状态的应用服务器和若干有状态的存储服务器（数据库、... 查看详情
分布式技术专题「系统服务优化系列」web应用服务的性能指标优化开发指南（基础篇）(代码片段)
前提概要针对于Web应用系统是现在计算机领域里面最常见的信息载体了，整个服务并不是一个孤立的个体，一个较为简单的Web应用主要是由前端视图页面、后端系统支撑、应用服务器、负载代理服务器、数据库等等其他... 查看详情
算法技术专题如何用java实现一致性hash算法（consistenthashing）（上）(代码片段)
...应用越来越广泛；一致性hash的目的一致性哈希算法是分布式系统中常用的算法，一致性哈希算法解决了普通余数Hash算法伸缩性差的问题，可以保证在上线、下线服务器的情况下 查看详情
搞懂分布式技术13：缓存的那些事
搞懂分布式技术13：缓存的那些事缓存和它的那些淘汰算法们为什么我们需要缓存？很久很久以前，在还没有缓存的时候……用户经常是去请求一个对象，而这个对象是从数据库去取，然后，这个对象变得越来越大，这个用户每... 查看详情