第八周学习心得

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

机械硬盘性能的影响因素：

数据是否连续存储在机械磁盘的磁道上固态硬盘虽然使用芯片的存储，但也是由控制器控制读写的，即使没有了机械结构，随机的读写也是比不上连续读写的

传统的数据库使用的 B+树操作：

是一种索引树的操作，读写的时候即使有索引，也是离散存储在存储上，会产生一个较高的磁盘 io 消耗





lsm 树：

log 合并树是以连续的方式读写的，所以会比 b+树会快

文件控制块：

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





Linux Inode 文件控制块：

1.          inode 中记录着文件权限、所有者、修改时间和文件大小等文件属性信息

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

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

RAID 独立硬盘冗余阵列：

单个的硬盘读写速度会比较慢，那么是不是多个硬盘协同工作的时候是不是可以提高性能，这就是 raid，一个磁盘读写相当于一个文件的数据块都是串行读或写到文件上，当文件的块的数量不变的情况下，做 raid 相当于将文件块读或写从串行变成了多个磁盘并行，从而提高读取或写入速度

1.          RAID 0：平分几分，同时进行读写操作

2.          RAID 1：单块读写，相同大小的一块磁盘作为纯备份

3.          RAID 10：即 raid1 和 raid0 结合多个磁盘做 raid0 之后用相同的一套 raid0 来做 raid1 来做备份

4.          RAID 5：并不是每个磁盘做备份，而是通过数据校验信息，对数据进行校验位来做数据准确性检查，校验盘上是通过一种异或算法存储的校验信息，校验位的存储是螺旋式存储的

5.          RAID 6：为了解决在连续的几块硬盘一起损坏的问题，会计算两个校验信息进行存储，但是磁盘利用率和性能会降低





分布式文件系统 HDFS：

以前是以磁盘为分片，现在是以服务器为分片，还是将数据块分片记录到服务器上，hdfs 数据块默认是 64M，它面向的是大文件的存储与计算，所以用 hdfs 来存储小文件是不划算的





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

时间复杂度和空间复杂度：

1.          时间复杂度：

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

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

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

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

2.          空间复杂度：

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

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





NP 问题：

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

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

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

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

基本的数据结构：

1.          数组：

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

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

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

2.          链表：

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

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

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

3.          链表和数组对比：

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

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

                用数组记录类似索引，分类的标志，将内容存储为一个链表的指针，实现结合链表和数组的优点



5.          Hash 表：

1.          时间复杂度为 O(1)的数据结构

2.          hash 表实际上是一种数组

3.          哈希表是一个数组，hash 表是 kv 形式来存储的，内存中数组通过内存地址作为下表，通过 key 可以计算出哈希表在内存中的地址（也就是数组下表）Hash 冲突：

6.          栈：

1.          数组和链表都被称为线性表，只有一个前驱，只有一个后继

2.          栈就是在线性表的基础上加了条件限制：后面添加的数据，在删除的时候必须先删除，即“后进先出”

3.          线程运行时专有的内存为什么被称为线程栈

7.          队列：

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

2.          典型场景：生产者、消费者；阻塞等待的线程被放入队列

8.          例：

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

2.          用队列搜索最短路径

红黑树原理与性能特性

树：

依据父子关系，建立数据之间关系

常见的树：

二叉排序树：

时间复杂度 O(logn)(特殊情况如不平衡的二叉排序树，有时会退化成链表，就不是 logn 了)





1.          左子树上所有节点的值均小于或等于它的根节点的值

2.          右子树上所有节点的值均大于或等于它的根节点的值

3.          左右字数也分别为二叉排序树（递归）

平衡二叉排序树：





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

2.          左右子树仍然为平衡二叉树

旋转二叉树恢复平衡：





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

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

红黑（排序）树：





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

2.          根节点是黑色的

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

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

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

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





红黑树 VS 平衡二叉树：

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

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

3.          红黑树的平衡性不如平衡二叉树，查找效率要查差一点

跳表：





1.          先构建一个链表

2.          然后更具一定的规则将链表中个别对象跳起来形成新的链表

3.          可以跳多次

4.          时间复杂度大约是 O(logn)

经典算法：

常用算法：

1.          穷举算法

2.          递归算法

3.          贪心算法

4.          动态规划

递归算法（快速排序算法）：时间复杂度 n*log(n)





贪心算法：

在对问题求解时，总是做出再当前看来是最好的选择。即不从整体最优上加以考虑，算法得到的实在某种意义上的局部最优解

例：背包问题





改进贪心算法·迪杰斯特拉算法（最快路径）





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

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

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

4.          计算最终路径

5.          核心：找到起点到每一个节点的最快路径

6.          解法：











动态规划算法解决背包问题：

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

例：还事背包问题

每个动态规划算法都从一个网格开始，背包问题如下：













遗传算法解决背包问题：

模拟达尔文生物进化论的自燃选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自燃进化过程搜索最优解得方法遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容

例：





基因编码与染色体：

1.          物品基因编码：



基因组合：染色体

1.          选择初始染色体：随机产生（也可以认为活着算法选择）



2.          适应函数与控制参数：选择适应函数，这里为商品总价



3.          选择控制参数，这里为总重量



选择算法：

在剩下的染色体重选择刻意被遗传下去的染色体以及繁殖次数





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

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

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

交叉遗传：

1.          选择结果：101010 和 010101 各繁殖两次

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



3.          有时，在遗传过程中会出现基因突变，得到基因突变染色体

注意：遗传算法得到的不是最优解

遗传算法过程：





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

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





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







网络数据包格式：





1.          物理层：

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

2.          链路层：

               链路层就是将数据进行封装后交给物理层进行传输，主要就是将数据封装成数据帧，以帧为单位通过物理层进行通信，有了帧，就可以在帧上进行数据校验，以帧为单位进行流量控制链路层会定义帧大小，这个大小也被称为最大传输单元，像 HTTP 要在传输的数据上添加一个 HTTP 头一样，数据链路层也会将封装好的帧添加一个帧头，帧头里记录的一个重要的信息就是发送者和接受者的 mac 地址。mac 地址是网卡的设备标识符。是唯一的，数据帧通过这个信息确保数据送达到正确的目标机器。

               数据链路层负载均衡：链路层实际应用



3.          网络层：

               网络层 IP 协议使得互联网应用根据 IP 地址就能访问到目标服务器，请求离开 App 后，到达运营服务商的交换机，交换机会根据这个 IP 地址经行路由转发，可能中间会经过很多个转发节点，最后数据到达目标服务器。网络层的数据需要交给链路层经行处理，而链路层帧的大小定义了最大传输单元，网络层的 IP 数据包必须姚晓宇最大传输单元才能经行网络传输，这个数据包也有一个 IP 头，主要包括的就是发送者和接受者的 IP 地址。

               IP 负载均衡：



4.          传输层（TCP）：

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

TCP 协议

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

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

2.          无措传输：试用校验和检测报文段的错误

3.          使用确认和计时器来检测和纠正丢包或延迟

4.          流量控制：避免主机分组发送的过快而使接收方来不及完全收下

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

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 的报文给服务器

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

TCP 关闭连接 4 次挥手：可以是任何一方发起





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

2.          当服务器接收到客户端的 FIN 时，向客户端发送一个 ACK

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

4.          当客户端厚道服务器端的 FIN 时，回复一个 ACK 给服务器端

应用层 HTTP 协议：

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





HTTP 请求的 7 种方法

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

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

3.          Post：提交请求

4.          Put：上传请求

5.          Delete：删除 URL 标识的资源

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

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





HTTP 响应的 5 种状态：

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

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

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

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

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





HTTP 协议版本：

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



2.          HTTP/1.1 试图引入保持连接的概念来解决这些问题，它允许客户端复用 TCP 连接，从而分摊了建立初始连接和针对多个请求缓慢启动的成本。但任意时点上每个链接只能执行一次请求/响应交换，随着网络发展，网站所需资源（CSS、JavaScript 和图像等）不断增长，浏览器再获取和呈现网页时需要越来越多的并发性。但由于 1.1 只允许客户端同时进行一次 HTTP 请求/响应，因此在网络层上获得并发能力的唯一方法是并行试用多个 TCP 链接



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



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



非阻塞网络 I/O

服务器-客户端：利用系统提供的网络接口进行编程





多线程服务器-客户端：有多少个连接就启用多少个线程







BIO Blocking I/O 阻塞 I/O

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





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





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

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

非阻塞 read 操作：

1.          非阻塞 read 操作：

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

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

2.          非阻塞 write 操作：

1.          Socket 发送缓冲区，返回失败（不会等待）

2.          Socket 发送缓冲区不满，写 n 个数据（不保证一次性全部写入，因此肯恩需要多次写）





通过 Java 体统的 Nio 类来实现非阻塞式的网络通信编程





通过 java IO 和 NIO 的代码对比，观察 IO 是阻塞式的通信模式，NIO 通过事件模式，多路复用实现高效的网络读写





selector 通过 select，pull 和 epoll 方式进行读写：多路复用的模式实现





Select（与 poll 差不多）管理下的 read 过程：需要遍历事件列表，性能相对比较差





epoll 管理下的 read 过程（需要操作系统支持 eventpoll）：





无活动连接时，Selector.select 方法被阻塞（虽然是非阻塞式的，但是无线死循环也是很耗资源的，在没有连接时就阻塞住）