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

5次阅读

共计 9838 个字符，预计需要花费 25 分钟才能阅读完成。

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

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

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

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

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

面试模仿

Q：Redis 的数据结构
A：从根本数据类型、非凡数据类型、底层数据结构三个方面答复

Q：为什么 Redis 应用的是哈希索引
A：内存键值数据库采纳哈希表作为索引，很大一部分起因在于，其键值数据根本都是保留在内存中的，而内存的高性能随机拜访个性能够很好地与哈希表 O（1）的操作复杂度相匹配。

Q：Redis 字符串底层和查问过程用的哪些数据结构
A：底层查问的过程中会波及到跳跃表的应用。

参考资料

  1. Redis 教程 – Redis 常识体系详解
  2. 三万字 + 八十图，详解 Redis 五十二问！太全面了!
  3. 妈妈再也不放心我面试被 Redis 问得脸都绿了
  4. Redis Bitmap 学习和应用
  5. Redis 源码分析 – 基数统计 hyperloglog
  6. Redis GEO & 实现原理深度剖析
  7. 基于 Redis 的 Stream 类型的完满音讯队列解决方案
  8. Redis Stream
正文完
后端
发表至： 后端
2023-09-08
 0
关于后端:最佳实践丨使用Rancher轻松管理上万资源不是梦
关于后端:制作python包并上传pypi
关于后端:CS300-Planner
关于后端:CAP原则

站内搜索

-「」