Redis 中 string 和 list 的原理说明

Redis 中 string 和 list 的底层实现

Redis有5种基础数据结构，对应的value分别为：string (字符串)、list (列表)、set (集合)、hash (哈希) 和 zset (有序集合)

Redis 对象头结构体：

struct RedisObject {int4 type; // 4bits 对象的基本类型int4 encoding; // 4bits 对象的编码方式int24 lru; // 24bits 对象的最近访问时间（Least Recently Used）int32 refcount; // 4bytes 对象的引用计数void *ptr; // 8bytes，64-bit system 指向对象的实际存储位置
} robj;

string

结构

Redis的字符串是动态字符串，是可以修改的字符串，内部结构实现上类似于Go的slice切片，采用预分配冗余空间的方式来减少内存的频繁分配

• 内部为当前字符串实际分配的空间capacity一般要高于实际字符串长度len
• 当字符串长度小于1M时，扩容加倍；大于1M时，扩容增加1M
• 字符串最大长度为512M

sds

虽然Redis是用c实现的，但是他们的string结构并不相同，Redis中的字符串是可以修改的字符串，在内存中它是以字节数组的形式存在的

Redis 的字符串叫「SDS」，也就是 Simple Dynamic String，是一个带长度信息的字节数组

struct SDS<T> {T capacity; // 数组容量   使用泛型表示T len; // 数组长度      使用泛型表示byte flags; // 特殊标识位.byte[] content; // 数组内容   字节数组
}

T:当字符串比较短时，len和capacity可以使用byte和short来表示，Redis为了对内存做极致的优化，不同长度的字符串使用不同的结构体来表示

编码方式

sds编码

当字符串长度小于或等于 44 字节 时，Redis 使用 embstr 编码（embedded string 嵌入式）

当字符串长度大于 44 字节 时，Redis 使用 raw 编码

整数编码

当存储的值是一个小整数时，Redis 会使用整数编码来存储，这样可以节省内存

list

Redis 的List类型是一个简单的字符串列表，支持从头部或尾部插入和删除元素。它的底层实现方式取决于列表的大小和元素的特性

双向链表（LinkedList）

在Redis3.2之前，当List的元素数量较多或元素较大时，Redis使用双向链表作为底层数据结构

// 节点
typedef struct listNode {struct listNode *prev;	//上一元素struct listNode *next;	//下一元素void *value;	//元素值
} listNode;// 双向链表
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;

压缩链表（ziplist）

当List中的元素数量较少（默认小于512个）且每个元素的大小较小（默认小于 64 字节）时，Redis会使用 ziplist

• zlbytes：4 字节，记录整个 Ziplist 占用的内存字节数
• zltail：4 字节，记录 Ziplist 表尾节点的偏移量
• zllen：2 字节，记录 Ziplist 中的节点数量
• entry：列表节点，每个节点的长度由其内容决定
• zlend：1 字节，标记 Ziplist 的结束（值为 0xFF）

快排列表（quicklist）

结构

在3.2之后，Redis使用Quicklist

Quicklist是由多个压缩列表（ziplist）组成的双向链表，每个压缩列表称为一个节点

// quicklist.htypedef struct quicklistEntry {unsigned char *value; // 存储的值unsigned int sz; // 值得长度long long longval; // 如果是整数，这里存储整数表示unsigned int encoding:4; // 值得编码方式unsigned int attempted_float_conversion:1; // 是否尝试过将值转换为浮点数
} quicklistEntry;typedef struct quicklistNode {struct quicklistNode *prev; // 前一个节点struct quicklistNode *next; // 下一个节点unsigned char *zl; // 指向ziplistunsigned int sz; // ziplist的大小unsigned int count:16; // ziplist中的元素数量unsigned int encoding:4; // 编码类型unsigned int container:4; // 容器类型unsigned int recompress:1; //是否需要重新压缩
} quicklistNode;typedef struct quicklist {quicklistNode *head; // 头节点quicklistNode *tail; // 尾节点const quicklistCompress *compress; // 压缩深度unsigned int count; // 节点数量unsigned long len; // 总元素数量signed int fill : QL_FILL_BITS; // 每个节点的填充因子unsigned int compress : QL_COMP_BITS; // 压缩深度unsigned int bookmark_count: QL_BM_BITS; // 书签数量quicklistBookmark bookmarks[]; // 书签数组
} quicklist;

主要的数据结构包括：

• quicklistEntry：表示 quicklist 中的一个条目（entry）
• quicklistNode：表示 quicklist 中的一个节点，包含一个 ziplist
• quicklist：整个 quicklist 结构，包含头尾节点、统计信息等

工作原理

1. 节点存储：
   • 每个 quicklistNode 包含一个 ziplist，用于紧凑存储多个元素。
   • ziplist 是一种紧凑的内存结构，适合存储小数据项。
2. 动态调整：
   • 当向 Quicklist 中插入数据时，Redis 会根据配置的 list-max-ziplist-size 参数决定是否需要创建新的节点。
   • 如果当前 ziplist 达到大小限制，Redis 会创建一个新的 quicklistNode，并在新节点中创建一个新的 ziplist。
3. 压缩策略：
   • Quicklist 支持对中间节点进行压缩，以节省内存。
   • 压缩深度由 list-compress-depth 参数控制，可以指定两端不压缩的节点数量。
4. 内存管理：
   • Quicklist 通过合理控制 ziplist 的大小，避免大规模连续内存申请。
   • 压缩和解压缩使用 LZF 算法，适合实时应用。