阻塞 IO

我们知道在调用某个函数的时候无非就是两种情况，要么马上返回，然后根据返回值进行接下来的业务处理。当在使用阻塞 IO 的时候，应用程序会被无情的挂起，等待内核完成操作，因为此时的内核可能将 CPU 时间切换到了其他需要的进程中，在我们的应用程序看来感觉被卡主(阻塞)了。

阻塞IO

非阻塞 IO

当使用非阻塞函数的时候，和阻塞 IO 类比，内核会立即返回，返回后获得足够的 CPU 时间继续做其他的事情。

非阻塞

IO 复用模型

当使用 fgets 等待标准输入的时候，如果此时套接字有数据但不能读出。IO 多路复用意味着可以将标准输入、套接字等都当做 IO 的一路，任何一路 IO 有事件发生，都将通知相应的应用程序去处理相应的 IO 事件，在我们看来就反复同时可以处理多个事情。这就是 IO 复用。

IO复用

信号驱动 IO

在信号驱动式 I/O 模型中，应用程序使用套接口进行信号驱动 I/O，并安装一个信号处理函数，进程继续运行并不阻塞。当数据准备好时，进程会收到一个 SIGIO 信号，可以在信号处理函数中调用 I/O 操作函数处理数据。

信号驱动

异步 IO

用程序告知内核启动某个操作，并让内核在整个操作（包括将数据从内核拷贝到应用程序的缓冲区）完成后通知应用程序。那么和信号驱动有啥不一样?

异步IO

• 讲讲 select 和 epoll 的区别？

这里一样的套路，先说出两者的用途，然后两者的优缺点。

select 的缺点

• select 返回的是含有整个句柄的数组，应用程序需要遍历整个数组才能发现哪些句柄发生了事件

• select 的触发方式是水平触发，应用程序如果没有完成对一个已经就绪的文件描述符进行 IO 操作，那么之后每次 select 调用还是会将这些文件描述符通知进程

• 内核 / 用户空间内存拷贝问题，select 每次都会改变内核中的句柄数据结构集，因而每次 select 调用时都需要从用户空间向内核空间复制所有的句柄数据结构，产生巨大的开销

• 单个进程能够监视的文件描述符的数量存在最大限制，通常是 1024，当然可以更改数量

epoll 实现

epoll 在内核中会维护一个红黑树和一个双向链表，红黑树存放通过 epoll_ctl 方法向 epoll 对象中添加进来的事件，所以不需要每次调用 epoll_wait 都全量复制所有的事件结构。双向链表存放就绪的事件，所有添加到 epoll 中的事件都会与设备(网卡)驱动程序建立回调关系，也就是说，当相应的事件发生时会调用这个回调方法，这个回调方法在内核中叫 ep_poll_callback,它会将发生的事件添加到 rdlist 双链表中。调用 epoll_wait 就会直接返回链表中的就绪事件，效率高。

• select 适合少量活跃连接，一般几千。

• epoll 适合大量不太活跃的连接。

• 乐观锁和悲观锁了解吗？

这个问题延伸的问题会很多，比如线程安全，CAS 原理，优缺点等。

啥是悲观和乐观，咋们面试的时候不得乐观一些。想给面试来一波官方解释，然后大白话解释一波就差不多了。

官方：悲观锁是总是假设最坏的情况，每次那数据都认为别人会修改它，所以每次去那数据都要上锁，这样别人去拿这个数据就会阻塞。乐观锁就不一样了，总是觉得一切都是最好的安排，每次拿数据都认为别人不会修改，所以也就不上锁，但是在更新的时候会判断这个期间别人有没有更新这个数据。

• 什么是缓存穿透？如何避免？什么是缓存雪崩？何如避免？

缓存穿透

一般来说，缓存系统会通过 key 去缓存查询，如果不存在对应的 value，就应该去后端系统查找（比如 DB）。这个时候如果一些恶意的请求到来，就会故意查询不存在的 key,当某一时刻的请求量很大，就会对后端系统造成很大的压力。这就叫做缓存穿透。

如何避免？

对查询结果为空的情况也进行缓存，缓存时间设置短一点，或者该 key 对应的数据 insert 了之后清理缓存。对一定不存在的 key 进行过滤。可以把所有的可能存在的 key 放到一个大的 Bitmap 中，查询时通过该 bitmap 过滤。

缓存雪崩

当缓存服务器重启或者大量缓存集中在某一个时间段失效，这样在失效的时候，会给后端系统带来很大压力。导致系统崩溃。

如何避免？

在缓存失效后，通过加锁或者队列来控制读数据库写缓存的线程数量。比如对某个 key 只允许一个线程查询数据和写缓存，其他线程等待。

做二级缓存，A1 为原始缓存，A2 为拷贝缓存，A1 失效时，可以访问 A2，A1 缓存失效时间设置为短期，A2 设置为长期。

不同的 key，设置不同的过期时间，让缓存失效的时间点尽量均匀。

2 redis 相关

如果是后端/服务端面试的同学，怎么说都的去找一本 redis 书来看看，其出现的概率只有那么大了，切记切记。看看 B 站问了哪几个问题。

• redis 的淘汰删除策略了解吗？

能说不了解吗，就算是没有听说过，咋们也可以来一句：“不好意思面试官，这一块还不怎么深入，但是从字面意思来理解巴拉巴拉”，不至于一脸懵逼。下面我们看看 redis 的缓存策略

Redis 中通过 maxmemory 参数来设定内存的使用上限，如果 Redis 所使用内存超过设定的最大值，那么会根据配置文件中的策略选取要删除的 key 来删除，从而留出新的键值空间。主要的六种淘汰 key 策略

1. volatile-lru

在键空间中设置过期时间，移除哪些最近最少使用的 key，占着茅坑不拉屎的 key

2. allkeys-lru

移除最近最少使用的 key

3. volatile-random

在键空间中设置过期时间，随机移除一个 key

4. allkeys-random

随机移除一个 key

5. noeviction

当内存使用达到阀值的时候，所有引起申请内存的命令会报错；

ok，现在知道了需要淘汰哪些 key，那我们如何去淘汰这些 key

1. 定时删除

很简单，设置一个闹钟，闹钟响了就删除即可。这种方式对于内存来说还是比较友好，内存不需要啥额外的操作，直接通过定时器就可保证尽快的删除。对于 CPU 来说就有点麻烦了，如果过期键比较多，那么定时器也就多，这删除操作就会占用太多的 CPU 资源

2. 惰性删除

每次从键空间获取键的时候检查键的过期时间，如果过期了，删除完事。

3. 定期删除

每隔一段时间就去数据库检查，删除过期的键

这种方案是定时删除和惰性删除的中和方法，既通过限制删除操作执行的时长来减少对 CPU 时间的影响，也能减少内存的浪费。但是难点在于间隔时长需要根据业务情况而定。

3 mysql

• mysql 中使用的锁有哪些？什么时候使用行锁，什么时候会使用表锁？

InnoDB 中的行锁是通过索引上的索引项实现，主要特点是，只有通过索引条件检索数据，InnoDB 才会使用行级锁，否则 InnoDB 将使用表锁。

这里注意，在 Mysql 中，行级锁不是锁记录而是锁索引。索引又分为主键索引和非主键索引两种。如果在一条语句中操作了非主键索引，Mysql 会锁定该非主键索引，再锁定相关的主键索引。

• 了解过间隙锁吗？间隙锁的加锁范围是怎么确定的？

• 了解 B+树吗？B+树什么时候会出现结点分裂？

这个回答在上一篇的 B+树已经详细说了。这里简述一下

1. 将已满结点进行分裂，将已满节点后 M/2 节点生成一个新节点，将新节点的第一个元素指向父节点。

2. 父节点出现已满，将父节点继续分裂。

3. 一直分裂，如果根节点已满，则需要分类根节点，此时树的高度增加。

• 事务还没执行完数据库挂了，重启的时候会发生什么？

• undo 日志和 redo 日志分别是干嘛的？

redo log 重做日志是 InnDB 存储引擎层的，用来保证事务安全。在事务提交之前，每个修改操作都会记录变更后的数据，保存的是物理日志-数据，防止发生故障的时间点，有脏页未写入磁盘，在重启 mysql 的时候，根据 redo log 进行重做从而达到事务的持久性

undo log 回滚日志保存了事务发生之前的数据的一个版本，可以用于回滚，同时也提供多版本并发控制下的读。

• 简单讲讲数据库的 MVCC 的实现原理？

细说太多了，几个大写字母代表啥，这几个大写字母又是如何关联起来完事。细问再深究

• mysql 的 binlog 日志什么时候会使用？

首先应该知道 binlog 是一个二进制文件，记录所有增删改操作，节点之间的复制都会依靠 binlog 来完成。从底层原理来说，binlog 有三个模式

1. 模式 1--row 模式

每一行的数据被修改就会记录在日志中，然后在 slave 段对相同的数据进行修改。比如说"update xx where id in(1,2,3,4,5)"，使用此模式就会记录 5 条记录

2. 模式 2--statement 模式

修改数据的 sql 会记录到 master 的 binlog 中。slave 在复制的时候 sql thread 会解析成和原来 maseter 端执行过的相同的 sql 在此执行

3. 模式 3--mixed 模式

mixed 模式即混合模式，Mysql 会根据执行的每一条具体 sql 区分对待记录的日志形式。那么 binlog 的主从同步流程到底是咋样的

binlog同步

流程简述：

Master 执行完增删改操作后都会记录 binlog 日志,当需要同步的时候会主动通知 slave 节点，slave 收到通知后使用 IO THREAD 主动去 master 读取 binlog 写入relay日志(中转日志),然后使 SQL THREAD 完成对 relay 日志的解析然后入库操作,完成同步。

4 基本数据结构

• 使用 LRU 时，如果短时间内会出现大量只会使用一次的数据，可能导致之前大量高频使用的缓存被删除，请问有什么解决办法?

• 了解过循环链表吗？他的长度怎么计算？

他的主要特点是链表中的最后一个节点的指针域指向头结点，整个链表形成一个环。****这里循环链表判断链表结束的标志是，判断尾节点是不是指向头结点

• 哪种数据结构可以支持快速插入，删除，查找等操作？

思考这个问题的时候，我们不凡复习下不错的二分查找，它依赖数组随机访问的特性，其查找时间复杂度为 O(log n)。如果我们将元素放入链表中，二分查找还好使吗？这就是今天和大家分享的跳表

理解跳表

假设使用单链表存储 n 个元素，其中元素有序如下图所示

一级索引

从链表中查找一个元素，自然从头开始遍历找到需要查找的元素，此时的时间复杂度为 O(n)。那采用什么方法可以提高查询的效率呢？问就是加索引，如何加，我们从这部分数据中抽取几个元素出来作为单独的一个链表，如下图所示]

假设此时咋们查找元素 16，首先一级索引处寻找，当找到元素 14 的时候，下一个节点的值为 18，意味着我们寻找的数在这两个数的中间。此时直接从 14 节点指针下移到下面的原始链表中，继续遍历，正好下一个元素就是我们寻找的 16。好了，我们小结一下，如果从原始链表中寻找元素 16，需要遍历比较 8 次，如果通过索引链表寻找我们只需要 5 次即可。

在这里插入图片描述

我们继续查找元素 16，此时比较次数变为 4 次。这样看来，加一层索引查找的次数就变少，如果有 n 个元素到底有多少索引？

假设我们按照每两个结点就抽出一个结点作为上一层的索引节点，第一层所以节点个数 n/2，第二层为 n/4,第 x 级索引的结点个数是第 x-1 级索引的结点个数的 1/2，那第 x 级索引结点的个数就是 n/(2^x)。假设索引有 y 级，我们可以得到 n/(2^y)=2，从而求得 y=log2n-1。

这么多索引是不是就很浪费内存嘞？

假设原始链表大小为 n，那第一级索引大约有 n/2 个结点，第二级索引大约有 n/4 个结点，以此类推，每上升一级就减少一半，直到剩下 2 个结点。如果我们把每层索引的结点数写出来，就是一个等比数列。这几级索引的结点总和就是 n/2+n/4+n/8…+8+4+2=n-2 。所以，跳表的空间复杂度是 O(n) 。那还能不能降低一些呢。机智的你应该就考虑到假设每三个结点抽取一个节点作为索引链表的节点。

跳表与二叉查找树

两者其查找的时间复杂度均为 O(logn) ，那跳表还有哪些优势？

先看二叉查找树，

特殊二叉查找树

这种结构会导致二叉查找树的查找效率变为 O(n),。

跳表与红黑树

说实话，红黑树确实比较复杂，面试的时候让你写红黑树，你就给他大嘴巴子？

红黑树需要通过左右旋的方式去维持树大小平衡。而跳表是通过随机函数来维护前面提到的 “ 平衡性 ” 。当我们往跳表中插入数据的时候，我们可以选择同时将这个数据插入到部分索引层中。如何选择加入哪些索引层呢？我们通过一个随机函数，来决定将这个结点插入到哪几级索引中，比如随机函数生成了值 K ，那我们就将这个结点添加到第一级到第 K 级这 K 级索引中。当我们往跳表中插入数据的时候，我们可以选择同时将这个数据插入到部分索引层中。

小结

Redis 中的有序集合采用了跳表的方式来实现，其实还采用了散列表等数据结构进行融合。它在插入，删除等都有比较快的速度，虽然红黑树也可以做到，但是红黑树对于按照区间查找数据这个操作，跳表可以做到 O(logn) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了

5 总结

请记下以下几点:

• 公司招你去是干活了，不会因为你怎么怎么的而降低对你的要求标准。

• 工具上面写代码和手撕代码完全不一样。

• 珍惜每一次面试机会并学会复盘。

• 对于应届生主要考察的还是计算机基础知识的掌握，项目要求没有那么高，是自己做的就使劲抠细节，做测试，只有这样，才知道会遇到什么问题，遇到什么难点，如何解决的。从而可以侃侃而谈了。

• 非科班也不要怕，怕了你就输了！一定要多尝试。

最后总结

搞定算法，面试字节再不怕，有需要文章中分享的这些二叉树、链表、字符串、栈和队列等等各大面试高频知识点及解析

最后再分享一份终极手撕架构的大礼包(学习笔记)：分布式+微服务+开源框架+性能优化

本文已被CODING开源项目：【一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频+实战项目源码】收录