redis源码之dict

大家都知道redis默认是16个db，但是这些db底层的设计结构是什么样的呢？

我们来简单的看一下源码,重要的字段都有所注释

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)  list一些数据结构中用到的阻塞api*/

    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 */

    unsigned long expires_cursor; /* Cursor of the active expire cycle. */

    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */

} redisDb;

redis中的所有kv都是存放在dict中的，dict类型在redis中非常重要。

字典disc的数据结构如下

typedef struct dict {

    dictType *type;  //

    void *privdata;

    dictht ht[2];    //hashtable,每个dict都有两个这样的数据结构，主要用于hash扩容

    long rehashidx; /* rehashing not in progress if rehashidx == -1  rehash的作用  防止链表无限增长*/

    unsigned long iterators; /* number of iterators currently running   遍历记录的一些字段*/

} dict;

redis中当出现hash冲突的时候，我们会采用头插法(链表)的方式来解决，但是链表无限增常的话hashtable会退化，退化成一个链表，影响查询效率，这个时候我们就需要对之前的数组进行扩容，把老的数据搬到新数组上面，这个过程就是rehash

接下来咱们来看看dictType的类型

typedef struct dictType {

    uint64_t (*hashFunction)(const void *key);

    void *(*keyDup)(void *privdata, const void *key);  //key用于数据类型的复制

    void *(*valDup)(void *privdata, const void *obj);  //value用于数据类型的复制

    int (*keyCompare)(void *privdata, const void *key1, const void *key2); //hash冲突的时候需要在冲突的值里面一个一个的对比

    void (*keyDestructor)(void *privdata, void *key);

    void (*valDestructor)(void *privdata, void *obj);

} dictType;

typedef struct dictht {

    dictEntry **table;  //指向数组的首地址  是健值对的核心结构

    unsigned long size;//数组的长度

    unsigned long sizemask; //恒等于size-1

    unsigned long used;

} dictht;

typedef struct  {

    void *key;  //指向SDS的数据结构

    union {  //联合体表示value类型,只会用到一个字段

        void *val;    //指向redis对象 redisObject

        uint64_t u64;

        int64_t s64;

        double d;

    } v;

    struct dictEntry *next;  //头插法解决hash冲突

} dictEntry;

接下来我们看一下内存关系的对应图

typedef struct redisObject {

    unsigned type:4;  //当前对象类型 list  string hash set zset等

    unsigned encoding:4; //redis做的底层优化(编码)

    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or

                            * LFU data (least significant 8 bits frequency

                            * and most significant 16 bits access time). */

    int refcount;

    void *ptr;

} robj;

最后咱们有一张总的图来表是redis的内存关系

encoding存储的优化策略

1:整型编码的处理

我们先来看一个例子

127.0.0.1:6379> set type-int 12345

OK

127.0.0.1:6379> object encoding type-int

"int"

//返回的encoding类型是int

127.0.0.1:6379> set type-int-long 12345678901234567890

OK

127.0.0.1:6379> object encoding type-int-long

"embstr"

//返回的encoding类型是embstr

我们可以发现，在都是数字的时候，如果长度小于20，就会自动转换为int类型，这是redis中专门做的处理

if (len <= 20 && string2l(s, len, &value))

在一个redisObject中，就可以直接用ptr去存储整型值，而不用重新去开辟一块sds的空间

2:redis对象字符串存储相关优化

127.0.0.1:6379> set type-str-short xxx

OK

127.0.0.1:6379> object encoding type-str-short

"embstr"

127.0.0.1:6379> set type-str-long xxxxxxxxxx-xxxxxxxxxx-xxxxxxxxxx-xxxxxxxxxx-x

//字符串长度45

127.0.0.1:6379> object encoding type-str-long

"raw"

127.0.0.1:6379> set type-str-long2 xxxxxxxxxx-xxxxxxxxxx-xxxxxxxxxx-xxxxxxxxxx-

//字符串长度44

127.0.0.1:6379> object encoding type-str-long2

"embstr"

一个redisobject是存在内存中的，cpu在完成一个io的时候，它是怎么来读数据的呢，其实cup的io中有一个缓冲行的概念，在linux系统中，一个缓冲行一般是64个字节

接下来我们看看一个redis对象大概占多大的内存空间，其实我们可以大概算出来。

typedef struct redisObject {

    unsigned type:4;  //4bit

    unsigned encoding:4; //4bit

    unsigned lru:LRU_BITS; //24bit

    int refcount;   //4byte

    void *ptr;   //8byte

} robj;

一个redis对象本身就需要占（4bit+4bit+24bit = 4byte） + 4byte + 8byte = 16byte的大小

这样的话一个缓冲行还剩余48个byte的大小，有点浪费，

48个byte，按照sds的分配策略应该在sdshdr8那个区间中，而sdshdr8本身就需要占3个字节，sds需要兼容c语言的函数库，都会在结尾加上\0，所以sdshdr8本身是占用4个字节，所以一个缓冲行中还剩余44个字节，来存储剩余的数据，所以在redis字符串对象中，当长度小于44的时候，encoding的类型是embstr，没有新开辟一块sds空间

关注我的技术公众号，每周都有优质技术文章推送。

微信扫一扫下方二维码即可关注：

巴特西

redis源码之dict

1:整型编码的处理

2:redis对象字符串存储相关优化

最新文章

热门文章