noSql
redis

redis-类型底层实现原理

1、String

存储类型：

可以用来存储int、float、string

存储实现原理：

redis是KV数据库，最外层是通过Hashtable实现的，我们称为外层的哈希

外层hash的实现：dick.h 47line

1
2
3
4
5
6
7
8
9
10
typedef struct dictEntry {
    void *key; // key 关键字定义
    union {
        void *val; // value 定义
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; //指向下一个键值对节点
} dictEntry;

实际上最外层是redisDb，里面放了dict：server.h 661line

1
2
3
4
5
6
7
8
9
10
11
typedef struct redisDb {
    dict *dict;                 /* 所有的键值对 */
    dict *expires;              /* 设置了过期时间的键值对*/
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP)*/
    dict *ready_keys;           /* Blocked keys that received a PUSH */
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    int id;                     /* Database ID */
    long long avg_ttl;          /* Average TTL, just for stats */
    unsigned long expires_cursor; /* Cursor of the active expire cycle. */
    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;

所以以set hello world 为例，因为key是字符串，redis自己实现了一个字符串类型，叫做SDS，所以hello指向一个SDS

value 是world，同样是一个字符串，但是当value存储一个字符串的时候并没有直接使用SDS存储，而是存在了redisObject中。

实际上五中常用的数据类型都是一样的，value通过redisObject存储，最终RedisObject通过一个指针指向实际的数据结构

redisObject定义：server.h 622

1
2
3
4
5
6
7
typedef struct redisObject {
    unsigned type:4;/*对象类型*/
    unsigned encoding:4; /*具体的数据结构*/
    unsigned lru:LRU_BITS; /*24位，对象最后一次被命令访问的事件，与内存回收有关*/
    int refcount;/*引用计数，为0表示可以回收了*/
    void *ptr; /*指向对象实际的数据*/
} robj;

用type key命令看到的就是type的内容

一个对象有对外展示的类型type，也有对内的编码encoding标明数据的存储结构

内部编码使用命令 object encoding key 就可查看

同样都是string类型，对内有三种编码方式：

  1. int 存储8字节长整型（2^63-1）
  2. embstr 代表embstr格式的SDS，用于存储小于44字节的字符串
  3. raw，存储大于44字节的字符串

问题1、SDS是什么？

Redis中字符串的实现，全称Simple Dynamic String简单动态字符串

源码：sds.h 47

1
2
3
4
5
6
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 长度 */
    uint8_t alloc; /* 总共分配的内存大小 */
    unsigned char flags; /* 当前字符数组的属性，标志是sdshdr8还是sdshdr16等 */
    char buf[];/* 字符串真正的值 */
};

本质上还是数组

sds有多种结构：sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64，用于存储不同长度的字符串。分表表示2^5=32byte，2^8=256byte ……

问题2、为什么redis要使用SDS实现字符串

因为C语言本生没有字符串类型，只能用字符数组char[]实现

  1. 使用字符数组要提前分配足够空间，否则可能溢出
  2. 如果要获取字符串长度，要遍历数组，事件为O(n)
  3. C字串长度变化需要重新内存分配，不能动态扩容
  4. 通过从字串开始到结尾碰到第一个‘\0’来标记字串结束，因此不能保证图片、音频等二进制文件保存的内容，二进制不安全

SDS解决了以上的问题，它具有以下特点：

  • 不担心溢出，能动态扩容
  • 获取长度时间为O(1)
  • 通过“空间预分配”和“惰性空间释放”防止多次重分配内存
  • 判断是否结束的标志是len属性，可以包含‘\0’，（可以继续使用c语言库函数）

问题3、embstr和raw编码的区别？为什么要为不同长度设计不同的编码

embstr的使用只分配一次内存空间（因为RedisObject和SDS是连续的内存）

raw需要两次分配内存，分为RedisObject空间和SDS空间

所以与raw相比，embstr好处在创建时少分配一次空间，删除时少释放一次空间，以及对象所有数据是在连续空间的

而embstr的缺点也很明显，如果字串长度增加需要重新分配内存时，整个redisObject和SDS都需要重新分配空间，因此Redis中的embstr实现为只读（这里的只读是对内存对象而言，对用户来说还是可以写的）

问题4、int和embstr什么时候转化为raw？

1、int 数据不再是整数—raw

2、int大小超出了long的范围—embstr

3、embstr长度超出了44字节—raw

问题5、没有超过44，怎么变成raw了

我们前面说过，对于embstr，由于它的实现是只读的，因此在对embstr对象进行修改时，都会先转化为raw在进行修改

因此，只要是修改过的string类型数据，都是raw编码的

问题6、当长度改变小于44时会还原吗

编码的升级是不可逆的，编码转化只能由小到大

问题7、为什么要对对曾的数据结构使用RedisObject进行一层包装

总结一下：其实无论是设计RedisObject，还是对存储字串设计这么多的SDS，都是为了根据存储不同选择不同的方式进行存储，这样可以尽量节省内存空间和提升查询速度的目的

应用场景：

1、缓存

2、分布式数据共享—session

3、分布式锁

4、全局id—利用INCRBY，利用原子性

5、计数器 – 秒杀场景

2、Hash

2.1 存储类型

用于存储多个无序的键值对，最大存储数量2^32-1(40亿左右)

hash的value只能是字符串，不能嵌套其他类型，比如hash或者list

同样是存储字符串，Hash与String的区别在哪？

  1. 把所有相关的值聚集到一个key中，减少内存空间
  2. 减少Key冲突
  3. 当需要批量获取值的时候，只需要使用一个命令，减少内存/IO/CPU的消耗

Hash不适合的场景

  1. Field 不能单独设置过期时间
  2. 需要考虑数量分布的问题（field非常多的时候，无法分布到多个节点）

2.2 存储实现原理

Redis的Hash本身也是一个KV结构，是不是跟外层的哈希一样使用dicEntry实现呢？

内层hash底层可以使用两种数据结构实现：

ziplist：OBJ_ENCODING_ZIPLIST 压缩列表

hashtable：OBJ_ENCODING_HT 哈希表

同样使用命令 object encoding key 查看

2.2.1 ziplist压缩列表

它是一个经过特殊编码的，有连续内存块组成的双向链表。

它不存储指向上一个链表节点和指向下一个链表节点的指针，而是存储上一个节点的长度和当前节点的长度。这样读写访问可能会慢一些，因为要去计算长度，但是可以节省内存，是时间换空间的思想。

源码ziplist.c 16行的注释

…

zlbytes：压缩列表的字节长度，占4字节，因此压缩列表最长是2^32-1

zltail：压缩列表尾元素相对于压缩列表起始地址的偏移量，占4字节

zllen：压缩列表的元素数目，占2字节，当元素数量超出2字节表示时，通过zllen无法获得压缩列表的元素数量，必须遍历整个压缩列表

entry：压缩列表存储的若干个元素，可以为字节数组或者整数

zlend：压缩列表的结尾符，恒为0XFF

ziplist元素的编码结构

编码有哪些？

1
2
3
4
5
6
7
8
#define ZIP_STR_06B (0 << 6)  // 长度小于等于63字节
#define ZIP_STR_14B (1 << 6)	//长度小于等于16383字节
#define ZIP_STR_32B (2 << 6)  //长度小于等于429496295字节
#define ZIP_INT_16B (0xc0 | 0<<4) 
#define ZIP_INT_32B (0xc0 | 1<<4)
#define ZIP_INT_64B (0xc0 | 2<<4)
#define ZIP_INT_24B (0xc0 | 3<<4)
#define ZIP_INT_8B 0xfe

ziplist详情请见

https://blog.csdn.net/zgaoq/article/details/89710600

https://segmentfault.com/a/1190000017328042

我们最关心的Entry内容 : ziplist.c 271

zlentry是根据一个ziplist元素解析计算出来的结构体，记录了该节点的一些重要信息

1
2
3
4
5
6
7
8
9
typedef struct zlentry {
    unsigned int prevrawlensize; /* 存储上一个链表节点的长度数值需要的字节数*/
    unsigned int prevrawlen;     /* 上一个链表节点占用的长度 */
    unsigned int lensize;        /* 存储当前链表节点长度数值所需要的字节数*/
    unsigned int len;            /* 当前链表节点实际数据占用字节长度 */
    unsigned int headersize;     /* 当前链表节点的头部大小 prevrawlensize + lensize. */
    unsigned char encoding;      /* 编码方式 */
    unsigned char *p;            /*压缩链表以字符串的形式保存，该指针指向当前节点起始位置 */
} zlentry;

根据以上的结构体信息，我们能够得到，节点数据的起始位置为 p + headersize，长度是len

p-prevrawlen 为上一个节点元素的起始位置

基于这种结构，ziplist从后向前遍历会比较合适

hash类型如何使用ziplist

那么，hash类型的数据是怎么使用ziplist存储的呢，

1
2
将同一键值对的两个节点紧挨着保存，保存键的节点在前，保存
值的节点在后，新加入的键值对，放在压缩列表表尾

展开看：

问题：什么时候用ziplist存储

当hash对象同时满足以下两个条件时：

  • hash对象保存的键值对数量小于512个
  • 所有键值对的键和值的字符串长度都小于64字节（一个字母一个字节）

通过查看redis配置文件：redis.conf

1
2
hash-max-ziplist-value 64
hash-max-ziplist-entries 521

超过这两个阈值的任何一个，存储结构就会转换成hashtable

2.2.2 hashtable（dict）

在Redis中，hashtabe被称为字典

前面我们了解到redis的kv结构是通过一个dictEntry实现的

在hashtable中，又对dictEntry进行了多层的封装

源码位置：dict.h 47

首先有一个dictEntry：

1
2
3
4
5
6
7
8
9
10
typedef struct dictEntry {
    void *key; // key 关键字定义
    union {
        void *val; // value 定义
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; //指向下一个键值对节点
} dictEntry;

dictEntry放到了dictht里面，ht再放在dict里面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

从最底层到最高层：dictEentry –> dictht–>dict

这是一个数组+链表的结构

展开一下，hash表的整体存储结构如下：

问题：为什么要定义两个hash表，其中一个不用呢

redis的hash默认使用的是ht[0]，ht[1]不会初始化和分配空间

哈希表dictht使用链地址法来解决碰撞问题的。在这种情况下，哈希表的性能取决于它的大小和它所保存的节点的数量之间的比率

  • 比率在1:1时，哈希表的性能最好
  • 如果节点数量比哈希表的大小要大大很多，那么哈希表回退化成很多个链表，哈希表本省的性能优势就不存在

如果单个哈希表的节点数量过多，哈希表需要扩容，rehash时就需要用到ht[1]

问题：什么时候触发扩容

根据负载因子决定

源码dict.c

1
2
static int dict_can_resize = 1;
static unsigned int dict_force_resize_ratio = 5;

扩容判断和扩容的操作大家可以自己看一下，跟hashMap一样，也有缩容

应用场景

string可以做的，hash也都可以做

存储对象类型的数据 key-id field-field value-value

购物车 key-uid field-商品id value-商品数量

3、List

存储类型

存储有序的字符串，元素可以重复。最大存储数量2^32-1（40亿左右）。

存储实现原理

在早期版本中，数据量较小时用ziplist存储，达到临界值时转换为linkedlist进行存储，分别对应OBJ_ENCODING_ZIPLIST 和 OBJ_ENCODING_LINKEDLIST

3.2版本之后统一用quicklist来存储。quicklist存储了一个双向链表，每个节点都是一个ziplist，所以它是ziplist和linkedlist的结合体。

使用 object encoding key 来查看

quicklist

先看总体结构

redis-db-quicklist

源码位置：quicklist.h 105行

1
2
3
4
5
6
7
8
9
10
typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* 所有的ziplist一共存了多少元素 */
    unsigned long len;          /* 双向链表的长度 */
    int fill : QL_FILL_BITS;              /* ziplist最大大小 */
    unsigned int compress : QL_COMP_BITS; /* 压缩深度 */
    unsigned int bookmark_count: QL_BM_BITS;/* 4位，bookmark数组大小 */
    quicklistBookmark bookmarks[];/* bookmark是一个可选字段，quicklist重新分配内存空间时使用，不使用不占空间 */
} quicklist;

redis.config相关参数：

list-max-ziplist-size：整数表示单个ziplist最多包含的entry个数，负数代表单个ziplist的大小，默认8k，-1 4K,-2 8k,-3 16k …

list-compress-depth：默认是0，1表示首位的ziplist不压缩；2表示收尾第一第二个ziplist不压缩，以此类推。

节点quicklistNode源码在quicklist.h 46行

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

总结一下：quicklist就是一个数组+链表的结构

应用场景：主要用于存储有序内容的场景

  • 用户的消息列表

  • 网站的公告列表

  • 活动列表

  • 博客的文章列表

  • 评论列表等

  • 还可以当做分布式环境的队列或者栈使用

4、Set

存储类型：无序集合

存储原理

redis 用intset或hashtable存储set。如果元素都是整型，就用inset

inset.h 35line

1
2
3
4
5
typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

如果不是整数类型，就用hashtable（数组+链表）

如果元素个数超过了512个，也会用hashtable，这与一个配置有关

1
set-max-intset-entries 512

问题：set的key没有value，怎么用hashtable存储？

value存null

应用场景：

  • 抽奖
  • 点赞、签到、打卡
  • 商品标签
  • 商品筛选
  • 用户关注（共同好友），推荐

5、Zset

存储类型

Sorted set存储有序的元素，每个元素有个score，按照score从小到大排名

score相同，按照key的ACSII码排序

存储原理

默认使用ziplist编码

在ziplist内部，按照Score排序递增来存储，插入的时候要移动之后的数据。

如果元素数量大于等于128个，或者任一member长度大于64字节，使用skiplist+dict存储

1
2
zset-max-ziplist-entries 128
zset-max-ziplist-value 64

什么是skiplist

先来看一下有序链表：

这样的链表中要查询数据需要从前往后遍历比较，时间复杂度为O(n)，插入亦然。

加入我们没相邻两个节点增加一个执政，让指针指向下一个节点（或者理解为有三个元素进入了第二层）

这样所有新增的指针连成了一个新链表

问：哪些元素会进入到第二层？

见源码t_zset.c 122行

现在查数据时，可以先沿着新链表查找，碰到比待查数大的节点，进入下一层

在这个查找过程中，由于新增的指针，我们不需要逐个节点去比较，需要比较的节点数大概只有原来的一半。

为什么不用AVL树或者红黑树？因为skiplist更加简洁

且level是随机的，得到的skiplist可能是这样的：

应用场景

顺序会动态变化的列表

  • 排行榜

6、Hyperloglogs

提供了一种不太精确的基数统计方法，用来统计一个集中不重复的元素个数，比如统计网站的UV，或者应用的日活，越活，存在一定误差

在redis实现的HyperLogLog，只需要12k内存就能统计2^64个数据。

7、GEO

8、Streams

5.0版本推出的数据类型，支持多波的可持久化的消息队列，用于实现发布订阅功能，借鉴了kafka的设计。

tips

这里介绍一下在网上看到的源码阅读方法（摘自redis源码解析）。

  • 自底向上：从耦合关系最小的模块开始读，然后逐渐过度到关系紧密的模块。就好像写程序的测试一样，先从单元测试开始，然后才到功能测试。
  • 从功能入手：通过文件名（模块名）和函数名，快速定位到一个功能的具体实现，然后追踪整个实现的运作流程，从而了解该功能的实现方式。
  • 自顶向下：从程序的 main() 函数，或者某个特别大的调用者函数为入口，以深度优先或者广度优先的方式阅读它的源码。

另外，按照黄健宏老师《如何阅读 Redis 源码？》一文中介绍的redis阅读方法，基本上可以将上述文件进行合理的拆分，以便于对其进行一一攻破。

按照上图对Redis源码的模块划分，初步确定一下源码的学习路线如下：

第一阶段

  • 阅读Redis的数据结构部分，基本位于如下文件中：内存分配 zmalloc.c和zmalloc.h
  • 动态字符串 sds.h和sds.c
  • 双端链表 adlist.c和adlist.h
  • 字典 dict.h和dict.c
  • 跳跃表 server.h文件里面关于zskiplist结构和zskiplistNode结构，以及t_zset.c中所有zsl开头的函数，比如 zslCreate、zslInsert、zslDeleteNode等等。
  • 基数统计 hyperloglog.c 中的 hllhdr 结构， 以及所有以 hll 开头的函数

第二阶段 熟悉Redis的内存编码结构

  • 整数集合数据结构 intset.h和intset.c
  • 压缩列表数据结构 ziplist.h和ziplist.c

第三阶段 熟悉Redis数据类型的实现

  • 对象系统 object.c
  • 字符串键 t_string.c
  • 列表建 t_list.c
  • 散列键 t_hash.c
  • 集合键 t_set.c
  • 有序集合键 t_zset.c中除 zsl 开头的函数之外的所有函数
  • HyperLogLog键 hyperloglog.c中所有以pf开头的函数

第四阶段 熟悉Redis数据库的实现

  • 数据库实现 redis.h文件中的redisDb结构，以及db.c文件
  • 通知功能 notify.c
  • RDB持久化 rdb.c
  • AOF持久化 aof.c

以及一些独立功能模块的实现

  • 发布和订阅 redis.h文件的pubsubPattern结构，以及pubsub.c文件
  • 事务 redis.h文件的multiState结构以及multiCmd结构，multi.c文件

第五阶段 熟悉客户端和服务器端的代码实现

  • 事件处理模块 ae.c/ae_epoll.c/ae_evport.c/ae_kqueue.c/ae_select.c
  • 网路链接库 anet.c和networking.c
  • 服务器端 redis.c
  • 客户端 redis-cli.c
  • 这个时候可以阅读下面的独立功能模块的代码实现
  • lua脚本 scripting.c
  • 慢查询 slowlog.c
  • 监视 monitor.c

第六阶段 这一阶段主要是熟悉Redis多机部分的代码实现

  • 复制功能 replication.c
  • Redis Sentinel sentinel.c
  • 集群 cluster.c

其他代码文件介绍

关于测试方面的文件有：

  • memtest.c 内存检测
  • redis_benchmark.c 用于redis性能测试的实现。
  • redis_check_aof.c 用于更新日志检查的实现。
  • redis_check_dump.c 用于本地数据库检查的实现。
  • testhelp.c 一个C风格的小型测试框架。

一些工具类的文件如下：

  • bitops.c GETBIT、SETBIT 等二进制位操作命令的实现
  • debug.c 用于调试时使用
  • endianconv.c 高低位转换，不同系统，高低位顺序不同
  • help.h 辅助于命令的提示信息
  • lzf_c.c 压缩算法系列
  • lzf_d.c 压缩算法系列
  • rand.c 用于产生随机数
  • release.c 用于发布时使用
  • sha1.c sha加密算法的实现
  • util.c 通用工具方法
  • crc64.c 循环冗余校验
  • sort.c SORT命令的实现
  • 一些封装类的代码实现：
  • bio.c background I/O的意思，开启后台线程用的
  • latency.c 延迟类
  • migrate.c 命令迁移类，包括命令的还原迁移等
  • pqsort.c 排序算法类
  • rio.c redis定义的一个I/O类
  • syncio.c 用于同步Socket和文件I/O操作

整个Redis的源码分类大体上如上所述了，接下来就按照既定的几个阶段一一去分析Redis这款如此优秀的源代码吧！