文件与硬盘 IO

机械硬盘

固态硬盘

磁盘存储数据结构

B+Tree

LSM

B+tree 保存在磁盘中时它也有一个明显的缺陷，那就是逻辑上相离很近但物理却可能相隔很远，这就可能造成大量的磁盘随机读写。随机读写比顺序读写慢很多，为了提升 IO 性能，我们需要一种能将随机操作变为顺序操作的机制，于是便有了 LSM 树。LSM 树能让我们进行顺序写磁盘，从而大幅提升写操作，作为代价的是牺牲了一些读性能。

文件控制块

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

Linux Inode 文件控制块

RAID 独立硬盘冗余阵列

提高磁盘写的性能和高可用，常用 Raid5

HDFS 架构

数据结构与算法

时间复杂度与空间复杂度

时间复杂度

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

空间复杂度

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

NP 问题

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

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

数据结构

数组

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

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

随机快速读写是数组的一个重要特性，根据数

组的下标访问数据，时间复杂度为 O(1)。

链表

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

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

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

Hash 表

栈

队列

树

二叉排序树

平衡二叉（排序）树

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

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

旋转二叉树恢复平衡

红黑（排序）树

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

根节点是黑色的。

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

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

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

跳表

常用算法

穷举算法

递归算法

贪心算法

动态规划

网络通信协议

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

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

网络数据包格式

物理层

物理层负责数据的物理传输，计算机输入输出的只能是 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 次挥手

应用层 HTTP 协议

HTTP 请求的 7 种方法

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

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

Post：提交请求。

Put：上传请求。

Delete：删除 URL 标识的资源。

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

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

HTTP 响应的 5 种状态

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

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

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

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

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

非阻塞网络 I/O

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

服务器 - 客户端

多线程服务器-客户端

线程池服务器

BIO Blocking I/O 阻塞 I/O

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

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

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

非阻塞 read 操作：

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

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

非阻塞 write：

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

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

Java NIO (New I/O)

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

Select（poll） 管理下的 read 过程

epoll 管理下的 read 过程

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