开发岗面试八股文知识速记

内容基于小林coding

网络篇

基础篇

TCP/IP网络模型

应用层

其实包含了OSI模型中的应用层/表示层/会话层三层

为用户提供各种应用功能，如HTTP，FTP，DNS等
形成数据报文（message）

传输层

传输协议（TCP/UDP）
不同端口号对应不同应用
数据分块（Maximum Segment Size），添加协议头形成数据段（segment）

网络层

IP（Internet Protocol）协议
寻址（在子网下寻找主机）与路由（根据目的子网选择转发路径）
数据分片（Maximum Transmission Unit），添加IP头形成数据包（packet）

网络接口层

其实包含了OSI模型中的数据链路层/物理层两层

根据MAC地址完成每一段路径的点到点传输
添加帧头和帧尾封装形成数据帧（Frame）

从网址到网页

HTTP

解析URL
- 访问协议+域名/地址+[资源路径]
- 未指定资源路径时访问根目录下事先设置的默认文件
生成HTTP请求信息（请求报文）

DNS

域名层级
- 根DNS服务器（.）
- 顶级域DNS服务器（.com, .org……）
- 权威DNS服务器（google.com, baidu.com……）
域名解析流程
1. 浏览器查看是否存在对应域名缓存→操作系统查看是否存在对应域名缓存→hosts文件是否存在解析→询问本地DNS服务器
2. 本地DNS服务器查看缓存，存在对应的域名解析则直接返回，否则询问根DNS服务器，根DNS服务器返回对应的顶级域DNS服务器地址
3. 本地DNS服务器询问顶级域DNS服务器，顶级域DNS服务器返回对应的权威DNS服务器地址
4. 本地DNS服务器询问权威DNS服务器，权威DNS服务器查询后返回IP地址
5. 本地DNS服务器返回结果

协议栈

应用程序通过调用socket库委托操作系统协议栈工作
协议栈分为上半的传输协议（TCP/UDP）和下半的IP协议
IP协议还包括告知网络包传输过程中错误和控制信息的ICMP（Internet Control Message Protocol）和根据IP地址查询MAC地址的ARP（Address Resolution Protocol）协议

TCP

面向连接的、可靠的、基于字节流的传输层通信协议
序号防止包乱序，初始值为通信双方第一次SYN信号随机确定的，每发送一个包就增加对应的字节数
确认序列防止丢包，标识下一次期望收到的报文的序号，发送方可以认为该序号之前的数据都已成功接收
状态位维护TCP连接状态：
- ACK：设置为1时确认序列有效，TCP规定除了第一次SYN之外的数据段必须将该为置1
- RST：设置为1时表示连接异常，必须强制断开连接
- SYN：设置为1时表示希望建立连接，序号字段进行整个连接的序号初始值设定
- FIN：设置为1时表示今后不会再有数据发送，希望断开连接
窗口大小用于流量控制，标识当前能够处理的能力
TCP也可以通过控制发送速度进行拥塞控制

IP

如果存在多张网卡，则根据路由表规则选择源IP地址（路由表说明了前往特定子网使用的网络接口，全0的子网标识默认网关）

MAC

协议类型在TCP/IP通信中一般只包括IP协议（实际数据的收发）和ARP协议（广播获取IP地址对应设备的MAC地址，然后存入ARP缓存）

网卡

操作系统通过网卡驱动程序控制网卡将数据帧转换为电信号传输
网卡驱动程序会给数据帧加上报头、起始帧分界符和末尾用于检测错误的帧校验序列

交换机

交换机工作在MAC层，即二层网络设备，其端口不具备MAC地址
交换机查看MAC地址表中是否存在目的地址，存在则转发到对应端口，不存在则广播
交换机每次收到来自某个端口的数据后都会更新对应的MAC地址表

路由器

路由器工作在IP层，即三层网络设备，其各个端口都有MAC地址和IP地址
路由器检查收到的包的目的MAC地址是否是自己的MAC地址，如果不是则丢弃，否则去掉MAC头部（上一段传输已经完成），完成接收操作
路由器根据包中的目的IP地址查询路由表，获取下一跳的IP地址，进而通过ARP（缓存）获取下一跳的目标MAC地址，添加MAC头部完成转发操作
包的转发操作就是不断通过IP寻路，找到下一跳，更改MAC完成下一跳链路传输的过程

网卡与操作系统的交互

接收方式

网络包到达网卡后，网卡就会通过DMA将其内容写入到指定内存区域

通知方式

网卡请求硬件中断，硬件中断函数首先屏蔽中断，然后发起软中断，最后恢复中断
软中断轮询需要处理的数据，如果发现则将其移交给网络协议栈

发送方式

socket系统调用，申请一块内存区域并拷贝需要发送的数据（第一次拷贝），将其加入发送缓冲区
如果使用TCP，则拷贝一块新的发送数据（第二次拷贝，为重传做准备），如果收到ACK释放原数据内存空间
申请的空间总是为各种头部数据预留了空间，从而填充各种协议的头部时只需要移动指针即可，避免深拷贝开销
如果IP层在填充头部时发现TCP填充头部后的数据大小大于MTU，则分片拷贝（可能的第三次拷贝）

HTTP篇

本篇中的HTTP如果没有特别指明版本则默认指代目前使用最多的HTTP/1.1

基本概念

超文本传输协议（ Hyper Text Transfer Protocol）
常见状态码：
- 1xx：提示信息，表示协议处理的中间状态，实际很少使用
- 2xx：客户端请求处理成功
  - 200 OK：一切正常，该响应包含Body数据
  - 204 No Content：成功，该响应不需要Body数据
  - 206 Partial Content：成功，该响应包含Body数据，但是分块传输或断点续传
- 3xx：重定向
  - 301 Moved Permanently：永久重定向
  - 302 Found：临时重定向
  - 304 Not Modified：缓存重定向，告知客户端直接使用缓存资源
- 4xx：请求有误，服务端无法处理
  - 400 Bad Request：表示请求有错误
  - 403 Forbidden：表示禁止访问对应资源
  - 404 Not Found：服务端不存在对应资源
- 5xx：请求正确，但服务端处理时出错
  - 500 Internal Server Error：服务器发生错误
  - 501 Not Implemented：功能尚未实现
  - 502 Bad Gateway：表示服务器自身工作正常，但访问更后端的服务器时出现了错误
  - 503 Service Unavailable：表示当前服务器繁忙
常见字段：
- Host：指定服务器域名/IP地址
- Content-Length：表示响应的数据长度（单位字节）
- Connection：设置为Keep-Alive表示指定建立长连接，避免每次请求都不断握手挥手
- Content-Type：表示响应的数据格式，客户端请求时可以使用Accept字段指定自己支持的数据格式
- Content-Encoding：表示响应采用的压缩格式，客户端请求时可以使用Accept-Encoding字段指定自己支持的数据压缩格式

GET和POST方法

在RFC规范的语义下：
- GET方法是从服务器获取指定的资源，请求参数位于URL中，不改变服务器上的资源，幂等（多次执行同一操作结果相同）且安全，可被缓存
- POST方法是根据请求负荷（报文Body部分）对指定的资源做出处理，请求参数位于报文的Body中，格式与服务端协商好即可，会改变服务器上的资源，不安全，大部分不幂等且不可被缓存
由于开发者不一定会按照RFC规范严格实现，例如使用GET方法实现新增或删除数据、使用POST方法实现数据查询，因此需要具体案例具体分析
RFC并没有规定GET方法不能带Body，只是在语义上不需要使用Body，也没有规定POST不能在URL中带请求参数

HTTP缓存

强制缓存

浏览器判断缓存未过期，直接使用浏览器的本地缓存（from disk cache），决定是否使用缓存的主动权在客户端
通过Header中的Cache-Control或Expires字段实现，前者指定相对时间，后者指定绝对时间，一般使用后者：服务器响应时设置该字段，客户端收到后，每次需要再次发起同样的请求时，先检查是否距离上次请求超过相对时间/当前时间是否超过绝对时间，如果超过才发送请求，否则直接使用缓存
如果两个字段同时存在，优先使用Cache-Control，即相对时间

协商缓存

服务器返回304指定客户端使用缓存，决定是否使用缓存的主动权在服务端
通过Header中的两套字段实现：
- 请求头中的If-Modified-Since和响应头中的Last-Modified：客户端每次收到响应都根据Last-Modified更新最后修改时间，发送时带上本地的最后修改时间，服务器通过判断客户端的最后修改时间和本地的最后修改时间决定是否使用缓存
- 请求头中的If-None-Match和响应头中的ETag：服务端为资源创建唯一标识，发生修改后标识会变化；客户端每次收到响应都根据ETag更新资源标识，发送时带上本地的资源标识，服务器通过判断客户端的标识和本地的标识是否匹配决定是否使用缓存
如果两套字段同时存在，优先使用If-None-Match和ETag的组合，它能解决下述修改时间无法解决的问题：
- 即使文件并未发生修改，文件的最后修改时间也可能发生变化
- 有些文件的修改可能在秒级以内发生，无法通过修改时间区分
- 有些服务器不能精确获取文件的最后修改时间

两种缓存的关系

浏览器会首先检查强制缓存是否命中，如果未命中才发起带有协商缓存的请求

HTTPS

HTTP的问题

无状态虽然避免了记忆状态带来的开销，但是需要频繁的身份校验，常见的方法是通过cookie解决，服务器每次响应都携带一个标识身份信息的cookie，客户端下次请求时携带该cookie信息
明文传输虽然避免了加密带来的开销，但是容易导致信息的泄露
不安全：
- 明文通信导致的信息泄露
- 不验证通信方身份遭遇伪装
- 不验证报文的完整性遭遇篡改

其中最主要的问题是不安全的问题。HTTP是应用层协议，通过在其下层传输层加入SSL(Secure Sockets Layer)/TLS（Transport Layer Security，前者普及后的标准化称呼）协议完全解决了HTTP不安全的问题，在其建立连接的过程中，先完成TCP的握手，然后完成TLS/1.2握手。

摘要算法+数字签名

摘要算法对发送的内容生成指纹，将指纹与内容一起发送，接收方计算收到的内容的指纹，通过检查指纹是否匹配避免了内容被篡改的问题（但内容和指纹一起被篡改的可能仍然存在）
数字签名：通信开始前服务端将其公钥发布给客户端，之后服务端通过其私钥加密指纹，客户端在获得报文内容和加密指纹后使用服务端公钥解密指纹，然后再匹配指纹，为上述情况增加了一重保障（但内容和指纹被篡改，同时伪造一对公私钥的情况仍然存在，例如你访问了一个伪装的站点）

数字证书

服务器将服务的用途、有效时间和自身公钥等信息提交到数字证书权威机构（CA）
CA对服务器提交的信息进行哈希计算，使用自己的私钥加密该哈希值，也即给证书做了数字签名，将该数字签名、签发者信息和服务器提交的信息打包成为数字证书
CA的公钥事先置入客户端的浏览器或操作系统，从而客户端可以通过计算证书信息的哈希值与解密的CA签名比对验证证书的真伪

该过程相当于引入了一个外部的权威机构，证明服务器的公私钥不是伪造的。但实际上类似于DNS服务器，数字证书一般都不由根证书签发，而是由中间证书签发的，从而存在一个证书信任链的问题：当客户端发现证书并不是由根证书签发的时候（不存在对应中间证书CA的公钥），就会根据对应证书中的签发者信息向对应的中间证书CA请求证书进行验证，如此逐步向上递归验证，直到签发者变为根证书。

CA分层的目的是使根证书与尽可能少的证书验证直接交互，确保根证书的绝对安全性，避免根证书的失守。

混合加密（TLS握手协议）

Client Hello：客户端发起加密通信请求，包含TLS协议版本、客户端生成的随机数R1、客户端支持的密码套件列表（如RSA加密算法、ECDHE加密算法）（全明文）
Server Hello：服务端响应客户端的请求，包含确认TLS协议版本、服务端生成的随机数R2、确认的密码套件列表、服务器的数字证书（全明文）
客户端回应：首先验证服务器数字证书的真伪，然后发送如下信息：
1. 随机数R3（服务器公钥加密）
2. 加密通信算法改变通知，表示随后的信息通过对称加密的会话密钥进行（明文）
3. 客户端握手结束通知，并将之前的通信内容通过摘要算法整合，用于服务端校验（会话密钥加密）
服务端最后回应：服务端收到随机数R3后解密并计算出会话密钥，发送加密通信算法改变通知（明文）和服务端握手结束通知（会话密钥加密）

通信建立前通过非对称加密交换会话密钥，通信过程中使用对称的会话密钥加密，非对称加密保证了安全性，通信过程使用对称加密则规避了非对称加密性能开销大的问题。

上述的随机数算法是RSA加密算法，缺点是不支持前向保密，如果服务器私钥泄露，就会导致过去被截获的所有加密通讯均被破译。

因此现在常用ECDHE加密算法完成加密，其原理是利用椭圆曲线的特殊规律，私钥是一个用后即焚的随机数，公钥则是使用这个随机数和椭圆曲线计算出的一个点（几乎不可能被反向推导），它们只需要交换公钥，就可以利用这条曲线的性质使得双方达成一致，而私钥只是一个每次通信重新生成的随机数，而且永远不会存在于内存之外的空间，即使被破解了也只能得到这一次通信的数据。ECDHE加密算法的核心是构建会话密钥的私钥不再固定，从而避免了私钥泄露导致通信内容被全部破译的问题。

此外，采用RSA算法的TLS/1.2握手必须完成四次通信（两个来回）才能开始正常通信，而采用ECDHE算法的TLS/1.2握手则可以在最后一次通信时就携带请求数据（称为TLS False Start）

TLS记录协议

消息分片
对分片的消息片段集合片段编码（防止重放攻击）通过哈希算法生成认证码（MAC值）
压缩后的片段数据和认证码一起通过会话密钥加密
给加密后的数据的头部加上数据类型、版本号、压缩后长度等信息组成最终报文数据

伪基站问题

伪基站转发到中间服务器，中间服务器可以获取用户与实际服务器之间的所有信息，是否说明HTTPS不够安全：这一切成立的前提是用户接受了中间服务器的证书，换句话说，就算中间服务器进行了数据泄露，也不是HTTPS的问题，而是中间服务器经营者，以及用户同意使用中间服务器的问题。

抓包工具原理

HTTPS的抓包工具的原理就是中间服务器，通过安装中间人自己的CA证书Fiddler使得工具创建的证书被浏览器信任，从而实现其充当中间服务器的合理性

如何避免中间服务器

首先主动防范，其次还可以通过HTTPS双向认证，即服务器还会认证客户端的身份信息（You are blocked😏）

HTTP演变

HTTP/1.0→HTTP/1.1

✅使用长连接改善了反复进行TCP握手挥手的性能损耗
✅支持管道网络传输，不必等待前一个请求的响应即可发送下一个请求
❌服务器按顺序响应，前一个请求处理完毕并响应之前，后一个请求即使已经处理完毕也只能排队，队头阻塞仍然存在
❌Header内容未经压缩就发送，损耗性能
❌没有请求优先级控制
❌仍然是“请求-响应”的模式

HTTP/1.1→HTTP/2.0

✅基于HTTPS，保障了安全性
✅头部压缩：HPACK算法，在客户端和服务端同时维护一张头信息表，如果后续发送的头信息与之前的一致，直接发送其在头信息表中的索引号
✅二进制格式：不再采用文本格式而是采用二进制格式（称为数据帧），节省了字节数以及计算机解析文本内容的时间，提升了传输效率
✅并发传输：引入Stream，多个Stream复用同一个TCP连接，每一个Stream对应一个原本HTTP/1.1中的HTTP请求，被分配一个独特的Stream ID，其中可以存在多个被拆分的数据帧，被拆分后的所有数据帧可以乱序发送，收到数据帧的一方按照Stream ID有序组装。相当于将原本的单车道扩建成了多车道。由此，后发出但先完成的请求就不会被先发出但还未完成的请求阻塞。
✅服务器主动推送：客服双方均可以建立Stream，客户端建立的Stream ID必须是奇数，服务端建立的则必须是偶数，服务器可以通过主动建立Stream向客户端推送数据，改变了传统的“请求-响应”模式
❌只解决了应用层的队头阻塞，但传输层的队头堵塞并没有解决，组装是在应用层完成的，对于传输层的TCP而言，它只认识传输层的序号，不认识流的编号，如果序号靠前的帧在传输过程中丢失，就会触发TCP的重传机制，来自任何流的任何帧（对于TCP而言，它们都是序号靠后的数据帧）抵达后都会被阻塞在内核缓冲区，直到那个丢失的序号靠前的帧重传，它才会将缓冲区的所有帧递交给应用层。

HTTP/2.0→HTTP/3.0

✅不再采用TCP连接，而是采用UDP，避免了TCP的队头阻塞问题
✅基于UDP的QUIC协议的可靠性传输保障：
- 无队头阻塞：类似于HTTP/2.0 Stream的多路复用，但丢包只阻塞当前流，不阻塞整条连接
- 更快的连接建立：HTTP/2.0中TCP和TLS/1.2分离，需要分别握手，至少要三个来回；QUIC握手中同时携带TLS/1.3（TLS/1.2握手需要两个来回，TLS/1.3握手只需要一个来回，后者仅支持ECDHE加密，合并了客户端端发起请求和公钥交换的步骤，以及服务端接受请求、公钥交换以及证书发布的步骤，客户端收到证书验证后即可直接发送数据）的握手信息，只需要一个来回就可以完成连接的建立
- 连接迁移：基于TCP的HTTP协议通过（源地址，源端口，目标地址，目标端口）的四元组确定一条TCP连接，如果发生网络切换则地址变化，需要重新建立连接，而且其过程相对缓慢；QUIC协议采用连接ID/Ticket标记一个连接，即使地址发生变化，只要保留了连接ID/Ticket，TLS会话密钥等上下文信息，就可以无缝恢复连接（对于TLS/1.3而言，恢复连接的ID/Ticket和请求数据会一起发送，以最快恢复连接，称为Pre-shared Key）。但是恢复连接存在一个问题：如果攻击者截获了之前的通信内容并获取到ID/Ticket，那就可以直接基于这些凭证进行重放攻击，因此需要设定会话密钥的过期时间。

如何优化HTTP应用

避免发送HTTP请求

见HTTP缓存

减少HTTP请求次数

减少重定向请求次数：如果存在代理服务器，多次往返的HTTP重定向消息会损耗性能，这时可以让代理服务器识别到需要重定向的请求直接返回
合并请求：将多个小资源的请求合并为一个大资源的请求，但这样的做法会导致其中一个小资源变化后需要重新下载整个大资源
延迟发送请求：懒加载

减少HTTP响应的数据大小

无损压缩：最小化与常见压缩算法
有损压缩：Header中的Accept字段还可以设置接受的q质量因子，常用的压缩方式如下：
- Webp图片格式
- H264/H265，AAC/AC3音视频的增量数据编码

HTTP和RPC

服务发现

HTTP通过DNS服务完成服务发现
RPC需要通过专门的中间服务，例如Etcd等（也有通过DNS完成RPC服务发现的例子）

底层连接形式

HTTP/1.1建立TCP长连接
RPC也会建立TCP长连接，但还会建立连接池，在请求量大的时候建立多个TCP连接置于其中，需要时取用，用完放回
不少编程语言的网络库也实现了连接池

传输的内容

HTTP使用的序列化方式大多是JSON，其信息比较冗余
RPC定制化的程度更高，不需要声明过多信息，从而采用体积更小的序列化协议（如Protobuf），获得更好的性能，因此在微服务中更多地被采用
然而随着HTTP/2.0及之后版本的出现，其性能表现超过了很多RPC协议，甚至gRPC底层使用的就是HTTP/2.0
目前RPC仍然在被大量使用更多是历史原因

HTTP和WebSocket

核心问题：如何实现看起来是“服务器主动将数据推送给客户端”？

HTTP不断轮询

对网络性能开销太大

长轮询

增长HTTP的超时时长，在这段时间内，服务器检测到状态变化立即响应

Websocket

HTTP是半双工的，而Websocket是全双工的（同一时间内，双方都可以主动发送数据），更适合服务器需要和客户端频繁交换数据的场景
在完成TCP握手后，客户端通过在Header中设置请求将协议升级为Websocket，并带有一段随机生成的base64码，发送给服务端；如果服务端支持升级，就开始Websocket握手流程，通过一个公开算法转换base64码，并带有状态码101（表示协议切换）发回给客户端；客户端检查转换后的base64码与自己转换的结果是否一致，如果一致则开始Websocket通信
Websocket帧结构如下所示，主要的字段包括：
- opcode：标识数据类型，例如1表示string类型，2标识二进制，8标识关闭连接；
- payload：数据长度，单位是字节（采用第一个字段标识范围，如果第一个字段为0~125，则就是真实长度；如果为126，则真实长度是后16位；如果为127，则真实长度是后64位）
- payload数据：真正要传输的数据
- 消息头+消息体的设计是为了避免粘包的问题（对于TCP而言粘包问题是应用层解决的，例如HTTP通过Header中的CR+LF划分消息的边界，因为TCP是面向字节流的传输协议，它并不区分传输单位的边界）

TCP篇

基础知识

什么是TCP连接

Socket：IP地址和端口号
序号：解决乱序问题
窗口大小：流量控制

UDP和TCP的区别

TCP面向连接，UDP无连接
TCP是一点一的连接，UDP支持一对一，一对多，多对多的交互通信
TCP是可靠的数据传输，保证无差错、不丢失、不重复、按序抵达；UDP尽最大努力交付数据，但不保证可靠，但可以基于它实现可靠的QUIC协议
TCP有拥塞控制和流量控制，UDP不控制
UDP的首部很简单，只包含源端口、目的端口、包长度和校验和，开销小
TCP是无边界的流式传输（不解决粘包，只是字节流），UDP是有边界的，它会一个包一个包地发送
TCP会自行分片，丢包后重传丢失的分片，UDP自己不分片
TCP常用于需要可靠的文件传输场景，例如FTP/HTTP；UDP常用于数据量小、注重整体连贯性的音视频等多媒体通信、广播通信

TCP三次握手

客户端发起连接请求，生成随机的客户端序号cli\_seq，将SYN位置为1，客户端进入SYN_SENT状态
服务端收到客户端发起的SYN请求，生成随机的服务端序号server\_seq，将SYN位和ACK位置为1，将确认号设置位cli\_seq+1（期望下一个收到的的字节编号，握手过程都是默认+1），进入SYNC_RCVD状态，将当前连接置入半连接队列
客户端收到服务端回应的SYN+ACK消息，将ACK位置1，确认号置为server\_seq+1，序号置为cli\_seq+1，客户端进入ESTABLISHED状态，在这条报文中已经可以携带数据进行通信（称为TCP Fast Open），服务端在收到第一条数据通信后进入ESTABLISHED状态，将当前连接从半连接队列移除，置入全连接队列

TCP四次挥手

客户端在发送最后一个报文时将报文的FIN位置为1，客户端进入FIN_WAIT_1状态
服务端收到客户端的FIN位置1报文后进入CLOSED_WAIT状态，回复一条ACK置1的报文表示准备关闭连接，客户端收到这条消息后进入FIN_WAIT_2状态，
服务端在完整地接收到最后一个报文的信息后向客户端发送一条FIN位和ACK位均置1的报文，服务端进入LAST_ACK（只有被动关闭连接的一方会进入这个状态）状态
客户端收到服务端的最后一条报文后回复一条ACK位置1的报文，客户端进入TIME_WAIT（只有主动发起连接关闭的一方会进入这个状态）状态并最多在这个状态等待2MSL（Maximum Segment Lifetime），如果在这个计时内都没有收到服务端的报文则默认服务端已关闭连接，进而客户端关闭连接，否则重置计时器（这个状态是防止服务端没收到LAST_ACK），服务端在收到这条报文后关闭连接（如果客户端默认关闭，但服务端没收到LAST_ACK，它也不会一直等下去，TCP保活机制（keep-alive）存在心跳检测，但要等很久，往往应用层的心跳检测会提前关闭连接）

TCP的Socket编程

即使不调用bind函数也可以通过connect默认指定端口连接，内核默认可以使用重复端口（它只是一个普通的港口，服务端的港口是发布特殊服务的，所以是特化港口）

TCP重传

下面的机制在TCP重传机制中往往同时工作，但TCP不会重传纯粹的ACK报文（只有首部有数据的ACK报文），至于ACK丢失影响整个传输进程的问题，往往是通过发送方重传来解决的

超时重传

如果超过RTO（Retransmission Timeout，超时重传时间）没有收到对应的ACK信息，则重传数据包，这个数值往往略大于RTT（Round-Trip Time，往返时延），实际上是通过一套复杂的机制计算这个具体的时间，并且每超时重传一次，都会将RTO翻倍（说明网络状况不佳，不应该频繁发送请求）

快速重传

为了解决超时重传的超时周期过长的问题，TCP引入了快速重传机制：

在收到某个序号靠前的报文之前，如果收到了序号靠后的报文，接收方返回的确认号仍然是靠前序号-1（说明还只收到了那之前的部分，当前接收到的阻塞在内核缓冲区无法进行组装）。基于这个原理，如果反复（一般是3次）收到同一确认号的回复，说明该确认号对应的分片丢失了，就可以进行重传。

但是如果发送方根本就收不到接收方的回复，就只能等待超时重传了，同时，该重传方式还存在着重传多少的问题：

如果只重传一个分片，但其实有可能后续还有一个分片也丢失了，则下一个分片又需要再次经历3次通信，带来不必要的回复开销
如果重传后续的所有分片，但其实有可能后续的分片都已经被接收了，带来不必要的发送开销

SACK方法

全名Selective Acknowledgment，选择性确认。

在TCP首部的选项字段中加入一个SACK字段，在其中填入当前内核缓冲区的序号范围，这样在快速重传时，发送方就知道需要重传哪些分片（就是确认号到SACK中左端点之间的分片）

Duplicate SACK

简称D-SACK，主要目的是告知发送方哪些消息被重复接收了，不直接维护传输的可靠性，只是锦上添花的作用。

同样使用上文提到的SACK字段，只不过这次还会填入接收方收到的小于确认号的序号范围，从而表明这些信息接收方已经收到过了。

TCP滑动窗口

为了提高网络的利用效率引入了滑动窗口，该机制的原理是：发送方在收到接收方的应答前，可以持续发送不超过当前接收方窗口值的数据量

累计确认/累计应答

得益于窗口的这个设计，即使接收方处理信息后中途的确认信息丢失了也不会影响，只要后续的确认信息成功被发送方收到，其确认号就会被更新为最大值，这个现象叫累计确认/累计应答（进而解释了TCP不重传纯粹的ACK报文）

窗口大小

双方在通信过程中不断通过TCP首部的Window字段协商

发送方的滑动窗口

分为四个部分：

已发送且已确认的部分
已发送但未确认的部分
未发送但可发送的部分
未发送也不可发送的部分

通过两个指针和窗口大小确定这四个部分：

第一个指针SND.UNA指向已发送但未确认的第一个字节序号
第二个指针SND.NXT指向未发送但可发送的第一个字节序号
接收方窗口大小SND.WND

其中第一个指针到其加上接收方窗口大小的部分就是滑动窗口，每当接收方回复的确认号增加，该窗口向后滑动

接收方的滑动窗口

分为三个部分：

已接收并确认的数据
未接收且可接收的数据（缓存剩余空间）
未接收且不可接收的数据

通过一个指针和窗口大小确定这两个部分：

第一个指针RCV.NXT指向未接受且可接收的第一个字节序号
接收方窗口大小RCV.WND

第一个指针到其加上接收方窗口大小的部分就是滑动窗口，每当接收方成功组装对应序号的报文，该窗口向后滑动

TCP流量控制

TCP通信的过程中，接收方的窗口大小并不是一成不变的，这个值与系统为它分配的缓存区大小有关。在通信的过程中协商窗口大小的变化，避免发送方发出的数据无法被接收方缓存，进而导致不断重传影响性能，就是TCP的流量控制。

TCP的流量控制的核心点在于，如果系统需要收缩分配的缓存区大小，则必须事先通过通信收缩窗口，然后再减少缓存，避免丢包。

窗口关闭

如果窗口大小缩小为0，就会阻止发送方发送数据，直到窗口变为非0为止，称为窗口关闭。

当窗口关闭结束时，如果通知窗口恢复的报文丢失了，由于TCP不重传纯粹的ACK，就会导致双方进入互相等待的死锁中。为了避免这个问题，每当发送方收到窗口关闭通知后就会启动一个计时器，每次超时就会发送窗口探测（Window probe）报文，接收方使用当前窗口大小回应

糊涂窗口综合症

如果接收方过于繁忙导致窗口很小，每次稍腾出一些缓存发送方就会迫不及待地发送寥寥无几的数据，导致头部数据远远多于通信数据，网络利用率低下，这就是糊涂窗口综合症。

为了避免这个情况出现，需要从两方面同时入手：

对于接收方而言，如果当前窗口小于min(MSS, 缓存空间/2)，则直接通知0窗口；直到这一状况解除才
对于发送方而言，只有可用窗口不小于MSS且可发送数据不小于MSS，或者之前发送的数据已经全部确认，才会发送数据（称为Nagle算法）

TCP拥塞控制

如果网络出现拥塞，导致数据包时延丢失，TCP还不断重传数据，就会导致网络负担进一步加重，形成恶性循环，为了避免这个问题，需要实现拥塞控制。

TCP拥塞控制的实现方式是在发送方维护一个拥塞窗口cwnd，其值随网络的拥塞程度动态变化，在引入这个值后，发送窗口的大小变为接收方可用窗口和拥塞窗口的较小值。TCP认为如果发送方没有在规定时间内收到ACK应答，网络就出现了拥塞，进而减小拥塞窗口；反之则增大拥塞窗口。

慢启动

拥塞窗口初始值较小，随通信正常慢慢增大：每当发送方收到一个ACK应答，cwnd = cwnd+1

慢启动阶段拥塞窗口增长呈现出1，2，4，8……的指数型增长，当到达慢启动门限（slow start threshold，一般为65535）后会转而使用拥塞避免算法

拥塞避免

每当发送方收到一个ACK应答，cwnd = cwnd+1/cwnd

因此，只有这一批报文全部都收到了ACK应答，拥挤窗口才会加1，呈现出线性增长

随着拥塞窗口不断增长，网络负担逐渐加重，直到出现了丢包，触发TCP重传，进入拥塞发生算法

拥塞发生

拥塞发生分两种情况

超时重传（问题比较严重）触发的拥塞发生：将慢启动门限减半，cwnd重置为1
快速重传（问题不太严重）触发的拥塞发生：将cwnd减半，慢启动门限设置为减半后的cwnd，然后进入快速恢复算法

快速恢复

首先将cwnd+3（收到了三个重复的ACK）
然后根据快速重传的机制重传数据
如果仍然收到重复的ACK应答，则将cwnd+1
如果收到了新的ACK应答，则将cwnd置为慢启动门限，进入拥塞避免算法

快速恢复算法的本质是出现拥塞后的慢启动，原因是TCP认为触发快速重传只是偶发性错误，尝试使用最快的速度解决这个丢失的数据包，然后恢复到正常的数据传输

IP篇

基础知识

IP位于网络层，作用是实现点到点通信
IP地址分类：
- A类：首位为0，0~127，前8位为子网号
- B类：首位为1，次位为0，128~191，前16位为子网号
- C类：前两位为1，第三位为0，192~223，前24位为子网号
- D类：前三位为1，第四位为0，224~239，组播/多播地址
- E类：剩下的，240~255，留待后用
- 网络地址：主机号全0的地址
- 广播地址：主机号全1的地址，广播可以分为本地广播（同一子网）和直接广播（不同子网，因安全问题一般不被转发，想要实现这一点需要通过组播地址）
CIDR（Classless Inter-Domain Routing）：在IP地址分类的基础之上引入了子网掩码，从而更细致地划分子网
私有IP地址：
- A类地址：10.0.0.0~10.255.255.255
- B类地址：172.16.0.0~172.31.255.255
- C类地址：192.168.0.0~192.168.255.255
IP分片：IP会对大于MTU的报文进行分片，每种数据链路的MTU不同，如果传输过程中某个分片丢失，整个IP报文作废，因此TCP引入了MSS分片，UDP尽可能不要发送大于MTU的数据报文
IPv6：
- 使用128位，可分配地址变多了
- 可自动配置，不需要DHCP服务器也可以自动分配IP地址
- 简化了首部结构（固定为40字节），提高了传输性能
  - 取消首部校验，将校验交给数据链路层和传输层
  - 取消分片和重新组装相关字段：不允许需要通过路由器的IP报文分片，提高转发速度
  - 取消选项字段：下一个首部字段指出选项的位置
- 能够应对伪造IP地址、防止线路窃听，提高了安全性
- IP地址每16位一组，采用十六进制表示，每组之间用冒号隔开，出现连续的0时可以用两个连续的冒号省略，但是一个地址中只能出现一次连续冒号
- 地址类型：
  - 单播地址，用于一对一通信
    - 不经过路由器的链路本地单播地址
    - 局域网内通信的唯一本地地址
    - 互联网内通信的全局单播地址
  - 组播地址，用于一对多通信
  - 任播地址，用于最近节点通信
回环地址与本机地址：
- localhost：在hosts文件中解析到127.0.0.1
- 127.0.0.1：回环地址，所有目标为该地址的都通过本地网卡发送（实际上并不是网卡，只是一个链表）
- 本机地址：发送之前判断目标地址是否为本机地址，如果是依然通过本地网卡发送
- 0.0.0.0：指定目的地址时不合法，只是应用层的特殊规定，用于监听本机的所有网络接口或访问本机的所有IP地址

RARP

已知MAC地址求IP地址，通常是嵌入式设备接入网络时需要使用，需要RARP服务器建立映射并分配

DHCP

全称Dynamic Host Configuration Protocol

客户端发起DHCP发现报文（DHCP DISCOVER），采用UDP广播，源地址是0.0.0.0（尚未分配），端口68（客户端监听端口）；目标地址是255.255.255.255（广播地址），端口67（服务端监听端口）
DHCP服务器收到DHCP发现报文后，回应DHCP提供报文（DHCP OFFER），采用UDP广播（不知道客户端的IP），报文信息中携带可租约的IP地址，子网掩码，默认网关，DNS服务器及IP租用期
客户端收到DHCP OFFER之后（可能有多个）选择其中的一个，UDP广播DHCP请求报文（DHCP REQUEST），说明自己选择的服务器，IP地址，租期等信息
对应的DHCP服务器收到DHCP REQUEST之后通过UDP广播回复确认配置信息的DHCP确认报文（DHCP ACK）
如果客户端的IP租期过半（50%），就会UDP单播给服务器请求续租；如果续租没有成功，租期快结束了（87.5%）或结束了，就会发送DHCP REQUEST广播
如何解决广播无法跨路由的问题：路由器收到DHCP的广播报文时，会以中继单播的形式发送给DHCP服务器

NAT

全称Network Address (Port) Translation

NAT的思路是同一时刻需要公有IP的数量远小于总计私有IP的数量，而NAPT则解决了NAT中所有私有IP都要上网的问题
使用少量的公有IP解决大量私有IP用户的联网需求，核心是将不同的私有IP服务映射到（同一）公有IP（的不同端口）上，由NAT（NAPT）路由器维护映射关系表
NAT/NAPT存在以下问题：
- 外部无法主动与NAT内部服务器建立连接，因为映射关系表中尚不存在记录
- 转换表的维护产生性能开销
- NAT路由器重启会关闭所有TCP连接
解决上述问题可以使用NAT穿透技术：NAT后的设备向NAT路由器主动申请建立映射，然后使用这个条目对外通信

ICMP

全称Internet Control Message Protocol

其功能包括确认IP包是否成功送达目标地址、报告发送过程中IP包的废弃原因、改善网络设置等
ICMP报文分类：
- 查询报文类型，表示用于诊断的查询消息
- 差错报文类型，通知出错原因的错误消息
  - 目标不可达：分为网络不可达、主机不可达、协议不可达、端口不可达、需要进行分片但设置了不分片
  - 原点抑制：路由器发送队列缓存清0（线路速度低），向源地址发送一个原点抑制，请求降低传输速率，由于可能引起不公平网络通信而一般不使用
  - 重定向：存在更优路由
  - 超时：超出TTL（Time To Live）
PING命令就是基于ICMP查询报文工作的，它向目标主机发送一条回送请求，目标主机收到后将请求的数据通过回送应答送回源主机，从而证明网络可达性
TRACEROUTE命令就是基于ICMP差错报文工作的：
- 通过逐渐增大TTL获取路由路径
- 故意设置不分片获取链路的MTU

IGMP

全称Internet Group Management Protocol

用于区分组播地址需要发送给哪些主机，工作在主机和最后一跳路由器之间
需要加入组播组时，主机只需要向路由器发送请求即可，地址是224.0.0.2（同一网段内所有路由器）
常规查询与响应（只是为了确认哪些组播组仍然存在）：
1. 路由器周期性发送目的地址224.0.0.1（同一网段内所有主机和路由器）IGMP常规查询报文
2. 主机收到常规查询报文后随机延时一段时间，发送IGMP成员关系报告报文（目的IP仍然是组播地址），如果在延时期间收到其他成员的成员关系报告报文，则不再发送
3. 路由器收到该成员关系报告报文后就在IGMP路由表中继续维护该组播组，为后续转发做准备
离开组播组：
1. 如果主机要离开组播组，向224.0.0.2发送IGMP离组报文
2. 路由器收到离组报文后，维护IGMP路由表，然后以1秒为间隔连续发送两个特定组查询报文，如果有主机响应，则继续维护；否则说明该网段内不再存在对应的组播成员，后续不再转发

系统篇

硬件结构

CPU缓存一致性

CPU缓存使用SRAM，相比内存使用的DRAM造价更高，但速度更快，从而能够更充分地利用CPU，但同时也带来了缓存内存、多个CPU缓存一致性的问题

缓存内存一致性

写直达：数据同时写入缓存和内存
写回：写缓存，数据变化才标记脏位，数据被从缓存中替换出时有脏位才写回内存

多CPU缓存一致性

保证多个CPU缓存的一致性需要确保以下两点：

某个CPU缓存更新时，必须要将变化传播到其他CPU缓存，即写传播
任何一个CPU缓存对数据的操作顺序必须都是一致的，即事务的串行化

总线嗅探与MESI协议

总线嗅探负责当某一个CPU缓存发生变化时，要将该事件广播通知到其他CPU，MESI协议通过标记缓存的状态减少了总线的广播压力

软中断

软中断是Linux为了解决中断处理程序执行时间过长和中断丢失问题提出的，将中断分为了两个部分：

上半部分屏蔽中断然后快速处理和硬件紧密相关或时间敏感的事务，也称为硬中断（例如网卡接收数据包时触发的中断，此时系统屏蔽中断，然后内核触发软中断）
下半部分一般以内核线程的方式延迟处理上半部分尚未完成的事务，也称软中断（例如将网卡数据包中的数据移交协议栈，处理后移交应用层）

操作系统结构

内核

内核是上层应用连接硬件设备的桥梁
现代操作系统的内核会提供四个基本能力：
- 进程调度
- 内存管理
- 硬件通信
- 系统调用
只有内核程序可以访问的空间称为内核空间，供应用程序访问的空间称为用户空间，使用用户空间时称为用户态，使用内核空间时则称为内核态

Linux设计

MultiTask

支持多任务并发或并行执行

SMP

对称多处理，意味着每个CPU地位相等，每个程序都可以被分配到任意一个CPU上执行

ELF

可执行文件链接格式

Monolithic Kernel

宏内核，即系统内核所有模块都运行在内核态

相对的微内核只保留最基本的能力，将一些应用放到了用户空间（例如鸿蒙操作系统）

同时还有一种混合型内核，类似于宏内核中包裹了一个微内核（例如Windows系统）

内存管理

虚拟内存

如果两个同时运行的程序能同时访问同一绝对地址对应的物理空间，显然会产生互相的干扰，为了解决这个问题引入了虚拟内存：即使虚拟内存地址值相同，在操作系统的管理下，它们也会映射到不相干涉的物理内存地址

内存分段

将整个物理内存根据需要的大小分为多个段，常见的代码段、数据段、栈段、页段就是这种分段式结构

分段式结构存在内存碎片（零散的小段分布在内存中无法被整块地利用）和内存交换效率低（为了解决内存碎片问题，需要移动零散的内存空间，为了移动这块区域需要将原本的内容写入硬盘的交换空间，即swap分区，然后换回目标位置，这带来了性能瓶颈，尤其是要交换一块很大的空间时）的问题

内存分页

分页将整个内存空间切割为一段段固定大小的页，由MMU（内存管理单元）负责将虚拟地址转换为物理地址的工作以及页表的维护

由于页是预先设计好的紧密划分，所以不会出现外部内存碎片的问题，但由于页成为了最小的内存分配单元，会存在页内空间冗余的内部内存碎片问题

如果内存空间不够，操作系统会把最近没使用的页换出，写入硬盘，将需要使用的页换入，这样内存中存在的始终都是最近需要使用的页，而不需要交换一整段空间，提升了空间交换效率

但这样的分页存在问题，由于每一页的空间相对很小（Linux上是4KB），所以每一张页表需要的空间都相对较大，而每一个进程都需要维护这样一张页表，这将会带来很大的内存开销

多级页表

为了解决单纯的分页带来的巨大内存开销问题，引入了多级页表

这个机制能节约页表带来的内存开销的原理是：使用不分级页表创建进程时，不管进程是否真的需要如此大规模的内存空间，它都必须为它划分好页，并创建好页表；但实际上大部分进程都不会使用这么大规模的内存，导致大部分页表项其实并没有被使用，采用分级页表就可以减少初始的二级页表数量，只创建好最初的一级页表，在需要的时候再创建需要的二级页表。

在64位的操作系统上，页表甚至会变成四级目录：

全局页目录项PGD
上层页目录项PUD
中间页目录项PMD
页表项PTE

TLB

当页表分级变多，虚拟地址转换的步骤也变复杂了，带来了时间上的开销，考虑到程序的局部性，大多数程序最经常访问的页其实很少，所以在CPU中添加一个专用于存放最常用页表项的Cache TLB，并由MMU管理

段页式内存管理

先将内存划分为逻辑段，然后在段中实现分页

进程管理

进程

进程（Process）是CPU正在运行的程序

进程状态

挂起状态有可能是主动挂起（ctrl+z），也有可能是因内存不足换入磁盘的交换空间引起的

进程的控制结构

操作系统通过进程控制块(Process Control Block, PCB)描述进程，其中的信息包括：

进程描述信息：进程标识符和用户标识符
进程控制和管理信息：进程当前状态和进程优先级
资源分配清单：内存地址空间信息、打开的文件列表和I/O设备信息
CPU相关信息：CPU中各个寄存器的值（以便进程的切换）

操作系统通常将状态相同的进程控制块通过链表（插入和删除操作频繁）连接在一起组成各种状态的队列

进程的上下文切换

操作系统中的所有进程共享CPU资源，对于一个CPU核心而言，从正在执行某个进程的状态切换到执行另一个进程的状态叫做进程的上下文切换。

在这个过程中，需要在进程控制块中保存现场（包括虚拟内存，栈，全局变量等用户空间资源以及内核堆栈、寄存器等内核空间资源）

线程

现代操作系统的最小的能独立运行的单位，各个线程可以并发运行并共享内存空间和打开的文件资源，每个线程都有一套独立的寄存器和栈

线程与进程的比较

进程是资源分配的单位，线程是CPU调度的单位
进程独享一个完整的资源平台，线程只独享必要的资源（寄存器和栈）
线程和进程同样具备就绪、阻塞、执行三种基本状态与状态间的切换
线程能减少并发执行时间和空间开销（创建、销毁速度更快；切换更快（不需要切换页表）；线程间共享数据不需要经过内核传递）

线程的上下文切换

如果发生切换的前后线程属于不同进程，则等同于进程切换
如果发生切换的前后线程同属一个进程，由于它们共享内存空间和打开的文件资源，只需要保存并切换线程的私有数据、寄存器等值即可

线程的实现

用户线程（N:1）：完全在用户空间，使用用户态的线程库实现，不由内核管理的线程
- 优点：由用户态线程库实现，可用于不支持线程管理的操作系统；上下文切换不需要内核介入，速度快
- 缺点：如果一个线程发起系统调用而阻塞，整个进程的所有线程都会阻塞（对内核来说，用户线程是不可见的，它只是一个进程，因此调用系统调用后整个进程阻塞）；所有用户线程平级，除非某个线程主动交出CPU的使用权，其他线程无法打断；系统分配时间片给进程，均摊下来每个线程的执行时间更少
内核线程（1:1）：在内核实现，内核管理的线程
- 优点：一个内核线程因系统调用而阻塞并不会打断其他内核线程；系统分配时间片给内核线程，运行时间更长
- 缺点：线程的创建、终止、切换都需要通过系统调用完成，开销大
轻量级进程（M:N）：内核支持的用户线程
- 综合上述两者的优点

调度

按照系统是否会根据时钟中断将执行一段时间的进程强行调度出CPU可以将调度算法分为非抢占式调度算法（一直运行到结束或阻塞）和抢占式调度算法

先来先服务调度算法 FCFS：每次调度就绪队列的队头，非抢占式，适合CPU繁忙的长作业
最短作业优先调度算法 SJF（不可实现）：优先调度运行时间最短的任务，非抢占式，长作业容易饿死
高响应比优先调度算法 HRRN（不可实现）：调度优先权=（等待时间+要求服务时间）/要求服务时间，非抢占式，兼顾了长作业和短作业
时间片轮转调度算法 RR：抢占式，时间用完或阻塞就调度
最高优先级调度算法 HPF：
- 静态优先级/动态优先级：前者在创建进程时就确定优先级；后者动态变化，随运行时间降低优先级，随等待时间升高优先级
- 抢占式/非抢占式
- 低优先级进程可能饿死
多级反馈队列调度算法 Multilevel Feedback Queue：
- 预设多个不同优先级的任务队列，优先级越高的队列时间片越短
- 新的进程放入第一优先级队列末尾，系统按先来先服务调度当前不为空的最高优先级队列
- 如果在某个优先级队列规定的时间片内没能完成任务，就将其放入下一优先级队列的队尾
- 如果当前正在执行较低优先级的任务，同时有新进程加入第一优先级队列，则立刻停止当前的进程，将其放入当前队列的队尾，转而去执行最高优先级队列中的任务

进程间通信方式

管道

将前一个命令的输出作为后一个命令的输入的单向数据传输
匿名管道和命名管道（FIFO）
通信效率低，不适合进程间频繁交换数据，但胜在简单
原理是通过pipe系统调用申请一段内核缓存，返回一个读取端描述符和一个写入端描述符
对于匿名管道，只能用于父进程进行系统调用后，fork出子进程，然后各自使用一端来完成通信（双向通信需要申请两个管道）
对于命名管道，实际上是生成了一个设备文件，可以用于无关进程间的通信

消息队列

消息队列是保存在内核中的消息链表，其中存储了在进程间通信的消息体，消息体在被读取后即被删除
消息队列需要在使用结束后手动释放
消息队列存在通信不及时、附件有大小限制的问题（内核对消息体有大小限制）
消息队列通信过程中存在用户态与内核态之间数据拷贝的开销

共享内存

两个进程选择一块虚拟地址空间映射到相同的物理内存中

信号量

但在虚拟内存的章节已经说过了，如果两个进程不加沟通地任意使用同一物理内存空间势必会导致错误，因此引入了信号量来避免冲突

信号量是一个整型计数器，用于实现进程间的互斥与同步
信号量包含两个原子操作：P（请求资源，计数器减一）和V（释放资源，计数器加一），对于同一进程而言，两个操作必须成对出现
对于共享资源模型而言，信号量初始化为1，保证同一时刻只有一个进程在操作该资源，此时为互斥信号量
对于生产者消费者模型而言，信号量初始化为0，保证消费者在生产者产出后才消费，此时为同步信号量

信号

Linux使用各种信号来通知异常情况，传递指令

信号是异步通信机制（可以随时给任一进程发送信号），其来源包括硬件（如ctrl+c对应的SIGINT信号）和软件（如kill命令对应的SIGKILL信号）
用户进程收到信号后会执行信号对应的默认操作；如果自定义了信号处理函数，则执行信号处理函数（称为捕捉信号）；对于某些非关键的（SIGKILL和SIGSTOP除外）信号，也可以忽略

Socket

跨主机的进程间通信

进程/线程冲突

互斥

操作具备Race Condition的共享变量的代码称为临界区，应该保证这段代码是互斥的，即同一时刻，最多有一个线程/进程在执行临界区的代码

同步

并发的线程/进程在某些关键节点上需要互相等待与互通消息，这种相互制约的等待与互通信息称为线程/进程同步

互斥与同步的实现

锁

上锁与解锁，容易实现互斥，可以通过解锁时通知被锁阻塞的线程/进程来实现同步

信号量

也可以看作是通过信号量实现了锁，见共享内存

锁的分类

自旋锁

也称忙等待锁，如果查询锁的状态并上锁的原子操作失败，则死循环，占用资源却什么也不做（也可以使用CPU提供的PAUSE指令）

互斥锁

也称无等待锁，发现上锁后就阻塞自己，互斥锁将申请的线程/进程加入自己记录的等待队列，解锁时依次调度

但阻塞与调度也是内核实现的，因此存在着用户态到内核态再到用户态的转换，带来性能开销

读写锁

分为读锁和写锁，读取时上读锁，写入时上写锁
写锁是独占锁，读锁是共享锁，实现并行读，串行写‘
可以进一步分为读优先锁、写优先锁和公平读写锁，读优先锁优先服务读进程（允许读进程插写进程的队），写优先锁优先服务写进程（允许写进程插读进程的队），公平读写锁不允许插队

悲观锁&乐观锁

上述锁的种类都是悲观锁，它认为同时修改共享资源导致出错的概率很高，所以访问前一定要上锁；

乐观锁则认为同时修改共享资源导致出错的概率很低，先修改了再说，如果发现了冲突再回退操作，共享文档、Git都是乐观锁，通过版本来校验是否出现了冲突

死锁问题

死锁概念

死锁只有同时满足四个条件才会发生：

互斥条件：多个线程/进程不能同时使用同一资源
持有并等待条件：线程/进程需要多个资源，在等待某个资源时不会释放另一个已经持有的资源
不可剥夺条件：线程/进程持有的资源在自己使用完之前不可被其他线程夺取
环路等待条件：两个线程获取资源的顺序构成了环形链条，即你等我，我等你

可以这样记忆：

首先，资源互斥
其次，出现了你等我，我等你的情况，我们各持有一个都需要的资源
而且，我们任何一方都不愿意放手
同时，你不放手，我还不能抢

避免死锁

破坏上述任意一个条件就可以避免死锁的产生

互斥条件：不太好破坏，除非能保证串行化
环路等待条件：最好破坏，只需要有序分配资源即可，即双方总是按照相同的顺序获取需要的资源
持有并等待条件：可以破坏，如果发现无法获取到某个资源，就释放掉之前获得的资源，下次再从头获取，但效率不高（类似于TCP不分片完全重传）
不可剥夺条件：一般不破坏，否则会出现不公平的情况

MySQL篇

MySQL的架构包含两层结构，分别是上层的Server层（负责建立连接、分析和执行SQL）和下层的存储引擎层（负责数据的存储与提取）

查询语句执行流程

连接器

与客户端进行TCP三次握手建立连接
校验客户端的用户名和密码
读取用户的权限，留作后面校验使用

查询缓存

在缓存中查找是否执行过相同的查询语句且没有失效，如果存在则直接返回
但对一张表只要有一个更新操作，这张表的所有查询缓存都会失效，所以命中率很低
8.0版本起已经被删除了

解析SQL

解析器进行词法分析提取关键字
解析器进行语法分析构建语法树（检测语法错误，但不检测执行错误（如表不存在），即静态检查）

执行SQL

预处理器
- 检查SQL语句中的表和字段是否存在
- 通配符展开
优化器：确定查询语句的执行方案（主要是决定使用的索引）
执行器：以记录为单位和存储引擎交互

存储结构

MySQL的默认存储引擎是InnoDB

文件

创建数据库后会在/var/lib/mysql路径下创建对应的数据库名称目录
目录下包含三个文件：
- db.opt：存储当前数据库的默认字符集和字符校验规则
- t_order.frm：存储表结构，即表的元数据信息
- t_order.ibd：存储表数据，从5.6.6版本开始默认每一张表都有一个独立的ibd文件
表中的记录按行存放
多个行组成一页，页是引擎的读写单位
多张页组成一个区，区是表中数据量过大时分配存储空间的方式，避免多张页的物理地址相隔太远引发随机I/O
多个区构成一个段，包含索引段（B+树非叶节点），数据段（叶节点）和回滚段

行格式

Redundant：结构不紧凑，几乎已经被淘汰
Compact：紧凑行格式
Dynamic：改进Compact
Compressed：改进Compact

Compact行格式

倒序存放变长字段长度列表
倒序存放NULL值列表（一个bit，节省空间，字节对齐）
记录头信息指向下一个行的记录头信息和真实数据之间的位置（所以前面要倒序存放，方便向左读取额外信息，向右读取真实信息）
发生行溢出后多余数据存到溢出页中，行中留下一个指向存储位置的地址

索引

基础概念

索引是帮助存储引擎快速获取数据的一种数据结构，是数据的目录

索引分类

按数据结构分类：B+树索引，Hash索引，Full-text索引
按物理存储分类：聚簇索引（主键索引），二级索引（辅助索引）
按字段特性分类：主键索引，唯一索引，普通索引，前缀索引
按字段个数分类：单列索引，联合索引

按数据结构分类索引

B+树索引

使用平衡多叉搜索树+（B树会在非叶子节点存储中间数据，导致在索引节点多读取一次硬盘，B+树的数据仅存储在叶子节点；此外，B+树的叶子节点之间通过双向链表连通，更适配数据库中范围查询的要求），按照指定列的值构建的搜索索引

Hash索引

哈希索引能够快速完成等值查询，但范围查询（尤其是范围比较大时）的效率远不如B+树索引

按物理存储分类索引

主键索引/聚簇索引

使用列的主键值构建的目录索引；如果没有指定主键，则使用第一个不包含NULL值（NOT NULL）的唯一列（UNIQUE），也即具备主键性质的列构建；如果具备主键性质的列也不存在，则InnoDB生成一个隐式的自增id作为索引键
主键索引的叶节点存储了每一行的所有信息

二级索引/辅助索引

由于用户有时并不一定以主键为条件查询数据，所以有时，在已经存在主键索引的情况下，还会构建其他列作为索引键的二级索引/辅助索引
二级索引的叶节点只存储对应行的主键值，得到主键值之后，如果用户要查找其他信息，需要再通过主键值查找主键索引，这个过程称为回表；否则，不需要查找主键索引（例如用户只查询主键值或只是计数）就可以直接返回，称为覆盖索引

按字段特性分类索引

主键索引

在主键上创建的索引，一张表只能有一个主键索引，创建表时在主键后声明（即使不声明，数据库也会默认在主键上创建索引）：

CREATE TABLE table_name (
    ......
    PRIMARY KEY (index_column_1) USING BTREE
);

唯一索引

在唯一字段上创建的索引，一张表可以有多个唯一索引，允许NULL，在创建表时在创建对应的唯一列后声明（不声明不默认创建）：

CREATE TABLE table_name (
    'id' int(11) UNIQUE,
    'sid' int(8) UNIQUE,
    ......
    UNIQUE KEY(id),
    UNIQUE KEY(sid)
);

也可以在建立表之后再创建：

CREATE UNIQUE INDEX index_name ON table_name(id);
CREATE UNIQUE INDEX index_name ON table_name(sid);

普通索引

在普通字段上创建的索引，一张表可以有多个普通索引，允许NULL，允许不唯一：

CREATE TABLE table_name (
    'score' int(20),
    'age' integer,
    ......
    INDEX(score)
    INDEX(age)
);

也可以在建立表之后再创建：

CREATE INDEX index_name ON table_name(score);
CREATE INDEX index_name ON table_name(age);

前缀索引

针对字符类型字段，仅建立在前几个字符上的索引，基本与普通索引一致，在列名后通过括号指定前缀长度

按字段个数分类

单列索引

顾名思义，上文提到的都是单列索引

联合索引

在多个列之上建立的索引，多个列满足最左匹配原则，即首先比较最左侧的元素，相等的情况下再比较下一个元素

CREATE INDEX index_name ON table_name(column1, column2, ......);

注意，对于联合索引而言，只有在第一个或前一个键值相等的情况下，下一个键才是有序的，即全局无序，局部相对有序。因此，联合索引的查询在查询完全开区间条件后就会停止（编写查询语句时不需要调整条件顺序，优化器会合理调整条件的顺序），因为一旦存在开区间，就代表着下一元素的集合完全无序，而且联合索引必然是二级索引，只知道下一元素属于哪个范围，但并不知道具体的值是多少；闭区间则不会停止，因为端点处的下一元素仍然有序，还可以部分进行

为了解决开区间中的元素只能回到主键索引逐个查询的问题，引入了索引下推优化，它会在遍历联合索引的过程中，先判断联合索引包含的字段，筛选掉不满足条件的记录（遍历时知道哪些行的下一元素不在对应范围内）

在构建联合索引时，应该将索引区分度（不同元素个数/总元素个数）更高的元素置于更左侧的位置

索引的适用场景

适用场景

字段有唯一性限制
经常用于WHERE查询条件的字段
经常用于GROUP BY和ORDER BY的字段

不适用场景

不会被用于WHERE，GROUP BY，ORDER BY的字段，索引是用于快速定位的，如果不需要被用于定位，则不需要创建索引
字段内存在大量重复数据时不需要创建索引（优化器在发现某个值在表中出现比例很高时也会自动放弃索引，采用全表扫描）
表中数据太少时不需要创建索引
数据经常更新的表不需要创建索引，会给B+树的维护带来很大的开销

索引优化方法

前缀索引优化

减小索引字段大小，但存在两个问题：

Order By条件存在时无法使用前缀索引
前缀索引不能被用于覆盖索引（数据不完整）

覆盖索引优化

避免回表，从而不需要查询整行的信息，常见的操作是多联合几行索引

主键索引自增

自增的主键索引可以减少插入新数据时维护B+树的复杂度

同时主键最好不要太长，以减少二级索引的空间占用

Not NULL

存在NULL值会复杂化索引统计等问题、难以选择索引

索引失效

对索引使用包含左模糊匹配的查询

B+树只能从前缀开始定位，像like %Company这样的包含左模糊匹配的查询自然就无从定位了

对索引键值使用函数

索引中记录的是数据的原始值，像length(name)=6这样的条件自然无法定位

但MySQL8.0开始引入了函数索引，即针对函数计算后的值建立索引

对索引键值进行表达式计算

其实和上一个情况很像，但要注意，优化器不会编译优化，哪怕是id+1=10这样的简单表达式也不行（id=10-1是可行的）

对索引键值进行隐式类型转换

本质上还是对键值进行了函数调用，转换成另一个格式

联合索引非最左匹配

前文中已经提到，由于后续元素无序且不知道具体值无法继续查询

条件中包含了不在索引中的键

有一方无索引，所以还是需要全表扫描

事务

事物特性

原子性（Atomicity）：一个事物中的所有操作，要么全部完成，要么一个也不完成，通过回滚日志（undo log）保证
隔离性（Isolation）：多个并发事务同时读写数据时，不会由于交叉操作导致数据不一致，通过MVCC（多版本并发控制）或锁机制保证
持久性（Durability）：事务提交后，对数据的修改是永久的，通过重做日志（redo log）保证
一致性（Consistency，最终目的）：事务操作前后，数据满足完整性约束，数据库保持一致状态，通过上述三个性质共同保证

隔离性

并发事务存在的问题

脏读（dirty read）：一个事务读到了另一个事务修改后但尚未提交的数据
不可重复读（non-repeatable read）：在同一个事务中，前后读取同一个数据的结果不一致（修改已存在）
幻读（phantom read）：在一个事务中，前后读取满足某个条件的记录数量不一致（新增）

事务隔离级别

读未提交：在一个事务提交前，它做出的更改就被允许读取，没有解决任何问题
读提交：在一个事务提交之后，它做出的更改才能被读取，解决了脏读问题，通过在每条语句执行前生成一个Read View实现
可重复读：一个事务执行的过程中，读取到某个数据的值始终一致，这是MySQL InnoDB的默认隔离级别，解决了脏读和不可重复读的问题，通过在事务启动时生成一个Read View实现
串行化：给所有记录加上读写锁，解决了脏读、不可重复读、幻读问题

Read View

Read View有四个重要的字段：
- m_ids：当前数据库中的活跃事务（启动了但还没有提交的事务）id列表
- min_trx_id：m_ids中的最小值
- max_trx_id：m_ids中的最大值
- creator_trix_id：创建该Read View的事务id
主键索引记录中有两个重要的隐藏列：
- trx_id：上次改动该记录的事务id
- roll_pointer：每次改动一条记录时，就将旧版本的记录写入undo log中，并用这个指针指向对应的旧版本记录
所以可以通过由事务id表征的版本链条来描述一条记录对一个事务的可见性，即多版本并发控制MVCC：
- 如果记录的trx_id小于min_trx_id，说明该记录是在创建Read View之前提交的，因此可见
- 如果记录的trx_id大于max_trx_id，说明该记录是在创建Read View之后提交的，因此不可见
- 否则，如果trx_id在m_ids中，则说明该记录还未被提交，因此不可见；如果不在，则说明已被提交，可见
- 对于不可见的记录，会顺着roll_pointer指向的undo log查找最近的可见记录

锁

全局锁

将整个数据库置于只读状态

表级锁

表锁：对表的读写锁，不仅会限制其他线程访问表，也会限制本线程访问其他表
元数据锁：对表操作时自动上锁/解锁
意向锁：单独给某条记录加锁前，先给表加上意向读锁/意向写锁，表明表中有记录被上了对应的锁，从而通知要给表上锁的事务，避免逐个查看
AUTO-INC锁：实现默认主键的自增

行级锁

记录锁：S（读）锁和X（写）锁
间隙锁：避免中间插入，从而避免幻读
临键锁：插入间隙锁的同时给记录上锁
插入意向锁：希望给一个间隙上锁（包括间隙锁和临键锁）时发现已上锁，则添加插入意向锁并阻塞自己，直到封锁的事务提交

原子性

undo log始终记录事务的操作，如果发生错误，则按照undo log执行相反的操作回滚到上一状态

持久性

数据库的存储引擎在提供服务时总是将一页加载到内存中，采用写回的方式以提高性能，但这样就存在着操作丢失的问题，为了避免这个问题，redo log会执行记录事务的操作，以避免操作的丢失

需要注意的是，redo log最开始同样是始终存在于内存中，但它在以下时机会触发落盘：

MySQL正常关闭时
redo log的大小超出缓存的一半时
每隔一秒落盘一次
事务提交时

从上述过程也可以看出来，redo log是工作在存储引擎层面的，还有一种工作在server层面的记录，称为binlog，具有更好的移植性

设计范式

1NF：数据列的原子性，每一列都必须是不可再分的最小数据单元
2NF：消除部分依赖，非主键列必须依赖于整个主键，而不是主键的某一部分
3NF：消除传递依赖，非主键列必须直接依赖于整个主键，而不是通过传递性依赖于主键

Redis篇

基础知识

Redis是开源的内存数据结构，常用于缓存、消息队列、分布式锁等场景
Redis提供了多种数据类型来支持不同的业务场景，并且对这些数据类型的操作都是原子的
Redis原生支持集群模式，具备高性能、高并发的特征

数据结构

String：字符串、整数或浮点数
List：由String组成的链表
Set：包含字符串的无序集合
Hash：包含键值对的无序散列表
Zset：包含键值对的有序散列表
BitMap：位图
HyperLogLog：海量计数使用
GEO：地理位置信息
Stream：消息队列

线程模型

早期Redis的主要功能是单线程完成的（相比CPU，内存大小、网络I/O才是制约其性能的关键），只有两个后台线程负责关闭文件和AOF刷盘
后来加入了一个新的后台线程用于异步释放内存，避免释放很大空间时阻塞主线程
随着网络I/O逐渐成为制约其性能的关键，引入了多线程模型处理网络I/O，但核心功能仍然是单线程的
单线程的核心功能避免了资源竞争带来的开销、同时使用内存的特征使得Redis效率极高

持久化方式

AOF日志：后台线程将执行的命令写入硬盘，存在总是写回、每秒写回和不控制写回（操作系统控制），通过AOF重写解决日志膨胀问题，读取每个值的状态，将多条包含历史的命令压缩为最后状态的一条命令
RDB快照：保存一瞬间的内存数据，解决了通过AOF命令恢复速度慢的问题，但保存需要时间，且会带来性能开销，可以在主线程执行保存，也可以在子线程执行
混合持久化：前半部分是RDB，后半部分是AOF，兼具AOF丢失数据少和RDB恢复速度快的优点

Redis集群

主从复制：主服务器可读可写，从服务器只可读，从服务器从主服务器获取数据更新信息，数据不是强一致
哨兵模式：哨兵监控主节点状态，并提供主从节点故障转移功能，避免主节点宕机需要手动恢复
切片集群模式：解决了数据太多无法被一台服务器缓存的问题，但存在脑裂问题（主从节点通信故障，导致另选主节点，此时原主节点恢复），解决方法是主节点发现可连接的从节点小于阈值后主节点拒绝写请求，直到新主节点上线

过期删除策略

惰性删除：访问时发现过期才删除，返回NULL
定期删除：定期随机挑选一部分检查，过期删除
两种机制同时作用，对于恢复过程，只有AOF写入时会写入过期键，AOF重写不考虑过期键；RDB不记录过期键，所以理论上恢复时也不会恢复过期键