关于后端:后端面经数据库Redis数据结构和底层数据类型

TOC
申明：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的利用场景和音讯队列的实现是绑定的。

相干命令:

音讯队列相干
- XADD key ID field value [field value ...]：依据键值key查找相干队列对象，在队尾增加音讯。音讯id个别应用*示意redis主动生成，自定义须要保障递增性，
  - XADD mystream * field1 A field2 B field3 C field4 D:在mystream对应的音讯队列中增加多条音讯，音讯id主动生成，音讯内容为field1:A field2:B field3:C field4:D
- XLEN key：依据键值key查找相干队列对象，取得音讯长度
  - XLEN mystream:取得mystream对应的音讯队列的长度
- XTRIM key MAXLEN [~] count：依据键值key查找相干队列对象，对队列进行修剪，限度长度为MAXLEN
  - XTRIM mystream MAXLEN 2：修剪mystream对应的音讯队列，限度长度为2
- XDEL key ID [ID ...]：依据键值key查找相干队列对象，删除指定ID的信息
  - XDEL mystream 1538561700640-0：在mystream对应的音讯队列中删除id为1538561700640-0的音讯
- XRANGE key start end [COUNT count]：依据键值key查找相干队列对象，取得[start end]之间的音讯列表，id从小到大。count管制返回的音讯数量，主动过滤已删除的音讯
  - XRANGE writers - + COUNT 2：依照id从小到大的程序，在writer对应的音讯队列中返回2个音讯记录
  - 此处的-和+示意最小值和最大值，只返回2个音讯记录；
- XREVRANGE key end start [COUNT count]：依据键值key查找相干队列对象，反向获取[end start]之间的音讯列表，ID从大到小
  - XREVRANGE writers + - COUNT 1：依照id从大到小的程序，在writer对应的音讯队列中返回一个音讯记录
- XREAD [COUNT count] [BLOCK milliseconds] STREAMS key [key ...] id [id ...]：count示意获取数量，block的毫秒数示意阻塞的毫秒数，没有设置则示意非阻塞，依据key查找相干音讯对象，读取对应id的音讯
  - XREAD COUNT 2 STREAMS mystream writers 0-0 0-0：从mystream、writers中别离读取id为0-0的音讯，返回音讯列表
生产组相干
- XGROUP CREATE key groupname id-or-$：在键值为key的值局部创立生产组，如果不存在key对应的表项则创立，生产组名为groupname，id-or-$决定生产方向，如果id为0-0，则示意从头开始读取音讯，如果id是$，示意从尾部开始生产
  - XGROUP CREATE mystream group1 0-0：在mystream对应的音讯队列中创立生产组group1，从头开始生产
- XREADGROUP GROUP group consumer [COUNT count] [BLOCK milliseconds] [NOACK] STREAMS key [key ...] ID [ID ...]：在key对应的音讯队列中，生产组名为group，消费者名为consumer，该消费者读取音讯队列中对应id的信息，读取数量为count，milliseconds示意阻塞工夫
  - XREADGROUP GROUP consumer-group-name consumer-name COUNT 1 STREAMS mystream >
- XACK key group id：被group对应的生产组解决的指定id的音讯标记为"已读"
- XGROUP SETID key groupname id-or-$：在键值为key对应的音讯队列，指定名为groupname的音讯队列进行游标挪动，id-or-$决定生产方向，如果id为0-0，则示意从头开始读取音讯，如果id是$，示意从尾部开始生产
- XGROUP DELCONSUMER key groupname consumername：删除对应键值的音讯队列中名为groupname的消费者组中，名为consumername的消费者
- XGROUP DESTROY key groupname：删除对应键值的音讯队列中名为groupname的消费者组
- XPENDING key group：显示对应键值的对应生产组中待处理音讯的信息列表，这些信息曾经被读取，然而还没有被确认
- XCLAIM key group consumername milliseconds ID：转移音讯归属权，相似于传递数据，键值key对应的音讯队列，将对应id的信息转移到消费者组group中对应的消费者consumername中，milliseconds示意阻塞工夫，超过这个工夫才开始转移
- XINFO GROUPS groupname：打印对应消费者组信息
- XINFO STREAM key：打印对应流信息
- XINFO CONSUMERS key groupname：打印对应消费者组中消费者信息

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; }dicthttypedef 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的结尾。

和个别的数组相比，ziplist的劣势在于：

节俭内存：不须要预留空间，而是依照encoding字段的理论需要来确定存储空间大小

同样也是因为节俭内存，不节约一点内存的思路，导致ziplist的毛病也很显著：

每次写操作都须要进行内存调配
扩容可能导致链式反应，影响后续节点的存储

面试模仿

Q：Redis的数据结构
A：从根本数据类型、非凡数据类型、底层数据结构三个方面答复
Q：为什么Redis应用的是哈希索引
A：内存键值数据库采纳哈希表作为索引，很大一部分起因在于，其键值数据根本都是保留在内存中的，而内存的高性能随机拜访个性能够很好地与哈希表O（1）的操作复杂度相匹配。
Q：Redis字符串底层和查问过程用的哪些数据结构
A：底层查问的过程中会波及到跳跃表的应用。

参考资料

Redis教程 - Redis常识体系详解
三万字+八十图，详解Redis五十二问！太全面了!
妈妈再也不放心我面试被Redis问得脸都绿了
Redis Bitmap 学习和应用
Redis源码分析--基数统计hyperloglog
Redis GEO & 实现原理深度剖析
基于Redis的Stream类型的完满音讯队列解决方案
Redis Stream

1. Redis数据类型

1.1 根本数据类型

1. string

2. hash

3. list

4. set

5. sortset/Zset

1.2 非凡数据类型

1. bitmap

2. hyperloglog

3. GEO

4. stream

2. Redis底层数据类型

2.1 简介

2.2 动静字符串SDS

2.3 快表QuickList

2.4 字典Dict

2.5 跳跃表ZSipList

2.6 整数汇合IntSet

2.7 压缩列表ZipList

面试模仿

参考资料