Redis底层数据结构

# Redis底层数据结构

Redis数据结构如下：

相比关系型数据库，Redis有库的概念但是没有表的概念。一个Redis实例下默认有16个库，每个库（DB）以编号区分（0开始），每个DB就是key的命名空间。value对应的是Redis提供的一些数据类型，比如string、list、hash、set、zset、bitmap等等。

Redis的库底层的数据结构是RedisDB，key-value的value的底层数据结构是RedisObject。

# RedisDB数据结构

Redis有“数据库”的概念，该结构由redis.h中的redisDB定义。

当 Redis 服务器初始化时，会预先分配 16 个数据库（该项是可配置的）。这些数据库对象会被保存到结构 redisServer 的一个成员 redisServer.db 数组中。而redisClient中则会存在一个名叫db的指针指向当前使用的数据库。

server.h中redisDB结构体源码：

typedef struct redisDb { 
  int id; // id是数据库序号，为0-15（默认Redis有16个数据库） 
  long avg_ttl; // 存储的数据库对象的平均ttl（time to live），用于统计 
  dict *dict; // 存储数据库所有的key-value（重点）
  dict *expires; // 存储key的过期时间（重点）
  dict *blocking_keys; // blpop 存储阻塞key和客户端对象 
  dict *ready_keys; // 阻塞后push 响应阻塞客户端 存储阻塞后push的key和客户端对象 
  dict *watched_keys; //存储watch监控的的key和客户端对象 
} redisDb;

# RedisObject数据结构

Value是一个对象，包含字符串对象，列表对象，哈希对象，集合对象和有序集合对象。

server.h中redisObject结构体源码：

typedef struct redisObject { 
  unsigned type:4; // 类型 五种对象类型 
  unsigned encoding:4; // 对象 编码 
  void *ptr; // 指向底层实现数据结构的指针 
  int refcount; // 引用计数  
  unsigned lru:LRU_BITS; // LRU_BITS为24bit 记录最后一次被命令程序访问的时间 
}robj;

type：表示对象的类型，占 4 位。可以通过type命令，读取 key对应的value指向的 RedisObject 对象的 type 字段获得类型：
```
127.0.0.1:6379> type k1 
string
```
主要有七种type：字符串对象*、跳跃表*、字典*、压缩列表、整数集合、快速列表*、流对象。
encoding：表示对象的内部编码，占 4 位。Redis 可以根据不同的使用场景来为对象设置不同的编码，目的是提高了 redis 的灵活性和效率。通过 object encoding 命令，可以查看对象采用的编码方式：
```
127.0.0.1:6379> object encoding k1 
"int"
```
type 和 encoding 的关联：我们知道，type指的是value对象使用的redis定义的数据类型，如string、hash、list等等，而encoding是指这些存储这些数据类型选择的编码方式。例如，存储了一个k1，value是1。那么它的type是stirng，而encoding就是int。
lru：记录的是对象最后一次被命令程序访问的时间，4.0 版本占 24 位，2.6 版本占 22 位。高16位存储一个分钟数级别的时间戳，低8位存储访问计数。（lru，高16位: 最后被访问的时间；lfu，低8位：最近访问次数）
refcount：记录的是该对象被引用的次数，类型为整型。主要用于对象的引用计数和内存回收。当对象的 refcount>1时，称为共享对象。Redis 为了节省内存，当有一些对象重复出现时，新的程序不会创建新的对象，而是仍然使用原来的对象。
ptr：指针指向具体的数据，比如：set hello world，ptr 指向包含字符串 world 的 SDS。

# RedisObject.type详解

Type主要有七种type：字符串对象*、跳跃表*、字典*、压缩列表、整数集合、快速列表*、流对象。

# 字符串对象

Redis 使用了 SDS(Simple Dynamic String，简单动态字符串)，用于存储字符串和整型数据。

SDS源码结构体定义如下：

struct sdshdr{ 
  int len; // 记录buf数组中已使用字节的数量 
  int free; // 记录 buf 数组中未使用字节的数量 
  char buf[]; // 字符数组，用于保存字符串, 通常最后以"\0"表示结尾，长度=len+free+1
}

SDS的优势：

SDS 在 C 字符串的基础上加入了 free 和 len 字段，使得操作时间复杂度降低。

例如，获取字符串长度：SDS 是 O(1)，而C 字符串是O(n)。（长度=len+free+1）
SDS 由于记录了长度，在可能造成缓冲区溢出时会自动重新分配内存，杜绝了缓冲区溢出。
可以存取二进制数据，以字符串长度len来作为结束标识

C语言中是以空字符串\0 表示字符串的结尾，而二进制数据包括空字符串，所以没有办法存取二进制数据。 SDS如果表示的是二进制，那么它可以使用字符串长度来控制这个问题。

使用场景：主要应用在存储字符串和整型数据、存储key、AOF缓冲区和用户输入缓冲。

# 跳跃表-sortedset

跳跃表是有序集合（sorted-set）的底层实现，效率高。

基本思想是将有序链表中的部分节点分层，每一层都是一个有序链表。

zset的排序是怎么实现的，增删改查的速度？大致结构如下:

左上角其实一直有元素存在，在开始的时候。会先放一个负无穷的数字，保证每一层的开始都是这个负无穷的数字，目的是为了防止很大的数字被提升之后的情况

查找：跳跃表在查找时优先从最高层开始向后查找，当到达某个节点时，如果next节点值大于要查找的值或next指针指向null，则从当前节点下降一层继续向后查找。这种每次跳层查找的过程就是我们说的“跳跃”，这种数据结构具有二分查找的功能，差不多就是一颗二叉树，只是有太多的重复元素，查找的时间复杂度为O(logn)；
插入：插入元素的策略是从寻找到最低层的插入位置后，执行插入操作，完成之后就采用随机造层的策略。
- 随机造层：抛硬币算法（五五开），正面的话，向上提升一层，然后在继续抛硬币，正面继续提升，继续抛硬币，直到反面出现为止；理想的层数是logn。
删除：先查找删除节点，如果否有下层，则继续往下删除。
修改：先查找修改位置，后依次往下层修改值。

插入、删除、修改都依赖查找，所以总体时间复杂度是O(logn)。

https://www.cnblogs.com/acfox/p/3688607.html

# 字典-hash

字典dict又称散列表（hash），是用来存储键值对的一种数据结构。

Redis整个数据库是用字典来存储的。对Redis进行CURD操作其实就是对字典中的数据进行CURD操作。

# 实现原理

hash通常采用数组+链表的方式实现。

数组：用来存储数据的容器，采用头指针+偏移量的方式能够以O(1)的时间复杂度定位到数据所在的内存地址。
Hash函数：把任意长度的输入通过散列算法转换成固定类型、固定长度的散列值。例如，redis中对key进行计算，计算的结果就是数组对应的下标。数组下标=hash(key)%数组容量。
Hash冲突，链表介入：不同的key经过计算后可能会出现数组下标一致的情况，称为Hash冲突。这个时候链表就可以介入了：可以采用单链表在相同的下标位置处存储原始key和value。当根据key找Value时，找到数组下标，遍历单链表可以找出key相同的value。

# Redis字典的实现

包含字典(dict)、Hash表(dictht)、Hash表节点(dictEntry)。

字典(dict)源码结构体定义如下：

typedef struct dict { 
  dictType *type; // 该字典对应的特定操作函数 
  void *privdata; // 上述类型函数对应的可选参数 
  dictht ht[2]; // 两张哈希表，存储键值对数据，ht[0]为原生哈希表， ht[1]为rehash 哈希表
  long rehashidx; // rehash标识 当等于-1时表示没有在rehash，
                 // 否则表示正在进行rehash操作，存储的值表示hash表ht[0]的rehash进行到哪个索引值 (数组下标)
  int iterators; // 当前运行的迭代器数量 } dict;

type字段：指向dictType结构体，里边包括了对该字典操作的函数指针

typedef struct dictType { 
  // 计算哈希值的函数 
  unsigned int (*hashFunction)(const void *key); 
  // 复制键的函数 
  void *(*keyDup)(void *privdata, const void *key); 
  // 复制值的函数 
  void *(*valDup)(void *privdata, const void *obj); 
  // 比较键的函数 
  int (*keyCompare)(void *privdata, const void *key1, const void *key2); 
  // 销毁键的函数 
  void (*keyDestructor)(void *privdata, void *key); 
  // 销毁值的函数 
  void (*valDestructor)(void *privdata, void *obj); 
} dictType;

Redis字典除了主数据库的K-V数据存储以外，还可以用于：散列表对象、哨兵模式中的主从节点管理等。
在不同的应用中，字典的形态都可能不同，dictType是为了实现各种形态的字典而抽象出来的操作函数（多态）。

Hash表(dictht)源码结构体定义如下：

typedef struct dictht { 
  dictEntry **table; // 哈希表数组 
  unsigned long size; // 哈希表数组的大小 
  unsigned long sizemask; // 用于映射位置的掩码，值永远等于(size-1) 
  unsigned long used; // 哈希表已有节点的数量,包含next单链表数据 
} dictht;

hash表的数组初始容量为4，随着k-v存储量的增加需要对hash表数组进行扩容，新扩容量为当前量的一倍，即4,8,16,32。
索引值=Hash值&掩码值（Hash值与Hash表容量取余）

Hash表节点(dictEntry)源码结构体定义如下：

typedef struct dictEntry { 
  void *key; // 键 
  union { // 值v的类型可以是以下4种类型 
    void *val; 
    uint64_t u64; 
    int64_t s64; 
    double d; 
  } v; 
  struct dictEntry *next; // 指向下一个哈希表节点，形成单向链表 解决hash冲突 
} dictEntry;

# 字典扩容（rehash）

字典达到存储上限（阈值 0.75），需要rehash（扩容）

扩容流程：申请新的内存 -》地址赋给h[1] -》rehashidx=0 -》h[1]=h[0](索引重新计算)

初次申请默认容量为4个dictEntry，非初次申请则为当前hash表容量的一倍。
rehashidx=0表示要进行rehash操作。
新增加的数据在新的hash表h[1]
修改、删除、查询在老hash表h[0]，因为新hash表h[1]中（rehash中）
将老的hash表h[0]的数据重新计算索引值后全部迁移到新的hash表h[1]中，这个过程称为rehash。

# 渐进式rehash

当数据量巨大时rehash的过程是非常缓慢的，所以需要进行优化。

服务器忙，则只对一个节点进行rehash
服务器闲，可批量rehash(100节点)

应用场景：主数据库的K-V数据存储、散列表对象（hash）、哨兵模式中的主从节点管理

# 压缩列表

压缩列表（ziplist）是由一系列特殊编码的连续内存块组成的顺序型数据结构，目的是节省内存。

简单来说就是一个字节数组，可以包含多个节点（entry）。每个节点可以保存一个字节数组或一个整数。数据结构如下：

ziplist源码结构体定义如下：

struct ziplist<T>{ 
  unsigned int zlbytes; // ziplist的长度字节数，包含头部、所有entry和zipend。 
  unsigned int zloffset; // 从ziplist的头指针到指向最后一个entry的偏移量，用于快速反向查询
  unsigned short int zllength; // entry元素个数 
  T[] entry; // 元素值 
  unsigned char zlend; // ziplist结束符，值固定为0xFF 
}

typedef struct zlentry { 
  unsigned int prevrawlensize; // previous_entry_length字段的长度 
  unsigned int prevrawlen; // previous_entry_length字段存储的内容 
  unsigned int lensize; //encoding字段的长度 
  unsigned int len; //数据内容长度 
  unsigned int headersize; // 当前元素的首部长度，即previous_entry_length字段 长度与 encoding字段长度之和。 
  unsigned char encoding; //数据类型 
  unsigned char *p; //当前元素首地址 
} zlentry;

应用场景:

sorted-set和hash元素个数少且是小整数或短字符串，会直接使用ziplist
list用快速链表(quicklist)数据结构存储，而快速链表是双向列表与压缩列表的组合。

# 整数集合

整数集合(intset)是一个有序的（升序）、存储整数的连续存储结构。

当Redis集合类型的元素都是整数并且都处在64位有符号整数范围内（2^64），使用该结构体存储。

127.0.0.1:6379> sadd k1 1 3 5 6 2 
(integer) 5 
127.0.0.1:6379> object encoding k1 
"intset" 
127.0.0.1:6379> sadd k2 1 100000000000000000000000000 9999999999 
(integer) 3 
127.0.0.1:6379> object encoding k2 
"hashtable"

intset源码结构体定义如下：

typedef struct intset{  
  uint32_t encoding; //编码方式
  uint32_t length; //集合包含的元素数量 
  int8_t contents[]; //保存元素的数组 
}intset

应用场景：可以保存类型为int16_t、int32_t 或者int64_t 的整数值，并且保证集合中不会出现重复元素。

# 快速列表-list

快速列表（quicklist）是Redis列表的底层实现。

在Redis3.2之前，Redis采用双向链表adlist和压缩列表ziplist实现。在Redis3.2以后，结合adlist和ziplist的优势Redis设计出了quicklist。

127.0.0.1:6379> lpush k1 1 2 5 4 3 
(integer) 5 
127.0.0.1:6379> object encoding k1 
"quicklist"

# 双向列表（adlist）

双向链表优势：

双向：链表具有前置节点和后置节点的引用，获取这两个节点时间复杂度都为O(1)。
无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL，对链表的访问都是以 NULL 结束。
带链表长度计数器：通过 len 属性获取链表长度的时间复杂度为 O(1)。
多态：链表节点使用 void* 指针来保存节点值，可以保存各种不同类型的值。

# 快速列表（quicklist）

quicklist是本质上是一个双向链表，而链表中的每个节点是一个ziplist结构，ziplist都能够存储多个数据元素。

quicklist源码结构体定义如下：

typedef struct quicklist { 
  quicklistNode *head; // 指向quicklist的头部 
  quicklistNode *tail; // 指向quicklist的尾部 
  unsigned long count; // 列表中所有数据项的个数总和
  unsigned int len; // quicklist节点的个数，即ziplist的个数 
  int fill:16; // ziplist大小限定，由list-max-ziplist-size给定 (Redis设定) 
  unsigned int compress : 16; // 节点压缩深度设置，由list-compress-depth给定 (Redis设定) 
} quicklist;

quicklistNode的源码结构定义如下：

typedef struct quicklistNode { 
  struct quicklistNode *prev; // 指向上一个ziplist节点 
  struct quicklistNode *next; // 指向下一个ziplist节点 
  unsigned char *zl; // 数据指针，如果没有被压缩，就指向ziplist结构，反之 指向 quicklistLZF结构 
  unsigned int sz; // 表示指向ziplist结构的总长度(内存占用长度) 
  unsigned int count : 16; // 表示ziplist中的数据项个数 
  unsigned int encoding : 2; // 编码方式，1--ziplist，2--quicklistLZF 
  unsigned int container : 2; // 预留字段，存放数据的方式，1--NONE，2--ziplist 
  unsigned int recompress : 1; // 解压标记，当查看一个被压缩的数据时，需要暂时解压，标记此参数为 1，之后再重新进行压缩 
  unsigned int attempted_compress : 1; // 测试相关 
  unsigned int extra : 10; // 扩展字段，暂时没用 
} quicklistNode;

# 数据压缩

quicklist每个节点的实际数据存储结构为ziplist，这种结构的优势在于节省存储空间。为了进一步降低ziplist的存储空间，还可以对ziplist进行压缩。

Redis采用的压缩算法是LZF。其基本思想是：数据与前面重复的记录重复位置及长度，不重复的记录原始数据。压缩过后的数据可以分成多个片段，每个片段有两个部分：解释字段和数据字段。

quicklistLZF的源码结构体如下：

typedef struct quicklistLZF { 
  unsigned int sz; // LZF压缩后占用的字节数 
  char compressed[]; // 柔性数组，指向数据部分 
} quicklistLZF;

应用场景：列表(List)的底层实现、发布与订阅、慢查询、监视器等功能。

# 流对象

stream主要由：消息、生产者、消费者和消费组构成。

Redis Stream的底层主要使用了listpack（紧凑列表）和Rax树（基数树）。

# listpack

listpack表示一个字符串列表的序列化，listpack可用于存储字符串或整数。用于存储stream的消息内容。结构如下图：

# Rax树

Rax 是一个有序字典树 (基数树 Radix Tree)，按照 key 的字典序排列，支持快速地定位、插入和删除操作。

Rax 被用在 Redis Stream 结构里面用于存储消息队列，在 Stream 里面消息 ID 的前缀是时间戳 + 序号，这样的消息可以理解为时间序列消息。使用 Rax 结构进行存储就可以快速地根据消息 ID 定位到具体的消息，然后继续遍历指定消息之后的所有消息。

应用场景：stream的底层实现

# RedisObject.encoding详解

Redis通过 encoding 属性为对象设置不同的编码。对于少的和小的数据，Redis采用小的和压缩的存储方式，encoding体现Redis的灵活性，大大提高了 Redis 的存储量和执行效率。下面举例不同数据类型的encoding方式。

# string

string的encoding有 int、raw、embstr。

int：REDIS_ENCODING_INT（int类型的整数）
raw： REDIS_ENCODING_EMBSTR(编码的简单动态字符串)，用于小字符串，长度小于44个字节。
embstr：REDIS_ENCODING_RAW （简单动态字符串），用于大字符串长度大于44个字节

127.0.0.1:6379> set k1 123 
OK
127.0.0.1:6379> object encoding k1 
"int"
127.0.0.1:6379> set k2 zhangsan 
OK
127.0.0.1:6379> object encoding k2 
"embstr"
127.0.0.1:6379> set k3 asdasdasdasdasdasdsadasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdas dasdasdas 
OK
127.0.0.1:6379> object encoding k3 
"raw"

# list

List列表的编码没得选，只能是quicklist，REDIS_ENCODING_QUICKLIST（快速列表）。

127.0.0.1:6379> lpush k1 1 2 5 4 3 
(integer) 5 
127.0.0.1:6379> object encoding k1 
"quicklist"

# hash

Hash散列的编码是字典dict和压缩列表ziplist。

dict（hashtable）：REDIS_ENCODING_HT（字典），当散列表元素的个数比较多或元素不是小整数或短字符串时。
ziplist：REDIS_ENCODING_ZIPLIST（压缩列表），当散列表元素的个数比较少，且元素都是小整数或短字符串时。

127.0.0.1:6379> hmset user:007 username111111111111111111111111111111111111111111111111111111111111111111111111 11111111111111111111111111111111 zhangsan password 111 num 2300000000000000000000000000000000000000000000000000 
OK
127.0.0.1:6379> object encoding user:007 
"hashtable"
127.0.0.1:6379> hmset user:008 username lisi password 111 age 23 sex M 
OK
127.0.0.1:6379> object encoding user:008 
"ziplist"

# set

set集合的编码是整形集合intset和字典dict。

intset：REDIS_ENCODING_INTSET（整数集合），当Redis集合类型的元素都是整数并且都处在64位有符号整数范围内（<18446744073709551616）
dict（hashtable）：REDIS_ENCODING_HT（字典），当Redis集合类型的元素都是整数并且都处在64位有符号整数范围外（>18446744073709551616）

127.0.0.1:6379> sadd k1 1 3 5 6 2 
(integer) 5 
127.0.0.1:6379> object encoding k1 
"intset"
127.0.0.1:6379> sadd k2 1 100000000000000000000000000 9999999999 
(integer) 3 
127.0.0.1:6379> object encoding k2 
"hashtable"

# zset

zset有序集合的编码是压缩列表ziplist和跳跃表skiplist+字典dict。

ziplist：REDIS_ENCODING_ZIPLIST（压缩列表），当元素的个数比较少，且元素都是小整数或短字符串时。
skiplist + dict：REDIS_ENCODING_SKIPLIST（跳跃表+字典），当元素的个数比较多或元素不是小整数或短字符串时。

127.0.0.1:6379> zadd k1 100 item1 20 item2 45 item3 
(integer) 3 
127.0.0.1:6379> object encoding k1 
"ziplist"
127.0.0.1:6379> zadd k2 100 item1111111111111111111111111111111111111111111111111111111111111111111111111111 1111111111111111111111111111111111 20 item2 45 item3 (integer) 3 
127.0.0.1:6379> object encoding k2 
"skiplist"

上次更新: 5/30/2023, 11:42:20 PM

Redis回收策略与缓存过期→