腾讯云最新社招面经出炉(面试原题+答案解析) |
您所在的位置:网站首页 › 常见面试算法题目和答案 › 腾讯云最新社招面经出炉(面试原题+答案解析) |
前言
大家好,今天给大家分享一篇腾讯云的面经,以下是面试题和答案。加油,一起卷。 聊聊项目,好的设计,好的代码 谈谈什么是零拷贝? 一共有几种 IO 模型?NIO 和多路复用的区别? Future 实现阻塞等待获取结果的原理? ReentrantLock和 Synchronized 的区别?Synchronized 的原理? 聊聊AOS?ReentrantLock的实现原理? 乐观锁和悲观锁, 让你来写你怎么实现? Paxos 协议了解?工作流程是怎么样的? B+树聊一下?B+树是不是有序?B+树和B-树的主要区别? TCP的拥塞机制 工作中有过JVM实践嘛 数据库分库分表的缺点是啥? 分布式事务如何解决?TCC 了解? RocketMQ 如何保证消息的准确性和安全性? 算法题:三个数求和 1.聊聊项目,好的设计,好的代码项目的话,你可以聊聊你平时做的项目,尤其有亮点的项目。如果没有什么特别亮点的项目,也可以说说一些好的设计,或者你优化了什么接口,性能提升了多少,优化了什么慢SQL都可以。甚至是一些好的代码写法都可以。 2. 谈谈什么是零拷贝?零拷贝是指计算机执行IO操作时,CPU不需要将数据从一个存储区域复制到另一个存储区域,从而可以减少上下文切换以及CPU的拷贝时间。它是一种I/O操作优化技术。 传统 IO 的执行流程 传统的IO流程,包括read和write的过程。 read:把数据从磁盘读取到内核缓冲区,再拷贝到用户缓冲区 write:先把数据写入到socket缓冲区,最后写入网卡设备。 用户应用进程调用read函数,向操作系统发起IO调用,上下文从用户态转为内核态(切换1) DMA控制器把数据从磁盘中,读取到内核缓冲区。 CPU把内核缓冲区数据,拷贝到用户应用缓冲区,上下文从内核态转为用户态(切换2),read函数返回 用户应用进程通过write函数,发起IO调用,上下文从用户态转为内核态(切换3) CPU将用户缓冲区中的数据,拷贝到socket缓冲区 DMA控制器把数据从socket缓冲区,拷贝到网卡设备,上下文从内核态切换回用户态(切换4),write函数返回 传统IO的读写流程,包括了4次上下文切换(4次用户态和内核态的切换),4次数据拷贝(两次CPU拷贝以及两次的DMA拷贝)。 零拷贝实现方式: 零拷贝并不是没有拷贝数据,而是减少用户态/内核态的切换次数以及CPU拷贝的次数。零拷贝一般有这三种实现方式: mmap+write sendfile 带有DMA收集拷贝功能的sendfile mmap+write mmap就是用了虚拟内存这个特点,它将内核中的读缓冲区与用户空间的缓冲区进行映射,以减少数据拷贝次数! 用户进程通过mmap方法向操作系统内核发起IO调用,上下文从用户态切换为内核态。 CPU利用DMA控制器,把数据从硬盘中拷贝到内核缓冲区。 上下文从内核态切换回用户态,mmap方法返回。 用户进程通过write方法向操作系统内核发起IO调用,上下文从用户态切换为内核态。 CPU将内核缓冲区的数据拷贝到的socket缓冲区。 CPU利用DMA控制器,把数据从socket缓冲区拷贝到网卡,上下文从内核态切换回用户态,write调用返回。 mmap+write实现的零拷贝,I/O发生了4次用户空间与内核空间的上下文切换,以及3次数据拷贝(包括了2次DMA拷贝和1次CPU拷贝)。 sendfile sendfile表示在两个文件描述符之间传输数据,它是在操作系统内核中操作的,避免了数据从内核缓冲区和用户缓冲区之间的拷贝操作 用户进程发起sendfile系统调用,上下文(切换1)从用户态转向内核态 DMA控制器,把数据从硬盘中拷贝到内核缓冲区。 CPU将读缓冲区中数据拷贝到socket缓冲区 DMA控制器,异步把数据从socket缓冲区拷贝到网卡, 上下文(切换2)从内核态切换回用户态,sendfile调用返回。 sendfile实现的零拷贝,I/O发生了2次用户空间与内核空间的上下文切换,以及3次数据拷贝。其中3次数据拷贝中,包括了2次DMA拷贝和1次CPU拷贝。 带有DMA收集拷贝功能的sendfile linux 2.4版本之后,对sendfile做了优化升级,引入SG-DMA技术,其实就是对DMA拷贝加入了scatter/gather操作,它可以直接从内核空间缓冲区中将数据读取到网卡。使用这个特点搞零拷贝,即还可以多省去一次CPU拷贝。 用户进程发起sendfile系统调用,上下文(切换1)从用户态转向内核态 DMA控制器,把数据从硬盘中拷贝到内核缓冲区。 CPU把内核缓冲区中的文件描述符信息(包括内核缓冲区的内存地址和偏移量)发送到socket缓冲区 DMA控制器根据文件描述符信息,直接把数据从内核缓冲区拷贝到网卡 上下文(切换2)从内核态切换回用户态,sendfile调用返回。 可以发现,sendfile+DMA scatter/gather实现的零拷贝,I/O发生了2次用户空间与内核空间的上下文切换,以及2次数据拷贝。其中2次数据拷贝都是包DMA拷贝。这就是真正的 零拷贝(Zero-copy) 技术,全程都没有通过CPU来搬运数据,所有的数据都是通过DMA来进行传输的。 看一遍就理解:零拷贝详解 3. 一共有几种 IO 模型?NIO 和多路复用的区别?一共有五种IO模型 阻塞IO模型 非阻塞IO模型 IO多路复用模型 IO模型之信号驱动模型 IO 模型之异步IO(AIO) NIO(非阻塞IO模型) NIO,即Non-Blocking IO,是非阻塞IO模型。非阻塞IO的流程如下: 应用进程向操作系统内核,发起recvfrom读取数据。 操作系统内核数据没有准备好,立即返回EWOULDBLOCK错误码。 应用程序进程轮询调用,继续向操作系统内核发起recvfrom读取数据。 操作系统内核数据准备好了,从内核缓冲区拷贝到用户空间。 完成调用,返回成功提示。 NIO(非阻塞IO模型)存在性能问题,即频繁的轮询,导致频繁的系统调用,同样会消耗大量的CPU资源。可以考虑IO复用模型去解决这个问题。 IO多路复用模型 IO多路复用就是,等到内核数据准备好了,主动通知应用进程再去进行系统调用。 IO复用模型核心思路:系统给我们提供一类函数(如我们耳濡目染的select、poll、epoll函数),它们可以同时监控多个fd的操作,任何一个返回内核数据就绪,应用进程再发起recvfrom系统调用。 IO多路复用之select 应用进程通过调用select函数,可以同时监控多个fd,在select函数监控的fd中,只要有任何一个数据状态准备就绪了,select函数就会返回可读状态,这时应用进程再发起recvfrom请求去读取数据。 非阻塞IO模型(NIO)中,需要N(N>=1)次轮询系统调用,然而借助select的IO多路复用模型,只需要发起一次询问就够了,大大优化了性能。 但是呢,select有几个缺点: 监听的IO最大连接数有限,在Linux系统上一般为1024。 select函数返回后,是通过遍历fdset,找到就绪的描述符fd。(仅知道有I/O事件发生,却不知是哪几个流,所以遍历所有流) 因为存在连接数限制,所以后来又提出了poll。与select相比,poll解决了连接数限制问题。但是呢,select和poll一样,还是需要通过遍历文件描述符来获取已经就绪的socket。如果同时连接的大量客户端,在一时刻可能只有极少处于就绪状态,伴随着监视的描述符数量的增长,效率也会线性下降。 IO多路复用之epoll 为了解决select/poll存在的问题,多路复用模型epoll诞生,它采用事件驱动来实现,流程图如下: epoll先通过epoll_ctl()来注册一个fd(文件描述符),一旦基于某个fd就绪时,内核会采用回调机制,迅速激活这个fd,当进程调用epoll_wait()时便得到通知。这里去掉了遍历文件描述符的坑爹操作,而是采用监听事件回调的机制。这就是epoll的亮点。 4. Future 实现阻塞等待获取结果的原理?Future.get()用于异步结果的获取。它是阻塞的,背后原理是什么呢? 我们可以看下FutureTask的类结构图: FutureTask实现了RunnableFuture接口,RunnableFuture继承了Runnable和Future这两个接口, 对于Runnable,我们太熟悉了, 那么Future呢? Future 表示一个任务的生命周期,并提供了相应的方法来判断是否已经完成或取消,以及获取任务的结果和取消任务等。 public interface Future { boolean cancel(boolean mayInterruptIfRunning); //Future 是否被取消 boolean isCancelled(); //当前 Future 是否已结束 boolean isDone(); //或取Future的结果值。如果当前 Future 还没有结束,当前线程阻塞等待, V get() throws InterruptedException, ExecutionException; //获取 Future 的结果值。与 get()一样,不过多了超时时间设置 V get(long timeout, TimeUnit unit) throws InterruptedException, ExecutionException, TimeoutException; }FutureTask 就是Runnable和Future的结合体,我们可以把Runnable看作生产者, Future 看作消费者。而FutureTask 是被这两者共享的,生产者运行run方法计算结果,消费者通过get方法获取结果。 生产者消费者模式,如果生产者数据还没准备的时候,消费者会被阻塞。当生产者数据准备好了以后会唤醒消费者继续执行。我们来看下FutureTask内部是如何实现的。 FutureTask内部维护了任务状态state //NEW 新建状态,表示FutureTask新建还没开始执行 private static final int NEW = 0; //完成状态,表示FutureTask private static final int COMPLETING = 1; //任务正常完成,没有发生异常 private static final int NORMAL = 2; //发生异常 private static final int EXCEPTIONAL = 3; //取消任务 private static final int CANCELLED = 4; //发起中断请求 private static final int INTERRUPTING = 5; //中断请求完成 private static final int INTERRUPTED = 6;生产者run方法: public void run() { // 如果状态state不是 NEW,或者设置 runner 值失败,直接返回 if (state != NEW || !UNSAFE.compareAndSwapObject(this, runnerOffset, null, Thread.currentThread())) return; try { Callable c = callable; if (c != null && state == NEW) { V result; boolean ran; try { //调用callable的call方法,获取结果 result = c.call(); //运行成功 ran = true; } catch (Throwable ex) { result = null; //运行不成功 ran = false; //设置异常 setException(ex); } //运行成功设置返回结果 if (ran) set(result); } } finally { runner = null; int s = state; if (s >= INTERRUPTING) handlePossibleCancellationInterrupt(s); } }消费者的get方法 public V get() throws InterruptedException, ExecutionException { int s = state; //如果状态小于等于 COMPLETING,表示 FutureTask 任务还没有完成, 则调用awaitDone让当前线程等待。 if (s COMPLETING) { if (q != null) q.thread = null; //返回 return s; } // 表示还有一些后序操作没有完成,那么当前线程让出执行权 else if (s == COMPLETING) // cannot time out yet Thread.yield(); //将当前线程阻塞等待 else if (q == null) q = new WaitNode(); else if (!queued) queued = UNSAFE.compareAndSwapObject(this, waitersOffset, q.next = waiters, q); //timed 为 true 表示需要设置超时 else if (timed) { nanos = deadline - System.nanoTime(); if (nanos M1)。对于 Acceptor1 来讲,这是它收到的 第一个提案。根据 P1(一个 Acceptor 必须接受它收到的 第一个提案),Acceptor1 必须接受该提案。同时 Acceptor1 认为 V2 被选定。这就出现了两个问题: Acceptor1 认为V2被选定,Acceptor2~5和Proposer2认为V1被选定。出现了不一致。 V1被选定了,但是编号更高的被Acceptor1接受的提案[M2,V2]的 value 为 V2,且 V2≠V1。这就跟 P2a(如果提案 P[M1,V1] 被接受了,那么所有比M1编号更高的,且被Acceptor接受的P,其值也是 V1。)矛盾了。 我们要对P2a约束强化一下得到约束P2b, 如果 P[M1,V1] 被选定后,任何Proposer 产生的 P,其值也是 V1。对于 P2b 中的描述,如何保证任何Proposer产生的P,其值也是V1 ?只要满足 P2c 即可: 对于任意的M和V,如果提案[M,V]被提出,那么肯定存在一个由半数以上的Acceptor组成的集合S,满足以下两个条件 中的任意一个: 要么S中每个Acceptor都没有接受过编号小于M的提案。 要么S中所有Acceptor批准的所有编号小于Mn的提案中,编号最大的那个提案的value值为Vn 8.3 算法流程8.3.1. Proposer生成提案 Prepare请求 Accept请求 在 P2c约束基础上,如何生成提案呢? Proposer选择一个新的提案编号N,向 Acceptor 集合 S(数目在半数以上)发送请求,要求 S 中的每一个 Acceptor 做出如下响应: 如果 Acceptor 没有接受过提案,则向 Proposer 保证 不再接受编号小于N的提案。 如果 Acceptor 接受过请求,则向 Proposer 返回 已经接受过的编号小于N的编号最大的提案。 我们将这个请求称为编号为N的Prepare请求。 如果Proposer收到半数以上的Acceptor 响应,则生成编号为N,value 为 V 的提案 [N,V],V 为所有响应中编号最大的提案的value。 如果 Proposer收到的响应中没有提案,那么 value 由 Proposer 自己生成,生成后将此提案发给 S,并期望Acceptor 能接受此提案。 我们称这个请求为Accept请求 8.3.2 Acceptor接受提案 一个Acceptor可能会受到来自Proposer的两种请求:Prepare请求和Accept请求。Acceptor 什么时候可以响应一个请求呢,它也有个约束:P1b: 一个Acceptor只要尚未响应过任何编号大于N的Prepare请求,那么他就可以接受这个编号为N的提案。Acceptor收到编号为 N的Prepare 请求,如果在此之前它已经响应过编号大于N的Prepare请求。由约束P1b,该Acceptor不会接受这个编号为N的提案。因此,Acceptor会忽略这个请求。 一个 Acceptor 只需记住两点:已接受的编号最大的提案和已响应的请求的最大编号。 8.3.3 Paxos算法描述 阶段一: Proposer选择一个提案编号N,然后向半数以上的Acceptor发送编号为N的Prepare请求。 如果一个Acceptor收到一个编号为N的Prepare请求,且N大于该Acceptor已经响应过的所有Prepare请求的编 号,那么它就会将它已经接受过的编号最大的提案(如果有的话)作为响应反馈给Proposer,同时该Acceptor 承诺不再接受任何编号小于N的提案。 阶段二: 如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应,那么它就会发送一个针对 [N,V]提案的Accept请求给半数以上的Acceptor。注意:V就是收到的响应中编号最大的提案的value,如果响应 中不包含任何提案,那么V就由Proposer自己决定。 如果Acceptor收到一个针对编号为N的提案的Accept请求,只要该Acceptor没有对编号大于N的Prepare请求 做出过响应,它就接受该提案。 8.3.4 Learner学习被选定的value B+树是有序的。 B+树和B-树的主要区别? B-树内部节点是保存数据的;而B+树内部节点是不保存数据的,只作索引作用,它的叶子节点才保存数据。 B+树相邻的叶子节点之间是通过链表指针连起来的,B-树却不是。 查找过程中,B-树在找到具体的数值以后就结束,而B+树则需要通过索引找到叶子结点中的数据才结束 B-树中任何一个关键字出现且只出现在一个结点中,而B+树可以出现多次。 假设有这么一个SQL: select * from Temployee where age=32;age加个一个索引,这条SQL是如何在索引上执行的?大家可以举例子画个示意图哈,比如二级索引树, 再画出id主键索引,我们先画出聚族索引结构图,如下: 因此,这条 SQL 查询语句执行大概流程就是酱紫: 搜索idx_age索引树,将磁盘块1加载到内存,由于32ssthresh时,进入了拥塞避免算法。 拥塞避免算法 一般来说,慢启动阀值ssthresh是65535字节,cwnd到达慢启动阀值后 每收到一个ACK时,cwnd = cwnd + 1/cwnd 当每过一个RTT时,cwnd = cwnd + 1 显然这是一个线性上升的算法,避免过快导致网络拥塞问题。 拥塞发生 当网络拥塞发生丢包时,会有两种情况: RTO超时重传 快速重传 如果是发生了RTO超时重传,就会使用拥塞发生算法 慢启动阀值sshthresh = cwnd /2 cwnd 重置为 1 进入新的慢启动过程 这真的是辛辛苦苦几十年,一朝回到解放前。其实还有更好的处理方式,就是快速重传。发送方收到3个连续重复的ACK时,就会快速地重传,不必等待RTO超时再重传。 image.png 慢启动阀值ssthresh 和 cwnd 变化如下: 拥塞窗口大小 cwnd = cwnd/2 慢启动阀值 ssthresh = cwnd 进入快速恢复算法 快速恢复 快速重传和快速恢复算法一般同时使用。快速恢复算法认为,还有3个重复ACK收到,说明网络也没那么糟糕,所以没有必要像RTO超时那么强烈。 正如前面所说,进入快速恢复之前,cwnd 和 sshthresh已被更新: - cwnd = cwnd /2 - sshthresh = cwnd然后,真正的快速算法如下: cwnd = sshthresh + 3 重传重复的那几个ACK(即丢失的那几个数据包) 如果再收到重复的 ACK,那么 cwnd = cwnd +1 如果收到新数据的 ACK 后, cwnd = sshthresh。因为收到新数据的 ACK,表明恢复过程已经结束,可以再次进入了拥塞避免的算法了。 Heap内存(老年代)持续上涨达到设置的最大内存值; Full GC 次数频繁; GC 停顿时间过长(超过1秒); 应用出现OutOfMemory 等内存异常; 应用中有使用本地缓存且占用大量内存空间; 系统吞吐量与响应性能不高或下降。 11.2 JVM调优的目标延迟:GC低停顿和GC低频率; 低内存占用; 高吞吐量; 11.3 JVM调优量化目标Heap 内存使用率 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |