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

8.1 文件与硬盘 I/O：如何把硬盘的读写速度提高十万倍？

• 机械硬盘

• 磁头移动比较慢，至少毫秒级

• 如果数据是离散的，机械过程非常慢，随机的读写效率很低。

• 固态硬盘

• 没有机械装置，速度快

• 尽量要用连续的存储方式

• B+树

• 传统的数据库采取 B+树的数据结构

• 数据库索引是记录在 B+树上的，通过索引去查找记录。离散数据查找很慢。

• LSM 树 (Log-Structured Merge-Tree)

• 先在内存中构建一个树，当这个树超过了一个范围的时候，就把这个树合并到外部去。在合并的时候以日志的方式刷出去，连续读写，速度非常快。

• 文件控制块

文件系统将硬盘空间以块为单位进行划分，每个文件占据若干个块，然后再通过一个文件控制块 FCB 记录每个文件占据的硬盘数据块。

• Linux Inode 文件控制块

• 有 12 个数据块指针

• 一个一级间接索引指针； 一个二级间接索引指针；一个三级间接索引指针

• RAID 独立硬盘冗余阵列

• RAID 0 - 读写速度快， 数据安全性差。

• RAID 1 - 有完整的备份，提升了数据的安全性，但性能较差。

• RAID 10 - 高可用，高性能，浪费磁盘。

• RAID 5 - 通过一块磁盘记录校验信息，通过校验信息反算，磁盘利用率高。通过亦或操作，计算校验信息。

• RAID 6 - 两个校验信息

• 分布式文件系统 HDFS

• NameNode - 相当于文件控制块，记录元数据。

• DataNode - 存储数据，64M 一个数据块。

• 安全性 - 缺省复制三份数据块，跨机架复制。

8.2 常见数据结构与 Hash 表原理分析

• 时间复杂度与空间复杂度

• 时间复杂度

• 并不是计算程序具体运行的时间，而是算法执行语句的次数。

• O(2^n) 表示对 n 数据处理需要进行 2^n 次计算

• 多项式时间复杂度

• 非多项式时间复杂度 - 计算时间庞大，非有效解

• 空间复杂度

• 一个算法在运行过程中临时占用存储空间大小的量度。

• O(n) 表示需要临时存储 n 个数据。

• NP 问题

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

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

• NP ?= P

• NP-hard 问题：比 NP 问题更难的问题（NP 问题的解法可以规约到 NP-hard 问题的解法）

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

• 数组

• 创建数组必须要内存中一块连续的空间。

• 数组中必须存放相同的数据类型。

• 随机快速读写是数组的一个重要特性，根据数组的下标访问数据，时间复杂度为 O(1)。

• 查找快，增加删除 O(N)

• 链表

• 链表可以使用零散的内存空间存储数据。

• 所以链表中的每个数据元素都必须包含一个指向下一个数据元素的内存地址指针。

• 要想在链表中查找一个数据，只能遍历链表，所以链表的查找复杂度总是 O(N)。

• 增加/删除 O(1)

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

• Hash 表

• 既快速访问数据，又快速增删数据

• Hash 冲突

• 栈

• 数组和链表都被称为线性表。

• 栈就是在线性表的基础上加了这样的操作限制条件：后面添加的数据，在删除的时候必须先删除，即通常所说的“后进先出”。

• 线程调用栈

• 队列

• 队列也是一种操作受限的线性表，栈是后进先出，而队列是先进先出。

• 典型应用场景：生产者消费者；阻塞等待的线程被放入队列。

8.3 红黑树原理与性能特性

• 树

• 二叉排序树

• 左子树上所有结点的值均小于或等于它的根结点的值。

• 右子树上所有结点的值均大于或等于它的根结点的值。

• 左、右子树也分别为二叉排序树。

• 不平衡的二叉排序树 - 退化成链表

• 平衡二叉（排序）树

• 从任何一个节点出发，左右子树深度之差的绝对值不超过 1。

• 左右子树仍然为平衡二叉树。

• 旋转二叉树恢复平衡

• 插入时，最多只需要两次旋转就会重新恢复平衡。

• 删除时，需要维护从被删节点到根节点这条路径上所有节点的平衡性，时间复杂度 O(logN)。

• 红黑（排序）树

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

• 根节点是黑色的。

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

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

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

• 跳表

8.4 经典算法

• 递归算法

• 自己调用自己

• 退出条件 (基线条件)

• 递归条件

• 贪心算法 - 贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

• 改进贪心算法- 迪杰斯特拉算法（最快路径）

• 迪杰斯特拉算法的核心是找到起点到每个节点的最快路径

• 动态规划算法解决背包问题

• 每个动态规划算法都从一个网格开始

• 遗传算法解决背包问题

• 遗传算法（Genetic Algorithm, GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。

• 基因编码与染色体 - 选择初始染色体：随机产生（也可以人为或者算法选择）

• 适应函数与控制参数

• 选择算法

• 轮盘赌选择（Roulette Wheel Selection）

• 随机竞争选择（Stochastic Tournament）

• 均匀排序

• 交叉遗传

• 遗传算法得到的不是最优解

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

• OSI 七层模型和 TCP/IP 四层模型

• 网络数据包格式

• 物理层

• 链路层

• 链路层会定义帧的大小，这个大小也被称为最大传输单元。像 HTTP 要在传输的数据上添加一个 HTTP 头一样，数据链路层也会将封装好的帧添加一个帧头，帧头里记录的一个重要信息就是发送者和接受者的 MAC 地址。MAC 地址是网卡的设备标识符，是唯一的，数据帧通过这个信息确保数据送达到正确的目标机器。

• 数据链路层负载均衡

• 网络层

• 网络层 IP 协议使得互联网应用根据 IP 地址就能访问到目标服务器，请求离开 App 后，到达运营服务商的交换机，交换机会根据这个 IP 地址进行路由转发，可能中间会经过很多个转发节点，最后数据到达目标服务器。

• IP 负载均衡

• 传输层（TCP 协议）

• IP 协议不是一个可靠的通信协议，不会建立稳定的通信链路，并不会确保数据一定送达。要保证通信的稳定可靠，需要传输层协议 TCP。

• TCP 协议是一种面向连接的、可靠的、基于字节流的传输层协议。TCP 作为一个比较基础的通讯协议，有很多重要的机制保证了 TCP 协议的可靠性和强壮性

• TCP 建立连接的 3 次握手过程

• TCP 关闭连接 4 次挥手

• 应用层 HTTP 协议

• HTTP 请求的 7 种方法

• Get

• Head

• Post

• Put

• Delete

• Trace

• Options

• HTTP 响应的 5 种状态

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

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

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

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

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

• HTTP 协议版本

• HTTP/1.0 - 客户端和服务器之间交换的每个请求/ 响应都会创建一个新的 TCP 连接

• HTTP/1.1 - 允许客户端复用 TCP 连接

• HTTP/2 - HTTP/2 引入了 HTTP“流”的概念，允许将不同的 HTTP 并发地复用到同一 TCP 连接上， 使浏览器更高效地复用 TCP 连接。

• HTTP/3 - HTTP/3 不是使用 TCP 作为会话的传输层，而是使用 QUIC （一种新的互联网传输协议）。QUIC 数据包封装在 UDP 数据包。

8.6 非阻塞网络 I/O

• 网络请求

• 服务器 - 客户端

• 多线程服务器 - 客户端

• 线程池服务器

• BIO Blocking I/O 阻塞 I/O

阻塞 I/O：进行 I/O 操作时，用户线程会一直阻塞，直到读操作或者写操作完成。

• 非阻塞 I/O（ Non-Blocking I/O ）

• 非阻塞 I/O：I/O 操作立即返回,发起线程不会阻塞等待。

• Java NIO (New I/O)

• 系统 I/O 复用方式：select，poll，epoll

• Select（poll） 管理下的 read 过程 - 遍历 Socket，高并发性能比较差

• epoll 管理下的 read 过程 - epoll 需要操作系统本身支持，构建 event 列表，在列表上指定了在哪些 Socket 上有事件到达。在 Socket 很多的时候，性能获得很大的提升。