Redis 设计与实现——Redis简单动态字符串

小咪咪 2022-09-03 04:17 151阅读 0赞

# Redis简单动态字符串 #

Redis不直接使用C语言传统的字符串表示，而是自己构建了一种名为**简单动态字符串**（SDS）的抽象类型。而在Redis中，C字符串只会作为字符串字面量。

redis> SET msg "hello world"
    OK

那么 Redis 将在数据库中创建了一个新的键值对， 其中：

*  键值对的键是一个字符串对象， 对象的底层实现是一个保存着字符串 `"msg"` 的 SDS 。
 *  键值对的值也是一个字符串对象， 对象的底层实现是一个保存着字符串 `"hello world"` 的 SDS 。

## SDS的定义 ##

Redis3.2版本前SDS的数据结构如下所示：

struct sdshdr {
        
        // 记录 buf 数组中已使用字节的数量
        // 等于 SDS 所保存字符串的长度
        int len;
        // 记录 buf 数组中未使用字节的数量
        int free;
        // 字节数组，用于保存字符串
        char buf[];
    
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70]

而在Redis3.2版本中，对数据结构进行了修改，目前的结构如下：

struct __attribute__ ((__packed__)) sdshdr8 {
         // 对应的字符串长度小于1<<8
        uint8_t len; /* used */ //目前字符串的长度
        uint8_t alloc; /* excluding the header and null terminator */ // 已经分配的总长度
        unsigned char flags; /* 3 lsb of type, 5 unused bits */ // //flag用3bit来标明类型，类型后续解释，其余5bit目前没有使用
        char buf[]; // //字符数组，以'\0'结尾
    };

和C字符串不同，因为SDS在len属性中记录了SDS本身的长度， 所以获取一个 SDS 长度的复杂度仅为O(1)。

## SDS与C字符串的区别 ##

1.  常数复杂度获取字符串长度。
2.  杜绝缓冲区溢出。  
    SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性： 当 SDS API 需要对 SDS 进行修改时， API 会先检查 SDS 的空间是否满足修改所需的要求， 如果不满足的话， API 会自动将 SDS 的空间扩展至执行修改所需的大小， 然后才执行实际的修改操作， 所以使用 SDS 既不需要手动修改 SDS 的空间大小， 也不会出现缓冲区溢出问题。
3.  减少修改字符串长度时所需的内存重分配次数。
4.  二进制安全。
5.  兼容部分C字符串函数。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70]: /images/20220829/7836d25279ff4c2187968ee4a2d6fb84.png