架构师训练营 第 8 周总结

本周学习内容：

• 数据结构与算法

• 网络通信协议

• 非阻塞网络 I/O

• 数据库架构原理与性能优化

数据结构与算法

架构师需要掌握基本的数据结构与算法，算法不要求深入，但需要熟练掌握数据结构的应用场景。

首先要掌握基本概念：

时间复杂度、空间复杂度，描述的是算法的性能；

NP 问题，P 指的是能在多项式时间复杂度内解决的问题，NP 表示能在多项式时间复杂度内验证是否正确。

基本数据结构及应用：

• 数组，连续的内存空间，且须存相同的数据类型，适用于随机读写的场景，时间复杂度 O(1)，但增删需要动态调整保持空间连续，影响性能，所以不适合增删场景；

• 链表，数据存储在零散的内存空间，且可以是不同的数据类型，读写只能通过顺序遍历定位，性能差，但增删是 O(1)，所以适用于频繁增删数据的场景；

• Hash 表，将 key 经过 hash 计算映射到数组索引，实现快速定位读写，且内存空间是固定的，不需要维持连续，除非在空间不够时需要动态扩容之类的，当 key 冲突时，可以转为链表存储；缺点是 hash 之后数据一般没办法填满内存空间，会有一定的内存浪费，如果是复杂的 hash 计算也可能损耗一定的性能；

• 栈，先入后出的结构，利用这种操作受限的特性，满足类似函数嵌套调用时需要保证后声明的函数先返回的要求；

• 队列，也是操作受限的结构，先入先出，典型场景是生产者与消费者模式，还可以利用在广度优先遍历，求最小路径的问题；

• 树，一种二维的结构，典型的有二叉树、二叉排序树、平衡二叉树，其中红黑树实现了近似平衡二叉树，因为维护平衡的代价太高；广泛应用在各种排序场景、数据库存储场景；

• 跳表，多级索引的链表，适用于快速增删改查的场景，应用在 redis kv 存储；

常用算法

• 穷举：暴力求解；

• 递归：深度优先、广度优先，递归代码往往简洁、表现力强；

• 贪心：从局部最优可推导到全局最优；改进版本的贪心：迪杰斯特拉算法；

• 动态规划：动态递推，填表的方式，套路一般是找出存在的状态，定义状态转换方程，然后编码实现；典型问题：背包问题、股票问题、编辑距离等；

• 遗传算法：初始化数据后，通过选择、交叉、变异，不同调整参数，最终达到最优解，但可能不是全局最优；

网络通信协议

OSI 七层网络模型

• 物理层：二进制数据传输，交换机；

• 链路层：数据帧传输，以 MAC 地址为依据，会对数据进行错误检测，避免数据错漏；

• 网络层：IP 包传输，IP 协议；

• 传输层：开放端口，进行端对端传输，TCP/UDP 协议；

• 会话层：连接功能；

• 表示层：转换数据格式、加密、数据压缩；

• 应用层：为应用服务提供访问网络的支持；

TCP/IP 四层模型

以 TCP/IP 协议族应用最广泛，且形成了自己的层次结构；

• 链路层：对应 OSI 的物理层与链路层；

• 网络层：对应 OSI 的网络层；

• 传输层：对应 OSI 的传输层；

• 应用层：对应 OSI 的会话层、表示层、应用层；

分层原因

网络数据经过层层包装，屏蔽下层实现细节，上层只关注数据的使用，下层负责数据传输，也是设计上的解耦合，封装的同时也保证传输的可靠性、完整性。

传输层的 TCP 协议

TCP 在传输层，是一种面向连接、可靠的、基于字节流的传输协议。实现了序号控制、流量控制、拥塞控制、丢包重传的功能。在连接创建和断开时，也有固定的模式，三次握手、四次挥手，主要是为了解决网络通信不可靠的问题。

HTTP 协议

超文本传输协议，广泛应用于互联网。

版本演进：

• http1.0 每次请求都需要建立 tcp 连接

• htt1.1 复用 tcp 连接，但每个 tcp 连接同时只有一个请求独享

• http/2 多个请求可同时使用一个 tcp 连接，但是前一个请求的数据传输会堵塞其它请求，因为 tcp 理解不了 http，只能按顺序接收 http 数据，不能实现 http 请求并发；

• http/3 用 QUIC 替换 TCP，多个请求流数据可同时传输，真正实现请求并发；QUIC 基于 UDP，不需要握手和慢启动创建流，但会进行数据校验，是可靠的；

非阻塞网络 I/O

传统多线程方法

1. 为每个请求 socket 创建一个线程

2. 维护一个线程池，新请求 socket 进来从线程池获取线程托管，优点在于不用每次都创建和释放进程，减少系统调用

阻塞型网络 I/O

每个 socket 的读写都会独占线程资源，读写期间不能做其它事情，直到 socket 释放

非阻塞网络 I/O

线程发起 socket 后会立即得到返回，不会阻塞等待操作完成，直到有数据需要进一步操作再通知线程继续

java 的 NIO 即是非阻塞 I/O

数据库架构与优化

• 连接器：管理数据库连接池，及其会话的上下文

• 语法分析：分析 sql 语法

• 语义分析与优化：将分析后的 sql 进入语义化，结合索引做进一步优化；

prepareStatement

数据库操作一般使用 prepareStatement，因为其方便数据库对 sql 进行预处理，不用每次都对完整的 sql 进行分析，相当于利用前面分析过的相同的 sql 片段，减少编译、分析的时间。

B+树

将节点改为多叉，存储更多的数据，减少树的层级，也就减少了磁头切换的次数，从而减少数据查找的耗时，提高数据库性能。

事务

基本原理：事务前的数据记录在数据库日志前，事务回滚时从中拿数据恢复。

数据库日志类型：

• undo log 记录未完成的操作，需要回滚；

• redo log 记录已经写日志成功，但没有持久化成功的操作，需要在数据库恢复后重新执行，这些操作是幂等的，重复执行不影响数据一致性；redo log 是通过磁盘数据块的一致性保证的，一次写一个块，要么成功要么失败。

参考：https://draveness.me/mysql-transaction/

启发

• 数据库的一致性最终还是得落到某个能保证强一致性的地方，比如上述说到的磁盘写数据块的原子性；

• 数据结构都是基于数组这种结构做的演化，毕竟 CPU 只认识内存这种随机读写的介质，如果利用这种介质解决各种实际问题，就需要靠算法，算法的特殊性往往需要特定的数据结构，所以又将数组抽象封装成各种适配的结构；

• 无论是架构设计还是数据结构算法，都依托于某个基本的计算机原理特性做的演进，学习知识可以知道这种演进，同时也能学到很多演进或优化的套路，但最终还是需要理解其背后的原理及逻辑，才能对其有更清楚的认识。