Redis版本升级的新功能优化

Redis 官网：https://redis.io

Redis 中文网：http://www.redis.cn/update.html

Redis借鉴了Linux操作系统对于版本号的命名规则：

如果版本号第二位是奇数，则为非稳定版本（例如2.7、2.9、3.1）

如果版本号第二位是偶数，则为稳定版本（例如2.6、2.8、3.0、3.2）

当前奇数版本就是下一个稳定版本的开发版本，例如2.9版本是3.0版本的开发版本。

所以，我们在生产环境通常选取偶数版本的Redis，如果对于某些新的特性想提前了解和使用，可以选择最新的奇数版本。

追踪学习最新技术的途径

做技术，经常说要跟踪最新的技术前沿知识，不断学习，掌握新技术。

那么，如何高效、快速的跟踪最新技术潮流呢？

1）跟踪技术栈的最新版本的知识更新点

2）跟踪行业巨头的技术博客、技术分享

3）在自己的项目实践中，应用新技术、并总结

关注新版本的特性，新功能优化是技术人必备的学习内容，可通常读者容易忽略....

Redis 版本升级的新功能优化

Redis 6.0

2020年8月27日

1、多线程IO

Redis的多线程部分只是用来处理网络数据的读写和协议解析，执行命令仍然是单线程顺序执行。

所以，我们不需要去考虑控制 key、lua、事务，LPUSH/LPOP 等等的并发及线程安全问题。

Redis6.0的多线程默认是禁用的，只使用主线程。

1）如需开启多线程，需要修改redis.conf配置文件：io-threads-do-reads yes。

2）开启多线程后，还需要设置线程数，否则是不生效的。

修改redis.conf配置文件：io-threads ，关于线程数的设置，官方有一个建议：4核的机器建议设置为2或3个线程，8核的建议设置为6个线程，线程数一定要小于机器核数。还需要注意的是，线程数并不是越大越好，官方认为超过了8个基本就没什么意义了。

更多关于redis 6.0多线程的讲解，请查看：Redis 6.0 新特性-多线程连环13问

2、SSL支持

连接支持SSL协议，更加安全。

3、ACL支持

在之前的版本中，Redis都会有这样的问题：用户执行FLUSHALL，整个数据库就空了

在以前解决这个问题的办法，可能是在Redis配置中将危险命令进行rename，这样将命令更名为随机字符串或者直接屏蔽掉，以满足需要。当有了ACL之后，你就可以控制比如：这个连接只允许使用RPOP，LPUSH这些命令，其他命令都无法调用。

Redis ACL（Access Control List，访问控制列表）该功能允许根据可以执行的命令和可以访问的键，来限制某些连接。它的工作方式是：在客户端连接之后，需要客户端进行身份验证，以提供用户名和有效密码：如果身份验证阶段成功，则将连接与指定用户关联，并且该用户具有指定的限制权限。可以对Redis进行配置，使新连接通过“默认”用户进行身份验证（这是默认配置），但是只能提供特定的功能子集。

在默认配置中，Redis 6（第一个具有ACL的版本）的工作方式与Redis的旧版本完全相同，也就是说，每个新连接都能够调用每个可能的命令并访问每个键，因此ACL功能对于客户端和应用程序与旧版本向后兼容。同样，使用requirepass配置指令配置密码的旧方法仍然可以按预期工作，但是现在它的作用只是为默认用户设置密码。

Redis AUTH命令在Redis 6中进行了扩展，因此现在可以在两个参数的形式中使用它：

AUTH <username> <password>

也可按照旧格式使用时，即：

AUTH <password>

Redis提供了一个新的命令ACL来维护Redis的访问控制信息，详情见：https://redis.io/topics/acl

4、RESP3

RESP（Redis Serialization Protocol）是 Redis 服务端与客户端之间通信的协议。Redis 6之前使用的是 RESP2，而Redis 6开始在兼容RESP2的基础上，开始支持RESP3。在Redis 6中我们可以使用HELLO命令在RESP2和RESP3协议之间进行切换：

# 使用RESP2协议
HELLO 2
# 使用RESP3协议
HELLO 3

推出RESP3的目的：

一是因为希望能为客户端提供更多的语义化响应（semantical replies），降低客户端的复杂性，以开发使用旧协议难以实现的功能；

另一个原因是为了实现 Client side caching（客户端缓存）功能。详细见：RESP3 specification

127.0.0.1:6380> HSET myhash a 1 b 2 c 3
(integer) 3
127.0.0.1:6380> HGETALL myhash
1) "a"
2) "1"
3) "b"
4) "2"
5) "c"
6) "3"
127.0.0.1:6380> HELLO 3
1# "server" => "redis"
2# "version" => "6.0"
3# "proto" => (integer) 3
4# "id" => (integer) 5
5# "mode" => "standalone"
6# "role" => "master"
7# "modules" => (empty array)
127.0.0.1:6380> HGETALL myhash
1# "a" => "1"
2# "b" => "2"
3# "c" => "3"

5、客户端缓存

基于 RESP3 协议实现的客户端缓存功能。为了进一步提升缓存的性能，将客户端经常访问的数据cache到客户端。减少TCP网络交互。不过该特性目前合并到了unstable 分支，作者说等6.0 GA版本之前，还要修改很多。

客户端缓存的功能是该版本的全新特性，服务端能够支持让客户端缓存values，Redis作为一个本身作为一个缓存数据库，自身的性能是非常出色的，但是如果可以在Redis客户端再增加一层缓存结果，那么性能会更加的出色。Redis实现的是一个服务端协助的客户端缓存，叫做tracking。客户端缓存的命令是:

CLIENT TRACKING ON|OFF [REDIRECT client-id] [PREFIX prefix] [BCAST] [OPTIN] [OPTOUT] [NOLOOP]

当tracking开启时， Redis会"记住"每个客户端请求的key，当key的值发现变化时会发送失效信息给客户端。失效信息可以通过 RESP3 协议发送给请求的客户端，或者转发给一个不同的连接(支持RESP2+ Pub/Sub)。

更多信息见：Client side caching in Redis 6

6、集群代理

Redis Cluster 内部使用的是P2P中的Gossip协议，每个节点既可以从其他节点得到服务，也可以向其他节点提供服务，没有中心的概念，通过一个节点可以获取到整个集群的所有信息。所以如果应用连接Redis Cluster可以配置一个节点地址，也可以配置多个节点地址。但需要注意如果集群进行了上下节点的的操作，其应用也需要进行修改，这样会导致需要重启应用，非常的不友好。从Redis 6.0开始支持了Proxy，可以直接用Proxy来管理各个集群节点。本文来介绍下如何使用官方自带的proxy：redis-cluster-proxy

通过使用 redis-cluster-proxy 可以与组成Redis集群的一组实例进行通讯，就像是单个实例一样。Redis群集代理是多线程的，使用多路复用通信模型，因此每个线程都有自己的与群集的连接，该连接由属于该线程本身的所有客户端共享。

在某些特殊情况下（例如MULTI事务或阻塞命令），多路复用将被禁用；并且客户端将拥有自己的集群连接。

这样客户端仅发送诸如GET和SET之类的简单命令就不需要Redis集群的专有连接。

redis-cluster-proxy的主要功能特点：

1）路由：每个查询都会自动路由到集群的正确节点

2）多线程

3）支持多路复用和专用连接模型

4）在多路复用上下文中，可以确保查询执行和答复顺序

5）发生ASK | MOVED错误后自动更新集群的配置：当答复中发生此类错误时，代理通过获取集群的更新配置并重新映射所有插槽来自动更新集群。更新完成后所有查询将重新执行，因此，从客户端的角度来看，一切正常进行（客户端将不会收到ASK | MOVED错误：他们将在收到请求后直接收到预期的回复）群集配置已更新）。

6）跨槽/跨节点查询：支持许多命令，这些命令涉及属于不同插槽（甚至不同集群节点）的多个键。这些命令会将查询分为多个查询，这些查询将被路由到不同的插槽/节点。这些命令的回复处理是特定于命令的。某些命令（例如MGET）将合并所有答复，就好像它们是单个答复一样。其他命令（例如MSET或DEL）将汇总所有答复的结果。由于这些查询实际上破坏了命令的原子性，因此它们的用法是可选的（默认情况下禁用）。

7）一些没有特定节点/插槽的命令（例如DBSIZE）将传递到所有节点，并且将对映射的回复进行映射缩减，以便得出所有回复中包含的所有值的总和。

8）可用于执行某些特定于代理的操作的附加PROXY命令

7、Disque module

这个本来是作者几年前开发的一个基于 Redis 的消息队列工具，但多年来作者发现 Redis 在持续开发时，他也要持续把新的功能合并到这个Disque 项目里面，这里有大量无用的工作。因此这次他在 Redis 的基础上通过 Modules 功能实现 Disque。

如果业务并不需要保持严格消息的顺序，这个 Disque 能提供足够简单和快速的消息队列功能。

8、其他

新的Expire算法：用于定期删除过期key的函数activeExpireCycle被重写，以便更快地收回已经过期的key；
提供了许多新的Module API；
从服务器也支持无盘复制：在用户可以配置的特定条件下，从服务器现在可以在第一次同步时直接从套接字加载RDB到内存；
SRANDMEMBER命令和类似的命令优化，使其结果具有更好的分布；
重写了Systemd支持；
官方redis-benchmark工具支持cluster模式；
提升了RDB日志加载速度；

Redis 5.0

2018年10月18日

1、Stream 数据结构：用来持久化消息队列。

Stream与Redis现有数据结构比较：

Stream	List, Pub/Sub, Zset
获取元素高效，复杂度为O(logN)	List获取元素的复杂度为O(N)
支持offset，每个消息元素有唯一id。不会因为新元素加入或者其他元素淘汰而改变id。	List没有offset概念，如果有元素被逐出，无法确定最新的元素
支持消息元素持久化，可以保存到AOF和RDB中	Pub/Sub不支持持久化消息
支持消费分组	Pub/Sub不支持消费分组
支持ACK（消费确认）	Pub/Sub不支持
Stream性能与消费者数量无明显关系	Pub/Sub性能与客户端数量负相关
允许按时间线逐出历史数据，支持block，给予radix tree和listpack，内存开销少	Zset不能重复添加相同元素，不支持逐出和block，内存开销大
不能从中间删除消息元素	Zet支持删除任意元素

2、新的Redis模块API

新的Redis模块API：定时器(Timers)、集群(Cluster)和字典API(Dictionary APIs)。

3、集群管理器更改

redis3.x和redis4.x的集群管理主要依赖基于Ruby的redis-trib.rb脚本，

redis5.0彻底抛弃了它，将集群管理功能全部集成到完全用C写的redis-cli中。

可以通过命令redis-cli --cluster help查看帮助信息。

4、Lua改进

将Lua脚本更好地传播到 replicas/AOF；

Lua脚本现在可以超时并在副本中进入BUSY状态。

5、RDB格式变化

Redis 5.0开始，RDB快照文件中增加存储key逐出策略LRU 和 LFU

LRU(Least Recently Used)：最近最少使用。长期未使用的数据，优先被淘汰。

LFU(Least Frequently Used)：最不经常使用。在一段时间内，使用次数最少的数据，优先被淘汰。

Redis5.0的RDB文件格式有变化，向下兼容。因此如果使用快照的方式迁移，可以从Redis低版本迁移到Redis5.0，但不能从Redis5.0迁移到低版本。

6、动态HZ

以前redis版本的配置项hz都是固定的，redis5.0将hz动态化是为了平衡空闲CPU的使用率和响应能力。

当然这个是可配置的，只不过在5.0中默认是动态的，其对应的配置为：dynamic-hz yes

7、ZPOPMIN & ZPOPMAX命令

ZPOPMIN key [count]

在有序集合ZSET所有key中，删除并返回指定count个数得分最低的成员，如果返回多个成员，也会按照得分高低（value值比较），从低到高排列。

ZPOPMAX key [count]

在有序集合ZSET所有key中，删除并返回指定count个数得分最高的成员，如果返回多个成员，也会按照得分高低（value值比较），从高到低排列。

BZPOPMIN key [key …] timeout ZPOPMIN的阻塞版本。

BZPOPMAX key [key …] timeout ZPOPMAX的阻塞版本。

8、CLIENT新增命令

1）CLIENT UNBLOCK

格式：CLIENT UNBLOCK client-id [TIMEOUT|ERROR]

用法：当客户端因为执行具有阻塞功能的命令如BRPOP、XREAD被阻塞时，该命令可以通过其他连接解除客户端的阻塞

2）CLIENT ID

该命令仅返回当前连接的ID。每个连接ID都有某些保证：

它永远不会重复，可以判断当前链接是否断开过；

ID是单调递增的。可以判断两个链接的接入顺序。

9、其他

主动碎片整理V2：增强版主动碎片整理，配合Jemalloc版本更新，更快更智能，延时更低；

HyperLogLog改进：在Redis5.0中，HyperLogLog算法得到改进，优化了计数统计时的内存使用效率；

更好的内存统计报告；

客户经常连接和断开连接时性能更好；

错误修复和改进；

Jemalloc内存分配器升级到5.1版本；

许多拥有子命令的命令，新增了HELP子命令，如：XINFO help、PUBSUB help、XGROUP help…

LOLWUT命令：没什么实际用处，根据不同的版本，显示不同的图案，类似安卓；

如果不为了API向后兼容，我们将不再使用“slave”一词：查看原因，Changing Redis master-slave replication terms with something

Redis核心在许多方面进行了重构和改进。

Redis 4.0

Redis 4.0在2017年7月发布为GA。包含几个重大改进：更好的复制（PSYNC2），线程DEL / FLUSH，混合RDB + AOF格式，活动内存碎片整理，内存使用和性能改进。目前小版本更新到4.0.6

一、主从数据同步机制

PSYNC2: 新的一种主从复制同步机制。

PSYNC1: 2.8~4.0之前版本的同步为PSYNC1

1、psync1因为网络中断或者阻塞导致主从中断，恢复后必须重新到主节点dump一份全量数据同步到从节点。psync2再中断恢复后只需要同步复制延迟的那部分数据。

2、psync1在重启从节点需要重新全量同步数据。psync2只部分同步增量数据。

3、在PSYNC1 当复制为链式复制的时候，如 A>B>C 主节点为A。当A出现问题，C节点不能正常复制B节点的数据。当提升B为主节点，C需要全量同步B的数据。在PSYNC2：PSYNC2解决了链式复制之间的关联性。A出现问题不影响C节点，B提升为主C不需要全量同步。

4、在使用星形复制。如一主两从。A>B , A>C 主节点为A。当A出现问题，B提升为主节点，C 重新指向主节点B。使用同步机制PSYNC2，C节点只做增量同步即可。在使用sentinel故障转移可以较少数据重新同步的延迟时间，避免大redis同步出现的网络带宽占满。

二、命令优化

线程DEL / FLUSH 优化

Redis现在可以在不同的线程中删除后台的key而不会阻塞服务器。新的`UNLINK`命令与`DEL`相同，但是以非阻塞的方式工作。但是在key过期的内部依然使用了DEL。类似地，为了让整个数据集或单个数据库异步释放，在“FLUSHALL”和“FLUSHDB”中添加了“ASYNC”选项。(手动清除大的key 可以使用unlink，不阻塞)

三、慢日志

记录客户端来源IP地址，这个小功能对于故障排查很有用处。

四、混合RDB + AOF格式

混合RDB + AOF格式: 混合的RDB-AOF格式。如果启用，则在重写AOF文件时使用新格式

重写使用更紧凑和更快的方式来生成RDB格式，并将AOF流附加到文件。

这允许在使用AOF持久性时更快地重写和重新加载。(目前相对于2.8没啥用)

五、新的管理命令

1、MEMORY 能够执行不同类型的内存分析：内存问题的故障排除（使用MEMORY DOCTOR，类似于LATENCY DOCTOR）,报告单个键使用的内存量，更深入地报告Redis内存使用情况。

查看键值使用 memory MEMORY USAGE key

memory统计分析 MEMORY STATS

MEMORY MALLOC-STATS

MEMORY PURGE

2、SWAPDB 能够完全立即（无延迟）替换同实例下的两个Redis数据库(目前我们业务没啥用)

六、内存使用和性能改进

1、Redis现在使用更少的内存来存储相同数量的数据。

2、Redis现在可以对使用的内存进行碎片整理，并逐渐回收空间(这个功能依然是试用阶段，可以通过参数不开启即可)

Redis 6.0 2020年8月27日

多线程IO

SSL支持

ACL支持

RESP3

客户端缓存

集群代理

Disque module

Redis 5.0 2018年10月18日

Stream类型

新的Redis模块API

集群管理器更改

Lua改进

RDB格式变化

动态HZ

ZPOPMIN&ZPOPMAX命令

CLIENT新增命令

Redis 4.0

可能出乎很多人的意料，Redis3.2之后的版本是4.0，而不是3.4、3.6、3.8。

一般这种重大版本号的升级，意味着软件或者工具本身发生了重大变革，Redis有了重大更新。

在Redis4.0版本上，最核心的功能是支持了module模块化，这极大的丰富的Redis的功能，使得许多Redis本身不具有的，第三方开发者拓展的功能，也能加载到Redis中当一个功能进行使用，比如RediSearch、ReJSON、Redis-ML等。

Redis发布了4.0-RC2，下面列出Redis4.0的新特性：

1）提供了模块系统，方便第三方开发者拓展Redis的功能，更多模块详见：http://redismodules.com。

2）PSYNC2.0：优化了之前版本中，主从节点切换必然引起全量复制的问题。

3）提供了新的缓存剔除算法：LFU（Last Frequently Used，最不经常使用），并对已有算法进行了优化。

4）提供了非阻塞del和flushall/flushdb功能，有效解决删除bigkey可能造成的Redis阻塞。

5）提供了RDB-AOF混合持久化格式，充分利用了AOF和RDB各自优势。

6）提供memory命令，实现对内存更为全面的监控统计。

7）提供了交互数据库功能，实现Redis内部数据库之间的数据置换。

8）Redis Cluster兼容NAT和Docker

9）支持了布隆过滤器以插件的形式加载到 Redis Server 中，主要用于统计去重。

10）redis-cell：一个基于漏斗算法的原子性限流模块，主要用于限流。

11）混合持久化：RDB加AOF混合持久化的方式。

12）缓存驱逐策略优化，Lazy Free，Active Defrag，交换数据库

Redis 3.2

Redis3.2在2016年5月6日正式发布，相比于Redis3.0主要特征如下：

1）新增了地理位置 GEO 模块 GEOHash，主要用于对位置地理信息的操作。

2）SDS在速度和节省空间上都做了优化。

3）支持用upstart或者systemd管理Redis进程。

4）新的List编码类型：quicklist。

5）从节点读取过期数据保证一致性。

6）添加了hstrlen命令。

7）增强了debug命令，支持了更多的参数。

8）Lua脚本功能增强。

9）添加了Lua Debugger。

10）config set支持更多的配置参数。

11）优化了Redis崩溃后的相关报告。

12）新的RDB格式，但是仍然兼容旧的RDB。

13）加速RDB的加载速度。

14）spop命令支持个数参数。

15）cluster nodes命令得到加速。

16）Jemalloc更新到4.0.3版本。

17）bitfield指令下的三个子指令，分别是 get/set/incrby，它们都可以对指定位片段进行读写，但是最多只能处理 64 个连续的位，只要用于支持位图操作。

Redis 3.0

Redis3.0在2015年4月1日正式发布，截止到本书完成已经到3.0.7版本，

相比于Redis2.8主要特性如下：

Redis3.0最大的改动就是添加Redis的分布式实现Redis Cluster，填补了Redis官方没有分布式实现的空白。

Redis Cluster经历了4年才正式发布也是有原因的，具体可以参考Redis Cluster的开发日志

1）Redis Cluster：Redis的官方分布式实现。

2）全新的embedded string对象编码结果，优化小对象内存访问，在特定的工作负载下速度大幅提升。

3）LRU (Least Recently Used，最近最少使用) 算法大幅提升。

4）migrate连接缓存，大幅提升键迁移的速度。

5）migrate命令两个新的参数copy和replace。

6）新的client pause命令，在指定时间内停止处理客户端请求。

7）bitcount命令性能提升。

8）config set设置maxmemory时候可以设置不同的单位（之前只能是字节），例如config set maxmemory1gb。

9）Redis日志小做调整：日志中会反应当前实例的角色（master或者slave）。

10）incr命令性能提升。

11）Wait 指令：wait 提供两个参数，第一个参数是从库的数量 N，第二个参数是时间 t，以毫秒为单位。用来将redis本身的异步复制变为同步复制。

Redis 2.8

Redis2.8在2013年11月22日正式发布，经历了24个版本，到2.8.24版本，

相比于Redis2.6，主要特性如下：

1）添加部分主从复制的功能，在一定程度上降低了由于网络问题，造成频繁全量复制生成RDB对系统造成的压力。

2）尝试性地支持IPv6。

3）可以通过config set命令设置maxclients。

4）可以用bind命令绑定多个IP地址。

5）Redis设置了明显的进程名，方便使用ps命令查看系统进程。

6）config rewrite命令可以将config set持久化到Redis配置文件中。

7）发布订阅添加了pubsub命令。

8）Redis Sentinel第二版，相比于Redis2.6的Redis Sentinel，此版本已经变成生产可用。

9）set 指令的扩展参数，使得 setnx 和 expire 指令可以一起执行，为了解决分布式锁指令原子性的问题。

10）新增scan指令，scan 参数提供了三个参数，第一个是 cursor 整数值，第二个是 key 的正则模式，第三个是遍历的 limit hint。主要用于key扫描，如大key查找、删除等。

11）无盘复制（Redis 2.8.18）：用来解决主节点在快照同步时大量IO影响效率的问题。

Redis 2.6

Redis2.6在2012年正式发布，经历了17个版本，到2.6.17版本，相比于

Redis2.4，主要特性如下：

1）服务端支持Lua脚本。

2）去掉虚拟内存相关功能。

3）放开对客户端连接数的硬编码限制。

4）键的过期时间支持毫秒。

5）从节点提供只读功能。

6）两个新的位图命令：bitcount和bitop。

7）增强了redis-benchmark的功能：支持定制化的压测，CSV输出等功能。

8）基于浮点数自增命令：incrbyfloat和hincrbyfloat。

9）redis-cli可以使用–eval参数实现Lua脚本执行。

10）shutdown命令增强。

11）info可以按照section输出，并且添加了一些统计项。

12）重构了大量的核心代码，所有集群相关的代码都去掉了，cluster功能将会是3.0版本最大的亮点。

13）sort命令优化。

常见的缓存算法

1、FIFO (Fist in first out，先进先出)

如果一个数据最先进入缓存中，则应该最早淘汰掉。

2、LFU (Least frequently used，最不经常使用)

如果一个数据在最近一段时间内（例如 1分钟、10分钟内）使用次数很少，那么在将来一段时间内被使用的可能性也很小。

3、LRU (Least recently used，最近最少使用)

如果数据最近被访问过，那么将来被访问的几率也更高。

像浏览器的缓存策略、memcached的缓存策略都是使用LRU这个算法，LRU算法会将近期最不会访问的数据淘汰掉。LRU如此流行的原因是实现比较简单，而且对于实际问题也很实用，良好的运行时性能，命中率较高。

LRU 最近最少使用的算法实现：

1）新数据插入到链表头部，当做是最近使用的数据

2）每当缓存命中（即缓存数据被访问），则将数据移到链表头部

3）当链表满的时候，将链表尾部的数据丢弃

LRU Cache具备的操作：

set(key,value)：如果key在hashmap中存在，则先重置对应的value值，然后获取对应的节点当前位置curr，将curr节点从链表删除，并将当前数据移动到链表的头部；若果key在hashmap不存在，则新建一个节点，并将节点放到链表的头部。当Cache存满的时候，将链表最后一个节点删除

get(key)：如果key在hashmap中存在，则把对应的节点放到链表头部，并返回对应的value值；如果不存在，则返回-1，对链表不操作

LRU的C++实现

LRU实现采用双向链表 + Map 来进行实现。

这里采用双向链表的原因是：

1）如果采用普通的单链表，则删除节点的时候需要从表头开始遍历查找，效率为O(n)

2）采用双向链表，可以直接改变节点的前驱的指针指向进行删除达到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) {}
};

对于LRU Cache这个类而言，构造函数需要指定容量大小

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算法的实现操作就完成了，完整的源码参考：leetcode/solution146.cpp

LRU和LFU的区别

LRU是最近最少使用页面置换算法(Least Recently Used)，也就是首先淘汰最长时间未被使用的页面

LFU是最近最不常用页面置换算法(Least Frequently Used)，也就是淘汰一定时期内被访问次数最少的页

比如，第二种方法的时期T为10分钟，如果每分钟进行一次调页，主存块为3

若所需页面走向为2 1 2 1 2 3 4，当调页面4时会发生缺页中断

若按LRU算法，应换页面1(1页面最久未被使用) 但按LFU算法应换页面3(十分钟内，页面3只使用了一次)

可见LRU关键是看页面最后一次被使用到发生调度的时间长短，而LFU关键是看一定时间段内页面被使用的频率!

本文参考：

Redis 4.0、5.0、6.0版本特性整理

Redis 4.0新特性

Redis 6.0 新特性-多线程连环13问