聊聊Redis数据结构中的String类型

Redis常用作分布式KV缓存，很多人仅仅只会使用，却不知道底层却有着很多不为人知的秘密。【相关推荐：Redis视频教程】

String类型

String作为Redis支持的最基础的数据类型，首先我们来看下String，他的数据结构和存储是怎么样的。

重新定义SDS 去存储String

众所周知，redis是用c语言进行编写的，而c语言是没有String类型的，只有char[]，并且在初始化的是时候就必须大小指定类型后就不能改变。为了实现动态增加和扩展等功能，如incr命令，append命令，所以redis就自己定义维护了一个SDS（Simple Dynamic String）来实现这些功能。

我们先来看一下redis源码中定义的数据结构,这里有5种类型，目的是为了节省空间。

1、len:获取char[]的长度，需要遍历数组，len(char[])时间复杂度O(n)；
2、alloc：c语言没有String类型， 只有char[]，且char[]必须先分配空间长度，char[]预先分配了长度，数据增长后需要扩容；

3、falgs：总是占用一个字节。其中的最低3个bit用来表示header的类型。header的类型共有5种，在sds.h中有常量定义。
4、buf[]：c语言的char数组，用'\0'代表结束，意味着存储二进制数据不能包含'\0'，图片音频等用二进制存储会有问题——这就是为什么Redis说自己实现的SDS是二进制安全的字符串。

SDS对c原始char数组的改进

1、Redis实现的SDS支持扩容
2、包含长度len，获取长度复杂度O(1)
3、空间预分配
4、惰性空间释放（下面会讲）

SDS的优缺点

优点

• 能够支持扩容
• 包含长度len，获取长度复杂度O(1)
• 空间预分配

缺点

• 需要分配额外的内存
• 频繁的分配和回收带来的效率问题

Redis 使用的内存分配库 jemalloc

jemalloc 在分配内存时，会根据我们申请的字节数 N，找一个比 N 大，但是最接近 N 的 2 的幂次数作为分配的空间，这样可以减少频繁分配的次数。举个例子。如果你申请 6 字节空间，jemalloc 实际会分配 8 字节空间；如果你申请 24 字节空间，jemalloc 则会分配 32 字节。所以，在我们刚刚说的场景里，dictEntry 结构就占用了 32 字节。

空间预分配

空间预分配用于优化 SDS 的字符串增长操作： 当 SDS 的 API 对一个 SDS 进行修改， 并且需要对 SDS 进行空间扩展的时候， 程序不仅会为 SDS 分配修改所必须要的空间， 还会为 SDS 分配额外的未使用空间。

其中， 额外分配的未使用空间数量由以下公式决定：

• 如果对 SDS 进行修改之后， SDS 的长度（也即是 len 属性的值）将小于 1 MB ， 那么程序分配和 len 属性同样大小的未使用空间， 这时 SDS len 属性的值将和 free 属性的值相同。 举个例子， 如果进行修改之后， SDS 的 len 将变成 13 字节， 那么程序也会分配13 字节的未使用空间， SDS 的 buf 数组的实际长度将变成 13 + 13 + 1 = 27 字节（额外的一字节用于保存空字符）。
• 如果对 SDS 进行修改之后， SDS 的长度将大于等于 1 MB ， 那么程序会分配 1 MB 的未使用空间。 举个例子， 如果进行修改之后， SDS 的 len 将变成 30 MB ， 那么程序会分配 1 MB 的未使用空间， SDS 的 buf 数组的实际长度将为 30 MB + 1 MB + 1 byte 。

通过空间预分配策略， Redis 可以减少连续执行字符串增长操作所需的内存重分配次数。

惰性释放

惰性空间释放用于优化 SDS 的字符串缩短操作： 当 SDS 的 API 需要缩短 SDS 保存的字符串时， 程序并不立即使用内存重分配来回收缩短后多出来的字节， 而是使用 free 属性将这些字节的数量记录起来， 并等待将来使用。

Redis的KV存储结构

在redis中，所有的存储都是以KV键值对的形式存储的，K是字符串类型，就是SDS；V 可能是字符串、list、hash等(Redis支持的数据结构)，V并没有直接定成具体的类型，而是用redisObject封装了一层；实际存储的数据结构是由ptr指针具体指向。

并且，redis为了更好的节省空间，ptr指针也有不同方式的存储，一方面，当保存的是 Long 类型整数时，RedisObject 中的指针就直接赋值为整数数据了，这样就不用额外的指针再指向整数了，节省了指针的空间开销。另一方面，当保存的是字符串数据，并且字符串小于等于 44 字节时，RedisObject 中的元数据、指针和 SDS 是一块连续的内存区域，这样就可以避免内存碎片。这种布局方式也被称为 embstr 编码方式。当然，当字符串大于 44 字节时，SDS 的数据量就开始变多了，Redis 就不再把 SDS 和 RedisObject 布局在一起了，而是会给 SDS 分配独立的空间，并用指针指向 SDS 结构。这种布局方式被称为 raw 编码模式。如图所示

• embstr 编码
  存储简短字符串，一次的内存分配；
  它是只读的，如果对内容进行修改，就会变成raw编码(即使没超过44字节)；
• raw 编码
  可分配多次内存空间，存储大于44个字节的长字符串。

raw 原生SDS 字符长度 缩减到小于44，会逆向变成embstr编码吗？
不会；Redis底层编码，转变后 不可逆(不会回退)。

总结

redis是常用的缓存中间件，我们必须了解清楚他的数据结构和存储，以便以使用的时候的选择更加合适的数据结构和内存的预估。

redis内存计算地址 http://www.redis.cn/redis_memory/

更多编程相关知识，请访问：编程入门！！

以上就是聊聊Redis数据结构中的String类型的详细内容，转载自php中文网