类型 | 编码方式 | 数据结构 |
---|---|---|
string | raw | 动态字符串编码 |
embstr | 优化内存分配的字符串编码 | |
int | 整数编码 | |
hash | hashtable | 散列表编码 |
ziplist | 压缩列表编码 | |
list | linkedlist | 双向链表编码 |
ziplist | 压缩列表编码 | |
quicklist | 3.2版本新的列表编码 | |
set | hashtable | 散列表编码 |
intset | 整数集合编码 | |
zset | skiplist | 跳跃表编码 |
ziplist | 压缩列表编码 |
字符串结构
Redis没有采用原生C语言的字符串类型,而是自己实现了字符串结构,内部简单动态字符串(simple dynamic string,SDS)。特点如下:
- O(1)时间复杂度获取字符串长度、已用长度、未用长度
- 可用于保存字节数组,支持安全的二进制数据存储
- 内部实现空间预分配机制,降低内存内存再分配次数
- 惰性删除机制,字符串缩减后的空间不释放,作为预分配空间保留
对于string,
- int:8个字节的长整型
- embstr:小于等于39个字节的字符串
- raw:大于39个字节的字符串,即用简单动态字符串(SDS)存储
embstr 编码的优化之处在于将创建字符串对象所需的内存分配次数从 raw 编码的两次降低为一次,mbstr 编码的字符串对象的所有数据都保存在一块连续的内存里面,redisObject 结构(type, encoding…)和 sdshdr 结构(free, len, buf)都放在一起
embstr 编码的字符串对象实际上是只读的: 当我们对 embstr 编码的字符串对象执行任何修改命令时, 程序会先将对象的编码从 embstr 转换成 raw , 然后再执行修改命令; 因为这个原因, embstr 编码的字符串对象在执行修改命令之后, 总会变成一个 raw 编码的字符串对象。
ziplist 压缩列表
hash、list、zset中,如果所有值小于hash_max_ziplist_value (默认值为 64 ),且元素个数小于 hash_max_ziplist_entries (默认值为 512 )时使用ziplist编码。
ziplist编码的主要目的是为了节约内存,因此所有数据都是采用线性连续的内存结构。结构字段含义:
- zlbytes:整个压缩列表所占字节长度。int-32,长度4字节。
- zltail:距离尾节点的偏移量。int-32,长度4字节。
- zllen:int-16,长度2字节。
- entry:具体的节点:
- prev_entry_bytes_length:记录前一个节点所占空间
- encoding:标示当前节点编码和长度
- contents:保存节点的值
- zlend:记录列表结尾,占一个字节
从上可以看出存在双向链表结构,以O(1)时间复杂度入队和出队。而新增删除操作涉及内存重新分配和释放。
hashtable
Redis 使用的hash算法是 MurmurHash2 ,解决冲突的方式是链地址法。程序总是将新节点添加到链表的表头位置(复杂度为 O(1)), 排在其他已有节点的前面。按2的幂rehash。
linkedlist
- 双端: langfei链表节点带有 prev 和 next 指针, 获取某个节点的前置节点和后置节点的复杂度都是 O(1) 。
- 无环: 表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL , 对链表的访问以 NULL 为终点。
- 带表头指针和表尾指针: 通过 list 结构的 head 指针和 tail 指针, 程序获取链表的表头节点和表尾节点的复杂度为 O(1) 。
- 带链表长度计数器: 程序使用 list 结构的 len 属性来对 list 持有的链表节点进行计数, 程序获取链表中节点数量的复杂度为 O(1) 。
- 多态: 链表节点使用 void* 指针来保存节点值, 并且可以通过 list 结构的 dup 、 free 、 match 三个属性为节点值设置类型特定函数, 所以链表可以用于保存各种不同类型的值。
intset
存储有序、不重复的整数集。集合只包含整数且长度不超过set-max-intset-entries
intset对写入整数进行排序,通过O(lgn)时间复杂度实现查找和去重操作。字段含义:
- encoding:整数表示类型,根据集合内最长整数值确定类型,整数类型划分为int-16,int-32,int-64
- length:表示集合元素个数
- contents:整数数组,按从小到达顺序排列
尽量保证整数范围一致,防止个别大整数触发集合升级操作,产生内存浪费。
skiplist
过在每个节点中维持多个指向其他节点的指针, 从而达到快速访问节点的目的。跳跃表支持平均 O(log N) 最坏 O(N) 复杂度的节点查找, 还可以通过顺序性操作来批量处理节点。
Object
Redis 中的每个对象都由一个 redisObject 结构表示, 该结构中和保存数据有关的三个属性分别是 type 属性、 encoding 属性和 ptr 属性。对象的 type 属性记录了对象的类型。对象的 ptr 指针指向对象的底层实现数据结构, 而这些数据结构由对象的 encoding 属性决定。
因为 C 语言并不具备自动的内存回收功能, 所以 Redis 在自己的对象系统中构建了一个引用计数(reference counting)技术实现的内存回收机制, 通过这一机制, 程序可以通过跟踪对象的引用计数信息, 在适当的时候自动释放对象并进行内存回收。由redisObject 结构的 refcount 属性记录:
- 在创建一个新对象时, 引用计数的值会被初始化为 1 ;
- 当对象被一个新程序使用时, 它的引用计数值会被增一;
- 当对象不再被一个程序使用时, 它的引用计数值会被减一;
- 当对象的引用计数值变为 0 时, 对象所占用的内存会被释放。
redisObject 结构包含的最后一个属性为 lru 属性, 该属性记录了对象最后一次被命令程序访问的时间。OBJECT IDLETIME 命令可以打印出给定键的空转时长, 这一空转时长就是通过将当前时间减去键的值对象的 lru 时间计算得出的。