本文非教学文，仅做知识点速览之用

目录

前言Redis的表层类型与底层类型学习目标 底层数据结构动态字符串——SDS特性执行效率 双向链表——list&listNode特性执行效率 跳跃表——zskipList&zskipListNode特性执行效率 字典——dick&dictht&dictEntry特性执行效率 压缩列表——zipList特性执行效率 整数集合——intset特性执行效率 表层对象StringListSetZSetHashMap多态内存回收

前言

Redis的表层类型与底层类型

为了提高读写性能，在不同的数据类型、数据量的情况下，需要使用不同的存储、管理方式。为了提升服务器吞吐率的同时，又能保证redis的易用性。redis 区分了底层数据结构与redis对象的关系。例如：HashMap数据量较少时，底层以ziplist结构存储而非dict；set为纯整数集合时，使用intset而非dict，诸如此类。在这里，分开总结底层实现的数据结构和表层对象，最后再梳理总结他们之间的关系。以期理清redis数据类型的实现原理，这对于在日常开发中，保障涉及redis交互的代码的运行效率至关重要。

学习目标

了解不同对象的数据结构及其使用场景了解不同数据结构之间转换的时机及其效率了解不同数据结构执行不同了解redis数据回收机制及其可能带来的影响

底层数据结构

动态字符串——SDS

特性

本质是动态字符数组空字符 '\0' 不计入已使用字节数，也不计入未使用字节数采用空间预分配+惰性释放策略修改后 小于 1 MB 时，预分配空间等于已使用空间；大于 1 MB 时，预分配空间为 1 MB惰性释放即不主动释放，但有sds有提供释放内存的api二进制安全。不以 '\0' 标记字符串结束，而以 len 标记在实现中，SDS除了独立存在，在Redis对象中，也会嵌套至其他类型中，以实现特定Redis对象（如dict用sds存具体元素值，实现hash map） 内存溢出：使用了未被分配的空间内存泄漏：已分配空间不再被使用，但未释放申请内存空间是慢操作：存在用户态与内核态的切换和外部资源调度（堆栈的换出换入；内存申请等。内存调度速度远慢于cpu计算速度）可能是为了进一步提升redis内存利用率。从redis 3.2 开始，将原本的sdshdr结构体进一步拆分为 sdshdr5; sdshdr8; sdshdr16; sdshdr32; sdshdr64 用于存储不同长度的字符串。其中 sdshdr5 在其源码注释说表明永远不会被使用

执行效率

字符串长度获取是 O(1) —— 直接读取sds结构体成员变量清除字符串(sdsclear) 是 O(1) —— 直接执行 len = 0，并未重置各元素值释放内存空间 (sdsfree) 是 O(n) —— n 是已申请的内存空间。注意与 sdsclear 区分 redis/src/sds.hredis/src/sds.c

双向链表——list&listNode

特性

多态：listNode 使用void *存储值。不同类型的dup; match; free 方法通过具体的宏 listSet<Xxx>Method 设置list 结构体包含长度和首尾指针

执行效率

前驱后继相关操作都是O(1)——获取前驱/后继、插入节点、删除给定节点需要查找单个节点的操作都是 O(n)——根据值获取节点、根据index获取节点、删除节点等 redis/src/adlist.hredis/src/adlist.c

跳跃表——zskipList&zskipListNode

特性

结构体中直接包含首尾指针、长度和最大层数每个节点包含 1 个后退指针每个节点基于 power law 生成范围 [1, 32] 个前进指针节点成员按照分值大小排序每个节点成员对象唯一

执行效率

redis/src/server.hredis/src/t_zset.c

字典——dick&dictht&dictEntry

特性

哈希算法采用 murmursh2/3。计算hash值后，&sizemask 决定键值对的位置。采用单向链表解决冲突负载因子大于1或0.5(触发RDB)时，会扩容并rehash，小于0.1时会收缩空间并rehashdict用数组存了两个hash table 指针 dictht[0]、dictht[1]，用于灰度执行rehashrehash过程中旧数据 dictht[0] 只减不增，具体迁移过程分到各个CRUD过程中。通过rehashidx计数当前rehash进度rehash期间，RUD操作会先后访问两张表

执行效率

删除特定键值对(Delete)操作是 O(1)，释放所有键值对是 O(n)CRUD 操作都是 O(1)随机返回键值对也是 O(1) redis/src/dict.hredis/src/dict.credis 使用的 MurmurHash 函数族及测试套件：aappleby/smhasher

压缩列表——zipList

特性

是一段连续的存储空间存储末尾节点的偏移量首部4字节记录整个ziplist占用总字节数用0xFF标记zipList结束

对于每个节点

首部 1 或 5 个字节记录了前驱的字节长度前驱小于 254 字节时，当前节点首字节存储前驱长度。否则，首字节为 0xFE 并以后续 4 个字节记录前驱长度

执行效率

前驱/后继相关操作为O(1) —— 基于偏移量计算前驱/后继位置获取zipList总占用字节数是O(1) —— 于zipList首部4字节存储获取zipList总节点数最好情况是O(1)，最坏情况是O(n) —— 节点数量大于65535查找的最好情况的O(n) —— 整数，最坏情况是O(n^2) —— 字节数组插入、创建、删除的最好情况是O(n)，最坏情况是O(n^2) —— 可能触发连锁更新

整数集合——intset

特性

直接用线性表存储，可能为 int16[]、int32[]、int64[]新增整数超出当前类型表示范围时，会触发升级操作。新元素只会在头部（过小）或尾部（过大）不存在降级操作（注意与dict的实现区分，dict负载因子小于0.1时会触发收缩并rehash）

执行效率

添加或删除新元素是O(n)整数数组的查找过程可以用折半查找，O(log n)获取字节数和元素个数都是O(1)，这点注意与zipList区分

表层对象

前文介绍了Redis主要的数据结构，而在具体实现中。对于String、List、Set、ZSet和HashMap实际上是Redis对象。Redis定义了RedisObject结构体，其中包含了一个 void *ptr 用于指向具体的数据结构。在不同的条件下，同一的对象也可能用不同的数据结构存储和管理（即，同类的RedisObject，其ptr成员变量指向了不同的数据结构）。接下来，就针对不同的RedisObject 简要概述。 RedisObject 定义：

typedef struct redisObject { unsigned type:4; unsigned encoding:4; unsigned lru:LRU_BITS; int refcount; void *ptr; } robj;

String

条件存储方式<= 32ByteembStr> 32ByteSDS整数，可以用long表示int(long) 浮点数也是用embStr或SDS存储对int类型的 INCRBYFLOAT 操作会触发类型转换

所谓的 embStr 就是用一段连续的存储空间同时存储redisObject和SDS结构。与SDS关键差别在于：SDS需要执行两次内存申请，而embStr只需要一次。

List

条件存储方式所有元素长度 < list-max-ziplist-value(Byte) && 元素数量 < list-max-ziplist-entries(Byte)zipList其他linkedList

Set

条件存储方式所有元素都可以用long int表示 && 元素数量 < set-max-intset-entries(Byte)intset其他dict

ZSet

条件存储方式所有元素长度 < zset-max-ziplist-value && 元素数量 < zset-max-ziplist-entries(Byte)zipList其他skipList + dict

数据量多时，使用两种不同的结构 skipList， dict 存储同一份数据。有利于查找效率保持O(1)的同时，排序相关操作（ZRANGE、ZRANK）保持O(n)

HashMap

条件存储方式所有元素长度 < zset-max-ziplist-value && 元素数量 < zset-max-ziplist-entries(Byte)zipList其他dict 在zipList中，key也是zipList的元素，key所在元素与value所在元素总是紧紧挨在一起key和value都作为StringObject存储，关于StringObject 的存储特性，参考本篇关于 String 对象的描述

多态

Redis的多态基于类型检查、编码方式检查实现。使得同一命令可以对不同的Redis对象、编码方式执行相应操作

Redis通过类型检查，判断某个命令能否对指定键执行 比如，DEL能对所有类型执行，而GET只能对String执行Redis通过检查编码方式encoding，判断对某个Redis对象用什么办法执行特定操作（如HashMap对象，其结构体中包含encoding成员变量，指明当前结构为 zipList 还是 dict

内存回收

Redis的GC与 PHP的GC核心思想基本一致：

在Redis对象中增加 refcount 成员变量作为引用计数新对象的引用计数为 1新增饮用+1，不再被使用-1为0时立即释放

回收函数参考 redis/src/object.c 的 decrRefCount 方法

但除此之外，Redis还通过LRU管理Redis对象，可以看到前文所属RedisObject 结构体中定义了 unsigned lru:LRU_BITS; 用于记录最后一次访问时间。当Redis已用内存达到 maxmemory 时。lru小的（越长时间未被使用），将被优先释放。

这提醒我们，为了避免数据丢失，除了保证Redis服务器硬件层面正常运行，还需要采取以下措施：

保证存储空间不被占满——非高峰时段，保持Redis内存占用在30%以下，是比较合适的对于需要持久化的数据，应该及时执行持久化操作，并有相应日志、监控、告警机制，避免未被持久化的数据丢失负载均衡——可以用Redis-Cluster或其他中间件处理