Redis的5种数据类型与编码结构分析

太过爱你忘了你带给我的痛 2022-03-11 06:30 187阅读 0赞

### 一、概述 ###

*  Redis作为一个分布式缓存实现，相对于Memecache，除了支持持久化之外，一个重要的特性是Redis支持丰富的数据类型，即Memecache只支持字符串类型，所有键值对都是字符串类型，而Redis的值支持字符串，列表，字典，集合，有序集合五种类型，故可以提供更加丰富的操作。
 *  Redis的每种数据类型都支持多种底层数据结构实现，即每种数据类型并不是绑定为一种数据结构的，而是可以多种。这种设计的原因是：Redis是一种内存数据库，所有数据都保存在内存中，故在设计时，需要在保证性能的前提下，尽可能的减少内存消耗，在内存和性能之间进行一个平衡，从而可以存储更多的数据。所以在介绍数据类型之前，先介绍一下Redis底层的数据结构。

### 二、数据结构 ###

#### 简单动态字符串 ####

*  Redis是使用C语言编写的，Redis没有直接使用C语言的字符串实现，而是基于C语言的字符串实现了简单动态字符串。其主要原因是C的字符串是底层的API，存在以下问题：（1）没有记录字符串长度，故需要O(n)复杂度获取字符串长度；（2）由于没有记录字符串长度，故容易出现缓冲区溢出问题；（3）每次对字符串拓容都需要使用系统调用，没有预留空间（4）C的字符串只能保存字符。
 *  基于以上问题，Redis的简单动态字符串提供了：（1）通过len记录字符串长度，实现O(1)复杂度获取；（2）内部字符串数组预留了空间，减少字符串的内存重分配次数，同时实现了自动拓容避免缓冲区溢出问题；（3）内部字符数组基于字节来保存数据，故可以保存字符和二进制数据。具体数据结构设计如下：
    
        struct __attribute__ ((__packed__)) sdshdr64 { 
            // 已使用字符串长度
            uint64_t len; /* used */
            // 一共分配了多少字节，alloc - len就是预留的
            uint64_t alloc; /* excluding the header and null terminator */
            unsigned char flags; /* 3 lsb of type, 5 unused bits */
            // 字节数组
            char buf[];
        };

#### 双向链表 ####

*  C语言没有提供双向链表的实现，故Redis自身实现了一个双向链表，主要用于存放列表数据。具体数据结构如下：
 *  链表节点定义：
    
        typedef struct listNode { 
            // 前置节点
            struct listNode *prev;
            // 后置节点
            struct listNode *next;
            // 数据，使用void指针实现多态，即可以存放多种数据类型的数据
            void *value;
        } listNode;
 *  链表定义：
    
        typedef struct list { 
            // 链表头指针
            listNode *head;
            // 链表尾指针
            listNode *tail;
            void *(*dup)(void *ptr);
            void (*free)(void *ptr);
            int (*match)(void *ptr, void *key);
            // 链表长度
            unsigned long len;
        } list;

#### 链式哈希字典 ####

*  Redis的哈希表实现为链式哈希，即冲突节点使用链表来维护，具体数据结构如下：
 *  哈希链表节点：
    
        // 哈希链表节点
        typedef struct dictEntry { 
            // 键key
            void *key;
            union { 
                // 值value
                void *val;
                uint64_t u64;
                int64_t s64;
                double d;
            } v;
        
            // 下一个链表节点
            struct dictEntry *next;
        } dictEntry;
 *  链式哈希表实现：
    
        // 链式哈希表实现
        typedef struct dictht { 
            // 链式哈希实现
            dictEntry **table;
            // 哈希表元素个数
            unsigned long size;
            // 哈希掩码，用于基于&与运算来计算哈希索引，大小总是为size -1
            unsigned long sizemask;
            unsigned long used;
        } dictht;
 *  Redis哈希结构：
    
        typedef struct dict { 
            dictType *type;
            void *privdata;
            // 两个哈希表，其中一个空着在rehash的时候使用
            dictht ht[2];
            long rehashidx; /* rehashing not in progress if rehashidx == -1 */
            unsigned long iterators; /* number of iterators currently running */
        } dict;

#### 压缩列表ziplist ####

*  压缩列表主要是基于节省内存的目标设计的，是由一些特殊编码的连续内存块组成的顺序型数据结构。
 *  当列表元素较少且元素类型都是小整数或者比较短的字符串时，使用压缩列表来存储。因为压缩列表的数据存取一般是需要遍历，即线性O(n)时间复杂度，但是元素较少时，不会造成性能问题，类似于常量O(1)时间复杂度了。
 *  压缩列表的整体结构如下：主要包括了列表总字节数zlbytes，列表尾节点距离列表起始地址多少个字节数zltail，列表总元素个数zllen，列表元素数据节点entry（图片均引自黄建宏的《Redis设计与实现》）  
    ![在这里插入图片描述][20190307145205199.png]
 *  元素列表的元素节点：每个节点都包含了前一个节点的大小，从而基于当前元素的位置计算前一个节点的位置实现遍历；encoding表示content所保存的值的数据类型和长度，content为具体的值。  
    ![在这里插入图片描述][20190307145403165.png]
    
        /* We use this function to receive information about a ziplist entry. * Note that this is not how the data is actually encoded, is just what we * get filled by a function in order to operate more easily. */
        typedef struct zlentry { 
            unsigned int prevrawlensize; /* Bytes used to encode the previos entry len*/
            unsigned int prevrawlen;     /* Previous entry len. */
            unsigned int lensize;        /* Bytes used to encode this entry type/len. For example strings have a 1, 2 or 5 bytes header. Integers always use a single byte.*/
            unsigned int len;            /* Bytes used to represent the actual entry. For strings this is just the string length while for integers it is 1, 2, 3, 4, 8 or 0 (for 4 bit immediate) depending on the number range. */
            unsigned int headersize;     /* prevrawlensize + lensize. */
            unsigned char encoding;      /* Set to ZIP_STR_* or ZIP_INT_* depending on the entry encoding. However for 4 bits immediate integers this can assume a range of values and must be range-checked. */
            unsigned char *p;            /* Pointer to the very start of the entry, that is, this points to prev-entry-len field. */
        } zlentry;

#### 整数集合intset ####

*  整数集合是集合的一种数据结构，当集合只存在整数元素且集合元素个数不多时，使用这种数据结构。
 *  具体数据结构定义如下：
    
        typedef struct intset { 
            uint32_t encoding;
            uint32_t length;
            // 整数元素集合，类型为int8整数
            int8_t contents[];
        } intset;

#### 跳跃表skiplist ####

*  跳跃表是一种特殊的链表结构，在每个链表节点包含了指向其他链表节点的指针，故可以快速访问其他链表节点，而不需要顺序遍历，实现了通过空间换时间的方法来优化性能。跳跃表的读写平均复杂度为O(logN)，故树结构差不多，不过结构比树结构简单。
 *  在Redis中，跳跃表主要用于实现有序集合zset，每个链表节点包含了成员对象和分数。从头结点到尾节点，以分值从小到大的升序排序。
 *  跳跃表定义：
    
        typedef struct zskiplist { 
            // 跳跃表的头结点和尾节点
            struct zskiplistNode *header, *tail;
            // 链表节点总个数
            unsigned long length;
            // 层的个数
            int level;
        } zskiplist;
 *  跳跃表节点定义：
    
        typedef struct zskiplistNode { 
            // 成员对象
            sds ele;
            // 分数
            double score;
            // 后置节点
            struct zskiplistNode *backward;
            // 层级
            struct zskiplistLevel { 
                // forward指针，执行下一层的某个节点
                struct zskiplistNode *forward;
                // forward指针对应的节点相对当前节点的层的跨度
                unsigned int span;
            } level[];
        } zskiplistNode;
 *  结构示意图：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMTM1NzM_size_16_color_FFFFFF_t_70]

### 三、数据类型 ###

*  以下数据类型为提供给应用程序使用的，在底层实现中使用以上的一种或者多种数据结构进行编码。
 *  对应每个键key可以使用TYPE命令查看其值的数据类型，使用OBJECT ENCODING来查查底层的编码类型，如下：
    
        127.0.0.1:6379> set test 123
        OK
        127.0.0.1:6379> type test
        string
        127.0.0.1:6379> object encoding test
        "int"
        127.0.0.1:6379>

#### 字符串string ####

*  在Redis中，对应整数类型，如果不超过C语言long类型的范围，则使用long类型来存储，如果超过则使用embstr或者raw字符串来存储；对应字符串和浮点数统一使用embstr或raw字符串来存储。
 *  int：可以使用long类型来保存的整数。
 *  embstr：字符串的字节数小于等于32时，使用embstr来编码，注意无法使用long类型来保存的整数，浮点数在Redis中都是使用字符串来存储的，如果遇到计算命令，如incrby递增，则Redis在读出该字符串后，先转换为相应的整数或浮点数进行计算。
 *  raw：embstr无法存储的字符串，即字节数大于32个字节的，则使用raw来编码。
 *  embstr和raw编码一样，都是用于存储字符串，embstr是对raw在存储短字符时的一种优化。不同的是embstr主要用于存放短字符串，在内存分配方面使用一次内存分配来创建数据类型string在Redis内部对应的对象redisObject和用于存储数据的简单动态字符串sds，而raw由于需要分配较大的sds，故使用两次内存分配分别创建以上两个对象。

#### 列表list ####

*  列表主要用于存放多个相同或不同的元素，在底层编码方面也存在压缩列表和双向链表两种数据结构。
 *  选择规则：列表中的所保存的字符串元素的长度都小于64个字节，且列表中元素个数小于512个时，使用压缩列表，否则使用双向链表。
 *  以上为默认规则，其中切换临界点：字符串长度和列表元素个数可以在配置文件redis.conf中通过list-max-ziplist-value，list-max-ziplist-entries来修改。

#### 字典hash ####

*  字典主要用于存放键值对数据，在底层编码也存在压缩列表和链式哈希表两种数据结构。
 *  选择规则：哈希对象的键和值的字符串长度都小于64字节且所有哈希对象个数小于512个，则使用压缩列表，否则使用链式哈希表。
 *  以上为默认规则，也可以通过redis.conf中的hash-max-ziplist-value和hash-max-ziplist-entries参数来修改。

#### 集合set ####

*  集合set是一个存放无重复元素的集合，在底层编码方面存在整数集合和链式哈希表两种数据结构。
 *  选择规则：集合中所有元素均为整数值（具体为int8）且元素个数不超过512个，则使用整数集合intset，否则使用链式哈希表。
 *  以上为默认规则，其中512的可以在redis.conf中通过set-max-intset-entries参数来修改。

#### 有序集合zset ####

*  有序集合主要实现了通过分数score来排序的功能，其中score可以重复，成员对象member不能重复，即有序是面向分数score的，集合是面向成员对象member的。
 *  在底层编码也存在压缩列表和跳跃表两种数据结构。
 *  选择规则：有序集合元素个数少于128个且每个元素的成员对象member的长度都小于64个字节，则使用压缩列表，否则使用跳跃表。
 *  以上规则可以在redis.conf中通过zset-max-ziplist-entires和zset-max-ziplist-value来修改。

### 四、编码降级 ###

*  除了字符串的值可以在int，embstr，raw之间切换之外（字符串类型对于SET命令其实是一个新的对象了），其他类型，即压缩列表，整数集合intset和其他数据结构之间是不能降级的，如对于集合set，值从整数集合inset升级为链式哈希表之后，在删除元素时，不能再降级为整数集合，如下：
    
        127.0.0.1:6379> sadd set2 1
        (integer) 1
        127.0.0.1:6379> object encoding set2
        "intset"
        
        // 添加hello字符串从整数集合intset升级为hashtable
        127.0.0.1:6379> sadd set2 hello
        (integer) 1
        127.0.0.1:6379> object encoding set2
        "hashtable"
        
        // 移除hello之后，集合只存在1这一个整数，集合不会降级为整数集合intset
        127.0.0.1:6379> srem set2 hello
        (integer) 1
        127.0.0.1:6379> smembers set2
        1) "1"
        127.0.0.1:6379> object encoding set2
        "hashtable"

[20190307145205199.png]: /images/20220311/1dbdafc787544ddf925ed7ae06a88fc6.png
[20190307145403165.png]: /images/20220311/4b23ebc80e3242b087566318e95014fb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMTM1NzM_size_16_color_FFFFFF_t_70]: /images/20220311/e8b6887301e247bfa7d5fb0cea46d211.png