Redis基础数据结构

tags: [Redis, 数据结构, 底层实现]Redis数据结构一、对外数据结构存储数据类型Redis 为开发者提供了五种基本数据结构每种结构都有特定的应用场景。1.1 String字符串描述最基本的数据类型可以存储文本、数字或二进制数据。最大容量为 512MB。底层实现简单动态字符串SDSSimple Dynamic String支持预分配和惰性释放减少内存重分配次数。常用命令SET、GET、INCR、DECR、APPEND应用场景缓存用户信息、会话计数器文章阅读量、点赞数分布式锁1.2 List列表描述有序的字符串列表支持从两端插入和删除。元素可以重复。底层实现Redis 3.2 之前小数据用 ziplist大数据用 linkedlist。Redis 3.2 之后统一使用 quicklistziplist 组成的双向链表。Redis 7.0 之后quicklist 中的 ziplist 被 listpack 替换。常用命令LPUSH、RPUSH、LPOP、RPOP、LRANGE应用场景消息队列最新文章列表记录用户操作日志1.3 Set集合描述无序且唯一的字符串集合。支持交集、并集、差集等集合运算。底层实现小数据用 intset整数集合大数据用 hashtable。常用命令SADD、SREM、SISMEMBER、SINTER、SUNION应用场景标签系统共同好友抽奖去重1.4 Zset有序集合描述有序的字符串集合每个元素关联一个分数score。按分数排序支持按分数范围查询。底层实现小数据用 ziplist/listpack大数据用 skiplist hashtable。Redis 7.0 之后小数据时用 listpack 代替 ziplist。常用命令ZADD、ZREM、ZRANGE、ZREVRANGE、ZSCORE应用场景排行榜延时任务带权重的消息队列1.5 Hash哈希描述键值对集合类似对象属性。支持字段级别的操作。底层实现小数据用 ziplist/listpack大数据用 hashtable。常用命令HSET、HGET、HMSET、HMGET、HGETALL应用场景存储对象用户信息、商品信息购物车二、底层数据结构2.1 简单动态字符串SDS特点O(1) 获取长度保存了字符串长度字段。二进制安全可以存储任意二进制数据包括\0。内存预分配减少内存重分配次数。惰性释放缩短字符串时不立即释放内存留作后续使用。结构structsdshdr{intlen;// 已使用长度intfree;// 未使用长度charbuf[];// 字节数组};2.2 压缩列表ziplist - 已弃用概述早期用于 List、Hash、Zset 的小规模存储。内存紧凑适合存储少量小数据。结构zlbytes4 字节记录整个 ziplist 占用的字节数。zltail4 字节记录最后一个 entry 的偏移量。zllen2 字节记录 entry 数量。entry不定长存储具体数据。zlend1 字节结束标记255。entry 结构prevlen前一个 entry 的长度1 或 5 字节。encoding当前 entry 的类型和长度1、2 或 5 字节。data实际数据。问题级联更新如果某个 entry 长度从小于 254 变为大于等于 254其下一个 entry 的 prevlen 需要从 1 字节扩展为 5 字节。可能引发连锁反应导致多个 entry 需要重新分配内存。2.3 紧凑列表listpack - Redis 7.0 引入概述替代 ziplist解决级联更新问题。设计更简单编码更灵活。结构total-bytes整个 listpack 的字节数。num-elementsentry 数量。entry包含 encoding、data、entry-len。entry-len放在 entry 末尾记录当前 entry 的总长度变长编码。改进去掉了 prevlen 字段改为在 entry 末尾记录自身长度。反向遍历时通过 entry-len 向前移动避免了级联更新。2.4 快速列表quicklist概述Redis 3.2 引入List 的默认底层实现。宏观上是双向链表微观上是 ziplist/listpack 数组。结构typedefstructquicklist{quicklistNode*head;// 头节点quicklistNode*tail;// 尾节点unsignedlongcount;// 所有 ziplist 中 entry 总数unsignedintlen;// quicklist 节点数intfill:16;// 每个节点最大容量由 list-max-ziplist-size 配置unsignedintcompress:16;// 压缩深度由 list-compress-depth 配置}quicklist;节点结构typedefstructquicklistNode{structquicklistNode*prev;structquicklistNode*next;unsignedchar*zl;// 指向 ziplist 或 listpackunsignedintsz;// ziplist/listpack 占用的字节数unsignedintcount:16;// entry 数量unsignedintencoding:2;// 编码方式1-RAW, 2-LZFunsignedintcontainer:2;// 容器类型2-ziplist/listpackunsignedintrecompress:1;// 是否需要重新压缩}quicklistNode;优点平衡了内存使用和操作效率。支持节点压缩节省内存。2.5 跳跃表skiplist概述用于 Zset 的大数据存储。有序数据结构支持平均 O(log N) 的查找、插入、删除。结构多层链表结构底层包含所有元素上层是索引层。每个节点包含元素值member分数score后退指针backward层数组level[]每层包含前进指针和跨度。插入过程随机生成节点层数1-32层数越高概率越低p0.25。从最高层开始查找插入位置。在各层链表中插入节点。优点支持范围查询。比平衡树如红黑树实现简单并发友好。2.6 哈希表hashtable概述用于实现 Set、Hash 以及全局键空间。采用链地址法解决哈希冲突。渐进式 rehashRedis 使用两个哈希表ht[0] 和 ht[1]在扩容时逐步迁移数据。每次对字典的增删改查操作时迁移少量 bucket。避免一次性 rehash 导致的阻塞。三、数据结构选择与配置3.1 配置参数数据类型配置项含义Listlist-max-ziplist-sizequicklist 中每个节点的最大容量Listlist-compress-depth节点压缩深度Hashhash-max-ziplist-entries使用 ziplist/listpack 的最大 entry 数Hashhash-max-ziplist-value使用 ziplist/listpack 时单个 value 的最大字节数Zsetzset-max-ziplist-entries使用 ziplist/listpack 的最大 entry 数Zsetzset-max-ziplist-value使用 ziplist/listpack 时单个 value 的最大字节数Setset-max-intset-entries使用 intset 的最大元素数3.2 性能考虑小数据优化多数数据类型在小数据时使用紧凑结构ziplist/listpack、intset节省内存。大数据切换超过阈值后切换为标准结构hashtable、skiplist、linkedlist保证操作效率。内存 vs 性能根据业务特点调整配置参数平衡内存使用和操作性能。四、总结对外数据结构String、List、Set、Zset、Hash满足不同业务需求。底层实现SDS、ziplist、listpack、quicklist、skiplist、hashtable针对不同场景优化。配置调优通过配置文件参数优化内存使用和性能。版本演进Redis 7.0 用 listpack 替代 ziplist解决级联更新问题。