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

第八周的两次课程中, 主要在课程中学习了数据结构与算法, 网络和数据库方面的知识。

关键知识点总结

数据结构和算法

时间复杂度和空间复杂度

时间复杂度和空间复杂度是衡量一个算法 "好与坏" 的标准。

时间复杂度

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

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

• O(1), O(log(n)), O(n^a) 是多项式时间复杂度

• O(a^n) 和 O(n!) 是非多项式时间复杂度

空间复杂度

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

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

NP 问题

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

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

NP - hard: 比 NP 问题更难的问题 (NP 问题的解法可以规约到 NP - hard 问题的解法)

NP 完全问题: 是一个 NP - hard 问题, 也是一个 NP 问题.

数组

数组具有如下的特性:

1. 存储在内存中一块连续的区间中

2. 数组中必须存放相同的数据类型

3. 数组适用下标访问数组中元素的时间复杂度为 O(1) (其对应的计算机底层的实现为通过数组的首地址 + 访问偏移量就能快速地访问到目标数据的内存地址, 从而取到数组对应下标的元素)

4. 在数组中添加和删除元素的平均时间复杂度为 O(n)

链表

链表具有如下的特性:

1. 可以使用零散的内存空间存储数据

2. 链表中每个元素必须包含一个指向下一个元素的指针

3. 在链表中查找一个数据, 需要遍历链表, 时间复杂度为 O(1)

4. 在链表中添加和删除元素的平均时间复杂度为 O(1)

哈希表

哈希表是一种非线性的数据结构, 具有如下的特征:

1. 访问表中元素的时间复杂度时间复杂度是 O(1)

2. 向表中添加或者删除元素的时间复杂度是 O(1)

3. 其底层实现是数组 + 链表

哈希表的实现方式是使用固定长度的数组来表示哈希表的"桶", 在哈希表数据的读写过程中通过元素的哈希值快速地定位到元素所在的"桶"。

在哈希表的写入过程中，可能出现多个元素会落在哈希表中的同一个"桶"中, 这个过程称为 "哈希冲突", 常见的解决哈希冲突的办法有:

1. 拉链法: 在哈希表的 "桶" 中行成一个链表

2. 开放寻址法: 如果写入元素的目标 "桶" 中存在元素了, 选择相邻位置作为元素的目标 "桶"

栈

数组和链表都是一种线性结构, 被称为线性表。

栈就是一种操作受限的线性表，有 "后进先出" 的特性。

线程运行时专有内存为什么被称为线程栈?

因为线程中的方法执行符合后进先出的特点, 一个线程执行方法, 首先把待执行方法相关的信息组装成栈帧, 放入线程栈, 当方法返回的时候, 栈帧出栈, 线程拿到返回值, 继续执行当前方法。

队列

队列也是一种操作受限的线性表，有 "先进先出" 的特性。

在实际的应用场景中，阻塞等待的线程被放入队列。

树

树是一种非线性的结构。如果一棵树的一个节点有 n 个儿子节点 (n > 1), 那么称这棵树为 n 叉树。

二叉搜索树 (Binary Search Tree)

一颗二叉搜索树具有如下的特性:

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

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

3. 左、右子树也分别为二叉搜索树

4. 中序遍历二叉搜索树可以得到一个递增的序列

二叉搜索树查找元素的平均时间复杂度是: O(logn)。极端状况下，二叉搜索树的查找效率会退化为链表，如图所示

平衡二叉搜索树

平衡二叉搜索树在二叉搜索树的特性上还满足:

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

2. 左右子树仍然是平衡二叉树

在平衡二叉搜索树中, 通过树的旋转来保持二叉树的平衡

1. 插入时, 最多只需要两次旋转就会重新恢复平衡

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

平衡二叉树的右旋

平衡二叉树的左旋

红黑树

一颗红黑树在二叉搜索树的基础上还具有如下的特性:

1. 每个节点只有两种颜色: 红色和黑色

2. 根节点是黑色的

3. 每个叶子节点 (NIL) 都是黑色的空节点

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

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

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

红黑树和平衡二叉搜索树的对比

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

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

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

跳表

跳表全称为跳跃列表，它允许快速查询，插入和删除一个有序连续元素的数据链表。

跳跃列表的平均查找和插入时间复杂度都是 O(logn)。

快速查询是通过维护一个多层次的链表，且每一层链表中的元素是前一层链表元素的子集。一开始时，算法在最稀疏的层次进行搜索，直至需要查找的元素在该层两个相邻的元素中间。这时，算法将跳转到下一个层次，重复刚才的搜索，直到找到需要查找的元素为止。

常用算法

穷举算法

将算法中所有可能的结果穷举出来, 筛选符合预期的结果, 时间复杂度高。

递归算法

递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。

分治算法

分治算法的基本思想是将一个规模为 N 的问题分解为 K 个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。

贪心算法

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

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。也就是说，不从整体最优上加以考虑，做出的只是在某种意义上的局部最优解。

动态规划算法

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

网络通讯协议

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

DNS

构成互联网 Internet 的最基本的网络协议就是互联网协议 Internet Protocol，简称 IP 协议。IP 协议里面最重要的部分是 IP 地址，各种计算机设备之间能够互相通信，首先要能够找到彼此，IP 地址就是互联网的地址标识。事实上这个 IP 地址是通过 DNS 域名解析服务器得到的。

CDN

CDN 是内容分发网络 Content Delivery Network 的缩写。我们能够用手机或者电脑上网，是因为运营服务商为我们提供了互联网接入服务，将我们的手机和电脑连接到互联网上。App 请求的数据最先到达的是运营服务商的机房，然后运营商通过自己建设的骨干网络和交换节点，将我们请求数据的目的地址发往互联网的任何地方。

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

传输层协议 TCP 和网络层协议 IP 共同构成 TCP/IP 协议栈，成为互联网应用开发最主要的通信协议。

OSI 开放系统互联模型将网络协议定义了 7 层，TCP/IP 协议栈将 OSI 顶部三层协议应用层、表示层、会话层合并为一个应用层，HTTP 协议就是 TCP/IP 协议栈中的应用层协议。

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

数据链路层就是将数据进行封装后交给物理层进行传输，主要就是将数据封装成数据帧，以帧为单位通过物理层进行通信，有了帧，就可以在帧上进行数据校验，进行流量控制。数据链路层会定义帧的大小，这个大小也被称为最大传输单元。像 HTTP 要在传输的数据上添加一个 HTTP 头一样，数据链路层也会将封装好的帧添加一个帧头，帧头里记录的一个重要信息就是发送者和接受者的 mac 地址。mac 地址是网卡的设备标识符，是唯一的，数据帧通过这个信息确保数据送达到正确的目标机器。

网络层 IP 协议使得互联网应用根据 IP 地址就能访问到目标地址。网络层的数据需要交给链路层进行处理，而链路层帧的大小定义了最大传输单元，网络层的 IP 数据包必须要小于最大传输单元才能进行网络传输，这个数据包也有一个 IP 头，主要包括的就是发送者和接受者的 IP 地址。IP 协议不是一个可靠的通信协议，并不会确保数据一定送达。要保证通信的稳定可靠，需要传输层协议 TCP。

TCP 协议在传输正式数据前，会先建立连接，这就是著名的 TCP 三次握手。

TCP 三次握手

App 和服务器之间发送三次报文才会建立一个 TCP 连接，报文中的 SYN 表示请求建立连接，ACK 表示确认。

1. App 先发送 SYN=1，Seq=X 的报文，表示请求建立连接，X 是一个随机数

2. 服务器收到这个报文后，应答 SYN=1，ACK=X+1，Seq=Y 的报文，表示同意建立连接

3. App 收到这个报文后，检查 ACK 的值为自己发送的 Seq 值 +1，确认建立连接，并发送 ACK=Y+1 的报文给服务器；

4. 服务器收到这个报文后检查 ACK 值为自己发送的 Seq 值 +1，确认建立连接。

TCP 四次挥手

1. 客户端向服务器端发送断开 TCP 连接请求的 [FIN，SEQ] 报文，在报文中随机生成一个序列号 SEQ = x，表示要断开 TCP 连接

2. 当服务器端收到客户端发来的断开 TCP 连接的请求后，回复发送 ACK 报文，表示已经收到断开请求。回复时，随机生成一个序列号 SEQ = y。由于回复的是客户端发来的请求，所以在客户端请求序列号 SEQ = x 的基础上加 1，得到 ACK= x + 1。

3. 服务器端在回复完客户端的 TCP 断开请求后，不会马上进行 TCP 连接的断开。服务器端会先确认断开前，所有传输到客户端的数据是否已经传输完毕。确认数据传输完毕后才进行断开，向客户端发送 [FIN，ACK] 报文，设置字段值为 1。再次随机生成一个序列号 SEQ=z。由于还是对客户端发来的 TCP 断开请求序列号 SEQ=x 进行回复，因此 ACK 依然为 x + 1。

4. 客户端收到服务器发来的 TCP 断开连接数据包后将进行回复，表示收到断开 TCP 连接数据包。向服务器发送 ACK 报文，生成一个序列号 SEQ = x + 1。由于回复的是服务器，所以 ACK 字段的值在服务器发来断开 TCP 连接请求序列号 SEQ = z 的基础上加 1，得到 ACK=z + 1

应用层 HTTP 协议

不管发送到 CDN 还是数据中心，App 请求都会以 HTTP 协议发送。HTTP 是一个应用层协议，当我们进行网络通信编程的时候，通常需要关注两方面的内容，一方面是应用层的通信协议，主要是我们通信的数据如何编码，既能使网络传输过去的数据携带必要的信息，又使通信的两方都能正确识别这些数据，即通信双方应用程序需要约定一个数据编码协议。另一方面就是网络底层通信协议，即如何为网络上需要通信的两个节点建立连接完成数据传输，目前互联网应用中最主要的就是 TCP 协议。

在 TCP 传输层协议层面，就是保证建立通信两方的稳定通信连接，将一方的数据以 bit 流的方式源源不断地发送到另一方，至于这些数据代表什么意思，哪里是两次请求的分界点，TCP 协议统统不管，需要应用层面自己解决。如果我们基于 TCP 协议自己开发应用程序，就必须解决这些问题。而互联网应用需要在全球范围为用户提供服务，将全球的应用和全球的用户联系在一起，需要一个统一的应用层协议，这个协议就是 HTTP 协议。

HTTP 请求的 7 种方法

1. GET 方法

GET 方法用于使用给定的 URI 从给定服务器中检索信息，即从指定资源中请求数据。使用 GET 方法的请求应该只是检索数据，并且不应对数据产生其他影响。

2. POST 方法

POST 方法用于将数据发送到服务器以创建或更新资源，它要求服务器确认请求中包含的内容作为由 URI 区分的 Web 资源的另一个下属。

POST 请求永远不会被缓存，且对数据长度没有限制；我们无法从浏览器历史记录中查找到 POST 请求。

3. HEAD 方法

HEAD 方法与 GET 方法相同，但没有响应体，仅传输状态行和标题部分。这对于恢复相应头部编写的元数据非常有用，而无需传输整个内容。

4. PUT 方法

PUT 方法用于将数据发送到服务器以创建或更新资源，它可以用上传的内容替换目标资源中的所有当前内容。它会将包含的元素放在所提供的 URI 下，如果 URI 指示的是当前资源，则会被改变。如果 URI 未指示当前资源，则服务器可以使用该 URI 创建资源。

5. DELETE 方法

DELETE 方法用来删除指定的资源，它会删除 URI 给出的目标资源的所有当前内容。

6. OPTIONS 方法

OPTIONS 方法用来描述了目标资源的通信选项，会返回服务器支持预定义 URL 的 HTTP 策略。

7. TRACE 方法

TRACE 方法用于沿着目标资源的路径执行消息环回测试；它回应收到的请求，以便客户可以看到中间服务器进行了哪些（假设任何）进度或增量。

HTTP 响应的 5 种状态

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

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

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

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

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

HTTP 协议版本

HTTP/1.0: 客户端请求到资源后会关闭连接, 并发量大的时候会导致频繁创建、关闭 TCP 连接, 而 TCP 三次握手、四次挥手会消耗一定的时间

HTTP/1.1: 默认启用长连接模式, 即客户端可以是用同一个 TCP 连接顺序发送多个请求, 新版本也引入了管道机制, 客户端可以不用等上一个请求的响应结果就可以发送下一个请求, 但是服务器端也是按照客户端请求的顺训进行响应的, 可以理解为半双工模式

HTTP/2: 复用 TCP 连接的方式不同, 依然遵循请求 - 响应模式, 但客户端发送多个请求和服务端给出多个响应的顺序不受限制, 这样既避免了"队头阻塞", 又能更快获取响应。

非阻塞网络 I/O

网络 I/O 的本质是 socket 的读取，socket 在 linux 系统被抽象为流，I/O 可以理解为对流的操作。这个操作又分为两个阶段：

1. 等待流数据准备

2. 从内核向进程复制数据

对于 socket 流而已，

• 第一步通常涉及等待网络上的数据分组到达，然后被复制到内核的某个缓冲区

• 第二步把数据从内核缓冲区复制到应用进程缓冲区

阻塞 I/O

阻塞就是进程 "被" 休息, CPU 处理其它进程去了。在网络 I/O 的时候，进程发起 recvform 系统调用，然后进程就被阻塞了，什么也不干，直到数据准备好，并且将数据从内核复制到用户进程，最后进程再处理数据，在等待数据到处理数据的两个阶段，整个进程都被阻塞, 不能处理别的网络 I/O。

阻塞 IO 的特点就是在 IO 执行的两个阶段都被 block 了

非阻塞 I/O

在网络 I/O 时候，非阻塞 I/O 也会进行 recvform 系统调用，检查数据是否准备好，与阻塞 I/O 不一样，"非阻塞将大的整片时间的阻塞分成 N 多的小的阻塞, 所以进程不断地有机会被 CPU 调度。

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

非阻塞 IO 的特点是用户进程需要不断的主动询问 kernel 数据是否准备好。

多路复用 I/O

多路复用有两个特别的系统调用 select, poll。select 调用是内核级别的，select 轮询相对非阻塞的轮询的区别在于---前者可以等待多个 socket，当其中任何一个 socket 的数据准好了，就能返回进行可读，然后进程再进行 recvform 系统调用，将数据由内核拷贝到用户进程，当然这个过程是阻塞的。多路复用有两种阻塞，select 或 poll 调用之后，会阻塞进程，与第一种阻塞不同在于，此时的 select 不是等到 socket 数据全部到达再处理, 而是有了一部分数据就会调用用户进程来处理。

多路复用的特点是通过一种机制一个进程能同时等待 IO 文件描述符，内核监视这些文件描述符（套接字描述符），其中的任意一个进入读就绪状态，select， poll，epoll 函数就可以返回。对于监视的方式，又可以分为 select， poll， epoll 三种方式。

数据库原理与性能优化

在关系型数据库中,一个 SQL 提交到数据库，经过连接器将 SQL 语句交给语法分析器，生成一个抽象语法树 AST；AST 经过语义分析与优化器，进行语义优化，使计算过程和需要获取的中间数据尽可能少，然后得到数据库执行计划；执行计划提交给具体的执行引擎进行计算，将结果通过连接器再返回给应用程序。

应用程序提交 SQL 到数据库执行，首先需要建立与数据库的连接，数据库连接器会为每个连接请求分配一块专用的内存空间用于会话上下文管理。建立连接对数据库而言相对比较重，需要花费一定的时间，因此应用程序启动的时候，通常会初始化建立一些数据库连接放在连接池里，这样当处理外部请求执行 SQL 操作的时候，就不需要花费时间建立连接了。这些连接一旦建立，不管是否有 SQL 执行，都会消耗一定的数据库内存资源，所以对于一个大规模互联网应用集群来说，如果启动了很多应用程序实例，这些程序每个都会和数据库建立若干个连接，即使不提交 SQL 到数据库执行，也就会对数据库产生很大的压力。所以应用程序需要对数据库连接进行管理，一方面通过连接池对连接进行管理，空闲连接会被及时释放；另一方面微服务架构可以大大减少数据库连接，比如对于用户数据库来说，所有应用都需要连接到用户数据库，而如果划分一个用户微服务并独立部署一个比较小的集群，那么就只有这几个用户微服务实例需要连接用户数据库，需要建立的连接数量大大减少。

连接器收到 SQL 以后，会将 SQL 交给语法分析器进行处理，语法分析器工作比较简单机械，就是根据 SQL 语法规则生成对应的抽象语法树。

SQL 语义分析与优化器就是要将各种复杂嵌套的 SQL 进行语义等价转化，得到有限几种关系代数计算结构，并利用索引等信息进一步进行优化。

使用 PrepareStatement 执行 SQL 的好处

这样做主要有两个好处。

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

另一个好处则更为重要，PrepareStatement 可以防止 SQL 注入攻击。

数据库文件存储原理

数据库索引使用 B+ 树，我们先看下 B+ 树这种数据结构。B+ 树是一种 N 叉排序树，树的每个节点包含 N 个数据，这些数据按顺序排好，两个数据之间是一个指向子节点的指针，而子节点的数据则在这两个数据大小之间。

B+ 树的节点存储在磁盘上，每个节点存储 1000 多个数据，这样树的深度最多只要 4 层，就可存储数亿的数据。如果将树的根节点缓存在内存中，则最多只需要三次磁盘访问就可以检索到需要的索引数据。