架构训练营 -week8- 数据结构与算法，网络，IO

[TOC]

文件与硬盘 I/O

基本概念：

• 机械硬盘

• 固态硬盘

B 树

一个 m 阶的 B 树具有如下几个特征：B 树中所有结点的孩子结点最大值称为 B 树的阶，通常用 m 表示。一个结点有 k 个孩子时，必有 k-1 个关键字才能将子树中所有关键字划分为 k 个子集。

• B 树主要用于文件系统以及部分数据库索引，例如： MongoDB。而大部分关系数据库则使用 B+树做索引，例如：mysql 数据库；

• 从查找效率考虑一般要求 B 树的阶数 m >= 3;

• B-树上算法的执行时间主要由读、写磁盘的次数来决定，故一次 I/O 操作应读写尽可能多的信息。因此 B-树的结点规模一般以一个磁盘页（一般是 4K）为单位。一个结点包含的关键字及其孩子个数取决于磁盘页的大小。

B+树

Ｂ＋树是Ｂ树的变种，B+树相比 B 树的优势：　　1.单一节点存储更多的元素，使得查询的 IO 次数更少；　　2.所有查询都要查找到叶子节点，查询性能稳定；　　3.所有叶子节点形成有序链表，便于范围查询。

有关 B 树/B+树的详细内容，参见：https://blog.csdn.net/z_ryan/article/details/79685072

LSM 树 Log-Structured Merge-Tree

参见：https://blog.csdn.net/las723/article/details/93767240

不属于一个具体的数据结构，它更多是一种数据结构的设计思想。大多 NoSQL 数据库核心思想都是基于 LSM 来做的，只是具体的实现不同。

LSM 树原理

LSM 树由两个或以上的存储结构组成，比如在论文中为了方便说明使用了最简单的两个存储结构。一个存储结构常驻内存中，称为 C0 tree，具体可以是任何方便健值查找的数据结构，比如红黑树、map 之类，甚至可以是跳表。另外一个存储结构常驻在硬盘中，称为 C1 tree，具体结构类似 B 树。C1 所有节点都是 100%满的，节点的大小为磁盘块大小。

插入一条新纪录时，首先在日志文件中插入操作日志，以便后面恢复使用，日志是以 append 形式插入，所以速度非常快；将新纪录的索引插入到 C0 中，这里在内存中完成，不涉及磁盘 IO 操作；当 C0 大小达到某一阈值时或者每隔一段时间，将 C0 中记录滚动合并到磁盘 C1 中；对于多个存储结构的情况，当 C1 体量越来越大就向 C2 合并，以此类推，一直往上合并 Ck。

文件控制块

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

Linux Inode

大小固定

RAID 独立硬盘冗余阵列

原理

比较：

分布式文件系统 HDFS

略

数据结构与算法

时间复杂度与空间复杂度

• 概念略

• 常见时间复杂度比较

NP 问题

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

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

• NP ?= P

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

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

常见的数据结构

简单的内容就不列出相关知识点了，这块实在太基础了~.~

数组

链表

Hash 表

数组+链表，实现快速查找与删除 --> JDK HashMap 基本思想，JDK 1.8 有进一步优化，引入红黑树

知识点：hash 冲突

栈

• 后进先出

队列

• 先进先出

使用：使用队列搜索最短路径

• 实际上就是使用队列来实现 BFS

树

二叉排序树

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

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

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

平衡二叉树

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

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

插入/删除节点时，通过旋转二叉树来回复平衡

红黑树

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

• 根节点是黑色的。

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

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

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

跳表

常见算法

• 穷举算法

• 递归算法

• 贪心算法

• 动态规划

• 遗传算法

网络通信协议

一次网络通信历程

OSI 模型与 TCP/IP 模型比较

网络数据包格式

TCP/IP 模型各层详解

物理层

负责数据的物理传输。

链路层

将数据封装成数据帧，以帧为单位通过物理层进行通信，有了帧，就可以在帧上进行数据校验，进行流量控制。

链路层会定义帧的大小，这个大小也被称为最大传输单元（Maximum Transmission Unit）。

一个标准的以太网数据帧大小是：1518，头信息有 14 字节，尾部校验和 FCS 占了 4 字节，所以真正留给上层协议传输数据的大小就是：1518 - 14 - 4 = 1500。

MTU 为何是 1500 参见 这篇文章：https://developer.aliyun.com/article/222535

上图来自《网络是怎样连接的》。

TCP 头部长度为 20-60 字节，IP 头部长度为 20-60 字节，一般而言这两者都是 20 字节，因此 MSS 长度一般为 1460 字节。

数据链路层也会将封装好的帧添加一个帧头，帧头里记录的一个重要信息就是发送者和接受者的 MAC 地址。

网络层

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

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

传输层

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

TCP 协议是一种面向连接的、可靠的、基于字节流的传输层协议。

TCP 作为一个比较基础的通讯协议，有很多重要的机制保证了 TCP 协议的可靠性和强壮性：

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

• 无错传输，使用校验和检测报文段的错误

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

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

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

• 丢失包的重传

TCP 建立连接 3 次握手

TCP 关闭连接 4 次挥手

4 次挥手可能引起的问题

和服务器的通信结束之后，用来通信的套接字也就不会再使用了，这时我们就可以删除这个套接字了。不过，套接字并不会立即被删除，而是会等待一段时间之后再被删除。等待这段时间是为了防止误操作，引发误操作的原因有很多，比如，假设客户端先发起断开，4 次挥手流程如下：

（1）客户端发送 FIN

（2）服务器返回 ACK 号

（3）服务器发送 FIN

（4）客户端返回 ACK 号

如果最后客户端返回的 ACK 号丢失了，结果会如何呢？这时，服务器没有接收到 ACK 号，可能会重发一次 FIN。如果这时客户端的套接字已经删除了，会发生什么事呢？套接字被删除，那么套接字中保存的控制信息也就跟着消失了，套接字对应的端口号就会被释放出来。这时，如果别的应用程序要创建套接字，新套接字碰巧又被分配了同一个端口号 B，而服务器重发的 FIN 正好到达，会怎么样呢？本来这个 FIN 是要发给刚刚删除的那个套接字的，但新套接字具有相同的端口号，于是这个 FIN 就会错误地跑到新套接字里面，新套接字就开始执行断开操作了。之所以不马上删除套接字，就是为了防止这样的误操作。

至于具体等待多长时间，这和包重传的操作方式有关。网络包丢失之后会进行重传，这个操作通常要持续几分钟。如果重传了几分钟之后依然无效，则停止重传。在这段时间内，网络中可能存在重传的包，也就有可能发生前面讲到的这种误操作，因此需要等待到重传完全结束。协议中对于这个等待时间没有明确的规定，一般来说会等待几分钟之后再删除套接字。

以上引自《网络是怎样连接的》

应用层

HTTP 协议。

HTTP 请求的 7 种方法

• GET

• POST

• PUT

• DELETE

• TRACE

• OPTION

• HEAD

HTTP 响应的 5 种状态

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

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

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

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

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

HTTP 协议版本

• HTTP 1.0

• HTTP 1.1

• HTTP 2.0

• HTTP 3.0

非阻塞网络 IO

分类：

• 同步阻塞 IO

• 同步非阻塞 IO

• IO 复用

• 信号驱动 IO

• 异步 IO

阻塞 IO

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

典型：ServerSocket 与 Socket

非阻塞 IO

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

非阻塞 read 操作：

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

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

非阻塞 write：

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

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

示例：JDK NIO

IO 多路复用内部实现

内部实现 select, poll, epoll。

select 是通过不断的轮询，查看是否有就绪事件。如果有的话，再把所有的流遍历一遍看是哪个流准备就绪。而 poll 也是采用这样的轮询，只不过 poll 采用的是链表存储，所以没有最大连接数的限制，epoll 是 even poll，和忙轮询、无差别轮询不一样，它会把哪个流发生了怎样的 I/O 事件通知我们，不用全都遍历一遍才知道是哪个流发生了。所以我们说 epoll 实际上是事件驱动（每个事件关联上 fd）的，此时我们对这些流的操作都是有意义的。（复杂度降低到了 O(1)），而 select 和 poll 查找复杂度都是 O(n)。

select

• 单个进程能够监视的文件描述符（file descriptor）的数量存在最大限制，在 Linux 上一般为 1024，可以通过修改宏定义甚至重新编译内核的方式提升这一限制，但 是这样也会造成效率的降低。

• 从流程上来看，使用 select 函数进行 IO 请求和同步阻塞模型没有太大的区别，甚至还多了添加监视 socket，以及调用 select 函数的额外操作，效率更差。但是，使用 select 以后最大的优势是用户可以在一个线程内同时处理多个 socket 的 IO 请求。用户可以注册多个 socket，然后不断地调用 select 读取被激活的 socket，即可达到在同一个线程内同时处理多个 IO 请求的目的。而在同步阻塞模型中，必须通过多线程的方式才能达到这个目的。

poll

• 没有最大数量限制（因为采用了链表存储，但是数量过大后性能也是会下降）

• 和 select 函数一样，poll 返回后，需要轮询 pollfd 来获取就绪的描述符。

epoll

• epoll 使用一个文件描述符管理多个描述符，将用户关系的文件描述符的事件存放到内核的一个事件表中，这样在用户空间和内核空间的 copy 只需一次。

• epoll 事先通过 epoll_ctl()来注册一 个文件描述符，一旦基于某个文件描述符就绪时，内核会采用类似 callback 的回调机制，迅速激活这个文件描述符，当进程调用 epoll_wait() 时便得到通知。

• 如果没有大量的 idle -connection 或者 dead-connection，epoll 的效率并不会比 select/poll 高很多，但是当遇到大量的 idle- connection，就会发现 epoll 的效率大大高于 select/poll。