Redisでは、C言語標準の文字列（char*）を拡張した独自の動的文字列ライブラリ「SDS (Simple Dynamic Strings)」を採用しています。主なソースコードは sds.h と sds.c に実装されています。

1. SDSのデータ構造

SDSは、文字列の長さに応じて複数のヘッダー構造体を使い分け、メモリ使用量を最適化しています。

typedef char *sds;

/* 構造体のパディングを無効化し、メモリを緊密に配置する */
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;      /* 使用済みの長さ */
    uint8_t alloc;    /* 割り当て済みの全容量（ヘッダーとNULL終端を除く） */
    unsigned char flags; /* 下位3ビットで型を識別 */
    char buf[];       /* 実際のデータ（フレキシブル配列メンバ） */
};

struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len;
    uint16_t alloc;
    unsigned char flags;
    char buf[];
};

struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len;
    uint32_t alloc;
    unsigned char flags;
    char buf[];
};

struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len;
    uint64_t alloc;
    unsigned char flags;
    char buf[];
};

__attribute__ ((__packed__)) を使用することで、コンパイラによる境界調整（アライメント）のためのパディングを防いでいます。これにより、文字列のポインタ s から1バイト戻った位置（s[-1]）を直接参照することで、フラグ情報を即座に取得できるようになります。

2. ヘッダーへのアクセス手法

SDSポインタは常に buf の先頭を指しています。そのため、メタデータ（長さや容量）を取得するには、ポインタ演算を用いてヘッダーの開始位置を特定します。

#define SDS_HDR_8(s) ((struct sdshdr8 *)((s)-(sizeof(struct sdshdr8))))

static inline size_t sdslen(const sds s) {
    unsigned char info_flag = s[-1];
    switch(info_flag & 7) { // 下位3ビットのタイプを確認
        case 1: // SDS_TYPE_8
            return SDS_HDR_8(s)->len;
        // 他のタイプも同様のロジックで取得
    }
    return 0;
}

3. 文字列の生成と初期化

新しいSDS文字列を生成する際、Redisは指定された初期サイズに基づいて最適なヘッダータイプを選択します。

sds create_new_sds(const void *init_data, size_t init_len) {
    void *raw_ptr;
    sds s_ptr;
    char sds_type = select_sds_type(init_len);
    
    // 空文字列の場合は、将来の拡張性を考慮してTYPE_8以上に昇格させることが多い
    if (sds_type == 0 && init_len == 0) sds_type = 1;

    int header_size = calculate_header_size(sds_type);
    raw_ptr = s_malloc(header_size + init_len + 1); // +1は'\0'のため
    
    if (raw_ptr == NULL) return NULL;
    
    s_ptr = (char*)raw_ptr + header_size;
    unsigned char *flags_ptr = (unsigned char*)s_ptr - 1;
    
    // ヘッダー情報の初期化
    setup_header(s_ptr, sds_type, init_len);
    
    if (init_len && init_data) {
        memcpy(s_ptr, init_data, init_len);
    }
    s_ptr[init_len] = '\0';
    return s_ptr;
}

4. 動的なメモリ拡張メカニズム

SDSの最大の特徴は、文字列の結合（append）時に発生するメモリ再割り当ての最適化です。

sds expand_sds_capacity(sds s, size_t needed_len) {
    size_t current_free = sds_get_free_space(s);
    if (current_free >= needed_len) return s;

    size_t current_len = sdslen(s);
    size_t target_len = current_len + needed_len;

    // 1MB未満なら2倍に拡張、1MB以上なら1MBずつ追加する（事前割り当て戦略）
    if (target_len < 1024 * 1024)
        target_len *= 2;
    else
        target_len += 1024 * 1024;

    char old_type = s[-1] & 7;
    char new_type = select_sds_type(target_len);
    
    // TYPE_5は拡張に適さないため、TYPE_8へ強制変換
    if (new_type == 0) new_type = 1;

    void *old_hdr = (char*)s - calculate_header_size(old_type);
    void *new_hdr;
    size_t new_header_size = calculate_header_size(new_type);

    if (old_type == new_type) {
        new_hdr = s_realloc(old_hdr, new_header_size + target_len + 1);
        if (new_hdr == NULL) return NULL;
        s = (char*)new_hdr + new_header_size;
    } else {
        // ヘッダーサイズが変わる場合は再配置が必要
        new_hdr = s_malloc(new_header_size + target_len + 1);
        if (new_hdr == NULL) return NULL;
        memcpy((char*)new_hdr + new_header_size, s, current_len + 1);
        s_free(old_hdr);
        s = (char*)new_hdr + new_header_size;
        s[-1] = new_type;
    }
    
    set_sds_alloc(s, target_len);
    return s;
}

この戦略により、文字列を頻繁に更新する場合でも、システムコールの回数を大幅に削減し、実行効率を高めています。

5. SDSの利点

• 計算量 O(1) での長さ取得: strlenのように文字列を走査する必要がありません。
• バイナリセーフ: 内部に \0 を含めることができるため、画像データやシリアライズされたバイナリも扱えます。
• バッファオーバーフローの防止: 割り当てサイズを常に把握しているため、安全に結合操作が行えます。
• C標準関数との互換性: 常に末尾に \0 を付与するため、printf 等の既存の関数にそのまま渡すことができます。