【后端面经-数据库】Redis数据结构和底层数据类型-526互联

声明：Redis的相关知识是面试的一大热门知识点，同时也是一个庞大的体系，所涉及的知识点非常多，如果用一篇文章罗列，往往会陷入知识海洋中无法感知其全貌，因此，这段时间我会试着拆分Redis的相关章节，辅以思维导图的形式介绍Redis的相关知识点，知识点范围包括如下几部分

Redis基本概念和特点
Redis数据结构和底层数据类型
Redis持久化（AOF和RDB）
Redis集群和高可用性
Redis缓存
Redis分布式锁
Redis实现异步队列
Redis运维问题

今天主要介绍的是Redis数据结构和底层数据类型

1. Redis数据类型

在之前的Redis基本概念讲解中，我们知道Redis的存储单位是键值对。
其中，键key只能是字符串类型，而值value则支持丰富的数据类型，包括基本数据类型和特殊数据类型。

1.1 基本数据类型

1. string

字符串类型，容量大小不超过512MB。主要存储内容为三类：

字符串：普通字符串 or 复杂的字符串（JSON/XML等）；
数字：整数 or 浮点数；
二进制文件：图片、视频、音频等。

应用场景：缓存、计数器、session共享等。

相关命令：

set key value：根据key查找指定键，设置值为value
get key：根据key查找指定键，获得其存储的value值
del key：根据key查找指定键，删除其存储的value值
incr key：根据key查找指定键，将其存储的value值自增1
decr key：根据key查找指定键，将其存储的value值自减1
incrby key amount：根据key查找指定键，将其存储的value值自增amount
decrby key amount: 根据key查找指定键，将其存储的value值自减amount

2. hash

之前我们提到过Redis的存储单位是键值对，hash指的是值本身又是一个键值对。
应用场景：缓存、存储对象信息等。

相关命令：
- hset key field value：根据key查找指定键，这个键的值是一个哈希表，添加键值对field:value
- hget key field：根据key查找指定键，这个键的值是一个哈希表，获取键field对应的值
- hgetall key：根据key查找指定键，这个键的值是一个哈希表，获取哈希表中所有的键值对
- hdel key field：根据key查找指定键，这个键的值是一个哈希表，删除键field对应的键值对

3. list

在Redis中使用双端链表实现list，列表的插入和删除可以引申出栈、队列等特殊的数据结构。
应用场景：消息队列、时间列表等。

相关命令：

lpush key value：根据key查找指定键，这个键的值是一个列表，把value值插入到列表的左端（左端push）
rpush key value：根据key查找指定键，这个键的值是一个列表，把value值插入到列表的右端（右端push）
lpop key：根据key查找指定键，获得键的对应值是一个列表，将列表的左侧首元素弹出
rpop key：根据key查找指定键，获得键的对应值是一个列表，将列表的右侧首元素弹出
lrange key start end：根据key查找指定键，获得键的对应值是一个列表，获取列表中指定范围的元素
lindex key index：根据key查找指定键，获得键的对应值是一个列表，获取列表中指定索引的元素，支持负数下标表示倒数第x个元素。

4. set

通过哈希表实现set，不允许重复元素。
应用场景：共同好友、共同关注等。

相关命令：

sadd key value：根据key查找指定键，这个键的值是一个集合，把value值插入到集合中
scard key：根据key查找指定键，获得键的对应值是一个集合，获取集合中元素的个数
smembers key：根据key查找指定键，获得键的对应值是一个集合，获取集合中所有元素
sismember key member：根据key查找指定键，获得键的对应值是一个集合，判断member是否在集合中

5. sortset/Zset

通过压缩列表或者跳跃表实现Zset，在第二部分会讲到。Zset不允许重复元素，但是每个元素都会关联一个double类型的分数，表示权重。元素本身不能重复，但是double类型的分数可以重复。Zset中的成员，根据分数从小到大排序。
应用场景：排行榜、带权重的消息队列等。

相关命令：

zadd zset-key score member：根据key查找指定键，这个键的值是一个有序集合，把member值插入到集合中，同时关联一个double类型的分数score
zrange zset-key start end：根据key查找指定键，获得键的对应值是一个有序集合，获取集合中指定范围的元素
zrem zset-key member：根据key查找指定键，获得键的对应值是一个有序集合，删除集合中指定的元素

1.2 特殊数据类型

1. bitmap

位图数据结构，操作二进制位进行记录，每一位都只有0·1两种状态，可以节省存储空间。
应用场景：统计用户的签到情况、统计用户的在线情况等。（今日已签/未签、今日在线/不在线）。

相关命令：

setbit key offset value：根据key查找指定键，设置指定偏移量位置的值为value
getbit key offset：根据key查找指定键，获得指定偏移量位置存储的value值
bitcount key [start end]：根据key查找指定键，在值所对应的的位图中，统计指定范围内的二进制位中1的个数

2. hyperloglog

拥有基数统计的数据结构，基数指的是集合中去掉重复数字之后的元素个数。基数统计指的是在误差允许范围内估算一组数据的基数，而不需要对数据进行全量统计。这样做的好处就是可以节省大量的内存空间。
应用场景：统计网站的UV（独立访客）、注册ip数、在线用户数、共同好友数等等

相关命令：

PFADD key element [element ...]：根据key查找指定键，这个键的值是一个基数统计的数据结构，添加元素到基数统计的数据结构中
PFCOUNT key ：根据key值查找指定键，统计指定键对应的基数统计的数据结构中的基数。
PFCOUNT key [key ...]：根据key值查找指定键，统计多个键对应集合的并集，对这个集合中的元素统计其基数。
PFMERGE destkey sourcekey [sourcekey ...]：根据key值查找指定键，将多个键对应集合的并集，并集存储在destkey对应的值中。

3. GEO

本身是使用zset实现的，存储的是经纬度信息，可以用来计算两个地理位置之间的距离。
应用场景：地图检索的相关场景

相关命令：

geoadd key longitude latitude member [longitude latitude member ...]：查找key对应的指定键，这个键的值是一个GEO类型，添加相关地理位置信息（经度longitude 维度latitude 成员名member）到数据结构中。
geopos key member [member ...]：查找key对应的指定键，这个键的值是一个GEO类型，获取指定成员的经纬度信息。
geodist key member1 member2 [unit]：查找key对应的指定键，这个键的值是一个GEO类型，获取两个成员之间的距离。
GEORADIUS key longitude latitude radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [ASC|DESC] [COUNT count]：查找key对应的指定键，这个键的值是一个GEO类型，以给定的经纬度为圆心，半径为radis，单位为（m米|km千米|ft英尺|mi英里）查找该范围内的位置元素。
- WITHCOORD：将位置元素的经纬度也一并返回
- WITHDIST：将位置元素与中心之间的距离也一并返回
- WITHHASH：将位置元素的geohash值也一并返回
- ASC：根据中心的位置，按照从近到远的顺序返回位置元素
- DESC：根据中心的位置，按照从远到近的顺序返回位置元素
- COUNT：限制返回的位置元素数量，从而减少带宽

4. stream

Stream这个数据结构，乍一看很像是文件读写时产生的流，但是实际上，这个数据结构和消息队列的实现有关。
Redis中消息队列的实现方式为发布订阅pub/sub，但是无法记录历史信息，而Stream支持消息持久化和主备到。
Redis中Stream的数据结构如下所示：

其中：

consumer group:消费组，一个消费组可以有多个消费者
last_delivered_id:每个消费组所拥有的游标，组内每个消费者读取信息之后，游标都会向前移动。
pending_ids:每个消费组内部，每个消费者的状态变量，记录当前已经被客户端读取但是尚未收到确认信息ack的字符
stream的应用场景和消息队列的实现是绑定的。

2. Redis底层数据类型

2.1 简介

在前文中，我们了解到Redis的基本存储单位是键值对，其中value部分支持丰富的数据类型，包括五个基本类型以及Bitmap、hyberloglog、geo、stream等特殊类型，不同的数据类型有不同的使用场景，因此Redis的功能十分强大。而这些丰富的数据类型，每个对象都是有两部分组成的：

对象结构redisObject
对应编码的数据结构
Redis 底层数据类型和数据结构的映射关系如下图所示：

而Redis为什么要多此一举，在实现数据类型之后，又要另外构建一套底层数据结构呢？
在之前的介绍中，我们介绍了很多相关的命令，其中很多都是基于键查找值对象，而有的命令是某个值对象特有的，例如LPUSH和LLEN等只用于列表，SADD只作用于集合，因此，为了方便这些命令的执行，需要让每个键都带有类型信息，从而让程序选择合适的处理方式。
简单来说，就是Redis相关操作命令的多态性决定了Redis需要底层数据结构的支持。

2.2 动态字符串SDS

存储二进制数据的动态扩容字符串，整体由三部分组成：

头部sdshdr:
- 具体包括四种头部，如下图所示：
- 其中，len表示字符串的长度，flags表示头部的类型，使用最后三位，alloc表示头部和\0之外的字节数
数据buf
\0

和C语言中的字符串相比，SDS的优势在于：

常数复杂度获取字符串长度：读取len参数即可获得字符串长度，时间复杂度为O(1)。
动态分配避免缓冲区溢出：SDS在进行字符修改的时候，先根据len检查内存空间是否满足，如果不足会进行内存扩展
减少修改字符串时带来的内存重分配次数：SDS在进行字符修改的时候，当字符串长度增加时，会预分配更多的内存空间（分配后长度小于1M，增加所需长度的两倍；分配后长度大于1M，则增加1M空间），减少内存重分配次数；当字符串长度减少的时候，不会立刻进行内存重新分配，二十使用alloc记录字节数，供后续使用
二进制安全：SDS可以存储二进制数据，而C语言中的字符串只能存储文本数据，因此SDS是二进制安全的
兼容C语言字符串：SDS以\0结尾，因此可以使用C语言字符串的大部分函数，例如strlen、strcat、strcpy等

2.3 快表QuickList

是一种双向链表，节点为ziplist(压缩链表)的形式：
这里定义了6个结构体:

quicklistNode, 宏观上, quicklist是一个链表, 这个结构描述的就是链表中的结点. 它通过zl字段持有底层的ziplist. 简单来讲, 它描述了一个ziplist实例
quicklistLZF, ziplist是一段连续的内存, 用LZ4算法压缩后, 就可以包装成一个quicklistLZF结构. 是否压缩quicklist中的每个ziplist实例是一个可配置项. 若这个配置项是开启的, 那么quicklistNode.zl字段指向的就不是一个ziplist实例, 而是一个压缩后的quicklistLZF实例
quicklistBookmark, 在quicklist尾部增加的一个书签，它只有在大量节点的多余内存使用量可以忽略不计的情况且确实需要分批迭代它们，才会被使用。当不使用它们时，它们不会增加任何内存开销。
quicklist. 这就是一个双链表的定义. head, tail分别指向头尾指针. len代表链表中的结点. count指的是整个quicklist中的所有ziplist中的entry的数目. fill字段影响着每个链表结点中ziplist的最大占用空间, compress影响着是否要对每个ziplist以LZ4算法进行进一步压缩以更节省内存空间.
quicklistIter是一个迭代器
quicklistEntry是对ziplist中的entry概念的封装. quicklist作为一个封装良好的数据结构, 不希望使用者感知到其内部的实现, 所以需要把ziplist.entry的概念重新包装一下

2.4 字典Dict

是一种哈希表，使用链地址法解决哈希冲突。
如图展示的是内存的分配情况：

table是一个数组，每个元素都是一个数值存放节点。
每个节点都是一个dictEntry结构体，其中key和value都是一个指针，指向实际存储的数据。
源代码如下所示：

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_tu64;
          int64_ts64;
     }v;
 
     //指向下一个哈希表节点，形成链表
     struct dictEntry *next;
}dictEntry

2.5 跳跃表ZSipList

跳跃表实际应用中主要作为有序列表使用，但是性能比一般的有序列表更优。
源码定义如下所示：

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

设计思路为：
头节点不持有任何数据, 且其level[]的长度为32
每个结点包括如下几个字段：

ele字段，持有数据，是sds类型
score字段, 其标示着结点的得分, 结点之间凭借得分来判断先后顺序, 跳跃表中的结点按结点的得分升序排列.
backward指针, 这是原版跳跃表中所没有的. 该指针指向结点的前一个紧邻结点.
level字段, 用以记录所有结点(除过头节点外)；每个结点中最多持有32个zskiplistLevel结构. 实际数量在结点创建时, 按幂次定律随机生成(不超过32).
每个zskiplistLevel中有两个字段
forward字段指向比自己得分高的某个结点(不一定是紧邻的), 并且, 若当前zskiplistLevel实例在level[]中的索引为X, 则其forward字段指向的结点, 其level[]字段的容量至少是X+1. 这也是上图中, 为什么forward指针总是画的水平的原因.
span字段代表forward字段指向的结点, 距离当前结点的距离. 紧邻的两个结点之间的距离定义为1.

和平衡树、哈希表等元素相比，跳跃表需要更大的存储空间，打死你性能更优；在范围查找上有相当的优势，且插入和删除更简单，算法实现也更容易。

2.6 整数集合IntSet

encoding 表示编码方式，的取值有三个：INTSET_ENC_INT16, INTSET_ENC_INT32, INTSET_ENC_INT64
length 代表其中存储的整数的个数
contents 指向实际存储数值的连续内存区域, 就是一个数组；整数集合的每个元素都是 contents 数组的一个数组项（item），各个项在数组中按值得大小从小到大有序排序，且数组中不包含任何重复项。（虽然 intset 结构将 contents 属性声明为 int8_t 类型的数组，但实际上 contents 数组并不保存任何 int8_t 类型的值，contents 数组的真正类型取决于 encoding 属性的值）
整数集合的升级
当存储int64的整数集合添加一个int32的元素，会导致集合中所有元素转变为int32类型，按照新元素的类型进行扩容和空间分配，将现有元素转变为新类型，之后改变encoding的值（对应存储元素的类型），并且length+1(表示加入一个新元素)。

2.7 压缩列表ZipList

是一种双向链表，可以存储字符串或整数（二进制形式）。
整体由5部分组成：

zlbytes：四字节，存储整体ziplist占用的内存字节数；
zltail：四字节，给出最后一个entry的偏移量用于快速定位末尾元素；
zllen：两字节，存储整个ziplist中entry的个数；如果超过16位的最大表示范围（65535），则使用特殊值65535表示entry个数未知，此时确认ziplist的长度需要遍历整个ziplist；
entry组：
- 有两种结构
- 一般结构：prevlen + encoding + entry-data
- 若存储的都是int型数据，则使用特殊结构：prevlen + encoding
zlend：终止字节，一个字节，固定值0xFF，用于标记ziplist的结尾。