OSTEP笔记3–持久化存储

大部分截图来自原书,贴出书的官方主页: 《Operating Systems: Three Easy Pieces
(作者Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau)。感谢原作者这么好的书。

本篇笔记是书的第三部分(Persistence),讲述了操作系统和外存系统相关的内容。

第一节 I/O Device

1.1 IO 总线

一般情况下, IO设备的性能较差(慢),所以用Peripheral IO Bus,为什么不用像显卡一样用的PCI呢?因为1)越快的总线越短,这样空间不够插;2)越快的总线制作成本越高,如果存储设备照总线的性能差的远,没必要用高性能总线。

这张图为总线的层次结构,memory bus是最快的也是最近的,IO Bus比较远,也是最慢的,中间有用于显卡的PCI等总线。

1.2 典型设备的组成部分

一个典型的外围设备如图所示,包括两部分: 接口内部结构

接口: 类似软件接口的功能,硬件接口是留给OS和设备交互的。
内部结构: 比如㓟CPU、MEM等基本组件,还有称为固件(firmware)的软件来实现内部功能。

1.3 两种IO模式(Polling和Interrupt)

Polling的形式,而interrupt。

一种典型的协议是 Polling (轮询),称为programmed IO,步骤有4:

  • 循环等待STATUS寄存器直到设备状态为不busy
  • 写数据到DATA寄存器
  • 写命令到COMMAND寄存器
  • 循环等待STATUS直到设备为不busy

Polling显著的缺点就是太浪费CPU时间,这是因为IO相对于CPU是很慢的,大量的CPU时间被用在了等待上。

Interrupt (中断)方法(也称为interrupt-handling IO)可以解决这个问题,用Interrupt方法进行IO时,当设备完成操作时,会raise一个硬件interrupt。但是这样的话,如果设备很快(比如现在的NVMe SSD设备),Interrupt由于需要进程上下文的切换、以及中断的控制等原因,会拖慢IO的速度。所以两种方法各有利弊:

Polling Interrupt
浪费CPU时间 节省CPU时间
更小的I/O延迟 进程切换及中断处理导致高延迟

在IO请求压力时大时小不好确定的系统中,更好的方案可能是采用hybrid(混合)的 两段协议 ,先poll一会儿,还没完成的话改用interrupt方式。还有一种方式是 中断合并 ,当一个请求完成,等一等,说不定又有新的请求完成了,这样就见小了中断数,减小了中断带来的性能损失,但是这样做的缺点也是显而易见的–用延迟代价换来了高吞吐。

 

1.4 传输任务的卸载(Direct Memory Access, DMA)

若不使用DMA,虽然可以用中断来讲等待设备IO完成的时间用在其他进程上,但是IO请求中还包括CPU从内存到设备以字长为单位一点一点搬运数据(数据传输)的过程,如图:

有了DMA这种专用设备帮CPU搬运,流水线就可以入下图一样:

当DMA完成任务,DMA控制器会raise一个中断,这样OS就知道传输完成了。

1.5 OS和设备的交互:PMIO和MMIO

以上的方法中CPU和设备的通信一般都可以用Port-mapped I/O(PMIO)的方式,这种方式是CPU通过指令和设备通过port进行的IN/OUT指令的通信。

还有一种称为Memory-mapped I/O(MMIO),这种方法中,设备寄存器被映射到内存地址空间,OS读写这个映射地址,硬件会自动将存取数据路由到设备而不是主存中,这时命令是LOAD/STORE。

1.6 设备驱动和I/O栈

I/O栈各层的抽象(如块设备驱动、文件系统等)当然有好处,其把不同的设备封装成统一的结构,但也有坏处。

其实不是从上层应用到底层驱动会出现信息丢失的问题(我曾经调研过上层到下层会有语义鸿沟的问题),底层的设备由于统一的抽象也会“丧失个性”,比如SCSI支持多种IO错误信息,但是ATA/IDE却不支持,因此Linux设计成上层文件系统只能接到更”EIO”错误(generic IO errer)。

驱动占Linux源码的70%,很多驱动都是“业余”开发的,因此很多系统崩溃也是由于驱动bug造成的。

第三节 RAID

书中有个对比表总结的不错:

第四节 文件和目录

文件(file)和目录(directory)是OS虚拟化中存储部分的两个重要的抽象概念。

本节主要解释一些基本的文件操作和对应的系统调用。比如:

常用操作 系统调用
cat命令 open() / read() / write()
数据同步 fsync()
mv命令重命名 rename()
ls的-l参数、stat命令 stat() / fstat()
rm命令 unlink()
mkdir命令 mkdir()
文件夹操作函数 opendir() / closedir() / readdir()
rmdir命令 rmdir()

这节还讲了硬链接和软连接、创建和挂载文件系统的内容,略了。。

第五节 文件系统的实现

本节主要讲,要实现一个文件系统的基本功能上应该怎么实现。

5.1 文件系统的根本

对于文件系统,我们头脑中应该有一种模型:文件系统(Filesystem, FS)由接入部分和基本数据结构部分组成。前者指的是read()、write()等这样的接口;后者关系到FS内部怎么组织存储用户数据和元数据。设计时,不同的文件系统一般都有相同的接口,不同FS的主要区别是内部的 数据结构

5.2 整体结构

文件系统内的数据可以分为用户数据(data)和元数据(metadata),元数据可以简单的理解为数据的数据。上节所讲的文件系统的两种重要抽象(文件和目录),都需要存储data和metadata。

data:
* 文件的data自然是用户数据,我们不需要关注用户数据的具体内容;目录的data应该存储文件名和对应文件的metadata。

metadata:

  • inode 文件的metadata是inode(曾经是index node的缩写)或者类似inode但不叫inode的东西;目录的metadata也是inode。inode以某种结构存储有对应文件或目录的数据块地址。
  • bitmap(或free list) 是与整个文件系统空闲空间相关的metadata,FS需要分配新空间时,会从这里查询哪里有空闲位置。分为data的bitmap和inode的bitmap。这里的bitmap也可以换为使用free list其他的数据结构。可以说,bitmap是metadata(文件和目录的inode)的metadata和data(文件和目录的data)的metadata,不过也还是metadata。。。
  • superblock 记录有文件系统最大inode数、inode块和数据块从哪个地址开始等信息,是整个文件系统的metadata。

5.3 Inode

组成: 每个inode都有一个inumber,由于inode是顺序排列的,给定inode table开始块的地址、inode的大小和inumber就可以知道这个inode在哪个块了。inode中包含的信息包括:type(一般文件还是目录)、size(文件大小)、各种时间信息、指向数据块的地址“指针”(索引)等。

数据块地址索引: 其中的地址“指针”可以分为两类,最简单的直接指向相关的data块,称为direct pointer;另一种更常应用的交indirect pointer。

为什么要用indirect呢?因为一个inode的空间是有限的,如果文件数据太大,inode中留给存储块地址的空间装不下。于是就有了间接的两层索引、三层索引这种结构。例如,三级索引中,总共inode有n个地址空间有a个直接索引,b个二级间接索引,c个三级间接索引,那么有n=a+b+c;如果设一个数据块可以存m个索引,块的大小为4KB,支持文件的最大大小为4KB * (a + b * m + c * m * m)

显然,这个多级索引结构是个非平衡树,也是不对称的,看了让人挺难受(强迫症),为什么这样设计呢?这是出于多数文件都很小的事实。

FAT的链式存储: FAT等FS没有inode,而是只存储第一个数据块的地址(类似链表头),然后下一个块的地址可以去前一个块找。这只是道理上的,如果真的这么做,随机访问肯定超级慢,所以还内存中存在一种存有连接信息的表,(可以看成key-value形式,用块的地址作为key,用下一个块作为value),这样就可以在内存中完成“链表的遍历”,加速了这种思路。这种结构的缺陷之一是无法创建硬链接。

书的作者给出了几种事实对设计FS很有借鉴意义:

事实 数据
多数文件都很小 多数都在2KB左右
平均大小会大一些 200KB左右
大多数数据都在大文件中 少数的大文件占据了大部分的空间
文件系统有很多文件 平均接近100k个
文件系统一般都是没满的 即使磁盘空间在变大,还是有50%空间空闲
目录一般都很小 平均小于20个项

5.4 目录的组织

在作者的例子中,目录和文件是类似的,都有inode,只不过目录的data中有文件名和文件inode地址的映射,这是一种类似线性链表的结构,所以目录如果深的话查找开销会比较大。

目录的组织是对数据结构的一种设计和选择,当然也可以有不同的选择,比如XFS就采用了B-tree作为目录的存储组织结构(这样在创建文件时也很容易确定是不是重名)。

5.5 空闲空间的管理

和目录的组织一样,作者的例子用了bitmap,但还可以用free list链表形式或者B-tree(XFS)等很多形式进行管理,这将导致性能和空间的trade-off。

当使用空闲空间时,尽量将连续的空间分配给需要的文件,这样的启发式方法会增加文件读写的速度(请求次数更少、一次顺序读写更多)。

5.6 read()和write()的过程

作者的例子中,一次读或写请求会导致多次IO。尤其对于写时不存在的文件进行creat操作时,需要更多的IO,因为要逐级更改上层目录data和inode等。读和创建文件的操作如下两图:

5.7 缓存和缓冲区(caching and buffering)

现代系统一般将virtual memory pages和文件系统pages合并成统一的page cache(unified page cache),这样内存可以被更灵活的在虚拟内存和文件系统间分配(?)。

write buffering是有好处的,等一等再往下存,可以batch一些请求或者减少请求(如创建后马上删除),现在的文件系统一般都会等5s或30s之类的。这样做是有trade-off的:增加了延迟,增加了系统crash时数据丢失的可能。DBMS等系统决不允许这样导致数据丢失,因此可以勤用fsync()同步、用direct I/O绕过缓存或用raw disk接口绕过文件系统。但是一般这种trade-off在作者看来是可以接受。

第六节 局部性和FFS(Fast File System)

本节主要讲了FFS,一种84年提出的Unix文件系统,ext2和ext3的前辈。

在FFS之前,磁盘的性能很差,主要是因为人们没有考虑底层磁盘的特性,把磁盘当成了一个随机存储设备。例如,相对更古老Unix FS中的碎片没有被适当的处理,越来越碎,性能越来越差;而且块太小只有一个扇区的大小,这会导致开销增大(传输一次的量太小了)。

措施1:分组存储

将整个文件系统分成Cylinder Group,每个Group都类似一个文件系统,甚至有冗余的Superblock。ext2和ext3中把这种结构称为block group。

这样存储就可以实现一些策略,这些“启发式”的策略并不是通过详细的论证得到,都是基于经验的,也是很管用的:1)将相关的文件(如同一个文件夹中的文件)放到一个组中(空间局部性,虽然FFS考虑了空间局部性,但没有考虑时间局部性,比如编译文件夹和源码文件夹在相距很远的两个目录里,就可能导致反复的查询);2)创建文件时平均让各个组的空余inode数平衡等。

措施2:大文件的分组存储

大的文件如果大到占了一个组的大部分,就开始破坏组内的局部性了,因为很少有地方可以存相关的文件了。因此可以根据预先设定,一个组内一个文件最多存多少块,如果多于这个数,就把一个文件分在多个组中存。

这样固然会降低存储效率,但是降低的应该不多,因为即使分块了,大文件的每个块依然较大,一次还是可以传输较多的数据,这样,传输所占的时间还是远大于请求所占的时间。这也是可以用数学公式计算一下比例的(摊还分析),作者在书中进行了推导,要达到50%的带宽,一个块400K即可,要达到99%的带宽,一个块需要40MB。(当然这只是针对磁盘,现在的高性能设备就不一定了!)

作者还讨论了HDD中顺序请求也可能让磁头旋转可能过头的问题。解决方法如图,具体解释,略。。。

第七节 FSCK和Journaling

7.1 Crash Consistency

FS的数据结构和其他内存中的数据结构不同,必须持久化存储。但是由于一次写请求是必定引起多次的磁盘IO(比如,要更新一个文件,需要更新或添加数据块、更新inode信息、可能更新bitmap块等。),若在一次写请求的多次IO之间系统崩溃了(可能由于断电等原因),那么文件系统结构就可能出现不一致。作者将这个问题成为crash consistency问题,并假设一次写请求分解成了3次基本IO操作(更新数据块、更新inode块、更新bitmap块),总结了几种情况,总结如下表(F for finished, N for not finished):

数据块 inode块 bitmap块 一致性 备注
N N N 一致 相当于什么也没干,FS一致,虽然写没有成功
N N F 不一致(bitmap和实际占用空间) 若bitmap记录了分配了新空间,可能导致“空间泄露”(道理类似内存泄漏),
N F N 不一致(inode指针和实际存储位置) 这时inode指向了并未更新的数据块,后续的读操作会返回一堆“垃圾”数据
N F F 不一致 同上,可能读到“垃圾”数据
F N N 一致 虽然写请求没有成功,但因为bitmap和inode都没变,写入数据块只是相当于白写了,没有引起不一致
F N F 不一致 由于inode没有更新,可能读不到更新的数据块
F F N 不一致(bitmap空闲空间和实际所用空间) 未更新的bitmap可能导致再次申请时覆盖有效数据
F F F 一致 请求正常完成了

FSCK和Journaling是保证crash consistency的两种最基本、最广泛的方法。FSCK即File System ChKer, Journaling又可以叫logging,都是保证crash consistency的方法。这些保证只是说保证系统不发生错误,无法保证写请求的成功。(类似DBMS的事务,consistency就是一次事务要么完了,要么没发生过,不能发生一半)

7.2 FSCK

思路很简单,在每次FS挂载时,进行FSCK检查,进行必要的修复。 缺点是很慢,因为每次都要全局进行检查。 检查方法如下:

Superblock 检查超级块有没有异常,如果有异常,会启用备用超级块。

Bitmap 逐一检查inode和indirect块,生成一个记录分配情况的新bitmap,这样就不会有数据块和inode块与bitmap记录的不一致的问题。

Inode 检查有没有异常,比如标志位是不是有效,检查Inode的link count是不是正确,如果inode没有被任何目录指向,会放到lost+found文件夹;如果指向的块没有在有效范围,可能inode会被清除以保证一致性。

Data block 如果两个inode指向同一个块,会复制一份让两个inode各自拥有一份数据块;directory数据块会检查前两个是不是.和..目录,并且要保证每个inode没有在同一个目录被link两次。

7.3 Journaling

借鉴了DBMS的write-ahead logging的方法来改进FS的一致性,将恢复时间由O(size-of-disk-volumn)降低到O(size-of-the-log),ext3、ext4、XFS、JFS、NTFS等FS都用了这种方法。

可以分为两种:metadata journaling和full mode journaling。后者在更新磁盘区域时,会提前将所有新数据写到journal区域;而前者在FS journal区域只存储inode、bitmap等metadata,不存user data,因为节省bandwidth,更为常用。

7.3.1 full mode journaling

大概需要三步:

  1. Journal write: 在journal区域以一个TxB(Transaction Begin)标志开始讲需要journal的data、metadata写入。
  2. Journal commit: 在日志写好后写一个TxE(Transaction End)标志表示日志写结束了。
  3. Checkpoint: Checkpoint过程就是真正更新磁盘的过程。
  4. Free: 过一段时间后,需要更新journal的superblock,mark这次事务为free

如下图:

两个问题:

  1. 其中为了将a)和b)两次IO合成一次减少性能开销,可以在TxB和TxE中都写一下日志的校验和(checksum),这样恢复的时候就可以根据TxB的checksum和已经存储的检验日志的完整性了,这个方法是被作者的团队提出的,现在被用于 ext4 中。
  2. journal的区域是一定的,不能无限增长,所以采用了类似环形链表的数据结构存储log,只需要存储开始块和结束块的指针就可以了。
7.3.2. metadata journaling

User Data 和 Journal的提交顺序:

metadata journaling中,根据user data写盘的顺序,又可以分为ordered journaling和non-ordered journaling,前者保证先写user data到磁盘,再写metadata到日志,最后写metadata到磁盘;后者的区别不保证user data和metadata的顺序性,实际这不会造成什么问题。所以NTFS、XFS等FS都采用了non-ordered metadata journaling的方式保证一致性。

大概分为五步

  1. Data write
  2. Journal metadata write
  3. Journal commit
  4. Checkpoint metadata
  5. Free

这里,只是将journal的内容减少了user data。在ordered mode中,data要先写完再开始下一步;在non-ordered mode中,data write和其他步顺序无关,异步进行。如图,complete顺序和具体运行有关:

7.4 其他方法

除了1)fsck、2)journaling,还可以用其他的方法保证一致性。比如3)Soft Update[1][2],4)copy-on-write(COW)被用于ZFS,5)backpointer-based consistency(BBC),等等。


[1] M. Dong and H. Chen, “Soft Updates Made Simple and Fast on Non-volatile Memory,” Atc, 2017.

[2] M. McKusick and G. Ganger, “Soft updates: a technique for eliminating most synchronous writes in the fast filesystem,” ATEC ’99 Proc. Annu. Conf. USENIX Annu. Tech. Conf., 1999.

第八节 LFS(log-structured filesystem)

What does “level of indirection” mean in David Wheeler’s aphorism?
, https://stackoverflow.com/questions/18003544/what-does-level-of-indirection-mean-in-david-wheelers-aphorism

第九节 分布式系统简介、NFS和AFS

介绍了分布式系统很复杂,系统各部分的错误是无法消除的,需要使用各种手段保证系统正常运行。

分布式系统的问题包括性能、安全、通信等问题,本节主要谈通信问题。首先,通信本身就是不可靠的,在网络传输中,丢包不可避免。TCP能保证传输可靠性,但性能牺牲太大,UDP只提供了简单的checksum机制,需要分布式系统自己保证传输的可靠。比如,作者较详细地介绍了RPC(详见原文),其一般为了保证性能,用UDP而不用TCP。

作者在下两节分别介绍了NFS和AFS两种分布式文件系统。

9.1 Sun’s Network File System(NFS)协议

NFS由SUN公司开发,并没有被实现为一种特定的系统,而是指定了一种开方的协议(open protocol)。现在最新为v4版,作者重点介绍NFSv2。

首先,NFSv2被实现为一种无状态协议(stateless protocol),即每个客户端的单个操作都包含着完成请求所需的所有信息。其次,它应该兼容POSIX,来方便用户和应用使用。

NFSv2的关键概念是 file handle 。它包括3部分:volume identifier、inode number和generation number。volume ID用于指定请求的是哪个server,inode number指明了是哪个文件,而generation number用于重复使用一个inode number使对请求进行区分。协议如图:

9.2 The Andrew File System(AFS)协议

AFS用的不多了,其特色思路已经被最新的NFSv4引入,人们大多用NFS和CIFS等代替它。作者重点是讲其思路。AFS最初由CMU开发,版本1(ITC)和版本2之间有较大变革。

与NFS不同,AFS是以文件为单位进行下载和更新的,而NFS是以块为单位的。

AFSv1的协议如下:

9.3 NFS和AFS

两者性能对比表如下:

发表评论

电子邮件地址不会被公开。 必填项已用*标注