数据结构与对象

简单动态字符串

简单动态字符串（simple dynamic string,SDS），结构体非常简单

struct sdshdr {
    // 记录 buf 数组中已使用字节的数量
    // 等于 SDS 所保存字符串的长度
    int len;
    // 记录 buf 数组中未使用字节的数量
    int free;
    // 字节数组，用于保存字符串
    char buf[];
};

redis中的key也是通过这种结构进行存储的。

为什么不用普通的c的字符串？

1. 利用SDS可以更快地获取字符串长度，通过len字段。
2. SDS封装了字符串的增添操作，保证了不会出现c字符串的缓冲区溢出情况。
3. c字符串每次变动，都会触发一次内存再分配操作，而SDS利用空间预分配+惰性空间释放的操作，减少再分配的次数。
4. c字符串必须符合某种编码，所以c字符串只能存储文本数据，而SDS由于它的数组属性，可以保存任意形式的二进制数据。
5. SDS还兼容部分C函数操作，因为他在buf的结尾是遵从C语言的字符串结尾\0。

链表

链表的数据结构也很简单

链表结构：

typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点的值
    void *value;
} listNode;

持有结构：

typedef struct list {
    // 表头节点
    listNode *head;
    // 表尾节点
    listNode *tail;
    // 链表所包含的节点数量
    unsigned long len;
    // 节点值复制函数
    void *(*dup)(void *ptr);
    // 节点值释放函数
    void (*free)(void *ptr);
    // 节点值对比函数
    int (*match)(void *ptr, void *key);
} list;

其中dup，free，match是为了实现多态链表所需的类型特定函数。

可以看出这是一个双向链表，其中除了链表键LIST以外，发布与订阅，慢查询，监视器等功能也都用到了链表。

看出其中拥有的特性：双向，无环，带表头指针和表尾指针，带链表长度计数器，多态。

字典

字典是hashmap的底层实现之一，当hash键值对较多或者元素比较长的时候，就会使用hashmap去实现。

字典结构

typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

节点结构

typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

image-20200821155129778

next的存在是用来解决hash冲突的。

持有结构

typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

type封装了各种多态的函数。

typedef struct dictType {
    // 计算哈希值的函数
    unsigned int (*hashFunction)(const void *key);
    // 复制键的函数
    void *(*keyDup)(void *privdata, const void *key);
    // 复制值的函数
    void *(*valDup)(void *privdata, const void *obj);
    // 对比键的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    // 销毁键的函数
    void (*keyDestructor)(void *privdata, void *key);
    // 销毁值的函数
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

可以观察到哈希表是有两个的，通常之后用0号hash表，在 rehash的时候会使用1号hash表。

用的hash算法是MurmurHash。

• 表冲突是怎么解决的？

通过链表，为了速度考虑，程序总会将新节点添加到链表的表头位置。

• rehash的过程

先为ht[1]分配内存，内存大小取决于扩容还是缩容，然后把ht[0]的键值对移动到ht[1]中，然后把ht[1]变成ht[0]。

• 什么时候会触发扩容或者缩容

负载因子 = 保存节点/哈希表大小，当负载因子大于等于1并且服务器没有使用BGSAVE或者BGREWRITEAOF操作，或者大于等于5等时候，触发扩容，如果小于0.1，触发收缩。

• 在rehash的时候，对hash进行CURD操作是怎么样子的？

DUR操作会在两个hash表上进行，而C只会在ht[1]执行。

跳跃表

跳跃表能达到平均O(logN)，最坏O(N)复杂度的节点查找。还可以用顺序操作来批量处理节点。

跳跃表的效率和平衡树相媲美，并且实现更加简单。

在有序集合键，和集群节点中用作内部数据结构。

image-20200821171908838

看起来相当复杂。位于图片最左边的是 zskiplist 结构， 该结构包含以下属性：

• header ：指向跳跃表的表头节点。
• tail ：指向跳跃表的表尾节点。
• level ：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。
• length ：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内）。

位于 zskiplist 结构右方的是四个 zskiplistNode 结构， 该结构包含以下属性：

• 层（level）：节点中用 L1 、 L2 、 L3 等字样标记节点的各个层， L1 代表第一层， L2 代表第二层，以此类推。每个层都带有两个属性：前进指针和跨度。前进指针用于访问位于表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的距离。在上面的图片中，连线上带有数字的箭头就代表前进指针，而那个数字就是跨度。当程序从表头向表尾进行遍历时，访问会沿着层的前进指针进行。
• 后退（backward）指针：节点中用 BW 字样标记节点的后退指针，它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。
• 分值（score）：各个节点中的 1.0 、 2.0 和 3.0 是节点所保存的分值。在跳跃表中，节点按各自所保存的分值从小到大排列。
• 成员对象（obj）：各个节点中的 o1 、 o2 和 o3 是节点所保存的成员对象。

typedef struct zskiplistNode {
       // 后退指针
       struct zskiplistNode *backward;
       // 分值
       double score;
       // 成员对象
       robj *obj;
       // 层
       struct zskiplistLevel {
           // 前进指针
           struct zskiplistNode *forward;
           // 跨度
           unsigned int span;
       } level[];
   } zskiplistNode;

跳跃表的level可以包含多个元素，但是每个节点的level数是随机的，介于1和32之间的值，越高层出现的概率越小。

前进指针是level[i].forward，指向下一个同层级的level，而跨了多长，就是level[i].span。

分值相同的值会按照成员对象在字典序的大小来排序。

整数集合

当一个集合只包含整数值元素，并且元素不多时，会使用整数集合作为集合键的底层实现。

typedef struct intset {
       // 编码方式
       uint32_t encoding;
       // 集合包含的元素数量
       uint32_t length;
       // 保存元素的数组
       int8_t contents[];
   } intset;

contents的int结构取决于encoding属性的值，有16,32,64位三种。里面是按从小到大排序的。

如果插入的数值，不符合encoding的数据类型的时候，会进行升级，这个时候是同步的，所以向整数集合添加新元素的时间复杂度是O（n）。

• 这样的数据结构有什么好处呢？

1. 提升灵活性，将encoding单独设置，可以避免c语言自带的类型检查。
2. 节约内存。

除了升级还能降级。

压缩链表

压缩链表是列表建和哈希键的底层实现之一。如果一个列表键只包含少量的列表项，并且每个列表项要么是小整数型，要嘛就是长度比较短的字符串，那么就会使用压缩链表实现。

image-20200821182936791

属性	类型	长度	用途
zlbytes	uint32_t	4 字节	记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重分配， 或者计算 zlend 的位置时使用。
zltail	uint32_t	4 字节	记录压缩列表表尾节点距离压缩列表的起始地址有多少字节： 通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址。
zllen	uint16_t	2 字节	记录了压缩列表包含的节点数量： 当这个属性的值小于 UINT16_MAX （65535）时， 这个属性的值就是压缩列表包含节点的数量； 当这个值等于 UINT16_MAX 时， 节点的真实数量需要遍历整个压缩列表才能计算得出。
entryX	列表节点	不定	压缩列表包含的各个节点，节点的长度由节点保存的内容决定。
zlend	uint8_t	1 字节	特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端。

压缩链表节点的构成

image-20200824094718937

previous_entry_length：记录了压缩列表中前一个节点的长度。属性的长度可以是 1 字节或者 5 字节

向前遍历就是通过这一个字段实现的。

encoding：记录了节点content属性所保存数据的类型以及长度。

content：节点的值。

连锁更新

由于previous_entry_length的存在，它可能是1字节或者5字节，当变动长度的时候，会导致相关的节点都会变动（有点像区块链？）

对象

redis中的每个对象都是由一个redisObject结构表示。

typedef struct redisObject {
       // 类型
       unsigned type:4;
       // 编码
       unsigned encoding:4;
       // 指向底层实现数据结构的指针
       void *ptr;
       // ...
   } robj;

type ：属性记录了对象的类型，值则可以是字符串对象、列表对象、哈希对象、集合对象或者有序集合对象的其中一种。

类型常量	对象的名称
REDIS_STRING	字符串对象
REDIS_LIST	列表对象
REDIS_HASH	哈希对象
REDIS_SET	集合对象
REDIS_ZSET	有序集合对象

encoding：是对象底层的数据结构。

类型	编码	对象
REDIS_STRING	REDIS_ENCODING_INT	使用整数值实现的字符串对象。
REDIS_STRING	REDIS_ENCODING_EMBSTR	使用 embstr 编码的简单动态字符串实现的字符串对象。
REDIS_STRING	REDIS_ENCODING_RAW	使用简单动态字符串实现的字符串对象。
REDIS_LIST	REDIS_ENCODING_ZIPLIST	使用压缩列表实现的列表对象。
REDIS_LIST	REDIS_ENCODING_LINKEDLIST	使用双端链表实现的列表对象。
REDIS_HASH	REDIS_ENCODING_ZIPLIST	使用压缩列表实现的哈希对象。
REDIS_HASH	REDIS_ENCODING_HT	使用字典实现的哈希对象。
REDIS_SET	REDIS_ENCODING_INTSET	使用整数集合实现的集合对象。
REDIS_SET	REDIS_ENCODING_HT	使用字典实现的集合对象。
REDIS_ZSET	REDIS_ENCODING_ZIPLIST	使用压缩列表实现的有序集合对象。
REDIS_ZSET	REDIS_ENCODING_SKIPLIST	使用跳跃表和字典实现的有序集合对象。

字符串对象

字符串对象的编码可以是 int 、 raw 或者 embstr 。

image-20200824110356790 image-20200824110459966 image-20200824110756553

• raw和embstr之间的区别？

如果字符串对象保存的是一个字符串值， 并且这个字符串值的长度小于等于 39 字节， 那么字符串对象将使用 embstr 编码的方式来保存这个字符串值。raw会调用两次内存分配来分别创建RedisObject和sdshdr结构，而embstr编码则通过一次内存分配来分配一块连续的内存。相比raw，更省内存。但由于是需要连续的内存，字符串太大的情况如果需要经常分配内存，则要带着redisObject一起变动，更难扩展。

三种字符串对象之间会相互转换。

列表对象

列表对象的编码可以是 ziplist 或者 linkedlist 。

image-20200824112457858 image-20200824112515387

当列表对象可以同时满足以下两个条件时， 列表对象使用 ziplist 编码：

1. 列表对象保存的所有字符串元素的长度都小于 64 字节；
2. 列表对象保存的元素数量小于 512 个；

hash对象

哈希对象的编码可以是 ziplist 或者 hashtable 。

当哈希对象可以同时满足以下两个条件时， 哈希对象使用 ziplist 编码：

1. ​ 哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节；
2. ​ 哈希对象保存的键值对数量小于 512 个；

这两个条件的上限值是可以修改的， 利用 hash-max-ziplist-value 选项和 hash-max-ziplist-entries 两个配置。

集合对象

集合对象的编码可以是 intset 或者 hashtable 。

有序集合对象

有序集合的编码可以是 ziplist 或者 skiplist 。

image-20200824113648815

skiplist 编码的有序集合对象使用 zset 结构作为底层实现， 一个 zset 结构同时包含一个字典和一个跳跃表：

typedef struct zset {
       //跳表，ZRANK 、ZRANGE 等命令就是基于跳跃表 API 
       zskiplist *zsl;
       //成员到分值的映射，通过这个字典， 程序可以用 O(1) 复杂度查找给定成员的分值
       dict *dict;
   } zset;

• 为什么有序集合需要同时使用跳跃表和字典来实现？

为了提高性能。

image-20200824114107366

• redis是如何实现特定命令类型检查的。

利用redisObject 结构的 type 属性，在执行命令的时候先检查键的类型是否正常。

引用计数

redis的内存回收是利用引用计数实现的。

typedef struct redisObject {
       // ...
       // 引用计数
       int refcount;
       // ...
   } robj;

如果引用计数的值为0，则内存会被释放。

引用计数属性还带有对象共享的作用。

如果键A和键B共享同个对象，那么这个对象的refcount为2，其它属性没有变化。如果这个值越大，则节约更多的内存。

共享对象不单单只有字符串键可以使用， 那些在数据结构中嵌套了字符串对象的对象（linkedlist 编码的列表对象、 hashtable 编码的哈希对象、 hashtable 编码的集合对象、以及 zset 编码的有序集合对象）都可以使用这些共享对象。

• 为什么Redis不共享包含字符串的对象？

当服务器考虑将一个共享对象设置为键的值对象时， 程序需要先检查给定的共享对象和键想创建的目标对象是否完全相同， 只有在共享对象和目标对象完全相同的情况下， 程序才会将共享对象用作键的值对象， 而一个共享对象保存的值越复杂， 验证共享对象和目标对象是否相同所需的复杂度就会越高， 消耗的 CPU 时间也会越多。

对象中还有lru属性。称空转时长，记录着该对象最后一次被调用的时间，若果内存占用过大，空转时长较高的部分键会释放。