架构师训练营第八周学习总结

文件系统与磁盘I/O

• 磁盘I/O

• 机械硬盘在接受到读取指令时，磁盘旋转至文件所在扇区，磁头从磁道读取信号；固态硬盘所有操作都是电子操作，比机械硬盘更快

• 无论是固态硬盘还是机械硬盘，连续读写都比随机读写的性能更强

• B+树

• 传统数据库使用B+树存储

• 每个节点分配磁盘块

• 可以通过较短的高度存储大量数据，通常高度不超过4，存储量可达几千万条

• 查找过程中仍需多次磁盘访问

• LMS树（Log Structured Merge Tree）以日志方式存储，可实现连续读写

• 文件系统

• 文件系统中以文件块为单位分配空间，每块的大小为4k

• Linux系统通过Inode文件控制块，记录文件信息，包括文件权限、所有者、修改时间、大小等信息，以及12个直接数据块指针和三个间接索引表指针，通过这15个索引能访问到的数据块为12+256+256*256+256*256*256 个数据块，如果每个数据块大小为4k，单个文件不超过70G

• 通过直接数据块指针可以直接访问数据块，通过间接索引表指针访问数据块，需要多次磁盘访问，访问速度更慢

• 为了提高磁盘读写效率，通常使用RAID独立硬盘冗余阵列代替单块硬盘，目前最常见的类型是RAID 5，这种类型的阵列将数据分片存储在不同磁盘上，同时通过异或运算生成校验位，校验位以螺旋方式轮流存储在不同磁盘中，当其中某块磁盘损坏造成数据块丢失时，可通过校验位和其他数据块恢复数据

• 通过HDFS分布式文件系统，可以极大提高大文件的存储效率和可用性

• NameNode存储文件元数据，包括文件名、副本数等数据；

• 文件以数据块为单位存储在DataNode上，文件写入时会同时向其他DataNode复制，一个数据块会同时存在三个副本

• DataNode与NameNode通过心跳检测保持状态报告，DataNode宕机时，NameNode发出指令将失效的DataNode的数据块重新复制（秒级），保持3个备份

常见数据结构与Hash表原理

• 时间复杂度：

• 多项式时间复杂度：O(1)，O(log(n))，O(n^a)，非多项式时间复杂度：O(a^n)，O(n!)，应用中只有多项式时间复杂度的算法才有意义

• NP问题

• P问题：能在多项式时间复杂度内解决的问题

• NP问题：能在多项式时间复杂度内验证答案正确与否的问题

• NP-hard问题：比NP问题更难的问题，NP问题的解法可以归一到NP-hard问题的解法，即一类NP问题的通性问题

• NP完全问题：是NP-hard问题，也是NP问题

• 常用数据结构

• 数组：以连续内存空间存储，每个元素具有相同长度，因此可以直接通过数组地址和下标计算元素地址，读取复杂度为O(1)，然而数组中增删元素时，都需要移动相应下标之后的元素，因此增删复杂度为O(N)

• 链表：元素离散存储，每个元素包含指向下一个元素地址的指针，查找元素需要依次从表头开始往下遍历，因此查找复杂度为O(N)，增删时只需要该表插入或删除位置元素指向下一个元素指针的指向，因此增删复杂度为O(1)

• 数组与链表结合可以实现快速查找和快速增删

• Hash表以数组为容器，每个元素存储指向数据链表的指针，访问数据时通过hash值余数取模计算下标，存储至对应下标指向的链表，可以实现快速查找和修改

• 栈和队列：数组和链表都被称为线性表，栈和链表都是操作受限的线性表，可以通过数组或者链表实现，栈的操作限制是后进先出，队列的操作限制是先进先出。

• 栈的应用实例为线程栈和线程栈桢、深度优先算法等

• 队列的应用实例为生产者消费者模式、消息队列、线程阻塞等待（公平锁）、广度优先算法等

红黑树原理与性能特征

• 二叉排序树与平衡二叉树：

• 二叉排序树的左子树所有节点的值均小于根节点的值，右子树所有节点的值均大于根节点的值，左子树和右子树都是二叉排序树

• 二叉排序树的查找时间复杂度为O(log(n))，增删时间复杂度为O(1)，然而不平衡的二叉排序树的查找性能会降低，极端情况下，二叉排序树会退化为链表

• 平衡二叉树通过旋转保持平衡，使得左右子树的深度差绝对值不超过1，从而使查找时间复杂度不超过O(log(n))；删除节点时，旋转可能由被删除节点处扩散至根节点，因此删除的时间复杂度为O(log(n))

• 红黑树：

• 定义：

• 每个节点只有两种颜色：红色和黑色

• 根节点是黑色的

• 每个叶子节点都是黑色的空节点

• 从根节点到叶子节点，不会出现两个连续的红色节点

• 从任何一个节点出发，到叶子节点的路径上都有相同数目的黑色节点

• 红黑树通过染色和旋转，保持红黑树满足定义

• 红黑树VS平衡二叉树：

• 红黑树最多只需3次旋转就能重新达成红黑平衡，时间复杂度O(1)

• 大量删除的情况下红黑树效率更高

• 红黑树平衡性不如平衡二叉树，查找效率差一些

• 跳表

• 构建过程：数据元素构成有序链表，每一层取出部分（通常是一半）元素上跳形成新层，查找过程由最上层开始，类似二叉树查找

• 特点：查找和修改的速度快，构建简单，空间复杂度高

经典算法

• 穷举法：列举所有可能，找到最优解，在可能数很少的情况下适用

• 递归算法：应用之一为快速排序算法，递归调用必须要有退出条件

• 贪心算法：每一步都做出当前最好的选择，得到局部最优解，迪杰斯特拉算法（最快路径）使用改进的贪心算法实现：1. 找出“最便宜”的节点，即可在最短时间内到达的节点，2. 更新该节点的邻居的开销，检查是否有前往它们的更短路径，如果有，就更新其开销；3. 重复这个过程，直到对图中的每个节点都这样做了；4. 计算最终路径

• 动态规划算法：通过找到合适的角度，将所求解的目标值在某（几）个维度上展开，将一个大问题拆解为若干小问题，从小问题的最优解，寻找大问题的最优解

• 遗传算法：性能非常好，不是最优解，但通常情况下使可以接受的解

网络通信基本原理与性能优化

• OSI七层模型：应用层、表示层、会话层、传输层、网络层、数据链路层、物理层

• TCP/IP四层模型：应用层、传输层、网络层、数据链路层

• 一般数据传输过程中，发送时储层叠加协议头，接收时逐层解包

• 传输层（TCP协议）通过多种机制实现可靠性和强壮性：

• 使用序号，对收到的TCP报文段进行排序和检测重复的数据

• 无错传输，使用校验和检测报文段的错误

• 使用确认和计时器来检测和纠正丢包或者延时

• 流量控制，避免主机分组发送得过快而使接收方来不及完全收下

• 拥塞控制，发送方根据网络承载情况控制分组的发送量，以获得高性能同时避免拥塞崩溃

• 丢失包的重传

• TCP连接通过3次握手建立连接，通过4次挥手断开连接：

• 3次握手：

• 第一次握手：客户端先发送SYN=1，Seq=X 的报文，表示请求建立连接，X 是一个随机数；客户端进入SYN-SEND状态

• 第二次握手：服务器应答SYN=1，ACK=X+1，Seq=Y 的报文，表示同意建立连接；服务器进入SYN-RCVD状态

• 第三次握手： 客户端检查ACK 的值为自己发送的Seq 值+1，确认建立连接，并发送ACK=Y+1 的报文给服务器；客户端进入ESTABLISHED状态

• 服务器收到这个报文后检查ACK 值为自己发送的Seq值+1，确认建立连接，服务器进入ESTABLISHED状态。

• 4次挥手：

• 第一次挥手：客户端发送一个FIN=M，客户端进入FIN_WAIT_1状态

• 第二次挥手：服务器端收到FIN后，先发送ack=M+1，告诉客户端，你的请求我收到了，但是我还没准备好，请继续你等我的消息，服务器进入CLOSE_WAIT状态。这个时候客户端就进入FIN_WAIT_2 状态，继续等待服务器端的FIN报文。

• 第三次挥手：当服务器端确定数据已发送完成，则向客户端发送FIN=N报文，告诉客户端，好了，我这边数据发完了，准备好关闭连接了。服务器端进入LAST_ACK状态。

• 第四次挥手：客户端收到FIN=N报文后，就知道可以关闭连接了，但是他还是不相信网络，怕服务器端不知道要关闭，所以发送ack=N+1后进入TIME_WAIT状态，如果Server端没有收到ACK则可以重传。服务器端收到ACK后，就知道可以断开连接了。客户端等待了2MSL（Maximum Segment Lifetime：最长报文段寿命，2分钟）后依然没有收到回复，则证明服务器端已正常关闭，那好，我客户端也可以关闭连接了。最终完成了四次握手。

• HTTP协议响应状态有以下5类：

• 1xx消息——请求已被服务器接收，继续处理

• 2xx成功——请求已成功被服务器接收、理解、并接受

• 3xx重定向——需要后续操作才能完成这一请求

• 4xx请求错误——请求含有词法错误或者无法被执行

• 5xx服务器错误——服务器在处理某个正确请求时发生错误

• HTTP各版本的区别：

• HTTP/1.0 每次请求/响应创建一个新的TCP连接;

• HTTP/1.1 允许复用TCP连接，但任意时间点每个连接只能执行一次请求/响应

• HTTP/2.0 引入HTTP“流”概念，允许将不同的HTTP并发地复用同一TCP连接，可以通过同一连接同时传输多个请求/响应，但仍然存在队头堵塞的问题

• HTTP/3 使用QUIC协议，该协议在传输层将流作为一等公民引入，多个QUIC 流共享相同的QUIC 连接，因此不需要额外的握手和慢启动来创建新的QUIC 流。但QUIC 流是独立的，因此在大多数情况下，只影响一个流的丢包不会影响其他流，这是因为QUIC 数据包封装在UDP数据包。

非阻塞I/O

• 阻塞式编程：每个请求建立一个连接，启动一个线程

• 阻塞点1：等待请求

• 阻塞点2：read数据，阻塞直到数据到达，CUP不数据拷贝到socket缓冲区

• 阻塞点3：write数据，如果输出缓冲区已满，需等待CPU把输出缓冲区拷贝并通过网卡发送出去才能继续写入

• 非阻塞I/O：

• 多路复用：多个channel使用一个selector

• 非阻塞I/O，使有限的线程/资源，服务更多的并发请求