第 8 周 作业 2

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

机器硬盘 VS 固态硬盘

机器硬盘：磁臂、磁头的寻道移动很慢（毫秒级），磁盘转速到指定扇区次之（7400 转/min）。数据如果不在连续磁道上读写性能会非常低（数据存储是否连续影响读取）。

固态硬盘：电子控制器，尽量都用连续读写。

B+ 树（通常高度不超过 4）：索引的快速查找

LSM 树（Log Struct Merge）：解决数据离散的存储。现在内存中构建一个树，当这颗树超过一定范围的时候，把树合并到外部，以日志方式刷新出去。

文件控制块

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

每个块 4K，HDFS 每个块 64M（不适合小文件）

Inode 文件控制块：

• 记录了文件权限、所有者、修改时间、文件大小等文件属性，以及文件数据块硬盘地址索引。

• inode 固定结构，只有 15 个硬盘地址索引数。前 12 个是直接指向数据块，后面分别 1 个一级间接索引表指针、1 个二级间接索引表指针、1 个三级间接表索引指针。如果数据小于 64K（12\*4=64），查找是很快的。

• 最多可以存储 12+256+256\*256+256\*256\*256 个数据块，单个块为 4K，单文件不能超过 70G。

RAID 独立硬盘冗余阵列：通过分片向多个硬盘、多个服务器提供并发读写

分布式文件系统 HDFS：通过分片向多个服务器提供并发读写

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

时间复杂度

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

• O(1)，O(longn), O(n^a) 多项式时间复杂度

• O(a^n), O(n!) 非多项式时间复杂度

旅行商问题

空间复杂度

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

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

NP 问题

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

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

基本数据结构

• 数组

内存中一块连续的空间，数组中必须存放相同的数据类型。

重要特性：随机快速读写，时间复杂度 O(1)

• 链表

可以使用零散的内存空间存储元素，每个元素必须包含一个指向下个元素内存地址的指针

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

链表中删除、增加元素性能很高

• Hash 表

快速的数据查找和读写

• 堆栈

数组和链表都是线性表

线性表增加操作限制：后进先出

线程调用栈

栈顶元素总是在最顶端：保证元素是栈顶的作用域中

• 队列

操作受限的线性表。先进先出

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

用队列搜索最短路径

红黑树原理与性能特性

树

• 二叉排序树：递归定义

• 平衡二叉排序树：任何一个节点，左右子树深度之差绝对值不超过 1，左右子树任然为平衡二叉排序树

• 红黑树：

红黑树 VS 平衡二叉树

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

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

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

跳表

一个排序的链表，元素跳起来，减少查找的路径。

主要实现是增加、删除元素

更多的空间要求

经典算法

穷举算法：列出所有可能性，找出最有解

递归算法（自己调用自己），快速排序算法

模版：

def recursion(level, param1, param2, ...):
  # recursion terminator 递归终止条件
  if level > MAX_LEVEL:
    process_result
    return
  # process logic in current level 处理当前逻辑
  process(level, data)
  # drill down 下转到下一层
  self.recursion(level+1, p1, ...)
  # reverse the current level status if needed 恢复当前状态

贪心算法：当前看来是最好的选择，不考虑全局上的最优解

动态规划：背包问题

遗传算法与染色体

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

第一层：Physical 层，传输二进制数据

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

第二层：Data Link 层，数据叫 Frame，协议有 ARP

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

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

数据链路层负载均衡

- 通过虚拟 IP 技术，集群对外提供一个 IP，负载均衡器通过修改数据帧的 MAC 地址，将包交给集群内不同服务器处理，处理完后，服务器直接将数据返回给请求方，不再经过负载均衡服务器返回。性能比 IP 层负载均衡性能高。

第三层：Network 层，数据叫 Packet

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

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

IP 负载均衡

负载均衡器通过修改数据包的目的 IP 地址将数据包转给不同集群内的服务器处理，处理完后服务器的返回数据包返回给负载均衡服务器，负载均衡服务器再修改数据包的目的 IP，将数据包发给实际的请求 IP 地址。

第四层：Transport 层，数据叫 Segment

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

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

使用序号，对收到的 TCP 报文段进行排序和检测重复的数据 无错传输，使用校验和检测报文段的错误

使用确认和计时器来检测和纠正丢包或者延时 流量控制，避免主机分组发送得过快而使接收方来不及完全收下 拥塞控制，发送方根据网络承载情况控制分组的发送量，以获得高性能同时避免拥塞崩溃 丢失包的重传

第五层：Session 会话层

第六层：Presentation 表示层

第七层：Application 应用层

HTTP1 - 每个请求都会创建一个新的 TCP 连接，都需要进行 TCP 握手连接，产生延迟。

HTTP1.1 - 通过长连接，允许客户端复用 TCP 连接，分摊每个连接建立的成本，但是一个时间点每个连接只能进行一次请求/响应交换。通过并行使用多个 TCP 连接获得并发能力。

HTTP2 - 引入“流”概念，同一连接同时传输多个请求/响应，存在对头堵塞现象。

QUIC - 通过 UDP 协议传输数据。

## 非阻塞网络 I/O

Socket、端口

fd 文件描述符：它是一个索引值，指向内核为每一个进程所维护的该进程打开的记录表。

当程序打开一个现有文件或者创建一个新文件时，内核向进程返回一个文件描述符，在程序设计中，一些涉及底层的程序编写往往会围绕着文件描述符展开。

IO 缓存：又称作标准 IO，大多数文件系统的默认 IO 操作都是缓存 IO。在 Linux 的缓存 IO 机制中，操作系统会将 IO 的数据缓存在文件系统的页缓存（page cache）中，也就是说，数据会先被拷贝到操作系统内核的缓存区，然后才会从操作系统内核的缓冲区拷贝到应用程序的地址空间。

数据在传输过程中需要在应用程序地址空间和内核进行多次数据拷贝操作，这些数据拷贝操作所带来的 CPU 以及内存开销是非常大的。

多线程服务端-多少个连接就需要多少线程

线程池服务器

BIO Blocking I/O 阻塞 I/O

C10k 、 C10M 问题