架构师训练营第 1 期 - 第 8 周 - 学习总结

8.1 文件与硬盘 I/O：如何把硬盘的读写速度提高十万倍？

机械硬盘与固态硬盘

B+树 、LSM 树

文件控制块（FCB）

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

Linux Inode 文件控制块

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

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

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

RAID 独立硬盘冗余阵列 （0，1，10，5，6）

分布式文件系统 HDFS

8.2 常见数据结构与 Hash 表原理分析

8.3 红黑树原理与性能特性

8.4 经典算法

数据结构与算法

-->时间复杂度（算法执行语句的次数），空间复杂度（一个算法在运行过程中临时占用存储空间大小的量度。）

NP 问题

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

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

Ø  NP ?= P

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

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

线性表：数组，链表，栈（-->线程调用栈），队列

Hash 表

树（二叉排序树，平衡二叉排序树，旋转二叉树恢复平衡，红黑排序树，跳表）

常用算法：穷举算法，递归算法，贪心算法，动态规划，遗传算法

8.5 网络通信基本原理与性能优化

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

ISO 七层模型

TCP/IP 四层模型

TCP 协议：面向连接的、可靠的，基于字节流的传输层协议。流量控制，拥塞控制。

TCP 3 次握手 和 4 次挥手

应用层协议 HTTP

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

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

Post：提交请求。  Put：上传请求。   Delete：删除 URL 标识的资源。

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

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

HTTP 协议版本：

HTTP/1.0

HTTP/1.1 保持连接

HTTP/2 HTTP "流" ==》 队头堵塞现象

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

8.6 非阻塞网络 I/O -- Java NIO (New I/O)

Selector

SelectionKey

SelectableChannel

Buffer