早就是优势,对于校招生来说,早准备的同学,有肉吃!
拿到了提前批 offer,不会马上说薪资的事情,大部分公司通常是延迟 10 月份才开奖,所以是大白菜,还是 sp,ssp offer,得等 10 月份了。
之前已经分享过深信服的提前批的面经,那么今天就来分享 tplink 提前批的后端开发面经,给大家感受一下提前批面试的氛围。
tplink 面试过程不是很长,通常一场面试 10 多个问题,相比互联网公司的面试数量,还是少一些,这次 tplink 的面经,还是我结合了 2 位同学的技术面试题汇总的。平常一些大厂面经,光是一个同学面经,就超过 30 个了。
考察的知识点,主要围绕Java+Redis+网络+算法:
根据 JVM8 规范,JVM 运行时内存共分为虚拟机栈、堆、元空间、程序计数器、本地方法栈五个部分。还有一部分内存叫直接内存,属于操作系统的本地内存,也是可以直接操作的。
JVM的内存结构主要分为以下几个部分:
本地方法栈与虚拟机栈在功能上有很多相似之处,但是它们之间还是有一些区别的。虚拟机栈主要用于执行 Java 方法,也就是字节码,而本地方法栈主要负责执行由非 Java 语言(如 C、C++)编写的 Native 方法。
每个线程都拥有一个和它生命周期相同的私有本地方法栈。虚拟机没有对本地方法栈使用的编程语言、实现方式和数据结构做严格限制,这意味着不同的虚拟机可以根据自己的需求实现本地方法栈。例如,Sun HotSpot 虚拟机就直接把本地方法栈和虚拟机栈合并为一个。
和虚拟机栈一样,本地方法栈也可能在栈深度超过虚拟机允许的范围时,抛出 StackOverflowError,在虚拟机栈动态扩展无法申请到足够内存时,抛出 OutOfMemoryError。
本地方法是指那些使用native关键字声明,但在Java外部实现的方法,通常使用C或C++编写。本地方法栈是每个线程私有的,它的功能与Java虚拟机栈类似,但是专门用于处理本地方法的调用。以下是本地方法栈的一些典型运行场景:
在Java中,native方法是一种特殊类型的方法,它允许Java代码调用外部的本地代码,即用C、C++或其他语言编写的代码。native关键字是Java语言中的一种声明,用于标记一个方法的实现将在外部定义。在Java类中,native方法看起来与其他方法相似,只是其方法体由native关键字代替,没有实际的实现代码。例如:
public class NativeExample {
public native void nativeMethod();
}
要实现native方法,你需要完成以下步骤:
synchronized
关键字来同步代码块或方法,确保同一时刻只有一个线程可以访问这些代码。对象锁是通过synchronized
关键字锁定对象的监视器(monitor)来实现的。public synchronized void someMethod() { /* ... */ }
public void anotherMethod() {
synchronized (someObject) {
/* ... */
}
}
volatile
关键字用于变量,确保所有线程看到的是该变量的最新值,而不是可能存储在本地寄存器中的副本。public volatile int sharedVariable;
java.util.concurrent.locks.Lock
接口提供了比synchronized
更强大的锁定机制,ReentrantLock
是一个实现该接口的例子,提供了更灵活的锁管理和更高的性能。private final ReentrantLock lock = new ReentrantLock();
public void someMethod() {
lock.lock();
try {
/* ... */
} finally {
lock.unlock();
}
}
java.util.concurrent.atomic
)提供了原子类,如AtomicInteger
、AtomicLong
等,这些类提供了原子操作,可以用于更新基本类型的变量而无需额外的同步。AtomicInteger counter = new AtomicInteger(0);
int newValue = counter.incrementAndGet();
ThreadLocal
类可以为每个线程提供独立的变量副本,这样每个线程都拥有自己的变量,消除了竞争条件。ThreadLocal<Integer> threadLocalVar = new ThreadLocal<>();
threadLocalVar.set(10);
int value = threadLocalVar.get();
java.util.concurrent
包中的线程安全集合,如ConcurrentHashMap
、ConcurrentLinkedQueue
等,这些集合内部已经实现了线程安全的逻辑。java.util.concurrent
包中的一些工具类可以用于控制线程间的同步和协作。例如:Semaphore
和CyclicBarrier
等。ThreadLocal
是Java中用于解决线程安全问题的一种机制,它允许创建线程局部变量,即每个线程都有自己独立的变量副本,从而避免了线程间的资源共享和同步问题。
从内存结构图,我们可以看到:
ThreadLocal的作用
ThreadLocal
为每个线程提供了独立的变量副本,这意味着线程之间不会相互影响,可以安全地在多线程环境中使用这些变量而不必担心数据竞争或同步问题。ThreadLocal
可以减少参数的传递,降低代码之间的耦合度,使代码更加清晰和模块化。ThreadLocal
避免了线程间的同步开销,所以在大量线程并发执行时,相比传统的锁机制,它可以提供更好的性能。ThreadLocal的原理
ThreadLocal
的实现依赖于Thread
类中的一个ThreadLocalMap
字段,这是一个存储ThreadLocal
变量本身和对应值的映射。每个线程都有自己的ThreadLocalMap
实例,用于存储该线程所持有的所有ThreadLocal
变量的值。
当你创建一个ThreadLocal
变量时,它实际上就是一个ThreadLocal
对象的实例。每个ThreadLocal
对象都可以存储任意类型的值,这个值对每个线程来说是独立的。
ThreadLocal
的get()
方法时,ThreadLocal
会检查当前线程的ThreadLocalMap
中是否有与之关联的值。initialValue()
方法(如果重写了的话)来初始化该值,然后将其放入ThreadLocalMap
中并返回。set()
方法时,ThreadLocal
会将给定的值与当前线程关联起来,即在当前线程的ThreadLocalMap
中存储一个键值对,键是ThreadLocal
对象自身,值是传入的值。remove()
方法时,会从当前线程的ThreadLocalMap
中移除与该ThreadLocal
对象关联的条目。可能存在的问题
当一个线程结束时,其ThreadLocalMap
也会随之销毁,但是ThreadLocal
对象本身不会立即被垃圾回收,直到没有其他引用指向它为止。
因此,在使用ThreadLocal
时需要注意,如果不显式调用remove()
方法,或者线程结束时未正确清理ThreadLocal
变量,可能会导致内存泄漏,因为ThreadLocalMap
会持续持有ThreadLocal
变量的引用,即使这些变量不再被其他地方引用。
因此,实际应用中需要在使用完ThreadLocal
变量后调用remove()
方法释放资源。
Redis 提供了丰富的数据类型,常见的有五种数据类型:String(字符串),Hash(哈希),List(列表),Set(集合)、Zset(有序集合)。
随着 Redis 版本的更新,后面又支持了四种数据类型:BitMap(2.2 版新增)、HyperLogLog(2.8 版新增)、GEO(3.2 版新增)、Stream(5.0 版新增)。Redis 五种数据类型的应用场景:
Redis 后续版本又支持四种数据类型,它们的应用场景如下:
对于读数据,我会选择旁路缓存策略,如果 cache 不命中,会从 db 加载数据到 cache。对于写数据,我会选择更新 db 后,再删除缓 存。
针对删除缓存异常的情况,我还会对 key 设置过期时间兜底,只要过期时间一到,过期的 key 就会被删除了。
除此之外,还有两种方式应对删除缓存失败的情况。
消息队列方案
我们可以引入消息队列,将第二个操作(删除缓存)要操作的数据加入到消息队列,由消费者来操作数据。
举个例子,来说明重试机制的过程。
订阅 MySQL binlog,再操作缓存
「先更新数据库,再删缓存」的策略的第一步是更新数据库,那么更新数据库成功,就会产生一条变更日志,记录在 binlog 里。
于是我们就可以通过订阅 binlog 日志,拿到具体要操作的数据,然后再执行缓存删除,阿里巴巴开源的 Canal 中间件就是基于这个实现的。
Canal 模拟 MySQL 主从复制的交互协议,把自己伪装成一个 MySQL 的从节点,向 MySQL 主节点发送 dump 请求,MySQL 收到请求后,就会开始推送 Binlog 给 Canal,Canal 解析 Binlog 字节流之后,转换为便于读取的结构化数据,供下游程序订阅使用。
下图是 Canal 的工作原理:
所以,如果要想保证「先更新数据库,再删缓存」策略第二个操作能执行成功,我们可以使用「消息队列来重试缓存的删除」,或者「订阅 MySQL binlog 再操作缓存」,这两种方法有一个共同的特点,都是采用异步操作缓存。
分布式锁是用于分布式环境下并发控制的一种机制,用于控制某个资源在同一时刻只能被一个应用所使用。
如下图所示:
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 单节点上完成了分布式锁的加锁和解锁。
当用户访问的数据,既不在缓存中,也不在数据库中,导致请求在访问缓存时,发现缓存缺失,再去访问数据库时,发现数据库中也没有要访问的数据,没办法构建缓存数据,来服务后续的请求。
那么当有大量这样的请求到来时,数据库的压力骤增,这就是缓存穿透的问题。
缓存穿透解决方案:
布隆过滤器由「初始值都为 0 的位图数组」和「 N 个哈希函数」两部分组成。当我们在写入数据库数据时,在布隆过滤器里做个标记,这样下次查询数据是否在数据库时,只需要查询布隆过滤器,如果查询到数据没有被标记,说明不在数据库中。
布隆过滤器会通过 3 个操作完成标记:
举个例子,假设有一个位图数组长度为 8,哈希函数 3 个的布隆过滤器。
在数据库写入数据 x 后,把数据 x 标记在布隆过滤器时,数据 x 会被 3 个哈希函数分别计算出 3 个哈希值,然后在对这 3 个哈希值对 8 取模,假设取模的结果为 1、4、6,然后把位图数组的第 1、4、6 位置的值设置为 1。当应用要查询数据 x 是否数据库时,通过布隆过滤器只要查到位图数组的第 1、4、6 位置的值是否全为 1,只要有一个为 0,就认为数据 x 不在数据库中。
布隆过滤器由于是基于哈希函数实现查找的,高效查找的同时存在哈希冲突的可能性,比如数据 x 和数据 y 可能都落在第 1、4、6 位置,而事实上,可能数据库中并不存在数据 y,存在误判的情况。
所以,查询布隆过滤器说数据存在,并不一定证明数据库中存在这个数据,但是查询到数据不存在,数据库中一定就不存在这个数据。
当 Redis 缓存数据量大到一台服务器无法缓存时,就需要使用 Redis 切片集群(Redis Cluster )方案,它将数据分布在不同的服务器上,以此来降低系统对单主节点的依赖,从而提高 Redis 服务的读写性能。
Redis Cluster 方案采用哈希槽(Hash Slot),来处理数据和节点之间的映射关系。在 Redis Cluster 方案中,一个切片集群共有 16384 个哈希槽,这些哈希槽类似于数据分区,每个键值对都会根据它的 key,被映射到一个哈希槽中,具体执行过程分为两大步:
接下来的问题就是,这些哈希槽怎么被映射到具体的 Redis 节点上的呢?有两种方案:
为了方便你的理解,我通过一张图来解释数据、哈希槽,以及节点三者的映射分布关系。
上图中的切片集群一共有 2 个节点,假设有 4 个哈希槽(Slot 0~Slot 3)时,我们就可以通过命令手动分配哈希槽,比如节点 1 保存哈希槽 0 和 1,节点 2 保存哈希槽 2 和 3。
redis-cli -h 192.168.1.10 –p 6379 cluster addslots 0,1
redis-cli -h 192.168.1.11 –p 6379 cluster addslots 2,3
然后在集群运行的过程中,key1 和 key2 计算完 CRC16 值后,对哈希槽总个数 4 进行取模,再根据各自的模数结果,就可以被映射到哈希槽 1(对应节点1) 和 哈希槽 2(对应节点2)。
需要注意的是,在手动分配哈希槽时,需要把 16384 个槽都分配完,否则 Redis 集群无法正常工作。
Redis集群模式优点/缺点
优点:
缺点:
TCP 是面向连接的协议,所以使用 TCP 前必须先建立连接,而建立连接是通过三次握手来进行的。三次握手的过程如下图:
从上面的过程可以发现第三次握手是可以携带数据的,前两次握手是不可以携带数据的,这也是面试常问的题。
一旦完成三次握手,双方都处于 ESTABLISHED 状态,此时连接就已建立完成,客户端和服务端就可以相互发送数据了。
在这里,我们首先给出答案,SYN是TCP头部中的一个控制位字段,该位为 1 时,表示希望建立连接,并在其「序列号」的字段进行序列号初始值的设定。
接下来让我们看看 TCP 头的格式,标注颜色的表示与本文关联比较大的字段,其他字段不做详细阐述。
序列号:在建立连接时由计算机生成的随机数作为其初始值,通过 SYN 包传给接收端主机,每发送一次数据,就「累加」一次该「数据字节数」的大小。用来解决网络包乱序问题。
确认应答号:指下一次「期望」收到的数据的序列号,发送端收到这个确认应答以后可以认为在这个序号以前的数据都已经被正常接收。用来解决丢包的问题。
控制位:
如果每个节点大于等于子树中的每个节点,我们称之为大顶堆,小于等于子树中的每个节点,我们则称之为小顶堆。
堆的要求:
堆通常是使用一维数组进行保存,节省空间,不需要存左右子节点的指针,通过下标就可定位左右节点和父节点。在起始位置为0的数组中:
我们可以把堆排序的过程大致分为两大步骤,分别是建堆和排序。
假设我们有一个数组 [4, 10, 3, 5, 1],堆排序的过程如下:
算法实现:
public class HeapSort {
// 堆排序方法
public static void heapSort(int[] arr) {
int n = arr.length;
// 构建堆(重新排列数组)
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 依次从堆中提取元素
for (int i = n - 1; i > 0; i--) {
// 将当前根节点移动到末尾
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 在堆中调整
heapify(arr, i, 0);
}
}
// 通过索引i对数组arr的前n个元素进行堆调整
private static void heapify(int[] arr, int n, int i) {
int largest = i; // 初始化最大值索引
int left = 2 * i + 1; // 左孩子节点
int right = 2 * i + 2; // 右孩子节点
// 如果左孩子大于根节点
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 如果右孩子大于当前最大值
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值不是根节点
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// 递归调整受影响的子树
heapify(arr, n, largest);
}
}
public static void main(String[] args) {
int[] arr = {4, 10, 3, 5, 1};
heapSort(arr);
System.out.println("排序后的数组:");
for (int i : arr) {
System.out.print(i + " ");
}
}
}
现在我们来分析一下堆排序的时间复杂度、空间复杂度以及稳定性。
什么是排序稳定性?
排序算法的稳定性是指在排序过程中,当有多个具有相同关键字的元素时,这些元素在排序后的序列中保持它们原有的相对顺序。
换句话说,如果两个元素有相同的键值,那么在排序前,如果第一个元素在第二个元素之前,排序后第一个元素也应该在第二个元素之前。
具体来说,对于一个序列中的两个元素A和B,如果A和B的键值相同,且在排序前A在B之前,那么在排序后A仍然应该在B之前,算法才能被称为是稳定的。例如,考虑一个包含姓名和年龄的列表:
[("Alice", 25), ("Bob", 25), ("Charlie", 20)]
如果排序算法是稳定的,那么在按年龄排序后,"Alice"和"Bob"的相对顺序不会改变:
[("Charlie", 20), ("Alice", 25), ("Bob", 25)]
但如果排序算法不稳定,"Alice"和"Bob"的相对顺序可能会在排序后改变:
[("Charlie", 20), ("Bob", 25), ("Alice", 25)]
在这种情况下,排序算法就被认为是不稳定的。