Redis 本质上是一个数据结构服务器,以高效的方式实现了多种现成的数据结构

https://redis.io/docs/latest/develop/data-types/

三层抽象结构

  • 对外数据类型:Redis API 的抽象,决定“这是什么”
  • 内部编码:Redis 内部的策略,决定“怎么存”
  • 基础数据结构:真正的代码实现,决定“具体存在哪里、怎么查找/遍历”
  • API 层:告诉 Redis “我要存什么”
  • 编码层:决定 “用哪种结构存”
  • 数据结构层:实现 “具体怎么存”

两种表述对比

角度 表述 含义 示例(string)
逻辑功能角度 “决定用哪种结构存” 这层负责 选择底层数据结构
也就是 encoding(int / embstr / raw,ziplist / dict / quicklist …)
"123" → int;"hello" → embstr;"very long text" → raw
操作方式角度 “决定怎么存” 这层负责 策略性的存储方式
包括选择数据结构、是否压缩、何时切换结构等
list 小量 → ziplist;大于阈值 → quicklist;
hash 小量 → ziplist,大量 → dict

区别在于角度:

  • “用哪种结构存” 强调的是 选择的结果(encoding)
  • “怎么存” 强调的是 策略逻辑(包括压缩、升级/降级、特殊情况优化)
层级 角色 核心功能
API / 对外数据类型 对外抽象 告诉 Redis “我要存什么” / “这是什么”
编码层 / internal encoding 策略层 决定 “用哪种数据结构存” + “什么时候切换结构” / “是否压缩” / “优化存储方式”
数据结构层 / 基础结构 实现层 真正的内存操作:分配、查找、遍历、删除

举例

对外数据类型(API 层)

  • 用户调用 SET key "hello"
  • Redis 解析命令 → 调用 setGenericCommand()createStringObject()

👉 代码位置:t_string.c(命令实现)


内部编码层(策略层)

  • createStringObject() 里会判断传入内容:
    • 如果是整数 → 生成 type=string, encoding=int
    • 如果是短字符串 → 生成 encoding=embstr
    • 如果是长字符串 → 生成 encoding=raw

👉 代码位置:object.c(redisObject 创建 & encoding 策略)

⚠️ 注意: 这里有“代码”,但它的职责是 决定用哪种基础结构,而不是自己去实现字符串存取


基础数据结构层(实现层)

  • 如果 encoding=raw/embstr → 会真正调用 sds.c 里的 API 来分配和存储:
    • sdsnewlen()
    • sdslen()
    • sdsfree()
  • 这些函数才是真正的 C 语言结构体操作,维护 buf、len、alloc 等字段

👉 代码位置:sds.c(字符串底层实现)

Redis 三层抽象 & 源码调用链

对外数据类型 (API) 内部编码层 (策略代码) 基础数据结构层 (实现代码) 调用链说明
String (SET/GET) object.c- createStringObject()- 判断 int/embstr/raw sds.c (raw/embstr)- sdsnewlen()- sdslen()- sdsfree() 用户 SET key val → t_string.c → object.c 判断 encoding → 调用 sds.c
List (LPUSH/LRANGE) object.c- createListObject() → 默认 quicklist quicklist.c + listpack.c Redis 3.2 后统一用 quicklist,节点里存 listpack;list API 在 t_list.c
Hash (HSET/HGET) object.c- createHashObject()- 小 → ziplist/listpack- 大 → dict listpack.c(小哈希)dict.c(大哈希) 命令在 t_hash.c,内部决定 ziplist/listpack 还是 dict
Set (SADD/SMEMBERS) object.c- createSetObject()- 全是整数 → intset- 否则 → dict intset.c(小整数集合)dict.c(一般集合) 命令在 t_set.c,内部根据成员是否全是整数决定用 intset 还是 dict
ZSet (Sorted Set) (ZADD/ZRANGE) object.c- createZsetObject()- 小 → ziplist/listpack- 大 → skiplist+dict listpack.c(小 zset)dict.c + skiplist(大 zset) 命令在 t_zset.c;大 zset 用 dict 做 O(1) 查找,skiplist 做范围查询
Stream (XADD/XRANGE) object.c- createStreamObject() rax.c(Radix Tree)+ listpack stream 用基数树存消息 ID,消息体用 listpack;命令在 t_stream.c

查看

  • 外部 type

    127.0.0.1:6379> set name dd
    OK
    127.0.0.1:6379> type name
    string
    127.0.0.1:6379> hset user name dd
    (integer) 1
    127.0.0.1:6379> type user
    hash
  • 内部 object encoding

    127.0.0.1:6379> set id 123
    OK
    127.0.0.1:6379> object encoding id
    "int"
    
    127.0.0.1:6379> set name dd
    OK
    127.0.0.1:6379> object encoding name
    "embstr"

总结几个关键点

  1. 抽象分层
    • 用户只看到逻辑类型(hash/set/list),而 Redis 可以自由切换实现
    • API 不变,但性能和内存利用率可以根据数据量自适应
  2. 内存效率
    • 小数据结构用紧凑存储(ziplist/intset)节省内存,减少碎片
    • 大数据结构用 dict/skiplist 保证性能
  3. 性能权衡
    • dict 提供 O(1) 查找,但内存开销大
    • ziplist 连续存储,内存紧凑,但插入/删除 O(N)
    • quicklist 结合两者优势
    • zset 用 dict + skiplist 组合同时兼顾 按值查找范围查询
  4. 灵活可扩展
    • redisObjectencoding 允许未来替换底层实现(比如 ziplist → listpack → future 更优化的结构)
    • 不会影响用户 API

redisObject

Redis所有数据类型的统一抽象

结构定义

struct redisObject {
    unsigned type:4;           // 对象类型,4位
    unsigned encoding:4;       // 编码方式,4位(底层实现)
    unsigned lru:LRU_BITS;     // LRU时间或LFU数据,24位(相对于 server.lruclock) 
    unsigned iskvobj : 1;      // 是否为kvobj,1位
    unsigned expirable : 1;    // 是否可过期,1位
    unsigned refcount : OBJ_REFCOUNT_BITS; // 引用计数,30位
    void *ptr;                 // 指向实际数据的指针
};

字段详解

type字段(4位)

表示对象的类型,支持以下类型:

  • OBJ_STRING (0) - 字符串对象

  • OBJ_LIST (1) - 列表对象

  • OBJ_SET (2) - 集合对象

  • OBJ_ZSET (3) - 有序集合对象

  • OBJ_HASH (4) - 哈希对象

  • OBJ_MODULE (5) - 模块对象

  • OBJ_STREAM (6) - 流对象

encoding字段(4位)

表示对象内部的编码方式,不同的编码方式对应不同的底层数据结构:

  • OBJ_ENCODING_RAW (0) - 原始编码

  • OBJ_ENCODING_INT (1) - 整数编码

  • OBJ_ENCODING_HT (2) - 哈希表编码

  • OBJ_ENCODING_INTSET (6) - 整数集合编码

  • OBJ_ENCODING_SKIPLIST (7) - 跳表编码

  • OBJ_ENCODING_EMBSTR (8) - 嵌入式字符串编码

  • OBJ_ENCODING_QUICKLIST (9) - 快速列表编码

  • OBJ_ENCODING_STREAM (10) - 流编码

  • OBJ_ENCODING_LISTPACK (11) - 列表包编码

  • OBJ_ENCODING_LISTPACK_EX (12) - 扩展列表包编码

lru字段(24位)

用于LRU(最近最少使用)或LFU(最不经常使用)算法:

  • LRU模式:存储对象的最后访问时间

  • LFU模式:低8位存储频率,高16位存储访问时间

iskvobj字段(1位)

标识这个结构是否作为kvobj的基类。kvobj是redisObject的特殊版本,用于存储键值对

expirable字段(1位)

标识这个键是否有过期时间。如果设置了,那么这个对象是kvobj类型

refcount字段(30位)

引用计数器,用于内存管理:

  • 普通对象的引用计数从1开始

  • OBJ_SHARED_REFCOUNT - 共享对象,永远不会被销毁

  • OBJ_STATIC_REFCOUNT - 静态对象,分配在栈上

ptr字段

指向实际数据的指针,根据type和encoding的不同,指向不同的数据结构

内存布局优化

Redis使用了位域(bit fields)来节省内存:

  • type和encoding各占4位,总共8位

  • lru占24位

  • iskvobj和expirable各占1位

  • refcount占30位

  • ptr是指针,通常8字节(64位系统)

特殊类型:kvobj

kvobj是redisObject的扩展版本,用于存储键值对:

typedef struct redisObject kvobj;
kvobj *kvobjCreate(int type, const sds key, void *ptr, int hasExpire) {
    // 计算嵌入键的大小
    size_t key_sds_len = sdslen(key);
    char key_sds_type = sdsReqType(key_sds_len);
    size_t key_sds_size = sdsReqSize(key_sds_len, key_sds_type);

    // 计算基础对象大小
    size_t min_size = sizeof(robj);
    if (hasExpire) min_size += sizeof(long long);
    min_size += 1 + key_sds_size; // 1字节用于SDS头部大小

    // 分配对象内存
    robj *o = zmalloc_usable(min_size, &bufsize);
    o->type = type;
    o->encoding = OBJ_ENCODING_RAW;
    o->ptr = ptr;
    o->refcount = 1;
    o->lru = 0;
    o->iskvobj = 1;
    o->expirable = hasExpire;

    // 在结构体后面嵌入数据
    char *data = (void *)(o + 1);
    
    // 设置过期时间字段
    if (o->expirable) {
        *(long long *)data = -1;
        data += sizeof(long long);
    }

    // 存储嵌入的键
    *data++ = sdsHdrSize(key_sds_type);
    sdsnewplacement(data, key_sds_size, key_sds_type, key, key_sds_len);

    return o;
}

内存布局示例

  +-----------+------------+------------------+------------------------+
  | robj (16) | expiry (8) | key-hdr-size (1) | sdshdr5 "mykey" \0 (7) | 
  +-----------+------------+------------------+------------------------+

对象创建和管理

创建对象

robj *createObject(int type, void *ptr) {
    robj *o = zmalloc(sizeof(*o));
    o->type = type;
    o->encoding = OBJ_ENCODING_RAW;
    o->ptr = ptr;
    o->refcount = 1;
    o->lru = 0;
    o->iskvobj = 0;
    o->expirable = 0;
    return o;
}

引用计数管理

void incrRefCount(robj *o) {
    if (o->refcount < OBJ_FIRST_SPECIAL_REFCOUNT) {
        o->refcount++;
    } else {
        if (o->refcount == OBJ_SHARED_REFCOUNT) {
            // 共享对象,无需操作
        } else if (o->refcount == OBJ_STATIC_REFCOUNT) {
            serverPanic("You tried to retain an object allocated in the stack");
        }
    }
}

void decrRefCount(robj *o) {
    if (o->refcount == OBJ_SHARED_REFCOUNT)
        return; // 共享对象,永不释放

    if (unlikely(o->refcount <= 0)) {
        serverPanic("illegal decrRefCount for object");
    }

    if (--(o->refcount) == 0) {
        // 根据对象类型释放内存
        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;
        case OBJ_MODULE: freeModuleObject(o); break;
        case OBJ_STREAM: freeStreamObject(o); break;
        default: serverPanic("Unknown object type"); break;
        }
        zfree(o);
    }
}

编码方式的动态转换

Redis会根据数据的特点动态选择最优的编码方式:

字符串对象

  • 小字符串:OBJ_ENCODING_EMBSTR(嵌入式)

  • 大字符串:OBJ_ENCODING_RAW

  • 整数:OBJ_ENCODING_INT

// 字符串对象的编码选择
robj *createStringObject(const char *ptr, size_t len) {
    if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT)
        return createEmbeddedStringObject(ptr,len);  // 嵌入式编码
    else
        return createRawStringObject(ptr,len);       // 原始编码
}
嵌入式字符串对象

对于小字符串,Redis使用嵌入式编码来节省内存:

robj *createEmbeddedStringObject(const char *val_ptr, size_t val_len) {
    size_t val_sds_size = sdsReqSize(val_len, SDS_TYPE_8);
    robj *o = zmalloc_usable(sizeof(robj) + val_sds_size, &bufsize);
    o->type = OBJ_STRING;
    o->encoding = OBJ_ENCODING_EMBSTR;  // 嵌入式编码
    o->refcount = 1;
    o->lru = 0;
    o->expirable = 0;
    o->iskvobj = 0;
    
    // 在对象后面直接存储字符串数据
    char *data = (char *)(o + 1);
    o->ptr = sdsnewplacement(data, remaining_size, SDS_TYPE_8, val_ptr, val_len);
    return o;
}

列表对象

  • 小列表:OBJ_ENCODING_LISTPACK

  • 大列表:OBJ_ENCODING_QUICKLIST

集合对象

  • 小整数集合:OBJ_ENCODING_INTSET

  • 大集合:OBJ_ENCODING_HT

内存管理特点

  1. 引用计数:避免重复释放和内存泄漏
  2. 共享对象:小整数等常用对象被共享使用
  3. 延迟释放:支持异步释放大对象
  4. 内存对齐:使用位域优化内存布局

实际应用示例

// 创建一个字符串对象
robj *str_obj = createStringObject("hello", 5);

// 创建一个列表对象
robj *list_obj = createQuicklistObject();

// 检查对象类型
if (str_obj->type == OBJ_STRING) {
    // 处理字符串对象
}

// 增加引用计数
incrRefCount(str_obj);

// 减少引用计数
decrRefCount(str_obj);

Redis对象机制

动态编码优化机制

Redis会根据数据特点自动选择最优编码方式,这是其内存优化的核心:

robj *tryObjectEncodingEx(robj *o, int try_trim) {
    long value;
    sds s = o->ptr;
    size_t len;

    // 只对字符串对象进行编码优化
    serverAssertWithInfo(NULL,o,o->type == OBJ_STRING);
    
    // 只处理RAW或EMBSTR编码的对象
    if (!sdsEncodedObject(o)) return o;
    
    // 共享对象不能重新编码
    if (o->refcount > 1) return o;

    // 尝试转换为整数编码
    len = sdslen(s);
    if (len <= 20 && string2l(s,len,&value)) {
        if (o->encoding == OBJ_ENCODING_RAW) {
            sdsfree(o->ptr);
            o->encoding = OBJ_ENCODING_INT;
            o->ptr = (void*) value;
            return o;
        } else if (o->encoding == OBJ_ENCODING_EMBSTR) {
            decrRefCount(o);
            return createStringObjectFromLongLongForValue(value);
        }
    }

    // 尝试转换为嵌入式编码
    if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT) {
        robj *emb;
        if (o->encoding == OBJ_ENCODING_EMBSTR) return o;
        emb = createEmbeddedStringObject(s,sdslen(s));
        decrRefCount(o);
        return emb;
    }

    // 最后尝试优化SDS字符串
    if (try_trim)
        trimStringObjectIfNeeded(o, 0);

    return o;
}

编码转换的触发时机

  • SET命令:设置新值时

  • INCR/DECR:数值操作时

  • APPEND:字符串追加时

  • 内存优化:主动调用tryObjectEncoding

对象比较机制

Redis提供了多种对象比较方式

int compareStringObjectsWithFlags(const robj *a, const robj *b, int flags) {
    serverAssertWithInfo(NULL,a,a->type == OBJ_STRING && b->type == OBJ_STRING);
    char bufa[128], bufb[128], *astr, *bstr;
    size_t alen, blen, minlen;

    if (a == b) return 0;
    
    // 处理不同编码的字符串
    if (sdsEncodedObject(a)) {
        astr = a->ptr;
        alen = sdslen(astr);
    } else {
        alen = ll2string(bufa,sizeof(bufa),(long) a->ptr);
        astr = bufa;
    }
    
    if (sdsEncodedObject(b)) {
        bstr = b->ptr;
        blen = sdslen(bstr);
    } else {
        blen = ll2string(bufb,sizeof(bufb),(long) b->ptr);
        bstr = bufb;
    }
    
    // 根据标志选择比较方式
    if (flags & REDIS_COMPARE_COLL) {
        return strcoll(astr,bstr);  // 使用locale比较
    } else {
        int cmp;
        minlen = (alen < blen) ? alen : blen;
        cmp = memcmp(astr,bstr,minlen);  // 二进制比较
        if (cmp == 0) return alen-blen;
        return cmp;
    }
}

内存使用计算

Redis提供了精确的内存使用计算:

size_t objectComputeSize(robj *key, robj *o, size_t sample_size, int dbid) {
    dict *d;
    dictIterator di;
    struct dictEntry *de;
    size_t asize = 0, elesize = 0, elecount = 0, samples = 0;

    if (o->type == OBJ_STRING) {
        if(o->encoding == OBJ_ENCODING_INT) {
            asize = sizeof(*o);  // 整数编码只计算对象头
        } else if(o->encoding == OBJ_ENCODING_RAW) {
            asize = sdsZmallocSize(o->ptr)+sizeof(*o);  // RAW编码加上SDS大小
        } else if(o->encoding == OBJ_ENCODING_EMBSTR) {
            asize = zmalloc_size((void *)o);  // 嵌入式编码计算整个对象
        }
    } else if (o->type == OBJ_LIST) {
        if (o->encoding == OBJ_ENCODING_QUICKLIST) {
            quicklist *ql = o->ptr;
            quicklistNode *node = ql->head;
            asize = sizeof(*o)+sizeof(quicklist);
            
            // 采样计算平均节点大小
            do {
                elesize += sizeof(quicklistNode)+zmalloc_size(node->entry);
                elecount += node->count;
                samples++;
            } while ((node = node->next) && samples < sample_size);
            
            asize += (double)elesize/elecount*ql->count;
        }
    }
    // ... 其他类型的计算
    return asize;
}

LRU/LFU机制

Redis支持两种内存淘汰策略:

int objectSetLRUOrLFU(robj *val, long long lfu_freq, long long lru_idle,
                       long long lru_clock, int lru_multiplier) {
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        // LFU模式:高16位存储时间,低8位存储频率
        if (lfu_freq >= 0) {
            serverAssert(lfu_freq <= 255);
            val->lru = (LFUGetTimeInMinutes()<<8) | lfu_freq;
            return 1;
        }
    } else if (lru_idle >= 0) {
        // LRU模式:存储最后访问时间
        lru_idle = lru_idle*lru_multiplier/LRU_CLOCK_RESOLUTION;
        long lru_abs = lru_clock - lru_idle;
        
        // 处理时钟回绕
        if (lru_abs < 0)
            lru_abs += LRU_CLOCK_MAX;
        val->lru = lru_abs;
        return 1;
    }
    return 0;
}

对象类型检查

int checkType(client *c, robj *o, int type) {
    if (o->type != type) {
        addReply(c,shared.wrongtypeerr);
        return 1;
    }
    return 0;
}

数值转换机制

Redis提供了多种数值转换函数

int getLongLongFromObject(robj *o, long long *target) {
    long long value;

    if (o == NULL) {
        value = 0;
    } else {
        serverAssertWithInfo(NULL,o,o->type == OBJ_STRING);
        if (sdsEncodedObject(o)) {
            if (string2ll(o->ptr, sdslen(o->ptr), &value) == 0) return C_ERR;
        } else if (o->encoding == OBJ_ENCODING_INT) {
            value = (long)o->ptr;
        } else {
            serverPanic("Unknown string encoding");
        }
    }
    *target = value;
    return C_OK;
}

对象长度获取

size_t getObjectLength(robj *o) {
    switch(o->type) {
        case OBJ_STRING: return stringObjectLen(o);
        case OBJ_LIST: return listTypeLength(o);
        case OBJ_SET: return setTypeSize(o);
        case OBJ_ZSET: return zsetLength(o);
        case OBJ_HASH: return hashTypeLength(o, 0);
        case OBJ_STREAM: return streamLength(o);
        default: return 0;
    }
}

对象调试命令

Redis提供了OBJECT命令来检查对象内部状态

void objectCommand(client *c) {
    kvobj *kv;

    if (!strcasecmp(c->argv[1]->ptr,"refcount") && c->argc == 3) {
        // 返回引用计数
        addReplyLongLong(c, kv->refcount);
    } else if (!strcasecmp(c->argv[1]->ptr,"encoding") && c->argc == 3) {
        // 返回编码方式
        addReplyBulkCString(c,strEncoding(kv->encoding));
    } else if (!strcasecmp(c->argv[1]->ptr,"idletime") && c->argc == 3) {
        // 返回空闲时间
        addReplyLongLong(c, estimateObjectIdleTime(kv) / 1000);
    } else if (!strcasecmp(c->argv[1]->ptr,"freq") && c->argc == 3) {
        // 返回访问频率(LFU模式)
        addReplyLongLong(c,LFUDecrAndReturn(kv));
    }
}