redis内部数据结构
2021-12-18 00:51:00 0 举报AI智能生成
redis内部数据结构
作者其他创作
大纲/内容
简单动态字符串sds
用途
实现字符串对象
Redis 是一个键值对数据库（key-value DB），数据库的值可以是字符串、集合、列表等多种类
型的对象，而数据库的键则总是字符串对象。
对于那些包含字符串值的字符串对象来说，每个字符串对象都包含一个 sds 值。
型的对象，而数据库的键则总是字符串对象。
对于那些包含字符串值的字符串对象来说，每个字符串对象都包含一个 sds 值。
char*类型的替代品
因为 char* 类型的功能单一，抽象层次低，并且不能高效地支持一些 Redis 常用的操作（比
如追加操作和长度计算操作），所以在 Redis 程序内部，绝大部分情况下都会使用 sds 而不是
char* 来表示字符串
如追加操作和长度计算操作），所以在 Redis 程序内部，绝大部分情况下都会使用 sds 而不是
char* 来表示字符串
目前来说，只要记住这样一个事实即可：在 Redis 中，客户端传入服务器的协议内容、aof 缓
存、返回给客户端的回复，等等，这些重要的内容都是由都是由 sds 类型来保存的。
存、返回给客户端的回复，等等，这些重要的内容都是由都是由 sds 类型来保存的。
这种简单的字符串表示在大多数情况下都能满足要求，但是，它并不能高效地支持长度计算和
追加（append）这两种操作：
• 每次计算字符串长度（strlen(s)）的复杂度为 θ(N) 。
4 Chapter 1. 内部数据结构
Redis 设计与实现, 第一版
• 对字符串进行 N 次追加，必定需要对字符串进行 N 次内存重分配（realloc）。
追加（append）这两种操作：
• 每次计算字符串长度（strlen(s)）的复杂度为 θ(N) 。
4 Chapter 1. 内部数据结构
Redis 设计与实现, 第一版
• 对字符串进行 N 次追加，必定需要对字符串进行 N 次内存重分配（realloc）。
sds 的实现
sdshdr
len:buf的长度，可直接返回长度
free：buf剩余可用长度
字符串数据buf
所有处理 sdshdr 的函数，都必须正确地更新
len 和 free 属性，否则就会造成 bug 。
len 和 free 属性，否则就会造成 bug 。
优化追加操作原理
内存预分配优化策略（空间换时间）
首次执行append命令
大于1M
分配所需长度加上 SDS_MAX_PREALLOC (1M)数量的空间
再次执行append命令
预分配空间足够，无须再进行空间分配
新字符串总长度小于1M
为字符串分配 2 倍于所需长度的空间
这种分配策略会浪费内存吗？
预分配空间不会释放，除非键被删除或者重启
因为执行 APPEND 命令的字符串键数量通常并不多，占用内存的体积通常也不大，所以这一
般并不算什么问题。
般并不算什么问题。
如果执行 APPEND 操作的键很多，而字符串的体积又很大的话，那可能就需要修
改 Redis 服务器，让它定时释放一些字符串键的预分配空间，从而更有效地使用内存。
改 Redis 服务器，让它定时释放一些字符串键的预分配空间，从而更有效地使用内存。
双端链表
是列表类型底层实现之一
压缩列表
双端列表内存占比比压缩列表要多，创建列表类型时会优先使用压缩列表
双端链表
在有需要的时候，才从压缩列表实现转换到双端链表实现
应用
事务模块使用双端链表来按顺序保存输入的命令
服务器模块使用双端链表来保存多个客户端
订阅/发送模块使用双端链表来保存订阅模式的多个客户端
事件模块使用双端链表来保存时间事件
实现
字典
应用
实现数据库键空间
Redis 是一个键值对数据库，数据库中的键值对就由字典保存：每个数据库都有一个与之相对
应的字典，这个字典被称之为键空间（key space）。
应的字典，这个字典被称之为键空间（key space）。
用作Hash类型键的其中一种底层实现
字典
压缩列表
因为压缩列表比字典更节省内存，所以程序在创建新 Hash 键时，默认使用压缩列表作为底层
实现
哈希表
跳跃表
跳跃表目前在 Redis 的唯一作用就是作为有序集类型的底层数据结构（之一，另一个构
成有序集的结构是字典）。
成有序集的结构是字典）。
收藏
0 条评论
下一页
