那大厂实习的面试难度到底如何?
今天,就来跟大家拆解一波美团Java 后端实习的面经,主要是考察了Java、MySQL、Redis、网络、操作系统这五大块知识,可以说是校招必须掌握的五件套知识了。
我只能说,不愧是大厂面试,强度是很大,光是写面经都快 2 万字了
考察的知识点,我给大家罗列了一下:
MySQL InnoDB 引擎通过什么技术来保证事务的这四个特性的呢?
按隔离水平高低排序如下:
针对不同的隔离级别,并发事务时可能发生的现象也会不同。
也就是说:
MySQL可以按照四个角度来分类索引。
接下来,按照这些角度来说说各类索引的特点。
按数据结构分类
从数据结构的角度来看,MySQL 常见索引有 B+Tree 索引、HASH 索引、Full-Text 索引。每一种存储引擎支持的索引类型不一定相同,我在表中总结了 MySQL 常见的存储引擎 InnoDB、MyISAM 和 Memory 分别支持的索引类型。
InnoDB 是在 MySQL 5.5 之后成为默认的 MySQL 存储引擎,B+Tree 索引类型也是 MySQL 存储引擎采用最多的索引类型。在创建表时,InnoDB 存储引擎会根据不同的场景选择不同的列作为索引:
其它索引都属于辅助索引(Secondary Index),也被称为二级索引或非聚簇索引。创建的主键索引和二级索引默认使用的是 B+Tree 索引。
按物理存储分类
从物理存储的角度来看,索引分为聚簇索引(主键索引)、二级索引(辅助索引)。这两个区别在前面也提到了:
所以,在查询时使用了二级索引,如果查询的数据能在二级索引里查询的到,那么就不需要回表,这个过程就是覆盖索引。如果查询的数据不在二级索引里,就会先检索二级索引,找到对应的叶子节点,获取到主键值后,然后再检索主键索引,就能查询到数据了,这个过程就是回表。
按字段特性分类
从字段特性的角度来看,索引分为主键索引、唯一索引、普通索引、前缀索引。
主键索引就是建立在主键字段上的索引,通常在创建表的时候一起创建,一张表最多只有一个主键索引,索引列的值不允许有空值。在创建表时,创建主键索引的方式如下:
CREATE TABLE table_name (
....
PRIMARY KEY (index_column_1) USING BTREE
);
唯一索引建立在 UNIQUE 字段上的索引,一张表可以有多个唯一索引,索引列的值必须唯一,但是允许有空值。在创建表时,创建唯一索引的方式如下:
CREATE TABLE table_name (
....
UNIQUE KEY(index_column_1,index_column_2,...)
);
建表后,如果要创建唯一索引,可以使用这面这条命令:
CREATE UNIQUE INDEX index_name
ON table_name(index_column_1,index_column_2,...);
普通索引就是建立在普通字段上的索引,既不要求字段为主键,也不要求字段为 UNIQUE。在创建表时,创建普通索引的方式如下:
CREATE TABLE table_name (
....
INDEX(index_column_1,index_column_2,...)
);
建表后,如果要创建普通索引,可以使用这面这条命令:
CREATE INDEX index_name
ON table_name(index_column_1,index_column_2,...);
前缀索引是指对字符类型字段的前几个字符建立的索引,而不是在整个字段上建立的索引,前缀索引可以建立在字段类型为 char、 varchar、binary、varbinary 的列上。使用前缀索引的目的是为了减少索引占用的存储空间,提升查询效率。在创建表时,创建前缀索引的方式如下:
CREATE TABLE table_name(
column_list,
INDEX(column_name(length))
);
建表后,如果要创建前缀索引,可以使用这面这条命令:
CREATE INDEX index_name
ON table_name(column_name(length));
按字段个数分类
从字段个数的角度来看,索引分为单列索引、联合索引(复合索引)。
通过将多个字段组合成一个索引,该索引就被称为联合索引。比如,将商品表中的 product_no 和 name 字段组合成联合索引(product_no, name),创建联合索引的方式如下:
CREATE INDEX index_product_no_name ON product(product_no, name);
联合索引(product_no, name) 的 B+Tree 示意图如下(图中叶子节点之间我画了单向链表,但是实际上是双向链表,原图我找不到了,修改不了,偷个懒我不重画了,大家脑补成双向链表就行)。
可以看到,联合索引的非叶子节点用两个字段的值作为 B+Tree 的 key 值。当在联合索引查询数据时,先按 product_no 字段比较,在 product_no 相同的情况下再按 name 字段比较。也就是说,联合索引查询的 B+Tree 是先按 product_no 进行排序,然后再 product_no 相同的情况再按 name 字段排序。因此,使用联合索引时,存在最左匹配原则,也就是按照最左优先的方式进行索引的匹配。在使用联合索引进行查询的时候,如果不遵循「最左匹配原则」,联合索引会失效,这样就无法利用到索引快速查询的特性了。比如,如果创建了一个 (a, b, c) 联合索引,如果查询条件是以下这几种,就可以匹配上联合索引:
需要注意的是,因为有查询优化器,所以 a 字段在 where 子句的顺序并不重要。但是,如果查询条件是以下这几种,因为不符合最左匹配原则,所以就无法匹配上联合索引,联合索引就会失效:
上面这些查询条件之所以会失效,是因为(a, b, c) 联合索引,是先按 a 排序,在 a 相同的情况再按 b 排序,在 b 相同的情况再按 c 排序。所以,b 和 c 是全局无序,局部相对有序的,这样在没有遵循最左匹配原则的情况下,是无法利用到索引的。联合索引有一些特殊情况,并不是查询过程使用了联合索引查询,就代表联合索引中的所有字段都用到了联合索引进行索引查询,也就是可能存在部分字段用到联合索引的 B+Tree,部分字段没有用到联合索引的 B+Tree 的情况。这种特殊情况就发生在范围查询。联合索引的最左匹配原则会一直向右匹配直到遇到「范围查询」就会停止匹配。也就是范围查询的字段可以用到联合索引,但是在范围查询字段的后面的字段无法用到联合索引。
MySQL 是会将数据持久化在硬盘,而存储功能是由 MySQL 存储引擎实现的,所以讨论 MySQL 使用哪种数据结构作为索引,实际上是在讨论存储引使用哪种数据结构作为索引,InnoDB 是 MySQL 默认的存储引擎,它就是采用了 B+ 树作为索引的数据结构。
要设计一个 MySQL 的索引数据结构,不仅仅考虑数据结构增删改的时间复杂度,更重要的是要考虑磁盘 I/0 的操作次数。因为索引和记录都是存放在硬盘,硬盘是一个非常慢的存储设备,我们在查询数据的时候,最好能在尽可能少的磁盘 I/0 的操作次数内完成。
二分查找树虽然是一个天然的二分结构,能很好的利用二分查找快速定位数据,但是它存在一种极端的情况,每当插入的元素都是树内最大的元素,就会导致二分查找树退化成一个链表,此时查询复杂度就会从 O(logn)降低为 O(n)。
为了解决二分查找树退化成链表的问题,就出现了自平衡二叉树,保证了查询操作的时间复杂度就会一直维持在 O(logn) 。但是它本质上还是一个二叉树,每个节点只能有 2 个子节点,随着元素的增多,树的高度会越来越高。
而树的高度决定于磁盘 I/O 操作的次数,因为树是存储在磁盘中的,访问每个节点,都对应一次磁盘 I/O 操作,也就是说树的高度就等于每次查询数据时磁盘 IO 操作的次数,所以树的高度越高,就会影响查询性能。
B 树和 B+ 都是通过多叉树的方式,会将树的高度变矮,所以这两个数据结构非常适合检索存于磁盘中的数据。
官方使用基准测试的结果是,单线程的 Redis 吞吐量可以达到 10W/每秒,如下图所示:
img 之所以 Redis 采用单线程(网络 I/O 和执行命令)那么快,有如下几个原因:
分布式锁是用于分布式环境下并发控制的一种机制,用于控制某个资源在同一时刻只能被一个应用所使用。如下图所示:
Redis 本身可以被多个客户端共享访问,正好就是一个共享存储系统,可以用来保存分布式锁,而且 Redis 的读写性能高,可以应对高并发的锁操作场景。Redis 的 SET 命令有个 NX 参数可以实现「key不存在才插入」,所以可以用它来实现分布式锁:
基于 Redis 节点实现分布式锁时,对于加锁操作,我们需要满足三个条件。
满足这三个条件的分布式命令如下:
SET lock_key unique_value NX PX 10000
而解锁的过程就是将 lock_key 键删除(del lock_key),但不能乱删,要保证执行操作的客户端就是加锁的客户端。所以,解锁的时候,我们要先判断锁的 unique_value 是否为加锁客户端,是的话,才将 lock_key 键删除。可以看到,解锁是有两个操作,这时就需要 Lua 脚本来保证解锁的原子性,因为 Redis 在执行 Lua 脚本时,可以以原子性的方式执行,保证了锁释放操作的原子性。
// 释放锁时,先比较 unique_value 是否相等,避免锁的误释放
if redis.call("get",KEYS[1]) == ARGV[1] then
return redis.call("del",KEYS[1])
else
return 0
end
这样一来,就通过使用 SET 命令和 Lua 脚本在 Redis 单节点上完成了分布式锁的加锁和解锁。
OSI七层模型
为了使得多种设备能通过网络相互通信,和为了解决各种不同设备在网络互联中的兼容性问题,国际标准化组织制定了开放式系统互联通信参考模型,也就是 OSI 网络模型,该模型主要有 7 层,分别是应用层、表示层、会话层、传输层、网络层、数据链路层以及物理层。
每一层负责的职能都不同,如下:
由于 OSI 模型实在太复杂,提出的也只是概念理论上的分层,并没有提供具体的实现方案。事实上,我们比较常见,也比较实用的是四层模型,即 TCP/IP 网络模型,Linux 系统正是按照这套网络模型来实现网络协议栈的。
TCP/IP模型
TCP/IP协议被组织成四个概念层,其中有三层对应于ISO参考模型中的相应层。ICP/IP协议族并不包含物理层和数据链路层,因此它不能独立完成整个计算机网络系统的功能,必须与许多其他的协议协同工作。TCP/IP 网络通常是由上到下分成 4 层,分别是应用层,传输层,网络层和网络接口层。
Linux 内核提供了不少进程间通信的方式:
Linux 内核提供了不少进程间通信的方式,其中最简单的方式就是管道,管道分为「匿名管道」和「命名管道」。
匿名管道顾名思义,它没有名字标识,匿名管道是特殊文件只存在于内存,没有存在于文件系统中,shell 命令中的「|」竖线就是匿名管道,通信的数据是无格式的流并且大小受限,通信的方式是单向的,数据只能在一个方向上流动,如果要双向通信,需要创建两个管道,再来匿名管道是只能用于存在父子关系的进程间通信,匿名管道的生命周期随着进程创建而建立,随着进程终止而消失。
命名管道突破了匿名管道只能在亲缘关系进程间的通信限制,因为使用命名管道的前提,需要在文件系统创建一个类型为 p 的设备文件,那么毫无关系的进程就可以通过这个设备文件进行通信。另外,不管是匿名管道还是命名管道,进程写入的数据都是缓存在内核中,另一个进程读取数据时候自然也是从内核中获取,同时通信数据都遵循先进先出原则,不支持 lseek 之类的文件定位操作。
消息队列克服了管道通信的数据是无格式的字节流的问题,消息队列实际上是保存在内核的「消息链表」,消息队列的消息体是可以用户自定义的数据类型,发送数据时,会被分成一个一个独立的消息体,当然接收数据时,也要与发送方发送的消息体的数据类型保持一致,这样才能保证读取的数据是正确的。消息队列通信的速度不是最及时的,毕竟每次数据的写入和读取都需要经过用户态与内核态之间的拷贝过程。
共享内存可以解决消息队列通信中用户态与内核态之间数据拷贝过程带来的开销,它直接分配一个共享空间,每个进程都可以直接访问,就像访问进程自己的空间一样快捷方便,不需要陷入内核态或者系统调用,大大提高了通信的速度,享有最快的进程间通信方式之名。但是便捷高效的共享内存通信,带来新的问题,多进程竞争同个共享资源会造成数据的错乱。
那么,就需要信号量来保护共享资源,以确保任何时刻只能有一个进程访问共享资源,这种方式就是互斥访问。信号量不仅可以实现访问的互斥性,还可以实现进程间的同步,信号量其实是一个计数器,表示的是资源个数,其值可以通过两个原子操作来控制,分别是 P 操作和 V 操作。
与信号量名字很相似的叫信号,它俩名字虽然相似,但功能一点儿都不一样。信号是异步通信机制,信号可以在应用进程和内核之间直接交互,内核也可以利用信号来通知用户空间的进程发生了哪些系统事件,信号事件的来源主要有硬件来源(如键盘 Cltr+C )和软件来源(如 kill 命令),一旦有信号发生,进程有三种方式响应信号 1. 执行默认操作、2. 捕捉信号、3. 忽略信号。有两个信号是应用进程无法捕捉和忽略的,即 SIGKILL 和 SIGSTOP,这是为了方便我们能在任何时候结束或停止某个进程。
前面说到的通信机制,都是工作于同一台主机,如果要与不同主机的进程间通信,那么就需要 Socket 通信了。Socket 实际上不仅用于不同的主机进程间通信,还可以用于本地主机进程间通信,可根据创建 Socket 的类型不同,分为三种常见的通信方式,一个是基于 TCP 协议的通信方式,一个是基于 UDP 协议的通信方式,一个是本地进程间通信方式。
一般来说,计算机网络都处在一个共享的环境。因此也有可能会因为其他主机之间的通信使得网络拥堵。
在网络出现拥堵时,如果继续发送大量数据包,可能会导致数据包时延、丢失等,这时 TCP 就会重传数据,但是一重传就会导致网络的负担更重,于是会导致更大的延迟以及更多的丢包,这个情况就会进入恶性循环被不断地放大....
所以,TCP 不能忽略网络上发生的事,它被设计成一个无私的协议,当网络发送拥塞时,TCP 会自我牺牲,降低发送的数据量。
于是,就有了拥塞控制,控制的目的就是避免「发送方」的数据填满整个网络。
为了在「发送方」调节所要发送数据的量,定义了一个叫做「拥塞窗口」的概念。
拥塞窗口 cwnd是发送方维护的一个的状态变量,它会根据网络的拥塞程度动态变化的。发送窗口 swnd 和接收窗口 rwnd 是约等于的关系,那么由于加入了拥塞窗口的概念后,此时发送窗口的值是swnd = min(cwnd, rwnd),也就是拥塞窗口和接收窗口中的最小值。
拥塞窗口 cwnd 变化的规则:
那么怎么知道当前网络是否出现了拥塞呢?其实只要「发送方」没有在规定时间内接收到 ACK 应答报文,也就是发生了超时重传,就会认为网络出现了拥塞。
拥塞控制有哪些控制算法?
拥塞控制主要是四个算法:
慢启动
TCP 在刚建立连接完成后,首先是有个慢启动的过程,这个慢启动的意思就是一点一点的提高发送数据包的数量,如果一上来就发大量的数据,这不是给网络添堵吗?慢启动的算法记住一个规则就行:当发送方每收到一个 ACK,拥塞窗口 cwnd 的大小就会加 1。这里假定拥塞窗口 cwnd 和发送窗口 swnd 相等,下面举个栗子:
慢启动算法的变化过程如下图:
可以看出慢启动算法,发包的个数是指数性的增长。那慢启动涨到什么时候是个头呢?有一个叫慢启动门限 ssthresh (slow start threshold)状态变量。
拥塞避免算法
前面说道,当拥塞窗口 cwnd 「超过」慢启动门限 ssthresh 就会进入拥塞避免算法。一般来说 ssthresh 的大小是 65535 字节。那么进入拥塞避免算法后,它的规则是:每当收到一个 ACK 时,cwnd 增加 1/cwnd。接上前面的慢启动的栗子,现假定 ssthresh 为 8:
拥塞避免算法的变化过程如下图:
所以,我们可以发现,拥塞避免算法就是将原本慢启动算法的指数增长变成了线性增长,还是增长阶段,但是增长速度缓慢了一些。就这么一直增长着后,网络就会慢慢进入了拥塞的状况了,于是就会出现丢包现象,这时就需要对丢失的数据包进行重传。当触发了重传机制,也就进入了「拥塞发生算法」。
拥塞发生
当网络出现拥塞,也就是会发生数据包重传,重传机制主要有两种:
这两种使用的拥塞发送算法是不同的,接下来分别来说说。发生超时重传的拥塞发生算法当发生了「超时重传」,则就会使用拥塞发生算法。这个时候,ssthresh 和 cwnd 的值会发生变化:
拥塞发生算法的变化如下图:
接着,就重新开始慢启动,慢启动是会突然减少数据流的。这真是一旦「超时重传」,马上回到解放前。但是这种方式太激进了,反应也很强烈,会造成网络卡顿。就好像本来在秋名山高速漂移着,突然来个紧急刹车,轮胎受得了吗。。。发生快速重传的拥塞发生算法还有更好的方式,前面我们讲过「快速重传算法」。当接收方发现丢了一个中间包的时候,发送三次前一个包的 ACK,于是发送端就会快速地重传,不必等待超时再重传。TCP 认为这种情况不严重,因为大部分没丢,只丢了一小部分,则 ssthresh 和 cwnd 变化如下:
快速恢复
快速重传和快速恢复算法一般同时使用,快速恢复算法是认为,你还能收到 3 个重复 ACK 说明网络也不那么糟糕,所以没有必要像 RTO 超时那么强烈。正如前面所说,进入快速恢复之前,cwnd 和 ssthresh 已被更新了:
然后,进入快速恢复算法如下:
快速恢复算法的变化过程如下图:
也就是没有像「超时重传」一夜回到解放前,而是还在比较高的值,后续呈线性增长。
Cookie和Session都是Web开发中用于跟踪用户状态的技术,但它们在存储位置、数据容量、安全性以及生命周期等方面存在显著差异:
线程池原理
线程池是为了减少频繁的创建线程和销毁线程带来的性能损耗,线程池的工作原理如下图:
线程池分为核心线程池,线程池的最大容量,还有等待任务的队列,提交一个任务,如果核心线程没有满,就创建一个线程,如果满了,就是会加入等待队列,如果等待队列满了,就会增加线程,如果达到最大线程数量,如果都达到最大线程数量,就会按照一些丢弃的策略进行处理。
线程池的参数有哪些?
线程池的构造函数有7个参数:
线程池种类有哪些?
ExecutorService executor = Executors.newFixedThreadPool(5);
ExecutorService executor = Executors.newCachedThreadPool();
ExecutorService executor = Executors.newSingleThreadExecutor();
ExecutorService executor = Executors.newScheduledThreadPool(5);
源自《Java并发编程艺术》 java.lang.Thread.State枚举类中定义了六种线程的状态,可以调用线程Thread中的getState()方法获取当前线程的状态。
线程状态 | 解释 |
---|---|
NEW | 尚未启动的线程状态,即线程创建,还未调用start方法 |
RUNNABLE | 就绪状态(调用start,等待调度)+正在运行 |
BLOCKED | 等待监视器锁时,陷入阻塞状态 |
WAITING | 等待状态的线程正在等待另一线程执行特定的操作(如notify) |
TIMED_WAITING | 具有指定等待时间的等待状态 |
TERMINATED | 线程完成执行,终止状态 |
synchronized 工作原理
synchronized是Java提供的原子性内置锁,这种内置的并且使用者看不到的锁也被称为监视器锁,
使用synchronized之后,会在编译之后在同步的代码块前后加上monitorenter和monitorexit字节码指令,他依赖操作系统底层互斥锁实现。他的作用主要就是实现原子性操作和解决共享变量的内存可见性问题。
执行monitorenter指令时会尝试获取对象锁,如果对象没有被锁定或者已经获得了锁,锁的计数器+1。此时其他竞争锁的线程则会进入等待队列中。执行monitorexit指令时则会把计数器-1,当计数器值为0时,则锁释放,处于等待队列中的线程再继续竞争锁。
synchronized是排它锁,当一个线程获得锁之后,其他线程必须等待该线程释放锁后才能获得锁,而且由于Java中的线程和操作系统原生线程是一一对应的,线程被阻塞或者唤醒时时会从用户态切换到内核态,这种转换非常消耗性能。
从内存语义来说,加锁的过程会清除工作内存中的共享变量,再从主内存读取,而释放锁的过程则是将工作内存中的共享变量写回主内存。
实际上大部分时候我认为说到monitorenter就行了,但是为了更清楚的描述,还是再具体一点。
如果再深入到源码来说,synchronized实际上有两个队列waitSet和entryList。
image.png
reentrantlock工作原理
ReentrantLock 的底层实现主要依赖于 AbstractQueuedSynchronizer(AQS)这个抽象类。AQS 是一个提供了基本同步机制的框架,其中包括了队列、状态值等。
ReentrantLock 在 AQS 的基础上通过内部类 Sync 来实现具体的锁操作。
不同的 Sync 子类实现了公平锁和非公平锁的不同逻辑。
ReentrantLock fairLock = new ReentrantLock(true);
ReentrantLock lock = new ReentrantLock();
Condition condition = lock.newCondition();
// 使用下面方法进行等待和唤醒
condition.await();
condition.signal();
应用场景的区别
synchronized
是一个很好的选择。它使用起来简单,不需要额外的资源管理,因为锁会在方法退出或代码块执行完毕后自动释放。synchronized
代码块。这可以让你更精细地控制同步的范围,从而减少锁的持有时间,提高并发性能。synchronized
关键字使用对象的内置锁(也称为监视器锁),这在需要使用对象作为锁对象的情况下很有用,尤其是在对象状态与锁保护的代码紧密相关时。ReentrantLock
提供了synchronized
所不具备的高级功能,如公平锁、响应中断、定时锁尝试、以及多个条件变量。当你需要这些功能时,ReentrantLock
是更好的选择。ReentrantLock
可以提供比synchronized
更好的性能,因为它提供了更细粒度的控制,如尝试锁定和定时锁定,可以减少线程阻塞的可能性。ReentrantLock
及其配套的Condition
对象可以提供更灵活的解决方案。综上,synchronized
适用于简单同步需求和不需要额外锁功能的场景,而ReentrantLock
适用于需要更高级锁功能、性能优化或复杂同步逻辑的情况。选择哪种同步机制取决于具体的应用需求和性能考虑。
Java 中的 Executors 类定义了一些快捷的工具方法,来帮助我们快速创建线程池。《阿里巴巴 Java 开发手册》中提到,禁止使用这些方法来创建线程池,而应该手动 new ThreadPoolExecutor 来创建线程池。这一条规则的背后,是大量血淋淋的生产事故,最典型的就是 newFixedThreadPool 和 newCachedThreadPool,可能因为资源耗尽导致 OOM 问题。所以,不建议使用 Executors 提供的两种快捷的线程池,原因如下:
除了建议手动声明线程池以外,我还建议用一些监控手段来观察线程池的状态。线程池这个组件往往会表现得任劳任怨、默默无闻,除非是出现了拒绝策略,否则压力再大都不会抛出一个异常。如果我们能提前观察到线程池队列的积压,或者线程数量的快速膨胀,往往可以提早发现并解决问题。
Spring IoC和AOP 区别:
在 Spring 框架中,IOC 和 AOP 结合使用,可以更好地实现代码的模块化和分层管理。例如:
Java的动态代理是一种在运行时动态创建代理对象的机制,主要用于在不修改原始类的情况下对方法调用进行拦截和增强。Java动态代理主要分为两种类型:
java.lang.reflect.Proxy
类和java.lang.reflect.InvocationHandler
接口。每一个动态代理类都必须实现InvocationHandler
接口,并且每个代理类的实例都关联到一个handler
。当通过代理对象调用一个方法时,这个方法的调用会被转发为由InvocationHandler
接口的invoke()
方法来进行调用。