后端需要知道的关于redis的事，基本都在这里了。

此文后续会改为粉丝可见，所以喜欢的请提前关注。

你的点赞和评论是我创作的最大动力，谢谢。

1、入门

Redis是一款基于键值对的NoSQL数据库，它的值支持多种数据结构：
字符串(strings)、哈希(hashes)、列表(lists)、集合(sets)、有序集合(sorted sets)等。
• Redis将所有的数据都存放在内存中，所以它的读写性能十分惊人，用作数据库，缓存和消息代理。

Redis具有内置的复制，Lua脚本，LRU逐出，事务和不同级别的磁盘持久性，并通过Redis Sentinel和Redis Cluster自动分区提供了高可用性。
• Redis典型的应用场景包括：缓存、排行榜、计数器、社交网络、消息队列等

1.1NoSql入门概述

1）单机Mysql的美好时代

瓶颈：

 

• 数据库总大小一台机器硬盘内存放不下
• 数据的索引（B + tree）一个机器的运行内存放不下
• 访问量（读写混合）一个实例不能承受

 

2）Memcached（缓存）+ MySql + 垂直拆分

通过缓存来缓解数据库的压力，优化数据库的结构和索引

垂直拆分指的是：分成多个数据库存储数据（如：卖家库与买家库）

 

3）MySql主从复制读写分离

1. 主从复制：主库来一条数据，从库立刻插入一条。
2. 读写分离：读取（从库Master），写（主库Slave）

 

4）分表分库+水平拆分+MySql集群

1. 主库的写压力出现瓶颈（行锁InnoDB取代表锁MyISAM）
2. 分库：根据业务相关紧耦合在同一个库，对不同的数据读写进行分库（如注册信息等不常改动的冷库与购物信息等热门库分开）
3. 分表：切割表数据（例如90W条数据，id 1-30W的放在A库，30W-60W的放在B库，60W-90W的放在C库）

 

MySql扩展的瓶颈

1. 大数据下IO压力大
2. 表结构更改困难

常用的Nosql

Redis
memcache
Mongdb
以上几种Nosql 请到各自的官网上下载并参考使用

Nosql 的核心功能点

KV(存储)
Cache(缓存)
Persistence(持久化)
……

1.2redis的介绍和特点:

       问题：
               传统数据库：持久化存储数据。
               solr索引库:大量的数据的检索。
               在实际开发中，高并发环境下，不同的用户会需要相同的数据。因为每次请求，
               在后台我们都会创建一个线程来处理，这样造成，同样的数据从数据库中查询了N次。
               而数据库的查询本身是ＩＯ操作，效率低，频率高也不好。
               总而言之，一个网站总归是有大量的数据是用户共享的，但是如果每个用户都去数据库查询
               效率就太低了。
       解决：
               将用户共享数据缓存到服务器的内存中。        
       特点：
               1、基于键值对
               2、非关系型(redis)
                       关系型数据库:存储了数据以及数据之间的关系,oracle,mysql
                       非关系型数据库:存储了数据,redis,mdb.
               3、数据存储在内存中，服务器关闭后，持久化到硬盘中
               4、支持主从同步
               实现了缓存数据和项目的解耦。
       redis存储的数据特点：
               大量数据
               用户共享数据
               数据不经常修改。
               查询数据
       redis的应用场景：
               网站高并发的主页数据
               网站数据的排名
               消息订阅

1.3redis——数据结构和对象的使用介绍    
       

redis官网

微软写的windows下的redis

我们下载第一个

额案后基本一路默认就行了

安装后，服务自动启动，以后也不用自动启动。

出现这个表示我们连接上了。

 

redis命令参考链接

1.3.1String

数据结构

struct sdshdr{
    //记录buf数组中已使用字节的数量
    int len;
    //记录buf数组中未使用的数量
    int free;
    //字节数组，用于保存字符串
    char buf[];
}

常见操作

127.0.0.1:6379> set hello world
OK
127.0.0.1:6379> get hello
"world"
127.0.0.1:6379> del hello
(integer) 1
127.0.0.1:6379> get hello
(nil)
127.0.0.1:6379>

应用场景

String是最常用的一种数据类型，普通的key/value存储都可以归为此类，value其实不仅是String，也可以是数字：比如想知道什么时候封锁一个IP地址（访问超过几次）。INCRBY命令让这些变得很容易，通过原子递增保持计数。

1.3.2LIST

数据结构

typedef struct listNode{
    //前置节点
    struct listNode *prev;
    //后置节点
    struct listNode *next;
    //节点的值
    struct value;
}

常见操作

> lpush list-key item
(integer) 1
> lpush list-key item2
(integer) 2
> rpush list-key item3
(integer) 3
> rpush list-key item
(integer) 4
> lrange list-key 0 -1
1) "item2"
2) "item"
3) "item3"
4) "item"
> lindex list-key 2
"item3"
> lpop list-key
"item2"
> lrange list-key 0 -1
1) "item"
2) "item3"
3) "item"

应用场景

Redis list的应用场景非常多，也是Redis最重要的数据结构之一。
我们可以轻松地实现最新消息排行等功能。
Lists的另一个应用就是消息队列，可以利用Lists的PUSH操作，将任务存在Lists中，然后工作线程再用POP操作将任务取出进行执行。

1.3.3HASH

数据结构

dictht是一个散列表结构，使用拉链法保存哈希冲突的dictEntry。

typedef struct dictht{
    //哈希表数组
    dictEntry **table;
    //哈希表大小
    unsigned long size;
    //哈希表大小掩码，用于计算索引值
    unsigned long sizemask;
    //该哈希表已有节点的数量
    unsigned long used;
}

typedef struct dictEntry{
    //键
    void *key;
    //值
    union{
        void *val;
        uint64_tu64;
        int64_ts64;
    }
    struct dictEntry *next;
}

Redis的字典dict中包含两个哈希表dictht，这是为了方便进行rehash操作。在扩容时，将其中一个dictht上的键值对rehash到另一个dictht上面，完成之后释放空间并交换两个dictht的角色。

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; 
    unsigned long iterators; 
} dict;

rehash操作并不是一次性完成、而是采用渐进式方式，目的是为了避免一次性执行过多的rehash操作给服务器带来负担。

渐进式rehash通过记录dict的rehashidx完成，它从0开始，然后没执行一次rehash例如在一次 rehash 中，要把 dict[0] rehash 到 dict[1]，这一次会把 dict[0] 上 table[rehashidx] 的键值对 rehash 到 dict[1] 上，dict[0] 的 table[rehashidx] 指向 null，并令 rehashidx++。

在 rehash 期间，每次对字典执行添加、删除、查找或者更新操作时，都会执行一次渐进式 rehash。

采用渐进式rehash会导致字典中的数据分散在两个dictht中，因此对字典的操作也会在两个哈希表上进行。
例如查找时，先从ht[0]查找，没有再查找ht[1]，添加时直接添加到ht[1]中。

常见操作

> hset hash-key sub-key1 value1
(integer) 1
> hset hash-key sub-key2 value2
(integer) 1
> hset hash-key sub-key1 value1
(integer) 0
> hgetall hash-key
1) "sub-key1"
2) "value1"
3) "sub-key2"
4) "value2"
> hdel hash-key sub-key2
(integer) 1
> hdel hash-key sub-key2
(integer) 0
> hget hash-key sub-key1
"value1"
> hgetall hash-key
1) "sub-key1"
2) "value1"

1.3.4SET

常见操作

> sadd set-key item
(integer) 1
> sadd set-key item2
(integer) 1
> sadd set-key item3
(integer) 1
> sadd set-key item
(integer) 0
> smembers set-key
1) "item2"
2) "item"
3) "item3"
> sismember set-key item4
(integer) 0
> sismember set-key item
(integer) 1
> srem set-key item
(integer) 1
> srem set-key item
(integer) 0
> smembers set-key
1) "item2"
2) "item3"

应用场景

Redis为集合提供了求交集、并集、差集等操作，故可以用来求共同好友等操作。

1.3.5ZSET

数据结构

typedef struct zskiplistNode{
        //后退指针
        struct zskiplistNode *backward;
        //分值
        double score;
        //成员对象
        robj *obj;
        //层
        struct zskiplistLever{
            //前进指针
            struct zskiplistNode *forward;
            //跨度
            unsigned int span;
        }lever[];
    }
    
    typedef struct zskiplist{
        //表头节点跟表尾结点
        struct zskiplistNode *header, *tail;
        //表中节点的数量
        unsigned long length;
        //表中层数最大的节点的层数
        int lever;
    }

跳跃表，基于多指针有序链实现，可以看作多个有序链表。

与红黑树等平衡树相比，跳跃表具有以下优点：

• 插入速度非常快速，因为不需要进行旋转等操作来维持平衡性。
• 更容易实现。
• 支持无锁操作。

常见操作

> zadd zset-key 728 member1
(integer) 1
> zadd zset-key 982 member0
(integer) 1
> zadd zset-key 982 member0
(integer) 0
> zrange zset-key 0 -1
1) "member1"
2) "member0"
> zrange zset-key 0 -1 withscores
1) "member1"
2) "728"
3) "member0"
4) "982"
> zrangebyscore zset-key 0 800 withscores
1) "member1"
2) "728"
> zrem zset-key member1
(integer) 1
> zrem zset-key member1
(integer) 0
> zrange zset-key 0 -1 withscores
1) "member0"
2) "982"

应用场景

以某个条件为权重，比如按顶的次数排序
ZREVRANGE命令可以用来按照得分来获取前100名的用户，ZRANK可以用来获取用户排名，非常直接而且操作容易。
Redis sorted set的使用场景与set类似，区别是set不是自动有序的，而sorted set可以通过用户额外提供一个优先级(score)的参数来为成员排序，并且是插入有序的，即自动排序。

 

redis命令参考链接

1.4Spring整合Redis

引入依赖
- spring-boot-starter-data-redis

		<dependency>
			<groupId>org.springframework.boot</groupId>
			<artifactId>spring-boot-starter-data-redis</artifactId>
		</dependency>

配置Redis
- 配置数据库参数

# RedisProperties
spring.redis.database=11#第11个库，这个随便
spring.redis.host=localhost
spring.redis.port=6379#端口

- 编写配置类，构造RedisTemplate

这个springboot已经帮我们配了，但是默认object，我想改成string

import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import org.springframework.data.redis.connection.RedisConnectionFactory;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.data.redis.serializer.RedisSerializer;

@Configuration
public class RedisConfig {

    @Bean
    public RedisTemplate<String, Object> redisTemplate(RedisConnectionFactory factory) {
        RedisTemplate<String, Object> template = new RedisTemplate<>();
        template.setConnectionFactory(factory);

        // 设置key的序列化方式
        template.setKeySerializer(RedisSerializer.string());
        // 设置value的序列化方式
        template.setValueSerializer(RedisSerializer.json());
        // 设置hash的key的序列化方式
        template.setHashKeySerializer(RedisSerializer.string());
        // 设置hash的value的序列化方式
        template.setHashValueSerializer(RedisSerializer.json());

        template.afterPropertiesSet();
        return template;
    }

}

访问Redis
- redisTemplate.opsForValue()
- redisTemplate.opsForHash()
- redisTemplate.opsForList()
- redisTemplate.opsForSet()
- redisTemplate.opsForZSet()

@RunWith(SpringRunner.class)
@SpringBootTest
@ContextConfiguration(classes = CommunityApplication.class)
public class RedisTests {

    @Autowired
    private RedisTemplate redisTemplate;

    @Test
    public void testStrings() {
        String redisKey = "test:count";

        redisTemplate.opsForValue().set(redisKey, 1);

        System.out.println(redisTemplate.opsForValue().get(redisKey));
        System.out.println(redisTemplate.opsForValue().increment(redisKey));
        System.out.println(redisTemplate.opsForValue().decrement(redisKey));
    }

    @Test
    public void testHashes() {
        String redisKey = "test:user";

        redisTemplate.opsForHash().put(redisKey, "id", 1);
        redisTemplate.opsForHash().put(redisKey, "username", "zhangsan");

        System.out.println(redisTemplate.opsForHash().get(redisKey, "id"));
        System.out.println(redisTemplate.opsForHash().get(redisKey, "username"));
    }

    @Test
    public void testLists() {
        String redisKey = "test:ids";

        redisTemplate.opsForList().leftPush(redisKey, 101);
        redisTemplate.opsForList().leftPush(redisKey, 102);
        redisTemplate.opsForList().leftPush(redisKey, 103);

        System.out.println(redisTemplate.opsForList().size(redisKey));
        System.out.println(redisTemplate.opsForList().index(redisKey, 0));
        System.out.println(redisTemplate.opsForList().range(redisKey, 0, 2));

        System.out.println(redisTemplate.opsForList().leftPop(redisKey));
        System.out.println(redisTemplate.opsForList().leftPop(redisKey));
        System.out.println(redisTemplate.opsForList().leftPop(redisKey));
    }

    @Test
    public void testSets() {
        String redisKey = "test:teachers";

        redisTemplate.opsForSet().add(redisKey, "刘备", "关羽", "张飞", "赵云", "诸葛亮");

        System.out.println(redisTemplate.opsForSet().size(redisKey));
        System.out.println(redisTemplate.opsForSet().pop(redisKey));
        System.out.println(redisTemplate.opsForSet().members(redisKey));
    }

    @Test
    public void testSortedSets() {
        String redisKey = "test:students";

        redisTemplate.opsForZSet().add(redisKey, "唐僧", 80);
        redisTemplate.opsForZSet().add(redisKey, "悟空", 90);
        redisTemplate.opsForZSet().add(redisKey, "八戒", 50);
        redisTemplate.opsForZSet().add(redisKey, "沙僧", 70);
        redisTemplate.opsForZSet().add(redisKey, "白龙马", 60);

        System.out.println(redisTemplate.opsForZSet().zCard(redisKey));
        System.out.println(redisTemplate.opsForZSet().score(redisKey, "八戒"));
        System.out.println(redisTemplate.opsForZSet().reverseRank(redisKey, "八戒"));
        System.out.println(redisTemplate.opsForZSet().reverseRange(redisKey, 0, 2));
    }

    @Test
    public void testKeys() {
        redisTemplate.delete("test:user");

        System.out.println(redisTemplate.hasKey("test:user"));

        redisTemplate.expire("test:students", 10, TimeUnit.SECONDS);
    }
}

这样还是稍微有点麻烦，我们其实可以绑定key

    // 多次访问同一个key
    @Test
    public void testBoundOperations() {
        String redisKey = "test:count";
        BoundValueOperations operations = redisTemplate.boundValueOps(redisKey);
        operations.increment();
        operations.increment();
        operations.increment();
        operations.increment();
        operations.increment();
        System.out.println(operations.get());
    }

2、数据结构原理总结

这部分在我看来是最有意思的，我们有必要了解底层数据结构的实现，这也是我最感兴趣的。

比如，你知道redis中的字符串怎么实现的吗？为什么这么实现？

你知道redis压缩列表是什么算法吗？

你知道redis为什么抛弃了红黑树反而采用了跳表这种新的数据结构吗？

你知道hyperloglog为什么用如此小的空间就可以有这么好的统计性能和准确性吗？

你知道布隆过滤器为什么这么有效吗？有没有数学证明过？

你是否还能很快写出来快排？或者不断优化性能的排序？是不是只会调库了甚至库函数怎么实现的都不知道？真的就是快排？

包括数据库，持久化，处理事件、客户端服务端、事务的实现、发布和订阅等功能的实现，也需要了解。

2.1数据结构和对象的实现

• 1） 字符串

redis并未使用传统的c语言字符串表示，它自己构建了一种简单的动态字符串抽象类型。

在redis里，c语言字符串只会作为字符串字面量出现，用在无需修改的地方。

当需要一个可以被修改的字符串时，redis就会使用自己实现的SDS（simple dynamic string）。比如在redis数据库里，包含字符串的键值对底层都是SDS实现的，不止如此，SDS还被用作缓冲区（buffer）：比如AOF模块中的AOF缓冲区以及客户端状态中的输入缓冲区。

下面来具体看一下sds的实现：

struct sdshdr
{
    int len;//buf已使用字节数量（保存的字符串长度）
    int free;//未使用的字节数量
    char buf[];//用来保存字符串的字节数组
};

sds遵循c中字符串以'\0'结尾的惯例，这一字节的空间不算在len之内。

这样的好处是，我们可以直接重用c中的一部分函数。比如printf；

    sds相对c的改进

    获取长度：c字符串并不记录自身长度，所以获取长度只能遍历一遍字符串，redis直接读取len即可。

    缓冲区安全：c字符串容易造成缓冲区溢出，比如：程序员没有分配足够的空间就执行拼接操作。而redis会先检查sds的空间是否满足所需要求，如果不满足会自动扩充。

    内存分配：由于c不记录字符串长度，对于包含了n个字符的字符串，底层总是一个长度n+1的数组，每一次长度变化，总是要对这个数组进行一次内存重新分配的操作。因为内存分配涉及复杂算法并且可能需要执行系统调用，所以它通常是比较耗时的操作。   

    redis内存分配：

1、空间预分配：如果修改后大小小于1MB，程序分配和len大小一样的未使用空间，如果修改后大于1MB，程序分配  1MB的未使用空间。修改长度时检查，够的话就直接使用未使用空间，不用再分配。 

2、惰性空间释放：字符串缩短时不需要释放空间，用free记录即可，留作以后使用。

    二进制安全

c字符串除了末尾外，不能包含空字符，否则程序读到空字符会误以为是结尾，这就限制了c字符串只能保存文本，二进制文件就不能保存了。

而redis字符串都是二进制安全的，因为有len来记录长度。

• 2） 链表

作为一种常用数据结构，链表内置在很多高级语言中，因为c并没有，所以redis实现了自己的链表。

链表在redis也有一定的应用，比如列表键的底层实现之一就是链表。（当列表键包含大量元素或者元素都是很长的字符串时）

发布与订阅、慢查询、监视器等功能也用到了链表。

具体实现：

//redis的节点使用了双向链表结构
typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点的值
    void *value;
} listNode;

//其实学过数据结构的应该都实现过
typedef struct list {
    // 表头节点
    listNode *head;
    // 表尾节点
    listNode *tail;
    // 链表所包含的节点数量
    unsigned long len;
    // 节点值复制函数
    void *(*dup)(void *ptr);
    // 节点值释放函数
    void (*free)(void *ptr);
    // 节点值对比函数
    int (*match)(void *ptr, void *key);
} list;

总结一下redis链表特性：

双端、无环、带长度记录、

多态：使用 void* 指针来保存节点值， 可以通过 dup 、 free 、 match 为节点值设置类型特定函数， 可以保存不同类型的值。

• 3）字典

其实字典这种数据结构也内置在很多高级语言中，但是c语言没有，所以redis自己实现了。

应用也比较广泛，比如redis的数据库就是字典实现的。不仅如此，当一个哈希键包含的键值对比较多，或者都是很长的字符串，redis就会用字典作为哈希键的底层实现。

来看看具体是实现：

//redis的字典使用哈希表作为底层实现
typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;

    // 该哈希表已有节点的数量
    unsigned long used;

} dictht;

table 是一个数组， 数组中的每个元素都是一个指向dictEntry 结构的指针， 每个 dictEntry 结构保存着一个键值对。

图为一个大小为4的空哈希表。

我们接着就来看dictEntry的实现：

typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

（v可以是一个指针， 或者是一个 uint64_t 整数， 又或者是一个 int64_t 整数。）

next就是解决键冲突问题的，冲突了就挂后面，这个学过数据结构的应该都知道吧，不说了。

 

下面我们来说字典是怎么实现的了。

typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引
    int rehashidx; /

uint8_t encoding; 

uint8_t notused[3]; 

uint8_t card[8]; 

uint8_t registers[]; 

};

HyperLogLog 对象中的 registers 数组就是桶，它有两种存储结构，分别为密集存储结构和稀疏存储结构，两种结构只涉及存储和桶的表现形式，从中我们可以看到 Redis 对节省内存极致地追求。

我们先看相对简单的密集存储结构，它也是十分的简单明了，既然要有 2^14 个 6 bit的桶，那么我就真使用足够多的 uint8_t 字节去表示，只是此时会涉及到字节位置和桶的转换，因为字节有 8 位，而桶只需要 6 位。

所以我们需要将桶的序号转换成对应的字节偏移量 offsetbytes 和其内部的位数偏移量 offsetbits。需要注意的是小端字节序，高位在右侧，需要进行倒转。

当 offset_bits 小于等于2时，说明一个桶就在该字节内，只需要进行倒转就能得到桶的值。

 offset_bits 大于 2 ，则说明一个桶分布在两个字节内，此时需要将两个字节的内容都进行倒置，然后再进行拼接得到桶的值。

Redis 为了方便表达稀疏存储，它将上面三种字节表示形式分别赋予了一条指令。

• ZERO : 一字节，表示连续多少个桶计数为0，前两位为标志00，后6位表示有多少个桶，最大为64。

• XZERO : 两个字节，表示连续多少个桶计数为0，前两位为标志01，后14位表示有多少个桶，最大为16384。

• VAL : 一字节，表示连续多少个桶的计数为多少，前一位为标志1，四位表示连桶内计数，所以最大表示桶的计数为32。后两位表示连续多少个桶。

 

Redis从稀疏存储转换到密集存储的条件是：

• 任意一个计数值从 32 变成 33，因为 VAL 指令已经无法容纳，它能表示的计数值最大为 32

• 稀疏存储占用的总字节数超过 3000 字节，这个阈值可以通过 hllsparsemax_bytes 参数进行调整。

2.4LRU专栏

2.4.1LRU介绍和代码实现

LRU全称是Least Recently Used，即最近最久未使用的意思。

LRU算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。（这一段是找的，让大家理解一下什么是LRU）。

 

说一下我们什么时候见到过LRU：其实老师们肯定都给大家举过这么个例子：你在图书馆，你把书架子里的书拿到桌子上。。但是桌子是有限的，你有时候不得不把一些书放回去。这就相当于内存和硬盘。这个例子都说过吧？

LRU就是记录你最长时间没看过的书，就把它放回去。在cache那里见过吧

 

然后最近在研究redis，又看到了这个LRU，所以就想写一下吧。

题目：设计一个结构，这个结构可以查询K-V，但是容量有限，当存不下的时候就要把用的年代最久远的那个东西扔掉。

其实思路很简单，我们维护一个双向链表即可，get也就是使用了，我们就把把它提到最安全的位置。新来的KV就依次放即可。

我们就先写这个双向链表结构

先写节点结构：

	public static class Node<V> {
		public V value;
		public Node<V> last;//前
		public Node<V> next;//后

		public Node(V value) {
			this.value = value;
		}
	}

然后写双向链表结构： 我们没必要把链表操作都写了，分析一下，我们只有三个操作：

1、加节点

2、使用了某个节点就把它调到尾，代表优先级最高

3、把优先级最低的移除，也就是去头部

（不会的，翻我之前的链表操作都有写）

	public static class NodeDoubleLinkedList<V> {
		private Node<V> head;//头
		private Node<V> tail;//尾

		public NodeDoubleLinkedList() {
			this.head = null;
			this.tail = null;
		}

		public void addNode(Node<V> newNode) {
			if (newNode == null) {
				return;
			}
			if (this.head == null) {//头空
				this.head = newNode;
				this.tail = newNode;
			} else {//头不空
				this.tail.next = newNode;
				newNode.last = this.tail;//注意让本节点前指针指向旧尾
				this.tail = newNode;//指向新尾
			}
		}

		public void moveNodeToTail(Node<V> node) {
			if (this.tail == node) {//是尾
				return;
			}
			if (this.head == node) {//是头
				this.head = node.next;
				this.head.last = null;
			} else {//中间
				node.last.next = node.next;
				node.next.last = node.last;
			}
			node.last = this.tail;
			node.next = null;
			this.tail.next = node;
			this.tail = node;
		}

		public Node<V> removeHead() {
			if (this.head == null) {
				return null;
			}
			Node<V> res = this.head;
			if (this.head == this.tail) {//就一个
				this.head = null;
				this.tail = null;
			} else {
				this.head = res.next;
				res.next = null;
				this.head.last = null;
			}
			return res;
		}

	}

链表操作封装完了就要实现这个结构了。

具体思路代码注释

	public static class MyCache<K, V> {
		//为了kv or vk都能查
		private HashMap<K, Node<V>> keyNodeMap;
		private HashMap<Node<V>, K> nodeKeyMap;
		//用来做优先级
		private NodeDoubleLinkedList<V> nodeList;
		private int capacity;//容量

		public MyCache(int capacity) {
			if (capacity < 1) {//你容量连1都不给，捣乱呢
				throw new RuntimeException("should be more than 0.");
			}
			this.keyNodeMap = new HashMap<K, Node<V>>();
			this.nodeKeyMap = new HashMap<Node<V>, K>();
			this.nodeList = new NodeDoubleLinkedList<V>();
			this.capacity = capacity;
		}

		public V get(K key) {
			if (this.keyNodeMap.containsKey(key)) {
				Node<V> res = this.keyNodeMap.get(key);
				this.nodeList.moveNodeToTail(res);//使用过了就放到尾部
				return res.value;
			}
			return null;
		}

		public void set(K key, V value) {
			if (this.keyNodeMap.containsKey(key)) {
				Node<V> node = this.keyNodeMap.get(key);
				node.value = value;//放新v
				this.nodeList.moveNodeToTail(node);//我们认为放入旧key也是使用过
			} else {
				Node<V> newNode = new Node<V>(value);
				this.keyNodeMap.put(key, newNode);
				this.nodeKeyMap.put(newNode, key);
				this.nodeList.addNode(newNode);//加进去
				if (this.keyNodeMap.size() == this.capacity + 1) {
					this.removeMostUnusedCache();//放不下就去掉优先级最低的
				}
			}
		}

		private void removeMostUnusedCache() {
			//删除头
			Node<V> removeNode = this.nodeList.removeHead();
			K removeKey = this.nodeKeyMap.get(removeNode);
			//删除掉两个map中的记录
			this.nodeKeyMap.remove(removeNode);
			this.keyNodeMap.remove(removeKey);
		}
	}

 

2.4.2Redis中的LRU算法改进

redis通常使用缓存，是使用一种固定最大内存的使用。当数据达到可使用的最大固定内存时，我们需要通过移除老数据来获取空间。redis作为缓存是否有效的重要标志是如何寻找一种好的策略：删除即将需要使用的数据是一种糟糕的策略，而删除那些很少再次请求的数据则是一种好的策略。
在其他的缓存组件还有个命中率，仅仅表示读请求的比例。访问一个缓存中的keys通常不是分布式的。然而访问经常变化，这意味着不经常访问，相反，有些keys一旦不流行可能会转向最经常访问的keys。 因此，通常一个缓存系统应该尽可能保留那些未来最有可能被访问的keys。针对keys淘汰的策略是：那些未来极少可能被访问的数据应该被移除。
但有一个问题：redis和其他缓存系统不能够预测未来。

LRU算法

缓存系统不能预测未来，原因是：那些很少再次被访问的key也很有可能最近访问相当频繁。如果经常被访问的模式不会突然改变，那么这是一种很有效的策略。然而，“最近经常被访问”似乎更隐晦地标明一种 理念。这种算法被称为LRU算法。最近访问频繁的key相比访问少的key有更高的可能性。
举个例子，这里有4个不同访问周期的key，每一个“~”字符代表一秒，结尾的“|”表示当前时刻。

~~~~~A~~~~~A~~~~~A~~~~A~~~~~A~~~~~A~~|
~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~|
~~~~~~~~~~C~~~~~~~~~C~~~~~~~~~C~~~~~~|
~~~~~D~~~~~~~~~~D~~~~~~~~~D~~~~~~~~~D|

A key每5秒请求一次，B周期是2秒，C、D都是10秒。
访问频率最高的是B，因为它的空闲时间最短，这意味着B是4个key中未来最有可能被访问的key。
同样的A和C目前的空闲时间是2s和6s也能很好地反映它们本身的周期。然而你可以看到不够严谨：D的访问周期是10秒，但它却是4个key中最近被访问的。
当然，在一个很长的运行周期中，LRU算法能工作得很好。通常有一个更高访问频率的key当然有一个更低的空闲周期。LRU算法淘汰最少被访问key，那些有最大空闲周期的key。实现上也相当容易，只需要额外跟踪最近被访问的key即可，有时甚至都需要：把所有我们想要淘汰的对象放到一个链表中，当一个对象访问就移除链表头部元素，当我们要淘汰元素是就直接淘汰链表尾部开始。

redis中的LRU:起因

最初，redis不支持LRU算法。当内存有效性成为一个必须被解决的问题时，后来才加上了。通过修改redis对象结构，在每个key对象增加24bit的空间。没有额外的空间使用链表把所有对象放到一个链表中（大指针），因此需要实现得更加有效，不能因为key淘汰算法而让整个服务改动太大。
24bits的对象已经足够去存储当前的unxi时间戳。这个表现，被称为“LRU 时钟”，key元数据经常被更新，所以它是一个有效的算法。
然后，有另一个更加复杂的问题需要解决：如何选择访问间隔最长的key，然后淘汰它。
redis内部采用一个庞大的hash table来保存，添加另外一个数据结构存储时间间隔显然不是一个好的选择。然而我们希望能达到一个LRU本身是一个近似的，通过LRU算法本身来实现。

redis原始的淘汰算法简单实现：**当需要淘汰一个key时，随机选择3个key，淘汰其中间隔时间最长的key。**基本上，我们随机选择key，淘汰key效果很好。后来随机3个key改成一个配置项"N随机key"。但把默认值提高改成5个后效果大大提高。考虑到它的效果，你根本不用修改他。

然而，你可能会想这个算法如何有效执行，你可以看到我们如何捣毁了很多有趣的数据。也许简单的N key，我们会遇到很多好的决策，但是当我们淘汰最好的，下一个周期又开始抓。

验证规则第一条：用肉眼观察你的算法

其中有一个观点已经应用到Redis 3.0正式版中了。在redis2.8中一个LRU缓存经常被使用在多个环境，用户关于淘汰的没有抱怨太多，但是很明显我可以提高它，通过不仅仅是增加额外的空间，还有额外的CPU时间。
然而为了提高某项功能，你必须观察它。有多个不同的方式去观察LRU算法。你可以通过写工具观察，例如模拟不同的工作负载、校验命中率和失误率。
程序非常简单：增加一些指定的keys，然后频繁地访问这些keys以至于每一个key都有一个下降的空闲时间。最终超过50%的keys被增加，一半的老key需要被淘汰。
一个完美理想的LRU实现，应该是没有最新加的key被淘汰，而是淘汰最初的50%的老key。

规则二：不要丢弃重要信息

借助最新的可视化工具，我可以在尝试新的方法观察和测试几分钟。使用redis最明显有效的提高算法就是，积累对立的垃圾信息在一个淘汰池中。
基本上，当N keys算法被采用时，通常会分配一个很大的线程pool（默认为16key），这个池按照空闲时间排序，所以只有当有一个大于池中的一个或者池为空的时候，最新的key只会进入到这个池中。
同时，一个新的redis-cli模式去测量LRU算法也增加了(看这个-lru-test选项)。
还有另外一个方式去检验LRU算法的好坏，通过一个幂等访问模式。这个工具通常校验用一个不同的测试，新算法工作工作效果好于真实世界负载。它也同样使用流水线和每秒打印访问日志，因此可以被使用不用为了基准不同的思想，至少可以校验和观察明显的速度回归。

规则三、最少使用原则（LFU算法）

一切源于一个开放性问题：但你有多个redis 3.2数据库时，而淘汰算法只能在本机选择。因此，假如你全部空闲小的key都是DB0号机器，空闲时间长的key都是1号机器，redis每台机器都会淘汰各自的key。一个更好的选择当然是先淘汰DB1，最后再淘汰DB0。
当redis被当作缓存使用时很少有情况被分成不同的db上，这不是一个好的处理方式。然而这也是我为什么我再一次修改淘汰代码的原因。最终，我能够修改缓存池包括数据库id，使用单缓存池为多个db，代替多缓存池。这种实现很麻烦，但是通过优化和修改代码，最终它比普通实现要快到20%。
然而这时候，我对这个redis缓存淘汰算法的好奇心又被点燃。我想要提升它。我花费了几天想要提高LRU算法实现：或许可以使用更大的缓存池？通过历史时间选择最合适被淘汰的key？
经过一段时间，通过优化我的工具，我理解到：LRU算法受限于数据库中的数据样本，有时可能相反的场景效果非常好，因此要想提高非常非常难。实际上，能通过展示不同算法的图片上看这有点非常明显：每个周期10个keys几乎和理论的LRU算法表现一致。
当原始算法很难提高时，我开始测试新的算法。 如果我们倒回到博客开始，我们说过LRU实际上有点严格。哪些key需要我们真正想要保留：将来有最大可能被访问，最频繁被访问，而不是最近被访问的key。
淘汰最少被访问的key算法成为：LFU（Least Frequently Used），将来要被淘汰腾出新空间给新key。
理论上LFU的思想相当简单，只需要给每个key加一个访问计数器。每次访问就自增1，所以也就很容易知道哪些key被访问更频繁。
当然，LFU也会带起其他问题，不单单是针对redis，对于LFU实现：
1、不能使用“移除顶部元素”的方式，keys必须要根据访问计数器进行排序。每访问一次就得遍历所有key找出访问次数最少的key。
2、LFU不能仅仅是只增加每一访问的计数器。正如我们所讲的，访问模式改变随时变化，因此一个有高访问次数的key，后面很可能没有人继续访问它，因此我们的算法必须要适应超时的情况。
在redis中，第一个问题很好解决：我们可以在LRU的方式一样：随机在缓存池中选举，淘汰其中某项。第二个问题redis还是存在，因此一般对于LFU的思想必须使用一些方式进行减少，或者定期把访问计数器减半。

24位的LFU实现

LFU有它本身的实现，在redis中我们使用自己的24bit来记录LRU。
为了实现LFU仅仅需要在每个对象额外新增24bit：
1、一部分用于保存访问计数器；
2、足够用于决定什么时候将计数器减半的信息；

我的解决方法是把24bit分成两列：

16bits8bitslast decr timeLOG_C

16位记录最后一次减半时间，那样redis知道上一次减半时间，另外8bit作为访问计数器。
你可能会想8位的计数器很快就会溢出，是的，相对于简单计数器，我采用逻辑计数器。逻辑计数器的实现：

uint8_t LFULogIncr(uint8_t counter) {
      if (counter == 255) return 255;
      double r = (double)rand()/RAND_MAX;
      double baseval = counter - LFU_INIT_VAL;
      if (baseval < 0) baseval = 0;
      double p = 1.0/(baseval*server.lfu_log_factor+1);
      if (r < p) counter++;
      return counter;
  }

基本上计数器的较大者，更小的可能计数器会增加：上面的代码计算p位于0~1之间，但计数器增长时会越来越小，位于0-1的随机数r，只会但满足r<p时计数器才会加一。
你可以配置计数器增长的速率，如果使用默认配置，会发生：

• 100次访问后，计数器=10；
• 1000次访问是是18；
• 10万次访问是142；
• 100万次访问后达到255，并不在继续增长；

下面，让我们看看计数器如果进行衰减。16位的被储存为unix时间戳保留到分钟级别，redis会随机扫描key填充到缓存池中，如果最后一个下降的时间大于N分钟前（可配置化），如果计数器的值很大就减半，或者对于值小的就直接简单减半。
这里又衍生出另外一个问题，就是新进来的key是需要有机会被保留的。由于LFU新增是得分都是0，非常容易被选举替换掉。在redis中，开始默认值为5。这个初始值是根据增长数据和减半算法来估算的。模拟显示得分小于5的key是首选。

代码和性能

上面描述的算法已经提交到一个非稳定版的redis分支上。我最初的测试显示：它在幂等模式下优于LRU算法，测试情况是每个key使用用相同数量的内存，然而真实世界的访问可能会有很大不同。时间和空间都可能改变得很不同，所以我会很开心去学习观察现实世界中LFU的性能如何，两种方式在redis实现中对性能的改变。
因此，新增了一个OBJECT FREQ子命令，用于报告给定key的访问计数器，不仅仅能有效提观察一个计数器，而且还能调试LFU实现中的bug。
注意运行中切换LRU和LFU，刚开始会随机淘汰一些key，随着24bit不能匹配上，然而慢慢会适应。 还有几种改进实现的可能。Ben Manes发给我这篇感兴趣的文章，描述了一种叫TinyLRU算法。链接

这篇文章包含一个非常厉害的观点：相比于记录当前对象的访问频率，让我们（概率性地）记录全部对象的访问频率，看到了，这种方式我们甚至可以拒绝新key，同样，我们相信这些key很可能得到很少的访问，所以一点也不需要淘汰，如果淘汰一个key意味着降低命中/未命中率。
我的感觉这种技术虽然很感兴趣GET/SET LFU缓存，但不适用与redis性质的数据服务器：用户期望keys被创建后至少存在几毫秒。拒绝key的创建似乎在redis上就是一种错误。
然而，redis保留了LFU信息，当一个key被覆盖时，举个例子：

SET oldkey some_new_value

24位的LFU计数器会从老的key复制到新对象中。

新的redis淘汰算法不稳定版本还有以下几个好消息：
1、跨DB策略。在过去的redis只是基于本地的选举，现在修复为所有策略，不仅仅是LRU。
2、易变ttl策略。基于key预期淘汰存活时间，如今就像其他策略中的使用缓存池。
3、在缓存池中重用了sds对象，性能更好。

这篇博客比我预期要长，但是我希望它反映出一个见解：在创新和对于已经存在的事物实现上，一种解决方案去解决一个特定问题，一个基础工具。由开发人员以正确的方式使用它。许多redis的用户把redis作为一个缓存的解决方案，因此提高淘汰策略这一块经常一次又一次被拿出来探讨。

2.6对象

刚写了redis主要的数据结构：

动态字符串、双端链表、字典、压缩列表、整数集合、跳表等

redis肯定不能直接使用这些数据结构来实现数据库，它用这些数据库建立了一个对象系统，包含：

字符串对象、列表对象、哈希对象、集合对象、有序集合对象

我们可以针对不同的使用场景，为对象设置多种分不同的数据结构实现，从而优化对象在不同场景下的效率。

1）键值对

对于redis的键值对来说：key只有字符串类型，而v可以是各种类型，

我们习惯把“这个键所对应的值是一个列表”表达为这是一个“列表键。

TYPE 命令的实现方式也与此类似， 当我们对一个数据库键执行 TYPE 命令时， 命令返回的结果为数据库键对应的值对象的类型， 而不是键对象的类型：

# 键为字符串对象，值为列表对象

redis> RPUSH numbers 1 3 5
(integer) 6

redis> TYPE numbers
list

2）对象

我们看一下redis对象的组成：

typedef struct redisObject {
    // 类型
    unsigned type:4;
    // 编码
    unsigned encoding:4;
    // 指向底层实现数据结构的指针
    void *ptr;
    // ...
} robj;

通过 encoding 属性来设定对象所使用的编码， 而不是为特定类型的对象关联一种固定的编码， 极大地提升了 Redis 的灵活性和效率， 因为 Redis 可以根据不同的使用场景来为一个对象设置不同的编码， 从而优化对象在某一场景下的效率。

字符串对象

字符串对象的编码可以是 int 、 raw 或者 embstr 。

如果一个字符串对象保存的是整数值， 并且这个整数值可以用 long 类型来表示， 那么字符串对象会将整数值保存在字符串对象结构的 ptr属性里面（将 void* 转换成 long ）， 并将字符串对象的编码设置为 int 。

如果字符串对象保存的是一个字符串值， 并且这个字符串值的长度大于 39 字节， 那么字符串对象将使用一个简单动态字符串（SDS）来保存这个字符串值， 并将对象的编码设置为 raw 。

如果字符串对象保存的是一个字符串值， 并且这个字符串值的长度小于等于 39 字节， 那么字符串对象将使用 embstr 编码的方式来保存这个字符串值。

embstr 编码是专门用于保存短字符串的一种优化编码方式， 这种编码和 raw 编码一样， 都使用 redisObject 结构和 sdshdr 结构来表示字符串对象，但 raw 编码会调用两次内存分配函数来分别创建 redisObject 结构和 sdshdr 结构，而 embstr 编码则通过调用一次内存分配函数来分配一块连续的空间， 空间中依次包含 redisObject 和 sdshdr 两个结构。

 embstr 编码有以下好处：

1. embstr 编码创建删除字符串对象只需操作一次内存
2. 因为数据都保存在一块连续的内存， 所以这种编码的字符串对象比 raw 编码字符串对象能更好地利用缓存带来的优势。

3）列表对象

列表对象的编码可以是 ziplist 或者 linkedlist 。

当列表对象可以同时满足以下两个条件时， 列表对象使用 ziplist 编码：

1. 列表对象保存的所有字符串元素的长度都小于 64 字节；
2. 列表对象保存的元素数量小于 512 个；

不能满足这两个条件的列表对象需要使用 linkedlist 编码。

4）哈希对象

哈希对象的编码可以是 ziplist 或者 hashtable 。

当哈希对象可以同时满足以下两个条件时， 哈希对象使用 ziplist 编码：

1. 哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节；
2. 哈希对象保存的键值对数量小于 512 个；

不能满足这两个条件的哈希对象需要使用 hashtable 编码。

5）集合对象

集合对象的编码可以是 intset 或者 hashtable 。

当集合对象可以同时满足以下两个条件时， 对象使用 intset 编码：

1. 集合对象保存的所有元素都是整数值；
2. 集合对象保存的元素数量不超过 512 个；

不能满足这两个条件的集合对象需要使用 hashtable 编码。

6）有序集合对象

有序集合的编码可以是 ziplist 或者 skiplist 。

当有序集合对象可以同时满足以下两个条件时， 对象使用 ziplist 编码：

1. 有序集合保存的元素数量小于 128 个；
2. 有序集合保存的所有元素成员的长度都小于 64 字节；

不能满足以上两个条件的有序集合对象将使用 skiplist 编码。

这里多说两句，各个语言的对象其实都差不多，底层实现也就那几个，比如java中的容器，c++的STL。java的hashset就是一个哈希而已，hashmap就是k带了一个v，而”有序的“Treemap使用了红黑树这种有平衡性的搜索二叉树。

redis的有序集合并没有再采取hash+红黑树的操作，而是把平衡树换成了跳表，实际上性能真的没差多少，甚至有时比红黑树有优势，比如跳表的性能较为平均，红黑树攒了很多次不平衡要调整可能会带来资源需求的一个高峰，再加上跳表实现简单的优点，红黑树真的没什么优势。

并且就算是真的想用一种带平衡性的搜索树，现在竞赛也是用的华人之光发明的SB树。

有序集合的优点就是它的有序操作，比如拿最大最小值，红黑树时间o(logN),而哈希表只能一个一个遍历。缺点在于插入一个值的时间也是o(logN),跳表也是。而哈希表插入数是o(1).

要了解底层和这些优缺点