美团中间件C++一面-面经总结

1、TCP和UDP 的区别？

速记标识符：连靠刘墉宿营
解释：
面向连接vs无连接
可靠传输vs不保证可靠
字节流vs报文传输
拥塞控制流量控制vs无
速度慢vs速度快
应用场景自己描述

2、服务端处于close wait是什么情况，是由什么造成的？

close_wait是一种状态，是收到了关闭请求，并且返回了ACK确认之后的状态。

1.客户端发起关闭请求（FIN）：客户端主动关闭连接，发送 FIN 报文给服务端。
2.服务端接收到 FIN，进入 CLOSE_WAIT 状态：服务端收到客户端的 FIN 报文后，向客户端发送一个 ACK 报文，确认收到了关闭请求。此时，服务端的状态变为 CLOSE_WAIT
3.等待服务端关闭连接：服务端的应用程序此时应该执行关闭操作（通常调用 close() 函数），发送 FIN 报文给客户端，并完成整个连接的关闭过程。

原因如下：
为什么会wait主要是因为：
1.服务端没有调用close() 没有及时关闭
2.资源泄漏或者代码缺陷
3.server的业务逻辑太复杂了

解决close_wait问题：
1.保证正确调用close
2.检查资源泄露
3.优化服务器逻辑
4.netstat和ss看看连接状态 可以看长时间是close_wait

3、讲讲三次握手和四次挥手？

第一次握手：client向server发送一个SYN 携带自己的初始化序列号。
第二次握手：server收到，以自己的SYN为应答，把自己的初始化序列号发送回client，并且把client的初始化序列号+1作为ACK返回。
第三次握手：client收到，把server的初始化序列号+1作为ACK发回server。

第一次挥手：client发送FIN给server来请求关闭连接
第二次挥手：server收到发回一个ACK 表示接收客户端关闭请求。
第三次挥手：server也发送一个FIN给client来请求关闭
第四次挥手：client收到，发送一个ACK作为应答，已经接收到了服务器的关闭请求。

4、讲讲慢启动？

探测网络的负载或者承受能力。

算法思路：由小到大逐渐增大拥塞窗口，当自己主机刚连进网络时如果一下注入太多资源可能造成网络拥塞，因此循序渐进的探测网络的拥塞程度。每收到一个确认报文拥塞窗口就增加一个报文段。

慢启动门限ssthresh(状态变量)防止拥塞窗口cwnd增长过大引起网络拥塞。

当cwnd<ssthresh，使用慢启动算法。
当cwnd>sshresh，停止使用慢启动算法而使用拥塞避免方法。
当cwnd = sshresh时既可以使用慢启动算法也可以使用拥塞避免算法。

5、ARP是哪层？

Address：数据链路层
处理IP-----MAC映射
作用：局域网内，通过IP地址查找MAC地址，在网络中进行数据帧传输。

6、TCP和UDP是哪层的？

传输层

7、分页置换算法你知道有啥？

FIFO-容易belady
LRU-最近最久
OPT-理论最优
CLOCK
LFU-最近最少使用
NRU
MFU

8、听说过page cache吗？

它通过将文件的数据缓存到内存中，减少对磁盘的直接访问，提高读写速度。

工作原理：

缓存文件内容：当应用程序从文件中读取数据时，操作系统会将这些数据存储到 Page Cache 中。下次读取相同的数据时，操作系统可以直接从内存中的 Page Cache 提供数据，而无需访问磁盘，减少 I/O 操作的延迟。
写入时缓存：对于写操作，操作系统通常不会立即将数据写入磁盘，而是先将数据写入 Page Cache。Page Cache 中的数据会在适当的时机（如内存压力大或文件关闭时）通过刷回机制写入磁盘，确保数据持久性。这种机制被称为 write-back 策略。
内存管理与回收：Page Cache 会占用系统内存，如果内存不足，操作系统会根据需求淘汰部分缓存页面，释放内存用于其他用途。

优点：

减少磁盘 I/O：通过缓存文件数据，可以大大减少对磁盘的访问，提升文件读写性能。
提高系统性能：由于内存的访问速度远快于磁盘，Page Cache 能显著减少文件操作的延迟。
Write-back 提高效率：对于写操作，Page Cache 可以减少频繁的磁盘写操作，等到适合的时机再批量写入，优化了写入性能。

运作过程：

读操作：
    当文件被读取时，操作系统首先会检查 Page Cache 是否已有相应数据。如果缓存命中，直接从 Page Cache 中返回数据。
    如果缓存未命中，则从磁盘加载页面到 Page Cache 中，并将数据返回给请求进程。
写操作：
    写操作也会被暂时存储在 Page Cache 中，数据不会立即写入磁盘。
    当内存压力增大或者文件关闭时，操作系统会将这些脏页（已被修改但尚未写回磁盘的页面）刷回磁盘，确保数据的一致性。

Page Cache 和虚拟内存：

Page Cache
是虚拟内存管理的一部分。操作系统将文件系统的页面和内存管理结合起来，通过文件映射将文件数据加载到虚拟地址空间。实际上，Page Cache
与应用程序的内存页（如进程的代码、堆栈等）共享相同的物理内存池，因此 Page Cache 的大小会根据系统内存的可用性进行动态调整。

9、满二叉树有多少个点 ？

深度为d 总数为2^d-1

10、怎么找链表上的环（快慢指针）？

这个很经典 快指针两步 慢指针一步
如果有环一定相遇 （想跑道）
没有环的话 快指针就回到nullptr

11、说说为啥用B+树，比较一下红黑树？

1.b+树只有数据存储在叶子节点，每次IO操作读取的内容更大，减少访问磁盘的次数
2.叶子节点之间还有链表连接，方便范围查询。
3.b+树多路查找，更加的矮胖，访问的节点数少。
4.查找时所有路径长度相同，查找时间更加稳定。
5.适合在磁盘或者外存，而不是红黑树的RAM

12、LSM树听说过吗？

Log-Structured Merge-tree
特别适用于需要大量写操作的场景，比如日志系统、数据库和文件系统。
LSM树的主要思想是将写操作批量化，并延迟写入磁盘，从而提高写入效率。它通过将数据分布到不同的存储层来实现高效的写入和读取。

写入操作（MemTable）：当数据写入 LSM 树时，首先会写入到内存中的一个数据结构，通常是一个跳表或平衡二叉搜索树，称为 MemTable。MemTable 是一个内存中树结构的实现，提供了快速的插入和查找操作。

数据刷新（SSTable）：当 MemTable 达到一定的大小时，它会被转换为一个不可变的数据结构，称为 Immutable MemTable。此时，MemTable 被写入到磁盘中，生成一个 SSTable（Sorted String Table） 文件。SSTable 是一种有序的数据文件，适合于高效的顺序读写。

合并操作（Merge）：随着时间的推移，多个 SSTable 文件可能会积累在磁盘中。为了保持读取性能，LSM 树会定期执行合并操作，将多个 SSTable 文件合并成更大的 SSTable 文件。这个过程称为 Compaction。

合并操作会将数据重新排序、删除重复或过时的数据，并优化存储结构，以减少后续的查询开销。

读取操作：在查询数据时，LSM 树首先会查询 MemTable，如果数据不在 MemTable 中，则会在 SSTable 文件中查找。读取操作通常会涉及到多个 SSTable 文件，但合并操作会优化查询路径，使得查询效率较高。

优势

高效的写入性能：
    写操作主要在内存中的 MemTable 进行，内存写入速度快，减少了直接对磁盘的频繁写入。
    数据写入磁盘时是批量操作，合并过程也能优化写入效率。
顺序写入优化：LSM 树的写操作是顺序写入到磁盘上的 SSTable 文件中，这对于现代存储设备（如 SSD）来说是非常高效的，因为顺序写入比随机写入性能更好。
减少磁盘碎片：合并操作可以减少磁盘碎片，优化存储布局，减少后续的读取开销。
高效的范围查询：SSTable 文件是有序的，这使得范围查询非常高效，尤其是在合并操作优化之后。

劣势

读取性能的复杂性：查询操作可能需要遍历多个 SSTable 文件，虽然合并操作能够优化查询路径，但在某些情况下，读取操作可能会比较复杂和耗时。
合并操作的开销：合并操作是一个资源密集型的过程，可能会影响系统的 I/O 性能和响应时间。

应用场景

数据库系统：如 Apache Cassandra、HBase 和 LevelDB 都使用了 LSM 树来优化写入性能和范围查询能力。
日志系统：适用于需要高效写入和读取日志数据的系统。
文件系统：用于优化文件的写入和读取操作。

13、讲讲mysql 的锁？

全局锁用于：全库逻辑备份（直接全局只读）
这个是针对MyISAM这种不支持事务的引擎。

表锁：粒度较大，但操作简单
元数据锁：用于保护对数据库对象的元数据的访问，例如表结构、索引等。
意向锁：用于协调不同粒度的锁（例如行锁和表锁）之间的冲突。

行级锁：仅锁定需要操作的具体行

14、讲一下innoDB？

innoDB是默认的引擎
1.支持ACID
2.支持牛逼的行锁，减少锁冲突
3.支持外键约束
4.有redo log崩溃后可以回复
5.支持数据压缩
6.支持四种事务隔离离别

talk is cheap，show me the code：

LC 76–最小覆盖子串