自我介绍与项目

自我介绍

面试官您好，我是西安电子科技大学的硕士研究生庄伟林，熟悉C++、网络编程、linux，了解分布式、redis等。使用C++实现了网络库和分布式kv数据库。使用go和python语言实现了服务器项目。本人也热衷于将杂乱的易忘记的知识整理成博客，累计博客达三百多篇。
（技能，三个项目，博客）
度小满：
面试官您好，我是西安电子科技大学的硕士研究生庄伟林，熟悉C++、网络编程、linux，了解分布式、redis等。使用C++实现了网络库和分布式kv数据库。使用go和python语言实现了服务器项目。实验室的linux服务器都有我管理，平时出现问题都由我进行修复。本人也热衷于将杂乱的易忘记的知识整理成博客，累计博客达三百多篇。

分布式kv数据库

本项目实现的是一个分布式kv数据库，每个服务器组处理不同的分片，通过哈希函数将不同的key对应到分片上。
本项目中，首先有一个存储配置信息的集群，配置信息用于告诉每个kv服务器组需要处理哪些分片。每个服务器组都是一个用于处理kv的集群，集群内使用raft算法实现数据的一致性。本项目采取的分片策略和redis中的槽类似。（分片，配置服务器、raft集群）
负载均衡：当有kv服务器组要退出或加入集群时，配置服务器会进行负载均衡处理，使得每个服务器处理数量相近的分片。即将分片最多的服务器组的分片分发给分片最少的服务器组，最后的效果就是分片最多的服务器组和分片最少的服务器组负责的分片数只差一。
kv服务器组会通过配置信息，从其他服务器组拉去分片对应的kv信息，拉去完了，通知其将kv信息删掉。
raft算法包括超时选举、日志复制（一致性检查）

• 超时没有收到心跳则成为候选者并向其他节点发送投票请求，当有超过半数的支持票，则当选leader。这里每个投票rpc都放在一个线程中，因为rpc需要等待对端的回应。
• 日志同步：和领导者选举一致，将每个日志同步的rpc放在一个线程中，向其他节点发送日志。然后如果日志冲突了，那么就会回退日志。

持久化操作还没有改进：每次收到数据都会进行持久化操作，可以模仿redis中的持久化操作。

网络库

网络库基本组成是一个主线程和多个子线程池，每个子线程都管理着一颗epoll树，主线程负责接收连接，并通过轮询的方式从线程池中选取一个子线程，然后将连接放入此子线程epoll树中。由于每个子线程都管理着一颗epoll树，所以每个子线程都可以用于处理多个连接。子线程不止可以用于处理连接上的事件，还可以将其他需要执行的任务放进任务队列里，然后通过eventfd提前唤醒子线程处理任务队列里的任务。
网络库会将接收到数据放进数据缓冲区中，对于数据缓冲区中数据进行解析就可以实现不同的协议，比如实现http就是解析，请求行，头部信息，实现rpc就是解析传输过来的protobuf格式的数据。
（分发、都处理多个连接、任务队列，http和rpc）。

八股

raft

• 领导者选举（超时变为candidate。根据term和log决定是否投票）、

• 日志复制（超半提交。和leader不符，找到第一个不符的，逐步覆盖）

• 安全性（“较新”的节点不能给“较旧”的节点投票、旧日志只能随着新日志的提交而提交。Follower崩溃了leader会不断发送心跳）

• 集群成员：会出现两个leader（两阶段：1.第一阶段，新老配置中获取半数以上支持）

  • 单节点集群成员变更：不会产生脑裂问题。
    通信故障导致网络分区，可能导致无法获取半数以上的支持。一种解决方法：在单节点集群成员变更中，如果老配置中有超过半数的节点支持日志提交和leader选举，就认为达到的大多数。
    连续的两次变更可能出现bug，上一个leader提交的Cnew2，被当前leader提交的Cnew1覆盖了，导致Cnew2的提交失效了。解决方法：新leader必须提交一条自己任期内的no-op日志，才能开始单节点集群成员变更。
  • 读的问题：老leader由于网络问题无法访问到其他节点，这时候client向老leader发出读请求，就会导致读取到过期的信息。解决方法：

• 把读也当做一个log

HTTP简介：

http/https：请求（请求行、头、空行、数据）、响应（状态行、头、空行、数据）

状态码（指示、成功、重定向、请求错误、服务器错误）

粘包问题（\r\n， Content-Length）

GET与POST：链接

• get会将数据缓存起来，而post不会。post用于修改和写入数据，get一般用于搜索排序和筛选之类的操作
• post在真正接收数据之前会先将请求头发送给服务器进行确认，然后才真正发送数据。post比get慢
• post更安全（不会作为url的一部分，不会被缓存、保存在服务器日志、以及浏览器浏览记录中）
• post发送的数据更大（get有url长度限制）、post能发送更多的数据类型（get只能发送ASCII字符）

强制缓存（直接存一段时间）与协商缓存（每次都问一下服务器）

HTTP/1.0(无状态、明文)、HTTP/1.1(长连接)，HTTP/2.0（二进制传输、首部压缩等，具体不知），HTTP/3.0(UDP)，HTTPS(SSL/TLS+证书)

HTTPS：

混合加密：非对称加密传输会话密钥，会话密钥加密明文。

非对称加密：公钥加密，私钥解密（会被冒充）、私钥加密，公钥解密（消息外泄）

摘要算法：使用哈希值防止内容被篡改，使用私钥加密哈希值。

数字证书：获取合法的公钥。证书有公钥和签名等，证书公钥是否合法：计算数字证书的哈希值和使用CA公钥解析签名得到的哈希值是否相同。

证书链：验证当前证书，可需要验证发放此证书方的机构是否合法。保证根证书安全。

TLS 四次握手：1.客户端向服务器索要公钥和生成会话密钥的材料（TLS版号、随机数等） 2.服务器发送材料（随机数和数字证书等） 3.客户端使用数字证书中的公钥加密信息发送给服务器，客户端根据材料制作会话密钥。并把之前所有发送的数据做个摘要，让服务器看看有什么问题没有 4.服务器根据材料制作会话密钥。并把之前所有发送的数据做个摘要，让客户端看看有什么问题没有

RSA 与ECDHE的不同在于加密算法的不同，即服务器发送的材料和制作会话过程的不同。 ECDHE使用临时密钥保证前向保密。

RPC与http：我觉得http规定了数据如何高效安全的被传递，狭义上RPC就是个远程方法调用，它为了使得调用远程方法和调用本地方法一样简单。RPC可以在http上实现，grpc就是这么做的。

HTTP是半双工的，WebSocket是全双工的。WebSocket用于游戏、网页聊天等。

C++

C++中using的四大用法总结：使用名称空间、给类型取别名（替代typedef）、修改子类中的基类的成员变量的访问权限、防止：子类中有一个函数名为A，那么父类中所有函数名为A的函数都不能用了（即使函数的参数不同）。

select（bitmap）、poll（链表）、epoll（红黑树）：从数据结构和内核拷贝分析、跨平台、边沿和水平

多态、继承、虚函数：构造函数作为虚函数（不行）、析构函数作为虚函数（delete父类指针，不调用子类析构函数）。虚函数的目的是为了让基类指针，根据指向的不同对象，而呈现不同的效果。

动态库和静态库：静态库是编译时就加载到可执行文件中的，而动态库是在程序运行时完成加载的

动态库还可以显示加载，自己控制需要加载的函数，不需要将整个库载入内存。动态库显式调用：运行时，再将库加载进来，这样就避免了将整个库加载进来。

• extern "C"声明的函数将使用函数名作符号名，就像C函数一样。以便于动态库的显示调用

智能指针：shared_ptr（多个指向同一对象）、enable_shared_from_this（在本类中传递shared_ptr出去）、unique_ptr独占，可移动，我用于减少数据拷贝，、weak_ptr：1.防止循环引用从而避免了内存泄漏（A对象以B对象为成员变量，B对象以A对象为成员变量） 2.判断指向的对象是否已被销毁

关键字：static、move（左值转右值，或者说控制权转移）、volatile：直接从内存中取此变量而不是从寄存器中、forward(t) ：传入函数的实参是左值\右值，在函数中仍是左值\右值、（future、packaged_task、async）获取线程函数的返回值或变量值。

移动构造函数、移动运算符

模板：形参的类型不确定（线程池）（不同的类型参数，就会实例化出不同的代码）、 类模板写出的函数可以在编译期被优化，删掉没有使用到的代码（模板的惰性：就是模板函数没有被使用，编译器就不会去编译函数）。

偏特化：部分模板参数固定，函数模板重载实现偏特化。类可以实现偏特化。

协程：0.函数返回值类型符合规则就是协程 1.挂起函数，恢复函数执行。2.使用co_yield（传入参数）与co_await（可定义等代体（挂起时，恢复时的执行函数））暂停，并等待恢复。

协程与线程：并发高，用户态切换。

手写代码：线程池、智能指针、生产者和消费者（虚假和错过唤醒）

Reactor：所有I/O操作都交给子线程处理。
Proactor：所有I/O操作都交给主线程或内核处理。需要向内核传⼊数据缓冲区的地址，从而直到让系统知道数据存放要存在哪里。

算法：双指针、栈、队列、unordered_map,unordered_set、二叉树、回溯算法（每层一个数组，每次收一个）：组合、切割、排列、子集、棋盘、动态规划（dp，递推、初始化）

redis

数据结构：简单动态字符串（buf[]、\0,分配多余空间）、双端链表（用于多或长）、

字典（用于多或长、哈希表、（渐进）rehash）、跳表（有序集合）、整数集合（用于少、升级）

压缩列表（用于少的哈希和列表、表示前一个结点的大小、连锁更新）

对象：字符串（int、raw、embstr）、列表（压缩列表和双端链表）、哈希（压缩列表和哈希表）、集合（整数集合和哈希表（v为NULL））和有序集合（压缩列表（多保存分值）和跳表（多保存分值））。

双端链表用于多且长，是因为数据可以分散的内存的各个区域

持久化：

AOF：alway，every，no。重写（压缩AOF 文件）：读取最新写入新文件、子进程写时复制、AOF重写缓冲区。
只要不重写，AOF每次执行只有一条或多条日志，而RDB每次需要生成整个内存的快照，较为耗时。

ROB：记录数据，而非命令。备份所有，影响性能。写时复制

AOF+ROB：RDB 方式写入到 AOF 文件，AOF 重写缓冲区中的所有内容以 AOF 方式写入到 AOF 文件。

淘汰缓存的原则：

过期删除：定期随机删除缓存（定时随机删除）+惰性删除过期缓存（访问时过期则删除）

超出内存删除：LRU（随机选取，删除最久未使用的）、LFU（随着时间变小，访问时增加，越大增加越慢）

redis：

主从节点——leader选举：哨兵监控主节点是否下线，如果下线就成为leader并请求投票，超过半数，就当选leader，通过频道发送新主节点的ip和端口

事务是什么东西？

集群：使用分片（槽），每个节点处理一个分片，每个分片对应多个key

如果key不存在，会返回信息告诉客户去哪个服务器找这个key

跳表保存key和槽的对应关系，

leader选举：选一个从节点成为leader，其他主节点投票，超过半数就成为leader。如果一个集群内节点全部丢失呢？

哈希一致性：

• 解决问题：当节点增加或减少时，无法通过哈希值找到对应的服务器
• 哈希环实现，一个节点在哈希环中有多个位置，key通过顺时针找到的第一个节点，就是处理此key的节点

缓存：

雪崩（随机数、控制请求数、集群）、击穿（热点不过期、互斥锁）、穿透（返回空、布隆）

一致性：更新数据库，删除缓存、更新缓存和数据库（锁-只能有一个在更新缓存）

布隆过滤器：多次哈希对应到位图数组上多个位置，全为一，则存在

计算机组成

进程通信：管道、消息队列、内存共享、信号量、信号、socket

进程、线程、协程的区别：
资源分配的基本单位 资源调度的基本单位 轻量级的线程
切换 页表、栈等 程序计数器、栈、寄存器等 栈和寄存器 切换代价越来越小
协程不用进入内核态，在用户态。它两陷入内核态的原因：进入内核态保存上下文信息。

死锁的四个必要条件：互斥、不可剥夺、持有并等待、环路。解决：银行家算法、资源图

运算器、控制器、存储器、输入设备、输出设备。

通用寄存器、程序计数器、指令寄存器

地址总线、数据总线、控制总线

CPU 执行程序的过程：读取指令，程序计数器加一，执行指令

存储器：寄存器、cache、内存、硬盘

cache：直接映射、cache命中率高，代码运行速度快、每次都写入内存或替换时写入内存、MESI：修，独，共，失，多核，即会检查其他核心的状态、伪共享：不同热点变量放在不同块

任务（线程）调度：deadline、抢占、普通（虚拟运行时间短的先执行）

浮点数：整数和小数转二进制——>科学计数法——>符号位、指数位（+127）、尾数（第一位1不包含）

内存管理：程序分段（外部碎片）、页表（内部碎片），本质：将地址拆分
虚拟内存：保证多个进程运行在不同的物理地址中。在物理地址上，进行可访问的空间是相互隔离的。

二级页表：将一个页表拆分成多个页表，虚拟页号前缀相同的在同一个页表中。

删除页：增加内存占用和内存访问次数、太久未访问的页表不存在内存中、快表（页表放到cache）

段页：段内使用页表。

用户空间：二进制代码区、数据区、BSS 段、堆区、栈区、全局区、常量字符串区。

互斥锁：保存和加载上下文，耗时，时间短就是用自旋锁。
自旋锁：while(CAS(lock, 0, pid))查看锁是否释放。CAS(lock, 0, pid) 就表示自旋锁的加锁操作，CAS(lock, pid, 0) 则表示解锁操作

malloc：分配比申请的字节数大的空间、释放内存的时候，缓存在 malloc 的内存池中，待下次使用。
如果使用malloc分配后的虚拟内存没有被访问的话，虚拟内存是不会映射到物理内存的，访问时在发生缺页中断。
new/delete和malloc/free：

• new/delete：编译器分配空间、调用构造函数\析构函数，存储在自由存储区
• malloc/free：自定义分配的空间的大小，存储在堆上。

堆是操作系统所维护的一块特殊内存，它提供了动态分配的功能，当运行程序调用malloc ()时就会从中分配，稍后调用free可把内存交还。 而自由存储是C++中通过new和delete动态分配和释放对象的抽象概念，通过new来申请的内存区域可称为自由存储区。 基本上，所有的C++编译器默认使用堆来实现自由存储，也即是缺省的全局运算符new和delete也许会按照malloc和free的方式来被实现，这时藉由new运算符分配的对象，说它在堆上也对，说它在自由存储区上也正确。

TCP/IP

TCP三次握手（请求，确认，确认（可带数据））。确认号 = 序号+1

• 两次握手：过期syn包会建立连接、没对服务器序列号进行确认
• 第三握手丢失没有关系
• MSS用于防止IP分片
• 其中一次握手丢失了（超时重传）
• SYN 攻击：1.增加半连接队列 2.第二次握手中带着cookie，cookie的缺点：不会重传、耗cpu

四次挥手(结束，确认（可省略），结束，确认）

• 第二次握手以后客户端还是能接收数据的
• 第三次握手的发送时机：read到结束信息或内核自己发送。开启延迟确认时第二和三可能合并发送。
• 两种关闭：关闭写、关闭读写，收到数据返回rst。
• 历史报文：随机初始化、序列号回绕、时间戳回绕
• 关闭连接老是收不到回应，则在重传多次以后，立即关闭。
• TIME_WAIT的作用：接收在链路上的报文、保证第四握手达到。
• TIME_WAIT 危害：端口和系统资源占用。tcp连接通过四元组（源IP、源端口、目的IP、目的端口）来定位，所以如果目的ip不同，端口也是能复用的。
  优化 TIME_WAIT（不建议）：1.用等了一秒的 2.重置超限的
• 服务器出现大量 TIME_WAIT 状态的原因：1.短连接 2.大量长连接超时 3.长连接超过一定数量，不再建立长连接
• HTTP长连接（一直不调用close就行，60秒内没有任何活动，就会关闭连接）、短连接（发一次，close一次，就会导致大量TIME_WAIT ）、HTTP/1.0和HTTP/1.1
• 不管哪一方禁用了 HTTP Keep-Alive，都是由服务端主动关闭连接：这样服务器端就不用一直read()等待客户端发送关闭操作。
• 服务器出现大量 CLOSE_WAIT：没有accept到连接、没有close连接
• tcp会在2个小时内没有收到数据就会发送探测报文，确定对方是否存活
• 宕机重启：rst，程序崩溃：内核发送fin
• listen执行时建立半连接队列（哈希表）和全连接队列（链表）。全连接队列满了（1.返回rst 2.重传第二次握手）
• accpet 系统调用并不参与 TCP 三次握手过程
• 没有 listen，能建立 TCP 连接：2台机器各自绑定一个本地地址和端口号，然后同时向对端绑定的端口发送connect 请求，此时就会建立TCP连接。

TCP：可靠的、面向连接的和基于流（stream）、UDP：不可靠、无连接和基于数据报（每个报文有一定长度）

TCP：可靠传输（超时重传）、流量控制（滑动窗口：告诉发送方还能接收多少数据）、发送端拥塞控制（慢开始（指数）、拥塞避免（「超过」慢启动门限，线性）、快恢复（减半））：出现超时或收到三个对同一报文的重复确认时会发生重传（快重传：三次确认以后立即重传），快恢复：出现快重传时，使用快恢复。门限值=cwnd/2，cwnd=门限值，然后线性增加。

csma/cd：载波监听多址接入/碰撞检测，二进制指数退避算法。