引言

上一篇文章详解了Redis网络层的实现，网络层与具体功能实现无关，却是单线程高性能的关键。

这篇文章主要聊聊Redis具体功能数据结构的实现，主要针对常用的五种数据结构，string，hash，list，set和zset的实现。

在Redis源码走马观花（2）配置解析中我曾经提到过，在redis.c:180中存储了Redis支持所有的指令及其实现函数：

struct redisCommand redisCommandTable[] = {
    {"get",getCommand,2,"r",0,NULL,1,1,1,0,0},
    {"set",setCommand,-3,"wm",0,NULL,1,1,1,0,0},
    {"setnx",setnxCommand,3,"wm",0,NULL,1,1,1,0,0},
    //...
}

第二个属性就是指令的具体实现函数，进入该函数即可阅读相应的指令的具体实现。

在调用具体的命令执行函数前，命令就被拆成一个个参数存放到相应的redisClient.argv中了，比如Redis命令set aaa "aaa"会被拆成数组{"set", "aaa", "aaa"}放在redisClient.argv中。

Redis数据库的真身

redisClient结构体中有一个db字段，它是redisDb类型，这个就是该redisClient目前选中的数据库，不论是哪种数据类型，都会调用setKey函数将自己设置进数据库中：

void setKey(redisDb *db, robj *key, robj *val) {

    // 添加或覆写数据库中的键值对
    if (lookupKeyWrite(db,key) == NULL) {
        dbAdd(db,key,val);
    } else {
        dbOverwrite(db,key,val);
    }

    //...
}

void dbAdd(redisDb *db, robj *key, robj *val) {

    //....
    int retval = dictAdd(db->dict, copy, val);

    //...
 }

发现其实就是在往redisDb的dict字典中加入kv，之前在第二章提到过，dict就是Redis自己实现的字典结构，其实现类似于高级语言中的hashmap，可见一个Redis数据库本质就是一个大字典，当你创建的不同的数据结构时，本质上都是在往这个大字典中写入kv。从setKey的签名可以看出，这个大字典中的每一个key和value都是robj类型，这是个什么东西呢？

redisObject

robj其实是redisObject的简称：

typedef struct redisObject {

    // 类型
    unsigned type:4;   // 4 bit 位域

    // 编码 （底层数据结构类型）
    unsigned encoding:4;

    // 对象最后一次被访问的时间
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */

    // 引用计数
    int refcount;

    // 指向实际值的指针  指向底层实现数据结构
    void *ptr;

} robj;

类型type代表了该robj对用户暴露的类型，就是引言中说的五种类型：

数据类型	type的值
string	REDIS_STRING
list	REDIS_LIST
hash	REDIS_HASH
set	REDIS_SET
zset	REDIS_ZSET

而encoding代表底层实际使用的数据结构类型，而具体的底层数据结构实现存储在ptr字段中。

底层数据结构

底层数据结构是指不对用户暴露，仅仅作为底层实现的一些数据结构，Redis有如下的底层数据结构：

long：就是C语言中普通的long类型，当字符串可以编码成long类型的数字时，会采用这种结构
sds：在第二章提到过，它就是Redis中的字符串类型
- 所有的key的底层数据结构都是它
- 字符串的底层数据结构，根据其内存摆放特点又有两种
  - raw：普通的sds
  - embstr：内存中位置紧跟在相应的redisObject后面，可以和redisObject一起分配与释放
dict：在第二章提到过，是Redis自己实现字典，除了用于实现Redis内部的功能外，还用于hash和set的底层数据结构
ziplist：在内存中连续排列的一个列表结构，可以存储字符串或者数字，和别的结构不一样的地方是，在代码中没有具体的结构体来表示，只有一些宏可以从代表ziplist的byte串取得具体属性的值，redis.c:246。
- 是list, hash和zset数据结构的默认实现
- 虽然是一个紧凑的数据结构，但却无法像数组一样随机访问，各种操作的时间复杂度和链表类似，在查询时需要一个一个元素往下走
- 该编码相对比较复杂，网上有很多文章讲解，这里就不专门介绍了
list：Redis自己实现的一个双向链表，可用于list的底层数据结构
intset：整数集合，其实就是个从小到大排列的整数数组，如果set中所有的元素都是数字的话，可以用于set的底层数据结构
skiplist：跳表，可以和dict一起用于zset的底层数据结构，其中dict用于按成员取分值，而skiplist负责按分值取成员。

下面逐一通过图示五种数据结构是如何在上面这7种底层数据结构中作选择的。

string

set msg "hello"
set number 12235

redis-string

hash

hset o1 f1 "aaa"

redis-hash

list

lpush languages python

redis-list

set

sadd names "Lily"

redis-set

zset

zadd page_rank 10 google.com

redis-set

在使用ziplist作为底层数据结构时，score是以字符串的形式编码在里面，具体为什么要这么做，我也比较困惑，ziplist本身是支持存数字的。

这个skiplist + dict的结构其实是zset结构体：

typedef struct zset {

    // 字典，键为成员，值为分值
    // 用于支持 O(1) 复杂度的按成员取分值操作
    dict *dict;

    // 跳跃表，按分值排序成员
    // 用于支持平均复杂度为 O(log N) 的按分值定位成员操作
    // 以及范围操作
    zskiplist *zsl;

} zset;

其中dict主要用于支持像zscore这样的按成员取分值的操作，而zsl跳跃表主要用于支持像zrange这样的按照分数取成员的操作。

End

下一篇文章专门研究一下hyperloglog的实现。