大家好, 我是小林。
分享一位同学阿里巴巴的后端面经,共有 2 面,第一面很顺利过了,可惜挂在第二面。
这两面的知识点范围,我帮大家罗列一下:
虽然都是比较基础的知识,但是会问很细,没深入学习的话,很容易扛不住。
ZSet用过吗 用过 zset 实现排行榜的功能。以博文点赞排名为例,小林发表了五篇博文,分别获得赞为 200、40、100、50、150。
# arcticle:1 文章获得了200个赞
> ZADD user:xiaolin:ranking 200 arcticle:1
(integer) 1
# arcticle:2 文章获得了40个赞
> ZADD user:xiaolin:ranking 40 arcticle:2
(integer) 1
# arcticle:3 文章获得了100个赞
> ZADD user:xiaolin:ranking 100 arcticle:3
(integer) 1
# arcticle:4 文章获得了50个赞
> ZADD user:xiaolin:ranking 50 arcticle:4
(integer) 1
# arcticle:5 文章获得了150个赞
> ZADD user:xiaolin:ranking 150 arcticle:5
(integer) 1
文章 arcticle:4 新增一个赞,可以使用 ZINCRBY 命令(为有序集合key中元素member的分值加上increment):
> ZINCRBY user:xiaolin:ranking 1 arcticle:4
"51"
查看某篇文章的赞数,可以使用 ZSCORE 命令(返回有序集合key中元素个数):
> ZSCORE user:xiaolin:ranking arcticle:4
"50"
获取小林文章赞数最多的 3 篇文章,可以使用 ZREVRANGE 命令(倒序获取有序集合 key 从start下标到stop下标的元素):
# WITHSCORES 表示把 score 也显示出来
> ZREVRANGE user:xiaolin:ranking 0 2 WITHSCORES
1) "arcticle:1"
2) "200"
3) "arcticle:5"
4) "150"
5) "arcticle:3"
6) "100"
获取小林 100 赞到 200 赞的文章,可以使用 ZRANGEBYSCORE 命令(返回有序集合中指定分数区间内的成员,分数由低到高排序):
> ZRANGEBYSCORE user:xiaolin:ranking 100 200 WITHSCORES
1) "arcticle:3"
2) "100"
3) "arcticle:5"
4) "150"
5) "arcticle:1"
6) "200"
Zset 类型的底层数据结构是由压缩列表或跳表实现的:
在 Redis 7.0 中,压缩列表数据结构已经废弃了,交由 listpack 数据结构来实现了。
JDK 1.7 ConcurrentHashMap
在 JDK 1.7 中它使用的是数组加链表的形式实现的,而数组又分为:大数组 Segment 和小数组 HashEntry。
Segment 是一种可重入锁(ReentrantLock),在 ConcurrentHashMap 里扮演锁的角色;HashEntry 则用于存储键值对数据。一个 ConcurrentHashMap 里包含一个 Segment 数组,一个 Segment 里包含一个 HashEntry 数组,每个 HashEntry 是一个链表结构的元素。
JDK 1.7 ConcurrentHashMap 分段锁技术将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问,能够实现真正的并发访问。
JDK 1.8 ConcurrentHashMap
在 JDK 1.7 中,ConcurrentHashMap 虽然是线程安全的,但因为它的底层实现是数组 + 链表的形式,所以在数据比较多的情况下访问是很慢的,因为要遍历整个链表,而 JDK 1.8 则使用了数组 + 链表/红黑树的方式优化了 ConcurrentHashMap 的实现,具体实现结构如下:
JDK 1.8 ConcurrentHashMap JDK 1.8 ConcurrentHashMap 主要通过 volatile + CAS 或者 synchronized 来实现的线程安全的。添加元素时首先会判断容器是否为空:
如果把上面的执行用一句话归纳的话,就相当于是ConcurrentHashMap通过对头结点加锁来保证线程安全的,锁的粒度相比 Segment 来说更小了,发生冲突和加锁的频率降低了,并发操作的性能就提高了。而且 JDK 1.8 使用的是红黑树优化了之前的固定链表,那么当数据量比较大的时候,查询性能也得到了很大的提升,从之前的 O(n) 优化到了 O(logn) 的时间复杂度。
TCP 三次握手过程
TCP 四次挥手过程
具体过程:
MSL 是 Maximum Segment Lifetime,报文最大生存时间,它是任何报文在网络上存在的最长时间,超过这个时间报文将被丢弃。因为 TCP 报文基于是 IP 协议的,而 IP 头中有一个 TTL 字段,是 IP 数据报可以经过的最大路由数,每经过一个处理他的路由器此值就减 1,当此值为 0 则数据报将被丢弃,同时发送 ICMP 报文通知源主机。
MSL 与 TTL 的区别:MSL 的单位是时间,而 TTL 是经过路由跳数。所以 MSL 应该要大于等于 TTL 消耗为 0 的时间,以确保报文已被自然消亡。
TTL 的值一般是 64,Linux 将 MSL 设置为 30 秒,意味着 Linux 认为数据报文经过 64 个路由器的时间不会超过 30 秒,如果超过了,就认为报文已经消失在网络中了。
TIME_WAIT 等待 2 倍的 MSL,比较合理的解释是:网络中可能存在来自发送方的数据包,当这些发送方的数据包被接收方处理后又会向对方发送响应,所以一来一回需要等待 2 倍的时间。
比如,如果被动关闭方没有收到断开连接的最后的 ACK 报文,就会触发超时重发 FIN 报文,另一方接收到 FIN 后,会重发 ACK 给被动关闭方, 一来一去正好 2 个 MSL。
可以看到 2MSL时长 这其实是相当于至少允许报文丢失一次。比如,若 ACK 在一个 MSL 内丢失,这样被动方重发的 FIN 会在第 2 个 MSL 内到达,TIME_WAIT 状态的连接可以应对。
HTTP是应用层协议,定义了客户端和服务器之间交换的数据格式和规则;Socket是通信的一端,提供了网络通信的接口;TCP是传输层协议,负责在网络中建立可靠的数据传输连接。它们在网络通信中扮演不同的角色和层次。
可以按照四个角度来分类索引。
聚簇索引数据结构是B+树,B+Tree 是一种多叉树,叶子节点才存放数据,非叶子节点只存放索引,而且每个节点里的数据是按主键顺序存放的。每一层父节点的索引值都会出现在下层子节点的索引值中,因此在叶子节点中,包括了所有的索引值信息,并且每一个叶子节点都有两个指针,分别指向下一个叶子节点和上一个叶子节点,形成一个双向链表。
聚簇索引的 B+Tree 如图所示:
数据存储到叶子节点,非叶子节点只有索引。
索引最大的好处是提高查询速度,但是索引也是有缺点的,比如:
所以,索引不是万能钥匙,它也是根据场景来使用的。
什么时候适用索引?
什么时候不需要创建索引?
使用联合索引时,存在最左匹配原则,也就是按照最左优先的方式进行索引的匹配。在使用联合索引进行查询的时候,如果不遵循「最左匹配原则」,联合索引会失效,这样就无法利用到索引快速查询的特性了。
(a, b, c) 联合索引,是先按 a 排序,在 a 相同的情况再按 b 排序,在 b 相同的情况再按 c 排序。所以,b 和 c 是全局无序,局部相对有序的,这样在没有遵循最左匹配原则的情况下,是无法利用到索引的。
对于读数据,我会选择旁路缓存策略,如果 cache 不命中,会从 db 加载数据到 cache。
对于写数据,我会选择更新 db 后,再删除缓存。
针对删除缓存异常的情况,我还会对 key 设置过期时间兜底,只要过期时间一到,过期的 key 就会被删除了。
除此之外,还有两种方式应对删除缓存失败的情况。
消息队列方案
我们可以引入消息队列,将第二个操作(删除缓存)要操作的数据加入到消息队列,由消费者来操作数据。
举个例子,来说明重试机制的过程。
订阅 MySQL binlog,再操作缓存
「先更新数据库,再删缓存」的策略的第一步是更新数据库,那么更新数据库成功,就会产生一条变更日志,记录在 binlog 里。
于是我们就可以通过订阅 binlog 日志,拿到具体要操作的数据,然后再执行缓存删除,阿里巴巴开源的 Canal 中间件就是基于这个实现的。
Canal 模拟 MySQL 主从复制的交互协议,把自己伪装成一个 MySQL 的从节点,向 MySQL 主节点发送 dump 请求,MySQL 收到请求后,就会开始推送 Binlog 给 Canal,Canal 解析 Binlog 字节流之后,转换为便于读取的结构化数据,供下游程序订阅使用。
下图是 Canal 的工作原理:
所以,如果要想保证「先更新数据库,再删缓存」策略第二个操作能执行成功,我们可以使用「消息队列来重试缓存的删除」,或者「订阅 MySQL binlog 再操作缓存」,这两种方法有一个共同的特点,都是采用异步操作缓存。
如果某个查询语句使用了二级索引(非聚簇索引),但是查询的数据不是主键值,这时在二级索引找到主键值后,需要去聚簇索引中获得数据行,这个过程就叫作「回表」,也就是说要查两个 B+ 树才能查到数据。
不过,当查询的数据是主键值时,因为只在二级索引(非聚簇索引)就能查询到,不用再去聚簇索引查,这个过程就叫作「索引覆盖」,也就是只需要查一个 B+ 树就能找到数据。
InnoDB 创建主键索引默认为聚簇索引,数据被存放在了 B+Tree 的叶子节点上。也就是说,同一个叶子节点内的各个数据是按主键顺序存放的,因此,每当有一条新的数据插入时,数据库会根据主键将其插入到对应的叶子节点中。
如果我们使用自增主键,那么每次插入的新数据就会按顺序添加到当前索引节点的位置,不需要移动已有的数据,当页面写满,就会自动开辟一个新页面。因为每次插入一条新记录,都是追加操作,不需要重新移动数据,因此这种插入数据的方法效率非常高。
如果我们使用非自增主键,由于每次插入主键的索引值都是随机的,因此每次插入新的数据时,就可能会插入到现有数据页中间的某个位置,这将不得不移动其它数据来满足新数据的插入,甚至需要从一个页面复制数据到另外一个页面,我们通常将这种情况称为页分裂。页分裂还有可能会造成大量的内存碎片,导致索引结构不紧凑,从而影响查询效率。
举个例子,假设某个数据页中的数据是1、3、5、9,且数据页满了,现在准备插入一个数据7,则需要把数据页分割为两个数据页:
出现页分裂时,需要将一个页的记录移动到另外一个页,性能会受到影响,同时页空间的利用率下降,造成存储空间的浪费。
而如果记录是顺序插入的,例如插入数据11,则只需开辟新的数据页,也就不会发生页分裂:
因此,在使用 InnoDB 存储引擎时,如果没有特别的业务需求,建议使用自增字段作为主键。
可以建立(a,b,c)联合索引,这样三个字段都能利用索引,并且 c 字段还能利用索引的有序性,避免了额外排序。
按隔离水平高低排序如下:
针对不同的隔离级别,并发事务时可能发生的现象也会不同。
在一个事务内多次查询某个符合查询条件的「记录数量」,如果出现前后两次查询到的记录数量不一样的情况,就意味着发生了「幻读」现象。
假设有 A 和 B 这两个事务同时在处理,事务 A 先开始从数据库查询账户余额大于 100 万的记录,发现共有 5 条,然后事务 B 也按相同的搜索条件也是查询出了 5 条记录。
接下来,事务 A 插入了一条余额超过 100 万的账号,并提交了事务,此时数据库超过 100 万余额的账号个数就变为 6。
然后事务 B 再次查询账户余额大于 100 万的记录,此时查询到的记录数量有 6 条,发现和前一次读到的记录数量不一样了,就感觉发生了幻觉一样,这种现象就被称为幻读。
快速排序的流程如下:
快速排序的时间复杂度为O(n log n),其中n为数组的长度。最坏情况下时间复杂度为O(n^2),发生在每次选择的基准元素都是最大或最小值时。平均情况下时间复杂度为O(n log n),效率较高。
主要是因为在每次划分时选择的基准元素不合适导致的。当每次选择的基准元素都是当前子数组中的最大或最小元素时,就会导致每次划分只能减少一个元素,而不是均匀地分成两部分,从而造成时间复杂度达到O(n^2)。
这种情况通常发生在数组已经有序或基本有序的情况下。为了避免最坏情况发生,可以通过随机选择基准元素或者使用三数取中法等策略来提高快速排序的性能。
冒泡排序在一些特定场景下仍然有其优势,比如:
红黑树是一种自平衡的二叉查找树,
具有以下特点:
红黑树的自平衡性质可以保证在进行插入、删除等操作后,树的高度保持在O(log n)内,从而保持了较高的查找、插入和删除效率。
下面是红黑树插入节点的过程,这左旋右旋的操作,就是为了自平衡。
左旋和右旋是两种基本的旋转操作,用于保持红黑树的平衡。下面简单描述一下左旋和右旋的操作步骤:
左旋操作:
接下来看下图片展示,首先断开节点PL与右子节点G的关系,同时将其右子节点的引用指向节点C2;然后断开节点G与左子节点C2的关系,同时将G的左子节点的应用指向节点PL。
接下来再放下 gif 图,希望能帮助大家更好地理解左旋
右旋操作与左旋操作对称,具体步骤如下:
首先断开节点G与左子节点PL的关系,同时将其左子节点的引用指向节点C2;然后断开节点PL与右子节点C2的关系,同时将PL的右子节点的应用指向节点G。
右旋的gif展示(图片来自网络):
hashmap扩容
HashMap 扩容的目的是为了减少哈希冲突,Java中hashmap扩容过程如下图:
当进行 put 操作导致整个哈希表的负载因子因此到达阈值后,会进入一个阻塞的扩容流程中,先通过复制一个两杯容量的entry数组,然后将原有entry中的元素进行遍历执行rehash,jdk1.8使用的是2次幂的扩展(指长度扩为原来2倍)。
所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。因此在执行rehash的时候只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”。
负载因子
HashMap 负载因子 loadFactor 的默认值是 0.75,当 HashMap 中的元素个数超过了容量的 75% 时,就会进行扩容。
默认负载因子为 0.75,是因为它提供了空间和时间复杂度之间的良好平衡。
负载因子太低会导致大量的空桶浪费空间,负载因子太高会导致大量的碰撞,降低性能。0.75 的负载因子在这两个因素之间取得了良好的平衡。
HashMap在发生扩容时,会重新计算元素的存放位置,可能导致原本分布均匀的元素在新的容量下发生“退化”,即多个元素映射到同一个桶(bucket)上,使得链表长度过长,影响了HashMap的性能。这种情况下,HashMap的查找、插入和删除操作的时间复杂度可能会由原本的O(1)上升到O(n),严重影响了HashMap的效率。
为了解决HashMap扩容后的退化问题,通常采用以下方法:
ArrayList在添加元素时,如果当前元素个数已经达到了内部数组的容量上限,就会触发扩容操作。ArrayList的扩容操作主要包括以下几个步骤:
ArrayList的扩容操作涉及到数组的复制和内存的重新分配,所以在频繁添加大量元素时,扩容操作可能会影响性能。为了减少扩容带来的性能损耗,可以在初始化ArrayList时预分配足够大的容量,避免频繁触发扩容操作。
1.5 可以充分利用移位操作,减少浮点数或者运算时间和运算次数。
// 新容量计算
int newCapacity = oldCapacity + (oldCapacity >> 1);