【面试题】技术面试题汇总

• 不同类型的锁：互斥锁、读写锁、自旋锁、条件锁。
• Java 中的锁类型：
  • 公平锁/非公平锁
  • 可重入锁
  • 独享锁/共享锁
  • 互斥锁/读写锁
  • 乐观锁/悲观锁
  • 分段锁
  • 偏向锁/轻量级锁/重量级锁
  • 自旋锁
• 互斥锁的实现方式：答案

(1) 死锁产生的四个必要条件

• 互斥条件
• 占有且等待条件：线程占有已经分配给它们的资源（如锁）并且等待其他的资源（也就是说不会主动释放）
• 不可抢占条件（也就是说不会被动释放）
• 环路等待条件：每个进程都在等待下一个进程占有的资源

这四个条件缺少一个就不会有死锁。

(2) 预防死锁

预防死锁就是破坏上面四个条件任意一个，但是实现很难：

• 破坏互斥条件：允许某些资源同时被多个进程访问。但是有些资源本身并不具有这种属性，因此这种方案实用性有限
• 破坏占有并等待条件：
  • 实行资源预先分配策略（当一个进程开始运行之前，必须一次性向系统申请它所需要的全部资源，否则不运行）
  • 或者只允许进程在没有占用资源的时候才能申请资源（申请资源前先释放占有的资源）
  • 缺点：很多时候无法预知一个进程所需的全部资源；同时，会降低资源利用率，降低系统的并发性
• 破坏非抢占条件：允许进程强行抢占被其它进程占有的资源。会降低系统性能
• 破坏循环等待条件：对所有资源统一编号，所有进程对资源的请求必须按照序号递增的顺序提出，即只有占有了编号较小的资源才能申请编号较大的资源。这样避免了占有大号资源的进程去申请小号资源，各个进程申请资源的顺序都是从小到大，就不会有环了

(3) 避免死锁

允许系统中同时存在四个必要条件，但是每当进程提出资源申请时，系统要分析满足该资源请求后，系统是否会发生死锁，若不会发生则实施分配，否则拒绝分配。银行家算法实现了这个过程。

(4) 检测死锁

画出资源分配图，检测是否存在环路。检测环路前要将资源分配图化简，化简的原理是“一个目前占有运行所需的资源的进程，迟早能够执行完成释放资源”。因此，可以从“进程—资源分配图”中找到一个既不阻塞又非孤立的进程，删除所有与该进程相连的有向边，回收资源，使之成为孤立结点，然后将所回收的资源分配给其它进程。循环此过程，直到无法化简。若仍存在环路，则该系统目前处于死锁状态。

检测到死锁后，需要解除死锁。

(5) 解除死锁

破坏除了“互斥条件”之外的其他三个条件：

• 回退执行：系统定期对各个进程进行检查，将检查点的有关信息写入文件。死锁时，让某占有必要资源的进程回退到取得资源之前的一个检查点，释放的资源分配给一个死锁进程（破坏“占有且等待”）
• 抢占资源：剥夺占有进程的资源，分配给另外某些进程，直至死锁环路被打破（破坏“不可抢占”）
• 杀掉进程：一次终止一个进程，直至消除死锁环路（破坏“循环等待”）

内部碎片和外部碎片：

• 内部碎片是固定分区法产生的，指被占用分区上未被利用的空间，由于该分区被占用，因此无法被分配使用
• 外部碎片是动态分区法产生的，指被占用分区之间的小空间，虽然可以被使用，但是由于太小而无法被分配

(1) 不同的内存分配技术及其优缺点

1. 等长固定分区法：每个分区大小相同，在系统启动时分配好，系统运行期间保持不变；每次给进程分配一整块区域，因此进程的大小必须 ≤ 分区的大小
   • 优点：系统需要维护的管理信息非常少，只要维护一个固定行数的表格，记载分区的使用情况；内存分配算法很简单，有足够大空闲分区就分配，否则就拒绝
   • 缺点：不同进程需要的空间不同，内部碎片多，浪费空间；分区总数固定，限制了并发执行的程序数量
2. 不等长固定分区法：每个分区大小不同，在系统启动时分配好，系统运行期间保持不变；分配时，需要根据进程的大小在空闲分区中选择一个大小合适的分区（优缺点同上）
3. 动态分区法：在系统运行中，根据每个进程需要的空间大小确定分区大小；通过空闲分区链表进行组织
   • 优点：并发执行的程序数量不受限制，只取决于是否有大小合适的内存块可以分配
   • 缺点：管理空闲快的复杂度增加；分配算法的时间开销增加，可能需要遍历多次才能找到合适的内存块
4. 页式内存管理：把固定分区面积缩小，一个进程可使用多个分区；进程被分割成若干块，装入内存中的几个分区中，物理上无需相连，逻辑上通过页表关联。这是一种内存的不连续分配方法
   • 优点：不存在任何外部碎片，只在每个进程的最后一个页框中存在内部碎片
5. 段式内存管理：按照逻辑意义将程序分成若干个段，每个段独立载入到内存的不同区间中
   • 优点：分页不考虑每个页中内容的意义，而分段是按照逻辑关系划分
   • 缺点：每个段必须连续、全部加载到内存中
6. 段页式内存管理：把分段和分页两种方式结合，先把程序按照逻辑意义分成段，然后每个段再分成固定大小的页

参考资料：段式内存管理 - Edison Zhou

(2) 不同的动态分区放置算法及其优缺点

• 最佳适应算法
  • 检查所有空闲分区，选择和新进程申请内存大小最接近的空闲分区
  • 优点：该算法保留大的空闲区
  • 缺点
    • 检查所有空闲分区需要时间
    • 外部碎片多：会留下许多难以利用的，很小的空闲分区，称为外部碎片
    • 可以采用内存紧凑的方法，将被使用的分区都移动到一起，减少外部碎片。但是移动内存中的代码和数据也需要很多时间
• 最差适应算法
  • 每次为进程分配分区时，都选择最大的空闲分区分配
  • 最差适应算法使链表中的结点大小趋于均匀，适用于请求分配的内存大小范围较窄的系统
  • 优点：该算法保留小的空闲区，尽量减少外部碎片的产生
  • 缺点：检查比较所有的空闲区间需要时间；系统中不会存在面积很大的空闲区间，难满足大进程的要求
• 首次适应法
  • 只要发现能用的分区就分配。这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区
  • 优点：可以剩下大的分区
  • 缺点：外部碎片多，集中在低址部分；并且每次查找都是从低址部分开始的，这无疑又会增加查找可用空闲分区时的开销
• 下一个适应法
  • 由于上面的放置算法每次都需要从头检查，有可能浪费很多时间。因此“下一个适应法”就是操作系统记住接下来该检查的空闲分区的位置，给进程分配分区时，系统从记录的分区开始依次向后查找直到碰到能用的分区为止，如果到链表尾还没有找到，就再从头开始
  • 缺点：上面的三个放置算法都是按照分区大小来分配，或是留下大区间（首次适应，最佳适应），或是留下小区间（最差适应）。下一个适应法很难剩下面积很大的区间，会使剩余分区的大小比较平均

(1) 虚拟内存的思想 / 实现方式

• 在系统中为每个程序定义一个虚拟地址空间，虚拟地址空间中的地址都是连续的
• 虚拟地址空间被分割成多个块，每块称为一个页或者页面
• 物理内存被分成和页面大小相同的多个区域，称作页框
• 程序加载时，可将任意一个页面放入内存中的任意一个页框
• CPU 的硬件负责将虚拟地址映射到物理内存中的地址（页面 -> 页框）
• 程序的整个地址空间无需全部载入物理内存，还有部分暂时存储在外存上，需要时再换入内存
• 如果程序引用到一部分不在物理内存中的虚拟地址时，会发生缺页中断，由操作系统负责将缺失的页面加载入页框中，并重新执行失败的指令

(2) 暂时不在内存中的数据存在哪里？

存储在交换分区（swap）中。当内存不足的时候，操作系统先把内存中暂时不用的数据，存到硬盘的交换空间，释放内存空间。详见 Swap - ArchWiki 。

(3) 虚拟地址的映射

页表：每个进程有一个页表，描述该进程每个页面对应的页框号，以及该页面是否已经被载入内存（“在/不在”位）。以下是一个进程的页表和地址映射过程的示意图：

• 一个完整的页表表项包含以下内容：
  • 页框号
  • 存在位：页面是否在内存中：
  • 访问位：页面是否已被访问，影响页面淘汰选择
  • 修改位：页面是否被修改，修改过的页面需要重新写回外存
  • …
  • 页面号：在页表中的下标，并不是一项真的内容

进程在运行时，需要将页表放在内存中。但在虚拟地址空间很大的情况下，会被分成很多个页面，那么进程的页表将占据很大的内存空间，甚至无法全部载入内存。

有一些针对大内存的页表实现方式：

• 多级页表：将页表进一步分页，页目录表相当于“页表的页表”，记录每个内层页表存放在哪个页框中；内层页表依然记录进程的每个页面存放在哪个页框中。以下是一个多级页表的示意图：
  
• 倒排页表：不再为每个进程记录页面到页框的映射，而是记录每个页框对应的 (进程号, 页面号) 二元组。整个操作系统只需要一个倒排页表，节省了大量空间。但是它必须遍历整个页表才能找到某个表项，无法将页面号当作索引直接找到页框号。
  
• 散列表：为了节省页表空间，同时加速查找过程，可以将当前进程的所有「在内存中」的页面建立一张散列表。用每个页面的虚拟地址来散列，相同散列值的元素会被链接到一起，每个元素包含三项内容：页面号、页框号、指向链表中下一个元素的指针。
  

(4) TLB 的原理

现代操作系统中，页表的个数是很多的，而每次执行语句时都需要先查找页表，将虚拟地址转换为物理内存地址。这部分切换的时间开销是很大的。因此，解决方案是为计算机设置一个小型的硬件设备 TLB。

转换检测缓冲区（TLB，translation-lookaside buffer），是 MMU（内存管理单元）的一部分。它提供一个缓冲区，记录虚拟页面号到物理页框号的映射，这样可以在 O(1) 的时间里直接将虚拟页面映射到物理页框，不需要访问页表，从而节省时间。

工作流程：如果页面号在 TLB 中，得到页框号，访问内存；否则，从内存中的页表中得到页框号，将其存入 TLB，访问内存。

TLB 基于局部性原理实现：

• 空间局部性：如果程序访问了地址 x，那么很有可能访问 x 附近的地址
• 时间局部性：如果程序访问了地址 x，很可能立刻又访问 x

(5) 缺页中断的处理

应用程序访问未加载到内存中的页面时，会引起缺页中断。操作系统回将缺失的页面加载入页框中，然后重新执行引起异常的指令。

缺页中断更准确地说，应当是“缺页异常（page fault）”。异常执行当前指令产生的错误情况，中断则是外部硬件产生的事件。详见陷阱、中断、异常、信号。

(6) 页面淘汰

当内存空间已被占满而又要调入新的页面时，必须将已在内存中的某个页面淘汰掉。如果被淘汰的页面曾被修改过，还要将此页写回到外存，再换进新的页面。这一过程称为页面淘汰。

如果某个页面频繁的被“调入-淘汰-调入-淘汰”，这种现象称为抖动。抖动导致系统将大部分时间花在了页面的置换上，因此在淘汰时，要选择今后不会或者最近不会用到的内容，以减少抖动。

(7) 不同的淘汰算法及其适用场景

根据具体的应用场景，选择合适的淘汰算法。除了操作系统的页面置换，redis 中也经常用到各种内存淘汰算法，往往需要结合具体业务场景来选择。

以下是几种常见的淘汰算法：

1. 最佳置换算法 / 最优策略（OPT）：选择以后再也不会用到的页面淘汰；如果都会用到，就选择那些再次使用的时间距离现在最远的页面淘汰。这是一种理想情况下的页面置换算法，实际上不可能实现。可以作为评测其他淘汰策略的标准。
2. 先进先出法（FIFO）：直接换出最早装入的页面。
   • 优点：简单
   • 缺点：性能不是很好，因为它淘汰的可能是常用的页面
   • 适用场景：数据只用一次，将来不太可能使用；[redis] 对数据时效性有要求（越旧的缓存越先被淘汰）
3. 第二次机会置换法（SCR：Second Chance Replacement）：对 FIFO 算法的改进，每个页面访问 2 次后再淘汰。具体实现上，设置页面访问位，每次检查队首的页面访问位：如果该位为 0，淘汰该页；如果该位为 1，将该位设为 0，将其移到队尾，看成新装入的页。
   • 优点：一定程度上，避免把经常使用的页面置换出去
     
4. 时钟置换法（Clock）：对第二次机会置换法的改进。第二次机会置换法需要在链表中移动页面，而时钟置换法将页面保存在环形链表中，只需要后移队头指针，就相当于是把原来的队头放到队尾了。
   • 优点：避免了移动链表节点的开销
     
5. 最近最少使用法（LRU：Least Recently Used）：优先淘汰最久未被访问的页面。根据局部性原理，一个进程在一段时间内要访问的指令和数据都集中在一起。如果一个页面很久没有被访问，那么将来被访问的可能性也比较小。
   • 优点：实验证明 LRU 的性能较好，能够降低置换频率
   • 缺点：存在缓存污染问题，即由于偶发性或周期性的冷数据批量查询，热点数据被挤出去，导致缓存命中率下降
   • 适用场景：访问分布未知的情况；[redis] 要求热点数据有效；[redis] 应用对缓存的访问符合二八定律 / 幂律分布
6. LRU-K：LRU-K 算法的核心思想是将“最近使用过 1 次”的判断标准扩展为“最近使用过 K 次”，LRU 可以认为是 LRU-1。能够降低“缓存污染”的问题。
7. 最近最不经常使用法（LFU：Least Frequently Used）：优先淘汰最近访问频率最少的数据。
   • 优点：能够避免缓存污染问题对 LRU 的命中影响
   • 缺点：存在访问模式问题，即如果访问内容发生较大变化，LFU 需要用更长的时间来适应，导致缓存命中率下降；维护相关数据结构的开销大
   • 适用场景：[redis] 数据的访问模式固定
8. 随机淘汰法（Random）：实现简单，不需要保留有关访问历史记录的任何信息
   • 适用场景：[redis] 如果应用对于缓存 key 的访问概率相等，则可以使用这个算法

操作系统常用的是 LRU 算法；一般数据的访问模式是随时间变化的，所以大多数的缓存也都是使用 LRU 算法或其变种。还有一些其他算法如 MRU、SLRU 等，见维基百科。

(1) 虚拟地址空间的组成部分

整体上，操作系统将每个进程的虚拟地址空间划分成两个部分：内核空间和用户空间。内核空间存放的是内核代码和数据，用户空间存放的是用户程序的代码和数据。在 32 位操作系统中，一般将最高的 1G 字节作为内核空间，而将较低的 3G 字节作为用户空间。

进程运行在内核空间时，处于内核态，此时可以执行任何特权指令。每个进程的内核空间都是相同的，用户代码无法访问内核空间。

虚拟地址空间的完整组成：

从上往下依次是：

• 内核虚拟内存：所有进程共享内核的代码和全局数据结构，独享与进程相关的数据结构，Linux 会将内核虚拟内存的共享区域映射到被所有进程共享的物理页面上
• 用户栈：从高地址向低地址增长
• 共享库：动态链接阶段
• 运行时堆：从低地址向高地址增长
• 程序代码和数据：从可执行文件中加载（代码段、数据段、BSS 段）

(2) 栈

用户栈其实就是函数调用栈，作用主要是：

• 保存函数的局部变量
• 保存某些寄存器的值
• 向被调用函数传递参数
• 返回函数的返回值
• 保存函数的返回地址

每个函数在执行过程中都需要使用一块栈内存用来保存上述这些值，这块栈内存为该函数的栈帧（stack frame）。栈的增长和收缩由编译器插入的代码自动完成，随着函数的调用而分配，随函数的返回而自动释放。程序员无需关心，这一点与堆不同。

(3) 堆

栈内存的分配需要实现确定其大小，而堆内存允许程序在运行时动态申请某个大小的内存空间。申请的内存在函数退出后依然保留，需要手动释放。C 语言中的 malloc / free 就是从堆中分配 / 释放内存，操作系统通过一个记录空闲内存地址的链表来管理堆内存。

如果反复向操作系统申请堆内存而不释放，会导致内存泄漏。在 C / C++ 中，必须由程序员手动释放堆内存。而 Java / Golang 中有垃圾回收器，会定期主动回收内存。但是即使有垃圾回收器，也有内存泄漏的风险，比如长期持有某个大对象的引用。

(4) 栈和堆的区别

1. 增长方向：栈向低地址方向增长，堆向高地址方向增长
2. 申请回收：栈自动分配和回收，堆需要手动申请和释放
3. 生命周期：栈的数据仅存在于函数运行过程中，堆的数据只要不释放就一直存在
4. 连续分配：栈是连续分配的，堆是不连续的，容易产生内存碎片
5. 空间大小：栈的大小是有限的（如默认 8M，Linux 上通过 ulimit -s 查看），而堆的空间较大，受限于系统中有效的虚拟内存

• malloc、free 的原理：答案
  • malloc、free 实现思路、简单实现代码
  • malloc 分配的内存块的格式
  • 为什么 free 只需要传递一个指针就可以释放内存
  • tcmalloc 简单了解
• 解密 Go 协程的栈内存管理
• 内存管理设计精要 - Draveness

1. 计算机最小的可寻址的内存单位是字节。按有效字节在内存地址中从小到大的存储顺序，可以分为大端法和小端法：大端法从高位到低位存储，小端法从低位到高位存储。比如某个 int 型整数的值为 0x01234567，存储在 0x100~0x103 的内存地址上。大端法和小端法的字节顺序如下所示：
   
2. 按内存地址顺序从低到高输出一个变量的全部字节，可以借助 char* 类型的指针来完成，见答案
3. 小端法输出 34 12 00，大端法输出 00 00 12，见答案

C 语言使用运行时栈来存储过程信息。每个函数的信息存储在一个栈帧中，包括寄存器、局部变量、参数、返回地址等。C 对于数组引用不进行任何边界检查，因此对越界的数组元素的写操作会破坏存储在栈中的状态信息，这种现象称为缓冲区溢出。

缓冲区溢出会破坏程序运行，也可以被用来进行攻击计算机，如使用一个指向攻击代码的指针覆盖返回地址。

防范缓冲区溢出攻击的机制有三种：随机化、栈保护和限制可执行代码区域。

(1) 随机化

使用缓冲区溢出进行攻击，需要知道攻击代码的地址。因此常见的防范方法有：

1. 栈随机化：程序开始时在栈上分配一段随机大小的空间
2. 地址空间布局随机化（Address-Space Layout Randomization，ASLR）：每次运行时程序的不同部分，包括代码段、数据段、栈、堆等都会被加载到内存空间的不同区域

但是攻击者依然可以使用蛮力克服随机化，这种方式称为“空操作雪橇（nop sled）”，即在实际的攻击代码前插入很长的一段 nop 指令序列，执行这条指令只会移动到下一条指令。因此只要攻击者能够猜中这段序列的某个地址，程序就会最终经过这段序列，到达攻击代码。

因此栈随机化和 ASLR 只能增加攻击一个系统的难度，但不能完全保证安全。

(2) 栈保护

在发生缓冲区溢出、造成任何有害结果之前，尝试检测到它。常见的栈破坏检测方法是栈保护机制：在每个函数的栈帧的局部变量和栈状态之间存储一个随机产生的特殊的值，称为金丝雀值（canary）。在恢复寄存器状态和函数返回之前，程序检测这个金丝雀值是否被改变了，如果是，那么程序异常终止。

(3) 限制可执行代码区域

内存页的访问形式有三种：可读、可写、可执行。只有编译器产生的那部分代码所处的内存才是可执行的，其他页应当限制为只允许读和写。以前 x86 将读和执行视为一个标志位，可读就可执行，为了限制某些页可读但不可执行，往往会带来严重的性能损失。现在新的处理器在硬件上引入新的位，将读和执行分开，由硬件来检查页是否可执行，效率上没有损失。

• 5 种 I/O 模型：阻塞 I/O、非阻塞 I/O、信号驱动式 I/O、I/O 多路复用、异步 I/O（AIO）
• I/O 同步和异步的区别在于：将数据从内核复制到用户空间时，用户进程是否会阻塞（需要用户进程来完成）
• I/O 阻塞和非阻塞的区别在于：进程发起系统调用后，是会被挂起直到收到数据后在返回、还是立即返回成功或错误
• I/O 多路复用 答案

推荐学习：操作系统中的各类 I/O 模型 - 马士兵

协程是一个用户态的线程，用户在堆上模拟出协程的栈空间。当需要进行协程上下文切换的时候，主线程只需要交换栈空间和恢复协程的一些相关的寄存器的状态，就可以实现上下文切换。没有了从用户态转换到内核态的切换成本，协程的执行也就更加高效。

(1) 协程的实现原理：

最基本的协程实现原理可以参考这篇文章，分析了一个简单的 C++ coroutine 的源码实现。协程的实现重点在于：

1. 在堆上模拟栈，从而实现一个用户态的线程
2. 调度器，负责协程的调度与上下文切换

Golang 的 goroutine 也是一个有栈协程。Golang 实现了自己的调度器 (GMP 模型)，使用队列管理协程 (运行队列、等待队列)；Golang 封装了系统调用，将阻塞的系统调用改为非阻塞的系统调用，从而在系统调用前将陷入“阻塞”的协程“切换”到等待队列，并让出计算资源。从 1.2 版本开始，goroutine 变为抢占式调度。

[进阶内容] 关于 go 语言的调度器原理和 goroutine 实现原理，可以阅读这些文章：

• Go 语言调度器与 Goroutine 实现原理 - Draveness
• Scheduling In Go: Part I、Part II、Part III：William Kennedy 的经典文章

(2) 协程切换哪些数据？

[TODO 待验证] 类似于线程的切换，协程切换时需要保存：

• 寄存器，包括 PC (指令位置) 和 CPU 寄存器 (参数、上下文…)
• 栈指针
• 返回值

(3) 协程的栈空间大小：

线程栈是固定大小的，可以使用 ulimit -a 查看。默认情况也是 8M（8192 字节），而协程占用的栈空间大小由 runtime 按需进行分配 (初始时很小，随后动态扩展)，可以查看这篇文章。

• Google 有详细的回答
• 字符编码笔记：ASCII，Unicode 和 UTF-8 - 阮一峰

TCP 是基于字节流的，数据块是没有边界、没有结构的字节流，因此可能产生粘包：

1. 发送方为了将多个发往接收端的包，更有效的发到对方，使用了优化方法（Nagle算法），将多次间隔较小、数据量小的数据包，合并成一个大的数据包一次性发送。
2. 接收方不能及时读取数据，导致缓冲区中的多个包粘连。

解决方法：

1. 发送方关闭 Nagle 算法
2. 应用层定义消息边界，最常见的两种解决方案就是基于长度或者基于终结符（Delimiter）
   1. 基于长度的实现有两种方式，一种是使用固定长度；另一种方式是使用不固定长度，但是需要在应用层协议的协议头中增加表示负载长度的字段，HTTP 协议的消息边界就是基于长度实现的
   2. HTTP 协议除了使用基于长度的方式实现边界，也会使用基于终结符的策略，当 HTTP 使用块传输（Chunked Transfer）机制时，HTTP 头中就不再包含 Content-Length 了，它会使用负载大小为 0 的 HTTP 消息作为终结符表示消息的边界

除了这两种方式之外，我们可以基于特定的规则实现消息的边界，例如：使用 TCP 协议发送 JSON 数据，接收方可以根据接收到的数据是否能够被解析成合法的 JSON 判断消息是否终结。

但值得注意的是，粘包并不是 TCP 协议本身的“问题”，而是一个“现象”。TCP 本身面向字节流的特性，导致会有所谓的“粘包”问题，需要应用层进行拆分。所以也有一种说法是“TCP 粘包是一个伪命题”。

为什么 UDP 协议没有粘包问题？UDP 是面向报文的，应用层交给 UDP 多长的报文，UDP 就照样发送，既不合并，也不拆分，而是保留这些报文的边界。

参考资料：为什么 TCP 协议有粘包问题 - draveness。

TCP 为什么是面向连接的：

• 发送之前需要先建立连接（三次握手）
• 使用排序和确认机制（分组之间并不是独立的；记录了分组之间的状态信息）
• 具有流量控制与拥塞控制
• 发送完毕后要释放连接（四次挥手）

参考资料：TCP/IP 高效编程：改善网络程序的 44 个技巧 第 2 章：理解面向连接和无连接的区别

TCP 如何保证传输的可靠性？

• 序列号：解决乱序问题
• 确认号 / 超时重传机制：解决丢包问题

TCP / UDP 协议头：

• UDP 协议头包含 4 个字段：源端口、目的端口、长度和校验码，其中每一个字段都占 2 字节，总长度 8 字节，请查看 RFC 文档：UDP Format - RFC 768
• TCP 协议头包含以下字段，详情请查看 RFC 文档：TCP Header Format - RFC 793

参考资料：为什么 UDP 头只有 8 个字节 - Draveness

• TCP：面向连接的、可靠的、基于字节流的传输层通信协议
• UDP：无连接的、不可靠的、基于报文的传输层通信协议
• 面向字节流：TCP 将要发送的数据视为无结构的字节流，如果发送的数据太长，就拆分发送，如果发送的数据太短，则积累较多的字节后再发送
• 面向报文：UDP 一次发送一个报文，不管多大，都以报文为发送单位

• 数字签名是什么 / 浏览器如何验证证书的有效性？ - 阮一峰
• SSL/TLS协议运行机制的概述 - 阮一峰
• SSL Handshake explained
• 你访问的网站是如何自动切换到 HTTPS 的？
• 什么是证书吊销列表 CRL？

整体流程：浏览器搜索自身的 DNS 缓存、搜索操作系统的 DNS 缓存、读取本地的 Host 文件和向本地 DNS 服务器进行查询等。

DNS 查询共有两类：递归查询和迭代查询。递归查询是指，当 A 向 B 查询某个域名的 IP 地址时，如果 B 不知道被查询的域名的 IP 地址，那么 B 会替 A 向更上层的服务器发起查询，将查询结果返回 A。迭代查询是指，当 A 向 B 查询某个域名的 IP 地址时，如果 B 不知道被查询的域名的 IP 地址，B 会告诉 A 下一步应该向哪个服务器查询，由 A 自己去查。

一般来说，主机（也就是我们的电脑）向本地域名服务器的查询是递归查询，而本地域名服务器向根域名服务器的查询是迭代查询。

常见的负载均衡软件：第四层 LVS、第七层 Nginx。

负载均衡系列专题 1-4 - houbb

• 建议直接阅读 man page：socket(), bind(), listen, accept(), connect()
• Linux Socket 编程
• Socket 的基本操作

流程图 [来源]：

TCP 和 UDP 可以同时监听同一个端口，操作系统根据五元组 {传输协议，源IP，目的IP，源端口，目的端口} 判断数据的接收者。

推荐学习以下课程：

• MySQL 索引设计概要 - Draveness
• 马士兵 MySQL 索引视频课

索引的作用主要是加快数据检索的速度。索引需要使用额外的存储空间来保存索引项。

索引的分类：MySQL 索引分类，90% 的开发都不知道

索引的优点：

• 大大加快了数据的检索速度
• 可以显著减少查询中分组和排序的时间
• 通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性
• 将随机 I/O 变为顺序 I/O（B+Tree 索引是有序的，会将相邻的数据都存储在一起）

索引的缺点：

• 占用额外空间
• 一开始增加索引时，需要创建索引表
• 新增或删除数据时，需要维护索引表

索引的适用场景：

• 等值匹配
• 范围查询
• 匹配最左前缀（联合索引）
• 仅针对索引列进行查询
• 其他：面试官出的 MySQL 索引问题 - 索引的适用场景

索引的适用场景：

适合建立索引：

1. 经常作为查询条件的字段。在不同值较多的列上建立索引，不同值少的列上不要建立索引。比如在雇员表的“性别”列上只有“男”与“女”两个不同值，就无必要建立索引。如果建立索引不但不会提高查询效率，反而会严重降低更新速度。
2. 频繁进行排序或分组（即进行 group by 或 order by 操作）的列
3. 如果待排序的列有多个，可以在这些列上建立联合索引 (compound index)

不适合建立索引：

1. 更新非常频繁的字段
2. 不会作为查询条件的字段 (不会出现在 WHERE 子句中)
3. 表记录很少的时候，没必要添加索引

数据库为什么用 B+ 树做索引？

用 B+ 树是为了减少 I/O 次数：

• 不可能把索引全部加载到内存中，只能逐一加载每个索引节点
• B+ 树的单个节点中包含的值个数越多，那么节点总数就会越少，I/O 次数也越少
• B+ 树高度一般为 2-4 层，查找记录时最多只需要 2-4 次 I/O
• 相反，二叉搜索树的高度高，所以需要的 I/O 次数更多

如果是内存数据库，不涉及磁盘 I/O，可以直接用二叉搜索树。

联合索引与最左匹配原则：

如果频繁地使用相同的几个字段查询，就可以考虑建立这几个字段的联合索引来提高查询效率。比如对于联合索引 test_col1_col2_col3，实际建立了 (col1)、(col1, col2)、(col, col2, col3) 三个索引。

最左匹配原则是指：这些索引能够被包含 col1、(col1 col2)、(col1 col2 col3) 的查询利用到，但是不能够被 col2、(col2、col3) 的等值查询利用到。这与底层实现有关。

联合索引实际上相当于将多个索引列视作一个列。叶节点中的每个行记录，也是按照这些索引列组合后的字典序进行比较的。字典序本身就符合最左匹配原则。

联合索引底层还是一棵 B+ 树。联合索引将多个索引列视为一个，所以非叶节点存储的是多个索引列 (col1、col2、col3) 的元组，叶节点存储的是索引列 col1、col2、col3 的值以及主键 id。叶节点之间按照 col1、col2、col3 的字典序排序。下图是一个简单的例子：

联合索引的主要优势是减少结果集数量：如果根据 col1、col2、col3 的单列索引进行查询，需要分别得到 num[i] 个结果，然后再取交集；而如果使用联合索引查询，只会得到很少的一段数据。见下图：

联合索引属于：

• 覆盖索引：如果 select a, b, c from table 且 (a b c) 是联合索引的前缀列 (比如联合索引是 (a, b, c, d))，那么不用进行回表查询，直接可以从索引表中获得这几个列的值
• 辅助索引：叶节点存储主键的值

数据库查询 offset 的流程：MySQL 查询时，offset 过大影响性能的原因与优化方法

1. 查询 offset 的流程：
   1. 先通过辅助索引找到所有主键值
   2. 再逐条回表查询，根据主键值找到数据块的内容，重复 offset + limit 次
   3. 丢弃前面的 offset 条数据，只保留最后的 limit 条
   4. 例如：LIMIT 30000, 10 的意思是，扫描满足条件的 30010 行，扔掉前面的 30000 行，然后返回最后的 10 行
2. MySQL 不会自动优化上面的语句，所以如果 offset 过大，会导致频繁通过主键索引访问 I/O，造成性能下降

3. 如何优化？可以在有序主键上进行子查询优化，即先查出偏移后的主键，再根据该主键回表查询：

    # 性能低下的语句：
    select * from member where gender=1 limit 300000,1;
    # 可以优化为：
    select a.* from member as a inner 
      join (
        select id from member where gender=1 limit 300000,1
      ) as b 
      on a.id=b.id
   

• 『浅入深出』MySQL 中事务的实现
• 数据库内核杂谈 (十)：事务、隔离、并发（1）
• MySQL的四种事务隔离级别

• 数据库内核杂谈 (十一)：事务、隔离、并发（2）
• 数据库内核杂谈 (十二)：事务、隔离、并发（3）
• 浅谈数据库并发控制 - 锁和 MVCC

• 分库分表的几种常见形式以及可能遇到的难题 - 丁浪
• 水平分库分表的关键步骤以及可能遇到的问题 - 丁浪
• 分库分表需要考虑的问题及思路 - jackcooper
• 大众点评订单系统分库分表实践 - 美团技术团队
• 读写分离、分库分表 - JavaGuide
• 主从复制、读写分离
  • 优点：提升系统的吞吐量、可用性
  • 缺点：数据不一致问题；类似于分库分表，提升了操作和运维的复杂性

• MySql查询性能优化 - poype - segmentfault
• 最全 MySQL 优化方法，从此优化不再难 - Wayne
• 优化 SQL 数据库的 6 种方式 - Chirag Thumar

ORM 封装了数据库底层实现的差异，开发人员不需要关注数据库是 mysql、mssql 还是 mongodb（不同数据库在 SQL 语法上有差异）。

ORM 使用链式函数调用来构建 SQL 语句，比直接写 SQL 语句更加友好，也不容易出错。

ORM 定义的模型是强类型的，能够编写类型友好的代码。而原生 SQL，返回的数据类型是未知的。

此外 ORM 能够抽象表与表之间的关系，可以让开发者专注于逻辑的编写。ORM 是面向对象的，利于管理和组织代码。

ORM 的缺点是效率低，另外有些场景只能用原生 SQL 实现。

• 《吊打面试官》系列 — Redis 基础
• 《吊打面试官》系列 — 缓存雪崩、击穿、穿透
• 《吊打面试官》系列 — Redis 哨兵、持久化、主从
• Redis 设计与实现

相同点：引用和指针都可以作为参数传递给函数，用于更改函数作用域外的变量；也可以作为函数的参数，在传递大对象时避免复制，提升效率。

不同点：

• 指针可以声明为 void，但引用永远不能为 void。
• 指针可以有指针的指针、指针的指针的指针… 但是引用只能有一级引用。
• 引用在声明之后就不能再修改。
• 引用其实是一个内部的指针。
• 引用比指针更安全，相对的，引用的也没有指针更灵活。
• 见 https://www.geeksforgeeks.org/references-in-c

值传递、指针传递和引用传递。

正数的原码、反码、补码都一样。这里只针对负数讨论。

反码是原码除符号位外的所有位进行按位取反运算。补码是原码符号位不变，其他位取反再加 1，或者反码再加 1。

比如：-1，原码 10000001，反码 11111110，补码 11111111。

计算机使用的是补码加法，这样就可以将减法运算转为加法运算，减去一个数等价于加上一个相反数，也即加上这个相反数的补码。

程序的局部性原理包含两个方面，一个是时间局部性，即程序在运行时，最近刚刚被引用过的一个内存位置容易再次被引用。另一个是空间局部性，即最近引用过的内存位置以及其周边的内存位置容易再次被使用。

编写局部性友好的代码：

• 使用局部变量
• 数组步长为 1（利用缓存行）
• 多维数组按行遍历（利用缓存行）

GMP 模型分别对应 goroutine、系统线程、logic processor。

M 为了保证自己不被释放，所以自旋。这样一旦有 G 需要处理，M 可以直接使用，不需要再创建。换句话说，如果 M 自旋，表示此时没有 G 需要处理。

1. 析构函数：基类 -> 成员类 -> 自身；析构函数相反。因为子类在构造函数和析构函数中可以访问父类（基类）。
2. 动态联编（运行时绑定）[TODO: 不确定的回答]
3. [TODO: 不会]
4. [TODO: 不会]

5. 6    // 字符数组的大小，5 + 1 (末尾的 \0)
   8    // 字符指针大小，8 字节
   8    // 字符指针数组的指针大小，8 字节
   8    // 指针大小，8 字节，64 位机器的指针大小都是 8 字节
   4    // int 在 32 位和 64 位系统都是 4 字节，long 在 32 位系统是 4 字节，在 64 位系统是 8 字节
   100  // 字符数组的大小
   

如何优化服务性能？火焰图是一个常用的工具。各类语言还有 profile 工具（比如 Golang 的 pprof），profile 就是定时采样，收集 CPU、内存等信息，进而给出性能优化指导。也可参考知乎的这个问题。

// 如何查看某个命令的文档？
man

// 如何查看占用某个端口的进程？
lsof -i :{port} // 如：lsof -i :8080

// 如何搜索当前目录下某个名字的文件？
find ./ -name filename

// 如何统计文件行数？
wc [选项] 文件1 文件2
  -c 统计字节数
  -l 统计行数
  -w 统计字数

// 如何统计一个文件中出现次数最多的前 10 个单词？
cat words.txt | sort | uniq -c | sort -nr | head -10
  sort: 对单词进行排序，以行为单位。-n 以数字格式排序而非 ascii 字符，-r 从大到小输出。
  uniq：显示唯一的行，只统计相邻的行，所以必须先排序。-c 每行行首加上本行在文件中出现的次数。

// grep 查找文件内容常用的几个选项
  -A 输出匹配行之后的多少行
  -B 输出匹配行之前的多少行
  -C 输出匹配行前后多少行
  -c --count 只统计总行数
  -i 忽略大小写

  -e 使用正则表达式
  -n --line-number 显示行号，常和 -r 一起使用
  -r 递归搜索整个目录
  -v --revert-match 反转查找，查找不包含指定字符串的文本行

  --color 关键字着色

统计 nginx 日志文件中请求量最高的前 10 个 IP。假设 Nginx 的日志每行记录一个请求的相关信息，用空格分隔各个字段：

{ip} {time} {header} {status} {useragent} {path}
220.181.108.104 - - [09/Apr/2015:07:00:20 +0800] "GET /xref/linux-3.18.6/ HTTP/1.1" 502 181 "-" "Mozilla/5.0 (compatible; B*aiduspider/2.0; +http://www
.baidu.com/search/spider.html)"

则：

cat nginx.log | awk '{print $1}' | sort | uniq -c | sort -nr | head -10 | awk '{print $2}'

• awk '{print $1}'：输出 nginx 日志第一列，即 ip 地址。
• uniq -c：相邻的相同行只显示一个，并在前面添加出现次数。由于只统计相邻行，所以需要先 sort。
• sort -nr：从大到小排序，-n 表示将第一列视作数字进行排序，输出的第一列是出现次数。
• head -10：取前 10 个。
• awk '{print $2}'：输出第二列，只有 ip 地址。

中间件是为应用提供通用服务和功能的软件。以下是分类和举例：

• RPC
  • drpc
  • thrift
• 内存缓存
  • redis
  • memcached
• 消息队列
  • kafka
  • rabbitmq
• 数据库分片
• 动态配置中心
• 打点
• 分布式链路追踪
  • opentracing
• 微服务 / 服务注册、发现
  • etcd
  • zookeeper

• 分布式系统一致性问题 - 赵坤
• 分布式系统的 CAP 理论 - hollischuang
• 分布式一致性与共识算法 - Draveness
• 分布式事务的实现原理 - Draveness
• 分布式系统与消息的投递 - Draveness

• Java HashMap 工作原理及实现 - Yikun
• Java HashMap 的负载因子为什么是 0.75
• Go 语言 map 底层实现

Map 使用不同数据结构实现的区别：

C++ STL 中的 map 和 unordered_map，分别使用红黑树和哈希表实现。使用红黑树方式实现，和哈希表实现的区别在于：

1. map 始终保证遍历的时候是按 key 的大小顺序的，这是一个主要的功能上的差异
2. map 可以做范围查找，而 unordered_map 不可以
3. map 节省内存
4. map 查找效率稳定，最差是 O(logN)
5. unordered_map 需要为每个 key 计算 hash 值，而 map 则不需要，只需比较 key 的前几个字符
6. map 在插入元素时比较耗时

如何实现一个并发安全的 HashMap？

1. 检测：例如 Java 的 HashMap 类型，使用了 fail-fast 机制，记录 modCount 表示哈希表的修改次数。在一个线程访问一个 map 前，会先记录 modCount 的旧值，然后在访问过程中比较旧值和当前值，如果不相等说明有其他线程修改了这个 map，于是抛出异常。可以理解为乐观锁。
2. 锁：例如 Java 的 HashTable 类型，结构和 HashMap 类似，唯独在接口上使用了 synchronized 修饰符，保证抢占到内置锁之后才会执行。可以理解为悲观所，线程竞争激烈的情况下，效率低下。
3. 分段锁：例如 Java 的 ConcurrentHashMap 类型。分段锁，顾名思义就是将锁分段，将锁的粒度变小，将存储的对象分散到各个分片中，每个分片由一把锁控制，这样使得当需要对在 A 分片上的数据进行读写时不会影响 B 分片的读写，从而提高并发度。
4. 冗余数据、降低加锁对性能的影响：例如 go1.9 引入的 sync.Map 类型，通过冗余的一份只读数据配合原子操作，降低了加锁对性能的影响。详见 Go 1.9 sync.Map 揭秘。

百万量级的数据排序：

• 任意大小：外排序，先将数据拆分到多个文件中，分别加载到内存中排序，然后再归并到一个文件里。实际上就是 LeetCode 23. 合并 k 个有序链表，需要用到最小堆。
• 范围为 [0, 10000]：计数排序。

百万量级的数据查询在不在：可以使用位图，前提是数据范围不超过内存大小。

百万量级的数据求 TopK：数据流的 TopK 问题，维护一个大小为 k 的小根堆，然后分片读入数据，并更新堆。

海量数据，统计只出现一次的数字：

(1) 位图法

如果题目给定数据大小范围是 0～10000，那么只需要申请一个 10000 字节的空间。即使是将所有的 int 整数表示出来，也只需要 2^32 bit 空间，大约 512MB，这个空间并不大。

位图的实现很简单。比如我在面试时使用 Go 实现的位图：

package main

import (
    "fmt"
)

type BitMap struct {
    bits []byte
}

func NewBitMap(capacity int) BitMap {
    return BitMap{make([]byte, (capacity+7)/8)}
}

func (bitmap *BitMap) Set(num int) {
    if (num > 8*len(bitmap.bits)) {
        return
    }
    pos := num / 8
    offset := uint(num % 8)
    bitmap.bits[pos] |= (0x80 >> offset)
}

func (bitmap *BitMap) Check(num int) bool {
    if (num > 8*len(bitmap.bits)) {
        return false
    }
    pos := num / 8
    offset := uint(num % 8)
    return bitmap.bits[pos] & (0x80 >> offset) > 0
}

func main() {
    bitmap := NewBitMap(15)
    bitmap.Set(2)
    bitmap.Set(15)
    bitmap.Set(30)
    fmt.Println(bitmap.Check(2))
    fmt.Println(bitmap.Check(3))
    fmt.Println(bitmap.Check(15))
    fmt.Println(bitmap.Check(30))
}

C 语言的位图实现，可以参考这篇文章。

(2) Hash 分治法

如果数据量过大，也可以先使用 hash 函数，将所有整数映射到 N 个文件中；然后在每个文件中使用 bitmap 或者 HashMap 去重，最后归并所有文件中只出现一次的结果。因为使用了 hash 函数，可以保证相同的数字必定会分到同一个文件中。

扩展阅读：

• 十道海量数据处理面试题与十个方法大总结
• 教你如何迅速秒杀掉：99% 的海量数据处理面试题
• 经典面试问题: Top K 之海量数据找出现次数最多或不重复的
• 10 亿 int 型数，统计只出现一次的数