一、RedisObj

• 每个 kv 对，对应以下 dictEntry 结构（dictEntry 表示哈希表节点的结构）

1. *key 指向一个 string 对象

2. *val 指向一个 redisObject 对象

3. *next 执行下一个 dictEntry

• 为便于操作，redis 统一使用了 redisObject 这种结构来代表不同数据类型，数据结构如下

struct redisObject {    unsigned type:4;//对象类型，如：OBJ_STRING、OBJ_LIST、OBJ_HASH、OBJ_SET、OBJ_ZSET    unsigned encoding:4;//当前值对应存储底层编码类型，如：sds、ziplist这些    unsigned lru:LRU_BITS; //清除算法，lru表示当内存超限时采用LRU算法清除内存中的对象（24位，如果是LRU则记录对象最后一次被程序访问的时间（与内存回收相关）    int refcount;//引用计数器，refcount=0表示不再被其他对象引用，可以被垃圾回收机制回收    void *ptr;//真正底层数据结构实现的指针};

其中一个 redisObject 占 16 个字节

二、String 类型结构

• INT 编码格式：键值为 64 位的有符号整数时（8 字节，仅整型浮点数不行），redisObject 底层编码存储如下：

• embstr 编码格式：键值字符串长度少于 39（redis 3.0 版本前）或者字符串长度少于 44（redis 3.2 版本后，sds 结构优化过，占用了更小字节），则 redisObject 底层编码用的是 OBJ_ENCODING_EMBSTR，*ptr 对应结构是 sds

• raw 编码格式：键值字符串长度大于上述情况或者 embstr 的值发生了更新（此时无论长度多少），redisObject 底部编码用 OBJ_ENCODING_RAW）

• embstr 和 rw 区别只是 embstr 存储 redisObject 和 sds 是连续内存空间存储，而 raw 是不连续的

• 为什么引入 sds 而不是用 c 语言自带的 char 数组？

三、Hash 类型结构

ziplist（压缩列表）

当哈希类型元素个数少于 512&每个元素大小于 64 字节时，redis 会用 ziplist 作为其哈希底层存储结构。目的是使用更加 紧凑的结构 实现多个元素的 连续存储，节省内存空间。（hash-max-ziplist-entries 配置（默认 512 个）、同时 所有值 都 小于 hash-max-ziplist-value）

• ziplist 的组成

1. zlbytes：记录整个压缩列表占用的内存字节数（在对压缩列表进行内存重分配或者计算 zlend 的位置时使用）

2. zltail：记录压缩列表尾节点距离起始地址的偏移量（有多少个字节），通过这个偏移量可以快速确定该压缩列表尾节点的地址（无需遍历整个列表）

3. zllen：记录整个压缩列表的节点数量，前提是节点数<65535（UINT16_MAX），如果 zllen=65535，那么该压缩列表的节点数还是要通过遍历来获得

4. entryN：各个节点

5. zlend：结尾标识符 0xFF（只有 1 字节），用于标记列表末端

• entry 的组成

• prevlen：前一 zlentry 的长度，为更节省内存，又区分了 2 种情况，当前一 zlentry 的长度 < 254 时，prevlen 占用 1 字节，而> 254 时，则占用 5 字节。因此会带来级联更新的问题，所以 Redis 7 以后用 listpack 代替了 ziplist

• encoding：记录了当前节点实际数据的类型以及长度

• entry_data：当前节点的实际数据

• 级联更新问题：当前多个相邻节点长度刚好 250-253 之间，刚好前面插入一个节点长度大于等于 254，因此触发 prevlen 由 1 字节变成 5 字节，依次类推，所有后面相邻的 prevlen 都有变化（实际概率很小）

• ziplist VS 链表

占用空间小，链表的指针都要占用不小空间

内存连续访问，比链表的内存不连续访问快

获取总字节数，可以实现 o(1)获取，而链表要遍历

一次性比较难申请比较大的连续内存空间，所以 ziplist 不适合存过多数据

• ziplist 总结

优点：使用连续紧凑的空间存储，通过计算前后节点的长度实现正向反向的偏移访问

缺点：存在级联更新问题，不适应于节点个数过多的情况（类似数组，需要遍历查询数据）

listpack

redis7 后引进，为了解决 ziplist 级联更新问题，结构大体和 ziplist 差不多

listpack 去掉了 prevlen，因此没了级联更新的问题

• 正向遍历

正向遍历时，listpack 首先跳过 6 字节的头部，指针就会指向第一个元素，再根据元素的 encoding 字段得到元素的长度和类型，然后就可以正常访问元素了。再根据 encoding 计算当前元素长度占用的字节数，跳过当前元素占用的字节数，就可以访问下一个元素了，直到访问到结尾符，代表结束。

• 反向遍历

首先访问 listpack 的前 4 字节得到总长度，然后就可以定位到末尾结尾符位置。然后指针左移就可以访问到最后一个元素的长度 len，指针再左移 len 就可以访问最后一个元素的 encoding，根据编码方式访问元素。指针再左移又可以访问到倒数第 2 个元素的长度，以此类推。访问元素长度 len 字段时，有一个关键点，就是如何判断 len 部分结束了。因为 len 可能占用 1 字节，也可能占用多个字节。listpack 的做法是，每个字节只使用 7 Bit，最高位来表示是否还要继续读。

hashtable

• hashtable 组成

• 代码体

typedef struct dict {    // 类型特定函数    dictType *type;    // 私有数据    void *privdata;    // 哈希表  一般情况下， 字典只使用 ht[0] 哈希表，ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。    dictht ht[2];    // rehash 索引，当 rehash 不在进行时，值为 -1    long rehashidx; /* rehashing not in progress if rehashidx == -1 */    // 当前运行的迭代位置    unsigned long iterators; /* number of iterators currently running */} dict;
typedef struct dictType {    // 计算哈希值的函数    uint64_t (*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;
/* This is our hash table structure. Every dictionary has two of this as we * implement incremental rehashing, for the old to the new table. */typedef struct dictht {    // 哈希表数组    dictEntry **table;    // 哈希表大小, 默认为 4    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;        double d;    } v;    // 指向下个哈希表节点，形成链表    struct dictEntry *next;} dictEntry;

• Hash 算法

// 使用字典设置的哈希函数，计算键 key 的哈希值hash = dict -> type -> hashFunction(key)// 使用哈希表的 sizemask 属性和哈希值，计算出索引值(sizemask 为哈希表大小掩码，用于计算索引值，总是等于 size - 1)// 根据情况不同，ht[x]可以是 ht[0]或者 ht[1]index = hash & dict -> ht[x].sizemask

• Hash 冲突

用 next 指针解决，每新增一个冲突的 dictEntry，都添加在头部，而非尾部

• Rehash（扩缩容）

1、负载因子：load_factor = ht[0].used / ht[0].szie

2、扩容条件

• 服务器没有执行 bgsave 或者 bgwriteaof，并且负载因子>=1;

• 务器不管没有执行 bgsave 或者 bgwriteaof，只要负载因子>=5;

3、缩容条件：负载因子<0.1

4、为字典 ht[1]分配空间，空间大小取决于 ht[0]已存在的健值对数量（也就是 ht[0].used 的值）

5、扩容：ht[1]大小为大一个大于等于 ht[0].used*2 的 2 ^ n （2 的 n 次方幂）

6、缩容：ht[1]大小为大一个大于等于 ht[0].used 的 2 ^ n （2 的 n 次方幂）

7、渐进式 rehsh：每次对字典进行增删改查的时候，会将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] ， 当 rehash 工作完成之后， 程序将 rehashidx 属性的值增一

ht[0]迁移 ht[1]完成后，释放 ht[0],会将 ht[1]设置为 ht[0]，并重建 ht[1]

四、List

为保证实现从首、尾操作 list 元素，保证查询效率和低内存占用。

• redis3.2 之前，用 ZipList 和 LinkedList 来实现 List（当列表元素数量小于 512，并且每个元素大小小于 64 个字节时用 ziplist）

• redis3.2 之后，统一采用 quicklist

ziplist

见上述 Hash 类型结构第一点：ziplist(压缩列表)

linkedlist

即普通的双端列表

quicklist

• 组成：本质就是 ziplist 的双向链表，每个 quicklistnode 就是一个 ziplist

这里介绍一下几个重要的变量的含义

• *quicklistNode head ：头结点指针

• *quicklistNode tail ：尾节点指针

• unsigned long count ：节点中所有 entry 的数量之和

• unsigned long len ：节点数量

• int fill : QL_FILL_BITS ：ZipList 中的 entry 数量上限

为了避免 QuickList 中的每个 ZipList 中 entry 过多，Redis 提供了一个配置项：list-max-ziplist-size 来限制，也即 QL_FILL_BITS 的值。

如果值为正，则代表 ZipList 的允许的 entry 个数的最大值

如果值为负，则代表 ZipList 的最大内存大小，分 5 种情况：（其默认值为 -2）

• -1：每个 ZipList 的内存占用不能超过 4kb

  -2：每个 ZipList 的内存占用不能超过 8kb

  -3：每个 ZipList 的内存占用不能超过 16kb

  -4：每个 ZipList 的内存占用不能超过 32kb

  -5：每个 ZipList 的内存占用不能超过 64kb

• unsigned int compress : QL_COMP_BITS：首尾不压缩的节点数量

• 总结

• 结合了链表和 ziplist2 个特性，在尽量减少内存使用的情况下，存在更多的元素（listnode 节点用 ziplist 实现）

• 同时为了查询效率，限制了每个 ziplist 的大小

五、Set

当元素是整数且元素个数小于 512 时为 intset，否则为 hashtable

IntSet

• 组成

• 代码结构

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

• 查询方式一般采用二分查找法，实际查询复杂度也就在 log(n)

HashTable

见上述 Hash 类型结构第三点：hashtable

六、Zset

当元素是元素个数小于 128 且每个元素大小小于 64 字节时为 ziplist 存储，否则为：hashtable + 跳表（skiplist）

ziplist

见上述 Hash 类型结构第一点：ziplist(压缩列表)

跳表（skiplist）

通过分层，从最高层向低层查询，效率提高，其时间复杂度为 logn（类似于二分查找）

dict+skiplist 的最终的存储结构如下：

• 代码结构

• zskiplist 用于保存跳表信息（如头尾节点指针、节点总数和层数等）

typedef struct zskiplist {    struct zskiplistNode *header, *tail; // 头节点和尾节点    unsigned long length;                // 节点数量    int level;                           // 层数} zskiplist;

• zskiplistNode 用于保存跳表单个节点信息

typedef struct zskiplistNode {    robj *obj;                           // 元素值    double score;                        // 分数，用于排序    struct zskiplistNode *backward;      // 后退指针    struct zskiplistLevel {        struct zskiplistNode *forward;   // 前进指针        unsigned long span;              // 跨度    } level[];} zskiplistNode;

• 跳表的插入

• 创建一个新跳跃表节点（随机生成一个介于 1 和 32 之间的值作为 level 数组的大小， 这个大小就是层的“高度”）

• 查找到对应位置，更新前进/后退指针，更新跨度

• 跳表的查找

• 从上层往下层找

• 途中经过多少跨度，实际就是该节点的 rank 排名值

• 跳表的特点

• 插入/删除/搜索 都是 O(logn)的数据结构

• 实现比平衡树简单，查询理论情况下也是接近平衡树

• 层数具有概率性，法保证所有操作都有最优的实时性能

• 存储多层，牺牲空间换时间

七、BitMap

Redis 的 Bitmap，也称为位图，是一种用于存储和处理二进制位（bit）的数据结构。在 Redis 中，Bitmap 不是一种独立的数据类型，而是字符串类型的一种特殊使用方式。通过特定的命令在字符串数据中处理二进制位。由于 Redis 中字符串的最大存储容量为 512 MB，每个字节有 8 位，因此一个字符串最多可以存储 512 * 1024 * 1024 * 8 = 2^32 个位。

• 为了直观展示，我们可以理解成 buf 数组的每个字节用一行表示，每一行有 8 个 bit 位，8 个格子分别表示这个字节中的 8 个 bit 位，如下图所示：