关于redis:Redis-系列redis-学习十五redis-sds数据结构和底层设计原理

redis 是 C 语言写的，那么咱们思考一下 redis 是如何示意一个字符串的？redis 的数据结构和 C 语言的数据结构是一样的吗？

咱们能够看到 redis 源码中的 sds 库函数，和 sds 的具体实现，别离有如下 2 个文件：

• sds.h
• sds.c

具体门路是：deps/hiredis/sds.h , deps/hiredis/sds.c

sds.h 中波及如下数据结构：

SDS

redis 中 SDS simple Dynamic string

简略动静字符串

C 语言中示意字符串的形式是字符数组，例如：

char data[]="xiaomotong"

如果 C 语言须要扩容的话须要重新分配一个再大一点的内存，寄存新的字符串，若每次都要重新分配字符串，对于效率和性能必然会大大降低，并且若某一个字符串是“xiaomo\0tong”

这个时候，实际上 C 中 遇到‘\0’就完结了，因而理论 “xiaomo\0tong” 只会读取到xiaomo , 字符串长度就是 6

因而 redis 中的 sds 数据结构是这样设计的，是通过一个成员来标记字符串的长度：

SDS：free:0
    len:6
    char buf[]="xiaomo"
        
若这个时候，咱们须要在字符串前面追加字符串，sds 就会进行扩容，例如在前面加上“tong”，那么 sds 的数据结构中的值会变成如下：free:10
    len:10
    char buf[]="xiaomotong"      

最初的 "xiaomotong" 也是带有 \0 的，这也放弃了 C 语言的规范，redis 中对于 sds 数据结构扩容是成倍增加的，然而到了肯定的级别，例如 1M 的时候，就不会翻倍的扩容，而是做加法 例如 1M 变成 2M，2M 变成 3M 等等

SDS 的劣势：

• 二进制平安的数据结构
• 内存预分配机制，防止了频繁的内存调配
• 兼容 C 语言的库函数

redis 源码 sds 数据结构

当初咱们看到的是 reids-6.2.5 sds 的数据结构，将以前的示意一个长度应用了 int 类型，是 32 字节的，能示意的长度能够达到 42 亿，其实远远没有必要应用 int32，太浪费资源了

上面的数据结构，能够依据不同的需要，选取不同的数据结构进行应用

struct __attribute__ ((__packed__)) hisdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];};
struct __attribute__ ((__packed__)) hisdshdr8 {
    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__)) hisdshdr16 {
    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__)) hisdshdr32 {
    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__)) hisdshdr64 {
    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[];};

• hisdshdr5

用于长度在 0 — 2^5 – 1 范畴内

• hisdshdr8

用于长度在 2^5– 2^8 – 1 范畴内

• hisdshdr16

用于长度在 2^8 — 2^16 – 1 范畴内

• hisdshdr32

用于长度在 2^16 — 2^32 – 1 范畴内

• hisdshdr64

用于长度在 2^32 — 2^64 – 1 范畴内

上述的 unsigned char flags 占用 1 个字节，8 个 bit 位：

• 其中 3 位 用于示意类型
• 其中 5 位 用于示意字符串的长度

后面 3 个 bit 位，能示意的数字范畴是 0 – 7，对于应到如下宏

#define HI_SDS_TYPE_5  0
#define HI_SDS_TYPE_8  1
#define HI_SDS_TYPE_16 2
#define HI_SDS_TYPE_32 3
#define HI_SDS_TYPE_64 4
#define HI_SDS_TYPE_MASK 7

源码实现是通过与操作来获取到具体的数据结构类型的：

咱们以 hisdshdr8 数据结构为例子，unsigned char flags 是这样的

• len

示意曾经应用的长度

• alloc

预调配的空间大小

• flag

示意应用哪一种数据结构（前 3 个 bit）

• buf

理论存储的字符串

那么，咱们就可能计算出来，该数据结构的空间残余 free = alloc – len

源码中 sds.h 下的函数 hisds hi_sdsnewlen(const void *init, size_t initlen)

应用 一个 init 指针和 initlen 长度，来创立一个字符串

hisds hi_sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    hisds s;
    // 计算 type，获取须要应用的数据结构类型
    char type = hi_sdsReqType(initlen);
    // 当初默认应用 HI_SDS_TYPE_8 了
    if (type == HI_SDS_TYPE_5 && initlen == 0) type = HI_SDS_TYPE_8;
    
    int hdrlen = hi_sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */
    
    // 分配内存
    sh = hi_s_malloc(hdrlen+initlen+1);
    if (sh == NULL) return NULL;
    if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    s = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)-1;
    // 依据不同的类型对数据结构初始化
    switch(type) {
        case HI_SDS_TYPE_5: {*fp = type | (initlen << HI_SDS_TYPE_BITS);
            break;
        }
        case HI_SDS_TYPE_8: {HI_SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case HI_SDS_TYPE_16: ...
        case HI_SDS_TYPE_32: ...
        case HI_SDS_TYPE_64: ...
    }
    if (initlen && init)
        memcpy(s, init, initlen);
    // 兼容 C 库，字符串前面加上 \0
    s[initlen] = '\0';
    return s;
}

• hi_sdsReqType

依据字符串的长度来计算所应用的数据类型

• hi_sdsHdrSize

依据不同的类型，获取该类型须要调配的空间大小

• hi_s_malloc

开拓内存，调用的是 alloc.h 中的 hi_malloc，具体实现就看不到了

• switch(type) …

依据不同的类型，来将对应的数据结构做初始化

• s[initlen] = ‘\0’

兼容 C 库，字符串前面加上’\0’

redis k-v 底层设计原理

redis 是如何存储海量数据的？

redis 中数据是以 key-value 的形式来存储的，key 都是字符串，而 value 依据不同的数据结构表现形式也不太一样

他们的存储形式是以 数组 + 链表的形式存储的：

• 数组

数组中寄存的是链表的地址

• 链表

链表中存储的是具体的数据

举个例子：

下面有说到 redis 外面的 key 都是字符串的形式，那么如何与数组和链表进行联合呢？

具体逻辑是应用 hash 函数，将字符串 key 依照算法计算出一个索引值，这个值就是数组的索引，该索引对应的数组元素是指向一个链表的，链表中寄存具体的数据

• dict[10] 作为数组，每一个元素会指向一条链表
• 当初咱们要插入 k1 – v1 , k2 – v2 , k3 – v3

通过 hash 函数进行计算：

hash(k1) % 10 = 0

hash(k2) % 10 = 1

此处对 10 取模的起因是，整个数组就只能寄存 10 个元素

那么后果是这样的

dict[0] -> (k1,v1) -> null
dict[1] -> (k2,v2) -> null

若这个时候咱们插入的 (k3，v3) 计算出来的索引与后面已有数据的抵触了咋办？

hash(k3) % 10 = 1

这就会 呈现 hash 抵触 了，当 hash 抵触的时候，若 k3 与 k2 是相等了，那么就会间接更新 k2 对应的 value 值

若 k3 与 k2 不同，则会通过 链地址法来解决 hash 抵触，会把 (k3，v3) 通过头插法来插入到原有的链表中，如：

dict[0] -> (k1,v1) -> null
dict[1] -> (k3,v3) -> (k2,v2) -> null

小结：

• 对于上述的 hash，雷同的输出，肯定会有雷同的输入
• 不同的输出，也有可能有雷同的输入，此时就 hash 抵触了，是须要解决的

参考资料：

• redis_doc
• reids 源码 reids-6.2.5 Redis 6.2.5 is the latest stable version.

欢送点赞，关注，珍藏

敌人们，你的反对和激励，是我保持分享，提高质量的能源

欢送大家对文章中的源码细节进行探讨和分享，不足之处还请多多指教，如果大佬们有更好的学习办法还请给予领导，谢谢

1、评论区超过 10 人互动（不含作者自己），作者能够以本人的名义抽奖送出掘金徽章 2 枚（掘金官网承当）

好了，本次就到这里

技术是凋谢的，咱们的心态，更应是凋谢的。拥抱变动，背阴而生，致力向前行。

我是 小魔童哪吒，欢送点赞关注珍藏，下次见~