第八周 性能优化（二）

文件系统与硬盘 I/O

机械硬盘 VS 固态硬盘

机械硬盘（HDD）主要由：盘片，磁头，盘片转轴及控制电机，磁头控制器，数据转换器，接口，缓存等几个部分组成。磁头可沿盘片的半径方向运动，加上盘片每分钟几千转的高速旋转，磁头就可以定位在盘片的指定位置上进行数据的读写操作。信息通过离磁性表面很近的磁头，由电磁流来改变极性方式被电磁流写到磁盘上，信息可以通过相反的方式读取。

固态硬盘（SSD）是用固态电子存储芯片阵列而制成的硬盘，具有快速读写、质量轻、能耗低以及体积小等特点，不过一旦硬件损坏，数据较难恢复等，闪存具有擦写次数限制的问，耐用性（寿命）相对较短。

• 外观造型、体积的差异

• 机械硬盘一般是 3.5 英寸，一般笔记本上的 mini 机械硬盘也有 2.5 英寸，而 SSD 固态硬盘的 SATA 接口产品，最大的是２.５英寸。

HDD vs. 2.5" SSD vs. M.2 SSD

• 读写速度的差异

• 寿命的差异 - SSD 固态硬盘寿命不如机械硬盘, 但是读取并不会导致 SSD 固态硬盘寿命的减少，只有写入才会。固态硬盘的写入方式则是擦除后重新写入。

• 价格差异 - SSD 固态硬盘的价格要比机械硬盘高，主要原因是因为制造成本

B+ 树

B+树和二叉树、平衡二叉树一样，都是经典的数据结构。

LSM 树

LSM 树（Log-Structured-Merge-Tree）和 B+树类似，它们被设计出来都是为了更好地将数据存储到大容量磁盘中。相对于 B+树，LSM 树拥有更好的随机写性能。LSM 树会将所有的数据插入、修改、删除等操作保存在内存之中，当此类操作达到一定的数据量后，再批量地写入到磁盘当中。而在写入磁盘时，会和以前的数据做合并。在合并过程中，并不会像 B+树一样，在原数据的位置上修改，而是直接插入新的数据，从而避免了随机写。

文件控制块 FCB

文件系统将硬盘空间以块为单位进行划分，每个文件占据若干个块，然后再通过一个文件控制块 FCB 记录每个文件占据的硬盘数据库。就算所存储的数据比文件控制块小，依然要占据一个文件块。

Linux Inode 文件控制块

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

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

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

RAID 独立硬盘冗余阵列

标准 RAID

• RAID0

• 优点：使用 n 颗硬盘，即可拥有将近 n 倍的读写效能。

• 缺点：数据安全性较低，同组数组中任一硬盘发生问题就会造成数据遗失。

• 硬盘数量：最少 2 个。

• 
  

• RAID1

• 优点：安全性依照数组里的实体硬盘数量倍数成长。

• 缺点：空间利用率是所有 RAID 中最没有效率的。

• 硬盘数量：最少 2 个。

• RAID5

• 优点：兼顾空间利用率与安全性。

• 缺点：需要额外的运算资源，仅能忍受 1 个硬盘损毁。

• 硬盘数量：至少 3 个。

• RAID6

• 优点：容错硬盘数量比 RAID 5 多 1 颗。

• 缺点：运算量比 RAID 5 大、空间利用率比 RAID 5 低。

• 硬盘数量：至少 4 个。

混合 RAID

• RAID N+N

• 在厂商支持的情况下，使用者甚至可以将 2 种以上的 RAID 组态放在同 1 组磁盘阵列内，也就是有时可以看到的双位数 RAID 01、10、50、60……等。

• 建立的方式也很好理解，首先利用前位数字的 RAID 方式建立数组，接着再将后方数字所代表的数组建立其上。

分布式文件系统 HDFS

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

“常见的算法是编程思维的修炼，用到用不到的都应该好好学习算法。”

数据结构和算法的思维脑图

数据结构

• 数组

• 必须要在内存中一块连续的空间

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

• 随机快速读写，根据小标访问，时间复杂度 O(1)

• 链表

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

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

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

• 链表中增删数据要比数据性能好的多

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

• Hash(哈希) 表

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

• Hash 表 Key 冲突

• 队列

• 先进先出的数据结构，可以用数组实现，也可以用链表实现。

• 阻塞等待的线程被放入队列。

• 典型应用场景：生产者消费者

• 用队列搜索好友中关系最近的有钱人

• 用队列搜索最短路径

• 栈

• 后进先出的数据结构，可以用数组实现，也可以用链表实现。

• 线程栈

• 树

• 二叉排序树

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

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

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

• 平衡二叉排序树

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

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

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

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

• 红黑（排序）树

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

• 根节点是黑色的。

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

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

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

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

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

• 跳表

• 跳着查找链表中的元素

• 需要额外的空间复杂度 O(n)

经典算法

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

算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

• 时间复杂度是一个函数，它定性描述该算法的运行时间。时间复杂度常用大 O 符号表述，一般不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷（n 表示）时的情况。

• 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，它也是问题规模 n 的函数。

四大常用算法

递归算法

是指一种通过重复将问题分解为同类的子问题而解决问题的方法。常用来解决的问题有：

• 数据的定义是按递归定义的。如费氏数列。

• 问题解法按递归算法实现。如汉诺塔。

• 数据的结构形式是按递归定义的。如二叉树、广义表等。

• 递归算法的 Python 模版

# Pythondef recursion(level, param1, param2, ...):     # recursion terminator     if level > MAX_LEVEL: 	   process_result 	   return     # process logic in current level     process(level, data...)     # drill down     self.recursion(level + 1, p1, ...)     # reverse the current level status if needed

贪心算法

是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。对于大部分的问题，贪心法通常都不能找出最佳解，因为他们一般没有测试所有可能的解。贪心法容易过早做决定，因而没法达到最佳解。不过也有例外，在某些图论上可以得到最优解，如著名的 Prim 算法、Kruskal 算法均为贪心算法。

动态规划

通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。著名的动态规划算法有：最长公共子序列、Floyd-Warshall 算法、Viterbi 算法等等。

例子，买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

输入: [7,1,5,3,6,4]输出: 7解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出,     这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，     在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

def use_dp(self, prices):        """        dp_i_0: Sale at ith day        dp_i_1: Hold at ith day        """        length = len(prices)        dp_i_0 , dp_i_1 = 0, float('-inf')        for i in range(length):            temp = dp_i_0            dp_i_0 = max(dp_i_0, dp_i_1 + prices[i])            dp_i_1 = max(dp_i_1, temp - prices[i])        return dp_i_0

遗传算法

最初是借鉴了进化生物学中的一些现象而发展起来的搜索算法，这些现象包括遗传、突变、自然选择以及杂交等等。遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称为个体）可抽象表示为染色体，使种群向更好的解进化。遗传算法擅长解决的问题是全局最优化问题，例如，解决时间表安排问题就是它的一个特长，很多安排时间表的软件都使用遗传算法，遗传算法还经常被用于解决实际工程问题。

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

一次 web 请求的过程

宏观

首先来看看一次 web 请求在网络中传输的大致过程

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

1. 客户端通过 query 域名服务器，进行域名解析，得到服务器端的 IP 地址，通常来说，域名解析会有一个 30 分钟左右的有效期。

2. 客户端产生一个 HTTP 请求，域名解析返回的 IP 地址有可能是多个，比如 CDN 服务器，以及部署在数据中心的负载均衡服务器。如果是 CDN 的 IP，那么 CDN 中已经有了内容，直接返回，如果 CDN 没有内容，那么 CDN 再去建立和负载均衡服务器的链接获取内容。动态内容一般不经过 CDN (HTTP 协议)

3. 请求到达负载均衡服务器之后，会被分发给一级的反向代理服务器集群 (HTTP 协议)

4. 如果一级反向代理服务器缓存没有所需要内容，则再继续请求二级负载均衡服务器 (HTTP 协议)

5. 二级负载均衡服务器把请求分发给网关服务器 (HTTP 协议)

6. 网关服务器则把请求交给相应的微服务应用服务器去处理 (RPC 协议)

7. 微服务有可能再访问缓存服务器或者数据库服务器或者消息队列等低层服务，获取相应数据

8. 数据获取之后，再层层返回到客户端

微观

再从微观角度来看一个 HTTP 请求数据包的产生。数据从客户端的浏览器，逐层下走，每经历一层，就会在已有的数据包上增加一个 header

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

网络传输控制协议有两种最基本的模型——OSI 和 TCP/IP 协议。如图所示：两者都是标准模型，相比之下 OSI 更为严谨详实；但是经过多年斗争，TCP/IP 胜出，因为简单粗暴才更能被广泛应用。

下面是 TPC/IP 各层协议，我们常听见的专业术语其实都是 TCP/IP 里某一层的协议

HTTP 协议

应用层中最最常用是 HTTP 协议；它是一种在客户端和服务器之间编码和传输数据的方法，一个请求/响应协议：客户端和服务端针对相关内容和完成状态信息的请求和响应。HTTP 是独立的，允许请求和响应流经许多执行负载均衡，缓存，加密和压缩的中间路由器和服务器。

一个基本的 HTTP 请求由一个动词（方法）和一个资源（端点）组成。 以下是常见的 HTTP 动词：

另外 “TRACE” 和 “OPTIONS”用的不多，基本用于诊断和测试。

TCP 协议

TCP 是通过 IP 网络的面向连接的协议。使用握手建立和断开连接。

• TCP 建立连接就是经典的三次握手，过程如下：

• TCP 的断开连接是四次挥手：

1. 客户端发送一个 FIN 段，并包含一个希望接收者看到的自己当前的序列号 K. 同时还包含一个 ACK 表示确认对方最近一次发过来的数据

2. 服务端将 K 值加 1 作为 ACK 序号值，表明收到了上一个包。这时上层的应用程序会被告知另一端发起了关闭操作，通常这将引起应用程序发起自己的关闭操作

3. 服务端发起自己的 FIN 段，ACK=K+1, Seq=L

4. 客户端确认，ACK=L+1

IP

IP 是 Internet Protocol（网际互连协议）的缩写，是 TCP/IP 体系中的网络层协议，可将 IP 信息包从源设备传送到目的设备。IP 协议依赖于 IP 地址（网络中唯一的地址）和路由（传送方式）两种机制。我们最常用的负载均衡——IP 负载均衡，就是通过 IP 地址分发流量到不同的服务器中。

网络编程

Socket

Socket 是应用层与传输层（TCP、UDP）之间的一个软件抽象层，它是一组接口。在设计模式中，Socket 其实就是一个门面模式，它把复杂的 TCP/IP 协议族隐藏在 Socket 接口后面，对用户来说，一组简单的接口就是全部，让 Socket 去组织数据，以符合指定的协议。

Socket 通信的过程如下：

1. 服务器端先初始化 Socket，然后与端口绑定（bind），对端口进行监听（listen），调用 accept 阻塞，等待客户端连接

2. 客户端初始化一个 Socket，然后连接（connect）服务器；如果成功，客户端与服务器端的连接就建立了

3. 客户端发送数据请求，服务器端接收请求并处理请求，然后把回应数据发送给客户端，客户端读取数据

4. 最后关闭连接，一次交互结束

IO 介绍

为了更好地了解 IO 模型，我们需要事先回顾下：同步、异步、阻塞、非阻塞

• 同步与异步针对的是函数/任务的调用方式：同步就是当一个进程发起一个函数（任务）调用的时候，一直等到函数（任务）完成，而进程继续处于激活状态。而异步情况下是当一个进程发起一个函数（任务）调用的时候，不会等函数返回，而是继续往下执行当，函数返回的时候通过状态、通知、事件等方式通知进程任务完成。

• 阻塞与非阻塞针对的是进程或线程：阻塞是当请求不能满足的时候就将进程挂起，而非阻塞则不会阻塞当前进程

IO 发生时涉及的对象和步骤。对于一个 network IO (这里我们以 read 举例)，它会涉及到两个系统对象，一个是调用这个 IO 的 process (or thread)，另一个就是系统内核(kernel)。当一个 read 操作发生时，该操作会经历两个阶段

• 等待数据准备 (Waiting for the data to be ready)

• 将数据从内核拷贝到进程中(Copying the data from the kernel to the process)

阻塞 IO(blocking IO)

当用户进程调用了 recvfrom 这个系统调用，kernel 就开始了 IO 的第一个阶段：准备数据。对于 network io 来说，很多时候数据在一开始还没有到达（比如，还没有收到一个完整的 UDP 包），这个时候 kernel 就要等待足够的数据到来。

而在用户进程这边，整个进程会被阻塞。当 kernel 一直等到数据准备好了，它就会将数据从 kernel 中拷贝到用户内存，然后 kernel 返回结果，用户进程才解除 block 的状态，重新运行起来。

所以，blocking IO 的特点就是在 IO 执行的两个阶段（等待数据和拷贝数据两个阶段）都被 block 了。

一个阻塞的例子

# Serverfrom socket import *server = socket(AF_INET, SOCK_STREAM)server.bind(('127.0.0.1',8081))server.listen(5)
while True:    conn, addr = server.accept()    print(addr)
    while True:        try:            data=conn.recv(1024)            if not data:break            conn.send(data.upper())        except ConnectionResetError:            print("ConnectionResetError")            break    conn.close()
server.close()

# Clientfrom socket import *
client = socket(AF_INET, SOCK_STREAM)client.connect(('127.0.0.1',8081))
while True:    msg=input('>>: ').strip()    if not msg:continue    client.send(msg.encode('utf-8'))    data=client.recv(1024)    print(data.decode('utf-8'))

非阻塞 IO(non-blocking IO)

从图中可以看出，当用户进程发出 read 操作时，如果 kernel 中的数据还没有准备好，那么它并不会 block 用户进程，而是立刻返回一个 error。从用户进程角度讲 ，它发起一个 read 操作后，并不需要等待，而是马上就得到了一个结果。用户进程判断结果是一个 error 时，它就知道数据还没有准备好，于是用户就可以在本次到下次再发起 read 询问的时间间隔内做其他事情，或者直接再次发送 read 操作。一旦 kernel 中的数据准备好了，并且又再次收到了用户进程的 system call，那么它马上就将数据拷贝到了用户内存（这一阶段仍然是阻塞的），然后返回。

也就是说非阻塞的 recvform 系统调用调用之后，进程并没有被阻塞，内核马上返回给进程，如果数据还没准备好，此时会返回一个 error。进程在返回之后，可以干点别的事情，然后再发起 recvform 系统调用。重复上面的过程，循环往复的进行 recvform 系统调用。这个过程通常被称之为轮询。轮询检查内核数据，直到数据准备好，再拷贝数据到进程，进行数据处理。需要注意，拷贝数据整个过程，进程仍然是属于阻塞的状态。

所以，在非阻塞式 IO 中，用户进程其实是需要不断的主动询问 kernel 数据准备好了没有

非阻赛例子

# Server
from socket import *import timeserver = socket(AF_INET, SOCK_STREAM)server.bind(('127.0.0.1',8083))server.listen(5)server.setblocking(False)
conn_l=[]
while True:    try:        conn, addr = server.accept()        conn_l.append(conn)        print(addr)    except BlockingIOError:        print('Doing sth else',len(conn_l))        del_l = []        for conn in conn_l:            try:                data=conn.recv(1024)                if not data:                    conn.close()                    del_l.append(conn)                    continue                conn.send(data.upper())            except BlockingIOError:                pass            except ConnectionResetError:                conn.close()                del_l.append(conn)
        for conn in del_l:            conn_l.remove(conn)       # Clientfrom socket import *
client = socket(AF_INET, SOCK_STREAM)client.connect(('127.0.0.1',8083))
while True:    msg=input('>>: ').strip()    if not msg:continue    client.send(msg.encode('utf-8'))    data=client.recv(1024)    print(data.decode('utf-8'))

总结

这节信息量还是很大的，光是算法和数据结构就已经是一个超级大的话题了，再加上文件系统，RAID 和网络编程，感觉一周的时间如果算上上班，那基本只是回顾或者学习新的概念了，如果不保持持续学习或者复习，估计很快会忘记，知识点多，每个也不简单，老师也没有办法让大家从技能上来熟练。只能从大的层面先熟悉，然后再靠平时的点滴积累练习。数据结构和算法倒是可以在 leetcode 上每天刷题，但是网络编程，文件系统和 RAID 就不是那么好练习了。