极客时间架构师训练营 1 期 - 第 8 周总结

文件与硬盘I/O



• 机械硬盘

机械硬盘是常用的硬盘，通过马达驱动磁头臂，带动磁头到指定磁盘位置访问数据，由于每次访问数据都要移动磁头臂，因此机械硬盘在数据连续访问（要访问的数据存储在连续的磁盘空间上）和随机访问（要访问的数据存储在不连续的磁盘空间）时，由于移动磁头臂的次数相差巨大，性能表现差别也非常大。

• 固态硬盘

固态硬盘又称做SSD或者Flash硬盘，其没有机械装置，数据存储在可持久记忆的硅晶体上，因此可以像内存一样快速随机访问。而且SSD具有更小的功耗与更少的磁盘震动与噪声。



网站应用中，大部分应用访问数据都是随机的，这种情况SSD具有更好的性能表现。但目前SSD硬盘还不太成熟，可靠性。性价比有待提升，因此SSD的使用还在摸索阶段。



----



B+树与LSM树

###### B+ 树

由于传统的机械硬盘具有快速顺序读写、慢速随机读写的访问特性，对硬盘存储结构和算法的选择影响甚大。

为了改善数据访问特性，文件系统或者数据库系统通常会对数据排序后存储，加快数据检索速度，这就需要保证数据不断更新、插入、删除后依然有序，

传统关系数据库的做法是使用B+树。

B+树是一种专门针对磁盘存储而优化的N叉排序树，以树节点为单位存储在磁盘中，从根开始查找所需数据所在的节点编号和磁盘位置，将其加载到内存中然后继续查找，直到找到所需的数据。

目前数据库多采用两级索引的B+树，树的层数最多三层。因此可能需要5次磁盘访问才能更新一条记录。

由于每次磁盘访问都是随机的，而传统机械硬盘随机访问性能差，都需要多次访问磁盘影响数据访问性能。



###### LSM树



传统关系型数据库使用btree或一些变体作为存储结构，能高效进行查找。但保存在磁盘中时它也有一个明显的缺陷，那就是逻辑上相离很近但物理却可能相隔很远，这就可能造成大量的磁盘随机读写。随机读写比顺序读写慢很多，为了提升IO性能，我们需要一种能将随机操作变为顺序操作的机制，于是便有了LSM树。LSM树能让我们进行顺序写磁盘，从而大幅提升写操作，作为代价的是牺牲了一些读性能。



目前需要NOSQL产品采用LSM树作为主要数据结构



LSM树并不像B+树、红黑树一样是一颗严格的树状数据结构，它其实是一种存储结构，目前HBase,LevelDB,RocksDB这些NoSQL存储都是采用的LSM树。LSM树的核心特点是利用顺序写来提高写性能，但因为分层(此处分层是指的分为内存和文件两部分)的设计会稍微降低读性能，但是通过牺牲小部分读性能换来高性能写，使得LSM树成为非常流行的存储结构。



写操作： 内存排序树--内存合并树-磁盘合并树

读操作：内存排序树查找--磁盘排序树顺序查找



当数据访问以写操作为主，而读操作则集中在最近写入的数据上时，使用LSM树可以极大程度减少磁盘的访问次数，加快访问次数。





RAID vs. HDFS



###### RAID技术



• RAID0

根据磁盘数量将数据分成N份，并发写入或者读取，具有极高的数据读写速度。但是不做数据备份，可靠性低，数据容易损坏；磁盘利用率高。

• RAID1

每份数据写入两块磁盘，访问速度慢，可靠性极高，磁盘利用率低50%.

• RAID10

结合RAID与RAID1两种方案，访问速度一般，可靠性高， 磁盘利用率50%.

• RAID3

数据分成N-1份，并发写入N-1块，并在第N块磁盘记录校验数据，任何一块磁盘损坏（包括校验数据磁盘），都可以利用其他N-1块磁盘的数据修复。访问速度较快，可靠性一般，第N块容易损坏。磁盘利用率（N-1)/N.

• RAID5

较多使用

与RAID3相似，但是校验数据不是写入第N块磁盘，而是螺旋式写入所有磁盘中。分摊校验数据的修改对于第N盘的访问压力。访问速度较快，可靠性较高。磁盘利用率(N-1)/N.

• RAID6

解决RAID5出现两块磁盘损坏的情况，提高可靠性。

与RAID5相似，但是数据只吸入N-2块磁盘，并螺旋式地在两块磁盘中写入校验信息（使用不同算法生成）。访问速度较快，可靠性比RAID5高，磁盘利用率（N-2)/N.



###### HDFS



RAID技术对于性能提醒有限，取决于并发读写磁盘的块数，毕竟是单台服务器。在大型网站更多使用HDFS分布式文件系统.其从增加服务器的角度实现。

HDFS以块（Block)为单位管理文件内容，一个文件被分割成若干个Block，当应用程序写文件时，每写完一个Block，HDFS就将其自动复制到两外两台机器上，保证每个Block有三个副本，即使有两台服务器宕机，数据依然可以访问，相当于实现了RAID1的数据复制功能。数据可靠性高。

HDFS配合MapReduce等并发计算框架进行大数据处理时，可以在整个集群并发读写所有的磁盘，无需RAID支持。访问速度高。



由于数据有三个副本，其磁盘利用率低。



----



数据结构与算法

###### 时间复杂度与空间复杂度



• 时间复杂度

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

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

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

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

• 空间复杂度

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

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



• NP问题

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

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

NP?=P

NP-hard问题：比NP问题更难的问题（NP问题的解法可以规约到NP-hard问题的解法）

NP完全问题：是一个NP-hard问题，也是一个NP问题。



• 数组

创建数组必须要内存中一块连续的空间。

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

随机快速读写是数组的一个重要特性，根据数 组的下标访问数据，时间复杂度为O(1)。

• 链表

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

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

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

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

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



• Hash 表

如何既快速访问数据，又快速增删数据？Hash表实际上也是数组



• Hash冲突

相同Hash值指向一个链表

避免Hash恶意攻击



• 栈

数组和链表都被称为线性表。

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

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

线程调用栈（控制程序运行顺序）



• 队列

队列也是一种操作受限的线性表，栈是后进先出，而队列是先进先出。

典型应用场景：

生产者消费者；阻塞等待的线程被放入队列。

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

用队列搜索最短路径



• 树

1. 二叉排序树

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

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

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

1. 不平衡的二叉排序树

1. 平衡二叉（排序）树

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

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



1. 旋转二叉树恢复平衡

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

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

1. 红黑（排序）树

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

根节点是黑色的

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

从根节点到叶子节点，不会出现两个连续的红色节点。

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

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



1. 红黑树VS平衡二叉树

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

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

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

• 跳表



###### 常用算法



• 穷举算法

• 递归算法

递归算法（快速排序算法）

时间复杂度：n*log(n)

需要注意：避免栈溢出。



• 贪心算法

背包问题：小偷背了一个4磅背包去商城偷东西，将哪些商品放入背包才能收益大化。

改进贪心算法-迪杰斯特拉算法（最快路径)，迪杰斯特拉算法的核心是找到起点到每个节点的快路径

1. 找出“便宜”的节点，即可在短时间内到达的节点。

2. 更新该节点的邻居的开销，检查是否有前往它们的更短路径，如果有，就更新其开销。

3. 重复这个过程，直到对图中的每个节点都这样做了。

4. 计算终路径。

• 动态规划

通过找到合适的角度，将所求解的目标值在某（几）个维度上展开，将一个大问题拆解为若干小问题，从小问题的优解，寻找大问题的优解

每个动态规划算法都从一个网格开始



• 遗传算法解决背包问题

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

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



1. 基因编码与染色

2. 适应函数与控制参数

3. 选择算法

• 轮盘赌选择（Roulette Wheel Selection）：是一种回放式随机采样方法。每个染色体 进入下一代的概率等于它的适应度值与整体适应度值和的比例。

• 随机竞争选择（Stochastic Tournament）：每次按轮盘赌选择一对个体，然后让这两 个个体进行竞争，适应度高的被选中，如此反复，直到选满为止。

• 均匀排序：对群体中的所有个体按期适应度大小进行排序，基于这个排序来分配各个 个体被选中的概率

1. 交叉遗传

生产下一代：染色体交叉遗传，循环迭代，如果连续几代遗传都没有出现更强的染色体（价值总和更大），那么算法收 敛，当前大价值的染色体为终解。

有时候会在遗传过程中进行基因突变，得到基因突变染色体。



遗传算法得到的不是最优解。但结果是比较乐观的结果。



-----



网络通信协议



###### OSI七层模型

• 应用层 Application Layer 为用户的应用提供服务并支持网络访

• 表示层 Presentation Layer 负责转化数据格式，并处理数据加密和数据压缩

• 会话层 Session Layer 负责管理网络中计算之间的通信，提供传输层不具 备的连接相关功

• 传输层 Transport Layer 提供端对端的接口

• 网络层 Network Layer 为数据包选择路由

• 数据链路层 Data Link Layer 传输有地址的帧以及错误检测功能

• 物理层 Physical Layer 在物理媒介上传输二进制格式数据



###### TCP/IP四层模型



• 应用层 Application Layer 对应OSI七层模型：应用层，表示层，会话层

• 传输层 Transport Layer 对应OSI七层模型：传输层

• 网络互联层 Internet Layer 对应OSI七层模型：网络层

• 网络访问（链路）层 Network Access(Link) Layer 对应OSI七层模型：数据链路层， 物理层



###### 物理层

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



###### 链路层

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

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

案例：



• 数据链路层负载均衡



###### 网络层

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

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

案例：IP 负载均衡



###### 传输层（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。



###### 应用层HTTP协议

而互联网应用需要在全球范围为用户提供服务，将全球的应用和全球的用户联系在一起， 需要一个统一的应用层协议，这个协议就是HTTP 协议。

HTTP请求的7种方法



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

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

• Post：提交请求。

• Put：上传请求。

• Delete：删除URL标识的资源。

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

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



HTTP响应的5种状态

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

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

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

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

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



HTTP协议版本

1996 年发布了HTTP/1.0 ，在 HTTP/1.0 中，客户端和服务器之 间交换的每个请求/ 响应都会创建 一个新的TCP 连接，这意味着所 有请求之前都需要进行TCP握手 连接，因此所有请求都会产生延 迟。



HTTP/1.1 试图引入保持连接的概念来解决这些问题，它允许客户端复用TCP 连接，从 而分摊了建立初始连接和针对多个请求缓慢启动的成本。但任意时点上每个连接只能执行一次请求/ 响应交换。



随着网络的发展，网站所需资源（CSS、JavaScript 和图像等）不断增长，浏览器在获 取和呈现网页时需要越来越多的并发性。但由于HTTP/1.1 只允许客户端同时进行一次 HTTP 请求/ 响应交换，因此在网络层上获得并发能力的唯一方法是并行使用多个TCP 连接



HTTP/2 引入了HTTP“流”的概念，允许将不同的HTTP 并发地复用到同一TCP 连接 上，使浏览器更高效地复用TCP 连接。HTTP/2 解决了单个TCP 连接的使用效率低的 问题，现在可以通过同一连接同时传输多个请求/ 响应。但是，TCP并不理解HTTP流， 当多个HTTP请求复用一个TCP连接，如果前面的请求/响应没有处理完，后面的请求/响 应也无法处理，也就是会出现队头堵塞现象。



HTTP/3 不是使用TCP 作为会话的 传输层，而是使用QUIC （一种新 的互联网传输协议）。该协议在传 输层将流作为一等公民引入。多个 QUIC 流共享相同的QUIC 连接， 因此不需要额外的握手和慢启动来 创建新的QUIC 流。但QUIC 流是 独立的，因此在大多数情况下，只 影响一个流的丢包不会影响其他流， 这是因为QUIC 数据包封装在UDP 数据包。



----



计算机之间如何进行网络请求？



• 服务器-客户端

• 多线程服务器-客户端

• 线程池服务器



###### BIO Blocking I/O 阻塞I/O



• 阻塞I/O：进行I/O操作时，用户线程会一直阻塞，直到读操作或者写操作完成。

• 非阻塞I/O（Non-Blocking I/O ）

非阻塞I/O：I/O操作立即返回,发起线程不会阻塞等待。

非阻塞read操作：

• Socket接收缓冲区有数据，读n个（不保证数据被读完整，因此有可能需要多次读）。

• Socket接收缓冲区没数据，则返回失败（不会等待）。



非阻塞write：

• Socket发送缓冲区满，返回失败（不会等待）。

• Socket发送缓冲区不满，写n个数据（不保证一次性全部写入，因此可能需要多次写）。

###### BIO Blocking I/O 阻塞I/O实现



• Java NIO (New I/O) 与Java IO

Java NIO中，无活动连接时，Selector.select方法被阻塞

• 系统I/O复用方式：select，poll，epoll