ICS2期末复习

持久化Ⅰ：IO和文件

IO设备

IO是持久化设备，可以加载程序、数据，保存状态，保存状态是CPU、Cache和RAM都无法做到的。

IO设备的层次结构

设备由近及远，速度由快到慢

内存Bus，一般IOBus，外围IOBus

IO设备的通用结构

状态、命令、数据

文件系统、通用块层、IO设备驱动都在内核态

磁盘调度

最短寻道时间优先(SSTF)：优先挑选在最近的轨道上的请求
- 饥饿
- 陷入局部最优，而达不到全局最优
电梯算法(SCAN和C-SCAN)
- F-SCAN：一个方向扫完之后才处理新来的请求
  - 避免饥饿
  - 新来的附近请求的处理效率低
- C-SCAN：从外到内移动磁头，移动到目前已有请求中最内道请求的位置，再置位到已有请求中最外道的位置。
  - 所有磁道更加公平，否则中间磁道访问的机会更多

闪存

写放大

擦除块前，先要将其中有效数据搬移到其他位置，产生了额外的写入量。

Flash翻译层(FTL)

地址映射

逻辑页 -> 物理页

内存可以通过闪存上的内容恢复

页(Page)级映射
- 占用内存空间较大
块(Block)级映射
- 节省空间
- 粒度粗，不方便。
混合映射：综合以上两者优点，多数(data table)采用块级映射，少数(log table)采用页级映射。
- 流程：先访问log table（用来记录新更新的pages）；不在其中的话，再找data table
混合映射的合并
- 为了减少内存开销，log table尽量通过合并操作转移到data table中
- switch merge：只需要切换block，开销是擦除一个block
- Partial merge: 把旧块中未修改的数据拷贝到新块中即可；开销是搬移pages + 擦除一个block
- Full merge: 其他情况；开销是搬移一个block的pages，擦除两个blocks

垃圾回收

回收invalid page占用空间

搬移合并后，擦除block

磨损平衡

静态：定期交换磨损最严重和最不严重的两个block中的数据

动态：实时观测磨损情况，尽量使用磨损小的block

Unix IO

内核提供的IO函数

所有的IO设备都被建模为文件

所有的输入输出都通过读写适当的文件来执行

打开文件

一个应用程序宣布它打算访问一个I/O设备时，内核获取相应的文件并返回一个小的非负整数，此后在对该文件的所有操作中都使用该整数标识该文件。

内核跟踪有关打开文件的所有信息，为每个打开的文件维护一个文件当前访问位置k，初始值为0。

应用程序只需要维护文件描述符，其他信息都在内核数据结构中。

一个应用程序可以通过seek操作，显式的设置文件的当前访问位置，read/write操作都从当前位置开始向后进行。

描述符表

每个进程有自己独立的描述符表，每个文件描述符是一个非负数字，作为文件描述符表的索引

0：标准输入（默认已打开）

1：标准输出（默认已打开）

2：标准错误（默认已打开）

其他打开的文件，从3开始编号

每个打开的文件描述符指向一个open file table中的一个
entry

File table

文件表由所有进程共享。每个文件表项包括：当前文件的读写位置、当前指向它的描述符项数的引用计数、指向v-node表项的指针。当文件表项的引用计数变为零时，内核删除该文件表项

V-node table

V-node表由所有进程共享

每个表项包含一个文件的大部分信息（文件访问权限，文件大小、文件类型等）

可能一个进程多个fd对应打开同一个打开的文件(如dup2)
可能多个进程对应同一个打开文件(如fork)
可能多个进程对应不同打开文件，但是同一个文件

关闭文件

内核释放打开文件时创建的数据结构

将该文件描述符重新放入可用文件描述符池。

下一个文件打开时，会分配文件描述符池中最小的一个文件描述符

读写文件

将字节从文件复制到内存

从文件当前访问位置开始
如果从到文件末尾的总字节数小于，则触发end-of-file(EOF)
- 可以被应用程序检测到
- 在文件末尾没有显式的“EOF字符”

short count

读写传输的字节数少于应用程序请求

读时遇到EOF
从终端读文本行
读写网络套接字

读取文件元数据

硬链接

一个inode号对应多个文件名
同一个文件使用了多个别名
硬链接可由命令link或ln创建
文件有相同的inode及data block
只能对已存在的文件进行创建
不能交叉文件系统进行硬链接的创建
不能对目录进行创建，只可对文件创建
删除一个硬链接文件并不影响其他有相同inode号的文件

软链接

文件用户数据块中存放的内容是另一文件的路径名的指向，则该文件就是软连接
软链接就是一个普通文件，只是数据块内容有点特殊。
软链接有着自己的inode号以及用户数据块

共享文件和IO重定向

open两次同一个文件：open file table中的两个文件指向V-node table中的同一个文件。

父子进程间共享文件：父子进程的文件描述符指向open file table中的同一个文件。

int dup2(int oldfd, int newfd)：将描述符newfd重定向到描述符oldfd。

持久化Ⅱ：文件系统

Linux IO栈

VFS(Virtual File System)

很薄的一层；提供各种文件操作接口；屏蔽不同文件系统的细节，提供统一接口。

Page Cache

充分利用内存空闲空间，为慢速IO设备提供缓冲，提升性能

dirty数据定期写回磁盘

General Block Layer

将低层各种硬件抽象为块设备

读、写两种访问接口
最小访问粒度为扇区（sector>=512B）
Flash等新硬件有读/写/擦除三种操作，所以需要通过FTL层伪装为块设备，OS才能正确访问

关键的数据结构是bio，代表用户的I/O请求

每个bio是I/O设备上一段连续的数据，有大小的限制
包含磁盘数据地址（扇区）和对应的内存page地址（多个page不一定连续）

IO调度

Noop：没有排序，最简单（适合低层是SSD）
Deadline：
- 四个队列，其中两个分别处理正常 read 和 write，另外两个处理超时 read 和 write 的队列
- 正常队列：按扇区号排序，合并相邻的请求；假设新请求都在相邻的地址，那么可能有其他磁盘位置的 io 请求被饿死
- 超时 read 和 write 的队列：按请求创建时间排序，保证超时（达到最终期限时间）的队列中的请求会优先被处理，防止请求被饿死
CFQ（完全公平队列调度）
- 它为每个进程创建一个同步 IO 调度队列，并默认以时间片和请求数限定的方式分配 IO 资源，以此保证每个进程的 IO 资源占用是公平的

文件系统

Create Files
Reading and Write Files
Reading and Write Files Randomly
Writing Immediately
Renaming Files
Getting Information About Files
Removing Files
Making, Reading, and Deleting Directories
Hard Links
Symbolic Links

文件系统实现

VSFS(Very Simple File System)

假设硬件只有64个块，每个块4KB

暂时不考虑针对硬件特性的优化

Inode：文件的元数据，每个文件对应一个inode

i-number：每个inode都有一个隐式的编号，根据i-number能知道inode在磁盘上的准确位置

Inode Table：比文件小很多，假设每个inode 256B，占用5个block，共80个inode，最多支持80个文件

Bitmap：记录inode和data block是否被占用。Inode bitmap和Data bitmap

Superblock：文件系统的一些参数，例如有多少inode， data block，inode table的位置等

Multi-level index

12 direct pointer + 1 single indirect point + 1 double indirect pointer

Extent

Point + length(in blocks)

当一个文件包含很多连续的data blocks时，节省Inode空间

Linked-based approach

Inode只包含一个指针，指向第一个data block，data block最后增加一个指针，指向下一个data block

做random访问时性能很差，可以把这些指针先放到内存中来加速

目录组织

目录被当做文件，有自己的inode和data block

Inode的类型是directory，而不是regular file

空闲空间管理

Bitmap/freelist/B-tree

创建文件：

查找inode bitmap，找到一个free inode
分配该inode给这个文件，并标记已使用
修改bitmap
分配data block也是类似

优化技巧：对新文件，找到连续8个block，数据保持连续性(pre-allocation）

从磁盘读取文件

Open（“/foo/bar”, O_RDONLY)

从path到bar文件的inode：

根目录/的inode
根目录/的data，找到下级目录/foo的i-number
/foo的inode
/foo的data
/foo/bar的inode

Read：

读/foo/bar的inode
读/foo/bar的data
写/foo/bar的inode，更新last accessed time
更新in-memory open file table，offset

写入磁盘

根据路径寻找文件与读类似

分配inode, data blocks，更新bitmap

写一个文件产生5次I/O

Read data bitmap
Write the bitmap
Read inode
Write inode
Write data

文件系统的额外开销，尤其是小文件

优化

批处理写入，合并一些I/O（例如同一个inode的修改）

请求合并、磁盘调度，性能更好

课堂练习：

文件名不是文件的一部分

文件大小，文件数据，文件数据块的存储位置均是文件的一部分

快速文件系统

Block group

例如，8个block组成一个group，放入同一个group的files，访问起来会比较快，因为磁头移动很少。

每个group都包括super block，可以并发访问；也包括组内的inode bitmap, data bitmap, inode

文件的元数据和数据放在临近的位置，访问会比较快

例如修改/foo/bar.txt，除了修改bar.txt的数据和元数据，也要修改目录foo，放在同一个group中，磁头移动很少

如何放置文件到block group：把目录以及该目录下的文件放进同一个group

大文件异常

大文件不连续地放在一个group里，如果全放在一起，当前目录下后续创建的文件就没有空间了。而是分散到多个不同的group。就算磁头移动增多，但对于大文件，磁头移动后也会连续访问一段。

小文件问题

无法充分利用4KB的data block，空间浪费

解决：sub-block (512B)

先以sub-block为单位分配空间
文件空间如果增长超过2KB，则迁移到一个完整的block上
新的问题：额外的数据拷贝
- 解决：修改libc，缓冲写数据，再分配到4KB的块上

文件系统检查器和日志

连续2次写入高度关联的A和B，在中间发生crash，原子性问题。系统会进入一个矛盾状态。

解决方案：

FSCK：file system checker
Journaling：write-ahead log

文件系统检查器

扫描data，让元数据（inode和bitmap）保持一致

superblock

检查superblock看起来是否正常

free blocks

检查inode，indirect block，double indirect block，看数据在磁盘上如何分布。基于这些信息去纠正bitmap和inode bitmap

inode state

检查inode的每个域是否正常；如果错误纠正不了，就会删除inode，同时更新inode bitmap

inode links

不同的目录包括同一个文件(link)，扫描整个目录树，重新计算link count，纠正inode记录的linkcount；

如果一个文件不被任何一个目录包括，则放到
lost+found目录

Deduplicates

检查deduplicate pointers，两个不同的Inode指向同一个block；(recall hard/soft link)

检查Inode是不是bad，可能被清除；也可能复制一份data block，两个Inode各指向自己的block

Bad Blocks

检查block pointers是否有问题，指向内容是否越界

如果出界只是去掉bad pointers或indirect blocks

Directory Check

确保./和…/是每个目录最开始的两项，每一项都有
对应的inode，不会有目录被链接两次

问题

太慢了！
只能整盘扫描
例如只修改3个block，扫描整盘效率很低

写前日志

写数据之前，先写到log里面，描述要做什么。写完日志时commit（对用户承诺Write OK）

如果写日志过程中崩溃，那么就当没发生过，不会出现数据不一致或写一半的情况

如果写入数据过程中系统崩溃，在恢复时可以依据log的内容回滚，然后重新尝试

避免扫描整个磁盘，只需查看日志区（完成的日志会删除，所以日志区不大）

Welcome to KK's Blog!