性能优化 (二)：性能分析 (数据结构与算法、网络、数据库)

性能分析

分析性能瓶颈，需熟悉整个计算机体系的基本运行原理，才能快速判断问题的根源

数据结构与算法

1. 算法度量标准

• 时间复杂度：执行当前算法所消耗的时间

• 空间复杂度：执行当前算法需要占用多少内存空间

• 多项式与非多项式：看算法的时间复杂度

多项式算法：时间复杂度以n为底数，比如：O(1), O(n), O(n^a)；

非多项式算法：时间复杂度为以n为指数或阶乘，比如O(n!), O(a^n)，复杂度以数量级呈指数级上升；

2. NP问题

• P问题：用一个确定性算法在多项式时间内求出解。复杂度是此类问题的一个实例的规模n的多项式函数。比如：排序问题，秋最短路径问题；

• NP问题：有些问题很难找到多项式时间的解法，也许根本不存在。但如果给出该问题的一个解，可在多项式时间内判断这个解是否正确。P问题是NP问题的子集；

• NPC问题：NP complete, 如果所有NP问题都能在多项式时间内转化为A, 则A为NPC问题；NPC是NP的子集；

• NPH问题：NP hard, 问题A不一定是一个NP问题，但所有的NPC问题都可以在多项式时间内转化为A, 则A为NPH问题；



3. 数据结构

• 数组

线性表的一种，特点：

连续空间，必须存放相同的数据类型

随机读写，时间复杂度O(1)

插入和删除，时间复杂度O(n), 数组空间用完，还需新申请+拷贝



• 链表

线性表的一种，特点：

使用零散内存空间储存数据，查找时间复杂度O(n)

插入和删除时间复杂度O(1)



• Hash表

数组+链表， 实现快速查找，快速增删

可能发生Hash冲突



• 栈

线性表基础上加操作限制条件“后进先出”

应用场景：线程栈



• 队列

线性表基础上加操作限制条件“先进先出”

应用场景：生产者/消费者， 阻塞等待线程



• 树

i) 二叉排序树：左子树<根节点，右子树>根节点

ii) 不平衡二叉排序树：退化链表，O(n)

iii) 平衡二叉树: 任一节点，左右子树深度之差绝对值不超过1, O(logn)

添加/删除节点，变得不平衡。解决：旋转二叉树恢复平衡（左旋，右旋）

插入：最多两次旋转可恢复；删除：需多次才能恢复，时间复杂度O(logn) 。解决：引入红黑树

iv) 红黑树

只有红色、黑色节点，根节点是黑色，每个叶子节点都是黑色的空节点；从根节点到叶子节点不会出现连续的红色节点；从任何一个节点出发，到叶子节点，这条路径都有相同数目的黑色节点。

增删节点时，红黑树通过染色、旋转， 最多3次旋转会重新达到平衡，时间复杂度O(1), 查询效率比平衡二叉树差一些



• 跳表

链表(顺序) + 稀疏链表(多层)， 空间复杂度增加

4. 算法

• 穷举算法

较少数据量是可以使用的

• 递归算法

自己调用自己，包含：退出条件，退出函数，递归条件

可能栈溢出，时间复杂度O(nlogn)



• 贪心算法

背包问题解决，思想：每一步找最优解，可能并不是最终最优解

改进：地杰斯特算法(最快路径)：起点到每个节点的最快路径



• 动态规划

思想：将一个大问题拆解成若干小问题



• 遗传算法

模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解得方法。可能得不到最优解，而是较优解

网络通信协议

1. 互联网应用网络架构



2. OSI七层模型 与 TCP/IP 四层模型

OSI七层模型：Physical Layer, Data Link Layer, Network Layer, Transport Layer,Session Layer,Presentation Layer,Application Layer

TCP/IP四层模型：Network Access Link Layer, Internet Layer,Transport Layer, Applicatin Layer



网络数据包格式：



i) 物理层：负责数据的物理传输，让不同的设备能理解、处理相同的二进制数据；

ii) 链路层：将数据封装成数据帧后交给物理层进行传输，在帧上进行数据校验，进行流量控制。并在封装好的帧上添加一个帧头，头里记录发送者和接收者的MAC地址。

iii) 网络层：IP协议，网络层的数据需交给链路层进行处理，数据包有一个协议头，包含发送者和接收者的IP地址

iv) 传输层：TCP协议，IP协议不是可靠协议，不会建立稳定的通信链路。要保证通信的稳定可靠，需传输层协议TCP。是一种面向连接、可靠的、基于字节流的传输层协议。作为基础的通讯协议，有很多机制保证TCP协议的可靠性和强壮性，包含：使用序号，无错传输，使用确认和计时器，流量控制，拥塞控制，丢失包重传。建立可靠连接，包含：TCP 三次握手，客户端才可主动发起；TCP四次挥手，双方都可主动发起

v) 应用层：HTTP协议等其他协议

3. HTTP协议

请求方式

• Get: 只读请求，请求处理过程不应该产生副作用，不应该因Get请求而发生任何状态改变；

• Head: 和Get方法一样，但只返回响应头

• Post: 提交请求

• Put: 上传请求

• Delete: 删除URL标识的资源

• Trace: 回显服务器收到的请求，用以测试、诊断

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

响应状态

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

• 2xx 成功：请求已成功被服务器接收，处理，响应

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

• 4xx 请求错误：请求含有语法错误或无法被执行

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

HTTP协议版本

• HTTP1.0

• HTTP1.1：保持连接，缓存处理，带宽优化及网络连接优化，错误通知管理，Host头处理

• HTTP2.0：并发复用TCP连接，但还是存在队头堵塞，还包含：降低延迟，请求优先级，header压缩，基于HTTPS加密协议传输，服务端推送Server Push

• HTTP3.0：QUIC协议，包含：1.减少TCP三次握手及TLS握手时间：基于UDP本身没有连接概念，建立连接只需一次交互；2.多路复用丢包时的队头阻塞问题：TCP连接上多个stream,一个丢包，需重传补充；QUIC多stream 无依赖，不影响其他stream；3. 优化重传策略：TCP 重传用一个sequence number,影响后续重传计算的耗时， QUIC每个封包有一个新的unique packet number; 4. 流量控制：连接层connection, Stream层流量控制，可对单个stream进行流量控制；5. 连接迁移：TCP连接基于四元组(源IP,源端口，目标IP, 目标端口)，网络变化需重新建连； QUIC连接是一个64随机数进行标识，connection ID没有变化，连接依然可维持。



非阻塞网络IO

1. 阻塞 VS 异步

阻塞：线程， 是看应用程序是否阻塞，而不是看实现逻辑中语句是否有阻塞

异步：执行时状态

2. Client与Server端Socket通信模型演变

i) 单线程: 阻塞点包含 socket.accept(), Inputstream.read(), OutputStream.write()，连接数n+1

ii) 多线程:阻塞点socket.accept(), 获取socket后开启线程进行读写操作

iii) 线程池：启动线程方式使用线程池

iv) 非阻塞IO: 使用Java NIO实现非阻塞IO

3. Blocking IO , Socket

阻塞IO: 进行IO操作时，用户线程会一直阻塞，直到读/写操作完成

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



4. Non-Blocking IO, Java New IO

非阻塞IO: IO操作立即返回，发起线程不会阻塞等待。线程轮询完成读写操作。读写操作可使用生产者/消费者算法实现。

Java NIO实现

i) selector:持续轮询channel事件状态，决定对Channel的操作。可读/可写/新连接

ii) buffer:缓冲区

iii) selectionKey：Channel状态

iv) selectableChanel：Channel通道

Selector.select()方式也是阻塞的，但应用程序整体不是阻塞的。

5. 系统IO复用方式

i）select：与poll类似

ii) poll：轮询查询状态

iii) epoll: eventPoll, 在FDList中读状态

数据库架构

1. 数据库整体架构



2. PrepareStatement预编译

PrepareStatement会预先提交带占位符的SQL到数据库进行预处理，提前生成执行计划，当给定占位符参数，真正执行SQL时，执行引擎可直接执行，效率更好一点。还可防止SQL注入攻击。

3. B-树与B+树

B树，中间节点保存数据；

B+树，只有叶子节点保存数据，且所有的叶子节点依关键字的大小自小而大顺序链接。会使得查询效率更高效；

4. 索引

分类：

i) 聚簇索引:聚簇索引的数据库记录和索引储存在一起，Mysql数据库的主键就是聚簇索引，主键ID和所在记录行储存在一个B+树上。

ii) 非聚簇索引：非聚簇索引在叶子节点记录不是数据行记录，而是聚簇索引，也就是主键。 通过非聚簇索引找到主键索引，再通过主键索引找到行记录的过程叫 回表。



注意：

i) 添加必要的索引优化SQL查询效能，

ii) 谨慎使用索引(生产环境不要盲目添加索引导致添加索引耗时长查询阻塞；删除不用的索引；使用更小的数据类型创建索引)

5. 数据库事务

关系型数据的事务特性，包含：

原子性(Atomicity): 要么全部完成，要么全部取消

隔离性(Isotation): 两个事务相互间的隔离，靠锁实现

持久性（Durability): 一旦事务提交，不管发生崩溃或出错，数据要保存数据库。

一致性（Consistency）：与CAP中一致性不同，是指合法数据(满足约束和完整性)才能写入



通过数据库事务日志，来保证事务的原子性、持久性。