以下知识均在后台开发面试中实际出现过、总结而来。

C++

多态的实现

即虚函数表。

STL 容器库

容器库 - cppreference.com

unordered_map 和 map 的区别

略。

multimap 和 map 的区别

略。

智能指针

智能指针(现代C++) | Microsoft Docs

智能指针是对普通指针的一个封装。普通指针 new 了以后一定要 delete,而智能指针是一个类,当这个类的对象超出作用域以后,会自动调用析构函数,因此不再需要 delete,也不会因为忘记 delete 而发生内存泄露。

智能指针和普通指针的对比:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void UseRawPointer()
{
// Using a raw pointer -- not recommended.
Song* pSong = new Song(L"Nothing on You", L"Bruno Mars");

// Use pSong...

// Don't forget to delete!
delete pSong;
}


void UseSmartPointer()
{
// Declare a smart pointer on stack and pass it the raw pointer.
unique_ptr<Song> song2(new Song(L"Nothing on You", L"Bruno Mars"));

// Use song2...
wstring s = song2->duration_;
//...

} // song2 is deleted automatically here.

智能指针体现什么机制:封装。

  • unique_ptrunique_ptr 的出现是为了替代 C++98 的 auto_ptr (而 auto_ptr 于 C++11 中被弃用)。如果不知道用什么,默认用 unique_ptr 就对了。unique_ptr 只占一个指针大小的空间
  • shared_ptrshared_ptr 的管理类似于 Python 的垃圾回收机制:对变量进行计数(如下图)。拷贝构造 auto sp3(sp2); 和赋值 auto sp4 = sp2; 都会使得计数++。shared_ptr 占两个指针大小的空间
  • weak_ptrshared_ptr 中如果有循环引用,导致二者的计数都不为 0,会导致内存泄露。可以在引用的地方使用 weak_ptr 并将 shared_ptr 赋给它,这不会使得 shared_ptr 计数++,之后能被正确地回收。例子 例子2
shared_ptr
shared_ptr

数据结构

快排算法、快排的时间复杂度(平均、最坏)

数据库

MySQL 数据库引擎

  • MyISAM:读性能高,但不支持外键、行级锁和事务,MySQL 5.5 默认
  • InnoDB:读性能稍弱,支持外键、行级锁和事务,MySQL 5.5.5 及以后默认

二者都使用 B+ 树作为存储的数据结构。

B 树和 B+ 树

B 树

B 树 | 维基百科
面试官问你B树和B+树,就把这篇文章丢给他- SegmentFault 思否

先要纠正两个常见误区:

  • B 树 (B-Tree) 不是二叉树 (Binary Tree)。B 的全称,可能起源于其发明者,不过理解成平衡 (balanced) 或宽的(broad) 或 茂密(bushy) 也不错。
  • 没有 B 减树!B 减树的出现可能是翻译人员错误地将 B 树 (B-Tree) 翻译成了 B 减树。
B 树
B 树

概述:B 树是是一种自平衡的树,能够保持数据有序(听起来就是在说平衡二叉树)。其与平衡二叉树的不同在于,B 树的一个节点可以拥有 2 个以上的子节点,且节点数在某范围内可变。这样的好处有:

  1. 子结点的增多能够降低深度,减少定位记录时所经历的中间过程,运用在磁盘、数据库中可以加快存取速度;
  2. 由于节点数在范围内可变,因此 B 树不需要像其他平衡二叉查找树那样经常进行平衡

定义:一棵 m 阶 B 树的定义:

  1. 每个节点最多有 m-1 个 key;
  2. 根节点最少可以只有 1 个 key,非根节点至少有 m/2 个 key(根节点的 key 数量范围:[1, m-1],非根节点的 key 数量范围:[m/2, m-1]。);
  3. 每个节点中的 key 都按照从小到大的顺序排列,每个 key 的左子树中的所有 key 都小于它,而右子树中的所有 key 都大于它;
  4. 所有叶子节点都位于同一层(即根节点到每个叶子节点的长度都相同);
  5. 每个节点都存有索引和数据,也就是对应的 key 和 value。

B 树插入的规则:插入的时候,判断当前结点key的个数是否小于等于 m-1,如果满足,直接插入即可,如果不满足,将节点的中间的 key 将这个节点分为左右两部分,中间的节点放到父节点中即可。

B+ 树

B+ 树具有上述 B 树的前四个特点。除此之外,B+ 树还有以下特点:

  1. B 树的所有结点都存储数据,而 B+ 树只有叶子结点存储数据,内部节点(或非叶子结点、索引节点)只存放索引;
  2. B+ 树每个叶子结点存有下一个叶子结点的指针,而 B 树无,所以所有叶子结点形成了一条有序链表,遍历整棵树只需要遍历链表,而不需要从树根往下遍历。

B+ 树较 B 树的优点就是遍历快吧。

慢查询

MySQL索引原理及慢查询优化- 美团技术团队

慢查询:超过指定时间的 SQL 语句查询。

优化方法:

  1. 查看日志查看慢查询
  2. 添加索引、修改索引(如先查区分度大的)
  3. 分库、分表

聚簇索引 & 非聚簇索引

聚簇索引 & 非聚簇索引
聚簇索引 & 非聚簇索引
  • 非聚簇索引(二级索引、辅助索引):表数据和索引分成两部分存储,叶子结点存主键索引键
  • 聚簇索引:表数据和主键一起存储,主键索引的叶子结点存行数据 (包含主键值)

InnoDB 为什么推荐使用 auto_increment 作为主键

  1. auto_increment 保证能新加入的数据的主键永远是最大的,加入的数据会被放在最后。在写入量大的时候,插入数据时是连续写入,而不是随机 I/O
  2. auto_increment 使得主键和业务分离,这样即便业务上出现调整,也不需要重构数据库

事务的 ACID

ACID,是指数据库管理系统 (DBMS) 在写入或更新资料的过程中,为保证事务 (transaction) 是正确可靠的,所必须具备的四个特性:

  • 原子性 (atomicity):一个事务要么全做要么全不做;
  • 一致性 (consistency):数据处于一种有意义的状态,这种状态是语义上的而不是语法上的。最常见的例子是转帐:从帐户 A 转一笔钱到帐户 B 上,如果帐户 A 上的钱减少了,而帐户 B 上的钱却没有增加,那么我们认为此时数据处于不一致的状态;
  • 隔离性 (isolation):一个事务不影响其他事务的运行效果;
  • 持久性 (durability):事务一旦提交,则其结果就是永久性的,即使故障也能恢复。

从数据库层面,数据库通过原子性、隔离性、持久性来保证一致性。也就是说 ACID 四大特性之中,C 是目的,AID 是手段,是为了保证一致性,数据库提供的手段。

事务的原子性和持久性的保证

  1. 将所有事务开始、提交、终止,以及数据的更新操作(记录数据更新前的值即前像,或更新后的值即后像)计入 log
  2. 系统崩溃后重启,先读取日志对已提交的事务进行 REDO(保证持久性)
  3. 然后对尚未提交的的事务进行 UNDO(保证原子性)

InnoDB 事务隔离级别

MySQL 事务隔离级别和锁– IBM Developer

SQL 标准定义了四种隔离,隔离程度由高到低依次为:

  • 读未提交/脏读:未提交事务的数据也可以被读,这也被称为脏读;
  • 读提交/不可重复读:提交了的东西就可以被读,但若一个事务两次读取过程中,有事务更新了数据,会导致不可重复读;
  • 可重复读/幻读(默认):同一个事务中,select 的结果是事务开始时的状态,因此可重复读。但由于 insert 语句等不受影响,所以可能出现幻读(本事务开始后,别的事务提交了数据 pk=1,本事务 select 不到 pk=1,但 insert pk=1 会报错主键冲突,像是读到了幽灵)
  • 序列化:如果要完全解决上面的三种问题,就只能让事务串行化了,也就是把多个事务变成一个序列。
有/无问题 脏读 不可重复读 幻读
读未提交
读提交
可重复读
序列化

InnoDB 锁

MySQL 事务隔离级别和锁 - IBM Developer

Innodb中的事务隔离级别和锁的关系 - 美团技术团队(很有意思,推荐认真阅读)

数据库遵循的是两段锁协议,将事务分成两个阶段,加锁阶段和解锁阶段(所以叫两段锁)

  • 加锁阶段:在该阶段可以进行加锁操作。加锁不成功,则事务进入等待状态,直到加锁成功才继续执行。
  • 解锁阶段:当事务释放了一个封锁以后,事务进入解锁阶段,在该阶段只能进行解锁操作不能再进行加锁操作。

这种方式虽然无法避免死锁,但是两段锁协议可以保证事务的并发调度是串行化(串行化很重要,尤其是在数据恢复和备份的时候)的。

行锁

InnoDB 实现了两种类型的行级锁:

  • 共享锁 (S):在对任何数据进行读操作之前要申请并获得 S 锁。其它事务可以继续加共享锁,但不能加排它锁;
  • 独占锁 (X):在进行写操作之前要申请并获得 X 锁。其它事务不能再获得任何锁;

表锁

InnoDB 支持多粒度锁,因此 S 和 X 锁还可以锁表(如使用 ALTER TABLE 等语句会给表上 X 锁)。

另外还设计了两个意向锁,注意意向锁都是表级的

  • 意向共享锁 (IS):表明事务即将给表中的行设置 S 锁。事务给行加 S 锁前必须获得该表的 IS 锁。
  • 意向排它锁 (IX):表明事务即将给表中的行设置 X 锁。事务给行加 X 锁前必须获得该表的 IX 锁。

综上,MySQL 支持两种行锁和四种表锁。

四种表锁的兼容表如下:

锁类型 X IX S IS
X 冲突 冲突 冲突 冲突
IX 冲突 兼容 冲突 兼容
S 冲突 冲突 兼容 兼容
IS 冲突 兼容 兼容 兼容

总结一下就是:

  • 意向锁之间相互不冲突
  • 互斥锁和所有锁都冲突
  • 共享锁互斥意向锁冲突

行锁的算法

  • Record Locks:锁(单条)记录
  • Rocord Gaps:锁范围
  • Next-Key Locks:锁范围+锁记录

乐观锁和悲观锁,以及多版本并发控制

一文读懂数据库中的乐观锁和悲观锁和MVCC | MySQL 技术论坛
乐观锁和 MVCC 的区别? - 用心阁的回答 - 知乎

乐观锁和悲观锁都不是数据库锁,而是两种用于解决写-写冲突的思想。


乐观锁(又称乐观并发控制)是乐观地假设,事务间的竞争没有那么多。

乐观并发控制的一种实现是基于版本号。首先进行修改,在提交事务前,检查一下事务开始后是否有别的提交,如果没有就提交,如果有就放弃并回滚重做。

乐观并发控制多用于读多写少的场景,由于没有上锁解锁(此处指数据库锁)的过程,读的性能会很高;但在读少写多的场景,需要反复回滚重做,所以效率会变低。


悲观锁(又称悲观并发控制)是悲观地假设,事务间的竞争很多。

悲观并发控制的一种实现就是利用数据库锁,在数据库层对数据进行上锁。

悲观并发控制多用于读少写多的场景,这种场景下,不需要回滚重做而是等待,会比乐观锁好;但是上锁解锁需要消耗一定性能。


多版本并发控制(MVCC)和上面的区别是,MVCC 解决的是读-写冲突

MVCC 在各数据库中有不同的实现,在 InnoDB 中是一种无锁并发控制。InnoDB MVCC 为事务分配递增的时间戳(或者 version),更新时 version++,读操作只读该事务开始前的数据库的快照。

这样在读操作不用阻塞写操作,写操作不用阻塞读操作的同时,避免了脏读和不可重复读。

计算机网络

OSI 七层

就是把应用层拓展为(自底向上)会话层、表示层(加密相关)、应用层。

TCP 三次握手与四次挥手

TCP 三次握手与四次挥手

三次握手:

  1. 客户端:发送 SYN,进入 SYN_SEND 状态
  2. 服务器:收到包后发送 SYN ACK,进入 SYN_RCVD 状态
  3. 客户端:收到包后发送 ACK,进入 ESTABLISHED 状态(服务器接收后也进入 ESTABLISHED 状态)

三个包的 seqACKnum 数值有如下关系:

  • SYN ACK 的 ACKnum = SYN 的 seq+1
  • ACK 的 ACKnum = SYN ACK 的 seq+1
TCP 三次握手
TCP 三次握手

四次挥手并不一定是客户端发起,也可以由服务端发起。故下面用 主动关闭被动关闭 称呼:

  1. 主动关闭方:发送最后一个数据包后,发送 FIN,进入 FIN_WAIT_1
  2. 被动关闭方:收到包后发送 ACK,进入 CLOSE_WAIT;客户端收到后进入 FIN_WAIT_2,此时客户端到服务端的单方连接被关闭;
  3. 被动关闭方:发送最后一个数据包后,发送 FIN,进入 LAST_ACK
  4. 主动关闭方:收到包后发送 ACK,进入 TIME_WAIT,一段时间后关闭通信;服务端收到后立即关闭通信。

可以理解为两对 FIN - ACK,且每个 ACK 的 ACKnum = 对方的 FIN 的 seq+1。

  • CLOSE_WAIT 可以理解成对方主动关闭了连接,但本方还没有关闭,在等待关闭连接 (wait close);
  • TIME_WAIT 首先发出 FIN 的一侧,如果给对侧的 FIN 响应了 ACK,那么就会超时等待 2*MSL 时间,然后关闭连接(time wait)。在这段超时等待时间内,本地的端口不能被新连接使用;避免延时的包的到达与随后的新连接相混淆。RFC793 定义了 MSL 为2分钟(即 TIME_WAIT 等待 4 分钟)。
TCP 四次挥手
TCP 四次挥手

被动关闭的一方也可以把 ACKFIN 合并为 FIN ACK,实现三次挥手。

TCP 流量控制

TCP流量控制、拥塞控制

  • 流量控制:考虑到可能接收方处理的比较慢,需要限制发送方的发送速度。方法是,接收方发回的 ACK 中会包含自己接收窗口的大小。
  • 流量控制死锁:当发送者收到了一个窗口为 0 的应答,便停止发送,等待接收者的下一个应答。但如果之后接受者发送的窗口不为 0 的应答在传输过程丢失,发送者一直等待下去,而接收者以为发送者已经收到该应答,等待接收新数据,这样双方就相互等待,从而产生死锁。
  • 流量控制死锁避免:TCP 使用持续计时器。每当发送者收到一个零窗口的应答后就启动该计时器,时间一到便主动发送报文询问接收者的窗口大小。若接收者仍然返回零窗口,则重置该计时器继续等待;若窗口不为0,则表示应答报文丢失了,此时重置发送窗口后开始发送。

TCP 快速重传

  • 在没有快速重传机制下,如果发送方的某报文丢失,即使接受方发送了多个重复确认,发送方仍需等待重传计时器到期才会重传;
  • 快速重传机制下,发送方一旦收到三个重复确认,就重传报文,无需等待计时器到期。

TCP 拥塞控制

TCP流量控制、拥塞控制

发送方维持一个变量:拥塞窗口 (congestion window, cwnd),取决于网络拥塞情况,且动态变化。

发送方使自己的发送窗口为 $\min(cwnd, wnd_{接收方})$。

  • 慢启动阶段,cwnd=1,每成功传输一次则 cwnd*=2,直至 cwnd 到达慢启动阈值 (slow-start threshold, ssthresh),进入拥塞避免状态。
  • 拥塞避免状态,每成功传输一次则 cwnd++
  • 任何时刻,出现发送方对某报文的计时器超时,令 ssthresh=cwnd/2,cwnd=1,重新进入慢启动
  • 快速恢复:任何时刻,出现发送方接收到三个重复确认,并不按照上一条执行,而是令 ssthresh=cwnd/2, cwnd=cwnd/2+3,进入拥塞避免状态(能收到重复报文,说明网络没那么拥堵,超时才是真的拥堵)

用户从输入域名到获取到信息过程中发生了什么

a. DNS 解析的过程:计算机先检查 DNS 缓存,如果没有缓存则向 DNS 服务器查询域名对应的 IP,查询的过程分为迭代和递归两种方式;面试官接着问了 DNS 基于什么协议,答案是 UDP,服务器一般使用 53 端口;
b. 获取到 IP 以后就可以发包了,需要对包进行一层层的封装,自顶向下的封装顺序为:HTTP、TLS、TCP、IP。
c. HTTP 协议的内容大致为 HTTP/1.1 GET /
d. TLS 协议会进行 TLS 握手,主要是客户端、服务端交换密钥;
e. 再往下是 TCP 和 UDP 协议。经典一问:TCP 和 UDP 的区别(TCP 面向连接、拥塞控制、流量控制),顺便还简单问了一下拥塞控制;
f. 再往下就是 IP 层,主机会向向路由器发 IP 包、路由器根据路由表和选路算法进行转发的过程;面试官又问了有那些选路算法(分为域内和域间协议,域内有 OSPF 和 RIP,域间使用 BGP);以及路由表的最长前缀匹配原则;
e. 再往下就是物理层了。

操作系统

进程和线程的区别

  • 调度并分派的单位称为线程(或轻量级进程 LWP
  • 资源所有权的单位称为进程

进程会创建进程控制块 (PCB),而线程是线程控制块 (TCB)。由于线程没有父子进程、资源控制等结构,所以 TCB 比 PCB 简单得多,这也导致线程的创建比进程的创建快得多,大概有一个数量级的区别。

这也是平时开发中,为了利用 CPU 多线程,我们常使用多线程开发,而不是多进程开发的原因。

用户态和内核态的区别,这样有什么好处

  • 用户模式:优先权较少,用于运行用户程序
  • 内核模式:优先权更高,用于运行内核,且某些指令、内存只能在特权模式下运行/访问,如:
    • 读取/修改 PSW 等控制寄存器
    • 原始 I/O 指令
    • 内存管理相关

区分用户模式和内核模式的原因:保护 OS 和重要操作系统表不受程序干扰

用户级线程和内核级线程

用户级线程和内核级线程
用户级线程和内核级线程
  • 用户级线程:线程、线程的创建、销毁全部由库函数实现。内核不知道用户级线程的存在,依旧按照进程为单位进行调度
    • 优点:线程切换不需要内核模式,快;调度策略因应用程序不同而不同;可以运行在任何操作系统上
    • 缺点:系统调用将阻塞同一进程中的其他线程;不能利用多处理器技术
  • 内核级线程:管理线程的所有工作均由内核完成。 Windows是这种方法的一个例子。
    • 优点:ULT 两个缺点反过来说;内核本身也可以是多线程的
    • 缺点:ULT 三个优点反过来说;

进程七状态

  • 运行
  • 就绪
  • 阻塞
  • 就绪/挂起
  • 阻塞/挂起
  • New
  • Exit

僵尸进程和孤儿进程

二者都是进程派生后,父子进程其中一个退出的情况。僵尸进程是子进程退出,孤儿进程是父进程退出。

孤儿进程:父进程派生出子进程。父进程退出,但子进程还在运行,子进程就被称为孤儿进程。Unix 系统下,孤儿进程会被 init 进程收养,并在孤儿进程退出后由 init 进程对它们完成状态收集工作。孤儿进程没有什么危害。

僵尸进程:父进程 fork 出子进程。子进程退出,父进程并没有获取子进程的状态信息,子进程的进程描述符仍然留在系统中,子进程被称为僵尸进程,在 htop 的状态一栏会被标记为 Z。大量僵尸进程会占用内存空间,需要把父进程 kill 掉,僵尸进程转为孤儿进程,进而被 init 回收。

进程调度算法

  • 先来先服务 First Come First Served, FCFS
  • 时间片轮转 Round Robin, RR
  • 短进程优先 Shortest Process Next, SPN
  • 剩余时间最短优先 Shortest Remaining Time, SRT
  • 响应比高者优先 Highest Response Ratio Next, HRRN
  • 反馈 Feedback

进程切换算法

  • 保存处理器上下文(寄存器)
  • 更新当前进程的 PCB(状态、数据结构等变化)
  • 将 PCB 的指针移至相应队列(就绪、阻塞、挂起等)
  • 选择另一进程执行

线程间通信方式

同一进程的线程共享内存地址空间,没有必要依赖 OS 进行通信,但要做好同步/互斥,保护共享的全局变量。

  1. 锁机制:三种常见的锁的实现包括互斥锁、读写锁、条件变量
    • 互斥锁:提供了以排他方式防止数据结构被并发修改的方法
    • 读写锁:允许多个线程同时读共享数据,而对写操作是互斥的
    • 条件变量:可以以原子的方式阻塞进程,直到某个特定条件为真为止(对条件的测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用)
  2. 信号量 (Semaphore)
  3. 信号机制 (Signal):类似进程间的信号处理

进程间通信方式

  1. 管道(pipe),分为无名管道和有名管道
  2. 信号(signal)
  3. 消息队列
  4. 共享内存
  5. 信号量
  6. 套接字(socket)

记住上面的六个词就可以对付 60% 的面试了,30% 的可能会问一下有名管道和无名管道的区别,剩下 10% 的面试可能每个都会问一下。

如何保证缓存一致性

缓存一致性就是保证内存和缓存中的内容相同。

实现上,每一行的缓存用一个 modified 标记了是否被修改。当这行缓存将被替换时,就会将这行内容写回内存。

开发

深拷贝和浅拷贝

  • 浅拷贝是创建一个新对象,这个对象有着原始对象属性值的一份精确拷贝。如果属性是基本类型,拷贝的就是基本类型的值,如果属性是引用类型,拷贝的就是内存地址 ,所以如果其中一个对象改变了这个地址,就会影响到另一个对象。
  • 深拷贝是将一个对象从内存中完整的拷贝一份出来,从堆内存中开辟一个新的区域存放新对象,且修改新对象不会影响原对象。
浅拷贝
浅拷贝
深拷贝
深拷贝

如何进行调试

  • 利用标准输出 / log 调试;
  • 利用 IDE 单步调试;
  • 利用 assert 语句调试。

设计模式

设计模式- 廖雪峰的官方网站

设计模式的原则

  • 开闭原则:对扩展开放、对修改关闭
  • 里氏替换原则:如果对父类的调用可以成功,对子类的调用也应该成功,这也是面向对象编程的基础

Linux 命令

命令 用途
top 任务管理器
free 查看剩余内存等(不过为什么不用 top 呢)
ps 查看进程,可使用 `ps aux
kill -9 <pid> 杀进程
lsof -i:8000 查看 8000 端口的占用进程
nload 查看流量大小
wc (word count) 统计文件的字数、行数、字符数
tail --follow 实时输出(日志)文件内容
journalctl -f -u <unit.service> 实时输出日志内容
grep word file.txt find.txt 查找 word 字符串,-i 大小写不敏感
find <directory> -name 'file.txt' 在目录下查找 file.txt
df -h 查看文件剩余空间

低频考点

以下是低频考点,但是在真实面试中问过一次,读者可以按需掌握。

C++

C 语言获取当前文件夹、函数名、行数

中望龙腾 C++ 岗笔试考过。

1
2
3
4
5
6
7
8
9
10
11
12
#include<iostream>
#include<direct.h>

using namespace std;

int main()
{
cout << _getcwd(0, 0) << endl // 获取当前文件夹
<< "__FUNCSIG__:" << __FUNCSIG__ << endl // 获取函数完整签名
<< "__FUNCTION__:" << __FUNCTION__ << endl // 获取函数名
<< "__LINE__:" << __LINE__; // 获取行数
}

输出:

1
2
3
4
C:\Users\liu\Desktop\test\cpp
__FUNCSIG__:int __cdecl main(void)
__FUNCTION__:main
__LINE__:11

C 语言字节对齐

cv 限定符

cv(const 与 volatile)类型限定符 | cppreference.com

cv 限定符是 constvolatile 的合称。

当对象最初被创建时,所用的 cv 限定符决定对象的常量性或易变性。

const 大家都懂,就是不能修改的常量 (constant),直接修改会编译报错,间接修改(如利用 const_cast<int&> 等手段)为未定义行为。还有一点,就是写为 const 之后,编译器会进行优化。

volatile 翻译过来是“易变”的,表明该变量可能通过软件甚至硬件方式变化。这会阻止编译器对这个变量进行任何优化,包括但不限于:不会将变量放到寄存器中;不会对 const volatile 变量当做 const 进行优化。(不过,CPU 仍可以将变量放入缓存中,因为缓存对程序员是透明的)

代码例子见 const_cast 部分。

static 用处

C 语言的 static 有三个用处:

  1. 函数内变量使用,扩展其生存期;
  2. 函数外变量函数使用,使其他文件不能通过 extern 访问到该变量/函数(默认是可以的);
  3. 类的成员/方法使用,使得该变量/函数属于类(其他的都是属于每个对象),可以直接由类名 Classname:: 调用;

禁止继承

C++ 11 引入了 final 关键字。

1
2
3
4
5
6
7
class A final {

};

class B : public A {

}; // error: 不能选择 final 类作为基类

禁止拷贝构造函数和赋值构造函数

C++11 加入了 = delete 控制类默认函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Thing
{
public:
Thing(const Thing&) = delete;
Thing& operator = (const Thing&) = delete;
};

int main(int)
{
Thing t1; // 错误 E0291:类 "Thing" 不存在默认构造函数
Thing t2(t1); // 错误 E1776:无法引用 函数 "Thing::Thing(const Thing &)" (已声明 所在行数:4) -- 它是已删除的函数
Thing t2 = t1; // 错误 E1776:无法引用 函数 "Thing::Thing(const Thing &)" (已声明 所在行数:4) -- 它是已删除的函数
return 0;
}

C++98 前可以定义为 private

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Thing 
{
public:
private:
Thing (const Thing &);
Thing & operator = (const Thing &);
};

int main(int)
{
Thing t1;
Thing t2(t1);  //error C2248: “Thing::Thing”: 无法访问 private 成员
Thing t2 = t1; //error C2248: “Thing::Thing”: 无法访问 private 成员
return 0;
}

std::vector 和 std::array

  • vector 和 array 都是可以通过 [] 访问下标对应元素的数组;
  • vector 是变长数组,可以通过 push_back inserterase 修数组大小。(注意 inserterase 都是 $O(n)$ 的);
  • C++ vector 内存分配与回收机制
  • array 则是 C++11 引入的、对标准数组的封装,是定长数组。

Lambda 捕获值列表

Modern C++ zh-cn

分为三种:

  1. 值捕获 [value][=value]:与参数传值类似,值捕获的前提是变量可以拷贝。不同之处则在于,被捕获的变量在 Lambda 表达式被创建时拷贝, 而非调用时才拷贝。
  2. 引用捕获 [&value]:与引用传参类似,引用捕获保存的是引用,值会发生变化。
  3. 隐式捕获 [=][&]:手动书写捕获列表有时候是非常复杂的,这种机械性的工作可以交给编译器来处理,这时候可以在捕获列表中写一个 &= 向编译器声明采用引用捕获或者值捕获。(很多地方说的是捕获 this,我觉得还是这个好理解一些,毕竟如果在 main 函数中,也没有 this 一说)

总结一下,捕获提供了 Lambda 表达式对外部值进行使用的功能,捕获列表的最常用的四种形式可以是:

  1. [] 空捕获列表
  2. [name1, name2, ...] 捕获一系列变量
  3. [&] 引用捕获, 让编译器自行推导引用列表
  4. [=] 值捕获, 让编译器自行推导值捕获列表

数据结构

堆的复杂度

面腾讯的时候被问到,建堆的复杂度是多少,还好之前写过博客,还有一点点印象不是 $O(n\log n)$,而是 $O(n)$。回顾了一下博客,果然是,顺便重温了一下证明。

计算机网络

TIME_WAIT 快速回收与复用

time-wait快速回收与复用 - rosewind的博客 | BY Blog
time_wait的快速回收和重用
NAT环境下tcp_timestamps问题_〓☆〓 清风徐来918 (QQ:89617663)-CSDN博客_tcp_timestamps

这是腾讯主管问的问题,一般第二次考到的概率很小,但作为一个知识了解也不错。

TIME_WAIT 状态产生的原因在上面部分提到了,这里不再赘述。如果 TIME_WAIT 太多,导致无法对外建立新 TCP 连接。

在 Linux 下,可以从系统层面,或从应用程序层面解决这个问题。


系统层面上,也有三种方法。

一是提高 tcp_max_tw_buckets,就能接受更多的 TIME_WAIT,但是治标不治本。

二是开启 TIME_WAIT 快速回收 tcp_tw_recycle(需同时开启 tcp_timestamps,系统默认开启)。原理是在 TCP 报文中加入时间戳(时间戳在 TCP 报文中的可选字段),然后系统缓存每个连接最新的时间戳。如果收到的 TCP 报文的时间戳早于缓存值,就丢弃数据包 (RFC1323)。

快速回收的问题在于,搭配 NAT 可能会出现问题。现在很多公司都用 LVS 做负载均衡,通常是前面一台 LVS,后面多台后端服务器,这其实就是 NAT,当请求到达 LVS 后,它修改地址数据后便转发给后端服务器,但不会修改时间戳数据,对于后端服务器来说,请求的源地址就是 LVS 的地址,加上端口会复用,所以从后端服务器的角度看,原本不同客户端的请求经过 LVS 的转发,就可能会被认为是同一个连接,加之不同客户端的时间可能不一致,所以就会出现时间戳错乱的现象,于是后面的数据包就被丢弃了,具体的表现通常是是客户端明明发送的 SYN,但服务端就是不响应 ACK。如果服务器身处 NAT 环境,安全起见,通常要禁止 tcp_tw_recycle,至于TIME_WAIT连接过多的问题,可以通过 TIME_WAIT 复用解决。

三是开启 TIME_WAIT 复用 tcp_tw_reuse(也需要同时开启 tcp_timestamps)另外复用也是也是有条件的:协议认为复用是安全的。与 tcp_tw_recycle 选项相比,本选项一般不会带来副作用。


应用层面上,有两种解决办法:一是将 TCP 短连接改造为长连接,二是快速关闭 socket。

HTTP 状态码

HTTP 状态码

  • 1xx:
    • 102 Processing (WebDAV) 用于表明 WebDAV 服务器收到了请求,但请求的操作比较费时,服务器正在处理(如遍历当前文件夹)。为了防止客户端 TCP 超时、假设请求丢失,于是服务器可以发送一个没有信息的 102 应答。
  • 2xx:
    • 200 OK
    • 201 Created
    • 202 Accepted 表示正在进行一个异步操作。用于 1. 重置密码时,服务器返回 202,然后将重置邮件发送给邮箱;2. Onedrive 分段上传时,如果完成了一部分的上传,会返回 202
    • 204 No Content
    • 206 Partial Content
  • 3xx:
    • 301 302 307 308 见后
    • 304 Not Modified
  • 4xx:
    • 400 Bad Request
    • 401 Unauthorized
    • 403 Forbidden
    • 404 Not Found
    • 405 Method Not Allowed
    • 409 Conflict
    • 415 Unsupported Media Type
  • 5xx:
    • 500 Internal Server Error
    • 502 Bad Gateway 常见于 Nginx 反代的服务出锅了
    • 504 Gateway Timeout
永久重定向 Permanently 暂时重定向 Temporarily
允许将 POST 方法改为 GET 301 Moved Permanently 302 Moved Temporarily
不允许将 POST 方法改为 GET 308 Permanent Redirect 307 Temporary Redirect

HTTPS 原理及握手过程

SSL/TLS协议运行机制的概述 - 阮一峰的网络日志

  1. 客户端发送:ClientHello + 随机数 client random
  2. 服务端发送:ServerHello + 随机数 server random + 证书
  3. (客户端验证证书有效性)
  4. 客户端发送:随机数 premaster secret (经公钥加密)
  5. (服务器和客户端使用三个随机数生成一个会话密钥)
  6. 客户端发送:finished (经会话密钥加密)
  7. 服务端发送:finished (经会话密钥加密)

Nginx

Nginx为什么快到根本停不下来? - 知乎

Nginx 的进程模型
Nginx 的进程模型

Nginx 多进程

一个 Master 进程配合多个 Worker 进程

  1. Master 进程:管理 Worker 进程
    • 对外接口:接收外部的操作(信号)
    • 对内转发:根据外部的操作的不同,通过信号管理 Worker
    • 监控:监控 worker 进程的运行状态,worker 进程异常终止后,自动重启 worker 进程
  2. Worker 进程:所有 Worker 进程都是平等的
    • 实际处理:网络请求,由 Worker 进程处理;
    • Worker 进程数量:可在 nginx.conf 中配置,一般设置为核心数;

Nginx IO 多路复用

Nginx 使用epoll 多路复用

Nginx 均衡负载算法

共五种:

  1. 轮询 (Round Robin)
  2. 加权轮训,权越大表示服务器的能力越强,能承受更大负载
  3. 最小连接数 (Least Connections)
  4. IP Hash,保证同 IP 映射到同一服务器,在集群不同享 Session 时很好用
  5. URL Hash,保证同 URL 映射到同一服务器,在有 URL 缓存时效率高

Docker

Docker 底层

Docker 的底层技术

概要:Docker 使用 Linux 命名空间实现容器的隔离,使用控制组实现对容器的资源限制,使用联合文件系统提高存储效率

和虚拟机不同,Docker 进程和宿主机进程共用一个内核和某些系统库等。而彼此各个进程的方法是 Linux 上的命名空间 (Namespaces)

Docker 使用名称空间来为容器提供隔离的工作空间。当一个容器运行时,Docker 就会为该容器创建一系列的名称空间,并为名称空间提供一层隔离。

Docker 引擎也依赖另一项叫 Control groups (cgroups,控制组) 的技术。控制组可以对程序进行资源限定,并允许 Docker 引擎在容器间进行硬件资源共享以及随时进行限制和约束,如内存等。

联合文件系统 (UnionFS) 是一种分层、轻量级并且高性能的文件系统,它支持将文件系统的修改作为一次提交来一层层地叠加。不同 Docker 容器可以共享基础的文件系统层,与自己独有的改动层一起使用,可以大大提高存储效率。

I/O 多路复用

内存零拷贝