Redis
参考博客
https://www.cnblogs.com/beiluowuzheng/
https://www.cnblogs.com/hunternet/
如有侵权，请联系我删除，谢谢！
目录
一、什么是redis
Redis是一个使用c语言开发的数据库。与传统数据库不同的是，Redis的数据是存储在内存中的，读写速度非常快，因此被广泛应用于缓存方向。另外，Redis除了做缓存之外，Redis也经常用来做分布式锁，甚至是消息队列。
Redis 提供了多种数据类型来⽀持不同的业务场景，包括String，list，set，hash，sortedset。Redis 还⽀持事务 、持久化、Lua 脚本、多种集群⽅案
二、数据结构
1.1 SDS，简单动态字符串
Redis默认并未直接使用C字符串（C字符串，仅仅作为字符串字面量，用在一些无需对字符串进行修改的地方，如打印日志。）。Redis使用Struct的形式构造了一个SDS的抽象类型。当Redis需要一个可以被修改的字符串时，就会使用SDS来表示。
- 在Redis数据库里，包含字符串值的键值对都是由SDS实现的
- Redis中所有的键都是由字符串对象实现的即底层是由SDS实现，Redis中所有的值对象中包含的字符串对象底层也是由SDS实现。
1.1.1 SDS底层结构
 - struct sdshdr{
- //字节数组用于保存字符串 sds遵循了c字符串以空字符结尾的惯例目的是为了重用c字符串函数库里的函数
- char buf[];
- //int 记录buf数组中未使用字节的数量 如上图free为0代表未使用字节的数量为0
- int free;
- //int 记录buf数组中已使用字节的数量即sds的长度 如上图len为5代表未使用字节的数量为5
- int len;
-
- }
在C语言中，如果对字符串进行修改，就需要面临内存重分配的情况。C字符串是有一个长度为n+1的字符数组，C字符串为静态数组，初始化后的数组长度不会改变，如果像增加字符串的长度，就需要重新分配一块更长的内存空间，否者会产生内存溢出。
- 扩容机制（SDS最大长度为512M）：空间预分配
- 如果修改后的len长度小于1M，扩容为原来的一倍：n*2+1；
- 如果修改后的len超过1M，只扩容1M的空间：n+1M+1。
- 释放机制：惰性空间释放
当字符串缩短时，Redis首先使用free属性记录，等待将来使用。
1.1.3 二进制安全
为了时SDS能够保存诸如图片、音频、视频等二进制数据，Redis API使用len属性来判断字符串的长度，而不是使用空字符串作为判断依据。因此SDS是二进制安全的。但SDS依然遵循C字符串的惯例使用空字符串结尾，目的是能够复用一部分的库中的函数。
1.1.4 为什么使用SDS
- 杜绝缓冲区溢出
- 减少字符串操作中的内存重分配次数
- 二进制安全
- 由于SDS遵循以空字符结尾的惯例，因此兼容部门C字符串函数
1.1.5 SDS API
sdsnew创建一个包含给定C字符串的SDSO(N) ，N 为给定C字符串的长度sdsempty创建一个不包含任何内容的空SDSO(1)sdsfree释放给定的SDSO(1)sdslen返回SDS的已使用空间字节数这个值可以通过读取SDS的len属性来直接获得，复杂度为O(1)sdsavail返回SDS的未使用空间字节数这个值可以通过读取SDS的free属性来直接获得，复杂度为 O(1)sdsdup创建一个给定SDS的副本（copy）O(N)，N为给定SDS的长度sdsclear清空SDS保存的字符串内容因为惰性空间释放策略，复杂度为O(1)sdscat将给定C字符串拼接到SDS字符串的末尾O(N)，N为被拼接C字符串的长度sdscatsds将给定SDS字符串拼接到另一个SDS字符串的末尾O(N)，N为被拼接SDS字符串的长度sdscpy将给定的C字符串复制到SDS里面，覆盖SDS原有的字符串O(N)，N为被复制C字符串的长度sdsgrowzero用空字符将SDS扩展至给定长度O(N)，N为扩展新增的字节数sdsrange保留SDS给定区间内的数据，不在区间内的数据会被覆盖或清除O(N)，N为被保留数据的字节数sdstrim接受一个SDS和一个C字符串作为参数，从SDS左右两端分别移除所有在C字符串中出现过的字符O(M*N)，M为SDS的长度，N为给定C字符串的长度sdscmp对比两个SDS字符串是否相同O(N)，N为两个SDS中较短的那个SDS的长度1.1.6 Redis3.2之后的SDS
Redis3.2 之后的SDS共有五个结构体
- typedef char *sds;
-
- /* Note: sdshdr5 is never used, we just access the flags byte directly.
- * However is here to document the layout of type 5 SDS strings. */
- struct __attribute__ ((__packed__)) sdshdr5 {
- unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
- char buf[];// buf[0]: z: 0101001
- };
- struct __attribute__ ((__packed__)) sdshdr8 {
- uint8_t len; /* used */
- uint8_t alloc; /* excluding the header and null terminator */
- unsigned char flags; /* 3 lsb of type, 5 unused bits */
- char buf[];
- };
- struct __attribute__ ((__packed__)) sdshdr16 {
- uint16_t len; /* used */
- uint16_t alloc; /* excluding the header and null terminator */
- unsigned char flags; /* 3 lsb of type, 5 unused bits */
- char buf[];
- };
- struct __attribute__ ((__packed__)) sdshdr32 {
- uint32_t len; /* used */
- uint32_t alloc; /* excluding the header and null terminator */
- unsigned char flags; /* 3 lsb of type, 5 unused bits */
- char buf[];
- };
- struct __attribute__ ((__packed__)) sdshdr64 {
- uint64_t len; /* used */
- uint64_t alloc; /* excluding the header and null terminator */
- unsigned char flags; /* 3 lsb of type, 5 unused bits */
- char buf[];
- };
-
- #define SDS_TYPE_5 0
- #define SDS_TYPE_8 1
- #define SDS_TYPE_16 2
- #define SDS_TYPE_32 3
- #define SDS_TYPE_64 4
- Redis会根据我们设置的字符串长度，选择不同的SDS结构体来存储，
- 除了sdshdr5，其他4个结构体都有len和alloc字段，这里len依旧代表buf存储的内容长度，而alloc则代表buf的总容量，如果我们要计算SDS剩余可存储字节，则用alloc-len，即为3.2前SDS的free字段。
- flags的最低3位表示SDS的类型，如果flags的值为SDS_TYPE_5（即为：0），则代表这个SDS的类型为sdshdr5、如果flags的值为SDS_TYPE_8（即为：1），则代表这个这个SDS的类型为sdshdr8，以此类推，如果flags的值为SDS_TYPE_64（即为：4，4的二进制表示为100），则代表这个SDS类型为sdshdr64。
- 这里会有人奇怪，为何每个SDS类型都需要一个flags来单独表示其SDS的类型，难道结构体本身不是已经代表其类型了吗？这是因为在Redis中很多时候传递SDS指针并不是以SDS对象的起始地址来传递的，而是以buf的起始地址来传递SDS对象。这里我们注意到每个SDS结构体的最后一个字段都是char buf[]，这是一个没有指定长度的的字符数组，这是C语言中定义字符数组的一种特殊写法，称为柔性数组（flexible array member），只能定义在结构体的最后一个字段上。这个字段只起到标记的作用，表示在flags字段后面就是一个字符数组，或者说，它指明了紧跟在flags字段后面的这个字符数组在结构体中的偏移位置。而程序在为结构体分配的内存的时候，并不会为柔性数组计算需要占用的空间。如果计算sizeof(struct sdshdr16)的值，那么结果是5个字节，不会把buf字段的长度计算进去。当然，我们为一个SDS分配内存，并非要一板一眼只分配5个字节，那么这5个字节的内存空间，仅仅能存储sdshdr16除buf外的字段，如果我们申请一块16字节的内存分配给sdshdr16对象，那么除去5个字节分配给sdshdr16除buf外的字段，我们还有11个字节来存储字符串。如果我们拿到buf的起始地址，flags即为buf[-1]，拿到flags后，我们便可以计算这个buf具体的SDS类型，继而可以获得len和alloc这两个字段，从而计算出这个数组要读取多少个字节才算结束，这个数组还可以容纳多少个字节的数据。
Redis是如何创建SDS对象
- sds sdsnewlen(const void *init, size_t initlen) {
- //这个指针会指向SDS起始位置
- void *sh;
- //sds也是一个指针，这里会指向SDS中buf的起始位置
- sds s;
- //根据不同的长度返回对应的SDS类型
- char type = sdsReqType(initlen);
- /* Empty strings are usually created in order to append. Use type 8
- * since type 5 is not good at this. */
- //如果判断要创建的SDS类型为5，且字符串为空串，则类型替换成SDS8
- if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
- //根据SDS类型获取内存占用大小，以便后续创建内存
- int hdrlen = sdsHdrSize(type);
- //fp用于指向SDS的flag地址
- unsigned char *fp; /* flags pointer. */
- //申请SDS大小+字符串长度+1的内存空间，这里+1是为了分配结束符号，C语言用\0表示字符串结束
- sh = s_malloc(hdrlen+initlen+1);
- //判断内存是否申请成功
- if (sh == NULL) return NULL;
- //判断是否处于init阶段
- if (init==SDS_NOINIT)
- init = NULL;
- //如果不是init阶段则将申请来的内存清零
- else if (!init)
- memset(sh, 0, hdrlen+initlen+1);
- //将s指向SDS的buf起始地址
- s = (char*)sh+hdrlen;
- //s指向buf的起始地址，往前一个字节即指向SDS的flag地址
- fp = ((unsigned char*)s)-1;
- switch(type) {
- case SDS_TYPE_5: {
- *fp = type | (initlen << SDS_TYPE_BITS);
- break;
- }
- case SDS_TYPE_8: {
- SDS_HDR_VAR(8,s);
- sh->len = initlen;
- sh->alloc = initlen;
- *fp = type;
- break;
- }
- case SDS_TYPE_16: {
- //这里使用了内联方法，声明一个对应SDS类型的变量sh
- //#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
- SDS_HDR_VAR(16,s);
- //初始化len和alloc
- sh->len = initlen;
- sh->alloc = initlen;
- //fp指针指向的内存赋值为对应的SDS类型
- *fp = type;
- break;
- }
- case SDS_TYPE_32: {
- SDS_HDR_VAR(32,s);
- sh->len = initlen;
- sh->alloc = initlen;
- *fp = type;
- break;
- }
- case SDS_TYPE_64: {
- SDS_HDR_VAR(64,s);
- sh->len = initlen;
- sh->alloc = initlen;
- *fp = type;
- break;
- }
- }
- //如果initlen和init都不为空，则将init指向的内存拷贝initlen个字节到buf
- if (initlen && init)
- memcpy(s, init, initlen);
- //分配一个结束符
- s[initlen] = '\0';
- //返回buf起始地址
- return s;
- }
- Redis在创建SDS对象时，返回的并不是SDS对象本身，而是buf的起始地址
- 在计算SDS字符串长度、计算buf容量、计算buf剩余容量……时，传入的也是buf的地址
为什么SDS不用内存对齐
- 什么是内存对齐
- 一个32位的CPU在一个周期内只能读取32位的数据，而CPU每次读取数据的起始地址都是4的倍数，如果我们声明了一个struct A对象，a字段的地址是01，b字段的地址是14，那么CPU要读取b字段，需要先读03，再读34，CPU需要读取两次才能完整的读取b字段的数据，如果我们声明了一个struct B对象，字段a的地址是03，字段b的地址是37，那么CPU就可以在一个周期内完整地读取b字段的数据，由此可见，浪费一点内存空间，会使得CPU的性能更为高效。
- 既然内存对齐可以让CPU更加高效，那么Redis作为非关系型内存数据库又为何放弃内存对齐呢？
- 这是因为SDS本身结构的特殊性让它只能是非内存对齐的。不同的SDS类型所需要的字节填充都不一样，如果不放弃内存对齐，我们很难通过buf的偏移获取到flags进而推算出SDS的类型。
1.2 链表
1.2.1 list底层结构
- adlist.h
- //链表结点
- typedef struct listNode {
- //前置节点
- struct listNode *prev;
- //后置节点
- struct listNode *next;
- //节点的值
- void *value;
- } listNode;
- //list
- typedef struct list {
- //表头节点
- listNode *head;
- //表尾节点
- listNode *tail;
- //节点值复制函数
- void *(*dup)(void *ptr);
- //节点值释放函数
- void (*free)(void *ptr);
- //节点值对比函数
- int (*match)(void *ptr, void *key);
- //链表所包含的节点数量
- unsigned long len;
- } list;
- list结构为链表提供了表头指针head、表尾指针tail，以及链表长度计数器len，而dup、free和match成员则是用于实现多态链表所需的类型特定函数：
1.2.2 Redis的链表实现的特性
- 双端：链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都为O(1)
- 无环：表头节点的prev指针和表尾节点的next指针都指向NULL，对链表的访问以NULL为终点
- 带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的时间复杂度为O(1)
- 带链表长度计数器：程序使用list结构的len属性来对list持有的链表节点进行计数，程序获取链表长度的时间复杂度为O(1)
- 多态：链表节点使用void*指针来保存节点值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各个不同类型的值
1.2.3 双向无环链表在Redis中的使用
操作\时间复杂度数组单链表双向链表rpush(从右边添加元素)O(1)O(1)O(1)lpush(从左边添加元素)0(N)O(1)O(1)lpop (从右边删除元素)O(1)O(1)O(1)rpop (从左边删除元素)O(N)O(1)O(1)lindex(获取指定索引下标的元素)O(1)O(N)O(N)len (获取长度)O(N)O(N)O(1)linsert(向某个元素前或后插入元素)O(N)O(N)O(1)lrem (删除指定元素)O(N)O(N)O(N)lset (修改指定索引下标元素)O(N)O(N)O(N)1.3 字典
数据库与哈希对象的底层实现就是字典。
- Redis字典使用散列表最为底层实现，一个字典里有一个dicht属性，ht属性是一个包含两个项的数组，数组中的每个项都是一个dictht哈希表， 一般情况下，字典只使用ht[0] 哈希表, ht[1]哈希表只会对ht[0]哈希表进行rehash时使用。
- dictht中存储着一个哈希表数组（用一个二级指针指向想哈希表数组），数组中的每个元素都是一个指向dictEntry结构的指针，每个dictEntry结构保存着一个键值对。
1.3.1 Redis如何解决散列冲突
- 链表法，当产生冲突时，使用链表法
- rehash。随着操作的进行，散列表中保存的键值对会也会不断地增加或减少，为了保证负载因子维持在一个合理的范围，当散列表内的键值对过多或过少时，内需要定期进行rehash，以提升性能或节省内存。Redis的rehash的步骤如下:
- 为字典的ht[1]散列表分配空间
- 扩展操作，那么ht[1]的大小为第一个大于等于ht[0].used*2的2n（2的n次方幂）（2n>ht[0].used*2）
- 收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的2^n
- 将保存在ht[0]中的键值对重新计算键的散列值和索引值，然后放到ht[1]指定的位置上。
- 将ht[0]包含的所有键值对都迁移到了ht[1]之后，释放ht[0],将ht[1]设置为ht[0],并创建一个新的ht[1]哈希表为下一次rehash做准备。
- rehash操作需要满足以下条件:
- 服务器目前没有执行BGSAVE(rdb持久化)命令或者BGREWRITEAOF(AOF文件重写)命令，并且散列表的负载因子大于等于1。
- 服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且负载因子大于等于5。
- 当负载因子小于0.1时，程序自动开始执行收缩操作。
- 渐进式 rehash
对于rehash我们思考一个问题如果散列表当前大小为 1GB，要想扩容为原来的两倍大小，那就需要对 1GB 的数据重新计算哈希值，并且从原来的散列表搬移到新的散列表。这种情况听着就很耗时，而生产环境中甚至会更大。为了解决一次性扩容耗时过多的情况，可以将扩容操作穿插在插入操作的过程中，分批完成。当负载因子触达阈值之后，只申请新空间，但并不将老的数据搬移到新散列表中。当有新数据要插入时，将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。每次插入一个数据到散列表，都重复上面的过程。经过多次插入操作之后，老的散列表中的数据就一点一点全部搬移到新散列表中了。这样没有了集中的一次一次性数据搬移，插入操作就都变得很快了。
1.4 跳跃表
Redis使用跳跃表作为有序集合键的底层实现之一,如果一个有序集合包含的元素数量比较多,又或者有序集合中元素的成员是比较长的字符串时, Redis就会使用跳跃表来作为有序集合健的底层实现
跳跃表在链表的基础上增加了多级索引以提升查找的效率，但其是一个空间换时间的方案，必然会带来一个问题——索引是占内存的。原始链表中存储的有可能是很大的对象，而索引结点只需要存储关键值值和几个指针，并不需要存储对象，因此当节点本身比较大或者元素数量比较多的时候，其优势必然会被放大，而缺点则可以忽略。
- 跳跃表节点的level数组可以包含多个元素，每个元素都包含一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度，一般来说，层的数量越多，访问其他节点的速度就越快。每次创建一个新跳跃表节点的时候，程序都根据幂次定律（power law，越大的数出现的概率越小）随机生成一个介于1和32之间的值作为level数组的大小，这个大小就是层的高度
- 最左边的是 skiplist结构,该结构包含以下属性
- header:指向跳跃表的表头节点，通过这个指针程序定位表头节点的时间复杂度就为O(1)
- tail:指向跳跃表的表尾节点,通过这个指针程序定位表尾节点的时间复杂度就为O(1)
- level:记录目前跳跃表内,层数最大的那个节点的层数(表头节点的层数不计算在内)，通过这个属性可以再O(1)的时间复杂度内获取层高最好的节点的层数。
- length:记录跳跃表的长度,也即是,跳跃表目前包含节点的数量(表头节点不计算在内)，通过这个属性，程序可以再O(1)的时间复杂度内返回跳跃表的长度。
- 右方的是四个 zskiplistNode结构
- 层(level):
- 每个层都带有两个属性:前进指针和跨度。前进指针用于访问位于表尾方向的其他节点,而跨度则记录了前进指针所指向节点和当前节点的距离(跨度越大、距离越远)。在上图中,连线上带有数字的箭头就代表前进指针,而那个数字就是跨度。当程序从表头向表尾进行遍历时,访问会沿着层的前进指针进行。
- 分值(score): 在跳跃表中,节点按各自所保存的分值从小到大排列。
- 成员对象(oj): 在同一个跳跃表中,各个节点保存的成员对象必须是唯一的,但是多个节点保存的分值却可以是相同的
1.5 整数集合
整数集合(intset)并不是一个基础的数据结构，而是Redis自己设计的一种存储结构，是集合键的底层实现之一,当一个集合只包含整数值元素,并且这个集合的元素数量不多时, Redis 就会使用整数集合作为集合键的底层实现。各个项在数组中按值的大小从小到大有序地排列,并且数组中不包含任何重复项。
1.5.1 整数集合升级
当我们要将一个新元素添加到整数集合里面,并且新元素的类型比整数集合现有所有元素的类型都要长时,整数集合需要先进行升级,然后才能将新元素添加到整数集合里面。升级整数集合并添加新元素主要分三步来进行。
- 根据新元素的类型，扩展整数集合底层数组的空间大小,并为新元素分配空间
- 将底层数组现有的所有元素都转换成与新元素相同的类型,并将类型转换后的元素放置到正确的位上,而且在放置元素的过程中,需要继续维持底层数组的有序性质不变。
- 将新元素添加到底层数组里面。
1.6 压缩列表
同整数集合一样压缩列表也不是基础数据结构，而是 Redis 自己设计的一种数据存储结构。它有点儿类似数组，通过一片连续的内存空间，来存储数据。不过，它跟数组不同的一点是，它允许存储的数据大小不同。
- 压缩列表(zip1ist)是列表和哈希的底层实现之一。
- 当一个列表只包含少量列表项,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会使用压缩列表来做列表的底层实现。
- 当一个哈希只包含少量键值对,比且每个键值对的键和值要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会使用压缩列表来做哈希的底层实现。
1.6.1 Redis压缩列表的构成
压缩列表是Redis为了节约内存而开发的,是由一系列特殊编码的连续内存块组成的顺序型(sequential)数据结枃。一个压缩列表可以包含任意多个节点(entry),每个节点可以保存一个字节数组或者一个整数值，如下图。
1.6.2 Redis压缩列表节点的构成
- 每个压缩列表节点可以保存一个字节数组或者一个整数值
- 长度小于等于63(2^6-1)字节的字节数组;
- 长度小于等于16383(2^14-1)字节的字节数组
- 长度小于等于4294967295(2^32-1)字节的字节数组
- 整数值可以是以下6种长度中的一种
- int16_t类型整数
- int32_t类型整数
- int64_t类型整数
- 4位无符号
- 1字节
- 3字节
1.7 快速列表
考虑到链表的附加空间相对太高，prev 和 next 指针就要占去 16 个字节 (64bit 系统的指针是 8 个字节)，另外每个节点的内存都是单独分配，会加剧内存的碎片化，影响内存管理效率。因此Redis3.2版本开始对列表数据结构进行了改造，使用 quicklist 代替了 ziplist 和 linkedlist.
1.7.1 基本结构
quicklist 实际上是 zipList 和 linkedList 的混合体，它将 linkedList 按段切分，每一段使用 zipList 来紧凑存储，多个 zipList 之间使用双向指针串接起来。
三、Redis对象系统
Redis用到的所有主要数据结构,简单动态字符串(SDS)、双端链表、字典、压缩列表、整数集合、跳跃表。
Redis并没有直接使用这些数据结构来实现键值对数据库,而是基于这些数据结构创建了一个对象系统,这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象,而每种对象又通过不同的编码映射到不同的底层数据结构。
3.1 Redis 对象类型和编码
Redis中的每个对象都由一个redisObject结构表示,该结构中和保存数据有关的三个属性分别是type属性、 encoding属性和ptr属性- typedef struct redisObiect{
- //type属性记录了对象的类型
- unsigned type:4;
- //encoding属性记录了对象使用的编码，也即是说这个对象使用了什么数据结构作为对象的底层实现，
- unsigned encoding:4;
- //指向底层数据结构的指针
- void *ptr;
- }
- Type
类型常量对象的名称REDIS_STRING字符串对象REDIS_LIST列表对象REDIS_HASH哈希对象REDIS_SET集合对象REDIS_ZSET有序集合对象
- encoding
编码常量编码所对应的底层数据结构REDIS_ENCODING_INTlong类型的整数REDIS_ENCODING_EMBSTRembstr编码的简单动态字符串REDIS_ENCODING_RAW简单动态字符串REDIS_ENCODING_HT字典REDIS_ENCODING_LINKEDLIST双端链表REDIS_ENCODING_ZIPLIST压缩列表REDIS_ENCODING_INTSET整数集合REDIS_ENCODING_SKIPLIST跳跃表和字典
- 不同类型和编码的对象
类型编码对象REDIS_STRINGREDIS_ENCODING_INT使用整数值实现的字符串对象REDIS_STRINGREDIS_ENCODING_EMBSTR使用embstr编码的简单动态字符串实现的字符串对象REDIS_STRINGREDIS_ENCODING_RAW使用简单动态字符串实现的字符串对象REDIS_LISTREDIS_ENCODING_ZIPLIST使用压缩列表实现的列表对象REDIS_LISTREDIS_ENCODING_LINKEDLIST使用双端链表实现的列表对象REDIS_HASHREDIS_ENCODING_ZIPLIST使用压缩列表实现的哈希对象REDIS_HASHREDIS_ENCODING_HT使用字典实现的哈希对象REDIS_SETREDIS_ENCODING_INTSET使用整数集合实现的集合对象REDIS_SETREDIS_ENCODING_HT使用字典实现的集合对象REDIS_ZSETREDIS_ENCODING_ZIPLIST使用压缩列表实现的有序集合对象REDIS_ZSETREDIS_ENCODING_SKIPLIST使用跳跃表和字典实现的有序集合对象
Redis使用对象来表示数据库中的键和值,每次当我们在Redis的数据库中新创建一个键值对时,我们至少会创建两个对象,一个对象用作键值对的健(键对象),另一个对象用作键值对的值(值对象)。
- 其中Redis的键对象都是字符串对象，
- Redis的值对象主要有字符串、哈希、列表、集合、有序集合几种
- 当我们对一个数据库键执行TYPE命令时，命令返回的结果为数据库键对应的值对象类型，而不是键对象类型
- 当我们称呼一个数据库键为“字符串键”时，我们指的是“这个数据库键所对应的值为字符串对象”
- 当我们称呼一个数据库键为“列表键”时，我们指的是“这个数据库键所对应的值为列表对象”
3.2 优势
- 可以自由改进内部编码，而对外的数据结构和命令没有影响，这样一旦开发出更优秀的内部编码，无需改动外部数据结构和命令.
例如Redis3.2提供了quicklist，其结合了ziplist和linkedlist两者 的优势，为列表类型提供了一种更为优秀的内部编码实现，而对外部用户来说基本感知不到。 这一点比较像程序设计中的分层架构。
- 多种内部编码实现可以在不同场景下发挥各自的优势，从而优化对象在不同场景下的使用效率
例如ziplist比较节省内存，但是在列表元素比较多的情况下，性能会有所下降，这时候Redis会根据配置选项将列表类型的内部实现转换linkedlist。 (后续文章将根据具体对象介绍)
四、Redis对象类型
4.1 字符串
字符串对象是 Redis 中最基本的数据类型,也是我们工作中最常用的数据类型。redis中的键都是字符串对象，而且其他几种数据结构都是在字符串对象基础上构建的。字符串对象的值实际可以是字符串、数字、甚至是二进制，最大不能超过512MB 。
4.1.1 内部实现
Redis字符串对象底层的数据结构实现主要是int和简单动态字符串SDS，其通过不同的编码方式映射到不同的数据结构。字符串对象的内部编码有3种 ：int、raw和embstr。Redis会根据当前值的类型和长度来决定使用哪种编码来实现。
- 如果一个字符串对象保存的是整数值,并且这个整数值可以用long类型来表示,那么字符串对象会将整数值保存在字符串对象结构的ptr属性里面(将void*转换成1ong),并将字符串对象的编码设置为int;
- 如果字符串对象保存的是一个字符串值,并且这个字符串值的长度大于32字节,那么字符串对象将使用一个简单动态字符串(SDS)来保存这个字符串值,并将对象的编码设置为raw;
- 如果字符串对象保存的是一个字符串值,并且这个字符申值的长度小于等于32字节，那么字符串对象将使用一个简单动态字符串(SDS)来保存这个字符串值，并将对象的编码设置为embstr
embstr编码是专门用于保存短字符串的一种优化编码方式，这种编码方式和raw编码一样，都使用redisObject结构和sdshdr结构来表示字符串对象，但raw编码会调用两次内存分配函数来分别创建redisObject结构和sdshdr结构，而embstr编码则通过调用一次内存分配函数来分配一块连续的空间，空间中依次包含redisObject结构和sdshdr结构:
使用embstr编码的字符串来保存短字符串值有以下好处：
- embstr编码将创建字符串对象所需的内存分配次数从raw编码的两次降低为一次
- 释放 embstr编码的字符串对象同样只需要调用一次内存释放函数
- 因为embstr编码的字符串对象的所有数据都保存在一块连续的内存里面可以更好的利用CPU缓存提升性能。
4.1.2 常用操作
- 添加：set key value [ex seconds] [px milliseconds] [nx|xx]
- set key value [ex seconds]操作是原子性的，相比连续执行set和expire，它更快。
- nx：键必须不存在，才可以设置成功，用于添加。由于set key value nx同样是原子性的操作，因此可以作为分布式锁的一种实现方案。
- xx：与nx相反，键必须存在，才可以设置成功，用于更新
- 批量设置：MSET key value [key value ...]
- 批量获取：MGET key [key ...]
- get: n次get时间 = n次网络时间 + n次命令时间
- mget: n次get时间 = 1次网络时间 + n次命令时间
- 学会使用批量操作，有助于提高效率，但是要掌握一个平衡的度，每次批量操作所发送的命令数并不是无节制的由于Redis是单线程架构，如果数量过多可能造成Redis阻塞或者网络拥
命令描述时间复杂度`set key value [ex seconds] [px milliseconds] [nxxx]`设置值get key获取值O(1)del key [key ...]删除keyO(N)(N是键的个数)mset key [key value ...]批量设置值O(N)(N是键的个数)mget key [key ...]批量获取值O(N)(N是键的个数)incr key将 key 中储存的数字值增一O(1)decr key将 key 中储存的数字值减一O(1)incrby key increment将 key 所储存的值加上给定的增量值（increment）O(1)decrby key incrementkey 所储存的值减去给定的减量值（decrement）O(1)incrbyfloat key increment将 key 所储存的值加上给定的浮点增量值（increment）O(1)append key value如果 key 已经存在并且是一个字符串， APPEND 命令将指定的 value 追加到该 key 原来值（value）的末尾O(1)strlen key返回 key 所储存的字符串值的长度。O(1)setrange key offset value用 value 参数覆写给定 key 所储存的字符串值，从偏移量 offset 开始O(1)getrange key start end返回 key 中字符串值的子字符O(N)(N是字符串的长度)4.1.3 应用场景
reids字符串的使用场景应该是最为广泛的，甚至有些对redis其它几种对象不太熟悉的人，基本所有场景都会使用字符串(序列化一下直接扔进去)。在众多的使用场景中总结一下大概分以下几种。
4.1.3.1 作为缓存层
Redis经常作为缓存层，来缓存一些热点数据。来加速读写性能从而降低后端的压力。一般在读取数据的时候会先从Redis中读取，如果Redis中没有，再从数据库中读取。在Redis作为缓存层使用的时候，必须注意一些问题，如：缓存穿透、雪崩以及缓存更新问题
4.1.3.2 计数器\限速器\分布式系统ID
计数器\限速器\分布式ID等主要是利用Redis字符串自增自减的特性。
- 计数器：经常可以被用来做计数器，如微博的评论数、点赞数、分享数，抖音作品的收藏数，京东商品的销售量、评价数等。
- 限速器：如验证码接口访问频率限制，用户登陆时需要让用户输入手机验证码，从而确定是否是用户本人，但是为了短信接口不被频繁访问，会限制用户每分钟获取验证码的频率，例如一分钟不能超过5次。
- 分布式ID：由于Redis自增自减的操作是原子性的因此也经常在分布式系统中用来生成唯一的订单号、序列号等。
4.1.3.3分布式系统共享session
因分布式系统通常有很多个服务，每个服务又会同时部署在多台机器上，通过负载均衡机制将将用户的访问均衡到不同服务器上。这个时候用户的请求可能分发到不同的服务器上，从而导致用户登录保存Session是在一台服务器上，而读取Session是在另一台服务器上因此会读不到Session。
这种问题通常的做法是把Session存到一个公共的地方，让每个Web服务，都去这个公共的地方存取Session。而Redis就可以是这个公共的地方。(数据库、memecache等都可以各有优缺点)。
4.2 哈希
在redis中，哈希类型是指Redis键值对中的值本身又是一个键值对结构，形如value=[{field1，value1}，...{fieldN，valueN}]
4.2.1 内部实现
哈希类型的内部编码有两种：ziplist(压缩列表),hashtable(哈希表)。只有当存储的数据量比较小的情况下，Redis 才使用压缩列表来实现字典类型。具体需要满足两个条件：
- 哈希类型元素个数小于hash-max-ziplist-entries配置（默认512个）
- 所有值都小于hash-max-ziplist-value配置（默认64字节）
ziplist使用更加紧凑的结构实现多个元素的连续存储，所以在节省内存方面比hashtable更加优秀。当哈希类型无法满足ziplist的条件时，Redis会使用hashtable作为哈希的内部实现，因为此时ziplist的读写效率会下降，而hashtable的读写时间复杂度为O（1）
[field ...]删除一个或多个Hash的fieldO(N) N是被删除的字段数量。HEXISTS key field判断field是否存在于hash中O(1)HGET key field获取hash中field的值O(1)HGETALL key从hash中读取全部的域和值O(N) N是Hash的长度HINCRBY key field increment将hash中指定域的值增加给定的数字O(1)HINCRBYFLOAT key field increment将hash中指定域的值增加给定的浮点数O(1)HKEYS key获取hash的所有字段O(N) N是Hash的长度HLEN key获取hash里所有字段的数量O(1)HMGET key field [field ...]获取hash里面指定字段的值O(N) N是请求的字段数HMSET key field value [field value ...]设置hash字段值O(N) N是设置的字段数HSET key field value设置hash里面一个字段的值O(1)HSETNX key field value设置hash的一个字段，只有当这个字段不存在时有效O(1)HSTRLEN key field获取hash里面指定field的长度O(1)HVALS key获得hash的所有值O(N) N是Hash的长度HSCAN key cursor [MATCH pattern] [COUNT count]迭代hash里面的元素4.2.2 应用场景
- Redis哈希对象常常用来缓存一些对象信息，如用户信息、商品信息、配置信息等。
- 原生字符串每个属性一个键。
- set user:1:name Tom
- set user:1:age 15`
缺点：占用过多的键，内存占用量较大，同时用户信息内聚性比较差，所以此种方案一般不会在生产环境使用。
- 序列化字符串后，将用户信息序列化后用一个键保存
- set user:1 serialize(userInfo)
缺点：序列化和反序列化有一定的开销，同时每次更新属性都需要把全部数据取出进行反序列化，更新后再序列化到Redis中。
- 序列化字符串后，将用户信息序列化后用一个键保存
- hmset user:1 name Tom age 15
缺点：要控制哈希在ziplist和hashtable两种内部编码的转换，hashtable会消耗更多内存。
4.3 列表List
列表（list）类型是用来存储多个有序的字符串，列表中的每个字符串称为元素(element)，一个列表最多可以存储232-1个元素。在Redis中，可以对列表两端插入（push）和弹出（pop），还可以获取指定范围的元素列表、获取指定索引下标的元素等。列表是一种比较灵活的数据结构，它可以充当栈和队列的角色，在实际开发上有很多应用场景。
- 列表中的元素是有序的，这就意味着可以通过索引下标获取某个元素或者某个范围内的元素列表。
- 列表中的元素可以是重复的.
4.3.1 内部实现
在Redis3.2版本以前列表类型的内部编码有两种。
- ziplist（压缩列表）：当列表的元素个数小于list-max-ziplist-entries配置（默认512个），同时列表中每个元素的值都小于list-max-ziplist-value配置时（默认64字节），Redis会选用ziplist来作为列表的内部实现来减少内存的使用。
- linkedlist（链表）：当列表类型无法满足ziplist的条件时，Redis会使用linkedlist作为列表的内部实现。
而在Redis3.2版本开始对列表数据结构进行了改造，使用 quicklist 代替了 ziplist 和 linkedlist.
命令说明时间复杂度BLPOP key [key ...] timeout删除，并获得该列表中的第一元素，或阻塞，直到有一个可用O(1)BRPOP key [key ...] timeout删除，并获得该列表中的最后一个元素，或阻塞，直到有一个可用O(1)BRPOPLPUSH source destination timeout弹出一个列表的值，将它推到另一个列表，并返回它;或阻塞，直到有一个可用O(1)LINDEX key index获取一个元素，通过其索引列表O(N)LINSERT key BEFOREAFTER pivot value在列表中的另一个元素之前或之后插入一个元素O(N)LLEN key获得队列(List)的长度O(1)LPOP key从队列的左边出队一个元素O(1)LPUSH key value [value ...]从队列的左边入队一个或多个元素O(1)LPUSHX key value当队列存在时，从队到左边入队一个元素O(1)LRANGE key start stop从列表中获取指定返回的元素O(S+N)LREM key count value从列表中删除元素O(N)LSET key index value设置队列里面一个元素的值O(N)LTRIM key start stop修剪到指定范围内的清单O(N)RPOP key从队列的右边出队一个元O(1)RPOPLPUSH source destination删除列表中的最后一个元素，将其追加到另一个列表O(1)RPUSH key value [value ...]从队列的右边入队一个元素O(1)RPUSHX key value从队列的右边入队一个元素，仅队列存在时有效O(1)4.3.2 应用场景
- 消息队列
列表类型可以使用 rpush 实现先进先出的功能，同时又可以使用 lpop 轻松的弹出（查询并删除）第一个元素，所以列表类型可以用来实现消息队列
- 文章(商品等)列表
4.4 集合set
Set 是一个无序并唯一的键值集合。它的存储顺序不会按照插入的先后顺序进行存储。
集合类型和列表类型的区别如下：
- 列表可以存储重复元素，集合只能存储非重复元素；
- 列表是按照元素的先后顺序存储元素的，而集合则是无序方式存储元素的。
Set可以存储232-1个元素。Redis除了支持集合内的增删改查，同时还支持多个集合取交集、并集、差集，合理地使用好集合类型，能在实际开发中解决很多实际问题。
4.4.1 内部实现
集合类型的内部编码有两种：
- intset(整数集合):当集合中的元素都是整数且元素个数小于set-maxintset-entries配置（默认512个）时，Redis会选用intset来作为集合的内部实现，从而减少内存的使用。
- hashtable(字典):当集合类型无法满足intset的条件时，Redis会使用hashtable作为集合的内部实现。
4.4.2 使用场景
集合的主要几个特性，无序、不可重复、支持并交差等操作。因此集合类型比较适合用来数据去重和保障数据的唯一性，还可以用来统计多个集合的交集、错集和并集等，当我们存储的数据是无序并且需要去重的情况下，比较适合使用集合类型进行存储。
4.5 有序集合 sorted set
有序集合类型 (Sorted Set或ZSet) 相比于集合类型多了一个排序属性 score（分值），对于有序集合 ZSet 来说，每个存储元素相当于有两个值组成的，一个是有序结合的元素值，一个是排序值。有序集合保留了集合不能有重复成员的特性(分值可以重复)，但不同的是，有序集合中的元素可以排序。
4.5.1 内部实现
有序集合是由ziplist或 skiplist组成的。
当数据比较少时，有序集合使用的是 ziplist 存储的，有序集合使用 ziplist 格式存储必须满足以下两个条件：
- 有序集合保存的元素个数要小于 128 个；
- 有序集合保存的所有元素成员的长度都必须小于 64 字节。
4.5.2 使用场景
五、类型检查与命令多态
Redis中用于操作键的命令基本上可以分为两种类型：
- 其中一种命令可以对任何类型的键执行，比如DEL命令、EXPIRE命令、RENAME命令、TYPE命令、OBJECT命令等。举个栗子，DEL命令可以用来删除三种不同类型的键：字符串键、列表键、集合键
- 而另一种命令只能对特性类型执行，比如：
- SET、GET、APPEND、STRLEN等命令只能对字符串键执行
- HDEL、HSET、HGET、HLEN等命令只能对哈希键执行
- RPUSH、LPOP、LINSERT、LLEN等命令只能对列表键执行
- SADD、SPOP、SINTER、SCARD等命令只能对集合键执行
- ZADD、ZCARD、ZRANK、ZSCORE等命令只能对有序集合键执行
5.1 类型检查和实现
为了确保只有指定类型的键可以执行某些特定的命令，在执行一个类型特定的命令前，Redis会先检查输入键的类型是否正确，然后再决定是否执行给定的命令。类型特定命令所进行的类型检查是通过redisObject结构的type属性来实现的：
- 在执行一个类型特定命令之前，服务器会先检查输入数据库键的值对象是否为执行命令所需的类型，如果是的话，服务器就会执行指定的命令
- 否则，服务器将拒绝执行命令，并向客户端返回一个类型错误
5.2 多态命令的实现
Redis除了会根据值对象的类型来判断键是否能够执行指令外，还会根据值对象的编码方式，选择正确的命令实现代码来执行命令。举个栗子，列表对象有ziplist和linkedlist两种编码可用，其中前者使用压缩列表API来实现列表命令，而后者使用双端链表来实现列表命令
现在，考虑这样一个情况，如果我们对一个键执行LLEN命令，那么服务器除了要确保执行命令的是列表键之外，还要根据键的值对象所使用的编码方式来选择正确的LLEN命令实现：
- 如果列表对象的编码为ziplist，程序将使用ziplistLen函数来返回列表的长度
- 如果列表对象的编码为linkedlist，程序将使用listLength函数来返回双端链表的长度
借用面向对象方面的术语来说，我们可以认为LLEN命令时多态的，只要执行LLEN命令的是列表键，那么无论值对象时压缩列表还是双端链表，命令都可以正常执行。实际上，我们可以将DEL、EXPIRE、TYPE等命令也称为多态命令，因为无论输入的键是什么类型，这些命令都可以正确地执行。
DEL、EXPIRE等命令和LLEN等命令的区别在于，
- 前者是基于类型的多态——一个命令可以同时用于处理多种不同类型的键，
- 而后者是基于编码的多态——一个命令可以同时用于处理多种不同编码
六、内存回收
因为C语言并不具备自动回收内存的功能 ，所以Redis在自己对的对象系统中构建了一个引用计数技术来实现自动回收内存，通过这一机制，程序可以跟踪对象的引用计数信息，在适当的时候自动释放对象并进行内存回收。每个对象的引用计数信息由redisObject结构的refcount属性记录：- typedef struct redisObject {
- unsigned type:4;/* Not used */
- unsigned encoding:4;
- unsigned lru:22;
- //引用计数
- int refcount;
- void *ptr;
- } robj;
- 在创建一个新对象时，引用计数的值会被初始化为1
- 当对象被一个新程序使用时，它的引用计数值会被增一
- 当对象不再被一个程序使用时，它的引用计数值会被减一
- 当对象的引用计数值变为0时，对象所占用的内存会被释放
函数作用incrRefCount将对象的引用计数值增一decrRefCount将对象的引用计数值减一，当对象的引用计数值等于0时，释放对象resetRefCount将对象的引用计数值设置为0，但并不释放对象，这个函数通常在需要重新设置对象的引用计数值时使用
- 对象的整个生命周期可以划分为创建对象、操作对象、释放对象
七 对象共享
除了用于实现引用计数内存回收机制之外，对象的引用计数属性还带有对象共享的作用。
在Redis中，让更多键共享一个值对象需要执行以下两个步骤：
- 将数据库键的值指针指向一个现有的值对象
- 将被共享的值对象的引用计数加1
目前来说，Redis会在初始化服务器时，创建一万个字符串对象，这些对象包含从0到9999的所有整数值，当服务器需要用到值为0到9999的字符串时，服务器就会使用这些共享对象，而不是新创建对象。另外，创建共享字符串的数量可以通过修改redis.h/OBJ_SHARED_INTEGERS来修改
为什么Redis不共享包含字符串的对象？当服务器考虑将一个共享对象设置为键的值对象时，程序需要先检查给定的共享对象和键想创建的目标对象是否相同，只有在共享对象和目标对象完全相同的情况下，程序才会将共享对象用作键的值对象，而一个共享对象保存的值越复杂，验证共享对象和目标对象相同所需的复杂度就会越高，消耗CPU时间也越多：
- 如果共享对象是保存整数值的字符串对象，那么验证操作的时间复杂度为O(1)
- 如果共享对象是保存字符串值的字符串对象，那么验证操作的复杂度为O(N)
- 如果共享对象是包含了多个值（或者对象的）对象，比如列表对象或者哈希对象，那么验证操作的时间复杂度为O(N^2)
因此，尽管共享更复杂的对象可以节约更多内存，但受到CPU时间的限制，Redis只对包含整数值的字符串对象进行共享
八、对象的空转时长
除了前面介绍过的type、encoding、ptr和refcount四个属性外，redisObject结构包含的最后一个属性为lru属性，该属性记录了对象最后一次被命令程序访问的时间：- typedef struct redisObject {
- unsigned type:4;
- unsigned notused:2;
- unsigned encoding:4;
- unsigned lru:22;
- int refcount;
- void *ptr;
- } robj;
OBJECT IDLETIME命令的实现是特殊的，这个命令在访问键时不会修改lru属性。除了可以被OBJECT IDLETIME命令打印出来之外，键的空转时长还有另外一项作用：如果服务器打开了maxmemory选项，并且服务器用于回收内存的算法为volatile-lru（仅对设置了过期时间的键采取LRU淘汰）或者allkeys-lru（对所有的键都采取LRU淘汰），那么当服务器占用的内存超过maxmemory选项所设置的上限值时，空转时长较高的那部分键会优先被服务器释放，从而回收内存
九、数据淘汰策略
9.1 过期淘汰策略
若果采用定时删除策略，当数据库中含有太多的过期数据，则会占用太多CPU时间，影响服务器响应时间和吞吐量，甚至造成堵塞。
- Redis服务器实际使用的是惰性删除和定期删除两种策略，通过配合使用这两种策略，服务器可以很好地在合理使用CPU时间和避免浪费内存空间之间取得平衡。
9.1.3 惰性删除
Redis 4.0 增加了懒惰删除功能，懒惰删除需要使用异步线程对已删除的节点进行内存回收，这意味着 Redis 底层其实并不是单线程，它内部还有几个额外的鲜为人知的辅助线程。
这几个辅助线程在 Redis 内部有一个特别的名称，就是“BIO”，全称是 Background IO，意思是在背后默默干活的 IO 线程。
Redis 大佬 Antirez 实现懒惰删除时，它并不是一开始就想到了异步线程。它最初的尝试是在主线程里，使用类似于字典渐进式搬迁的方式来实现渐进式删除回收。
异步线程释放内存不用为每种数据结构适配一套渐进式释放策略，也不用搞个自适应算法来仔细控制回收频率，只是将对象从全局字典中摘掉，然后往队列里一扔，主线程就干别的去了。异步线程从队列里取出对象来，直接走正常的同步释放逻辑就可以了。
9.1.4 定期删除
- 定期删除策略每隔一段时间执行一次删除过期键操作，并通过限制删除操作执行的时长和频率来减少删除操作对CPU时间的影响
- 除此之外，通过定期删除过期键，定期删除策略有效地减少了因为过期键而带来的内存浪费
定期删除策略的难点是确定删除操作执行的时长和效率
Redis 会将每个设置了过期时间的 key 放入到一个独立的字典中，默认每 100ms 进行一次过期扫描：
- 随机抽取 20 个 key
- 删除这 20 个key中过期的key
- 如果过期的 key 比例超过 1/4，就重复步骤 1，继续删除。
- 为什不扫描所有的 key？
Redis 是单线程，全部扫描岂不是卡死了。而且为了防止每次扫描过期的 key 比例都超过 1/4，导致不停循环卡死线程，Redis 为每次扫描添加了上限时间，默认是 25ms。如果在同一时间出现大面积 key 过期，Redis 循环多次扫描过期词典，直到过期的 key 比例小于 1/4。这会导致卡顿，而且在高并发的情况下，可能会导致缓存雪崩。
9.2 缓存淘汰策略
可以设置内存最大使用量maxmemory，当内存使用量超出时，会施行数据淘汰策略。
Redis 具体有 6 种淘汰策略，配置 maxmemory-policy：：
策略描述volatile-lru从已设置过期时间的数据集中挑选最近最少使用的数据淘汰volatile-ttl从已设置过期时间的数据集中挑选将要过期的数据淘汰volatile-random从已设置过期时间的数据集中任意选择数据淘汰allkeys-lru从所有数据集中挑选最近最少使用的数据淘汰allkeys-random从所有数据集中任意选择数据进行淘汰volatile-lfu对有过期时间的key采用LFU淘汰算法allkeys-lfu对全部key采用LFU淘汰算法noeviction禁止驱逐数据9.1.2 Redis的LRU算法 (Least recently used) 最近最少使用
实现 LRU 算法除了需要 key/value 字典外，还需要附加一个链表，链表中的元素按照一定的顺序进行排列。当空间满的时候，会踢掉链表尾部的元素。当字典的某个元素被访问时，它在链表中的位置会被移动到表头。所以链表的元素排列顺序就是元素最近被访问的时间顺序。
Redis中的LRU与常规的LRU实现并不相同，常规LRU会准确的淘汰掉队头的元素，但是Redis的LRU并不维护队列。只是根据配置的策略
- 要么从所有的key中随机选择N个（5，N可以配置）
- 要么从所有的设置了过期时间的key中选出N个键，然后再从这N个键中选出最久没有使用的一个key进行淘汰。
- Redis3.0之后又改善了算法的性能，会提供一个待淘汰候选key的pool，里面默认有16个key，按照空闲时间排好序。更新时从Redis键空间随机选择N个key，分别计算它们的空闲时间idle，key只会在pool未满或者空闲时间大于pool里最小的时，才会进入pool，然后从pool中选择空闲时间最大的key淘汰掉。
9.1.3 LFU (Least frequently used) 最不经常使用
LFU是在Redis4.0后出现的，LRU的最近最少使用实际上并不精确。LFU 表示按最近的访问频率进行淘汰，它比 LRU 更加精准地表示了一个 key 被访问的热度。
在 LFU 模式下，lru 字段 24 个 bit 用来存储两个值，分别是 ldt(last decrement time) 和 logc(logistic counter)。
- logc 是 8 个 bit，用来存储访问频次，因为 8 个 bit 能表示的最大整数值为 255，存储频次肯定远远不够，所以这 8 个 bit 存储的是频次的对数值，并且这个值还会随时间衰减。如果它的值比较小，那么就很容易被回收。为了确保新创建的对象不被回收，新对象的这 8 个 bit 会初始化为一个大于零的值，默认是 LFU_INIT_VAL=5。
- ldt 是 16 个位，用来存储上一次 logc 的更新时间，因为只有 16 位，所以精度不可能很高。它取的是分钟时间戳对 2^16 进行取模，大约每隔 45 天就会折返。
- lfu-log-factor可以调整计数器counter的增长速度，lfu-log-factor越大，counter增长的越慢。lfu-decay-time是一个以分钟为单位的数值，可以调整counter的减少速度
十、持久化
10.1 RDB持久化
因为Redis是内存数据库，它将自己的数据库状态存储在内存里面，所以如果不想办法将存储在内存中的数据库状态保存到磁盘中，那么一旦服务器进程退出，服务器中的数据库状态也会消失。为了解决这个问题，Redis提供了RDB持久化功能，可以将Redis内存中的数据库状态保存到磁盘中，避免数据意外丢失
10.1.1 是什么
在指定的时间间隔内将内存中的数据集快照写⼊磁盘， 也就是⾏话讲的 Snapshot 快照，它恢复时是将快照⽂件直接读到内存⾥
10.1.2 持久化流程
10.1.3 save vs bgsave
- SAVE命令会阻塞Redis服务器，直到RDB文件创建完毕为止，在服务器进程阻塞期间，服务器不能处理任何命令请求
- BGSAVE命令会派生出一个子进程，然后由子进程负责创建RDB文件，服务器进程（父进程）继续处理命令请求：
- 如果服务器开启了AOF持久化功能，那么服务器就会优先使用AOF文件来还原数据库状态
- 只有在AOF持久化功能处于关闭状态时，服务器才会使用RDB文件来还原数据库状态
10.1.4 BGSAVE命令执行时的服务器状态
- 如果BGSAVE命令正在执行，那么客户端发送的BGREWRITEAOF命令会被延迟到BGSAVE命令执行完毕之后再执行
- 如果BGREWRITEAOF命令正在执行，那么客户端发送的BGSAVE命令会被服务器拒绝
10.1.5 自动间隔性保存
因为BGSAVE命令可以在不阻塞服务器的情况下执行，所以Redis允许用户通过没设置服务器配置的save选项，让服务器每隔一段时间自动执行一次BGSAVE命令。用户可以通过save选项设置多个保存条件，但只要其中一个条件被满足，服务器就会执行BGSAVE命令。
10.1.6 优缺点
- 优点
l 适合大规模的数据恢复
l 对数据完整性和一致性要求不高更适合使用
l 节省磁盘空间
l 恢复速度快
- 缺点
l Fork的时候，内存中的数据被克隆了一份，大致2倍的膨胀性需要考虑
l 虽然Redis在fork时使用了写时拷贝技术,但是如果数据庞大时还是比较消耗性能。
l 在备份周期在一定间隔时间做一次备份，所以如果Redis意外down掉的话，就会丢失最后一次快照后的所有修改。
10.2 AOF持久化
10.2.1 是什么
以日志的形式来记录每个写操作（增量保存），将Redis执行过的所有写指令记录下来(读操作不记录)， 只许追加文件但不可以改写文件，redis启动之初会读取该文件重新构建数据，换言之，redis重启的话就根据日志文件的内容将写指令从前到后执行一次以完成数据的恢复工作
10.2.2 持久化流程
（1）客户端的请求写命令会被append追加到AOF缓冲区内；
（2）AOF缓冲区根据AOF持久化策略[always,everysec,no]将操作sync同步到磁盘的AOF文件中；
（3）AOF文件大小超过重写策略或手动重写时，会对AOF文件rewrite重写，压缩AOF文件容量；
（4）Redis服务重启时，会重新load加载AOF文件中的写操作达到数据恢复的目的；
10.2.3 重写流程
如果Redis的AOF当前大小>= base_size +base_size*100% (默认)且当前大小>=64mb(默认)的情况下，Redis会对AOF进行重写。
（1）bgrewriteaof触发重写，判断是否当前有bgsave或bgrewriteaof在运行，如果有，则等待该命令结束后再继续执行。
（2）主进程fork出子进程执行重写操作，保证主进程不会阻塞。
（3）子进程遍历redis内存中数据到临时文件，客户端的写请求同时写入aof_buf缓冲区和aof_rewrite_buf重写缓冲区保证原AOF文件完整以及新AOF文件生成期间的新的数据修改动作不会丢失。
（4）1).子进程写完新的AOF文件后，向主进程发信号，父进程更新统计信息。2).主进程把aof_rewrite_buf中的数据写入到新的AOF文件。
（5）使用新的AOF文件覆盖旧的AOF文件，完成AOF重写。
10.2.4 优缺点
- 优点
- 备份机制更稳健，丢失数据概率更低。
- 可读的日志文本，通过操作AOF稳健，可以处理误操作。
- 缺点
- 比起RDB占用更多的磁盘空间。
- 恢复备份速度要慢。
- 每次读写都同步的话，有一定的性能压力。
- 存在个别Bug，造成恢复不能。
十一、文件事件
Redis是基于Reactor模式开发了自己的网络事件处理器，这个处理器被称为文件事件处理器：
- 文件事件处理器使用I/O多路复用程序来同时监听多个套接字，并根据套接字目前执行的任务来为套接字关联不同的事件处理器
- 当被监听的套接字准备好执行连接应答（accept）、读取（read）、写入（write）、关闭（close）等操作时，与操作相对应的文件事件就会产生，这时文件事件处理器就会调用套接字之前关联好的事件处理器来处理这些事件
虽然文件事件处理器以单线程方式运行，但通过使用I/O多路复用程序来监听多个套接字，文件事件处理器既实现了高性能的网络通信模型，又可以很好地与Redis服务器中其他同样以单线程方式运行的模块进行对接，这保持了Redis内部单线程设计的简单性
11.1文件事件处理器的构成
文件事件处理器的四个组成部分，它们分别是套接字、I/O多路复用程序、文件事件分派器，以及事件处理器
尽管多个文件事件可能会并发地出现，但I/O多路复用程序总是会将所有产生事件的套接字都放到一个队列中，然后通过这个队列，以有序、同步、每次一个套接字的方式向文件事件分派器传送套接字。当上一个套接字产生的实践被处理完毕之后（该套接字为事件所关联的事件处理器执行完毕），I/O多路复用程序才会继续向文件事件分派器传送下一个套接字
- select：线程不安全，如果任何一个sock(I/O stream)出现了数据，select 仅仅会返回，但是并不会告诉你是那个sock上有数据，
- poll ：线程不安全，去掉了1024个链接的限制
- epoll 现在是线程安全的。 不仅告诉你sock组里面数据，还会告诉你具体哪个sock有数据，你不用自己去找了
十二、主从复制
主机数据更新后根据配置和策略， 自动同步到备机的master/slaver机制，Master以写为主，Slave以读为主
12.1 新版复制功能的实现
为了解决旧版复制功能在处理断线重复制情况时的低效问题，Redis从2.8版本开始，使用PSYNC命令代替SYNC命令来执行复制时的同步操作。PSYNC命令具有完整同步和部分同步两种模式：
- 其中完整重同步用于处理初次复制情况：通过让主服务器创建并发送RDB文件，以及向从服务器发送保存在缓冲区里面的写命令来进行同步。
- 同步
- 从服务器向主服务器发送SYNC命令
- 收到SYNC命令的主服务器执行BGSAVE命令，在后台生成一个RDB文件，并使用一个缓冲区记录从现在开始执行的所有命令
- 当主服务器的BGSAVE命令执行完毕时，主服务器会将BGSAVE命令生成的RDB文件发送给从服务器，从服务器接收并载入这个RDB文件，将自己的数据库状态更新至主服务器执行执行BGSAVE命令时的数据库状态
- 主服务器将记录在缓冲区中的所有写命令发送给从服务器，从服务器执行这些写命令，将自己的数据库状态更新至主服务器数据库当前所处的状态
- 命令传播
- 每当主服务器执行客户端发送的写命令时，主服务器的数据库就有可能会被修改，并导致主从服务器状态不再一致
- 主服务器需要对从服务器执行命令传播操作，主从服务器会将自己的写命令，即是造成主从服务器不一致的那条写命令发送给从服务器执行，当从服务器执行了相同的写命令后，主从服务器将再次回到一致的状态
- 而部分重同步则用于处理断线后重复制情况：当从服务器在断线后重新连接主服务器时，如果条件允许，主服务器可以将主从服务器连接断开期间执行的写命令发送给从服务器，从服务器只要接收并执行这些写命令，就可以将数据库更新至主服务器当前所处的状态。
部分重同步由以下三个部分构成：
- 主服务器的复制偏移量（replication offset）和从服务器的复制偏移量
- 主服务器每次向从服务器传播N个字节的数据时，就将自己的复制偏移量的值加上N
- 从服务器每次收到主服务器传播来的N个字节的数据时，就将自己的复制偏移量的值加上N
- 主服务器的复制积压缓冲区（replication backlog）
- 复制积压缓冲区是有主服务器维护的一个固定长度（fixed-size）先进先出（FIFO）队列，默认大小为1MB。当主服务器进行命令传播时，它不仅将命令发送给所有从服务器，还会将写命令入队到复制积压缓冲区中。
- 主服务器的复制积压缓冲区会保存着一部分最近传播的写命令，并且复制积压缓冲区会为队列的每个字节记录相应的复制偏移量
- 当从服务器重新连上主服务器时，从服务器通过PSYNC命令将自己的复制偏移量offset发送给主服务器，主服务器会根据这个复制偏移量来决定对从服务器执行何种同步操作：
- 如果offset偏移量之后的数据（也即是偏移量offset+1开始的数据）仍然存在于复制积压缓冲区中，那么主服务器将对从服务器执行部分同步操作
- 相反，如果offset偏移量之后的数据已经不存在于复制积压缓冲区，那么主服务器将对从服务器执行完整重同步操作
- 服务器的运行ID（run ID）
- 如果从服务器保存的运行ID和当前连接的主服务器的运行ID相同，那么说明从服务器断线之前复制的就是当前连接的这个主服务器，主服务器可以继续尝试执行部分重同步操作
- 相反地，如果从服务器保存的运行ID和当前连接的主服务器的运行ID并不相同，那么说明从服务器断线之前复制的主服务器并不是当前连接的这个主服务器，主服务器将对从服务器执行完整重同步操作
十三、Redis哨兵高可用框架
哨兵（sentinel）是特殊的Redis服务，不提供读写，主要用来监控Redis实例节点。
哨兵架构下的客户端在第一次从哨兵获得Redis主节点后，后续就直接访问Redis的主节点，不需要每次都通过哨兵访问Redis主节点。当Redis主节点有变化时，哨兵会第一时间感知到，并且将新的Redis主节点通知给客户端(这里面Redis客户端一般都实现了订阅功能，订阅sentinel发布的节点变动消息)。
十四 集群
Redis高可用集群是一个由多个主从节点群组成的分布式服务器群，它具有复制、高可用和分片特性。
Redis集群不需要sentinel哨兵也能完成节点移除和故障转移的功能，只需要将每个节点设置成集群模式，这种集群模式没有中心节点，可水平扩展，官方文档称可以线性扩展到上万个节点(官方推荐不超过1000个节点)。Redis集群的性能和高可用性均优于之前版本的哨兵模式，且集群配置简单。高可用集群相较于哨兵集群，至少不会出现主节点下线后，整个集群在一段时间内处于不可用状态，直到选举出主节点。因为高可用集群有多个主节点，当我们需要向整个Redis服务写入大批量数据时，数据会根据写入的key算出一个hash值，将数据落地到不同的主节点上，所以当一个主节点下线后，落地到其他主节点的写请求还是正常的。
十五 redis引用问题解决
15.1 缓存穿透
- 问题描述
访问一个数据库中没有的键
- 解决方案
- 对空值缓存：如果一个查询返回的数据为空（不管是数据是否不存在），我们仍然把这个空结果（null）进行缓存，设置空结果的过期时间会很短，最长不超过五分钟
- 设置可访问的名单（白名单）：使用bitmaps类型定义一个可以访问的名单，名单id作为bitmaps的偏移量，每次访问和bitmap里面的id进行比较，如果访问id不在bitmaps里面，进行拦截，不允许访问。
- 采用布隆过滤器：布隆过滤器可以用于检索一个元素是否在一个集合中。是一个很长的二进制向量(位图)和一系列随机映射函数（哈希函数）。返回存在不一定存在，返回不存在则一定不存在
- 进行实时监控
15.2 缓存击穿
- 问题描述
- 解决方案
- 预先设置热门数据：在redis高峰访问之前，把一些热门数据提前存入到redis里面，加大这些热门数据key的时长
- 实时调整：现场监控哪些数据热门，实时调整key的过期时长
- 使用锁
15.3 缓存雪崩
- 问题描述
- 解决方案
- 构建多级缓存架构
- 使用锁或队列：用加锁或者队列的方式保证来保证不会有大量的线程对数据库一次性进行读写，从而避免失效时大量的并发请求落到底层存储系统上。不适用高并发情况
- 设置过期标志更新缓存：记录缓存数据是否过期（设置提前量），如果过期会触发通知另外的线程在后台去更新实际key的缓存。
- 将缓存失效时间分散开**：**
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
