Basics of IO

IO 也是 memory 组成的一部分。我们使用 mapped memory 方式来访问 IO。

Characters of IO

IO 有三种：

只读：比如鼠标、键盘
只写：比如显示器
可读写：比如硬盘、网络接口

IO 的对象要么是人类（鼠标键盘显示器）、要么是机器（网络硬盘磁带）。

带宽是 IO 的重要指标。

Performance Metrics of IO

吞吐量（Throughput）：吞吐量也可以分为两种情况。前者就是 bit/byte per second，后者则是 IOPS (i/o operations per second)
- 对于大容量存储（bulk storage）而言，带宽是瓶颈
- 对于流媒体来说，有时处理能力是瓶颈，因为需要传输大量的小视频块
反应时间：跟人交互的 IO 设备，response time 非常重要

Recap: Amdahl's Law

如果硬盘等 IO 的性能不提高，那么就会严重拖后腿。

Some Issues

我们有多种方法可以提高速度、增加寿命：

软件优化：虽然 average seek time 大可能会造成一定影响，但是，通过下面的方法，可以一定程度上使得 AST 不那么重要
- locality：尽量连续读
- OS scheduling：我们并不见到一块就去读一块，而是将需要读取的硬盘地址排序，使得 seek time 尽量低
使用更 smart 的磁盘控制器。
- 预取：可以使用更好的预取方式——预测接下来要用到的数据
- 我们还可以设计更好的空间分配算法，让磁盘的每一块能够更加均衡地被访问
- ……

硬盘控制器还要做些什么？

硬盘控制器还需要进行纠错编码（一般是 ECC）等等。

事实上，磁盘控制器是非常复杂的东西，设计难度并不小于一个 CPU

Categories of Storage Devices

对于磁盘，可以参考 DBMS: Storage。下面我们讲一讲 flash memory。

对于 NOR flash 而言，我们可以进行随机读写。缺点是储存密度不高，一般不超过 1MB。通常用于嵌入式设备的 IMem。

对于 NAND flash 而言，只能整块地读写，但是密度高，容量大，很容易达到 GB 级别，因此广泛用于 USB、移动硬盘等等。

NOR vs NAND: more details

对于 NOR 而言，写入的时候，如果是 1 改成 0，那么就可以直接改；如果是 0 改成 1，那么必须要整块擦除。

对于 NAND 而言，不管写些什么，都需要整块擦除。

而擦除会对其造成很大的破坏，一个 block 擦除 10000 次之后就不能用了。

Availability

除了 performance 以外，我们还需要考虑其稳定性。

电脑上每一个模块都有一个理想情况下的 behavior，如果实际执行情况与理想情况不符，就是 service interruption/failure。

Availability Metric

主要有三个概念：

MTTF: Mean Time To Failure
MTTR: Mean Time To Repair
MTBF: Mean Time Between Failures
- MTBF = MTTR + MTTF

显而易见，availability = (time you can use) / (all time) = MTTF / MTBF = MTTF / (MTTF + MTTR)

如何提升 MTTF？

其中，fault tolerance 本质上就是通过冗余的方式来进行 fault avoidance。比如：

使用 ECC 纠正单比特错误
使用多 CPU 同时运行来纠正某一个 CPU 的错误（在太空中常用）

fault forecasting 有一个例子：如果服务器连续运行了一定的时间，就要进行重启，从而回收泄露的内存以及运行时 bug。

fault 都是谁引起的？

据统计（如下图），最多的 fault 还是人为引起的。因此要尽量自动化，少使用人工操作。

Disk Array

通过小磁盘 + 磁盘并行访问，我们可以做到成倍地加快磁盘速度。

问题就在于：通过现有的策略（RAID0，我们之后会讲到），

如果有一个磁盘坏了，那么所有硬盘上的数据都会损坏
同时，一个硬盘坏了，整个阵列都会无法使用。而增加磁盘的数量，将会成倍地减小 MTTF。

因此，我们需要通过冗余来减小这样的情况发生。

RAID: Redundant Array of Inexpensive Disks

为了均衡性能、储存效率和 MTTF，我们将 RAID 分成下面这么多的等级。

Level	Description	Minimum numbers of drives	Space efficiency	Fault tolerance	Fault isolation	Read performance	Write performance
RAID 0	Block-level striping without parity or mirroring	2	1	None	Drive Firmware Only	n	n
RAID 1	Mirroring without parity or striping	2	1/n	n − 1 drive failures	Drive Firmware or voting if n > 2	n	1
RAID 2	Bit-level striping with Hamming code for error correction	3	\(1 - \frac1n \log_2(n+1)\)	One drive failure	Drive Firmware and Parity	Depends	Depends
RAID 3	Byte-level striping with dedicated parity	3	1 − 1/n	One drive failure	Drive Firmware and Parity	n − 1	n − 1
RAID 4	Block-level striping with dedicated parity	3	1 − 1/n	One drive failure	Drive Firmware and Parity	n − 1	n − 1
RAID 5	Block-level striping with distributed parity	3	1 − 1/n	One drive failure	Drive Firmware and Parity	n	single sector: 1/4
RAID 6	Block-level striping with double distributed parity	4	1 − 2/n	Two drive failures	Drive Firmware and Parity	n	single sector: 1/6

如图，在实际中：

RAID 0 被广泛使用，通常用于对速度、存储要求高，但是不太在乎 MTTF 的情况
RAID 1 被用于非常在意数据安全的情况
RAID 4 在某些网络应用中被使用
- 注意：RAID 3 本质上和 RAID 4 是一样的，只不过 RAID 4 更实际，以 block 为单元，而不是 byte
RAID 5 被广泛使用，是比较均衡的选择

RAID 的一些概念

首先，衡量一种 RAID 效率的指标有两个：储存效率和读写效率。

储存效率：就是 \(\frac {\text{logical disk size}} {\text{physical disk size}}\)
读/写效率：主要就是支持多少并发读写
- Small Read/Write: 可以在满足约束条件的情况下，一次只读/写一行中某一个盘
- Large Read/Write: 在满足约束条件的情况下，一次必须读/写一行所有盘
bit/byte/block 条带化：就是将 bit/byte/block 1 放到 disk 1，bit/byte/block 2 放到 disk 2，……，bit/byte/block n 放到 disk \(n \% \# \text{of disks}\)

RAID 3

如图，如果

只有一个盘损坏
我们知道损坏的是哪一个盘

那么就可以将这个盘进行恢复。

Parity Code vs Hamming Code

假如不知道损坏的是哪一个盘，还是老老实实用 hamming code 的 RAID 2 吧。

RAID 3 的不足

只能够 large write。而不能 small write。

这是因为 RAID 3 是 byte-条带化的，从而逻辑中的一块是分布在物理上的所有块上的。
因此，如果你希望写逻辑中的一块进入磁盘，那么必须在物理上将数据同时写入所有磁盘。

RAID 4

RAID 4 和 RAID 3 的差别是：

RAID 4 是 block 条带化的，而 RAID 3 是 byte 条带化的。
RAID 4 支持 small write。由于 \(P_\text{old} = \text{other tables} \oplus \text{old data of this table}\)，因此，\(P_\text{new} = \text{other tables} \oplus \text{new data} = \text{other tables} \oplus \text{old data} \oplus \text{old data} \oplus \text{new data} = P_\text{old} \oplus \text{old data} \oplus \text{new data}\)。我们只需要通过该块的旧数据、新数据和奇偶校验块本身，就可以计算得出。

RAID 4 相比 RAID 3 的缺点

缺点很简单：假如说需要反复读某些块，而这些块在硬盘阵列上分布得不均匀。那么，就很容易导致硬盘之间的损耗不均匀（i.e. 某些硬盘比其他硬盘更早坏）。