学习笔记: 架构师训练营 - 第八周

文件与硬盘 I/O

1、机械硬盘

原理：机械硬盘中所有的盘片都装在一个旋转轴上，每张盘片之间是平行的，在每个盘片的存储面上有一个磁头，磁头与盘片之间的距离只有 0.1μm～0.5μm，较高的水平已经达到 0.005μm～0.01μm，所有的磁头联在一个磁头控制器上，由磁头控制器负责各个磁头的运动。

机械硬盘在读数据时，磁盘的旋转速度还是非常快的，每分钟达到 5400 转甚至 7200 转，但是磁头移动的速度比较慢，毫秒级，因此读数据比较慢的大多数原因是由于存储的数据是分散的，不在连续的磁道中，在读取数据的过程中，不断的移动磁头，而磁头在移动到其他分区时所消耗的时间在读取数据的时间中占较大的比例。

2、固态硬盘

固态驱动器（Solid State Disk 或 Solid State Drive，简称 SSD），俗称固态硬盘。它是用固态电子存储芯片阵列制成的硬盘。SD 由控制单元和存储单元（FLASH 芯片、DRAM 芯片）组成。

闪存完全擦写一次叫做 1 次 P/E，因此闪存的寿命就以 P/E 作单位。34nm 的闪存芯片寿命约是 5000 次 P/E，而 25nm 的寿命约是 3000 次 P/E。一款 120G 的固态硬盘，要写入 120G 的文件才算做一次 P/E。

3、B 树、B+树、B*树

参考资料：

文件存储要选用 B+树这样的数据结构https://www.cnblogs.com/cangqiongbingchen/p/4559192.html

老师 PPT 中的树应该是 B 树而不是 B+树。

B 树：平衡多路查找树，B 树中的每个结点根据实际情况可以包含大量的关键字信息和分支(当然是不能超过磁盘块的大小，根据磁盘驱动(disk drives)的不同，一般块的大小在 1k~4k 左右)；这样树的深度降低了，这就意味着查找一个元素只要很少结点从外存磁盘中读入内存，很快访问到要查找的数据；

B+树：

一棵 m 阶的 B+树和 m 阶的 B 树的差异在于：

1.有 n 棵子树的结点中含有 n 个关键字； (而 B 树是 n 棵子树有 n-1 个关键字)

2.所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (而 B 树的叶子节点并没有包括全部需要查找的信息)

3.所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而 B 树的非终节点也包含需要查找的有效信息)

相较于 B 树，B+树的优势：

1)B+树的磁盘读写代价更低

B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对 B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说 IO 读写次数也就降低了。

2) B+树的查询效率更加稳定

由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

B*树：在 B+ 树非根和非叶子结点再增加指向兄弟的指针；B 树定义了非叶子结点关键字个数至少为(2/3)M，即块的最低使用率为 2/3（代替 B+树的 1/2）

B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中 1/2 的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。

B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的 关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制 1/3 的数据到新结点，最后在父结点增加新结点的指针。

4、LSM 树

即日志结构合并树(Log-Structured Merge-Tree)。其实它并不属于一个具体的数据结构，它更多是一种数据结构的设计思想。大多 NoSQL 数据库核心思想都是基于 LSM 来做的，只是具体的实现不同

5、文件控制块

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

6、Linux Inode 文件控制块

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

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

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

7、RAID 独立硬盘冗余阵列

把多个相对便宜的硬盘组合起来，成为一个硬盘阵列组，使性能达到甚至超过一个价格昂贵、容量巨大的硬盘

RAID 0

有多个硬盘驱动器，数据分成数据块保存在不同硬盘上

缺点：只有数据存储没有数据差错控制

优点：数据读取速度是同级别中最快的

RAID 1

有两块硬盘，两块硬盘数据相同（一个盘错了另一个还有数据），通过镜像的方式提高系统的容错能力

缺点：数据读取速度和单独一个盘的读取速度相同（因为两个盘数据相同），与一个盘相比，大大影响服务器效率

优点：安全性是最好的（甚至可以在不断电的情况下对故障硬盘进行更换，更换完毕只要从镜像盘上恢复数据即可）

RAID 5

与 RAID 类似，不过增加了校验功能，数据段和校验信息轮流写到组内的每个硬盘里，硬盘如果损坏可以通过剩下的硬盘的校验信息恢复

缺点：RAID 5 的数据读取速度与 RAID 0 相似，只是因为多了一个奇偶校验信息，写入数据速度相对独立写入一块硬盘硬盘的速度略慢

优点： 每个盘都有奇偶校验信息，因此磁盘空间利用率要比 RAID 1 高，适用于读操作比较频繁而写操作较少

RAID6：

带有两种分布存储的奇偶校验码的独立磁盘结构 （最少 4 个硬盘）。它是对 RAID5 的扩展，主要是用于要求数据绝对不能出错的场合。当然了，由于引入了第二种奇偶校验值，所以需要 N+2 个磁盘，同时对控制器的设计变得十分复杂，写入速度也不好，用于计算奇偶校验值和验证数据正确性所花费的时间比较多，造成了不必须的负载。

RAID10：

高可靠性与高效磁盘结构（最少 2 个硬盘）。这种结构无非是一个带区结构加一个镜象结构，因为两种结构各有优缺点，因此可以相互补充，达到既高效又高速还可以的目的。大家可以结合两种结构的优点和缺点来理解这种新结构。这种新结构的价格高，可扩充性不好。主要用于容易不大，但要求速度和差错控制的数据库中。

8、分布式文件系统 HDFS

HDFS 基本结构分 NameNode、SecondaryNameNode、DataNode 这几个。

NameNode：是 Master 节点，有点类似 Linux 里的根目录。管理数据块映射；处理客户端的读写请求；配置副本策略；管理 HDFS 的名称空间；起一个统领的作用，用户通过 namenode 来实现对其他数据的访问和操作，类似于 root 根目录，目录与数据块之间的关系（靠 fsimage 和 edits 来实现），数据块和节点之间的关系

SecondaryNameNode：保存着 NameNode 的部分信息（不是全部信息 NameNode 宕掉之后恢复数据用），是 NameNode 的冷备份；合并 fsimage 和 edits 然后再发给 namenode。（防止 edits 过大的一种解决方案）

DataNode：负责存储 client 发来的数据块 block；执行数据块的读写操作。是 NameNode 的小弟。

热备份：b 是 a 的热备份，如果 a 坏掉。那么 b 马上运行代替 a 的工作。

冷备份：b 是 a 的冷备份，如果 a 坏掉。那么 b 不能马上代替 a 工作。但是 b 上存储 a 的一些信息，减少 a 坏掉之后的损失。DataNode 在 HDFS 中真正存储数据。

首先解释块（block）的概念：

1. DataNode 在存储数据的时候是按照 block 为单位读写数据的。block 是 hdfs 读写数据的基本单位。

2. 假设文件大小是 100GB，从字节位置 0 开始，每 128MB 字节划分为一个 block，依此类推，可以划分出很多的 block。每个 block 就是 128MB 大小。

3. block 本质上是一个 逻辑概念，意味着 block 里面不会真正的存储数据，只是划分文件的。

4. block 里也会存副本，副本优点是安全，缺点是占空间

fsimage:元数据镜像文件（文件系统的目录树。）

edits：元数据的操作日志（针对文件系统做的修改操作记录）

namenode：内存中存储的是=fsimage+edits。

参考文献：

https://www.cnblogs.com/wxplmm/p/7239342.html

数据结构与算法

1、时间复杂度与空间复杂度

时间复杂度

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

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

• 多项式时间复杂度

• 非多项式时间复杂度

空间复杂度

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

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

2、NP 问题

P 问题：

一个问题可以在多项式（O(n^k)）的时间复杂度内解决。

NP 问题：

一个问题的解可以在多项式的时间内被验证。

NP-hard 问题：

任意 np 问题都可以在多项式时间内归约为该问题，但该问题本身不一定是 NP 问题。归约的意思是为了解决问题 A，先将问题 A 归约为另一个问题 B，解决问题 B 同时也间接解决了问题 A。

NPC 问题：

既是 NP 问题，也是 NP-hard 问题。

3、数组

创建数组必须要内存中一块连续的空间。数组中必须存放相同的数据类型。随机快速读写是数组的一个重要特性，根据数 组的下标访问数据，时间复杂度为 O(1)。

4、链表

链表可以使用零散的内存空间存储数据。 所以链表中的每个数据元素都必须包含一个指向下一个数据元素的内存地址指针。 要想在链表中查找一个数据，只能遍历链表，所以链表的查找复杂度总是 O(N)。

5、Hash 表

hash 函数就是根据 key 计算出应该存储地址的位置，而哈希表是基于哈希函数建立的一种查找表

6、Hash 冲突

使用 hash 函数计算不同的 key 出现一样的存储地址，即 H（key1）=H（key2）

Hash 冲突解决方案:

• 开放定制法

• 链地址法

• 公共溢出区法:建立一个特殊存储空间，专门存放冲突的数据。此种方法适用于数据和冲突较少的情况。

• 再散列法:准备若干个 hash 函数，如果使用第一个 hash 函数发生了冲突，就使用第二个 hash 函数，第二个也冲突，使用第三个……重点了解一下开放定制法和链地址法

7、栈

数组和链表都被称为线性表。栈就是在线性表的基础上加了这样的操作限制条件：后面添加的数据，在删除的时候必须先删除，即通常所说的“后进先出”。

8、队列

队列也是一种操作受限的线性表，栈是后进先出，而队列是先进先出。典型应用场景：生产者消费者；阻塞等待的线程被放入队列。

9、树-二叉排序树

左子树上所有结点的值均小于或等于它的根结点的值。 右子树上所有结点的值均大于或等于它的根结点的值。 左、右子树也分别为二叉排序树。

10、平衡二叉（排序）树

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

旋转二叉树恢复平衡

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

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

11、红黑（排序）树

特性：

（1）每个节点或者是黑色，或者是红色。（2）根节点是黑色。（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL 或 NULL)的叶子节点！]（4）如果一个节点是红色的，则它的子节点必须是黑色的。（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

注意：(01) 特性(3)中的叶子节点，是只为空(NIL 或 null)的节点。(02) 特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。

参考资料：

红黑树(一)之 原理和算法详细介绍

红黑树 VS 平衡二叉树

红黑树最多只需 3 次旋转就会重新达成红黑平衡，时间复杂度 O(1)。 在大量增删的情况下，红黑树的效率更高。 红黑树的平衡性不如平衡二叉树，查找效率要差一些。

12、跳表

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

参考资料：

数据结构与算法—跳表

13、常用算法-穷举算法

又称穷举搜索法，是一种在问题域的解空间中对所有可能的解穷举搜索，并根据条件选择最优解的方法的总称。数学上也把穷举法称为枚举法，就是在一个由有限个元素构成的集合中，把所有元素一一枚举研究的方法。

使用穷举法解决问题，基本上就是以下两个步骤：　　

• 确定问题的解（或状态）的定义、解空间的范围以及正确解的判定条件；　　

• 根据解空间的特点来选择搜索策略，逐个检验解空间中的候选解是否正确；

解空间的定义解空间就是全部可能的候选解的一个约束范围，确定问题的解就在这个约束范围内，将搜索策略应用到这个约束范围就可以找到问题的解。要确定解空间，首先要定义问题的解并建立解的数据模型。如果解的数据模型选择错误或不合适，则会导致解空间结构繁杂、范围难以界定，甚至无法设计穷举算法。穷举解空间的策略穷举解空间的策略就是搜索算法的设计策略，根据问题的类型，解空间的结构可能是线性表、集合、树或者图，对于不同类型的解空间，需要设计与之相适应的穷举搜索算法。简单的问题可以用通用的搜索算法，比如线性搜索算法用于对线性解空间的搜索，广度优先和深度优先的递归搜索算法适用于树型解空间或更复杂的图型解空间。

盲目搜索和启发式搜索对于线性问题的盲目搜索，就是把线性表中的所有算法按照一定的顺序遍历一遍，对于复杂问题的盲目搜索，常用广度优先搜索和深度优先搜索这两种盲目搜索算法。如果搜索能够智能化一点，利用搜索过程中出现的额外信息直接跳过一些状态，避免盲目的、机械式的搜索，就可以加快搜索算法的收敛，这就是启发性搜索。启发性搜索需要一些额外信息和操作来“启发”搜索算法，根据这些信息的不同，启发的方式也不同。

剪枝策略对解空间穷举搜索时，如果有一些状态节点可以根据问题提供的信息明确地被判定为不可能演化出最优解，也就是说，从此节点开始遍历得到的子树，可能存在正确的解，但是肯定不是最优解，就可以跳过此状态节点的遍历，这将极大地提高算法的执行效率，这就是剪枝策略，应用剪枝策略的难点在于如何找到一个评价方法（估值函数）对状态节点进行评估。特定的评价方法都附着在特定的搜索算法中，比如博弈树算法中常用的极大极小值算法和“α-β”算法，都伴随着相应的剪枝算法。

剪枝和启发剪枝不是启发性搜索。剪枝的原理是在结果已经搜索出来或部分搜索出来（比如树的根节点已经搜索出来了，但是叶子节点还没有搜索出来）的情况下，根据最优解的判断条件，确定这个方向上不可能存在最优解，从而放弃对这个方向的继续搜索。而启发性搜索通常是根据启发函数给出的评估值，在结果出来之前就朝着最可能出现最优解的方向搜索。它们的差异点在于是根据结果进行判断还是根据启发函数的评估值进行判断。

搜索算法的评估和收敛收敛原则是只要能找到一个比较好的解就返回（不求最好），根据解的评估判断是否需要继续下一次搜索。大型棋类游戏通常面临这种问题，比如国际象棋和围棋的求解算法，想要搜索整个解空间得到最优解目前是不可能的，所以此类搜索算法通常都通过一个搜索深度参数来控制搜索算法的收敛，当搜索到指定的深度时（相当于走了若干步棋）就返回当前已经找到的最好的结果，这种退而求其次的策略也是不得已而为之

参考资料：

算法设计常用思想之穷举法

14、常用算法-递归算法

在数学与计算机科学中，递归(Recursion)是指在函数的定义中使用函数自身的方法

递归的三要素：

• 明确递归终止条件

• 给出递归终止时的处理办法

• 提取重复的逻辑，缩小问题规模

15、常用算法-贪心算法

在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅仅是在某种意义上的局部最优解

基本思路

• 建立数学模型来描述问题

• 把求解的问题分成若干个子问题

• 对每个子问题求解，得到子问题的局部最优解

• 把子问题的解局部最优解合成原来问题的一个解

存在的问题

• 不能保证求得的最后解是最佳的

• 不能用来求最大值或最小值的问题

• 只能求满足某些约束条件的可行解的范围

16、常用算法-动态规划

问题的最优解如果可以由子问题的最优解推导得到，则可以先求解子问题的最优解，在构造原问题的最优解；若子问题有较多的重复出现，则可以自底向上从最终子问题向原问题逐步求解

17、遗传算法

遗传算法（Genetic Algorithm, GA）是模拟达尔文生物进化论的自然选择和遗传学机理 的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数 空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、 初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗 传算法的核心内容

网络通信协议

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

1、客户端拿到域名后，请求 DNS 服务器，域名解析成对应的 IP 地址

2、解析出的 IP 地址如果是 CDN 地址，则向 CDN 请求时查看是否有缓存，如果没有会将请求转发至负载均衡服务器

3、负载均衡服务器在收到请求后，转发至相应的反向代理服务器，

4、反向代理服务器再将请求转发到服务内部负载均衡服务器，

5、收到请求的负载均衡服务器，将再请求网关服务器，在网关服务器内部做权限校验等操作，

6、通过校验后的请求，在调用相应的微服务服务器，

7、微服务服务在经过业务处理，归集各个子服务的数据，并原路返回

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

2.1、网络数据包格式

2.2、物理层

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

2.3、链路层

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

链路层会定义帧的大小，这个大小也被称为最大传输单元。像 HTTP 要在传输的数据上 添加一个 HTTP 头一样，数据链路层也会将封装好的帧添加一个帧头，帧头里记录的一 个重要信息就是发送者和接受者的 MAC 地址。MAC 地址是网卡的设备标识符，是唯一 的，数据帧通过这个信息确保数据送达到正确的目标机器。

2.4、网络层

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

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

2.5、传输层（TCP 协议）

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

TCP 协议是一种面向连接的、可靠的、基于字节流的传输层协议。TCP 作为一个比较基础的通讯协 议，有很多重要的机制保证了 TCP 协议的可靠性和强壮性：

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

• 使用校验和检测报文段的错误

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

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

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

TCP 建立连接的 3 次握手过程:

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

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

3. App 收到这个报文后，检查 ACK 的值为自己发送的 Seq 值 +1，确认建立连接，并发送 ACK=Y+1 的报文给服务器；服务器收到这个报文后检查 ACK 值为自己发送的 Seq 值 +1，确认建立连接。至此，App 和服务器建立起 TCP 连接，就可以进行数据传输了。

TCP 关闭连接 4 次挥手:

• 客户端向服务器端发送一个 FIN，请求关闭数据传输。

• 当服务器接收到客户端的 FIN 时，向客户端发送一个 ACK，其中 ACK 的值等于 FIN + SEQ。

• 然后服务器向客户端发送一个 FIN，告诉客户端应用程序关闭。

• 当客户端收到服务器端的 FIN 是，回复一个 ACK 给服务器端。其中 ACK 的值等于 FIN + SEQ。

2.6、应用层 HTTP 协议

超文本传输协议（英文：HyperText Transfer Protocol，缩写：HTTP）是一种用于分布式、协作式和超媒体信息系统的应用层协议

请求方法

Get：只读请求，请求处理过程不应该产生副作用，即 web 应用不应该因为 get 请求而发生任何状态改变。

Head：和 get 方法一样，但是只返回响应头。

Post：提交请求。

Put：上传请求。

Delete：删除 URL 标识的资源。

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

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

协议状态五种状态

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

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

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

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

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

参考资料：

HTTP协议超级详解

3、非阻塞网络 I/O

操作 I/O 时涉及的对象和步骤（以 read 为例）：　　

　　这里会涉及到两个系统对象，一个是调用这个 I/O 的应用进程（或线程），另一个就是系统内核。当一个 read 操作发生时，它会经历两个阶段：1）等待数据就绪 （可读）；2）将数据从内核拷贝到应用进程中 。这两个阶段很重要，因为各种 I/O 模型的区别就是在这两个阶段上各有不同的情况。

同步 I/O 操作（synchronous I/O operation）：导致请求进程阻塞，直到 I/O 操作完成。包含阻塞式 I/O 模型、非阻塞式 I/O 模型、I/O 复用模型和信号驱动式 I/O。

异步 I/O 操作（asynchronous I/O operation）：不导致请求进程阻塞。工作机制是：告知内核启动某个操作，并让内核在整个操作（包括将数据从内核复制到我们自己的缓冲区）完成后通知我们

信号驱动模型的主要区别在于：信号驱动式 I/O 是由内核通知我们何时可以启动一个 I/O 操作，而异步 I/O 模型是由内核通知我们 I/O 操作何时完成

参考资料：

网络I/O中的同步、异步、阻塞和非阻塞概念