Redis 6.0 源码阅读笔记(3)-概述 Redis 重要数据结构及其 6 种数据类型

女爷i 2023-10-05 09:08 38阅读 0赞

#### 文章目录 ####

*  1. 重要数据结构
 *   *   *  1.1 redisServer
         *  1.2 redisDb
         *  1.3 dict
         *  1.4 dictht
         *  1.5 dictEntry
 *  2. 数据类型
 *   *   *  2.1 Redis 数据对象结构
         *  2.2 Redis 数据类型及其存储结构
         *   *  2.2.1 字符串对象 String
             *  2.2.2 列表对象 List
             *  2.2.3 集合对象 Set
             *  2.2.4 有序集合对象 ZSet
             *  2.2.5 哈希对象 Hash
             *  2.2.6 流对象 Stream

## 1. 重要数据结构 ##

Redis 有许多重要的数据结构，其存储结构从外层往内层依次是 `redisDb`、`dict`、`dictht`、`dictEntry`

> redisDb 默认情况下有16个，每个 redisDb 内部包含一个 dict 的数据结构，dict 内部包含 dictht 数组，数组个数为2，主要用于 hash 扩容使用。dictht 内部包含 dictEntry 的数组，dictEntry 其实就是 hash 表的一个 key-value 节点，如果冲突通过 [链地址法][Link 1] 解决

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUwNTMxMw_size_16_color_FFFFFF_t_70_pic_center]

#### 1.1 redisServer ####

数据结构 `redisServer` 是一个 redis 服务端的抽象，定义在 `server.h` 中。 `redisServer` 中的属性非常多，以下为节选的一部分，简单介绍下

> 1.  `hz`: redis 定时任务触发的频率
> 2.  `*db`: redisDb 数组，默认 16 个 redisDb
> 3.  `*commands`: redis 支持的命令的字典
> 4.  `*el`: redis 事件循环实例
> 5.  `runid[CONFIG_RUN_ID_SIZE+1]`: 当前 redis 实例的 runid

struct redisServer {
        
        /* General */
        pid_t pid;                  /* Main process pid. */
        
        ......
        
        int hz;                     /* serverCron() calls frequency in hertz */
        redisDb *db;
        dict *commands;             /* Command table */
        dict *orig_commands;        /* Command table before command renaming. */
        aeEventLoop *el;
        
        ......
        
        char runid[CONFIG_RUN_ID_SIZE+1];  /* ID always different at every exec. */
        
        ......
        
        list *clients;              /* List of active clients */
        list *clients_to_close;     /* Clients to close asynchronously */
        list *clients_pending_write; /* There is to write or install handler. */
        list *clients_pending_read;  /* Client has pending read socket buffers. */
        list *slaves, *monitors;    /* List of slaves and MONITORs */
        client *current_client;     /* Current client executing the command. */
      
        ......
    };

#### 1.2 redisDb ####

`redisDb` 是 redis 数据库的抽象，定义在 `server.h` 中，比较关键的属性如下

> 1.  `*dict`: 存储数据的字典
> 2.  `*expires`: 存储有过期时间的 key

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

#### 1.3 dict ####

`dict` 是 redis 中的字典，定义在 `dict.h` 文件中，其主要的属性如下

> 1.  `ht[2]`: 哈希表数组，为了扩容方便有 2 个元素，其中一个哈希表正常存储数据，另一个哈希表为空，空哈希表在 rehash 时使用
> 2.  `rehashidx`:rehash 索引，当不在进行 rehash 时，值为 -1

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;

#### 1.4 dictht ####

`dictht` 是哈希表结构，定义在 `dict.h` 文件中，其重要的属性如下

> 1.  `**table`: key-value 键值对节点数组，类似 Java 中的 HashMap 底层数组
> 2.  `size`: 哈希表容量大小
> 3.  `sizemask`: 总是等于 size - 1，用于计算索引值
> 4.  `used`: 哈希表实际存储的 dictEntry 数量

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

#### 1.5 dictEntry ####

`dictEntry` 是 redis 中的 key-value 键值对节点，是实际存储数据的节点，定义在 `dict.h` 文件中，其重要的属性如下

> 1.  `*key`: 键对象，总是一个字符串类型的对象
> 2.  `*val`: 值对象，可能是任意类型的对象
> 3.  `*next`: 尾指针，指向下一个节点

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

## 2. 数据类型 ##

#### 2.1 Redis 数据对象结构 ####

Redis 数据库中所有数据都以 key-value 节点 dictEntry 存储，其中 key 和 value 都是一个 `redisObject` 结构体对象，只不过 key 总是一个字符串类型的对象，value 则可能是任意一种数据类型的对象。 `redisObject` 结构体定义在 `server.h` 中如下所示

> 可以看到该结构体中重要的属性如下，不同的对象具有不同的类型 type，同一个类型的 type 会有不同的存储形式 encoding
> 
> 1.  `type`: 该属性标明了数据对象的类型，比如 String，List 等
> 2.  `encoding`: 这个属性指明了对象底层的存储结构，比如 ZSet 类型对象可能的存储结构有 ZIPLIST 和 SKIPLIST
> 3.  `*ptr`: 指向底层存储结构的指针

typedef struct redisObject {
        
        unsigned type:4;
        unsigned encoding:4;
        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;

#### 2.2 Redis 数据类型及其存储结构 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUwNTMxMw_size_16_color_FFFFFF_t_70_pic_center 1]  
以上为 Redis 中数据类型及其存储结构的关系图示，图中的宏定义在 `server.h` 文件中

/* The actual Redis Object */
    #define OBJ_STRING 0    /* String object. */
    #define OBJ_LIST 1      /* List object. */
    #define OBJ_SET 2       /* Set object. */
    #define OBJ_ZSET 3      /* Sorted set object. */
    #define OBJ_HASH 4      /* Hash object. */
    
    /* The "module" object type is a special one that signals that the object
     * is one directly managed by a Redis module. In this case the value points
     * to a moduleValue struct, which contains the object value (which is only
     * handled by the module itself) and the RedisModuleType struct which lists
     * function pointers in order to serialize, deserialize, AOF-rewrite and
     * free the object.
     *
     * Inside the RDB file, module types are encoded as OBJ_MODULE followed
     * by a 64 bit module type ID, which has a 54 bits module-specific signature
     * in order to dispatch the loading to the right module, plus a 10 bits
     * encoding version. */
    #define OBJ_MODULE 5    /* Module object. */
    #define OBJ_STREAM 6    /* Stream object. */
    
    
    
    /* Objects encoding. Some kind of objects like Strings and Hashes can be
     * internally represented in multiple ways. The 'encoding' field of the object
     * is set to one of this fields for this object. */
    #define OBJ_ENCODING_RAW 0     /* Raw representation */
    #define OBJ_ENCODING_INT 1     /* Encoded as integer */
    #define OBJ_ENCODING_HT 2      /* Encoded as hash table */
    #define OBJ_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
    #define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. */
    #define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
    #define OBJ_ENCODING_INTSET 6  /* Encoded as intset */
    #define OBJ_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
    #define OBJ_ENCODING_EMBSTR 8  /* Embedded sds string encoding */
    #define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of ziplists */
    #define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */

##### 2.2.1 字符串对象 String #####

`OBJ_STRING` 字符串对象底层数据结构一般为简单动态字符串（SDS），但其存储方式可以是 `OBJ_ENCODING_INT`、`OBJ_ENCODING_EMBSTR` 和 `OBJ_ENCODING_RAW`，不同的存储方式代表着对象内存结构的不同

> 1.  `OBJ_ENCODING_INT`  
>     如果保存的字符串长度小于 20 并且可以解析为整数，那么这个整数就会直接保存在 `redisObject` 的 `ptr` 属性里
> 2.  `OBJ_ENCODING_EMBSTR`  
>     长度小于 44 （OBJ\_ENCODING\_EMBSTR\_SIZE\_LIMIT）的字符串将以简单动态字符串（SDS） 的形式存储，但是会使用 malloc 方法一次分配内存，将 redisObject 对象头和 SDS 对象连续存在一起
> 3.  `OBJ_ENCODING_RAW`  
>     字符串将以简单动态字符串（SDS） 的形式存储，需要两次 malloc 分配内存，redisObject 对象头和 SDS 对象在内存地址上一般是不连续的

>  *  在 Redis 中，long、double 类型的浮点数是被封装在字符串对象中再进行存储的
>  *  `OBJ_ENCODING_RAW` 与 `OBJ_ENCODING_EMBSTR` 不同点在于内存分配与释放，raw 需要两次操作，embstr 只需一次，另外由于 embstr 内存块连续，能更好的利用缓存带来的优势
>  *  `OBJ_ENCODING_EMBSTR` 编码的对象是只读的，一旦修改会先转码为`OBJ_ENCODING_RAW`

##### 2.2.2 列表对象 List #####

`OBJ_LIST` 列表对象的底层存储结构有过 3 种实现，分别是 `OBJ_ENCODING_LINKEDLIST`、 `OBJ_ENCODING_ZIPLIST` 和 `OBJ_ENCODING_QUICKLIST`，其中 OBJ\_ENCODING\_LINKEDLIST 在 3.2 版本以后就废弃了

> 1.  `OBJ_ENCODING_LINKEDLIST`  
>     底层采用双端链表实现，每个链表节点都保存了一个字符串对象，在每个字符串对象内保存了一个元素
> 2.  `OBJ_ENCODING_ZIPLIST`  
>     底层实现类似数组，使用特定属性保存整个列表的元信息，如整个列表占用的内存大小，列表保存的数据开始的位置，列表保存的数据的个数等，其保存的数据被封装在 `zlentry`  
>     使用ziplist 需要满足两个条件
>     
>      *  列表对象保存的所有字符串元素的长度小于64字节
>      *  列表对象保存的元素数量小于512个
> 3.  `OBJ_ENCODING_QUICKLIST`  
>     底层采用双端链表结构，不过每个链表节点都保存一个 ziplist，数据存储在 ziplist 中

##### 2.2.3 集合对象 Set #####

`OBJ_SET` 集合对象的底层存储结构有两种，`OBJ_ENCODING_HT` 和 `OBJ_ENCODING_INTSET`

> 1.  `OBJ_ENCODING_INTSET`  
>     集合保存的所有元素都是整数值将会采用这种存储结构，但当集合对象保存的元素数量超过512 (由server.set\_max\_intset\_entries 配置)个后会转化为 OBJ\_ENCODING\_HT
> 2.  `OBJ_ENCODING_HT`  
>     底层为 `dict` 字典，数据作为字典的键保存，键对应的值都是NULL，与 Java 中的 HashSet 类似

##### 2.2.4 有序集合对象 ZSet #####

`OBJ_ZSET` 有序集合对象的存储结构分为 `OBJ_ENCODING_SKIPLIST` 和 `OBJ_ENCODING_ZIPLIST`

> 1.  `OBJ_ENCODING_ZIPLIST`  
>     当 ziplist 作为 zset 的底层存储结构时，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素值，第二个元素保存元素的分值，而且分值小的靠近表头，大的靠近表尾
> 
>  *  有序集合对象使用 ziplist 存储需要同时满足以下两个条件，不满足任意一条件将使用 skiplist
>     
>      *  所有元素长度小于64 (server.zset\_max\_ziplist\_value 配置)字节
>      *  元素个数小于128 (server.zset-max-ziplist-entries 配置)

> 1.  `OBJ_ENCODING_SKIPLIST`  
>     底层实现是跳跃表结合字典。每个跳跃表节点都保存一个集合元素，并按分值从小到大排列，节点的 object 属性保存了元素的值，score属性保存分值；字典的每个键值对保存一个集合元素，元素值包装为字典的键，元素分值保存为字典的值
> 
>  *  `skiplist 同时使用跳跃表和字典实现的原因`
>     
>      *  跳跃表优点是有序，但是查询分值时复杂度为O(logn)；字典查询分值复杂度为O(1) ，但是无序，结合两者可以实现优势互补
>      *  集合的元素成员和分值是共享的，跳跃表和字典通过指针指向同一地址，不会浪费内存

##### 2.2.5 哈希对象 Hash #####

`OBJ_HASH` 的存储结构分为 `OBJ_ENCODING_ZIPLIST` 和 `OBJ_ENCODING_HT`，其实现如下：

> 1.  `OBJ_ENCODING_ZIPLIST`  
>     在以 ziplist 结构存储数据的哈希对象中，key-value 键值对以紧密相连的方式存入压缩链表，先把key放入表尾，再放入value；键值对总是向表尾添加
> 
>  *  哈希对象使用 ziplist 存储数据需要同时满足以下两个条件，不满足任意一个都使用 dict 结构
>     
>      *  所有键值对的键和值的字符串长度都小于64 (server.hash\_max\_ziplist\_value 配置)字节
>      *  键值对数量小于512(server.hash-max-ziplist-entries)个

> 1.  `OBJ_ENCODING_HT`  
>     底层为 `dict` 字典，哈希对象中的每个 key-value 对都使用一个字典键值对`dictEntry`来保存，字典的键和值都是字符串对象

##### 2.2.6 流对象 Stream #####

`OBJ_ENCODING_STREAM` 流对象是 5.0 版本引入的新的数据对象，与列表对象 List 极为相似，但是功能更为强大，带有订阅发布的能力。其采用的存储结构 `OBJ_ENCODING_STREAM` 与其他的存储结构截然不同

> `OBJ_ENCODING_STREAM`  
> 底层使用压缩前缀树(radix tree) 来存储字符串元素，从源文件 `rax.h` 的注释可以知道，radix tree 其实是字典树(Trie tree)的压缩优化版本，它会把多个只有一个子节点的连续节点保存的字符压缩到一个节点中
> 
>  *  Trie Tree 的原理  
>     将每个字符串元素 key 按照单个字符拆分，然后对应到每个分支上。这样从根节点遍历到某个分支的叶节点，所有经过的节点保存的字符拼接出的字符串即为这条分支对应的元素 key

Trie tree ：
     *              (f) ""
     *                \
     *                (o) "f"
     *                  \
     *                  (o) "fo"
     *                    \
     *                  [t   b] "foo"
     *                  /     \
     *         "foot" (e)     (a) "foob"
     *                /         \
     *      "foote" (r)         (r) "fooba"
     *              /             \
     *    "footer" []             [] "foobar"
    
    
    Radix tree:
                       ["foo"] ""
     *                     |
     *                  [t   b] "foo"
     *                  /     \
     *        "foot" ("er")    ("ar") "foob"
     *                 /          \
     *       "footer" []          [] "foobar"

[Link 1]: https://blog.csdn.net/weixin_45505313/article/details/100134493#Reference_hash_37
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUwNTMxMw_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200827130829449.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUwNTMxMw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUwNTMxMw_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/2020082616290159.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUwNTMxMw==,size_16,color_FFFFFF,t_70#pic_center