Redis存储原理剖析<一>：存储模型和基础命令解析

1. 前言

2022年，是充满挑战性的一年。

这一年，我选择离开了自己熟悉的信息化领域，把精力投向了互联网金融。

在22年的后半程，鉴于平台和团队所带来的效应，个人也在高频交易业务领域吸收了足够多的知识。过程中，认知的颠覆和自我的怀疑常常是共存。

所幸这些经历最后都能够作为养分，支撑我一步步走到当下。

这个系列的文章，初稿实际上在22年的年底就已经完成。但碍于平日里事务繁忙兼琐事繁多，使得日子一再蹉跎，一直推迟到23年过半，才开始尝试去重新梳理其中的些许细节，并准备将它发表在博客里。

初稿原本诞生于22年在高频交易系统的技术选型、架构搭建和研发过程中。当时和团队里优秀的工程师们对redis尝试不断地深入探索，试图吸收其在架构设计方面的优点，并思考对于交易业务领域可以如何进行二次开发以达到发挥极致性能的目的，从而形成了这份初稿。当然，由于保密机制，文档中原先存在的定制化方案和敏感信息已去除，但对redis架构有兴趣的朋友，仍然可以通过这个系列洞悉redis在设计方面的优点。

过程中难免会因为篇幅原因删除细枝末节的代码，这也是为更好的去掌握主流程，让整个文档脉络更清晰而做的取舍。若对内容有异议，可通过邮箱联系我。
                                        huangzh
                                        2023.08.25

阅读本文档存在一些门槛，不建议新手直接阅读，建议大家先掌握以下必要的技能：

良好的c语言基础。
掌握多路复用编程网络模型。
对操作系统中io的认知。
学习并调试过其他常用中间件代码的经验。
耐心。

redis的存储模型，是典型的hash存储。即一个key对应一个或多个值，这在redis支持的数据类型有着明确的体现，redis一共支持五种类型的数据结构存储：

string
hash（又称为set）
list
zset
zlist

从广义上来看，这五种类型数据的存储都可以用key-value形式去实现，无非是value所对应的值的形式有所不同。

2. hash存储引擎

提到redis，不得不先提及hash存储引擎的概念，一个典型的hash存储引擎原理如下图所示：

hash存储示意

这种基于hash的存储方式，与传统关系性数据库有着非常大的区别。

在内存中通过一定的hash算法均匀的散列key值，使不同的key均匀的散落在hashtable的不同栏位。

由于相同的key可能对应不同的value，因此hashtable每个栏位实际上采用挂载链表的形式存储每一个value节点。

每个value节点中，包含三个最重要的元素：

position：value的起始位置
size：value对应的长度
fileid：value存储的文件标识符

当然，节点中当然可以包含其他额外的值，不同软件有着自己的额外添加的元素。

但是，不约而外的，通过这三个必要的元素，可以找到key对应的value究竟存储于哪个文件，以及value在该文件中对应的起始位置和长度。

通过这种方式，实际上可以很方便的查找key-value元素。同时，这种方式将hashtable中每个栏位的写入由随机写（hash值随机）转变为顺序写（每个栏位的数据只需要顺序往该栏位对应的文件中添加即可，通过节点链表顺序连接），大大提高了写入的效率。

同时，使用hash存储引擎还存在以下特点：

时间复杂度o(1)。
满足“=”，“IN”条件查询。
不支持范围查询，比如between关键字。
不支持order by关键字排序。

3. redis数据模型

我们在描述一种存储类型的中间件时，无论它是缓存类的存储，亦或是传统写入磁盘的关系性数据库存储，都存在它们各自最基础也是最核心的数据存储模型，这里我个人习惯把它叫做数据模型，基于数据模型才能实现上层复杂的结构存储。

redis的数据模型，可以把它看成字典，一种基于key-value存储的数据结构，底层由数组实现的基于hashtable的拉链法存储。

以下是从redis源码中提取的四种以此从外到内的核心数据模型，其中redisDb为最外层，抽丝剥茧之后，不难发现真正的数据存储于底层的dictEntry：

typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB */
    dict *expires;              /* Timeout of keys with a timeout set */
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP)*/
    dict *ready_keys;           /* Blocked keys that received a PUSH */
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    int id;                     /* Database ID */
    long long avg_ttl;          /* Average TTL, just for stats */
    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

dictEntry是最基本的存储单元，包含了一组key-value元素，key即存储对应的key值，v所对应的union结构存储具体类型对应的value。还有一个next指针指向下一个存储单元，这样就可以构成一个链表。

dictht（全称dicthashtable）包含多条由dictEntry构成的链表，table作为二级指针，表示一组dictEntry，其中每一个dictEntry存储的值是指向具体存储了某个数据的dictEntry的指针，size标识有几条链表存在，used表示所有链表的节点总数。

dict再封装了两个dictht，一个用于存储真实的key-value数据（datatable），一个用于渐进式hash时临时存放原有的数据，我们的redis客户端指令每次对key的查找请求都是去datatable获取数据。

redisDb封装了dict，此外还有带有expire key的字典，即expires，可以理解为expires内部，用hash存储的方式存储了key对应的过期时间戳。

4. 命令代码执行过程分析

我们从两个最基本的redis命令案例分析源代码，实际上，这个过程不可能面面俱到，但是只要掌握大体的流程，就可以逐步洞悉内部的精髓。

4.1 expire key expire

来看一个最基本的命令：

expire testKey 60

这个命令表示对值为testKey的key，设置60毫秒的过期时间。来看redis代码中对于该命令的处理：

void ç(client *c, redisDb *db, robj *key, long long when) {
    dictEntry *kde, *de;

    // 1.先从redisDb中的dict中获取存储了key-value的dictEntry，由kde指针指向该dictEntry的地址
    kde = dictFind(db->dict,key->ptr);
    serverAssertWithInfo(NULL,key,kde != NULL);
  	// 2.从redisDb中的expire字典中寻找存储了具体过期时间戳的dictEntry，由de指针指向该dictEntry的地址
    de = dictAddOrFind(db->expires,dictGetKey(kde));
  	// 3.更新de所指向的dictEntry中的过期时间
    dictSetSignedIntegerVal(de,when);
		// 4.触发集群间的同步，保证数据一致性
    int writable_slave = server.masterhost && server.repl_slave_ro == 0;
    if (c && writable_slave && !(c->flags & CLIENT_MASTER))
        rememberSlaveKeyWithExpire(db,key);
}

这里为什么要先从具体存储数据的字典中先查找一遍？个人认为是为了保证数据必须真实存储在字典中，因为redis的过期机制（惰性/LFU/LRU）往往需要cpu花费一些时间片去调度，所以在设计上需要尽可能严格的保证资源的不必要浪费。

dictFind是最基础的查询函数：

dictEntry *dictFind(dict *d, const void *key)
{
    dictEntry *he;
    uint64_t h, idx, table;
		// 1.如果两个dictht的used均为0，说明当前既没有数据存储，也没有发生扩容导致的rehash，直接返回NUll。
    if (d->ht[0].used + d->ht[1].used == 0) return NULL; 
  	// 2.如果当前正在发生扩容，则当前线程帮助推进rehash的过程
  	//   这样做的目的，是将rehash的压力分担到各个操作中去（修改/删除/查询）
    if (dictIsRehashing(d)) _dictRehashStep(d);
  	// 3.得到key的hash值
    h = dictHashKey(d, key);
  	// 4.hash值模上hashtable的使用栏位数量，得到一个由dictEntry构成的链表
  	//   依次遍历每一个dictEntry，比较key的值，得到最终的entry
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        while(he) {
            if (key==he->key || dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}

接下来看看dictAddOrFind，这个方法对key进行查找，如果不存在会新增，否则得到原本就存在的dictEntry。是否符合我们expire命令的逻辑？原先testKey不存在expireTime，我们通过命令设置expireTime的过程就是在expire字典中新增一个dictEntry，然后设置它的value为expireTime对应的时间戳：

dictEntry *dictAddOrFind(dict *d, void *key) {
    dictEntry *entry, *existing;
    entry = dictAddRaw(d,key,&existing);
  	//如果entry指针的值存在，说明entry指针指向的dictEntry是通过dictAddRaw新增的，否则返回原本存在的existing地址。
    return entry ? entry : existing;
}

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    long index;
    dictEntry *entry;
    dictht *ht;
		// 1.如果当前正在发生扩容，则当前线程帮助推进rehash的过程
  	//   这样做的目的，是将rehash的压力分担到各个操作中去（修改/删除/查询）
    if (dictIsRehashing(d)) _dictRehashStep(d);

    // 2.如果计算出index为-1，代表原先存在，返回null
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL;

    // 3.1 原先不存在，判断是否处于rehash状态，如果是就将数据存储于第二个hashtable，否则存储于第一个hashtable
  	ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    // 3.2 分配需要的内存，将新的dictEntry插入链表的头部
    entry = zmalloc(sizeof(*entry));
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;

    // 4.为新的dictEntry设置key值
    dictSetKey(d, entry, key);
    return entry;
}

如果觉得不够清晰，可以看一下dictFind的调用时序图：

sequenceDiagram 　　participant dictAddOrFind 　　participant dictAddRaw 　　dictAddOrFind->>dictAddRaw:invoke 　　　　Note OVER dictAddRaw: 判断是否触发_dictRehashStep推进rehash 　　Note OVER dictAddRaw: 计算index，判断是否已存在entry，存在直接返回NULL 　　Note OVER dictAddRaw: 判断是否处于rehash过程，决定存储于哪个hashtable 　　Note OVER dictAddRaw: 分配内存，构造dictEntry，插入链表头部　　Note OVER dictAddRaw: 为新的dictEntry设置key值　　　　dictAddRaw-->>dictAddOrFind:return 　　Note OVER dictAddOrFind: 已存在返回&existing，否则返回dictEntry *entry

4.2 set key value

再来看一个命令：

set name huangzh

这是最基本的添加数据命令，表示我们可以使用该命令创造一个key为name，value为huangzh的dictEntry。那么，从这个命令进入redis-server端的代码，看看它的执行流程：

void setKey(redisDb *db, robj *key, robj *val) {
  	// 1.lookupKeyWrite查找字典中是否存在key，内部实际上仍然调用dictFind基础查询函数
    if (lookupKeyWrite(db,key) == NULL) {
      	// 2.如果当前key在字典中不存在，新增
        dbAdd(db,key,val);
    } else {
      	// 3.如果当前key在字典中存在，覆盖
        dbOverwrite(db,key,val);
    }
  	// 4.value的引用计数+1
    incrRefCount(val);
  	// 5.如果原先db中存在key且配置了expireTime，这一步会直接移除存储old key过期时间的dictEntry
    removeExpire(db,key);
  	// 6.通知watch了该key的客户端
    signalModifiedKey(db,key);
}

这里我们看到了新的类型robj，它的全称是redisObject，事实上，在dictEntry中，存储的key和value时的传参都是用它作为载体：

typedef struct redisObject {
  	// 类型，枚举值，对应了redis支持的所有数据类型
    unsigned type:4;
  	// 编码
    unsigned encoding:4;
  	// 24位存储，用于LRU或是LFU淘汰机制，在后面会专门描述
    unsigned lru:LRU_BITS; 
  	// 当前引用数
    int refcount;
  	// 指向具体值的指针
    void *ptr;
} robj;

回到setKey的主流程，上面说到，如果当前字典不存在key，则调用dbAdd函数进行新增，我们从这里进入内部的实现：

void dbAdd(redisDb *db, robj *key, robj *val) {
  	//sds 全称Simple Dynamic Strings，是redis中提供的简易安全的字符串库
    sds copy = sdsdup(key->ptr);
  	// 调用字典的新增方法
    int retval = dictAdd(db->dict, copy, val);

    serverAssertWithInfo(NULL,key,retval == DICT_OK);
    if (val->type == OBJ_LIST ||
        val->type == OBJ_ZSET)
        signalKeyAsReady(db, key);
    if (server.cluster_enabled) slotToKeyAdd(key);
}

int dictAdd(dict *d, void *key, void *val)
{		
  	//实际新增在这一步，dictAddRaw已经分析过，不做赘述
    dictEntry *entry = dictAddRaw(d,key,NULL);

    if (!entry) return DICT_ERR;
  	//为新增的dictEntry填充value
    dictSetVal(d, entry, val);
    return DICT_OK;
}

这里出现了一个结构体叫做sds，全称Simple Dynamic Strings，是redis提供的字符串高效操作库，不是分析的重点，具体可参考https://github.com/antirez/sds。

可以看到实际调用dictAddRaw函数进行新增的时候，传入的是sds，而在之前已经分析过，dictAddRaw会对新增的dictEntry进行key的填充，所以我们可以得出，其实sds才是key作为存储的数据载体，那么来看一下构造sds的过程：

sds sdsdup(const sds s) {
    return sdsnewlen(s, sdslen(s));
}

sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
  	// 根据初始字符串决定构造的动态字符串类型
    char type = sdsReqType(initlen);
    // 空串判断
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp;

    assert(hdrlen+initlen+1 > initlen); 
  	//分配需要的内存，sds的结构：header的长度+字符串值的初始长度+末尾的空项长度
    sh = s_malloc(hdrlen+initlen+1);
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    if (sh == NULL) return NULL;
    s = (char*)sh+hdrlen;
  	//fp是返回用于读取的实际指针，指向header末尾
    fp = ((unsigned char*)s)-1;
  	//根据不同的类型，构造实际的动态字符串
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
    }
    if (initlen && init)
      	//拷贝字符串的值到新构造的动态字符串
        memcpy(s, init, initlen);
  	//末尾空项补齐
    s[initlen] = '\0';
    return s;
}

最后来看一下不同type对应的动态字符串内部结构，可以看到它们都包含了表示长度的len和存储实际字符的数组buf，sdshdr5比较特殊，因为定位其为空串，所以不需要记录长度：

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; 
    uint8_t alloc; 
    unsigned char flags; 
    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[];
};

接着再回到setKey的主流程，看看removeExpire的内部逻辑：

int removeExpire(redisDb *db, robj *key) {
    serverAssertWithInfo(NULL,key,dictFind(db->dict,key->ptr) != NULL);
  	//从db中的exipre字典删除key对应的dictEntry
    return dictDelete(db->expires,key->ptr) == DICT_OK;
}

int dictDelete(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
}

static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
    uint64_t h, idx;
    dictEntry *he, *prevHe;
    int table;
		//当前没有数据存储，直接返回NULL
    if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;
		//如果当前正在rehash，则触发推进rehash的过程
    if (dictIsRehashing(d)) _dictRehashStep(d);
  	//计算hash值
    h = dictHashKey(d, key);
		
  	//遍历两个hashtable，找到链表中符合key值的dictEntry
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        prevHe = NULL;
        while(he) {
            if (key==he->key || dictCompareKeys(d, key, he->key)) {
                if (prevHe)
                  	//当前节点的前继节点的下一个节点指针直接指向当前节点的后继节点
                    prevHe->next = he->next;
                else
                  	//如果是头节点，则头节点指针改为当前节点的后继节点
                    d->ht[table].table[idx] = he->next;
                if (!nofree) {
                  	//释放内存
                    dictFreeKey(d, he);
                    dictFreeVal(d, he);
                    zfree(he);
                }
              	//hashtable的节点使用数-1
                d->ht[table].used--;
                return he;
            }
            prevHe = he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
  	//如果没命中key，则返回NULL
    return NULL; 
}

那么，来画一个简单的setKey函数执行add key命令时的时序图，省略集群同步和监听通知等步骤后如下：

sequenceDiagram 　　participant setKey 　　participant lookupKeyWrite 　　participant dictFind 　 participant dbAdd 　 participant dictAdd 　　setKey->>lookupKeyWrite:invoke 　　　　lookupKeyWrite->>dictFind:invoke 　　dictFind-->>lookupKeyWrite:return 　　　　lookupKeyWrite-->>setKey:return 　　Note OVER setKey: 判断dictEntry是否存在，不存在就调用dbAdd新增 setKey->>dbAdd:invoke Note OVER dbAdd: 创建sds，装载redisObject中的ptr值 dbAdd->>dictAdd:invoke Note OVER dictAdd: 调用dictAddRaw，创建dictEntry，存入hashtable并填充key值 Note OVER dictAdd: 调用dictSetVal填充value dictAdd-->>dbAdd:return dbAdd-->>setKey:return Note OVER setKey: 调用incrRefCount使value引用计数+1 Note OVER setKey: 调用removeExpire重置expire过期时间

比起一层层深入的跟踪源码，这种时序图能更直观的反应代码执行时的主体流程，也更考验对代码整体逻辑的总结归纳能力。

至此，通过两个简单案例的分析，由浅入深，可以洞悉redis在存储数据时其字典数据结构的全貌：

redis存储数据模型

5. Key对内存的影响

实际上，在redis中，一个key往往需要存储在两个hashtable中，一个是存储data的ht，而另一份则是存储了过期时间戳的ht。也就意味着，如果为一个key设置了expireTime，那么在redis会存在两份key，这使得在一些极端情况不得不考虑key的大小对内存占用的影响。

通过上面的分析，已经知道真正存储key的是sds结构体，但是在转化sds之前，需要先经过dictEntry和redisObject的过渡，也就意味着创建dictEntry和redisObject的内存全部都要计入key的存储范围。

我们以64位编译器为例子，先看redisObject的结构：

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; 
    int refcount;
    void *ptr;
} robj;

64位编译器的void指针占用8个字节，int类型占用4个字节。LRU_BITS为24，即24位3个字节。type4位，encoding4位，合计一个字节。所以构成一个redisObject需要16个字节的容量。

再看dictEntry：

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

针对64位编译器void指针还是8个字节，union里所有的类型均占用8个字节，next为结构体指针，因此在64位编译器中也占用8个字节，因此构成一个dictEntry需要24个字节的容量。

最后我们看sds，这里我们使用上面值为testKey作为例子，首先testKey字符串的长度为七个字节，会被分配到的sds类型结构如下：

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

需要的字节数为1+1+1+7 = 10个字节。

那么，对于调用命令添加一个testKey，所需要的字节总数为16+24+10 = 50。

在设计key的过程中，应当避免key过长。

同时，redis针对这种由于key的字节长度引起的存储容量问题，有着自己的key删除策略和过期淘汰机制。

key删除策略和过期淘汰机制将会在后续的章节中展开分析。