OSTEP阅读笔记-Persistence（三）

Chapter I/O设备

Q：如何将I/O集成进计算机系统中？

36.1 系统架构

典型的系统架构如图所示：CPU通过memory bus连接到系统内存。显卡或者其它高速I/O设备通过常规的IO总线（I/O bus，例如PCI）连接到系统。最后是外围总线（peripheral bus，例如SCSI、SATA、USB），他们将最慢的设备连接到系统，包括磁盘、鼠标等。

36.2 标准设备

标准设备包括两部分，分别是：

• 向系统其他部分展现的硬件/软件接口
• 内部结构，包括设备相关的特定实现，负责具体实现设备展现给系统的抽象接口。

36.3 标准协议

一个简化的设备接口包括三个寄存器：

• 一个状态（status）寄存器：读取并查看设备的当前状态
• 一个命令（command）寄存器：用于通知设备执行某个具体任务。
• 一个数据（data）寄存器：将数据传给设备或从设备接收数据。

通过读写这些寄存器，OS可以控制设备的行为。

因此可以将操作步骤设置为如下：

1. OS反复读取状态寄存器，等待设备进入可以接受命令的就绪状态。（轮询）
2. OS将数据发送到数据寄存器。
3. OS将命令写入命令寄存器。
4. OS再次通过不断轮询设备，等待并判断设备是否执行完成命令。

Q：如何减少频繁轮询，从而降低管理设备的CPU的开销？

36.4 利用中断减少CPU开销

设备可以抛出一个硬件中断，引发CPU跳转执行OS预先定义好的中断服务例程（ISR）或者更为简单的中断处理程序（interrupt handler）。

使用中断并非是最佳方案，假如有一个高性能的设备，在CPU第一次轮询时就可以返回结果，那么使用中断反而效率更低。如果设备的速度未知，可以考虑混合策略，先尝试轮询一小段事件，如果设备没有完成操作，此时再使用中断。

如果是网络环境中，那么不要使用中断，因为每个数据包都会发生一次中断，那么可能导致OS发生活锁（一直处理中断程序而不处理用户的请求）。

另一个基于中断的优化就是合并（coalescing），设备在抛出中断之前往往会等待一小段时间，在此期间如果有其他请求的中断，会将多次中断合并为一次中断抛出。从而降低处理中断的代价。

36.5 DMA方式

Q：如何减少Programming IO的开销？

使用DMA（Direct Memory Access）：DMA引擎是一种特殊设备，它可以协调完成内存和设备间的数据传递，不需要CPU介入。

工作过程如下：为了能够将数据传送给设备，OS通过programming告诉DMA引擎数据在内存的位置，要拷贝的大小以及拷贝到哪个设备。在此之后，OS就可以处理其他请求了。当DMA的任务完成后，DMA控制器会抛出一个中断来告诉OS自己完成了数据传输。

36.6 设备交互的方法

Q：如何与设备通信？

• 使用明确的I/O指令。
• 内存映射I/O（memory-mapped I/O）
  • 通过这种方式，硬件将设备寄存器映射到指定的内存地址中。

36.7 纳入OS：设备驱动程序

每个设备都有非常具体的接口，如何将它们纳入OS，而我们希望OS尽可能通用。

Q：如何实现一个设备无关的OS？

操作系统将与IO设备交互的软件称为设备驱动程序。（封装，向上层展现接口即可）

36.8 IDE磁盘驱动程序

基本逻辑如下：

1. 等待驱动就绪：当驱动READY，读取状态寄存器（0x1F7）
2. 向命令寄存器写入参数：写入扇区数，待访问扇区对应的逻辑块地址（LBA），并将驱动编号（master= 0x00，slave = 0x10，因为IDE允许接入两个硬盘）写入命令寄存器（0x1F2- 0x1F6）。
3. 开启I/O：发送读写命令到命令寄存器。向命令寄存器（0x1F7）中写入READ-WRITE命令。
4. 数据传送（针对写请求）：等待直到驱动状态为READY和DRQ（驱动请求数据），向数据端口写入数据。
5. 中断处理：每个扇区的数据传送结束后都会触发一次中断处理程序，可以合并中断。
6. 错误处理：每次操作之后读取状态寄存器，如果ERROR位被置位。可以读取错误寄存器来获取详细信息。

四个主要函数：

• ide_rw()：将一个请求加入队列，或者直接将请求发送到磁盘（通过ide_start_request()）
• ide_start_request()：将请求发送到磁盘
• ide_wait_ready()：确保驱动处于就绪状态
• ide_intr()：发生中断时，该函数会被调用，会从设备中读取数据，并且结束后唤醒等待的进程。如果队列中还有未处理的请求，会调用第二个函数接着处理下一个IO请求。

Chapter 37 磁盘驱动器

Q：现代磁盘驱动器如何存储数据？接口是什么？数据是如何存储和访问的？磁盘调度如何提高性能？

37.1 接口

现代驱动器的基本接口非常简单，驱动器由大量扇区组成，可以进行多扇区操作，但是写入操作只能保证单扇区是原子性的。无法在断电情况下保证完整写入。

37.2 基本几何形状

• 盘片（platter）：磁盘有一个或多个盘片，每个盘片有两面，都称为表面（surface），盘片由一些硬质材料制成，然后涂上薄薄的磁性层，从而持久存储数据位。
• 主轴（spindle）：所有盘片围绕主轴连接在一起，主轴连接到电机，以一个恒定的速度旋转盘片，旋转速度以每分钟转数（Rotations Per Minute, RPM）来测量。
• 扇区（sector）：将磁道划分成若干个弧段，每个弧段称为一个扇区。
• 磁道（track）：一个表面由磁道构成，是同心圆的结构。
• 磁头（disk head）：要从表面进行读写操作，需要一种机制，能感应磁盘上的磁性数据，读写操作由磁头完成。
• 磁盘臂（disk arm）：每个表面都有一个磁头，磁头连接到单个磁盘臂，磁盘臂在表面移动，将磁头定位到期望的磁道上。

37.3 简单的磁盘驱动器

#### 单磁道延迟：旋转延迟

旋转延迟（rotation delay）：磁头移动的时间

寻道时间

寻道时间包括以下阶段：

1. 磁盘臂移动时的加速阶段
2. 随着磁盘臂全速移动而惯性移动
3. 随着磁盘臂减速，最后磁道在正确的磁道上停下来，停放时间通常不小，例如0.5 ~ 2ms。

其他细节

• 磁道偏斜（track skew）：确保即使在跨越磁道边界时，顺序读取也能方便地服务。

• 多区域（multi-zoned）：外圈磁道比内圈磁道具有更多扇区，磁盘被组织成多个区域，区域是表面上连续的一组磁道。每个区域每个磁道具有相同的扇区数量。

• 磁道缓冲区（track buffer）：少量的内存空间，通常大小位8MB或16MB。例如：从磁盘读取扇区时，驱动器可能决定读取该磁道上的所有扇区并将其缓存在其驱动器上，这样可以让驱动器快速响应所有后续的同一磁道的请求。

写入操作分为以下几种：

• 后写（write back）：将数据放入内存中，在一段时间后写入。
• 直写（write through）：直接写入磁盘。

37.4 I/O时间

\[T_{I/O} = T_{寻道} + T_{旋转}$ + T_{传输}\]

37.5 磁盘调度

SSTF：最短寻道时间优先

会导致饥饿问题，距离长的始终无法调度。

SCAN电梯算法

SPTF：最短定位时间优先

Chapter 38 RAID

Q：如何构建大型、快速、可靠的存储系统？

RAID（Redundant Array of Inexpensive Disks）：廉价冗余磁盘阵列。

从外部看：RAID看起来像一个磁盘：一组可以读取或写入的块。

在内部：RAID是由多个磁盘、内存以及多个处理器来管理系统，更像一个计算机系统，专门管理一组磁盘。

RAID优点：

• 性能高：并行使用多个磁盘可以大大加快I/O时间
• 容量大
• 可靠性：RAID通过redundancy，可以增加数据可靠性。
• 透明部署：向系统添加新功能时，不需要对其余部分进行修改

38.1 接口和RAID内部

提供接口给上层调用。

RAID内部包括一个微控制器，运行固件以指导RAID的操作。某些情况下，还包括非易失性存储器，安全地缓冲写入。

38.2 故障模型

• fail-stop：故障停止模型，在这种模式下，磁盘可以处于两种状态之一：工作状态或故障状态，使用工作状态的磁盘时，所有块都可以读写，相反，磁盘出现故障时，将不提供服务。

38.3 如何评估RAID

三个方面：

1. 容量
2. 可靠性
3. 性能

38.4 RAID 0：条带化

实际上不是RAID级别，因为没有冗余。

基本思想：以轮转方式将磁盘阵列的块分布在磁盘上。目的是对数组的连续块请求时，从阵列中获得最大的并行性。将同一行中的块称为条带。

RAID映射问题：给定一个逻辑块地址A，RAID如何确定物理磁盘和偏移量？

使用一些映射关系进行计算。

大块大小

大块大小影响针列地性能，大小较小的大块意味着许多文件将多个磁盘进行条带化，从而增加了对单个文件的读取和写入的并行性。但是，跨多个磁盘访问块的定位时间会增加。因为整个请求的定位时间由所有驱动器上请求的最大定位时间决定。

38.5 RAID 1：镜像

只需要生成系统中每个块的多个副本。

一致性更新问题：可以通过预写日志解决，首先记录RAID简要执行的操作，采用这种办法，可以在发生崩溃时，通过运行恢复程序，将数据恢复到最新状态。

38.6 RAID 4：通过奇偶校验节省空间

对于每一条数据，都添加一个奇偶校验（parity）块，用于存储该条块的冗余信息。

为了计算奇偶性，需要使用一个数学函数，可以使用XOR。

存在小写入问题（small-write problem），导致性能下降。

38.7 RAID 5：旋转奇偶校验

为了解决小写入问题，推出了RAID-5。RAID-5的工作原理与RAID-4几乎完全相同，只是RAID-5将奇偶校验块跨驱动器旋转。

Chapter 39 文件和目录

Q：OS如何管理持久设备？

39.1 文件和目录

存储虚拟化形成了两个关键的抽象：

• 文件：线性字节数组，每个文件都有一个low-level name。通常这个name被称为inode number。
• 目录：也存在inode number，包括一个(用户可读名字,low-level name)键值对列表

39.2 文件系统接口

创建文件

int fd = open(const char * pathname, int flags);

flags部分含义如下：

• O_CREAT：创建文件
• O_WRONLY：以只读方式打开文件
• O_WRONLY：以只写方式打开文件

39.4 读写文件

ssize_t write (int fd, const void * buf, size_t count);

write()会把buf所指的内存写入count个字节到参数fd所指的文件内. 当然, 文件读写位置也会随之移动。

返回值：如果顺利write()会返回实际写入的字节数. 当有错误发生时则返回-1, 错误代码存入errno中.

ssize_t read(int fd, void * buf, size_t count);

read()会把参数fd 所指的文件传送count 个字节到buf 指针所指的内存中. 若参数count 为0, 则read()不会有作用并返回0. 返回值为实际读取到的字节数, 如果返回0, 表示已到达文件尾或是无可读取的数据,此外文件读写位置会随读取到的字节移动。

39.6 fsync()

当程序调用write()时，只是将数据写入内存缓冲区中，等过一段时间写入存储设备。可以调用fsync()以确保立即强制写入磁盘。

39.7 文件重命名

int rename(char * oldname, char * newname);

39.8 获取文件信息

这些信息通常称为metadata，通过stat()或fstat()系统调用完成。

int stat(const char * file_name, struct stat *buf);

stat结构体如下：

struct stat
{
    dev_t st_dev; //device 文件的设备编号
    ino_t st_ino; //inode 文件的i-node
    mode_t st_mode; //protection 文件的类型和存取的权限
    nlink_t st_nlink; //number of hard links 连到该文件的硬连接数目, 刚建立的文件值为1.
    uid_t st_uid; //user ID of owner 文件所有者的用户识别码
    gid_t st_gid; //group ID of owner 文件所有者的组识别码
    dev_t st_rdev; //device type 若此文件为装置设备文件, 则为其设备编号
    off_t st_size; //total size, in bytes 文件大小, 以字节计算
    unsigned long st_blksize; //blocksize for filesystem I/O 文件系统的I/O 缓冲区大小.
    unsigned long st_blocks; //number of blocks allocated 占用文件区块的个数, 每一区块大小为512 个字节.
    time_t st_atime; //time of lastaccess 文件最近一次被存取或被执行的时间, 一般只有在用mknod、utime、read、write 与tructate 时改变.
    time_t st_mtime; //time of last modification 文件最后一次被修改的时间, 一般只有在用mknod、utime 和write 时才会改变
    time_t st_ctime; //time of last change i-node 最近一次被更改的时间, 此参数会在文件所有者、组、权限被更改时更新
};

39.9 删除文件

int unlink(const char * pathname);

39.10 创建目录

int mkdir(const char *pathname, mode_t mode);

39.13 硬链接

link()系统调用，在创建链接的目录中创建了另一个名称，并将其指向原有的文件的inode number。

39.14 符号链接

也称为软链接，硬链接有些局限：不能创建目录的硬链接（担心会在目录树中创建一个环），不能硬链接到其他磁盘分区中的文件（inode在文件系统中唯一，不能跨文件系统）

符号链接实际上与硬链接完全不同，其本身实际上是一个不同类型的文件。符号链接指向文件的路径作为链接文件的数据。

Chapter 40 文件系统实现

Q：如何构建一个简单的文件系统？磁盘上需要什么结构？

40.1 思考方式

• 文件系统的结构：文件系统在磁盘上使用哪些类型的结构来组织数据和元数据。
• 访问方法：如何将进程发出的调用映射到它的结构上。

40.2 整体组织

首先将磁盘分成一系列的块，每块大小4KB，在N个4KB的块中，分出大部分空间存储用户数据，这部分被称为data region。还有一部分磁盘空间需要存放元数据，这部分被称为inode table。

还需要一些空间记录inode或者数据块是空闲还是已分配。可以使用空闲列表（free list），或者使用位图（bitmap）。

还需要一块留给superblock，其中包含一些特定的文件系统信息，包括文件系统中有多少个inode和数据块、inode表的开始位置。

40.3 文件组织：inode

inode用于保存元数据结构，例如其长度、权限以及其组成块的位置。每个inode都由一个数字隐式引用。

inode表大小为20KB，由80个inode组成。每个inode大小为256 bytes。

要读取inode 32，文件系统首先计算inode区域的偏移量（32 * inode大小 = 8192），将其加商inode表的起始地址（inodeStartAddr = 12KB） ，从而可以得到希望的inode块的正确地址。

inode块的扇区地址iaddr可以计算如下：

blk = (inumber * sizeof(inode_t)) / blockSize;
sector = ((blk * blockSize) + inodeStartAddr) / sectorSize;

多级索引

为了支持更大的文件，文件系统的设计者必须在inode中引入不同的结构，一种常见的思路是用一个称为间接指针，它指向包含更多指针的块，每个指针再指向用户数据。

40.4 目录组织

目录基本上只包含一个二元组(条目名称, inode号)。但是线性存储不是存储这些信息的唯一方法，任何数据结构都可以，XFS使用B树存储目录。

40.5 空闲空间管理

文件系统需要记录哪些inode和数据块是空闲的，哪些不是。当创建一个文件时，需要为该文件分配一个inode，文件系统将通过位图搜索一个空闲的内容，将其分配给文件，文件系统将inode标记为已使用。

40.6 访问路径：读取和写入

从磁盘读取文件

发出open("/foo/bar", O_RDONLY)调用时，文件系统首先需要找到文件bar的inode，从而获得文件的基本信息，通过遍历路径名查找。从根目录开始遍历。找到inode后，读取包含foo的inode以及目录数据的块，最后找到bar的inode号，通过open()系统调用将该inode读入内存。打开后，通过read()系统调用，从文件中读取。

写入磁盘

写入文件是一个类似的过程，首先文件必须打开，然后通过write()系统调用以新内容更新文件，最后关闭文件。

写入文件可能会分配一个块，当写入一个新文件时，不仅需要将数据写入磁盘，还需要决定将哪个块分配给文件，从而相应地更新磁盘的其他结构。每次更新会导致五个I/O，分别是：

• 读取数据位图，然后更新以标记新分配的块被使用
• 一个写入位图（将新状态存入磁盘）
• 两次读取，然后写入inode
• 最后一次写入真正的数据块本身

Q：如何降低文件系统I/O成本？

40.7 缓存和缓冲

大多数文件系统使用DRAM来缓存重要的块。

早期文件系统引入一个固定大小的缓存来保存常用的块。然而静态的内存划分可能导致浪费。

现代系统采用动态划分方法，具体来说，许多现代操作系统将虚拟内存页面和文件系统集成到统一页面缓存中（unified page cache）通过这种方式，可以在虚拟内存和文件系统中更灵活的分配内存。

Chapter 44 数据完整性和保护

Q：系统如何确保数据完整性？

44.1 磁盘故障模式

分为两种类型：

• 潜在扇区错误（latent-sector errors , LSE）
• 块讹误（block corruption）

当扇区以某种方式发生block corruption时，会出现LSE。例如磁头由于某种原因接触到表面（磁头碰撞，head crash），则会使得数据位不可读。

驱动器会使用Error Correcting Code来确定磁盘位是否良好，会修复错误位。

44.2 处理潜在的扇区错误

Q：如何处理潜在的扇区错误？

如果存储系统尝试访问块，并且磁盘块返回错误时，需要用它的冗余机制来返回正确数据。

但是，LSE的增长影响了RAID的设计。当全盘故障核LSE接连发生时，RAID-4/5会尝试读取奇偶校验组中的所有磁盘，并重新计算缺失值，来重建磁盘。

44.3 检查讹误：校验和

Q：如何检测出现了讹误？

现代存储系统用于保持数据完整性的主要机制称为校验和（checksum），校验和是一个函数的结果。该函数以一块数据作为输入，输出数据内容的概要（4字节或8字节），此摘要称为校验和。

通过将数据和校验和一起存储，然后再访问时确定数据是否被破坏或改变。

44.5 错误的写入

错误位置的写入（misdirected write）：写入位置出错。

Q：如何解决错误的写入？

在每个校验和中添加更多的信息，例如：添加物理ID。

44.6 丢失的写入

丢失写入（lost write）：实际上没写入。

Q：如何处理丢失写入？

执行写入验证（write verify），或者写入后读取验证（read-after-write）。

44.7 擦净

校验和何时得到实际检查？

大多数数据很少访问，因此将保持未检查状态。未检查的数据对于可靠的存储系统是一个问题，因为数据位衰减最终可能影响特定数据的副本。

为了解决这个问题，许多系统利用各种形式的磁盘擦净（disk scrubbing），定期去读取系统的每个块，并检查校验和是否有效。

44.8 校验和的开销

空间开销：

• 磁盘本身需要存储校验和

时间开销：

• CPU需要计算每个块的校验和，存储/访问时都需要计算。

Chapter 47 分布式系统

Q：如何构建在出现故障时仍能工作的系统？

其他问题：

• 系统性能
• 安全

47.1 通信基础

丢包是网络的基本现象。问题：如何处理丢包？

47.5 RPC

RPC是分布式系统中的通信方式。

RPC系统分成两部分：

• stub generator/protocol compiler
  • 通过自动化，简化将函数参数和结果打包成消息的过程。
  • 优化代码，提高性能。
• runtime library

interface {
	int func1(int arg1);
	int func2(int arg1, int arg2);
}

stub generator

stub generator接收接口，并生成不同的代码片段，对于client，生成client stub，其中包含接口中的每个函数。希望使用此RPC服务的客户端程序将链接此client stub，调用它进行RPC。

在内部，client stub中每个函数都执行RPC的核心业务代码。主要分为以下步骤：

1. 创建消息缓冲区。
2. 将所需信息打包到消息缓冲区中。包括函数名，参数。也称为消息的序列化。
3. 将消息发送到目标RPC服务器。，与RPC服务器的通信，由RPC的runtime library处理。
4. 等待回复。
5. 解包返回代码和其他参数。也称为反序列化。
6. 返回给调用者。

其它问题：

• 复杂参数如何封装
• 并发编程

runtime library

首要挑战：如何找到远程服务？

建立命名系统，存储对应的RPC服务名称和主机IP地址、端口等。

下一个问题：选择TCP/UDP传输协议？

根据系统功能做抉择。

其他问题

• 超时机制
• 大参数的过程调用
• 字节序，有些机器使用大端序，有些机器使用小端序。
• 异步同步问题