面试问题浓缩总结
小游
2021-03-20

数据类型

本文参考：硬核Redis总结，看这篇就够了！ (qq.com) (opens new window)

# 8大基本数据类型

图片

# String

适用于简单key-value存储、setnx key value实现分布式锁、计数器(原子性)、分布式全局唯一ID。

底层使用 char[] 实现，Redis 使用SDS(simple dynamic string)封装char[]（这是是Redis存储的最小单元），最大可以存储512M信息。数据结构如下：

struct sdshdr{
  unsigned int len; // 标记char[]的长度
  unsigned int free; //标记char[]中未使用的元素个数
  char buf[]; // 存放元素的坑
}
1
2
3
4
5

Redis对SDS再次封装生成了RedisObject，核心有两个作用：

  1. 说明是5种类型哪一种。
  2. 里面有指针用来指向 SDS。

当你执行set name sowhat的时候，其实Redis会创建两个RedisObject对象，键的RedisObject 和 值的RedisOjbect 其中它们type = REDIS_STRING，而SDS分别存储的就是 name 跟 sowhat 字符串。

并且Redis底层对SDS有如下优化：

  1. SDS修改后大小 > 1M时 系统会多分配空间来进行空间预分配。
  2. SDS是惰性释放空间的，你free了空间，可是系统把数据记录下来下次想用时候可直接使用。不用新申请空间。

# List

使用双向链表实现，该链表最大长度为2^32-1 。

图片

可以组合为先进后出的栈、先进先出的队列、有限集合、消息列队。

一般可以用来做简单的消息队列，并且当数据量小的时候可能用到独有的压缩列表来提升性能。

# Hash

Redis中只有一个K，一个V。其中 K 绝对是字符串对象，而 V 可以是String、List、Hash、Set、ZSet任意一种。

底层主要是采用字典dict的结构，整体呈现层层封装。（dict包含dictht包含dictEntry）

  1. dictEntry 是真正的数据节点，包括key、value 和 next 节点。
  2. dictht包含下面几个内容
    1. dictEntrytable: 数据 dictEntry 类型的数组，每个数组的item可能都指向一个链表。
    2. size :数组长度 size
    3. sizemask :等于 size - 1
    4. used:当前 dictEntry 数组中包含总共多少节点
  3. dict包括下面几个内容
    1. dictType 类型，包括一些自定义函数，这些函数使得key和value能够存储
    2. rehashidx 其实是一个标志量，如果为-1说明当前没有扩容，如果不为 -1 则记录扩容位置。
    3. dictht数组，两个Hash表。
    4. iterators 记录了当前字典正在进行中的迭代器

整体结构如下

图片

# Set

类似于Java中HashSet是HashMap (opens new window)的简化版

# ZSet

用于积分排行榜、时间排序新闻、延时队列。

有序的set，Zset用的就是可以跟二叉树媲美的跳跃表来实现有序。跳表就是多层链表的结合体，跳表分为许多层(level)，每一层都可以看作是数据的索引，这些索引的意义就是加快跳表查找数据速度。

跳表每一层的数据都是有序的，上一层数据是下一层数据的子集，并且第一层(level 1)包含了全部的数据；层次越高，跳跃性越大，包含的数据越少。

redis跳跃表可以参考：跳跃表 — Redis 设计与实现 (redisbook.readthedocs.io) (opens new window)

# Redis Geo

功能：

主要用于存储地理位置，并提供操作方法：Redis GEO | 菜鸟教程 (runoob.com) (opens new window)

底层原理：

他的核心思想就是将地球近似为球体来看待，然后 GEO利用 GeoHash 将二维的经纬度转换成字符串，来实现位置的划分跟指定距离的查询。

# HyperLogLog

是一种概率数据结构，使用概率算法来统计集合的近似基数，而它算法的最本源则是伯努利过程 + 分桶 + 调和平均数。

深入原理参考：初识Redis的数据类型HyperLogLog - throwable - 博客园 (cnblogs.com) (opens new window)

功能：

误差允许范围内做基数统计 (基数就是指一个集合中不同值的个数) 的时候非常有用，每个HyperLogLog的键可以计算接近2^64不同元素的基数，而大小只需要12KB。错误率大概在0.81%。如果用做 UV 统计很合适。

HyperLogLog底层 一共分了 2^14 个桶，也就是 16384 个桶。每个(registers)桶中是一个 6 bit 的数组，这里有个骚操作就是一般人可能直接用一个字节当桶浪费2个bit空间，但是Redis底层只用6个然后通过前后拼接实现对内存用到了极致，最终就是 16384*6/8/1024 = 12KB。

# bitmap

使用一个bit位来表示元素的状态，所以 BitMap 能映射的状态有限，但是使用比特位的优势是能大量的节省内存空间。

底层原理：

是基于字符串类型来实现的，可以把 Bitmaps 想象成一个以比特位为单位的数组，数组的每个单元只能存储0和1，数组的下标在 Bitmaps 中叫做偏移量，BitMap 的 offset 值上限 2^32 - 1。

图片

用途：

  1. 用户签到（key使用年份+用户id offset 然后值为（今天是一年中的第几天） % （今年的天数））
  2. 统计活跃用户（使用日期作为 key，然后用户 id 为 offset 设置不同offset为0 1 即可）

# 布隆过滤器

用于快速判断某个值是否在大量数据集中，特点是不存在的一定不存在，存在的不一定存在，而且占用内存特别小。

原理：

当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点(有效降低冲突概率)，把它们置为1。检索时，我们只要看看这些点是不是都是1就知道集合中有没有它了：如果这些点有任何一个为0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。

注：除了Redis，guava 工具包也提供了布隆过滤器的使用

详细原理：Redis详解（十三）------ Redis布隆过滤器 - YSOcean - 博客园 (cnblogs.com) (opens new window)

# 发布订阅机制

redis提供了发布、订阅模式的消息机制，其中消息订阅者与发布者不直接通信，发布者向指定的频道（channel）发布消息，订阅该频道的每个客户端都可以接收到消息。

图片

# Hash如何扩容

采用渐进式rehash的方式，hash底层有两个数组（目的是为了扩容时不影响前端CRUD），初始默认hash长度为4，当元素个数与hash表长度一致时，就发生扩容，hash长度变为原来的二倍。

rehash步骤：

  1. 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表
  2. 将rehashindex的值设置为0，表示rehash工作正式开始
  3. 在rehash期间，每次对字典执行增删改查操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashindex索引上的所有键值对rehash到ht[1]，当rehash工作完成以后，rehashindex的值+1
  4. 随着字典操作的不断执行，最终会在某一时间段上ht[0]的所有键值对都会被rehash到ht[1]，这时将rehashindex的值设置为-1，表示rehash操作结束

渐进式rehash采用的是一种分而治之的方式，将rehash的操作分摊在每一个的访问中，避免集中式rehash而带来的庞大计算量。

需要注意的是在渐进式rehash的过程，如果有增删改查操作时，如果index大于rehashindex，访问ht[0]，否则访问ht[1]。

深入可参考：redis中的hash扩容渐进式rehash过程_沐雨金鳞-CSDN博客 (opens new window)

编辑 (opens new window)
上次更新: 2021/04/01, 17:14:55
MySQL底层
持久化

← 持久化→

Theme by Vdoing | Copyright © 2021-2021 小游