大话Redis系列--数据结构系列之String类型

在Redis的底层当中，String通常会是大家使用频率相对较高的一个类型，这一类型的数据结构在使用的时候也非常简单，例如下边这段操作指令：

>set test-key value1
OK

但是大家又是否有深入了解过String类型的key在Redis底层中又是如何存储的呢？

下边我们来进入一段实战演练环节，查看下字符串类型的数据结构在Redis当中的存储细节：

SDS源代码部分探索

如果对Redis的String类型参数有一定了解的朋友，应该都知道Redis底层在存储字符串类型数据的时候会使用一个叫做sds的数据结构。我大概地将其整理了一下，核心字段为以下部分：（这是早期的Redis版本）

typedef char *sds; // SDS 字符串指针，指向 sdshdr.buf

    struct sdshdr { 
        int  len;          // 已用空间长度
        int  free;        // 剩余空间
        char buf[];           // 字符数组，保存以'\0'结尾的字符串，与传统 C 语言中的字符串的表达方式保持一致
    };

场景分析：

假设我们要存储一个叫做idea的字符串，那么此时会分配8字节的空间，然后len为4，free也为4，buf中存储的是idea这四个字符的数据。同时buf的末尾会有一个\0的结束符，这是c语言的一个特性。

另外在扩容的时候会调用一个叫做addlen的函数，用两倍的大小空间给字符串扩容。也就是：

如果idea字符串变成了ideaidea2,那么此时buf数组需要从8扩容为16，同时len字段和free字段会分别变成：8和8.

随着Redis版本的升高，sds的源代码也做了调整，将free字段换成了allot字段

allot字段表示实际分配的空间大小，也就是原先的free+len的数值。

ps：这一部分的设计有点让我联想到了JDK里面的ArrayList数据结构的原理。

原理探索

往redis中写入一个数字，然后自增。

接下来通过type命令可以查看这个数据在redis中的存储类型，

通过object encoding命令可以查看到对应的编码格式：

> set test-str 1
OK
> get test-str
1
> incr test-str
2

ps：

object encoding 【key】该指令可以专门用于查看一个key的编码格式

type 【key】查看某个key对应的value底层存储的数据结构

> type test-str
string
> object encoding test-str
int

接下来我们再来看看这么一组操作：

> set test-str-2 str-value
OK
> type test-str-2 str-value
string
> object encoding test-str-2
embstr

从上边的两段执行指令结果中可以看出，当写入的数据是一个数字的时候（例如1），此时底层的编码格式是int类型，但是当写入的数据是一个字符串的时候，返回的编码格式却是embstr类型。

所以这里面便需要大家伙们一起去理解一个叫做RedisObject的概念。

RedisObject

在Redis内部还会有一个叫做RedisObject的对象用于记录一些额外的信息，例如说访问次数，访问时间等信息。RedisObject内部主要有两个部分组成，一个是元数据，另外一个是实际数据存储的指针。

从Redis6.0底层的源代码入手，我们可以对它有更加深入的理解：

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;

接下来我来逐个解释下这个数据结构中的每个字段所代表的含义分别是什么：

type（4个bit位）

其实type很好理解，我们在输入type命令的时候就是专门查看对应key的RedisObject中存储的type字段所对应的值，例如string,list,hash,set,zset,stream这几种类型。

encoding （4个bit位）

encoding命令则是用于专门查看对应key在底层存储的编码格式了。常见的集中供暖encoding类型其实在redis的源代码中已经有一一罗列了：

具体位置：server.h文件内部

/* Objects encoding. Some kind of objects like Strings and Hashes can be
 * internally represented in multiple ways. The 'encoding' field of the object
 * is set to one of this fields for this object. */
#define OBJ_ENCODING_RAW 0     /* Raw representation */
#define OBJ_ENCODING_INT 1     /* Encoded as integer */
#define OBJ_ENCODING_HT 2      /* Encoded as hash table */
#define OBJ_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
#define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. */
#define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define OBJ_ENCODING_INTSET 6  /* Encoded as intset */
#define OBJ_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
#define OBJ_ENCODING_EMBSTR 8  /* Embedded sds string encoding */
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of ziplists */
#define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */

lru （24个bit位）

lru属性是用于记录了该对象最近的一次访问时间，当我们在配置redis的最大内存参数之后，一旦当redis的使用内存达到上限之后，该lru属性就会用于辅助删除数据使用。

refcount （4个字节）

refcount 记录了当前对象被引用的次数，当 refcount =0时，表示可以安全回收当前对象。（redis的引用技术法实现关键）

当配置有 maxmemory 时，存在共享对象池，[0-1000] 范围内的数值存在共享对象，这些共享对象被引用的次数越多相应的 refcount 越大。

*ptr（8byte）

ptr 就是真实存储数据的指针。指向真实数据。

所以其实整体分析下来，RedisObject的元数据部分占用了8byte大小，指针部分也占用了8byte的大小。

不同编码格式的String底层是如何存储的

Int类型的编码格式

当存入redis中的value是一个数字的时候，其编码格式是int类型，此时底层的存储大致如上图所示。RedisObject中的元数据占用了8个字节的空间，另外还有8个字节的空间原本是用于存放指针的，但是此时却改为了存放对应的具体数字信息。

Embstr类型的编码格式

当存入redis的value是字符串类型的时候，则需要根据实际存储的字符串体积来进行区分，当字符串的大小小于44字节的时候，RedisObject中的指针部分会直接指向对应的sds结构体部分，并且元数据，指针，sds三者所处的内存空间是一个连续的内存空间。

为什么要设计成连续的内存空间呢？

这里就涉及到了之前我在写操作系统相关文章中所提及的缓存行问题了。

[root@izwz9ic9ggky8kub9x1ptuz ~]#  cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size 
64

linux操作系统中的缓存行大小通常默认就是64字节，那么假设当sds的空间大小为44byte以内的时候，sds+元空间+指针大小是小于一个cache_line大小的，将数据体积尽可能地控制在了一个缓存行大小内能够有效地提高计算机的计算效率。

Raw类型的编码格式

当sds的体积大小超过了44byte之后，则RedisObject和Sds两个模块就分别存储在不连续的内存空间中了，此时RedisObject内部的指针依然是存在的，并且会指向对应的sds地址空间。

预估内存大小

这个功能相信在工作中会经常要求使用到，因此在使用到的时候我们可以借助这款工具来进行预估计算：

http://www.redis.cn/redis_memory/

其实通过对Redis当中String存储的原理进行深入剖析之后，可以很明显的发现String结构在内存开销部分是比较大的，那么Redis是否有提供什么内存开销较小的数据结构呢？这部分我将在下一篇文章中为大家介绍。