止步腾讯二面了，有点可惜....

2023-10-24 18:07:06 浏览数 (1)

大家好，我是小林。

之前分享了很多 Java 后端的大厂面经，有同学想知道 C 面试后端会问什么。

这次分享一位 C 同学面试腾讯一二面的面经，问的最多的是网络，其次是 C ，然后还会问一点基础的数据库，很可惜因为后端项目经验比较少，止步二面。

网络

Select 、 epoll 有什么区别？

select 实现多路复用的方式是，将已连接的 Socket 都放到一个文件描述符集合，然后调用 select 函数将文件描述符集合拷贝到内核里，让内核来检查是否有网络事件产生，检查的方式很粗暴，就是通过遍历文件描述符集合的方式，当检查到有事件产生后，将此 Socket 标记为可读或可写， 接着再把整个文件描述符集合拷贝回用户态里，然后用户态还需要再通过遍历的方法找到可读或可写的 Socket，然后再对其处理。

所以，对于 select 这种方式，需要进行 2 次「遍历」文件描述符集合，一次是在内核态里，一个次是在用户态里 ，而且还会发生 2 次「拷贝」文件描述符集合，先从用户空间传入内核空间，由内核修改后，再传出到用户空间中。

select 使用固定长度的 BitsMap，表示文件描述符集合，而且所支持的文件描述符的个数是有限制的，在 Linux 系统中，由内核中的 FD_SETSIZE 限制， 默认最大值为 1024，只能监听 0~1023 的文件描述符。

poll 不再用 BitsMap 来存储所关注的文件描述符，取而代之用动态数组，以链表形式来组织，突破了 select 的文件描述符个数限制，当然还会受到系统文件描述符限制。

但是 poll 和 select 并没有太大的本质区别，都是使用「线性结构」存储进程关注的 Socket 集合，因此都需要遍历文件描述符集合来找到可读或可写的 Socket，时间复杂度为 O(n)，而且也需要在用户态与内核态之间拷贝文件描述符集合，这种方式随着并发数上来，性能的损耗会呈指数级增长。

poll 通过两个方面，很好解决了 select/poll 的问题。

  • 第一点，epoll 在内核里使用红黑树来跟踪进程所有待检测的文件描述字，把需要监控的 socket 通过 epoll_ctl() 函数加入内核中的红黑树里，红黑树是个高效的数据结构，增删改一般时间复杂度是 O(logn)。而 select/poll 内核里没有类似 epoll 红黑树这种保存所有待检测的 socket 的数据结构，所以 select/poll 每次操作时都传入整个 socket 集合给内核，而 epoll 因为在内核维护了红黑树，可以保存所有待检测的 socket ，所以只需要传入一个待检测的 socket，减少了内核和用户空间大量的数据拷贝和内存分配。
  • 第二点， epoll 使用事件驱动的机制，内核里维护了一个链表来记录就绪事件，当某个 socket 有事件发生时，通过回调函数内核会将其加入到这个就绪事件列表中，当用户调用 epoll_wait() 函数时，只会返回有事件发生的文件描述符的个数，不需要像 select/poll 那样轮询扫描整个 socket 集合，大大提高了检测的效率。

从下图你可以看到 epoll 相关的接口作用：

img

epoll 的方式即使监听的 Socket 数量越多的时候，效率不会大幅度降低，能够同时监听的 Socket 的数目也非常的多了，上限就为系统定义的进程打开的最大文件描述符个数。因而，epoll 被称为解决 C10K 问题的利器。

TCP 三次握手和四次挥手的过程

TCP 三次握手过程：

TCP 三次握手

  • 第一次握手（SYN）：客户端发送一个带有SYN（同步）标志的数据包给服务器，请求建立连接。这个数据包中，客户端会选择一个初始的序列号并发送给服务器，用于后续数据传输的顺序控制。
  • 第二次握手（SYN-ACK）：服务器收到客户端的请求后，会回复一个带有SYN和ACK（确认）标志的数据包给客户端。在这个数据包中，服务器会确认客户端的请求，并选择一个自己的初始序列号。同时，服务器也会把客户端的初始序列号加1作为确认号发送给客户端。
  • 第三次握手（ACK）：客户端收到服务器的回复后，会发送一个带有ACK标志的数据包给服务器，用于确认服务器的确认号。在这个数据包中，客户端会把服务器的初始序列号加1作为自己的确认号发送给服务器。

TCP 四次挥手的过程如下：

在这里插入图片描述

具体过程：

  • 客户端主动调用关闭连接的函数，于是就会发送 FIN 报文，这个 FIN 报文代表客户端不会再发送数据了，进入 FIN_WAIT_1 状态；
  • 服务端收到了 FIN 报文，然后马上回复一个 ACK 确认报文，此时服务端进入 CLOSE_WAIT 状态。在收到 FIN 报文的时候，TCP 协议栈会为 FIN 包插入一个文件结束符 EOF 到接收缓冲区中，服务端应用程序可以通过 read 调用来感知这个 FIN 包，这个 EOF 会被放在已排队等候的其他已接收的数据之后，所以必须要得继续 read 接收缓冲区已接收的数据；
  • 接着，当服务端在 read 数据的时候，最后自然就会读到 EOF，接着 read() 就会返回 0，这时服务端应用程序如果有数据要发送的话，就发完数据后才调用关闭连接的函数，如果服务端应用程序没有数据要发送的话，可以直接调用关闭连接的函数，这时服务端就会发一个 FIN 包，这个 FIN 报文代表服务端不会再发送数据了，之后处于 LAST_ACK 状态；
  • 客户端接收到服务端的 FIN 包，并发送 ACK 确认包给服务端，此时客户端将进入 TIME_WAIT 状态；
  • 服务端收到 ACK 确认包后，就进入了最后的 CLOSE 状态；
  • 客户端经过 2MSL 时间之后，也进入 CLOSE 状态；

每个方向都需要一个 FIN 和一个 ACK，因此通常被称为四次挥手。

大量TIME_WAIT什么原因，怎么避免 ？

TIME_WAIT 状态是主动关闭连接方才会出现的状态，所以如果服务器出现大量的 TIME_WAIT 状态的 TCP 连接，就是说明服务器主动断开了很多 TCP 连接。

问题来了，什么场景下服务端会主动断开连接呢？

  • 第一个场景：HTTP 没有使用长连接
  • 第二个场景：HTTP 长连接超时
  • 第三个场景：HTTP 长连接的请求数量达到上限

接下来，分别介绍下。

第一个场景：HTTP 没有使用长连接

我们先来看看 HTTP 长连接（Keep-Alive）机制是怎么开启的。

在 HTTP/1.0 中默认是关闭的，如果浏览器要开启 Keep-Alive，它必须在请求的 header 中添加：

代码语言：javascript复制
Connection: Keep-Alive

然后当服务器收到请求，作出回应的时候，它也被添加到响应中 header 里：

代码语言：javascript复制
Connection: Keep-Alive

这样做，TCP 连接就不会中断，而是保持连接。当客户端发送另一个请求时，它会使用同一个 TCP 连接。这一直继续到客户端或服务器端提出断开连接。

从 HTTP/1.1 开始， 就默认是开启了 Keep-Alive，现在大多数浏览器都默认是使用 HTTP/1.1，所以 Keep-Alive 都是默认打开的。一旦客户端和服务端达成协议，那么长连接就建立好了。

如果要关闭 HTTP Keep-Alive，需要在 HTTP 请求或者响应的 header 里添加 Connection:close 信息，也就是说，只要客户端和服务端任意一方的 HTTP header 中有 Connection:close 信息，那么就无法使用 HTTP 长连接的机制。

关闭 HTTP 长连接机制后，每次请求都要经历这样的过程：建立 TCP -> 请求资源 -> 响应资源 -> 释放连接，那么此方式就是 HTTP 短连接，如下图：

HTTP 短连接

在前面我们知道，只要任意一方的 HTTP header 中有 Connection:close 信息，就无法使用 HTTP 长连接机制，这样在完成一次 HTTP 请求/处理后，就会关闭连接。

问题来了，这时候是客户端还是服务端主动关闭连接呢？

在 RFC 文档中，并没有明确由谁来关闭连接，请求和响应的双方都可以主动关闭 TCP 连接。

不过，根据大多数 Web 服务的实现，不管哪一方禁用了 HTTP Keep-Alive，都是由服务端主动关闭连接，那么此时服务端上就会出现 TIME_WAIT 状态的连接。

客户端禁用了 HTTP Keep-Alive，服务端开启 HTTP Keep-Alive，谁是主动关闭方？

当客户端禁用了 HTTP Keep-Alive，这时候 HTTP 请求的 header 就会有 Connection:close 信息，这时服务端在发完 HTTP 响应后，就会主动关闭连接。

为什么要这么设计呢？HTTP 是请求-响应模型，发起方一直是客户端，HTTP Keep-Alive 的初衷是为客户端后续的请求重用连接，如果我们在某次 HTTP 请求-响应模型中，请求的 header 定义了 connection：close 信息，那不再重用这个连接的时机就只有在服务端了，所以我们在 HTTP 请求-响应这个周期的「末端」关闭连接是合理的。

客户端开启了 HTTP Keep-Alive，服务端禁用了 HTTP Keep-Alive，谁是主动关闭方？

当客户端开启了 HTTP Keep-Alive，而服务端禁用了 HTTP Keep-Alive，这时服务端在发完 HTTP 响应后，服务端也会主动关闭连接。

为什么要这么设计呢？在服务端主动关闭连接的情况下，只要调用一次 close() 就可以释放连接，剩下的工作由内核 TCP 栈直接进行了处理，整个过程只有一次 syscall；如果是要求 客户端关闭，则服务端在写完最后一个 response 之后需要把这个 socket 放入 readable 队列，调用 select / epoll 去等待事件；然后调用一次 read() 才能知道连接已经被关闭，这其中是两次 syscall，多一次用户态程序被激活执行，而且 socket 保持时间也会更长。

因此，当服务端出现大量的 TIME_WAIT 状态连接的时候，可以排查下是否客户端和服务端都开启了 HTTP Keep-Alive，因为任意一方没有开启 HTTP Keep-Alive，都会导致服务端在处理完一个 HTTP 请求后，就主动关闭连接，此时服务端上就会出现大量的 TIME_WAIT 状态的连接。

针对这个场景下，解决的方式也很简单，让客户端和服务端都开启 HTTP Keep-Alive 机制。

第二个场景：HTTP 长连接超时

HTTP 长连接的特点是，只要任意一端没有明确提出断开连接，则保持 TCP 连接状态。

HTTP 长连接可以在同一个 TCP 连接上接收和发送多个 HTTP 请求/应答，避免了连接建立和释放的开销。

img

可能有的同学会问，如果使用了 HTTP 长连接，如果客户端完成一个 HTTP 请求后，就不再发起新的请求，此时这个 TCP 连接一直占用着不是挺浪费资源的吗？

对没错，所以为了避免资源浪费的情况，web 服务软件一般都会提供一个参数，用来指定 HTTP 长连接的超时时间，比如 nginx 提供的 keepalive_timeout 参数。

假设设置了 HTTP 长连接的超时时间是 60 秒，nginx 就会启动一个「定时器」，如果客户端在完后一个 HTTP 请求后，在 60 秒内都没有再发起新的请求，定时器的时间一到，nginx 就会触发回调函数来关闭该连接，那么此时服务端上就会出现 TIME_WAIT 状态的连接。

HTTP 长连接超时

当服务端出现大量 TIME_WAIT 状态的连接时，如果现象是有大量的客户端建立完 TCP 连接后，很长一段时间没有发送数据，那么大概率就是因为 HTTP 长连接超时，导致服务端主动关闭连接，产生大量处于 TIME_WAIT 状态的连接。

可以往网络问题的方向排查，比如是否是因为网络问题，导致客户端发送的数据一直没有被服务端接收到，以至于 HTTP 长连接超时。

第三个场景：HTTP 长连接的请求数量达到上限

Web 服务端通常会有个参数，来定义一条 HTTP 长连接上最大能处理的请求数量，当超过最大限制时，就会主动关闭连接。

比如 nginx 的 keepalive_requests 这个参数，这个参数是指一个 HTTP 长连接建立之后，nginx 就会为这个连接设置一个计数器，记录这个 HTTP 长连接上已经接收并处理的客户端请求的数量。如果达到这个参数设置的最大值时，则 nginx 会主动关闭这个长连接，那么此时服务端上就会出现 TIME_WAIT 状态的连接。

keepalive_requests 参数的默认值是 100 ，意味着每个 HTTP 长连接最多只能跑 100 次请求，这个参数往往被大多数人忽略，因为当 QPS (每秒请求数) 不是很高时，默认值 100 凑合够用。

但是，对于一些 QPS 比较高的场景，比如超过 10000 QPS，甚至达到 30000 , 50000 甚至更高，如果 keepalive_requests 参数值是 100，这时候就 nginx 就会很频繁地关闭连接，那么此时服务端上就会出大量的 TIME_WAIT 状态。

针对这个场景下，解决的方式也很简单，调大 nginx 的 keepalive_requests 参数就行。

TCP 拥塞控制算法说一下？

在网络出现拥堵时，如果继续发送大量数据包，可能会导致数据包时延、丢失等，这时 TCP 就会重传数据，但是一重传就会导致网络的负担更重，于是会导致更大的延迟以及更多的丢包，这个情况就会进入恶性循环被不断地放大....

所以，TCP 不能忽略网络上发生的事，它被设计成一个无私的协议，当网络发送拥塞时，TCP 会自我牺牲，降低发送的数据量。

于是，就有了拥塞控制，控制的目的就是避免「发送方」的数据填满整个网络。

为了在「发送方」调节所要发送数据的量，定义了一个叫做「拥塞窗口」的概念。

拥塞控制主要是四个算法：

  • 慢启动
  • 拥塞避免
  • 拥塞发生
  • 快速恢复

慢启动

TCP 在刚建立连接完成后，首先是有个慢启动的过程，这个慢启动的意思就是一点一点的提高发送数据包的数量，如果一上来就发大量的数据，这不是给网络添堵吗？

慢启动的算法记住一个规则就行：当发送方每收到一个 ACK，拥塞窗口 cwnd 的大小就会加 1。

这里假定拥塞窗口 cwnd 和发送窗口 swnd 相等，下面举个栗子：

  • 连接建立完成后，一开始初始化 cwnd = 1，表示可以传一个 MSS 大小的数据。
  • 当收到一个 ACK 确认应答后，cwnd 增加 1，于是一次能够发送 2 个
  • 当收到 2 个的 ACK 确认应答后， cwnd 增加 2，于是就可以比之前多发2 个，所以这一次能够发送 4 个
  • 当这 4 个的 ACK 确认到来的时候，每个确认 cwnd 增加 1， 4 个确认 cwnd 增加 4，于是就可以比之前多发 4 个，所以这一次能够发送 8 个。

慢启动算法的变化过程如下图：

慢启动算法

可以看出慢启动算法，发包的个数是指数性的增长。

那慢启动涨到什么时候是个头呢？

有一个叫慢启动门限 ssthresh （slow start threshold）状态变量。

  • 当 cwnd < ssthresh 时，使用慢启动算法。
  • 当 cwnd >= ssthresh 时，就会使用「拥塞避免算法」。

拥塞避免

当拥塞窗口 cwnd 「超过」慢启动门限 ssthresh 就会进入拥塞避免算法。

一般来说 ssthresh 的大小是 65535 字节。

那么进入拥塞避免算法后，它的规则是：每当收到一个 ACK 时，cwnd 增加 1/cwnd。

接上前面的慢启动的栗子，现假定 ssthresh 为 8：

  • 当 8 个 ACK 应答确认到来时，每个确认增加 1/8，8 个 ACK 确认 cwnd 一共增加 1，于是这一次能够发送 9 个 MSS 大小的数据，变成了线性增长。

拥塞避免算法的变化过程如下图：

拥塞避免

所以，我们可以发现，拥塞避免算法就是将原本慢启动算法的指数增长变成了线性增长，还是增长阶段，但是增长速度缓慢了一些。

就这么一直增长着后，网络就会慢慢进入了拥塞的状况了，于是就会出现丢包现象，这时就需要对丢失的数据包进行重传。

当触发了重传机制，也就进入了「拥塞发生算法」。

拥塞发生

当网络出现拥塞，也就是会发生数据包重传，重传机制主要有两种：

  • 超时重传
  • 快速重传

当发生了「超时重传」，则就会使用拥塞发生算法。

这个时候，ssthresh 和 cwnd 的值会发生变化：

  • ssthresh 设为 cwnd/2，
  • cwnd 重置为 1 （是恢复为 cwnd 初始化值，我这里假定 cwnd 初始化值 1）

拥塞发生算法的变化如下图：

拥塞发送 —— 超时重传

接着，就重新开始慢启动，慢启动是会突然减少数据流的。这真是一旦「超时重传」，马上回到解放前。但是这种方式太激进了，反应也很强烈，会造成网络卡顿。

还有更好的方式，前面我们讲过「快速重传算法」。当接收方发现丢了一个中间包的时候，发送三次前一个包的 ACK，于是发送端就会快速地重传，不必等待超时再重传。

TCP 认为这种情况不严重，因为大部分没丢，只丢了一小部分，则 ssthresh 和 cwnd 变化如下：

  • cwnd = cwnd/2 ，也就是设置为原来的一半;
  • ssthresh = cwnd;
  • 进入快速恢复算法

快速恢复

快速重传和快速恢复算法一般同时使用，快速恢复算法是认为，你还能收到 3 个重复 ACK 说明网络也不那么糟糕，所以没有必要像 RTO 超时那么强烈。

正如前面所说，进入快速恢复之前，cwnd 和 ssthresh 已被更新了：

  • cwnd = cwnd/2 ，也就是设置为原来的一半;
  • ssthresh = cwnd;

然后，进入快速恢复算法如下：

  • 拥塞窗口 cwnd = ssthresh 3 （ 3 的意思是确认有 3 个数据包被收到了）；
  • 重传丢失的数据包；
  • 如果再收到重复的 ACK，那么 cwnd 增加 1；
  • 如果收到新数据的 ACK 后，把 cwnd 设置为第一步中的 ssthresh 的值，原因是该 ACK 确认了新的数据，说明从 duplicated ACK 时的数据都已收到，该恢复过程已经结束，可以回到恢复之前的状态了，也即再次进入拥塞避免状态；

快速恢复算法的变化过程如下图：

快速重传和快速恢复

也就是没有像「超时重传」一夜回到解放前，而是还在比较高的值，后续呈线性增长。

解释TCP为什么是流协议？怎么分割？

当用户消息通过 TCP 协议传输时，消息可能会被操作系统分组成多个的 TCP 报文，也就是一个完整的用户消息被拆分成多个 TCP 报文进行传输。

这时，接收方的程序如果不知道发送方发送的消息的长度，也就是不知道消息的边界时，是无法读出一个有效的用户消息的，因为用户消息被拆分成多个 TCP 报文后，并不能像 UDP 那样，一个 UDP 报文就能代表一个完整的用户消息。

举个实际的例子来说明。

发送方准备发送 「Hi.」和「I am Xiaolin」这两个消息。

在发送端，当我们调用 send 函数完成数据“发送”以后，数据并没有被真正从网络上发送出去，只是从应用程序拷贝到了操作系统内核协议栈中。

至于什么时候真正被发送，取决于发送窗口、拥塞窗口以及当前发送缓冲区的大小等条件。也就是说，我们不能认为每次 send 调用发送的数据，都会作为一个整体完整地消息被发送出去。

如果我们考虑实际网络传输过程中的各种影响，假设发送端陆续调用 send 函数先后发送 「Hi.」和「I am Xiaolin」 报文，那么实际的发送很有可能是这几种情况。

第一种情况，这两个消息被分到同一个 TCP 报文，像这样：

图片

第二种情况，「I am Xiaolin」的部分随 「Hi」 在一个 TCP 报文中发送出去，像这样：

图片

第三种情况，「Hi.」 的一部分随 TCP 报文被发送出去，另一部分和 「I am Xiaolin」 一起随另一个 TCP 报文发送出去，像这样。

图片

类似的情况还能举例很多种，这里主要是想说明，我们不知道 「Hi.」和 「I am Xiaolin」 这两个用户消息是如何进行 TCP 分组传输的。

因此，我们不能认为一个用户消息对应一个 TCP 报文，正因为这样，所以 TCP 是面向字节流的协议。

当两个消息的某个部分内容被分到同一个 TCP 报文时，就是我们常说的 TCP 粘包问题，这时接收方不知道消息的边界的话，是无法读出有效的消息。

要解决这个问题，要交给应用程序。

如何解决粘包？

粘包的问题出现是因为不知道一个用户消息的边界在哪，如果知道了边界在哪，接收方就可以通过边界来划分出有效的用户消息。

一般有三种方式分包的方式：

  • 固定长度的消息；
  • 特殊字符作为边界；
  • 自定义消息结构。

1、固定长度的消息

这种是最简单方法，即每个用户消息都是固定长度的，比如规定一个消息的长度是 64 个字节，当接收方接满 64 个字节，就认为这个内容是一个完整且有效的消息。

但是这种方式灵活性不高，实际中很少用。

2、特殊字符作为边界

我们可以在两个用户消息之间插入一个特殊的字符串，这样接收方在接收数据时，读到了这个特殊字符，就把认为已经读完一个完整的消息。

HTTP 是一个非常好的例子。

图片

HTTP 通过设置回车符、换行符作为 HTTP 报文协议的边界。

有一点要注意，这个作为边界点的特殊字符，如果刚好消息内容里有这个特殊字符，我们要对这个字符转义，避免被接收方当作消息的边界点而解析到无效的数据。

3、自定义消息结构

我们可以自定义一个消息结构，由包头和数据组成，其中包头包是固定大小的，而且包头里有一个字段来说明紧随其后的数据有多大。

比如这个消息结构体，首先 4 个字节大小的变量来表示数据长度，真正的数据则在后面。

代码语言：javascript复制
struct { 
    u_int32_t message_length; 
    char message_data[]; 
} message;

当接收方接收到包头的大小（比如 4 个字节）后，就解析包头的内容，于是就可以知道数据的长度，然后接下来就继续读取数据，直到读满数据的长度，就可以组装成一个完整到用户消息来处理了。

TCP keep-alive和HTTP keep-alive 有什么区别？

HTTP 的 Keep-Alive 也叫 HTTP 长连接，该功能是由「应用程序」实现的，可以使得用同一个 TCP 连接来发送和接收多个 HTTP 请求/应答，减少了 HTTP 短连接带来的多次 TCP 连接建立和释放的开销。

TCP 的 Keepalive 也叫 TCP 保活机制，该功能是由「内核」实现的，当客户端和服务端长达一定时间没有进行数据交互时，内核为了确保该连接是否还有效，就会发送探测报文，来检测对方是否还在线，然后来决定是否要关闭该连接。

HTTP 2.0 和 HTTP1.1 有什么区别？

HTTP/2 协议是基于 HTTPS 的，所以 HTTP/2 的安全性也是有保障的。

HTT/1 ~ HTTP/2

那 HTTP/2 相比 HTTP/1.1 性能上的改进：

  • 头部压缩
  • 二进制格式
  • 并发传输
  • 服务器主动推送资源

1. 头部压缩

HTTP/2 会压缩头（Header）如果你同时发出多个请求，他们的头是一样的或是相似的，那么，协议会帮你消除重复的部分。

这就是所谓的 HPACK 算法：在客户端和服务器同时维护一张头信息表，所有字段都会存入这个表，生成一个索引号，以后就不发送同样字段了，只发送索引号，这样就提高速度了。

2. 二进制格式

HTTP/2 不再像 HTTP/1.1 里的纯文本形式的报文，而是全面采用了二进制格式，头信息和数据体都是二进制，并且统称为帧（frame）：头信息帧（Headers Frame）和数据帧（Data Frame）。

HTTP/1 与 HTTP/2

这样虽然对人不友好，但是对计算机非常友好，因为计算机只懂二进制，那么收到报文后，无需再将明文的报文转成二进制，而是直接解析二进制报文，这增加了数据传输的效率。

3. 并发传输

我们都知道 HTTP/1.1 的实现是基于请求-响应模型的。同一个连接中，HTTP 完成一个事务（请求与响应），才能处理下一个事务，也就是说在发出请求等待响应的过程中，是没办法做其他事情的，如果响应迟迟不来，那么后续的请求是无法发送的，也造成了队头阻塞的问题。

而 HTTP/2 就很牛逼了，引出了 Stream 概念，多个 Stream 复用在一条 TCP 连接。

img

从上图可以看到，1 个 TCP 连接包含多个 Stream，Stream 里可以包含 1 个或多个 Message，Message 对应 HTTP/1 中的请求或响应，由 HTTP 头部和包体构成。Message 里包含一条或者多个 Frame，Frame 是 HTTP/2 最小单位，以二进制压缩格式存放 HTTP/1 中的内容（头部和包体）。

针对不同的 HTTP 请求用独一无二的 Stream ID 来区分，接收端可以通过 Stream ID 有序组装成 HTTP 消息，不同 Stream 的帧是可以乱序发送的，因此可以并发不同的 Stream ，也就是 HTTP/2 可以并行交错地发送请求和响应。

比如下图，服务端并行交错地发送了两个响应：Stream 1 和 Stream 3，这两个 Stream 都是跑在一个 TCP 连接上，客户端收到后，会根据相同的 Stream ID 有序组装成 HTTP 消息。

img

4、服务器推送

HTTP/2 还在一定程度上改善了传统的「请求 - 应答」工作模式，服务端不再是被动地响应，可以主动向客户端发送消息。

客户端和服务器双方都可以建立 Stream， Stream ID 也是有区别的，客户端建立的 Stream 必须是奇数号，而服务器建立的 Stream 必须是偶数号。

比如下图，Stream 1 是客户端向服务端请求的资源，属于客户端建立的 Stream，所以该 Stream 的 ID 是奇数（数字 1）；Stream 2 和 4 都是服务端主动向客户端推送的资源，属于服务端建立的 Stream，所以这两个 Stream 的 ID 是偶数（数字 2 和 4）。

img

再比如，客户端通过 HTTP/1.1 请求从服务器那获取到了 HTML 文件，而 HTML 可能还需要依赖 CSS 来渲染页面，这时客户端还要再发起获取 CSS 文件的请求，需要两次消息往返，如下图左边部分：

img

如上图右边部分，在 HTTP/2 中，客户端在访问 HTML 时，服务器可以直接主动推送 CSS 文件，减少了消息传递的次数。

arp 协议有什么用？

在传输一个 IP 数据报的时候，确定了源 IP 地址和目标 IP 地址后，就会通过主机「路由表」确定 IP 数据包下一跳。然而，网络层的下一层是数据链路层，所以我们还要知道「下一跳」的 MAC 地址。

由于主机的路由表中可以找到下一跳的 IP 地址，所以可以通过 ARP 协议，求得下一跳的 MAC 地址。

那么 ARP 又是如何知道对方 MAC 地址的呢？

简单地说，ARP 是借助 ARP 请求与 ARP 响应两种类型的包确定 MAC 地址的。

ARP 广播

  • 主机会通过广播发送 ARP 请求，这个包中包含了想要知道的 MAC 地址的主机 IP 地址。
  • 当同个链路中的所有设备收到 ARP 请求时，会去拆开 ARP 请求包里的内容，如果 ARP 请求包中的目标 IP 地址与自己的 IP 地址一致，那么这个设备就将自己的 MAC 地址塞入 ARP 响应包返回给主机。

操作系统通常会把第一次通过 ARP 获取的 MAC 地址缓存起来，以便下次直接从缓存中找到对应 IP 地址的 MAC 地址。

不过，MAC 地址的缓存是有一定期限的，超过这个期限，缓存的内容将被清除。

操作系统

用户态和内核态有什么区别？

用户态是指在操作系统中运行的应用程序或用户进程所处的执行模式。在用户态下，进程只能访问受限的资源和执行受限的操作，不能直接访问或控制系统的关键资源和硬件设备。用户态下的进程不能执行特权指令，例如访问硬件设备、修改内存页表等操作，这些操作需要特权级别更高的内核态才能执行。

内核态是操作系统内核所处的执行模式。在内核态下，操作系统具有完全的控制权和访问权限，可以执行任意的特权指令，访问系统的关键资源和硬件设备。内核态下的操作系统可以管理进程、内存、文件系统、设备驱动等系统资源，处理中断和异常等系统级任务。

区别：

  1. 权限和特权级别：用户态下的应用程序只能访问受限的资源和执行受限的操作，而内核态下的操作系统具有完全的控制权和特权级别，可以执行任意的特权指令。
  2. 可执行的操作：用户态下的应用程序不能直接访问硬件设备和系统关键资源，而内核态下的操作系统可以执行和管理这些操作。
  3. 安全性和稳定性：通过将操作系统和应用程序的运行环境隔离开来，用户态和内核态之间的切换提供了更高的安全性和稳定性，防止应用程序对系统造成破坏或崩溃。

linux 进程的内存结构说一下？

在 Linux 操作系统中，虚拟地址空间的内部又被分为内核空间和用户空间两部分，不同位数的系统，地址空间的范围也不同。比如最常见的 32 位和 64 位系统，如下所示：

img

通过这里可以看出：

  • 32 位系统的内核空间占用 1G，位于最高处，剩下的 3G 是用户空间；
  • 64 位系统的内核空间和用户空间都是 128T，分别占据整个内存空间的最高和最低处，剩下的中间部分是未定义的。

用户空间分布的情况，以 32 位系统为例，我画了一张图来表示它们的关系：

虚拟内存空间划分

通过这张图你可以看到，用户空间内存，从低到高分别是 6 种不同的内存段：

  • 代码段，包括二进制可执行代码；
  • 数据段，包括已初始化的静态常量和全局变量；
  • BSS 段，包括未初始化的静态变量和全局变量；
  • 堆段，包括动态分配的内存，从低地址开始向上增长；
  • 文件映射段，包括动态库、共享内存等，从低地址开始向上增长；
  • 栈段，包括局部变量和函数调用的上下文等。栈的大小是固定的，一般是 8 MB。当然系统也提供了参数，以便我们自定义大小；

上图中的内存布局可以看到，代码段下面还有一段内存空间的（灰色部分），这一块区域是「保留区」，之所以要有保留区这是因为在大多数的系统里，我们认为比较小数值的地址不是一个合法地址，例如，我们通常在 C 的代码里会将无效的指针赋值为 NULL。因此，这里会出现一段不可访问的内存保留区，防止程序因为出现 bug，导致读或写了一些小内存地址的数据，而使得程序跑飞。

在这 7 个内存段中，堆和文件映射段的内存是动态分配的。比如说，使用 C 标准库的 malloc() 或者 mmap() ，就可以分别在堆和文件映射段动态分配内存。

堆与栈有什么区别？

  • 管理方式：栈的管理由编译器自动完成，通过分配和释放栈帧来管理栈上的变量。而堆的管理需要手动进行，程序员负责分配和释放堆上的内存。
  • 内存分配：栈上的内存分配是连续的，以栈指针为基准，每次分配的内存大小是固定的，而且自动释放。堆上的内存分配是动态的，大小不固定，需要手动分配和释放。
  • 存储内容：栈主要用于存储局部变量、函数调用、函数返回地址等临时数据，它们的生命周期与函数的调用和返回相关。而堆用于存储动态分配的数据，如对象、数组等，它们的生命周期由程序员控制。
  • 空间大小：栈的空间通常比较小，因为它受限于系统的栈大小和函数调用的嵌套深度。而堆的空间较大，通常受限于系统的可用内存大小。

C

Std::sort的底层是怎么实现的？

std::sort主要是三种算法的结合体：插入排序，快速排序，堆排序。

算法

时间复杂度

优点

缺点

插入排序

O(N*N)

当数据量很少时，效率比较高。

当数据量比较大时，时间复杂度比较高。

快速排序

平均 O(NlogN)，最坏 O(NN)

大部分时候性能比较好。

算法时间复杂度不稳定，数据量大时递归深度很大，影响程序工作效率。

堆排序

O(N*logN)

算法时间复杂度稳定，比较小，适合数据量比较大的排序。

堆排序在建堆和调整堆的过程中会产生比较大的开销，数据量少的时候不适用。

std::sort 根据上文提到的几种算法的优缺点，对排序算法进行整合。

  1. 快速排序，递归排序到一定深度后，数据已经被分为多个子区域，子区域里面的数据可能是无序的，但是子区域之间已经是有序了。
  2. 在这多个子区域里，如果某个子区域数据个数大于阈值（16），采用堆排序，使得某个子区域内部有序。
  3. 剩下的没有被堆排序的小区域，数据量都是小于阈值的，最后整个数据区域采用插入排序。
  1. std::sort 采用的是分治思维，先采用快速排序，将整个区域分成多个子区域，每个子区域内部根据数据量采用不同算法。
  2. 分治后，各个子区域局部有序后再通过整个区域进行排序。

智能指针有哪些？

在C 中，有三种常用的智能指针：std::unique_ptr、std::shared_ptr和std::weak_ptr。

  • std::unique_ptr：std::unique_ptr是一种独占所有权的智能指针。它通过使用独占所有权的方式来管理资源，只能有一个std::unique_ptr指向同一个对象或数组。当std::unique_ptr超出作用域或被显式释放时，它会自动删除所管理的对象或数组。它通常用于表示独占的资源所有权，如动态分配的单个对象或数组。
  • std::shared_ptr：std::shared_ptr是一种共享所有权的智能指针。它可以有多个std::shared_ptr指向同一个对象，通过引用计数来管理资源的生命周期。只有当最后一个std::shared_ptr超出作用域或被显式释放时，资源才会被删除。std::shared_ptr允许多个指针共享对同一资源的访问，通常用于表示共享的资源所有权。
  • std::weak_ptr：std::weak_ptr是一种弱引用的智能指针。它可以指向由std::shared_ptr管理的对象，但不会增加引用计数。std::weak_ptr主要用于解决std::shared_ptr的循环引用问题，通过std::weak_ptr.lock()方法可以获取一个有效的std::shared_ptr来访问被管理的对象。

delete和free的区别

  • new/delete是C 的操作符，而malloc/free是C中的函数。
  • new做两件事，一是分配内存，二是调用类的构造函数；同样，delete会调用类的析构函数和释放内存。而malloc和free只是分配和释放内存。
  • new建立的是一个对象，而malloc分配的是一块内存；new建立的对象可以用成员函数访问，不要直接访问它的地址空间；malloc分配的是一块内存区域，用指针访问，可以在里面移动指针；new出来的指针是带有类型信息的，而malloc返回的是void指针。
  • new/delete是保留字，不需要头文件支持；malloc/free需要头文件库函数支持。

内存泄露怎么检测？

可以用 Valgrind 工具。

首先看一段 C 程序示例，比如：

代码语言：javascript复制
#include <stdlib.h>
int main()
{
    int *array = malloc(sizeof(int));
    return 0;
}

编译程序：gcc -g -o main main.c，比哪一需要加上 -g 选项打开调试，使用 IDE 的可以用 Debug 模式编译。

使用 Valgrind 检测内存使用情况：

代码语言：javascript复制
valgrind --tool=memcheck --leak-check=full ./main

结果：

代码语言：javascript复制
==31416== Memcheck, a memory error detector
==31416== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==31416== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==31416== Command: ./main_c
==31416==
==31416==
==31416== HEAP SUMMARY:
==31416==     in use at exit: 4 bytes in 1 blocks
==31416==   total heap usage: 1 allocs, 0 frees, 4 bytes allocated
==31416==
==31416== 4 bytes in 1 blocks are definitely lost in loss record 1 of 1
==31416==    at 0x4C2DBF6: malloc (vg_replace_malloc.c:299)
==31416==    by 0x400537: main (main.c:5)
==31416==
==31416== LEAK SUMMARY:
==31416==    definitely lost: 4 bytes in 1 blocks
==31416==    indirectly lost: 0 bytes in 0 blocks
==31416==      possibly lost: 0 bytes in 0 blocks
==31416==    still reachable: 0 bytes in 0 blocks
==31416==         suppressed: 0 bytes in 0 blocks
==31416==
==31416== For counts of detected and suppressed errors, rerun with: -v
==31416== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

先看看输出信息中的 HEAP SUMMARY，它表示程序在堆上分配内存的情况，其中的 1 allocs 表示程序分配了 1 次内存，0 frees 表示程序释放了 0 次内存，4 bytes allocated 表示分配了 4 个字节的内存。

另外，Valgrind 也会报告程序是在哪个位置发生内存泄漏。例如，从下面的信息可以看到，程序发生了一次内存泄漏，位置是 main.c 文件的第 5 行：

代码语言：javascript复制
==31416== 4 bytes in 1 blocks are definitely lost in loss record 1 of 1
==31416==    at 0x4C2DBF6: malloc (vg_replace_malloc.c:299)
==31416==    by 0x400537: main (main.c:5)

函数传参用引用的作用是什么？

可以避免避免拷贝，使用引用传参可以避免对大型对象进行复制。如果传递一个对象作为值参数，会触发对象的拷贝构造函数，造成额外的开销。而使用引用传参，可以直接在函数中操作原始对象，避免了拷贝操作。

数据库

索引的数据结构有哪些？

MySQL 常见索引有 B Tree 索引、HASH 索引、Full-Text 索引。

每一种存储引擎支持的索引类型不一定相同，我在表中总结了 MySQL 常见的存储引擎 InnoDB、MyISAM 和 Memory 分别支持的索引类型。

img

InnoDB 是在 MySQL 5.5 之后成为默认的 MySQL 存储引擎，B Tree 索引类型也是 MySQL 存储引擎采用最多的索引类型。

主键索引 B Tree

事务的ACID是什么？怎么实现的？

  • 原子性（Atomicity）：一个事务中的所有操作，要么全部完成，要么全部不完成，不会结束在中间某个环节，而且事务在执行过程中发生错误，会被回滚到事务开始前的状态，就像这个事务从来没有执行过一样，就好比买一件商品，购买成功时，则给商家付了钱，商品到手；购买失败时，则商品在商家手中，消费者的钱也没花出去。
  • 一致性（Consistency）：是指事务操作前和操作后，数据满足完整性约束，数据库保持一致性状态。比如，用户 A 和用户 B 在银行分别有 800 元和 600 元，总共 1400 元，用户 A 给用户 B 转账 200 元，分为两个步骤，从 A 的账户扣除 200 元和对 B 的账户增加 200 元。一致性就是要求上述步骤操作后，最后的结果是用户 A 还有 600 元，用户 B 有 800 元，总共 1400 元，而不会出现用户 A 扣除了 200 元，但用户 B 未增加的情况（该情况，用户 A 和 B 均为 600 元，总共 1200 元）。
  • 隔离性（Isolation）：数据库允许多个并发事务同时对其数据进行读写和修改的能力，隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致，因为多个事务同时使用相同的数据时，不会相互干扰，每个事务都有一个完整的数据空间，对其他并发事务是隔离的。也就是说，消费者购买商品这个事务，是不影响其他消费者购买的。
  • 持久性（Durability）：事务处理结束后，对数据的修改就是永久的，即便系统故障也不会丢失。

InnoDB 引擎通过什么技术来保证事务的这四个特性的呢？

  • 持久性是通过 redo log （重做日志）来保证的；
  • 原子性是通过 undo log（回滚日志） 来保证的；
  • 隔离性是通过 MVCC（多版本并发控制） 或锁机制来保证的；
  • 一致性则是通过持久性 原子性 隔离性来保证；

事务隔离级别有哪些？按照性能排序是怎么样的？

四个隔离级别如下：

  • 读未提交），指一个事务还没提交时，它做的变更就能被其他事务看到；
  • 读提交，指一个事务提交之后，它做的变更才能被其他事务看到；
  • 可重复读，指一个事务执行过程中看到的数据，一直跟这个事务启动时看到的数据是一致的，MySQL InnoDB 引擎的默认隔离级别；
  • 串行化；会对记录加上读写锁，在多个事务对这条记录进行读写操作时，如果发生了读写冲突的时候，后访问的事务必须等前一个事务执行完成，才能继续执行；

按隔离水平高低排序如下：

图片

后端

分布式生成唯一ID，除了UUID方案，你还知道什么？

1、Redis生成ID

Redis是单线程的，所以也可以用生成全局唯一的ID。可以用Redis的原子操作 INCR和INCRBY来实现。优势是不依赖于数据库，使用灵活，性能也优于数据库；而缺点则是可能要引入新的组件 Redis，如果 Redis 出现单点故障问题，则会影响序号服务的可用性。

2、Zookeeper 生成 ID

主要是利用 Zookeeper 的 znode 数据版本来生成序列号，可以生成 32 位和 64 位的数据版本号，客户端可以使用这个版本号来作为唯一的序列号。由于需要依赖 zookeeper，并且是多步调用 API，如果在竞争较大的情况下，可能需要考虑使用分布式锁，故此种生成唯一 ID 的方法的性能在高并发的分布式环境下不甚理想。

3、snowflake雪花算法生成ID

把64-bit分别划分成多段，分开来标示机器、时间等，比如在snowflake中的64-bit分别表示如下图所，

雪花算法把玩- Yang Blog

snowflake 算法的核心思想是使用 41bit 作为毫秒数，10bit 作为机器的 ID（比如其中 5 个 bit 可作为数据中心，5 个 bit 作为机器 ID）,12bit 作为毫秒内的流水号（意味着每个节点在每毫秒可以产生 4096 个 ID），最后还有一个符号位，永远是 0。理论上snowflake方案的QPS约为409.6w/s，这种分配方式可以保证在任何一台机器在任意毫秒内生成的ID都是不同的。缺点：强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。

3、美团 Leaf 分布式ID生成服务

Leaf 也提供了两种ID生成的方式，分别是 Leaf-segment 数据库方案和 Leaf-snowflake 方案。

Leaf-segment 号段模式

号段模式可以理解成从数据库批量获取 ID，然后将 ID 缓存在本地，以此来提高业务获取 ID 的效率。例如，每次从数据库获取 ID 时，获取一个号段，如(1,1000]，这个范围表示 1000 个 ID，业务应用在请求获取 ID 时，只需要在本地从 1 开始自增并返回，而不用每次去请求数据库，一直到本地自增到 1000 时，才去数据库重新获取新的号段，后续流程循环往复。

Leaf-segment 号段模式是对直接用数据库自增 ID 充当分布式 ID 的一种优化，减少对数据库的访问频率。相当于每次从数据库批量的获取自增 ID。

Leaf-server 采用了预分发的方式生成 ID，即可以在 DB 之上挂 N 个 Server，每个 Server 启动时，都会去 DB 拿固定长度的 ID List。这样就做到了完全基于分布式的架构，同时因为 ID 是由内存分发，所以也可以做到很高效。接下来是数据持久化问题，Leaf 每次去 DB 拿固定长度的 ID List，然后把最大的 ID 持久化下来，也就是并非每个 ID 都做持久化，仅仅持久化一批 ID 中最大的那一个。其流程如下图所示：

img

Leaf-server 中缓存的号段耗尽之后再去数据库获取新的号段，可以大大地减轻数据库的压力。对 max_id 字段做一次 update 操作，update max_id = max_id step，update 成功则说明新号段获取成功，新的号段范围为(max_id, max_id step]。

为了解决从数据库获取新的号段阻塞业务获取 ID 的流程的问题，Leaf-server 中采用了异步更新的策略，同时通过双 buffer 的方式，如下图所示。通过这样一种机制可以保证无论何时 DB 出现问题，都能有一个 buffer 的号段可以正常对外提供服务，只有 DB 在一个 buffer 的下发周期内恢复，都不会影响这个 Leaf 集群的可用性。

img

Leaf-snowflake 方案

Leaf-snowflake 方案沿用 snowflake 方案的 bit 位设计，即”1 41 10 12“的方式组装 ID 号（正数位（占 1 比特） 时间戳（占 41 比特） 机器 ID（占 5 比特） 机房 ID（占 5 比特） 自增值（占 12 比特）），如下图所示：

img

对于 workerID 的分配，当服务集群较小时，通过配置即可；当服务集群较大时，基于 zookeeper 持久顺序节点的特性引入 zookeeper 组件配置 workerID。部署架构如下图所示：

img

Leaf-snowflake 方案在处理时钟回拨问题的策略如下所示：

1）服务启动时

  • 在服务启动时，首先检查自己是否写过 zookeeper leaf_forever 节点；
  • 如果写过，则用自身系统时间与 leaf_forever/${self}节点记录时间做比较，若小于则认为机器时间发生了大步长回拨，服务启动失败并告警；
  • 如果没有写过，直接创建持久节点 leaf_forever/${self}，并写入自身系统时间；
  • 然后取 leaf_temporary 下的所有临时节点(所有运行中的 Leaf-snowflake 节点)的服务 IP：Port，然后通过 RPC 请求得到所有节点的系统时间，计算 sum(time)/nodeSize；
  • 如果若 abs( 系统时间-sum(time)/nodeSize ) < 阈值，认为当前系统时间准确，正常启动服务，同时写临时节点 leaf_temporary/${self} 维持租约；否则认为本机系统时间发生大步长偏移，启动失败并报警；
  • 每隔一段时间(3s)上报自身系统时间写入 leaf_forever/${self}。

2）服务运行时

  • 会检查时钟回拨时间是否小于 5ms，若时钟回拨时间小于等于 5ms，等待时钟回拨时间后，重新产生新的 ID；若时钟回拨时间大于 5ms，直接抛异常给到业务侧。

算法

  • 算法：最长公共子串
  • 算法：包含所有元素的不重复连续子串
服务端 客户端 连接 数据 腾讯

0 人点赞