Redis

Redis 简介 Redis

Redis是一个内存数据库、一个Key/Value存储系统，支持多种数据结构，包括字符串、哈希、列表、集合、有序集合等。

常用于缓存、消息中转、数据流引擎和分布式锁等

在Redis官方Docs中，可以看到Redis可以用作数据库、缓存、流式处理引擎、消息代理等。还提供了根据不同场景的使用指南

Redis 数据结构 Redis Data Types

Redis是一个数据结构服务，核心是提供一组原生的数据结构帮助服务应用解决各种问题，从缓存到队列到事件处理，都有适用的数据结构.

其核心数据结构有：

String: 字符串，是Redis中最基本的数据结构.
List: 列表，按照插入顺序排序的字符串列表.
Sets: 无序集合，是唯一字符串的无序集合.
Hash: 哈希表，是字段-值集合的记录类型.
ZSet: 有序集合，是唯一字符串的有序集合.
Stream: 流，其作用类似于仅追加的日志，有助于按事件发生的顺序记录事件.
BitMap: 位图，允许对字符串执行按位运算.
Bitfield: 位域，可以有效将多个计数器编码位字符串.
Geospatial: 地理空间，用于存储和查询地理空间数据.

扩展数据结构：

Json: 提供与流行的 JSON 文本文件格式匹配的结构化分层数组和键值对象.
Probabilistic data types: 允许以近似但高效的方式收集和计算统计数据.
Time series: 允许存储和查询带时间戳的数据点.

对于Redis详细的数据结构，可以参考Redis/data-types.

Redis Object 结构

Redis是kv存储，key和value在Redis中被抽象成对于(Object)，key只能是String对象，value支持丰富的对象类型，即上述的Redis数据结构.

RedisObject的结构:

#define LRU_BITS 24

typedef struct reidsObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time or
                            * lFU data */
    int refcount;
    void *ptr;
} robj;

type: RedisObject的类型，如String、List、Hash等，对应上述数据结构.
encoding: RedisObject的编码，表示了哪种底层编码.
lru: 记录RedisObject被访问的时间，用于LRU算法.
refcount: RedisObject的引用计数，表示了RedisObject被引用的次数，即有多少指针指向该对象
ptr: RedisObject的指针，指向RedisObject对应的数据结构.

RedisObject和不同的数据结构及其编码的关系图:

对于Redis在不同场景下使用不同的数据结构，数据结构又有不同的编码，其一般会使用如下规则：

当数据量较少时，尽量使用紧凑结构的编码方式，以节省内存空间，而且因为数据量较少，在性能上不会有太大的影响.
当数据量较大时，将以空间换时间的方式，使用高效的数据编码，以提高性能.

Redis Object 过期时间

Redis的过期时间给一个Key，指定一个时间，当到达这个时间时，Redis会自动删除这个Key.

设置过期时间的目的是可以有效地节省内存，而且在某些场景里，过期时间可以用于实现一些功能，如缓存、限流等.

过期时间的设置

通过以下方法可以设置过期时间:

SET key value EX seconds；
SET key value PX milliseconds；设置毫秒
TTL key；查看还有多少时间过期

在设置过期时间后，会有专门的字典记录key和过期时间.

过期键清除策略

过期之后的键实际上不是立即删除的，一般过期键清除策略有三种：

定时删除
定期删除
惰性删除

定时删除 是在设置键的过期时间的时候，创建一个定时器，让定时器在键过期时间立即执行对键删除操作，定时删除对内存友好，但是对CPU不友好，如果某个时间段比较多的Key过期，可能会影响命令处理性能
惰性删除 是指使用的时候，发现key过期了，此时再进行删除，这个策略的思路是对应用而言，只要不访问，过期不过期业务都无所谓，但是这样的代价是如果某些key一直不访问，那些本该过期的key变成了常驻的key。这种策略对CPU最友好，但是对内存不太友好
定期删除 每过一段时间，程序就对数据库进行一次检查，每次删除一部分过期键，这属于一种渐进式兜底策略
- 定期删除的频率：决定于Redis周期任务的执行频率，周期任务里面会关闭过期客户端、删除过期key的一系列任务，可以用INFO查看周期任务
- 每次删除的数量: 每次检查的数量是写死在代码里面的，每次20个，但是会有一个循环会检查过期key数量占比，大于25%，则再抽查20个来检查，同时Redis为了保证定期不会出现循环过度，导致线程卡死，为此增加了了定期删除循环流程的时间上限，默认不超过25ms

Redis过期键采用的是惰性删除+定期删除二者结合的方式进行删除

Redis< String > Redis String

Redis String 类型，存储字节，包括文本，序列化对象和二进制数组，因此 String是Redis最基本的数据结构 。通常用于缓存，而且Redis支持其他功能，允许实现计数器并执行按位运算.

由于Redis中key是一个字符串，因此Redis使用String数据结构作为key的值.

在默认情况下，Stirng最大为512MB，可以通过配置项proto-max-bulk-len进行修改.

String 适用场景

使用场景：一般用来存放字节数据、文本数据、序列化后的对象数据.

缓存场景：Value存Json字符串等信息.
计数场景：因为Redis处理命令是单线程，所以执行命令的过程是原子的，因此String数据结构适合计数场景.

String 命令

常用命令:

创建 --> set, setnx, getset
- SET key value # 设置一个key值为特定的value
set命令扩展参数： EX（键过期时间秒）、PX（键过期时间毫秒）、NX（只有键不存在时才对键进行操作，基本替代下面的SETNX操作）、XX（键存在时才对键进行操作）
- SETNX key value # 用于在指定的key不存在时，为key设置指定的值，对于实现锁很有用
- GETSET key value # 设置一个key的值，并返回原来的值
查询 --> get, mget
- Get key # 查询某个key，存在就返回对应的value，不存在返回nil
- Mget key [key ...] # 一次查询多个key，如果某个key不存在，对应位置返回nil
更新 --> set
- 见上面的set命令
删除 --> del
- DEL key [key ...] # 删除对象，返回值为删除成功了几行

其他命令：incr, incrby, incrbyfloat

INCR key [increment] # 以原子方式将给定键中存储的计数器加 1
INCRBY key increment # 以原子方式将给定键中存储的计数器加上指定的增量值
INCRBYFLOAT key increment # 以原子方式将给定键中存储的计数器加上指定的浮点数增量值

🔗 String命令列表

String 编码(底层实现)

Redis String类型，底层实现是使用C语言的SDS字符串类型，sds类型是Redis自己实现的一种动态字符串类型，它比C语言的String类型多了一个指针，指向字符串的结尾，方便在字符串末尾追加数据。

String的三种编码方式:
- INT: 存放整形，可以用long表示的整数以该编码存储；
- EMBSTR: 如果字符串 <= 阈值字节(redis.version > 3.2 ? 44 : 39)，使用EMBSTR编码
- RAW: 字符串大于 > 阈值字节(redis.version > 3.2 ? 44 : 39)，使用RAW编码

点击查看EMBSTR的阈值为什么是44？

阈值字节: 在源码中使用OBJ_ENCODING_EMBSTR_SIZE_LIMIT宏定义，默认为44字节，在Redis 3.2版本中，该阈值是39字节.

Redis默认使用jemalloc作为内存分配器
jemalloc是以64字节作为内存单元做内存分配，如果超出了64个字节就超过了一个内存单元. 在内存分配时，RedisObject会尽量在一个内存单元，是为了减少内存寻址，又不会消耗分配过多没用到的内存，
围绕64字节的关键分界分析版本变化，Redis的字符串对象是由一个RedisObject+sdshdr两部分组成，
- RedisObject大小为4+4+24+32+64 = 128bits = 16bytes，其中的ptr是64，是为了方便各种编译器和目标平台上使用
- sdshdr8占用内存大小: 1byte + 1byte + 1byte + 内联数组的大小，由于内联数组中还有一个'\0'占位一个字符，所以能用的大小为64-16(redisObject)-3(sdshdr非内容属性)-1('\0')=44

RedisObject Struct:

#define LRU_BITS 24

typedef struct reidsObject {
    unsigned type:4;        // 4 bit
    unsigned encoding:4;    // 4 bit
    unsigned lru:LRU_BITS;  // 24 bit

    int refcount;           // 32 bit
    void *ptr;              // 64 bit
} robj;                     // 128 bit == 16 bytes

sdshdr Struct:

struct __attribute__((__packed__)) sdshdr8 {
    uint8_t len;          // 1 byte
    uint8_t alloc;        // 1 byte
    unsigned char flags;  // 1 byte
    char buf[];           // '\0' 占位符 1 byte
}

EMBSTR和RAW是由redisObject和SDS两个结构组成，两者差异在于EMBSTR编码下redisObject和SDS是连续的内存，RAW编码下redisObject和SDS的内存是分开的.

EMBSTR的优缺点：

优点：一次性分配内存，redisObject和SDS两个结构一次性分配内存
缺点：重新分配空间时，整体需要重新再分配
EMBSTR设计为只读，任何写操作之后EMBSTR都会变成RAW

编码转化的可能：

INT -> RAW: 当内存不再是整形，或者大小超过了long
EMBSTR -> RAW: 任何写操作之后EMBSTR都会变成RAW

SDS解释

🔗 查看SDS

Redis< List > Redis List

Redis List是一组连续的字符串值链表，这意味着向List的头部或者尾部中添加新元素的操作会在恒定的时间内完成，无论其已经存储了多少元素，但是缺点是访问元素的操作则需要遍历List，时间复杂度为O(N)

Redis List经常用于:

实现堆栈和队列
为后台系统构建队列管理

List 命令

常用命令:

创建 --> LPUSH, RPUSH
- LPUSH key value [value ...] # 从头部增加元素，返回List中元素总数
- RPUSH key value [value ...] # 从尾部增加元素，返回List中元素总数
查询 --> LLEN, LRANGE
- LLEN # 查看List的长度，即List中元素的总数
- LRANGE key start stop # 查看start到stop为角标的元素
更新 --> LPUSH, RPUSH, LPOP, RPOP, LREM
- LPOP key # 移除并获取列表的第一个元素
- RPOP key # 移除并获取列表的第一个元素
- LREM key count value # 移除值等于value的元素
  - count = 0 ，则移除所有等于value的元素；
  - count > 0 ，则从左到右开始移除count个value元素；
  - count < 0，则从右往左移除count个元素
删除 --> DEL, UNLINK
- DEL key [key ...] # 删除对象，返回值为删除成功了几个键
- UNLIKN key [key ...] # 删除对象，返回值为删除成功了几个键

del命令与unlink命令均为删除对象，不同的是del命令是同步删除目录，会阻塞客户端，直到删除完成； unlink命令是异步删除命令，只是取消key在键空间的关联，让其不在能查到，删除是异步进行，所以不会阻塞客户端.

List还支持多个阻塞命令：BLPOP, BLMOVE...

BLPOP # 从列表头部删除并返回一个元素。如果列表为空，则该命令将阻塞，直到有元素可用或达到指定的超时为止.
BMOVE # 以原子方式将元素从源列表移动到目标列表。如果源列表为空，该命令将阻塞，直到有新元素可用.

详细List命令

🔗 List命令列表

List 编码(底层实现)

在Redis.Version < 3.2时，List的编码为ZIPLIST或LINKEDLIST，在Redis.Version >= 3.2时，List的编码为QUICKLIST，当Redis.Version >= 7.0后，ZIPLIST优化为LISTPACK，其本质也是一种压缩列表.

List对象保存的所有字符串长度都小于64字节，且对象元素个数少于512个时，使用ZIPLIST编码，否则使用LINKEDLIST编码.

ZIPLIST的底层使用压缩列表实现，内存排序紧凑，可以有效节省内存空间.

编码详解

🔗 查看ZIPLIST编码

如果使用LINKEDLIST编码，是以链表的形式连接，在内存上不如ZIPLIST紧凑，所以只有在List元素个数或者节点长度比较大的时候，才会使用LINKEDLIST编码.

LINKEDLIST是以牺牲内存换取更快的处理性能.

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;

在Redis 3.2版本只会，引入了QUICKLIST编码. QUICKLIST编码是ZIPLIST和LINKEDLIST的结合体，LINKEDLIST原先的节点存放数据，现在单个节点存放的是一个ZIPLIST.

当数据较少时，QUICKLIST的节点只有一个，相当于一个ZIPLIST.
当数据较多时，则同时利用ZIPLIST和LINKEDLIST的优点.

Redis< Set > Redis Set

Redis Set是一个唯一字符串的集合

适用于：

跟踪唯一目标(e.g., 跟踪访问给定博客的所有唯一IP地址)
表示关系(e.g., 具有给定角色的所有用户集合)
执行常见的集合运算(e.g., 根据集合运算能力获取不同用户的共同信息)

Redis Set的最大大小为2^32-1(4294967295)

Set 命令

Set的基本操作有：

创建：SADD
- SADD key member [member ...] # 添加元素，返回值为成功添加了几个元素
查询：SISMEMBR, SCARD, SMEMBERS, SSCAN, SINTER, SUNION, SDIFF
- SISMEMBER key member # 查询元素是否存在
- SCARD key # 查询集合元素个数
- SMEMBERS key # 查看集合的所有元素
- SSCAN key cursor[MATCH pattern][COUNT count] # 查看集合元素，可以理解为指定游标进行查询，可以指定个数，默认为10
- SINTER key [key ...] # 返回在第一个集合，同时在后面所有集合都存在元素
- SUNION key [key ...] # 返回所有集合的并集，集合个数大于等于2
- SDIFF key [key ...] # 返回第一个集合有，且后续集合中不存在的元素，结合个数大于等于2，注意
更新：SADD, SREM
- SADD -- > 参考上文
- SREM key member [member ...] # 删除元素，返回值为成功删除几个元素
删除：DEL
- DEL key 删除元素

详细Set命令

🔗 Set命令列表

Set 编码(底层实现)

Redis Set的底层编码是: INTSET, HASHTABLE

INTSET：存储元素为整数，且元素数量不超过52个，其结构如下

text

<encoding> <length> <contents>

<contents> --> <value1><value2>...

可以看到INTSET的结构排列紧凑，内存占用少，查询的时候使用二分查找，之所以使用二分查找是因为INTSET存储的元素是排序的，且元素个数不多，但是对于Redis Set来说，应该将INTSET编码下的元素视为无序，不应该依赖其有序性，整体上应该当初无序来使用

HASHTABLE：是一个哈希表，查询一个元素的性能很高，在O(1)时间复杂度情况下返回元素.

值得注意的是Redis Hash使用的底层编码也有HASHTABLE

Set 使用HASHTABLE编码时，只存储键，不存储值，因而其key永远指向NULL

编码详解

🔗 查看HASHTABLE编码

Redis< Hash > Redis Hash

Redis Hash 是结构化为字段值(field)->值(value)集合的记录类型. 可以使用Hash来表示基础对象并存储计数器分组.

创建的Hash数量没有实际限制，除了受到可用内存的限制，但是每个Hash最多可以存储 4,294,967,295 (2^32 - 1) 个字段值对

Hash可以很方便的表示对象

Hash 命令

Hash常用命令：

创建：HSET, HSETNX
- HSET key field value # 为集合对于field设置value，可以一次设置多个field-value
- HSETNX key field value # 如果field不存在，则为集合对应field设置value数据
查询：HGETALL, HGET, HLEN, HSCAN
- HGETALL key # 查找全部数据
- HGET key field # 查找某个key（field）
- HLEN key # 查找Hash中元素总数
- HSCAN key cursor [MATCH pattern] [COUNT count] # 从指定位置查询一定数量的数据，这里注意如果是小数据量下，处于ZIPLIST时，COUNT不管填多少，都是返回全部，因为ZIPLIST本身就用于小集合，没必要切分几段返回
更新：HSET, HSETNX, HDEL
- HDEL key field [field ...] # 删除指定field，可以一次删除多个
删除：DEL
- DEL key [key ...] # 删除Hash对象

Hash 编码(底层实现)

Hash底层有两个编码方式：ZIPLIST, HASHTABLE

ZIPLIT编码需要满足以下条件:
- Hash对象保存的所有值和键的长度都小于64字节
- Hash对象保存元素对象小于512个

当Hash的底层编码为ZIPLIST时，即数量较少时将数据紧凑排列，对应到Hash，就是将field-value当作entry存放进ZIPLIST.

如果Hash的底层编码为HASHTABLE时，与上面的Set（无序列表）使用HASHTABLE，区别在于在Set中Value始终为null，但是在Hash中，具有对应的值.

编码详解

🔗 查看HASHTABLE编码

Redis< ZSet > Redis Sorted Set

Redis ZSet 是一个关联分数排序的唯一字符串集合. 当多个字符串具有相同分数时，字符串会按照字典顺序排列。

ZSet可以适用于:

排行榜. 使用ZSet维护大型游戏中最高分数的有序列表.
速率限制器. 使用ZSet构建滑动窗口速率限制器，以防止过多的API请求.

ZSet可以视为是集合和哈希的混合，一方面，其与集合类似，由唯一的、不重复的字符串元素组成；另一方面，集合内元素没有排序，但是排序集合中每个元素都和一个浮点值相关联，也就是类似于哈希，每个元素映射一个值

此外，排序集中的元素是按顺序获取的，这个顺序遵守以下规则：

如果 B 和 A 是具有不同分数的两个元素，则如果 A.score 是 > B.score，则 A > B.
如果 B 和 A 的分数完全相同，则如果 A 字符串按字典顺序大于 B 字符串，则 A > B。 B 和 A 字符串不能相等，因为排序集仅具有唯一元素

ZSet 命令

ZSet常见命令：

创建：ZADD
- ZADD key score member [score member] # 向Sorted Set增加数据，如果key已经存在的Key，则更新对应的数据
  - 扩展参数：XX, NX, LT, GT
查询：ZRANGE, ZCOUNT, ZRANK, ZCARD, ZSCORE
- ZCARD key # 查看ZSet中的成员
- ZRANGE key start stop [WITHSCORES] # 查询从start到stop范围的ZSet数据，WITHSCORES选填，不写输出里只有key，没有score值
- ZREVRANGE key start stop [WITHSCORES] # 即reverse range，从大到小遍历，WITHSCORES选项，不写不会输出score
- ZCOUNT key min max # 计算min-max积分范围的成员
- ZRANK key member # 查看ZSet中member的排名索引，索引从0开始，所以排名是第一，索引就是0
- ZSCORE key member # 查询ZSet成员的分数
更新：ZADD, ZREM
- ZREM key member [member ...] # 删除ZSet中的元素
删除：DEL, UNLINK

详细ZSet命令

🔗 ZSets命令列表

ZSet 编码(底层实现)

ZSet底层编码有两种：ZIPLIST， SKIPLIST+HASHTABLE

ZIPLIST
- 列表对象保存的所有字符串对象长度都小于64字节，且列表对象元素个数少于128个
- 使用ZIPLIST的目的是在数据量小的时候节省内存，在紧凑的结构中以value+score的形式存放进ziplist.entry

当上述条件不符合的时候，编码使用SKIPLIST+HASHTABLE

SKIPLIST是一种可以快速查找的多级链表结构，通过SKIPLIST可以快速定位到数据所在，它的排名操作、范围查询性能都很高

编码详解

🔗 查看SKIPLIST编码

Redis< Stream > Redis Stream

Redis Stream是一种数据结构，其作用类似于仅追加日志，但也实现了多种操作克服典型的仅追加日志的限制. 包括O(1)时间内的随机访问和复杂的消费策略

Stream的使用示例：

1. 事件溯源(追踪用户操作、点击)；
2. 传感器健康;
3. 通知(将每个用户的通知存储在单独的流中)

Redis为每个流条目生成一个唯一ID，可以使用这些ID检索其关联条目或读取并处理流中的所有后续条目

Redis支持多种修剪策略和多种消费策略

Stream 命令

XADD # 将新条目添加到流中
XREAD # 读取一个或多个条目，从给定位置开始并及时向前移动
XRANGE # 返回两个提供的条目ID之间的条目范围
XLEN # 返回流的长度

TIP

Redis Stream 详细请阅读 Redis Stream

Redis< enc-SDS > Redis Encoding SDS

sds(Simple Synamic String)，简单动态字符串，是redis内部作为基石的字符串封装（很重要）

sds是redis封装字符串结构，用以解决字符串追加和长度计算操作来带的性能瓶颈问题

redis中SDS分为sdshdr8、sdshdr16、sdshdr32、sdshdr64，字段属性一致，区别再对应不同大小的字符串

struct __attribute__((__packed__)) sdshdr8 {
    uint8_t len;   // 使用了多少内部
    uint8_t alloc; // 分配了多少内存
    unsigned char flags; // 标记是什么分类 例如： #define SDS_TYPE_8 1
    char buf[];
}

从上面的结构可以看出SDS是怎么解决问题的：

增加len字段，快速返回长度
增加空余空间(alloc - len)，为后续追加数据留余地
不要以'\0'作为判断标准，二进制安全

SDS预留空间大小的规则：alloc = min(len, 1M) + len：

len小于1M的情况下，alloc=2*len, 预留len大小的空间
len大于1M的情况下，alloc=1M+lne, 预留1M大小的空间

Redis< enc-ZipList > Redis Encoding ZipList

ZIPLIST压缩列表，是排列紧凑的列表，为Redis供紧凑型的数据存储方式，能节约内存（节省链表指针的开销），数据量小的时候遍历访问性能好（连续+缓存命中率友好）

关于LISTPACK是Redis 5.0引入，Redis 7.0完全替代ZIPLIST.

ZIPLSIT 整体结构

text

// redis代码注释，描述了ZIPLIST的结构

 <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

各字段定义：

zlbytes: 表示该ZIPLIST一共占了多少字节，这个数字是包含zlbytes本身占据的字节的
zltail: ZIPLIST尾巴节点，相对于ZIPLIST的开头，偏移的字节数
zllen: 表示有多少个数据节点
entry: 表示压缩列表的数据节点
zlend: 一个特殊的entry节点，为1个字节11111111即255占据，表示ZIPLIST的结束

ZIPLIST 节点结构 - entrys

其定义如下

text

 * <prevlen> <encoding> <entry-data>

各字段含义：

prevlen: 表示前一个节点的长度。通过该节点定位到前一个节点的起始地址，如果前一个节点是压缩列表的开头，那么这个字段的值为0，通过该字段，可以实现往前操作，即ZIPLIST可以从后往前遍历.
有关上一个entry的长度，从prevlen字段可以获得，根据entry的大小，prevlen所占字节也会有所变化:
- entry < 254 : prevlen为1字节，(值得注意的是255在entry中是个特殊数字，被zlend使用，表示ZIPLIST的结束)
- entry >= 254 : prevlen为5字节，在这5个字节中，第一个字节作为标志位，固定为11111110，表示prevlen是5个字节，后面4个字节才是prevlen记录的上一个节点长度.
encoding: 编码类型，包含了entry的长度信息，用于正序遍历.
encoding是一个整型数据，其二进制数据由entry-data的类型和字节长度组成
- 如果是string类型，那么encoding由两部分，前几位为标识位、后几位标识长度
- 如果是int类型，整体1字节编码，那么仅标识类型，根据不同的int类型，确定其长度，例如int32就是32位，4字节
entry-data: 实际的数据

ZIPLIST 查询数据

获取节点数量 ZIPLIST可以在O(1)时间复杂度返回节点数量，因为其header定义了记录节点数量的zllen，但是zllen仅占2字节长度，最大记录65534，当节点数量超过65535时，就需要通过遍历节点获取节点数量.

之所以zllen是2个字节，原因是redis中应用ZIPLIST是为了节点个数少的场景，所以将zllen设计得比较小，节约内存空间

查询指定数据的节点

在ZIPLIST中查询指定数据的节点，需要遍历压缩列表，平均时间复杂度为O(N)

ZIPLIST 更新数据

ZIPLIST的更新就是增加、删除数据，ZIPLIST提供头尾增减的能力，平均时间复杂度O(N)，因为在头部增加一个节点会导致后面节点都往后移动，所以更新平均时间复杂度O(N).

更新操作可能带来连锁更新，连锁更新是指节点后移发生不止一次，而是多次

连锁更新的触发条件是：插入一个大于254字节的元素时，如果记录新元素的长度的下一节点的prevlen原本为1字节，但是因为新元素的长度大于254字节，导致prevlen需要变成5字节，导致后面节点的prevlen可能需要跟着变化，这就是ZIPLIST的连锁更新.

尽管连锁更新可能导致性能问题，但实际上这种情况发生的概率较低。因为要发生连锁更新，需要ZipList中有连续多个长度刚好为250到253字节的节点，这种情况在实际应用中并不常见.

LISTPACK 优化

LISTPACK是为了解决ZIPLIST最大的痛点——连锁更新

ZIPLIST需要支持LIST，LIST是一种双端访问的结构，所以需要能从后往前遍历 ZIPLIST的数据节点：prevlen encoding entry-data 其中，prevlen表示上个节点的数据长度，通过这个字段可以定位上一个节点的数据连锁更新的问题，就是因为prevlen导致的

LISTPACK以一种不记录prevlen，并且还能找到上一个节点的起始位置的节点结构，解决ZIPLIST存在的连锁更新问题

text

<encoding-type> <element-data> <element-tot-len>

encoding-type是编码类型，element-data是数据内容，element-tot-len存储整个节点除了它自身之外的长度即element-type和element-data的长度之和
element-tot-len所占用的每个字节的第一个bit用于标识是否结束，第一个bit 0 是结束 1 是继续，剩下7个bit来存储数据大小

Redis< enc-HashTable > Redis Encoding HASHTABLE

HASHTABLE可以使用O(1)时间复杂度能够快速找到field对应的value，简单理解，HASHTABLE是一个目录，可以帮助我们快速找到需要内容

HASHTABLE的结构:

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

最外层封装一个dictht结构，字段含义如下：

Table: 指向实际hash存储。存储可以看做一个数组
Size: 哈希表大小，实际就是dictEntry有多少元素空间
Sizemask: 哈希表大小的掩码表示，总是等于size-1. 这个属性和哈希值一起决定一个键应该放到table数组的那个索引上面，规则 Index = hash & sizemask.
Used: 表示已经使用的节点数量。通过这个字段可以查询目前HASHTABLE元素总量

dictEntry结构如下：

typedef struct dictEntry {
    void *key;

    union {
      void *val;
      uint64_t u64;
      int64_t s64;
      double d;
    } v;
    struct dictEntry *next;

    void *metadata[];
} dictEntry;

Hash 渐进式扩容/缩容

扩容

渐进式扩容就是一点一点扩大HASHTABLE的容量，默认值为4 (#define DICT_HT_INTTIAL_SIZE 4) 为了实现渐进式扩容，Redis没有直接把dictht暴露给上层，而是再封装了一层

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

dict结构里面，包含了2个dictht结构，也就是2个HASHTABLE结构。

dictEntry是链表结构，用拉链法解决Hash冲突，用的是头插法

实际上，平时使用的时候就是一个HASHTABLE，在触发扩容之后，就会有两个HASHTABLE同时使用，详细过程如下：当向字典添加元素时，需要扩容时会进行rehash

Rehash流程分以下三步：

为新Hash表ht[1]分配空间，新表大小为第一个大于等于原表ht[0]的2倍used的2次幂。例如，原表used=500，2*used=1000，第一个大于1000的2次幂为1024，因此新表的大小为1024. 此时，字典同时持有ht[0]和ht[1]两个哈希表，字典的偏移索引rehashidx从静默状态-1，设置为0，表示Rehash正式开始工作。
迁移ht[0]数据到ht[1]在Rehash进行期间，每次对字典执行增删改查操作，程序会顺带迁移当前rehashidx在ht[0]上的对应数据，并更新偏移索引(rehashidx)。
随着字典操作的不断执行，最终在某个节点，ht[0]的所有键值对会被Rehash到ht[1]，此时再将ht[1]和ht[0]两个指针对象互换，同时把偏移索引的值设置为-1，表示Rehash操作已经完成。小总结：渐进式扩容的核心是操作时顺带迁移

扩容时机

redis提出一个负载因子的概念，负载因子表示目前Redis HASHTABLE的负载情况

用k表示负载因子：k=ht[0].used/ht[0].size，也就是使用空间和总空间大小的比例，redis会根据负载因子的情况来扩容：

负载因子 k大于1 时，说明此时空间非常紧张，新数据在链表上叠加，越来越多的数据导致查询无法在O(1)时间复杂度找到，还要遍历链表，如果此时服务器没有执行BGSAVE或BGREWRITEAOF两个命令，就会发生扩容。
负载因子 k大于5 时，说明HASHTABLE已经不堪重负，此时即使有复制命令在，也要进行扩容

缩容

当有了多余的空间，如果不释放，就会导致多余的空间被浪费

缩容过程和扩容是相似的，也是渐进式缩容，同样缩容时机也是用负载因子来控制的

当负载因子小于0.1，此时进行缩容，新表的大小为第一个大于等于used的2次幂

使用BGSAVE或BGREWRITEAOF两个复制命令，缩容也会受影响，不会进行

Redis< enc-SkipList > Redis Encoding SKIPLIST

跳表是Redis有序集合ZSet底层的数据结构

redis中跳表的两处应用：

1. 实现有序集合键
2. 在集群节点中作为内部数据结构

从本质上看是链表，这种结构虽然简单清晰，但是查询某个节点的效率比较低，而在有序集合场景，无论是查找还是添加删除元素，我们是需要快速通过score定位到具体位置，如果是链表的话时间复杂度是O(N)

为了提高查找的性能，Redis引入跳表，跳表在链表的基础上，给链表增加了多级的索引，通过索引可以一次实现多个节点的跳跃，提高性能

SKIPLIST 结构

Redis SKIPLIST 单节点的结构:

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

字段的定义：

Ele: SDS结构，用来存储数据
Score: 节点的分数，浮点型数据
Backward: 指向上一个节点的回退指针，支持从表尾向表头遍历，也就是ZREVRANGE这个命令
level: 是个zskiplistLevel结构体数组，包含两个字段，一个是forward，指向该层下个能跳到的节点，span记录距离下个节点的步数，数组结构表示每个节点可能是多层结构

在标准的跳表中，score值是不可重复的，但是在Redis ZIPLIST中，score值是可重复的，增加了回退指针

SKIPLIST 细节

Redis跳表单个节点有几层？

层次的决定，需要比较随机，才能在各个场景表现出较平均的性能，这里Redis使用概率均衡的思路来确定插入节点的层数：

Redis跳表决定每一个节点，是否能增加一层的概率为25%，而最大层数限制在Redis 5.0是64层，在Redis 7.0是32层

Redis跳表的性能优化了多少？

平均时间复杂度为O(log(n))，跳表的最坏平均时间复杂度是O(N)，当然实际的生产过程中，体现出来的基本是跳表的平均时间复杂度

Redis 架构 Redis Arch

Redis的架构：

单线程模型
Reactor
多线程优化解包
多进程处理持久化任务
过期淘汰算法

通过了解Redis的架构，可以更好地理解Redis的工作原理，了解其执行流程，对后续的Redis持久化、应用场景等有更好的理解

Redis 单线程模型 Redis Single Thread

redis是一个能高效处理请求的组件

核心处理逻辑：Redis一直都是单线程，其他辅助模块会有一些多线程、多进程的功能，例如：复制模块用的多进程；某些异步流程从4.0开始用多线程；网络I/O解包从6.0开始用多线程；

Redis在处理客户端的请求时，包括获取（socket写）、解析、执行、内容返回等都是由一个顺序串行的主线程处理，这就是所谓的单线程

Redis 单线程的选择

Redis的定位是内存k-v存储，是做短平快的热点数据处理，一般来说执行会很快，执行本身不会成为瓶颈，瓶颈通常在网络I/O，处理逻辑多线程并不会有太大收益

同时Redis本身秉持简洁高效的理念，代码的简单性、可维护性是redis一直依赖的追求，执行本身不应该成为瓶颈，而且多线程本身也会引起额外成本

引入多线程带来复杂度和额外成本

多线程引入的复杂度是极大的
- 多线程引入后，redis原来的顺序执行特性就不复存在，为了事务的原子性、隔离性，redis就不得不引入一些很复杂的实现
- redis的数据结构是极其高效，在单线程模式下做了很多特性的优化，如果引入多线程，那么所有底层数据都要改为线性安全，这很复杂
- 多线程模式使得程序调试更加复杂和麻烦，会带来额外的开发成本及运营成本
多线程带来额外的成本
- 上下文切换成本，多线程调度需要切换线程上下文，这个操作先存储当前线程的本地数据，程序指针，然后载入另一个线程数据，这种内核操作的成本不可忽略
- 同步机制的开销，一些公共资源，在单线程模式下直接访问就行，多线程需要通过加锁等方式进行同步
- 一个线程本身也占据内存大小，对redis这种内存数据库来说，内存非常珍贵，多线程本身带来的内存使用的成本也需要谨慎决策

Redis 单线程的高性能

Redis 核心的请求处理是单线程，但是Redis却能使用单线程模型达到每秒数万级别的处理能力，这是Redis多方面极致设计的一个综合结果.

Redis的大部分操作在内存上完成，内存操作本身就特别快
Redis选择了很多高效的数据结构，并做了很多优化，比如ziplist，hash，skiplist等，有时候一种对象底层有几种实现以应对不同场景
Redis采用了多路复用机制，使其在网络IO操作中能并发处理大量的客户端请求，实现高吞并量

Redis I/O多路复用

Redis在内存中处理数据，其性能瓶颈更多是在I/O

Redis的I/O多路复用机制，是指Redis在处理客户端请求时，通过使用操作系统提供的I/O多路复用功能，实现同时处理多个客户端的请求，而不是阻塞等待每个请求的处理完成

Redis做了一层包装，叫Reactor模型，本质就是监听各种事件，当事件发生时，将事件分发给不同的处理器

I/O多路复用让redis单线程有了较大的并发度，这里是并发，不是并行，这种模式下，Redis单核的性能可以是被充分利用

Redis 多线程持久化 Redis Multi Thread Persistence

Redis多线程模型

redis一开始就是基于单线程模型，Redis里所有的数据结构都是非线程安全，规避了数据竞争问题，使得Redis对各种数据结构的操作非常简单

redis选择单线程的核心原因是Redis都是内存操作，CPU处理都非常快，瓶颈更容易出现在I/O而不是CPU，所以选择了单线程模型

随着数据量的增大，redis的瓶颈更容易出现在I/O而不是CPU

因为上述情况，Redis选择了引入多线程来处理网络I/O，这样即保持了Redis核心的单线程处理价格，又引入了多线程解决提高网络I/O的性能

Redis

Redis 简介 Redis ​

Redis 数据结构 Redis Data Types ​

Redis Object 结构 ​

Redis Object 过期时间 ​

过期时间的设置 ​

过期键清除策略 ​

Redis< String > Redis String ​

String 适用场景 ​

String 命令 ​

String 编码(底层实现) ​

Redis< List > Redis List ​

List 命令 ​

List 编码(底层实现) ​

Redis< Set > Redis Set ​

Set 命令 ​

Set 编码(底层实现) ​

Redis< Hash > Redis Hash ​

Hash 命令 ​

Hash 编码(底层实现) ​

Redis< ZSet > Redis Sorted Set ​

ZSet 命令 ​

ZSet 编码(底层实现) ​

Redis< Stream > Redis Stream ​

Stream 命令 ​

Redis< enc-SDS > Redis Encoding SDS ​

Redis< enc-ZipList > Redis Encoding ZipList ​

ZIPLSIT 整体结构 ​

ZIPLIST 节点结构 - entrys ​

ZIPLIST 查询数据 ​

ZIPLIST 更新数据 ​

LISTPACK 优化 ​

Redis< enc-HashTable > Redis Encoding HASHTABLE ​

Hash 渐进式扩容/缩容 ​

扩容 ​

扩容时机 ​

缩容 ​

Redis< enc-SkipList > Redis Encoding SKIPLIST ​

SKIPLIST 结构 ​

SKIPLIST 细节 ​

Redis 架构 Redis Arch ​

Redis 单线程模型 Redis Single Thread ​

Redis 单线程的选择 ​

引入多线程带来复杂度和额外成本 ​

Redis 单线程的高性能 ​

Redis I/O多路复用 ​

Redis 多线程持久化 Redis Multi Thread Persistence ​

Redis 过期淘汰算法 Redis Expire Algorithm ​

Redis 简介 Redis

Redis 数据结构 Redis Data Types

Redis Object 结构

Redis Object 过期时间

过期时间的设置

过期键清除策略

Redis< String > Redis String

String 适用场景

String 命令

String 编码(底层实现)

Redis< List > Redis List

List 命令

List 编码(底层实现)

Redis< Set > Redis Set

Set 命令

Set 编码(底层实现)

Redis< Hash > Redis Hash

Hash 命令

Hash 编码(底层实现)

Redis< ZSet > Redis Sorted Set

ZSet 命令

ZSet 编码(底层实现)

Redis< Stream > Redis Stream

Stream 命令

Redis< enc-SDS > Redis Encoding SDS

Redis< enc-ZipList > Redis Encoding ZipList

ZIPLSIT 整体结构

ZIPLIST 节点结构 - entrys

ZIPLIST 查询数据

ZIPLIST 更新数据

LISTPACK 优化

Redis< enc-HashTable > Redis Encoding HASHTABLE

Hash 渐进式扩容/缩容

扩容

扩容时机

缩容

Redis< enc-SkipList > Redis Encoding SKIPLIST

SKIPLIST 结构

SKIPLIST 细节

Redis 架构 Redis Arch

Redis 单线程模型 Redis Single Thread

Redis 单线程的选择

引入多线程带来复杂度和额外成本

Redis 单线程的高性能

Redis I/O多路复用

Redis 多线程持久化 Redis Multi Thread Persistence

Redis 过期淘汰算法 Redis Expire Algorithm