theme: juejin

前言

上篇文章【Redis】数据类型、操作、使用场景，通过源码我们知道，这些数据类型的底层是RedisObject，话不多说，一起研究Redis的底层实现。

RedisObject是什么

redisObject是Redis数据库系统中用来表示和管理各种数据类型的底层核心数据结构。

是对Redis中存储的各种数据类型（如字符串、列表、集合、哈希表、有序集合等）进行抽象和封装的基础数据结构。

为什么要设计RedisObject

1. 统一对象管理
2. 内存优化
3. 操作一致性
4. 编码优化
5. 元数据存储

RedisObject数据结构

/* 
* Redis 对象 
*/
typedef struct redisObject { 

    // 当前值对象的数据类型 
    unsigned type:4;

    // 当前值对象底层存储的编码类型
    unsigned encoding:4;

    // 清除算法
    // LRU - 24位, 记录最末一次访问时间（相对于lru_clock）; 或者 LFU（最少使用的数据：8位频率，16位访问时间）
    unsigned lru:LRU_BITS;
    
    // 对象的引用计数
    int refcount;
    
    // 指向底层数据结构的指针
    void *ptr;
} robj;

type：当前值对象的数据类型

#define OBJ_STRING 0 // 字符串 
#define OBJ_LIST 1 // 列表 
#define OBJ_SET 2 // 集合 
#define OBJ_ZSET 3 // 有序集 
#define OBJ_HASH 4 // 哈希表

encoding:当前值对象底层存储的编码类型

// 原始编码 SDS
#define OBJ_ENCODING_RAW 0   /* Raw representation */
// 整型编码
#define OBJ_ENCODING_INT 1     /* Encoded as integer */
// 哈希表编码
#define OBJ_ENCODING_HT 2      /* Encoded as hash table */
// 压缩字典编码  版本2.6后不再使用
#define OBJ_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
// 链表编码  不再使用、旧版本2.x中String的底层之一
#define OBJ_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */
// 压缩链表编码
#define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
// 整数集合编码
#define OBJ_ENCODING_INTSET 6  /* Encoded as intset */
// 跳跃表编码
#define OBJ_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
// EMBSTR编码字符串
#define OBJ_ENCODING_EMBSTR 8  /* Embedded sds string encoding */
// quicklist编码
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of ziplists */
// 前缀压缩树（radix tree）
#define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */

ptr：指针，指向实际保存值的数据结构，由type和encoding属性决定。

举个栗子， 如果一个redisObject的type属性为OBJ_LIST， encoding 属性为OBJ_ENCODING_QUICKLIST，那么这个对象就是一个Redis列表（List)，它的值保存在一个QuickList的数据结构内，而ptr指针就指向quicklist的对象；

redisObject、数据类型、编码类型、底层数据结构之间关系

lru：记录对象最后一次被命令程序访问的时间

服务器回收内存的算法为volatile-lru或者allkeys-lru并且占用的内存数超过了maxmemory选项所设置的上限值时，lru时间较久的的那部分键会优先被服务器回收。 较

recount:引用计数器

对象的引用计数，计数达到0，就回收这个对象。

Redis命令处理

底层数据结构

简单动态字符串SDS

Redis 是用 C 语言写的，但是对于Redis的字符串，却不是 C 语言中的字符串（即以空字符’\0’结尾的字符数组），它是自己构建了一种名为 简单动态字符串（simple dynamic string,SDS）的抽象类型，并将 SDS 作为 Redis的默认字符串表示。

SDS：用于存储二进制数据的一种结构，具有动态扩容的特点。SDS有5种header类型，目的是为了让不同的字符串使用不同长度的header，从而节省内存。

struct __attribute__ ((__packed__)) sdshdr64 {
    //记录buf数组中已使用的字节数量
    uint64_t len; 
    //分配的buf数组长度，不包括头和空字符结尾 
    uint64_t alloc;
    // 标志位， 最低3位表示类型，另外5个位没有使用
    unsigned char flags; 
    // 用来保存字符串每个元素的数组
    char buf[];
};

既然Redis是用c语言实现的，为什么不使用c语言字符串，而使用SDS？

压缩列表 - ZipList

ziplist是为了提高存储效率而设计的一种特殊编码的双向链表。它可以存储字符串或者整数，存储整数时是采用整数的二进制而不是字符串形式存储。

ziplist结构

zlbytes：存储的是整个ziplist所占用的字节数。

zktail：指的是ziplist中最后一个entry的偏移量，用于快速定位最后一个entry，以快速完成pop等操作。

zllen：整个ziplist中entry的数量。

zlend：终止字节。

Entry结构

prevlen：前一个entry大小。

encoding：entry的类型长度，不同情况下值不同。

entry-data：存储entry的数据（如果是int类型，则没有此结构，数据直接存储在encoding中）。

为什么ZipList特别省内存

ziplist节省内存是相对于普通的list来说的，如果是普通的数组，那么它每个元素占用的内存是一样的且取决于最大的那个元素（很明显它是需要预留空间的）；

ziplist的缺点

1、ziplist不预留内存空间,每次写操作都会进行内存分配操作。 2、结点如果扩容, 导致结点占用的内存增长, 可能会导致链式反应:最坏情况下, 第一个结点的扩容, 会导致整个ziplist表中的后续所有结点的entry.prevlen字段扩容。

快表

quickList是一种以ziplist为结点的双端链表结构. 宏观上, quicklist是一个链表, 微观上, 链表中的每个结点都是一个ziplist。

字典/哈希表

哈希表结构结构：

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

哈希表是由数组 table 组成，table 中每个元素都是指向 dict.h/dictEntry 结构，dictEntry 结构定义如下：

typedef struct dictEntry{
     //键
     void *key;
     //值
     union{
          void *val;
          uint64_tu64;
          int64_ts64;
     }v;
 
     //指向下一个哈希表节点，形成链表（链地址法）
     struct dictEntry *next;
}

key 用来保存键，val 属性用来保存值，值可以是一个指针，也可以是uint64_t整数，也可以是int64_t整数。

扩容和收缩

1、如果执行扩展操作，会基于原哈希表创建一个大小等于 ht[0].used*2n 的哈希表（也就是每次扩展都是根据原哈希表已使用的空间扩大一倍创建另一个哈希表）。相反如果执行的是收缩操作，每次收缩是根据已使用空间缩小一倍创建一个新的哈希表。

2、重新利用哈希算法，计算索引值，然后将键值对放到新的哈希表位置上。

3、所有键值对都迁徙完毕后，释放原哈希表的内存空间。

渐进式 rehash

如果要一次性的进行rehash，势必会造成Redis一段时间内不能进行别的操作。渐进式rehash期间，字典的删除查找更新等操作可能会在两个哈希表上进行，第一个哈希表没有找到，就会去第二个哈希表上进行查找。但是进行增加操作，一定是在新的哈希表上进行的。

zipmap

dict作为字典结构, 优点很多, 扩展性强悍, 支持平滑扩容等等, 但对于字典中的键值均为二进制数据, 且长度都很小时, dict的中的一坨指针会浪费不少内存, 因此Redis又实现了一个轻量级的字典, 即zipmap.

zipmap适合使用的场合是:

键值对量不大, 单个键, 单个值长度小 键值均是二进制数据, 而不是复合结构或复杂结构. dict支持各种嵌套, 字典本身并不持有数据, 而仅持有数据的指针. 但zipmap是直接持有数据的。zipmap的内存布局就是一块连续的内存空间。

zipmap结构

整数集

整数集合（intset）是集合类型的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis 就会使用整数集合作为集合键的底层实现。

首先看源码结构

typedef struct intset {
    // 编码方式 取值有三个：INTSET_ENC_INT16, INTSET_ENC_INT32, INTSET_ENC_INT64
    uint32_t encoding;
    // 存储整数个数
    uint32_t length;
    // 实际存储数值的数组
    int8_t contents[];
} intset;

跳表

有序列表（Zset）底层数据结构。跳跃表的性能可以保证在查找，删除，添加等操作的时候在对数期望时间内完成，这个性能是可以和平衡树来相比较的，而且在实现方面比平衡树要优雅，这就是跳跃表的长处。跳跃表的缺点就是需要的存储空间比较大，属于利用空间来换取时间的数据结构。

为什么不用平衡树或者哈希表？

1、简而言之就是实现简单且达到了类似效果。

2、可以范围查找

总结

本文是Redis系列的第二篇，这个系列会系统全面的梳理Redis的知识体系，如果有遗漏或者错误，欢迎留言沟通交流。

如果你都看到这了，点赞支持弥金吧。