08 性能优化（二）

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

文件与硬盘 I/O

机械硬盘

空气过滤片、主轴、音图马达、永磁铁、磁盘、磁头、磁头臂

磁盘旋转非常快，但是磁头的移动比较慢，如果读取离散数据（数据在不同的磁道上），那么磁头的移动、起落会比较慢（毫秒级别）。读取硬盘数据的速度快慢主要取决于数据是否连续。

固态硬盘

固态硬盘连续读写同样比随机读取要快。

B+ 树

每次读取一个磁盘块来查找，根节点一般存储在内存中。

数据库的索引一般存在 B+ 树中。

每次读取磁盘块的时候，可能需要移动磁臂，受限于磁盘块的离散存储。

LSM 树

日志方式，连续读取

文件控制块

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

Linux Inode 文件控制块

文件控制块在 Linux 中是固定大小的，除了文件的基本信息，就是要存储的数据。Linux 的文件块，只支持三级索引。

• inode 中记录着文件权限、所有者、修改时间和文件大小等文件属性信息，以及文件数据块硬盘地址索引

• inode 是固定结构的，能够记录的硬盘地址索引数也是固定的，只有 15 个索引

• 每个 inode 最多可以存储 12 + 256 + 256*256 + 256*256*256 个数据块，如果每个数据块的大小为 4k，也就是单个文件最大不超过 70G

05 丨文件系统原理：如何用 1 分钟遍历一个 100TB 的文件？  

05 | 从 RAID 看垂直伸缩到水平伸缩的演化

06 | 新技术层出不穷，HDFS 依然是存储的王者

RAID 独立硬盘冗余阵列

读写文件的时候，在多个磁盘上读写，提高性能。磁盘阵列硬盘热插拔。

商业硬盘普通使用寿命大概一年

• RAID 0 将数据分片写入多块硬盘，读写效率高，但是数据可靠性差，任意一块硬盘损坏，数据都不可读，实践中很少用

• RAID 1 同时向两块硬盘写入数据，极大提升了数据安全性，但是效率很差

• RAID 10 硬盘分为四组，通过分片提高了性能，通过复制实现了可靠性，磁盘空间浪费较多

• RAID 5 业界使用最广泛的，留一块磁盘记录校验信息，任何一块磁盘损坏，可以通过校验信息恢复，性能提升，磁盘利用率很高，可靠性也很高。校验数据一般采用异或方式计算，方便计算丢失的数据。螺旋式记录校验位，如果记录在一块磁盘上（RAID 3），那么该磁盘会成为瓶颈，访问压力大，寿命短。

• RAID 6 计算两个校验信息，即使丢失两块盘，仍然能够恢复，提高了数据可靠性，但是磁盘利用率下降

分布式文件系统 HDFS

将数据分片存储在不同的服务器上，性能提升上百倍

数据块 64M

通过数据复制保障可用性（降低空间利用率，复制 3 份，比 RAID 10 更低）

当一个 Datanode 没有心跳的时候，Namenode 就会认为已经死机，给集群中其他服务器发送信息，复制该 Datanode 上的所有数据块

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

时间复杂度与空间复杂度

时间复杂度

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

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

• 多项式时间复杂度：O(1)，O(log(n))，O(na) 

• 非多项式时间复杂度：O(an)，O(n!)

空间复杂度

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

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

NP 问题

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

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

NP ?= P 

如果能在多项式的时间复杂度内验证一个问题，那么能够找到一个在多项式间复杂度内的算法

区块链的 Hash 证明，显然是一个 NP 问题，但是找到 Hash 却是一个非常复杂的计算问题，非多项式复杂度

NP-hard 问题：比 NP 问题更难的问题，多个 NP 问题的解法可以规约到 NP-hard 问题的解法

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

数独问题：

旅行商问题：

数组

创建数组必须在内存中有一块连续的空间，数组中必须存放相同的数据类型（数组中存放的数据元素长度必须是相同的）

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

链表

链表可以使用零散的内存空间存储数据，链表中的每个数据元素都必须包含一个指向下一个数据元素内存地址的指针，链表对数据元素的长度不作要求

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

链表中增删数据的时间复杂度为 O(1)，比数组 O(n) 性能好（在数组总增删元素需要移动数据元素）

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

这个难道不是 Hash 表么？

Hash 表

栈

数组和链表都被成为线性表。

栈就是在线性表的基础上增加了限制条件：后进先出 LIFO

线程运行时专有内存为什么被成为线程栈？

线程调用栈

void f() {    int x = g(1);    // g 函数返回，当前堆栈顶部为 f 函数栈桢，在当前栈桢继续执行 f 函数的代码    x++; }int g(int x) {    return x + 1;}

队列

队列也是一种操作受限的线性表，先进先出 FIFO

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

这幅图的来源是《图解算法》的第六章广度优先算法，原本是寻找芒果经销商（mango seller）

用队列搜索最短路径

这个是课后练习。

有点犹豫，要不要趁机通读一下 Grokking Algorithms

8.3 红黑树原理与性能特性

树

二叉排序树

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

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

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

查找时间复杂度为 Log(n)

不平衡的二叉排序树 vs 平衡二叉（排序）树

平衡二叉（排序）树：从任何一个节点出发，左右子树深度之差的绝对值不超过 1，左右子树仍然为平衡二叉树

旋转二叉树恢复平衡

插入时，最多只需要两次旋转，就能恢复平衡

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

《14 | 二叉排序树：如何动态查找第 k 大元素？》

《15 | AVL 树：如何让二叉排序树永远保持最优？》

红黑（排序）树

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

根节点是黑色

每个叶子节点（nil）都是黑色的空节点

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

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

增删节点的时候，红黑树通过染色和旋转，保持红黑树满足定义

红黑树 vs. 平衡二叉树

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

在大量增删的情况下，红黑树的效率更高

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

跳表

数据首先构建成有序链表

8.4 经典算法

1. 穷举算法

暴力 brute force

在数目不是很多的情况下，往往是更有效的

1. 递归算法

def quicksort(array):

    if len(array) < 2:

        return array    # 基线条件：为空或只包含一个元素的数组是“有序”的

    else:

        pivot = array[0]    # 递归条件

        # 由所有小于基准值的元素组成的子数组

        less = [i for i in array[1:] if i <= pivot]

        # 由所有大于基准值的元素组成的子数组

        greater = [i for i in array[1:] if i > pivot]

        return quicksort(less) + [pivot] + quicksort(greater)

print quicksort([10, 5, 2, 3])

时间复杂度：n*log(n)

1. 贪心算法

背包问题

迪杰斯特拉算法（最快路径）

1. 找出“最便宜”的节点，即可在最短时间内到达的节点

2. 更新该节点邻居的开销，检查是否有前往它们的更短路径，如果有，就更新其开销

3. 重复这个过程，直到对图中的每个节点都这样做了

4. 计算最终路径

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

1. 动态规划

动态规划解决背包问题

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

遗传算法解决背包问题

基因编码与染色体

适应函数与控制函数

选择算法

交叉遗传

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

编辑

删除

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

Web 请求的一次网络通信历程

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

网路数据包格式

Packets and Frames are the names given to Protocol data units (PDUs) at different network layers

• Segments are units of data in the Transport Layer (TCP/UDP in case of the Internet)

• Packets are units of data in the Network Layer (IP in case of the Internet)

• Frames are units of data in the Link Layer (e.g. Wifi, Bluetooth, Ethernet, etc).

• Data: PDU of Application, Presentation and Session Layers

• Segment: PDU of Transport Layer

• Packet: PDU of network Layer

• Frame: PDU of data-link Layer

• Bit: PDU of physical Layer

物理层 Physical

物理层负责数据的物理传输，计算机输入输出的只能是 01 这样的二进制数据，但是在真正的通信线路里有光纤、电缆、无线各种设备。光信号和电信号，以及无线电磁信号在武力上是完全不同的，如何让这些不同的设备能够理解、处理相同的二进制数据，这就是物理层要解决的问题。

链路层 Data Link

链路层就是将数据进行封装后交给物理层进行传输，主要就是将数据封装成数据帧，以帧为单位通过物理层进行通信，有了帧，就可以在帧上进行数据校验，进行流量控制。

链路层会定义帧 Frame 的大小（最大传输单元 MTU ）。数据链路层会将封装好的帧添加一个帧头 Frame header，其中记录发送者和接收者的 MAC 地址。

MAC 地址是网卡的唯一设备标识符，数据帧通过这个信息确保数据送达正确的目标及其。

数据链路层负载均衡

网络层（IP 协议）

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

网络层的数据需要交给链路层进行处理，而链路层帧的大小定义了最大传输单元，网络层的 IP 数据包必须要小于最大传输单元才能进行网络传输，这个数据包也有一个 IP 头（Packet header），主要包括的就是发送者和接收者的 IP 地址。

IP 负载均衡

传输层（TCP 协议）

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

TCP 协议是一种面向连接的、可靠的、基于字节流的传输层协议。

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

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

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

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

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

TCP 建立连接的 3 次握手协议

TCP 关闭连接的 4 次挥手

应用层（HTTP 协议）

互联网应用需要在全球范围为用户提供服务，将全球的应用和用户联系在一起，需要一个统一的应用层协议，HTTP 协议。

HTTP 相应的 5 种状态

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

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

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

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

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

HTTP 协议版本

1. Get：只读，请求处理过程中不应该产生副作用，即 Web 应用不会因为 Get 请求而发生任何状态改变

2. Head：只返回响应头

3. Post：提交

4. Put：上传

5. Delete：删除

6. Trace：回显服务器收到的请求，用以测试或者诊断

7. Options：请求服务器返回支持的所有 HTTP 请求方法，测试服务器是否正常

• HTTP/1.0

1996 年发布，客户端和服务器之间交换的每个请求、相应都会创建一个新的 TCP 连接，也就是说，所有请求之前都需要进行 TCP 握手连接，所有请求都会产生延迟。

The original model of HTTP, and the default one in HTTP/1.0, is short-lived connections. Each HTTP request is completed on its own connection; this means a TCP handshake happens before each HTTP request, and these are serialized.

• HTTP/1.1

HTTP/1.1 试图引入保持连接 Keep-Alive 概念来解决这些问题，允许客户端复用 TCP 连接，从而分摊了建立初始连接和针对多个请求缓慢启动的成本；但任意时间点上每个连接只能执行一次请求、响应交换。

随着网络的发展，网站所需资源（CSS、JavaScript 和图像等）不断增长，浏览器在获取和呈现网页时需要越来越多的并发性。由于 HTTP/1.1 只允许客户端同时进行一次 HTTP 请求、响应交换，所以在网络层上获得并发能力的唯一方法是并行使用多个 TCP 连接。

A persistent connection is one which remains open for a period of time, and can be reused for several requests, saving the need for a new TCP handshake, and utilizing TCP's performance enhancing capabilities.

Pipelining is the process to send successive requests, over the same persistent connection, without waiting for the answer. This avoids latency of the connection. Theoretically, performance could also be improved if two HTTP requests were to be packed into the same TCP message. The typical MSS (Maximum Segment Size), is big enough to contain several simple requests, although the demand in size of HTTP requests continues to grow.

Today, every HTTP/1.1-compliant proxy and server should support pipelining, though many have limitations in practice: a significant reason no modern browser activates this feature by default.

• HTTP/2

HTTP/2 引入了 HTTP “流” 的概念，允许将不同的 HTTP 并发的复用到同一 TCP 连接上，使浏览器更高效的复用 TCP 连接。HTTP/2 解决了单个 TCP 连接使用效率低下的问题，可以通过同一连接传输多个请求、响应。但是，TCP 并不理解 HTTP 流，当多个 HTTP 请求复用一个 TCP 连接，如果前面的请求、响应没有处理完，后面的请求、响应也无法处理，会出现队头阻塞的情况。

• HTTP/3

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

QUIC ( Quick UDP Internet Connections) is a new transport which reduces latency compared to that of TCP. On the surface, QUIC is very similar to TCP+TLS+HTTP/2 implemented on UDP. Because TCP is implemented in operating system kernels, and middlebox firmware, making significant changes to TCP is next to impossible. However, since QUIC is built on top of UDP, it suffers from no such limitations.

8.6 非阻塞网络 I/O

计算机之间如何进行网络请求？

服务器 — 客户端

多线程服务器 — 客户端

线程池服务器

BIO Blocking I/O 阻塞 I/O

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

Socket 接收数据，系统内核的处理过程

NIO Non-Blocking I/O 非阻塞 I/O 

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

非阻塞 read：

• Socket 接收缓冲区有数据，读 n 个（不保证数据被完整读完，因此有可能需要多次读）

• Socket 接收缓冲区没数据，则返回失败（不等待）

非阻塞 write：

• Socket 发送缓冲区满，返回失败（不等待）

• Socket 发送缓冲区不满，写 n 个数据（不保证一次性全部写入，因此可能需要多次写）

Java NIO (New I/O)

Java IO 与 NIO 比较

传统 java.io 包，基于流模式实现，提供 File 抽象、输入输出流等，同步阻塞方式交互。很多时候，java.net 下面的网络 API，比如 Socket、ServerSocket、HttpURLConnection 也归类到同步阻塞 IO 类库（网络通信同样是 IO 行为）

Java 1.4 引入 NIO 框架（java.nio 包），提供 Channel、Selector、Buffer 等新的抽象，构建多路复用的、同步非阻塞 IO 程序，提供更接近操作系统底层的高性能数据操作方式。

Java 7 中，NIO 改进为 NIO 2，引入异步非阻塞 IO 方式，也称之为 AIO（Asynchronous IO）

• IO 不仅仅是对文件操作，网络编程中，比如 Socket 通信，都是典型的 IO 操作目标

• 输入流、输出流（InputStream/OutputStream）适用于读取或写入字节的，例如操作图片文件

• 而 Reader/Writer 则是用于操作字符，增加了字符解码等功能，适用于类似从文件中读取或写入文本信息。本质上计算机操作的都是字节，不管是网络通信还是文件读取，Reader/Writer 相当于构建了应用逻辑和原始数据之间的桥梁

• BufferedOutputStream 等带缓冲区的实现，可以避免频繁的磁盘读写，进而提高 IO 处理效率

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

8.7 第八周课后练习

作业一：（至少完成一个）

1. 有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。请用代码（或伪代码）描述算法，并给出时间复杂度。

2. 请画出 DataNode 服务器节点宕机的时候，HDFS 的处理过程时序图。

作业二：根据当周学习情况，完成一篇学习总结