侧边栏壁纸
  • 累计撰写 244 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论
隐藏侧边栏

Redis 常见数据结构的底层实现系列(二):字符串篇

kaixindeken
2021-04-28 / 0 评论 / 0 点赞 / 78 阅读 / 3,119 字

单个 Redis 数据库实例底层是一张巨大的哈希表,所有的 Redis 键值对都是挂载在这张哈希表上的,因此,才能实现 Redis 键值对的高效存取操作,但是和 Memcached 不同,除了简单的字符串格式键值外,Redis 的键值还支持列表、集合、字典等其他丰富的数据结构。

字符串底层是原生字符串吗

首先是字符串类型的键值(数字类型也被包含在字符串类型里面了,我们这里先介绍纯字符串类型的底层实现),你可能会觉得这非常简单啊,字符串本身就是一个基本的数据类型,将哈希表的键值指针指向字符串所在的内存地址不就可以了,那是不是这样呢?

我们知道 Redis 是基于 C 语言实现的,在 C 语言中,本身不支持字符串类型,而是通过字符数组 + \0 结束符作为标识间接实现的。对于数组这种结构,适合随机读取元素,对应的时间复杂度是 O(1),不适合动态插入、删除元素,因为需要对操作元素前后的数组元素进行移动,最差的情况下,需要遍历这个数组,对应的时间复杂度是 O(n),这是标榜高性能的 Redis 所不能承受的,因此 Redis 不支持对字符串内部元素进行动态增删。

不过,我们注意到 Redis 有一个获取字符串长度的 STRLEN 指令,如果按照 C 语言字符串的实现,要获取字符串长度,需要从头到尾遍历字符数组,直到遇到结束符 \0,这样一来对应的时间复杂度也是 O(n),Redis 肯定要避免这样的低效操作;另外,Redis 字符串类型还支持 APPEND 这种动态扩容操作,如果按照 C 原生字符串的实现,对应的时间复杂度也是 O(n),所以到这里,我们基本可以猜到 Redis 的字符串类型底层肯定不是简单的原生字符串实现。

那它是什么样的数据结构呢?

简单动态字符串的底层结构

在 Redis 底层,通过「简单动态字符串」(Simple Dynamic String,简称 SDS)的数据结构来存储字符串类型的键值,它是一个在字符数组的基础上新增数组长度的结构体:

struct SDS<T> {
  T capacity; // 数组容量
  T len; // 数组长度
  byte flags; // 特殊标识位,不理睬它
  byte[] content; // 数组内容
}

这里数组长度和容量的概念和 Go 语言的切片类型差不多:

1.jpeg

在初始化 SDS 时,默认有一个初始容量,而字节数组 content 中实际存放的元素数量就是数组长度,有了数组长度,当调用 STRLEN 指令时,通过哈希表定位到键值位置后,直接返回该字段的值就可以了,时间复杂度仍然是 O(1),扩容实现也非常简单,只需要将字符串指针加上长度作为偏移量,即可定位到数组结束的位置,将追加的元素逐一往后拷贝即可,如果元素数量是 m,则对应的时间复杂度是 O(m),m 通常是常量,时间复杂度也是 O(1)。

如果数组容量 append 值不大的话,势必导致扩容时,需要额外分配内存空间,然后再把原来旧的数据元素拷贝到新分配的内存空间,这样一来,整体的时间复杂度变成了O(n+m),m 即便是常量,时间复杂度也是 O(n),n 越大,扩容带来的成本就越高。

你的担心是对的,Redis 也确实在这方面用心做了设计,这个初始容量不能太小,太小会导致扩容概率变高,牺牲时间复杂度,又不能太大,太大会造成内存空间的冗余和浪费。

为了在时间复杂度和空间复杂度两方面做好平衡,在初始化时,数组容量和长度值是一样的,毕竟不是每个字符串都会扩容,多分配就是浪费,实际上,绝大多数时候都不会对字符串做追加元素的操作。一旦某个字符串要追加元素,需要扩容,在字符串长度小于 1M 的情况下,容量会按照数组长度两倍的尺寸进行扩容,而当数组长度超过 1M 后,每次扩容会将容量值增加 1M,避免浪费非常宝贵的内存空间。

在 Redis 中,字符串长度不是无限增长的,而是有上限的,这个上限值是 512 M。

不同长度字符串和数字类型的编码

为了进一步压榨性能,Redis 底层还在存储不同长度字符串时做了优化,当字符串长度特别短(<= 44)时,使用 embstr 编码形式存储,当字符串长度超过 44 时,使用 raw 编码形式存储,两者底层数据结构一致,之所以做这个区分,是因为前者只需要分配一次内存空间,而后者需要分配两次。

127.0.0.1:6379> set name kaixindeken
OK
127.0.0.1:6379> debug object name
Value at:0x7f867960e600 refcount:1 encoding:embstr serializedlength:10 lru:90436 lru_seconds_idle:2
127.0.0.1:6379> set name kaixindekenkaixindeken
OK
127.0.0.1:6379> strlen name
(integer) 45
127.0.0.1:6379> debug object name
Value at:0x7f86796c4c90 refcount:1 encoding:raw serializedlength:20 lru:91043 lru_seconds_idle:9

对于数字类型,默认的编码格式是 int,因为数字类型的存取效率肯定比字符串高:

127.0.0.1:6379> set num 100
OK
127.0.0.1:6379> debug object num
Value at:0x7f867964d900 refcount:2147483647 encoding:int serializedlength:2 lru:16713972 lru_seconds_idle:153790

只是我们在进行自增和自减操作时,会将其转化为数值进行操作。

浮点类型和整型一样。

另外,当数字类型发生转化后,虽然对应字符串长度小于 44,但是依然会转化为 raw 编码:

127.0.0.1:6379> debug object num
Value at:0x7f86796c4ce0 refcount:1 encoding:raw serializedlength:10 lru:90662 lru_seconds_idle:61

其实 embstr 也是这样:

127.0.0.1:6379> set name kaixindeken
OK
127.0.0.1:6379> append name kaixindekenkaixindeken
(integer) 18
127.0.0.1:6379> strlen name
(integer) 18
127.0.0.1:6379> debug object name
Value at:0x7f86796c4cc0 refcount:1 encoding:raw serializedlength:19 lru:91163 lru_seconds_idle:5

因为 embstr 是只读的,Redis 没有对其编写任何的修改程序,在修改 embstr 对象时,都会先将其转化为 raw 再进行后续修改,所以修改后的编码类型自然是 raw 了,数字类型转化时当然也是这个原因(自增自减不会改变编码类型,除非长度超过 long 整型的最大值)。

0

评论区