数据库面试重点

发表于 更新于 分类于

MySQL

隔离级别 7

并发一致性问题

  • 丢失修改：一个事务对数据的修改被另一个事务对数据的修改覆盖
  • 脏读：一个事务读取了被另一个事务修改，但是未提交的数据。如果修改被撤销，那么此次读到的就是脏数据
  • 不可重复读：是指一个事务在执行期间多次读取某一行数据。这期间如果有另一个事务对这个数据进行了修改（更新或删除），会导致两次读取的数据结果不同。
  • 幻读：同一查询多次执行时，由于其他事务在这个数据范围内执行了插入操作，会导致每次返回不同结果

隔离级别

  • 未提交读：其他事务可以读取到一个事务还未提交的数据，会导致脏读、不可重复读和幻读
  • 提交读：事务只能看见已提交的事务对数据库进行的修改，避免脏读，但是会有不可重复读和幻读
  • 可重复读（MySQL默认隔离级别）：一个事务在多次读取同一个数据时读取到的都是相同的结果，可以避免不可重复读
  • 可串行化：强制事务串行执行，不可能发生冲突，从而解决幻读

不可重复读和幻读的区别

不可重复度针对的是一个数据整体（对单个学生的信息进行修改），而幻读针对的是一个数据范围，并且需要是插入操作（就比如查询成绩在某个范围内的学生，在此期间不断进行插入操作）

索引 6

为什么要索引

优点

  • 加快数据的检索速度
  • 创建唯一性索引可以保证表中每一行数据的唯一性

缺点

  • 创建和维护索引消耗很大，对数据进行增删时，如果数据有索引，对应的索引也需要修改，降低 SQL 的执行效率
  • 占用物理内存，索引也需要物理文件进行存储

聚簇索引的索引树叶子节点存放的是整行数据，表中行内容在物理存储中的顺序和索引顺序一致。一个表只能包含一个聚簇索引，因为索引只能按照一种方法进行排列

优点是查询速度快，定位到索引的节点就相当于定位到数据；缺点是修改代价大，修改数据就相当于修改了索引

非聚簇索引的叶子节点内容是主键的值，不存储数据。在 InnoDB 中非主键索引也被称为二级索引，因为根据定位到的主键再用主键索引树查一遍数据，这个过程叫做回表

优点是更新代价相比聚簇索引小，因为叶子节点不存放数据，缺点是会需要回表（二次查询），这样查找速度会慢些

覆盖索引是指在普通索引树上的查询已经提供了结果，不需要回表操作。覆盖索引可以显著提高查询效率。是常见的 MySQL 优化手段，所以可以对经常作为查询条件的列加索引

非主键索引 叶子节点存储的是 列值 + 主键

联合索引是由多列组成的索引，需要遵循最左前缀原则

假设创建的联合索引由三个字段组成:

1
ALTER TABLE table ADD INDEX index_name (num,name,age)

那么当查询的条件有为:num / (num AND name) / (num AND name AND age)时，索引才生效。所以在创建联合索引时，尽量把查询最频繁的那个字段作为最左(第一个)字段。查询的时候也尽量以这个字段为第一条件。

适合作为索引的字段：经常被查询的字段、经常被作为查询条件的字段、频繁用于连接的字段、经常出现在 ORDER BY / GROUP BY 后面的字段

索引失效的场景：以 % 开头的 LIKE 语句（表示匹配任意个字符）、OR 语句前后没有同时使用索引、数据出现隐式转换（例如 varchar 不加单引号可能会转为 int）

ACID 5

  • 原子性，一个事务不可分割，要么全部成功提交，要么全部失败回滚
  • 一致性，是基于AID的，保证事务只能把数据库从一个正确的状态转移到另一个正确的状态。所谓正确的状态就是要满足数据库提前定义的一些规则：例如值不能小于0等。因为数据库只保证一个 transaction 是否符合定义的规则，不保证它在逻辑上是否正确，逻辑上的正确性要由使用者决定。
  • 隔离性，多个事务并发执行时，一个事务的执行不影响其他事务的执行，保证数据库的执行结果和每个事务先后单独执行的结果一致
  • 持久性，一个事务一旦提交，对数据库的修改应该永久保存

索引的数据结构 4

B树 / B+树

  • B+树和B树都不是二叉树，一个节点可以存放多个值，并且指向多个子节点，指向子节点的值在节点左边的 key 和右边的 key 范围之间
  • 因为可以容纳更多子节点，并且节点容纳的信息更多，所以树更加矮胖，树的高度增长也很慢
  • 适合于数据库是因为较低的树高，如果每读取一个节点就要进行一次磁盘IO（将节点大小设置为磁盘页大小），那么高度越少，进行磁盘IO的次数也越少。因为磁盘读写速度远低于内存读写速度，所以宁可读取一个节点后在内存中进行多次比较，也不多次进行磁盘IO

区别

主要在于节点中存储的信息，B+树中间节点只存放索引，数据都在叶子节点；B树中间节点既存放数据又存放索引，叶子节点不携带任何信息

B+树相对于B树的好处

  • IO次数更少：中间节点只存放索引，数据都在叶子节点，中间节点可以存放更多的索引数据，数结构可以更矮胖，访问子节点次数少了，进行磁盘IO次数也少了
  • 查询效率更高稳定：因为每次查询从根节点到叶子节点的路径长度都相同，查询时间都差不多
  • 范围查询更高效：因为数据都在叶子节点，所以只需要遍历叶子节点的链表；而B树因为每个子节点都存在数据，所以要遍历的节点更多
  • 遍历更高效：B+树只需要遍历叶子节点，B树需要层次遍历整棵树

B+树索引 和 哈希索引 的区别

B+树索引

  • 有序，除了查找还可以进行排序分组

哈希索引

  • 哈希索引时间为O(1)
  • 失去有序性，无法用于排序分组
  • 只能进行精确查找，不能用于范围查找

InnoDB有一个自适应哈希索引，当某个索引值使用很频繁，会在B+Tree索引之上在创建一个哈希索引，让原来的索引具有哈希索引的快速查找功能。

红黑树和AVL树因为本质上都是二叉树，树的高度远高于 B树，所以需要进行 磁盘IO 的次数过多，不适合作为索引

事务 3

事务是一个操作序列，其中的操作要么都执行，要么都不执行，以 BEGIN TRANSACTION 开始， 以 ROLLBACK/COMMIT 结束

实现原理

  • 日志文件 - redo log / undo log
  • 锁技术
  • MVCC

原子性通过 undo log 实现

持久性通过 redo log 实现

隔离性通过 读写锁 + MVCC 实现

一致性 通过 原子性、持久性、隔离性 来实现

数据库引擎 3

InnoDB和MyISAM区别

  • 事务：MyISAM 不支事务；lnnoDB 是事务类存储引擎
  • 并发：MyISAM 只支持表级锁；InnoDB 支持表级锁和行级锁，默认为行级锁
  • 外键：MyISAM 不支持外键；InnoDB 支持外键
  • 备份：MyISAM 不支持在线热备份；InnoDB 支持在线热备份；
  • 崩溃恢复：MyISAM 崩溃后发生损坏的概率比 InnoDB 高，而且恢复速度也慢
  • 其他：MyISAM 支持空间数据索引（地理信息）和压缩表（减小所占空间）；InnoDB 相对的要占用更多磁盘空间

InnoDB 内部做了很多优化

  • 从磁盘读数据时采用可预测读（将用户很可能用到的数据预先加载到缓存池）
  • 会创建自适应哈希索引，加快读的速度
  • 有插入缓冲区（主要是针对非聚集索引，叶子节点的插入不再是顺序的了）来加速插入操作

Redo、Undo Log 3

Undo Log

Undo Log 用于存放数据被修改前的值，如果修改出现异常，可以通过 undo log 实现回滚操作，因为要实现回滚，所以 undo log 也是逻辑日志。Undo Log 也是实现 MVCC 的关键

Redo Log

Redo Log 用于记录事务对数据页的修改，是物理日志

对数据库中数据进行 UPDATE 操作时，需要将数据从磁盘读取到 buffer pool，然后在 buffer pool 中修改数据， redo log 中就记录了这些修改操作。如果更新的数据还没有同步到磁盘但是发生 crash 了，可以通过 redo log 中的记录恢复之前的修改操作（重做），保证了事务的持久性

redo log 和 binary log 的主要区别在于

  • redo log 是物理日志，用于记录对数据页做了什么修改； binary log 是逻辑日志，记录的是 sql 语句的原始逻辑
  • redo log 是存储引擎层产生的，用来实现事务的持久性，binary log 是数据库层产生的，用于恢复数据库和实现主从复制
  • redo log 是循环写，空间用完后会覆盖之前的记录；binary log 是追加写，文件到达一定大小会换一个文件，不会覆盖之前的记录
  • 在事务开始后，修改操作就开始写在 redo log 中。事务提交之前，所执行的操作记录才会被写到 binary log 中，然后事务被提交。

锁相关 2

乐观锁、悲观锁、行锁、表锁、意向锁

乐观锁和悲观锁

  • 悲观锁：总是假设最坏的情况，每次去拿数据的时候都认为别人会修改，所以每次在拿数据的时候都会上锁，这样别人想拿这个数据就会阻塞直到它拿到锁。应用于数据更新比较频繁的场景，ReentrantLock sychronized 这些独占锁就是悲观锁的实现。
  • 乐观锁：总是假设最好的情况，每次去拿数据的时候都认为别人不会修改，所以不会上锁，但是在更新的时候会判断一下在此期间别人有没有去更新这个数据，可以使用版本号机制和CAS算法实现。应用于读多写少的场景

ABA 问题

当前事务读取的数据值是 A ，在此期间数据被改成 B 后又被改成 A。在此期间数据被修改过，但是系统认为它没有被修改过。解决办法是添加一个版本号，在比较数据时通过比较版本号来确认数据是否被修改

封锁粒度

MySQL提供两种封锁粒度：表级锁和行级锁

好处：封锁粒度越细，发生锁争用的可能性就越小，系统并发性就越高

坏处：系统开销大，因为加锁、释放锁、检查锁的状态都要消耗资源

互斥锁 X 锁：对数据加上 X 锁之后只允许该事务对数据进行读和修改，其他事务不能对该数据加任何锁

共享锁 S 锁：对数据加 S 锁之后事务能对数据进行读操作但是不能进行修改，其他事务只能对该数据加 S 锁

意向锁

  • 一个事务在获取某一行对象的S锁之前必须要获得整个表的IS锁或更强的锁
  • 一个事务在获得某一行对象的X锁之前，必须先获得整个表的IX锁
  • 锁的兼容关系：X 锁不兼容任何锁，S 锁和 IX 锁不兼容，其余均兼容

在存在行级锁的情况下，如果没有意向锁，一个事务要对表加X锁就要检查是否有其他事务对表中任意一行加了X锁。有意向锁之后，要对表加X锁只需要检查有没有其他事务对表加了X/IS/IX/S锁。如果有，表示其他事务正在使用这个表，加X锁失败

InnoDB 对 INSERT、UPDATE、UPDATE 语句会自动加 X 锁。对于普通 SELECT 语句不会加任何锁。显式加锁方法为：

加S锁：SELECT * FROM table_name WHERE … LOCK IN SHARE MODE

加X锁：SELECT * FROM table_name WHERE … FOR UPDATE

InnoDB的行锁是基于索引实现的，如果不通过索引访问数据，InnoDB会使用表锁。

（２）InnoDB间隙锁机制，以及InnoDB使用间隙锁的原因。

（３）在不同的隔离级别下，InnoDB的锁机制和一致性读策略不同。

（４）ＭySQL的恢复和复制对InnoDB锁机制和一致性读策略也有较大影响。

（５）锁冲突甚至死锁很难完全避免。

MVCC 2

多版本并发控制，用于实现 读提交 和 可重复读 两种隔离级别，通过一份数据临时保留多个版本的方法来实现并发控制

MVCC 的做法是让每个事务读到的是当前数据库的一个快照。 MVCC 更新一条数据时，不是用新数据覆盖旧数据，旧数据只会被标记为过时，然后在别处增加新数据。这样就会存储多个版本的数据，但是只有一个是最新的

数据库每个表中有两列关于 MVCC 的隐藏记录

  • 数据行版本号 (TRX_ID)：表示该行数据的版本
  • 回滚指针 (ROLL_PTR)：指向上一个 Undo log

通过控制读取数据的版本来实现并发控制：

  • 读提交：事务总是读这个数据最近一次被 commit 的版本
  • 可重复读：事务只读取当前事务开始前最后一次被 commit 的版本

通过加锁来实现并发的效率可能会非常差，一旦表被加上互斥锁，其他事务就不能进行读操作了。通过版本号减少了锁的争用，提高了系统性能

Undo Log

InnoDB 通过 Undo log 实现 MVCC。当对数据进行修改操作后，会生成一个 Undo log，Undo 中存储的是老版本的数据(被修改之前的值)，然后新数据行的回滚指针指向该 Undo log，当一个旧事务需要读取数据，需要通过回滚指针在undo链找到满足其可见性的记录

其中 INSERT 生成的日志在提交后会被删除，DELETE 作为一种特殊的 UPDATE，还会将 DEL 位改为1

Read View

在InnoDB中，创建一个新事务的时候还会将当前活跃着的事务列表创建一个 Read View

可见性算法比较

就是当前知道了读的数据行版本号，还有一个还活跃着的事务的一个数组。然后判断当前数据行在当前隔离级别下是否可读

假设当前正在读的数据行的版本号为 trx_id

read view中最老的事务id为trx_ id_min，最新的事务为 trx_id_max

  • 如果 trx_id < trx_ id_min，说明这个数据在当前事务开始之前已经被提交，是可见的
  • 如果 trx_id_current > trx_id_max ，说明该行数据在当前事务创建后才被创建并提交，不应该被看见。
  • 如果trx_ id_min <= trx_id <= trx_id_max
    • 如果trx_id在表中，表示对应的事务还没有提交，快照不可用
    • 反之表示已经提交，可以读

如果不可读，会通过回滚指针查找undo log，返回一条可见的记录。

根据隔离级别

  • 提交读会在事务每次进行 SELECT 操作的时候创建一个 READ VIEW
  • 重复读只会在第一次读的时候创建一个 READ VIEW ，以后都是复用之前的 READ VIEW

快照读和当前读

只有 SELECT 操作是快照读，读取的快照数据

修改操作都是当前读，对数据进行加锁确保读取到的是最新的数据

MVCC 只是避免了 SELECT 操作的锁争用

MySQL 如何解决幻读

MVCC 在可重复读隔离级别下加上 Next-Key Lock 可以避免幻读

Next-Key Lock 是由 Record Lock 和 Gap Lock 组成

两者结合后，在搜索的区域内，InnoDB首先会给区域内的索引项加锁（Record Lock），还会给键值在范围内但不存在的记录加锁（Gap Lock），这样就实现了整个区域的上锁。

举例来说，假如user表中只有101条记录，其empid的值分别是 1,2,…,100,101，下面的SQL：

1
select * from  user where user_id > 100 for update;

是一个范围条件的检索，InnoDB不仅会对符合条件的user_id值为101的记录加锁，也会对user_id大于101（这些记录并不存在）的“间隙”加锁。

产生幻读的原因是，行锁只能锁住行，但是新插入记录这个动作，要更新的是记录之间的“间隙”。因此，为了解决幻读问题，InnoDB 只好引入新的锁，也就是间隙锁 (Gap Lock)。

Innodb是如何实现事务的
Innodb 通过 Buffer Pool, LogBuffer, Redo Log, Undo Log 来实现事务，以一个 update 语句为例：

  1. Innodb在收到一个update语句后，会先根据条件找到数据所在的页，并将该页缓存在Buffer Pool中
  2. 执行update语句，修改Buffer Pool中的数据，也就是内存中的数据
  3. 针对update语句生成一个RedoLog对象，并存入LogBuffer中
  4. 针对update语句生成undolog日志，用于事务回滚
  5. 如果事务提交，那么则把RedoLog对象进行持久化，后续还有其他机制将Buffer Pool中所修改的数据页持久化到磁盘中
    如果事务回滚，则利用undolog日志进行回滚

连接表 2

inner join/left join/right join区别

  • 只返回两张表匹配的记录，这叫内连接（inner join）
  • 返回匹配的记录，以及表 A 多余的记录，这叫左连接（left join）
  • 返回匹配的记录，以及表 B 多余的记录，这叫右连接（right join）
  • 返回匹配的记录，以及表 A 和表 B 各自的多余记录，这叫全连接（full join）
1
2
//连接语句
select * from tableA inner join tableB on tableA.id = tableB.id;

inner join 不加条件的结果和 cross join 一样；cross join 加上条件的结果和 inner join 一样

inner join 属于内连接；left join / right join / full join 属于外连接；cross join 属于交叉连接

主从复制

主从复制就是指把数据从一个MySQL主服务器复制到多个从服务器。从服务器可以复制主服务的所有数据或特定的表，采用异步方式。

实现原理

  • 主服务器 binary log dump：将主服务器中数据增删改日志写到binary log中
  • 从服务器IO线程：将主服务器binary log中的信息读取并写入到到自己的relay log中
  • 从服务器SQL线程：读取relay log，解析出主服务器进行的数据修改并在从服务器重新执行，来保证数据的一致性

实现了读写分离，主服务器用来写，从服务器用来读

  • 缓解了锁的争用，即使主服务器被锁，从服务器依然可以读数据
  • 从服务器可以使用MyISAM，提升查询性能并节省系统开销
  • 增加冗余，提高可靠性
  • 降低单个服务器磁盘IO访问频率，提高单个机器IO性能

三大范式

  • 1NF：属性不可分割
    • 根据实际需求来定，以地址为例
  • 2NF：非主属性完全依赖于主属性
    • B 完全依赖于 A ，就是指 A 中的所有属性唯一决定 B ，少了不能唯一决定，多了会冗余。不满足这个规则会导致出现冗余数据
    • 依赖是指主属性确定的情况下可以唯一确定非主属性，不可能寻在两条记录，主属性相同但是非主属性不一致
    • 完全依赖是指一旦主属性少一个值，依赖关系就不存在
  • 3NF：非主属性不传递依赖于主属性
    • 例如：学生 -> 所在学院 -> 学院院长

视图

是从一张或多张表中导出的虚拟的表，其中的内容由查询语句定义，视图中不存储数据，其中的数据还是从实际的表中查询得来

  • 单表视图一般用于查询和修改，会改变基本表的数据
  • 多表视图一般用于查询，不会改变基本表的数据

Redis

数据结构 9

几种数据结构和底层实现，用来做什么，zset底层原理

String

  • 普通的 key/value 存储都可以归结为 string 类型
  • value 不仅是 string， 也可以是数字
  • 是动态字符串，可以被修改，底层类似于 ArrayList，是一个字符数组
  • 有三种编码：int 保存整数值；raw 保存长字符串；embstr 保存短字符串

应用场景

  • 因为是二进制安全的，可以存放图片
  • 可以作为计数器，统计在线人数，关注者人数
  • 实现分布式 session

List

  • 简单的字符串列表
  • 底层是双向链表 linkedlist，并不是数组，所以插入删除很快，定位很慢
  • 可以实现 栈、队列、阻塞队列 的功能

应用场景

  • 实现消息列表或者简单的消息队列
  • 利用 lrange 实现分页功能

Set

  • String 类型的无序集合，集合中的元素没有重复，相当于 Java 中的 HashSet
  • 整数也会转为 String 类型进行存储
  • 内部实现是 hashtable 相当于一个特殊字典，每个 key 都是一个字符串对象，value 都为 NULL

应用场景

  • 利用交集操作实现共同关注者的查询
  • 根据 set 的特性可以进行全局去重

Zset（重点）

https://zsr.github.io/2017/07/03/redis-zset%E5%86%85%E9%83%A8%E5%AE%9E%E7%8E%B0/

  • 和 set 相比， zset 中的对象是有序的，每个元素有一个 score 属性，以此作为排序依据
  • 同时包含一个字典 hash 和一个跳跃表 skiplist
  • 跳跃表按 score 大小从小到大保存所有集合元素，根据 score 查 member
  • 字典保存 member 到 score 的映射，根据 member 查找 score 的复杂度 O(1)
  • 两个数据结构通过指针来共享相同元素，不会浪费额外内存

跳跃表 skiplist 底层实现

理想的跳跃表是上下两层链表的节点数有严格对应，查找过程就类似于二分查找，复杂度为 O(logN)，但是插入节点会破坏这种关系，维持这种关系要调整后面所有的节点，时间复杂度又会退化到O(n)，为了避免这一情况，Redis 的 skiplist 采用的实现方法是

  • 上下两层节点没有严格对应关系
  • 每个节点随机出一个层数 n，在第一层到第 n 层都插入这个节点
  • 最大层数为 32
  • score 允许重复，score 相同的情况下根据数据内容进行字典排序
  • 第一层是一个双向链表，可以以倒序获取一个范围的元素
  • 每一个 forward 指针还有一个 span 变量，表示当前指针跨过多少节点，该变量用于计算元素排名

skiplist 和 平衡树 的比较

  • skiplist 插入和删除操作只要修改相邻节点指针；平衡树会引发树结构的改变
  • skiplist 范围查找更简单，找到最小值之后对第一层进行若干遍历即可；平衡树还要通过中序遍历查找
  • 实现相对来说更简单

应用场景

  • 范围查找，TOP N 排行榜应用

Hash

  • key 是一个字符串类型，value 是键值对集合
  • 相当于 Java 中的 HashMap，也是通过 数组 + 链表 解决哈希冲突

应用场景

  • 存储用户信息、商品信息等

持久化机制 5

快照 RDB 持久化

通过创建快照来获取内存中的数据在某个时间点上的副本

生成快照时，程序会对数据库中的键进行检查，已过期的键不会被保存到新建的 RDB 文件中

Redis 使用操作系统的多进程**写时复制技术（Copy On Write）**来实现快照持久化，保证在子线程生成 RDB 快照的同时，主线程依然可以写入数据，具体步骤为：

  • 持久化时， Redis 使用 bgsave 命令调用 glibc 函数 fork 一个子进程，快照持久化完全交给子进程处理，继续处理客户端请求。子进程刚产生时和父进程共享内存中的代码段和数据段，所以子进程刚刚被创建时，内存的增长几乎没有明显变化。极端情况下当刚 fork 完成后 redis 对整个内存都做了一次修改操作，会瞬时生成 2 份内存，内存占用变为原来的 2 倍
  • bgsave 的子进程可以共享主进程的所有内存数据，读取主线程的数据并写入到 RDB 快照中
  • 主线程执行写指令修改数据时，会发生写复制，生成一个修改后的数据的副本，子进程只能读取修改前的副本，无法获取后续的修改

可以把这个快照复制到其他服务器中来创建具有相同数据副本（主从结构）

系统发生故障会丢失最后一次创建快照后的数据

频繁生成 RDB 快照的问题：

  • 频繁对磁盘进行写入操作，磁盘压力过大
  • 使用 bgsave 来 fork 子进程的过程会阻塞主线程，使用 COW 也可以进一步减小 fork 时的阻塞时间

默认配置是：

  • 15分钟后有1个key发生变化就创建快照
  • 5分钟后有10个key发生变化就创建快照
  • 1分钟后有10000个key发生变化就创建快照

AOF 持久化

将写命令添加到AOF文件中

可以设置同步频率，每秒将写入操作同步到磁盘中，这样系统崩溃时只会丢失1秒的数据

问题是，随着写请求越来越多，AOF文件会越来越大。Redis提供了将AOF重写的特性来去除冗余的写命令。新的 AOF 文件和旧 AOF 文件保存的数据库状态完全一致，但是体积小的多。通过精简指令，（例如，原 AOF 对数据进行了一系列增删，新 AOF 只保留创建最终结果的那一句语句）

  • 重写的时候 fork 一个子进程，主进程仍然接收新的命令，子进程对原 AOF 文件扫描并把新的写命令追加到新创建的 AOF 文件中。子进程执行期间，主进程接收到的新写命令会存入到重写缓冲区，子进程完成重写之后，会先把缓冲区的命令追加到新的 AOF 文件，然后用新 AOF 文件替换旧 AOF 文件

Redis4.0有一个混合持久化，AOF重写的时候，fork 出来的子线程会先把和主线程共享的内存数据以 RDB 的方式写到 AOF 文件的开头，期间主线程的写操作会被记录在重写缓冲区，重写缓冲区的写命令以 AOF 方式追加写入到 AOF 文件，然后用新 AOF 替换旧 AOF。兼顾了 RDB 的快速加载特性和 AOF 的特性来避免丢失过多数据。如果想要开启，在配置文件中添加 aof-use-rdb-preamble yes

主从复制 3

复制过程

  • 从服务器向主服务器发送 SYNC 命令
  • 主服务器创建快照文件，发送给从服务器，期间在缓冲区中记录写命令，快照发送完成之后，服务器先执行缓冲区的写命令，并向从服务器发送缓冲区中的写命令
  • 从服务器丢弃所有旧数据并阻塞自己，载入主服务器发来的快照文件，然后接收主服务器发来的写命令
  • 主服务器每执行一次写命令，就向从服务器发送一次写命令

主服务器中的复制缓冲区是一个 FIFO 的队列，大小默认 1M，存储了最近的一些写命令，存储形式是 偏移量 + 字节值。每次加入新的写操作都会更新偏移量值，从服务器收到传输的命令后也会更新自己的偏移量值。

  • 主从节点的偏移量相同说明数据是同步的
  • 缓冲区中新命令写入后旧命令就会出队列
  • 某个从服务器断线重连之后发送同步命令给主服务器并带上自己的偏移量
    • 如果偏移量在缓冲区中，就把偏移量之后的所有命令发送给从服务器
    • 如果不在缓冲区，就要进行一次全量复制（此时主服务器进行 全量备份 时可能会造成毫秒级卡顿）

从服务器不会主动淘汰过期 key，主服务器处理掉过期的 key 后会向从服务器发送 del 命令来同步淘汰数据

主从复制可能存在的问题：

  • 一旦主节点宕机，从节点晋升主节点，同时需要修改应用方的主节点地址，还需要命令所有从节点去复制新的主节点，整个过程需要人工干预。
  • 如果从节点发生中断之后发起重新同步不成功，需要进行全量同步，此时主服务器进行全量备份时可能会造成毫秒级卡顿

主从链

随着负载上升，主服务器可能无法很快更新所有从服务器，主从链通过中间加入一层服务器来分担主服务器的复制工作。中间层服务器是主服务器的从服务器，又是下层服务器的主服务器。

实现 Redis 集群高可用

哨兵机制，是一个管理多个 Redis 实例的工具

  • 集群监控：监控 主从 服务器的 Redis 是否正常工作
  • 消息通知：如果有 Redis 实例有故障，会发送消息给管理员
  • 故障转移：如果主节点不能正常工作，，会自动将其中一个从节点升级为新的主节点，然后将其他从节点指向新的主节点

哨兵节点工作方式

  • 每个哨兵节点以每秒一次的频率向主服务器、从服务器和其他哨兵节点发送 PING 命令
  • 如果一个实例距离最后一次回复 PING 的事件超过了限定值，这个实例就会被哨兵标记为主观下线
  • 如果主服务器被标记为主观下线，其他正在监视该服务器的哨兵节点要以每秒一次的频率确认主服务器进入了主观下线状态
  • 如果一个主服务器被判定为主观下线，并且有一定数量的哨兵节点在指定时间范围内同意该判断，这个主服务器就被标记为客观下线，进入客观下线后才可以进行故障转移操作，实施故障转移还需要获得大多数哨兵的授权。
  • 一般情况下哨兵会每10秒向主服务器和从服务器发送 INFO 命令。当主服务器被标记为客观下线，哨兵向所有从服务器发送 INFO 命令的频率从 10 秒一次改为 每秒一次
  • 如果没有足够数量的哨兵同意主节点下线，客观下线状态就被移除；如果主节点重新向哨兵返回 PING 的有效回复，主观下线会被解除

Redis为什么速度快 2

  • 纯内存操作，不需要进行磁盘 IO
  • 单线程，保证了系统没有上下文切换的开销
    • 单线程只是只有一个线程来处理网络请求
    • 为了发挥多核 CPU 优势，可以创建多个 Redis 实例来处理网络请求
  • 数据结构简单，对数据的操作也简单
  • 采用 IO多路复用机制来同时监听多个 socket，非阻塞 IO

Redis 是单线程是因为内部使用文件事件处理器，这个处理器是单线程的

Redis采用IO多路复用机制来同时监听多个socket，根据socket的事件选择对应的事件处理器进行处理。

文件处理器包括4个结构：

  • 多个socket
  • IO多路复用程序
  • 文件事件分派器
  • 事件处理器

多个socket可能会并发产生不同的操作，每个操作对应不同的文件事件；IO多路复用程序会监听多个socket，将socket产生的事件放入队列中排队；事件分派器每次从队列中取出一个事件，把它交给对应的事件处理器处理。

跳表 2

构造方法，为什么不用红黑树

  • 是一个多层结构，最下层是双向链表，按序存储所有的元素，上层是逐渐稀疏的链表
  • 上层的节点记录了 forward 指针指向的下一个节点地址
  • 查找的时候从上往下快速找到对应区间，然后找到对应位置

和红黑树相比

  • 实现更加简单
  • 插入删除节点只涉及前后节点指针的改变；平衡树则会涉及到旋转，子树结构的改变
  • 范围查找时跳表只要找到端点值然后在底层链表遍历即可；平衡树还要通过一定中序遍历算法

热点缓存

MySQL 里有 2000w 数据，Redis 中只存 20w 的数据，如何保证 Redis 中的数据都是热点数据?

  1. volatile-lru：从设置过期时间的数据集中挑选最近最少使用的数据淘汰
  2. volatile-ttl：从设置过期时间的数据集中挑选将要过期的数据淘汰
  3. volatile-random：从设置过期时间的数据集中任意选择数据淘汰
  4. allkeys-lru：内存不足时，从所有键中淘汰最近最少使用的key
  5. allkeys-random：内存不足时，选择任意的键淘汰
  6. volatile-lfu：从设置过期时间的数据集中选择访问频率最低的淘汰
  7. allkeys-lfu：从所有键中选择访问频率最低的淘汰

lfu（Least Frequently Used）统计的是访问频率，将一定时间内被访问次数最少的键淘汰

缓存穿透、缓存击穿、缓存雪崩概念和解决办法

缓存穿透

客户端大量请求一些根本不存在于缓存中的 key，导致这些请求穿过缓存直接落到数据库上

解决办法

  • 将所有可能的请求值放入布隆过滤器，收到的请求如果不在过滤器中直接拦截
  • 如果一个 key 的查询结果为 null，将 key-null 键值对也加入缓存，并设置一个过期时间

缓存击穿

某个热点缓存突然失效，大量请求落到服务器上（和缓存雪崩的区别是针对某一个 key 的缓存）

解决办法

  • 设置热点数据不过期
  • 如果有多个线程向服务器查询该数据，就用一个互斥锁锁住该数据，等到查询到了数据并存入缓存，其他线程直接从缓存中取数据

缓存雪崩

缓存在同一时间内大面积失效，所有请求都落到数据库上，导致数据库短时间受到大量请求

  • 缓存集体到了过期时间
  • 服务器突然宕机，Redis 服务不可用

解决办法

  • 随机设置缓存的过期时间，可以在原来过期时间的基础上加上一个随机值
  • 使用 redis 集群并将热点数据分布在不同的 redis 服务器上

布隆过滤器

为什么不用 HashMap

  • HashMap 存储容量占比更高，而且负载因子的存在导致空间不能被用满
  • 布隆过滤器的数据结构占用空间少，但是返回结果是概率性

原理

  • 初始是一个 m 位的列表，每一位都置 0
  • 添加数据时
    • 使用多个 hash 函数对 key 进行计算得到一个索引值
    • 然后对列表长度 m 进行取模运算得到一个位置
    • 每个 hash 函数都会计算得到不同的位置
    • 将这些位置的值都置 1
  • 查询时
    • 也对 key 使用多个 hash 函数计算最后得到位置
    • 查看每个位置是否都为 1
    • 如果有一个不为 1，就肯定不存在这个 key
    • 如果都为 1，这个 key 可能存在，因为这个位置的 1 也有可能是其他 key 导致的
  • 性能需要在 hash 函数数量 和 布隆过滤器长度 之间做权衡

应用场景

  • 解决 redis 的缓存穿透问题
  • 业务中判断用户是否读过某文章，看过某视频。会有一定误判率，可能实际没读过但被判定为读过

事务相关

Redis 中的事务

开启事务的步骤

  • 用 MULTI 命令开启一个事务
  • 输入要执行的指令，这些指令会被放到队列中
  • 调用 EXEC 命令会让队列中的所有命令被执行
  • 调用 DISCARD 命令会清空事务队列，并放弃执行事务
  • 如果发送 EXEC 命令前用户掉线， redis 也会清空事务队列
  • WATCH 命令可以监控一个或多个键，一旦其中有一个键被修改或删除，之后的事务就不会被执行
    • 类似于 乐观锁 CAS 的机制
    • 对键的监视从执行 WATCH 开始，到 EXEC 结束，保证事务在所监视的键没有被修改的前提下被执行

报错机制

  • 命令有语法错误，执行 EXEC 会直接报错，任何指令都不会执行
  • 命令出现运行错误，错误的命令不会执行，但是事务中的其他命令仍然会被执行

Redis 事务无法保证原子性，运行错误时事务不会回滚。可以通过 lua 脚本来实现原子性

Redis 分布式锁

SETNX 指令

使用 SETNX 指令插入一个键值对，如果 Key 存在，就会返回 False，说明对象正处于锁定状态，获取锁失败；否则插入成功，返回 True。可以使用 EXPIRE 指令为一个键值对设置一个过期时间，避免锁释放失败的问题

RedLock算法

使用多个 Redis 实例来实现分布式锁，保证发生单点故障时仍然可用

  • 尝试从 N 个互相独立的 Redis 实例获取锁
  • 只有当获取锁消耗的时间小于锁过期的时间，并且获取超过半数的锁时，才认为锁获取成功
  • 如果获取失败，就释放每个实例上的锁

其他问题

加入主服务器写入新的数据，但是从服务器没有来得及复制，该如何查询

10亿个用户点赞 判断是否点过赞

  • 布隆过滤器，但是不一定精确，可能用户没有点过赞但被判定为点过