1. SDS 概述
   1.1 什么是 SDS
   SDS (Simple Dynamic String) 是 Redis 中用于存儲(chǔ)字符串的核心數(shù)據(jù)結(jié)構(gòu)，相比傳統(tǒng)的 C 字符串具有顯著優(yōu)勢(shì)：

// C 字符串的問(wèn)題
char *str = "hello";
int len = strlen(str);  // O(n) 時(shí)間復(fù)雜度

// SDS 的優(yōu)勢(shì)  
sds s = sdsnew("hello");
size_t len = sdslen(s); // O(1) 時(shí)間復(fù)雜度

1.2 SDS vs C 字符串對(duì)比

image.png

2. SDS 數(shù)據(jù)結(jié)構(gòu)詳解
   2.1 五種 SDS 結(jié)構(gòu)
   Redis 根據(jù)字符串長(zhǎng)度使用不同的結(jié)構(gòu)，實(shí)現(xiàn)空間優(yōu)化：

typedef char *sds;

// 1. 超小字符串 (< 32字節(jié))
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags;    // 標(biāo)志位 + 長(zhǎng)度信息
    char buf[];            // 字符串?dāng)?shù)據(jù)
};

// 2. 小字符串 (32-255字節(jié))
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;           // 已使用長(zhǎng)度 (1字節(jié))
    uint8_t alloc;         // 總分配長(zhǎng)度 (1字節(jié))  
    unsigned char flags;   // 標(biāo)志位
    char buf[];           // 字符串?dāng)?shù)據(jù)
};

// 3. 中等字符串 (256字節(jié)-64KB)
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len;          // 已使用長(zhǎng)度 (2字節(jié))
    uint16_t alloc;        // 總分配長(zhǎng)度 (2字節(jié))
    unsigned char flags;   // 標(biāo)志位
    char buf[];           // 字符串?dāng)?shù)據(jù)
};

// 4. 大字符串 (64KB-4GB)
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len;          // 已使用長(zhǎng)度 (4字節(jié))
    uint32_t alloc;        // 總分配長(zhǎng)度 (4字節(jié))
    unsigned char flags;   // 標(biāo)志位
    char buf[];           // 字符串?dāng)?shù)據(jù)
};

// 5. 超大字符串 (>4GB)
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len;          // 已使用長(zhǎng)度 (8字節(jié))
    uint64_t alloc;        // 總分配長(zhǎng)度 (8字節(jié))
    unsigned char flags;   // 標(biāo)志位
    char buf[];           // 字符串?dāng)?shù)據(jù)
};

3. 內(nèi)存優(yōu)化原理
   3.1 packed 屬性的作用

// ? 沒(méi)有 __packed__ - 浪費(fèi)空間
struct sdshdr32_normal {
    uint32_t len;        // 4字節(jié)
    uint32_t alloc;      // 4字節(jié)  
    unsigned char flags; // 1字節(jié)
    // 編譯器自動(dòng)填充 3字節(jié)
};
// 總大?。?2字節(jié)

// ? 使用 __packed__ - 節(jié)省空間
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len;        // 4字節(jié)
    uint32_t alloc;      // 4字節(jié)
    unsigned char flags; // 1字節(jié)
    // 無(wú)填充
};
// 總大小：9字節(jié)，節(jié)省 25% 空間！

3.2 分級(jí)結(jié)構(gòu)的空間節(jié)省

# 如果統(tǒng)一使用最大結(jié)構(gòu)存儲(chǔ)所有字符串
存儲(chǔ) "hello" (5字符)：
- 統(tǒng)一方案：17字節(jié)頭部 + 5字節(jié)數(shù)據(jù) = 22字節(jié)
- SDS方案：3字節(jié)頭部 + 5字節(jié)數(shù)據(jù) = 8字節(jié)
- 節(jié)?。?4% 的空間！

3.3 整數(shù)類型選擇原理

image.png

4. Redis 字符串對(duì)象編碼類型
   4.1 三種編碼方式
   Redis 字符串對(duì)象會(huì)根據(jù)內(nèi)容自動(dòng)選擇最優(yōu)編碼：
   INT 編碼

# 適用：純數(shù)字字符串
redis> SET count "123"
redis> OBJECT ENCODING count
"int"

# 內(nèi)存結(jié)構(gòu)：僅占用 redisObject，約16字節(jié)

EMBSTR 編碼

# 適用：長(zhǎng)度 ≤ 44字節(jié)的字符串
redis> SET name "Alice"
redis> OBJECT ENCODING name  
"embstr"

# 內(nèi)存結(jié)構(gòu)：redisObject + SDS 連續(xù)存儲(chǔ)
[redisObject][sdshdr8][字符串?dāng)?shù)據(jù)]

RAW 編碼

# 適用：長(zhǎng)度 > 44字節(jié) 或 需要修改的字符串
redis> SET article "很長(zhǎng)的文章內(nèi)容..."
redis> OBJECT ENCODING article
"raw"

# 內(nèi)存結(jié)構(gòu)：redisObject 和 SDS 分別分配
redisObject → ptr → [sdshdr*][字符串?dāng)?shù)據(jù)]

4.2 編碼自動(dòng)轉(zhuǎn)換

# 數(shù)字 → 字符串
redis> SET val "123"        # INT編碼
redis> APPEND val "abc"     # 轉(zhuǎn)為EMBSTR編碼

# 短串 → 長(zhǎng)串
redis> SET msg "short"      # EMBSTR編碼  
redis> APPEND msg "很長(zhǎng)很長(zhǎng)..." # 轉(zhuǎn)為RAW編碼

# 只讀 → 可寫
redis> SET greeting "hello" # EMBSTR編碼
redis> APPEND greeting "!"  # 轉(zhuǎn)為RAW編碼

5. SDS 核心算法
   5.1 長(zhǎng)度獲取算法

static inline size_t sdslen(const sds s) {
    unsigned char flags = s[-1];  // 獲取flags字段
    switch(flags & SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->len;
        case SDS_TYPE_16:  
            return SDS_HDR(16,s)->len;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->len;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;
}

5.2 空間預(yù)分配策略

sds sdsMakeRoomFor(sds s, size_t addlen) {
    size_t free = sdsavail(s);
    size_t len, newlen;
    
    if (free >= addlen) return s;  // 空間足夠
    
    len = sdslen(s);
    newlen = (len + addlen);
    
    // 預(yù)分配策略
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;  // 小于1MB時(shí)，分配2倍空間
    else
        newlen += SDS_MAX_PREALLOC;  // 大于1MB時(shí)，額外分配1MB
        
    return sdsResize(s, newlen);
}

6. 內(nèi)存布局圖解

SDS內(nèi)存布局示例 (sdshdr16):
┌──────────┬──────────┬───────┬─────────────────┬────┐
│   len    │  alloc   │ flags │      buf[]      │ \0 │
│ (2字節(jié))  │ (2字節(jié))  │(1字節(jié))│   (字符串?dāng)?shù)據(jù))   │    │
└──────────┴──────────┴───────┴─────────────────┴────┘
           ↑                   ↑                      
         頭部信息            sds指針指向這里