前言

本文为 Redis 系列第二篇文章，开启 Redis 数据结构相关知识点内容的总结。

Redis 提供了丰富的数据类型:

• 五种基础类型：String（字符串），Hash（哈希），List（列表），Set（集合）、Zset（有序集合）；
• 四种特殊类型： BitMap、HyperLogLog、GEO、Stream。

以上这些是 Redis 键值对中值的数据类型，也就是数据的保存形式，而非底层数据结构。

数据类型的底层实现方式才是数据结构，Redis 之所以高效，有一部分原因也是源于其高效的数据结构，因此研究底层数据结构是非常有意义的，Redis 中数据结构有：SDS、链表、压缩列表、哈希表、整数集合、跳表、quicklist、listpack。

由于 Redis 数据结构比较多，该知识点将分为多篇文章进行讲解，该系列主要内容如下：

该系列文章将以数据类型对照底层数据结构的方式进行分组讲解，本节重点内容如下：

• Redis 的对象机制
• Redis 的字符串类型和其编码实现

喜欢本系列文章的小伙伴欢迎收藏、点赞、加关注哦！ Redis 系列文章：

1.对象机制

学习 Redis 数据结构，第一步需要理解 Redis 的对象机制。

Redis 对象机制是 Redis 内部数据结构的抽象封装，它将不同类型的数据（如字符串、列表、集合、有序集合和哈希表）都封装成对象 （底层实现：redisObject）。

该图展示了 redisObject 对象、数据类型、编码类型以及底层数据结构的关系。

Redis 的每种数据类型对外的封装都是对象结构（redisObject），方便了逻辑的统一实现和处理；每种数据类型又对应若干编码类型，不同的编码类型又对应了更加底层的数据结构，以多种编码类型来灵活处理不同的元素内容，从而实现高效的内存管理和性能优化（这是本系列要讲的重点内容，后续会详细介绍）。这一节我们就简单的来聊一聊什么是 Redis 的对象机制。

1.1 redisObject 对象

redisObject，也称为 robj，是 Redis 中用于表示各种数据类型的通用对象结构。它是 Redis 内部数据结构的核心，用于表示字符串、列表、集合、有序集合和哈希表等数据类型。Redis 的每种数据类型都可以由 redisObject 对象结构统一抽象表示，redisObject 数据结构如下：

typedef struct redisObject {
    // 类型
    unsigned type:4;
    // 编码方式
    unsigned encoding:4;
    // LRU - 24位, 记录最后一次访问时间
    unsigned lru:LRU_BITS; // LRU_BITS: 24
    // 引用计数
    int refcount;
    // 指向底层数据结构实例
    void *ptr;
} robj;

redisObject 是 Redis 中用于表示各种数据类型的通用对象结构。它通过 type 字段表示对象类型，通过 encoding 字段表示对象的编码方式，通过 lru 字段管理对象的淘汰策略，通过 refcount 字段管理对象的生命周期，通过 ptr 字段指向对象的数据内容。

• type：对象的数据类型（4位），表示对象是字符串、列表、集合、有序集合或哈希类型。
• encoding：对象的编码类型（4位），表示对象的内部编码方式。对象编码的目的是为了提高内存利用率和操作效率。Redis 使用了多种编码方式来存储不同类型的数据对象，每种对象类型都有其特定的编码方式，通过使用多种编码方式，能够在内存利用率和操作效率之间取得良好的平衡，从而提供高性能的数据存储服务。
• lru：用于实现 LRU 缓存策略（24位），记录对象的最后一次访问时间。
• refcount：引用计数，用于垃圾回收，记录对象被引用的次数，当引用计数为 0 时，表示对象不再被使用，可以释放其内存。
• ptr：指针 - 指向实际保存值的数据结构，该数据结构由 type + encoding 共同决定其底层实现方式。

1.2 为什么要设计 redisObject

Redis 设计 redisObject 对象有多种原因，主要集中在内存管理、性能优化和数据类型的灵活性等方面。

1. 内存管理 - Redis 是一个内存数据库，内存管理是其核心任务之一。redisObject 通过以下方式优化内存管理：
   • 引用计数：redisObject 通过引用计数来管理对象的生命周期。当对象的引用计数降为 0 时，Redis 会自动释放该对象占用的内存。
   • 共享对象：对于常用的小整数值和短字符串，Redis 会共享这些对象，避免重复创建，从而节省内存。
   • 惰性删除：通过引用计数和 LRU（Least Recently Used）机制，Redis 能够自动回收不再使用的对象，减少内存浪费。
2. 性能优化 - Redis 的高性能部分依赖于 redisObject 的设计：
   • 编码优化：redisObject 支持多种编码方式（如整数编码、压缩列表、哈希表等），根据数据的不同特点选择最合适的编码方式，从而提高操作效率。
   • 惰性编码转换：在需要时才转换对象的编码方式，避免不必要的开销。例如，一个字符串对象可以在整数编码和普通字符串编码之间转换。
   • 快速访问：通过引用计数和 LRU 机制，Redis 能够快速定位和访问最近使用的对象，从而提升性能。
3. 数据类型的灵活性 - Redis 支持多种数据类型（如字符串、列表、集合、有序集合和哈希表），redisObject 通过统一的结构体封装不同类型的数据，使得 Redis 能够灵活地处理各种数据类型：
   • 类型字段（type）：表示对象的类型（字符串、列表、集合、有序集合或哈希）。
   • 编码字段（encoding）：表示对象的内部表示方式（如整数编码、压缩列表、哈希表等）。
   • 指针字段（ptr）：指向实际的数据结构（如字符串、链表等）。
4. 统一接口，提高代码可维护性 - redisObject 使得 Redis 能够通过统一的接口处理不同类型的数据对象，简化了代码实现。例如，所有类型的对象都有引用计数属性，可以使用统一的方式管理这些对象的引用计数，源码如下：

// 增加对象的引用计数
void incrRefCount(robj *o) {
    if (o->refcount != OBJ_SHARED_REFCOUNT) {
        o->refcount++;
    }
}

// 减少对象的引用计数
void decrRefCount(robj *o) {
    if (o->refcount == 1) {
        freeObject(o);
    } else if (o->refcount != OBJ_SHARED_REFCOUNT) {
        o->refcount--;
    }
}

// 释放对象内存
void freeObject(robj *o) {
    switch (o->type) {
        case OBJ_STRING: freeStringObject(o); break;
        case OBJ_LIST: freeListObject(o); break;
        case OBJ_SET: freeSetObject(o); break;
        case OBJ_ZSET: freeZsetObject(o); break;
        case OBJ_HASH: freeHashObject(o); break;
        default: serverPanic("Unknown object type");
    }
    zfree(o);
}

2. String 与 SDS

String 类型的底层的数据结构实现主要是 long 和 SDS（简单动态字符串），本节就详细讲述一下 String 类型以及其底层实现。

2.1 String 字符串

String 是 redis 中最基本的数据类型，一个 key 对应一个 value。 String 可以是字符串、整数或浮点数，支持对整个字符串或字符串的一部分进行操作；对整数或浮点数进行自增或自减操作；可以存储最大 512 MB 的数据。

Redis 中 String 类型是二进制安全的，意思就是 String 可以包含任何数据，而不局限于纯文本数据。具体来说，二进制安全性指的是：

1. 任意数据类型：Redis 中 String 类型可以存储任何数据类型，包括数字、文本、图像、音频、视频和其他任何二进制数据，而且这些数据在存储和传输过程中不会被修改。
2. 不进行编码转换：Redis 不会对 String 类型的数据进行任何编码转换或解析，这保证了数据的完整性。

常用命令查询平台：www.redis.net.cn/order/

应用场景：

Redis 的 String 类型是最基本的数据类型，由于其灵活性和高效性，String 类型在许多应用场景中得到了广泛应用。以下是一些常见的应用场景：

1. 缓存：在 Web 应用、API 服务等场景中，Redis 常用作缓存层，用于存储一些计算开销较大的数据或频繁访问的数据。
2. 会话管理：在 Web 应用中，可以使用 Redis 的 String 类型来存储用户的会话信息，支持快速访问和过期管理。
3. 计数：因为 Redis 处理命令是单线程，所以执行命令的过程是原子的；而且 String 类型支持自增和自减操作，因此可以用来实现计数器功能，这在统计访问量、点赞数等场景中非常有用。
4. 分布式锁：在分布式场景下 Redis 处理命令也是单线程的，而且 SET 命令有个 NX 参数可以实现「key不存在才插入」，用它来实现分布式锁是十分方便的。（当然使用 Redis 实现分布式锁会存在一些问题，后边可以详细聊一下）

2.2 编码类型

Redis 中的字符串数据结构可以被编码为多种形式：

• raw：字符串对象默认为 raw 格式编码，使用一个简单动态字符串（SDS）来保存这个字符串；
• int：整数编码。当字符串表示一个整数值时，Redis 会尝试使用整数编码来优化内存使用和操作效率；Redis 会检测这个字符串是否可以被解析为整数。如果可以，并且整数值在 64 位有符号整数范围内，Redis 会使用整数编码来存储这个值，保存为 long 类型。
• embstr：如果字符串长度小于等于 OBJ_ENCODING_EMBSTR_SIZE_LIMIT（通常为 44 字节），尝试进行 EMBSTR 编码。

String 类型的底层的数据结构实现主要是 long 和 SDS（简单动态字符串）。

为了更清晰的解释 Redis 对于 String 类型编码优化的处理，用源码了解一下：

1. 首先创建字符串对象 - 当你使用 SET 命令存储一个字符串值时，会调用 createStringObject 函数创建字符串对象，默认编码 OBJ_ENCODING_RAW：

robj *createStringObject(const char *ptr, size_t len) {
    return createObject(OBJ_STRING, sdsnewlen(ptr, len));
}

robj *createObject(int type, void *ptr) {
    robj *o = zmalloc(sizeof(*o));
    o->type = type;
    o->encoding = OBJ_ENCODING_RAW; // 默认编码为 RAW
    o->ptr = ptr;
    o->refcount = 1;
    o->lru = LRU_CLOCK();
    return o;
}

1. 尝试优化编码 - 创建字符串对象后，会调用 tryObjectEncoding 函数，尝试对对象进行编码优化：

robj *tryObjectEncoding(robj *o) {
    long value;
    sds s = o->ptr;
    size_t len;

    // 仅尝试对字符串对象进行编码
    if (!sdsEncodedObject(o)) return o;

    // 确保对象是 RAW 编码
    if (o->encoding != OBJ_ENCODING_RAW) return o;

    // 如果字符串太长，跳过编码尝试
    len = sdslen(s);
    if (len > 21) return o;

    // 尝试整数编码
    if (string2l(s, len, &value)) {
        // 如果整数值在共享整数范围内，使用共享整数对象
        if (value >= 0 && value < OBJ_SHARED_INTEGERS) {
            decrRefCount(o);
            incrRefCount(shared.integers[value]);
            return shared.integers[value];
        } else {
            if (o->refcount == 1) {
                o->encoding = OBJ_ENCODING_INT;
                o->ptr = (void*) value;
                return o;
            } else {
                decrRefCount(o);
                return createStringObjectFromLongLong(value);
            }
        }
    }

    // 尝试 EMBSTR 编码
    if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT) {
        robj *emb;

        if (o->refcount > 1) {
            decrRefCount(o);
            return createEmbeddedStringObject(s, sdslen(s));
        }

        emb = createEmbeddedStringObject(s, sdslen(s));
        zfree(o);
        return emb;
    }

    // 如果没有进行编码转换，返回原始对象
    return o;
}

简单解析一下关键代码：

尝试整数编码：

• string2l 函数尝试将字符串转换为整数。
• 如果转换成功，检查整数值是否在共享整数范围内（0 到 OBJ_SHARED_INTEGERS）。
• 如果值在共享整数范围内：减少原对象的引用计数；增加共享整数对象的引用计数；返回共享整数对象。
• 如果值不在共享整数范围内：如果对象的引用计数为 1，直接修改对象的编码为 OBJ_ENCODING_INT，并将指针设置为整数值；否则，减少原对象的引用计数，并创建一个新的整数字符串对象返回。

OBJ_SHARED_INTEGERS 是 Redis 内部的一种优化机制，通过预先创建和共享常见的整数对象，减少内存使用和提高性能。在处理整数值时，Redis 会优先检查是否可以使用共享对象，从而避免重复创建相同的对象。

尝试 EMBSTR 编码：

• 如果字符串长度小于等于 OBJ_ENCODING_EMBSTR_SIZE_LIMIT（通常为 44 字节），尝试进行 EMBSTR 编码。
• 如果对象的引用计数大于 1，减少原对象的引用计数，并创建一个新的嵌入式字符串对象返回。
• 否则，创建一个新的嵌入式字符串对象，释放原对象的内存，返回新的嵌入式字符串对象。

OBJ_ENCODING_EMBSTR_SIZE_LIMIT 是 Redis 中用来定义 EMBSTR 编码的字符串对象的最大长度。EMBSTR（Embedded String）编码是一种优化，用于存储短字符串。它将字符串对象和字符串数据存储在连续的内存块中，以减少内存碎片和内存分配开销。

1. 创建一个新的整数字符串对象

robj *createStringObjectFromLongLong(long long value) {
    robj *o;

    if (value >= 0 && value < OBJ_SHARED_INTEGERS) {
        incrRefCount(shared.integers[value]);
        o = shared.integers[value];
    } else {
        if (value >= LONG_MIN && value <= LONG_MAX) {
            o = createObject(OBJ_STRING, NULL);
            o->encoding = OBJ_ENCODING_INT;
            o->ptr = (void*)((long)value);
        } else {
            o = createObject(OBJ_STRING, sdsfromlonglong(value));
        }
    }
    return o;
}

如果一个字符串对象保存的是整数值，并且这个整数值可以用 long 类型来表示，那么字符串对象会直接将整数值保存在字符串对象结构的 ptr 属性里面（(void*)((long)value) 直接存储 Long 值），并将字符串对象的编码设置为 OBJ_ENCODING_INT。

1. 创建一个嵌入式字符串对象（EMBSTR 编码），用于存储较短的字符串

robj *createEmbeddedStringObject(const char *ptr, size_t len) {
    robj *o = zmalloc(sizeof(robj) + len + 1);
    o->type = OBJ_STRING;
    o->encoding = OBJ_ENCODING_EMBSTR;
    o->ptr = ((char*)o) + sizeof(robj);
    o->refcount = 1;
    o->lru = LRU_CLOCK();
    if (ptr) {
        memcpy(o->ptr, ptr, len);
        ((char*)o->ptr)[len] = '\0';
    } else {
        memset(o->ptr, 0, len + 1);
    }
    return o;
}

createEmbeddedStringObject 函数在 Redis 中用于创建嵌入式字符串对象，这种对象将字符串数据和对象头信息存储在一起，以减少内存碎片和提高访问效率。

• 分配内存：大小为sizeof(robj) + len + 1 字节，sizeof(robj) 表示对象的大小，len + 1 表示字符串数据的大小，加上一个用于存储字符串终止符 \0 的字节。
• 将字符串对象的编码设置为 OBJ_ENCODING_EMBSTR。
• 将对象的 ptr 指针指向分配内存中的字符串数据部分，即 ((char*)o) + sizeof(robj) 处。
• 拷贝字符串数据：如果传入的字符串指针 ptr 不为空，使用 memcpy 函数将字符串数据拷贝到对象的 ptr 指针所指向的内存区域，并在字符串末尾添加终止符 \0。如果传入的字符串指针 ptr 为空，使用 memset 函数将字符串数据部分全部初始化为 0。

嵌入式字符串对象适用于存储较短的字符串，能够显著提升 Redis 的性能和内存利用率。嵌入式字符串对象将对象头和字符串数据存储在一块连续的内存中。这种设计有以下几个优点：

1. 减少内存碎片：通过将对象头和字符串数据存储在一块连续的内存中，减少了内存碎片。
2. 提高访问效率：由于对象头和字符串数据在内存中是连续存储的，访问时只需要一次内存访问，效率更高。
3. 内存分配效率：对于短字符串，使用嵌入式字符串对象可以减少内存分配和释放的开销。

OBJ_ENCODING_EMBSTR_SIZE_LIMIT 通常为 44 字节的原因：

1. 内存对齐和缓存行效率：大多数现代 CPU 的缓存行大小为 64 字节。为了提高缓存命中率和内存访问效率，Redis 选择使嵌入式字符串对象尽可能地接近 64 字节，但不超过这个限制。
2. 对象头的大小：在 64 位系统上，robj 对象头的大小为 16 字节。因此，字符串数据部分的大小为 64 - 16 = 48 字节。然而，为了保证字符串数据部分有一个终止符 \0，实际可用的字符串长度为 48 - 4 = 44 字节。
3. 性能权衡：选择 44 字节作为限制，是在内存利用率和性能之间的一个平衡点。对于大多数应用场景，44 字节的限制能够涵盖绝大多数短字符串。

所以使用 Redis 存储字符串，想要提升性能，最好把 value 控制在 44 字节内。

2.3 SDS 简单动态字符串

Redis 是用 C 语言编写的，但对于 Redis 的字符串类型，却不是 C 语言中的字符串（以空字符 '\0' 结尾的字符数组），而是自己构建的、一种名为简单动态字符串（simple dynamic string）的抽象类型，并将 SDS 作为 Redis 的默认字符串表示。

SDS 结构定义 在 Redis 6.0 中，SDS（Simple Dynamic String）有不同的头部结构类型，用于存储不同长度的字符串。以下是这些不同头部结构的定义：

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;    /* used */
    uint8_t alloc;  /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len;   /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len;   /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len;   /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

SDS 头部结构属性介绍：

• len：记录了字符串长度（不包括'\0'）。这样获取字符串长度的时候，只需要返回这个成员变量值就行，时间复杂度只需要 O（1）。
• alloc：分配给字符数组的空间长度（不包括'\0'）。这样在修改字符串的时候，可以通过 alloc - len 计算出剩余的空间大小，可以用来判断空间是否满足修改需求，如果不满足的话，就会自动将 SDS 的空间扩展至执行修改所需的大小，然后才执行实际的修改操作。因此，不会出现缓冲区溢出的问题。
• flags：用来表示不同类型的 SDS。一共设计了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64。
• buf[]：字符数组，用来保存实际数据，包括结尾空白字符 '\0'。不仅可以保存字符串，也可以保存二进制数据。

Redis 一共设计了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64。这 5 种类型的主要区别就在于，它们数据结构中的 len 和 alloc 成员变量的数据类型不同。

例如：sdshdr16 类型的 len 和 alloc 的数据类型都是 uint16_t，表示字符数组长度和分配空间大小不能超过 2 的 16 次方。

之所以 SDS 设计不同类型的结构体，是为了能灵活保存不同大小的字符串，从而有效节省内存空间。比如，在保存小字符串时，结构头占用空间也比较少。Redis 还提供了根据字符串的长度来选择对应的数据结构的函数：

static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5)  // 32
        return SDS_TYPE_5;
    if (string_size < 1<<8)  // 256
        return SDS_TYPE_8;
    if (string_size < 1<<16)   // 65536 64k
        return SDS_TYPE_16;
    if (string_size < 1ll<<32)  // 4294967296 4G
        return SDS_TYPE_32;
    return SDS_TYPE_64;
}

Redis 的 SDS 除了能够有效节省内存空间，还在 C 语言原本字符数组之上，增加了三个元数据：len、alloc、flags，用来解决 C 语言字符串的缺陷：

1. O(1) 复杂度获取字符串长度
   • C 语言的字符串长度获取 strlen 函数，需要通过遍历的方式来统计字符串长度，时间复杂度是 O(N)；
   • Redis 的 SDS 结构因为加入了 len 成员变量，那么获取字符串长度的时候，直接返回这个成员变量的值就行，所以复杂度只有 O(1)。
2. 二进制安全
   • C 字符串以 '\0' 字符作为字符串结束的标识，而对于一些二进制文件（如图片等），内容可能包括 '\0' 字符串，因此 C 字符串无法正确存取。
   • 因为 SDS 不需要用 '\0' 字符来标识字符串结尾了，而是有个专门的 len 成员变量来记录长度，所以可存储包含 '\0' 的数据。 SDS 的 API 都是以处理二进制的方式来处理 SDS 存放在 buf[] 里的数据，程序不会对其中的数据做任何限制，数据写入的时候时什么样的，它被读取时就是什么样的，因此可以支持图片、视频等二进制数据。
   • 但是 SDS 为了兼容部分 C 语言标准库的函数， SDS 字符串结尾还是会加上 '\0' 字符。
3. 不会发生缓冲区溢出
   • C 语言的字符串标准库提供的字符串操作函数，大多数都是不安全的，程序内部并不会判断缓冲区大小是否足够用，当发生了缓冲区溢出就有可能造成程序异常结束。
   • Redis 的 SDS 结构里引入了 alloc 和 len 成员变量，这样 SDS API 通过 alloc - len 计算，可以算出剩余可用的空间大小，这样在对字符串做修改操作的时候，就可以由程序内部判断缓冲区大小是否足够用，不够用时，会进行自动扩容。
4. 节省内存空间（前面已经提到）
   • SDS 结构中有个 flags 成员变量，表示的是 SDS 类型。
   • SDS 通过不同的头部结构类型（如 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64）来优化不同长度的字符串存储，之所以 SDS 设计不同类型的结构体，是为了能灵活保存不同大小的字符串，从而有效节省内存空间。比如，在保存小字符串时，结构头占用空间也比较少。

总结

本文讲述了 Redis 的对象机制，String 类型以及其内部实现方式，接下来就总结一下；

设计 redisObject 对象的主要目的是为 Redis 提供一个统一、灵活、高效的数据结构接口。通过 redisObject，Redis 可以实现类型安全、多态性、内存优化、性能优化、自动内存管理、LRU 机制和统一接口等功能。这些特性使得 Redis 能够高效地管理和操作不同类型的数据，满足各种复杂的应用需求。

String 类型的底层的数据结构实现是 long 和 SDS（简单动态字符串）。Redis 中的字符串数据结构可以被编码为多种形式：

• raw：字符串对象默认为 raw 格式编码，使用一个简单动态字符串（SDS）来保存这个字符串；
• int：整数编码。当字符串表示一个整数值时，Redis 会尝试使用整数编码来优化内存使用和操作效率。当一个字符串值存储到 Redis 中时，Redis 会检测这个字符串是否可以被解析为整数。如果可以，并且整数值在 64 位有符号整数范围内，Redis 会使用整数编码来存储这个值，保存为 long 类型；
• embstr：如果字符串长度小于等于 OBJ_ENCODING_EMBSTR_SIZE_LIMIT（通常为 44 字节），尝试进行 EMBSTR 编码，它将字符串对象和字符串数据存储在连续的内存块中，以减少内存碎片和内存分配开销。

Redis 实现了自己的字符串类型 SDS，而不是直接使用 C 语言的字符串类型，解决了 C 语言字符串的多个缺陷，C 字符串与 SDS 对比如下：

C字符串	SDS
获取字符串长度复杂度为O(N)	获取字符串长度复杂度为O(1)
API 是不安全的，可能会造成缓冲区溢出	API 是安全的，不会造成缓冲区溢出
修改字符串长度必然会需要执行内存重分配	修改字符串长度 N 次最多会需要执行 N 次内存重分配
只能保存文本数据	可以保存文本或二进制数据
可以使用所有<string.h>库中的函数	可以使用一部分<string.h>库中的函数