日志结构的文件系统

最近时间临近期末考,还有一大堆其他的事情。好久都没有更新。这次更新也只是最近小班课的内容。等到暑假再更新更多有意思的东西吧。

在现代操作系统中,文件结构是不可缺少的一个重要组成部分,面向用户构建一个实用、安全、稳定的文件系统是任何一个操作系统需要完成的最基本的任务。
为了达成这一点,文件系统需要基于许多方面考虑:

  1. 为了实用性考虑,文件系统首先要支持目录结构,方便用户管理文件
  2. 为了安全性稳定性,尽管电脑断电也不应当造成严重的文件损坏
  3. 作为一个面向用户的系统,应当尽量体验,比如存储的速度
    基于以上种种考虑,日志结构的文件系统成为了一种优秀的选择。本文也将以这三点需求而对日志结构的文件系统(LFS)进行介绍。

快速的存储

LFS (Log-structured File System)是怎么样存储文件的呢?
LFS首先会对要存储的数据在内存中以“块”为单位进行缓存,达到一定数量之后,则把这些块合并成一个“段”而向磁盘的空闲区域进行统一的写入。
为什么要这样做?

原本的存储方式与弊端

首先我们要想到一个磁盘的存储原理:(等我写出来这篇博客的时候会在这里替换为链接)
当我们需要写入一个数据的时候,我们要找到它的位置(seek)。写入的时候如果时间不是连续的话,那么磁盘就会继续旋转,你必须等待它转回的时候才能在同样的位置继续写入,产生了旋转延迟。
那么就产生了两个缺点:

  1. 随机输入输出和序列输入输出的速度差别很大
  2. 磁盘搜索和旋转延迟的时间开销比较大

LFS如何解决这个问题

正如上文所说的,为了避免这些因为寻道非连续写入造成的时间开销,我们干脆直接把数据缓存起来,这样就可以连续写入了。
如果我们直接向硬盘空闲的地方写入,也就减少了寻道的开销。
由此也可以看出,从这个角度来说,LFS是一种针对磁盘优化的文件系统。(固态硬盘的存取原理是什么样的呢?或许以后会有一篇博客)
这个时候可能你会想到一个问题:那读取怎么办?
读取好像确实没有什么非常好的办法,而LFS好像也没对读取产生什么额外的优化,这是因为LFS本身就基于一种预设:

  1. 大部分的读取数据都缓存至内存了
  2. 大部分的磁盘操作都是写操作
    为什么会这样子呢?这就是计算机技术发展的体现,内存的成本变得比以前更低廉,也更庞大了。一个技术引入时的用途和后来的并不一定完全一样。想当初我们还用虚拟内存的方法把内存中的数据换到硬盘中以获得更大的内存空间,现在我们把硬盘中的数据换到内存中以加速数据的读取。
    所以,基于这种“假设”,我们的LFS基本只用考虑加速写操作的需求就可以了,读数据的操作可以通过提前缓存到内存来大幅提升速度。

安全稳定

所谓的安全稳定,用一句简单的话来说就是防掉电,或者说就是任何数据写入过程被中断的情况。
试想,如上文中所说,我们把要写入的数据缓存成一整段写入,如果写到半截就断电了,那么我们应该需要一种机制来告诉我们断电前我们在干什么吧?

在写入过程中引入“日志”

所以,在这里就正式引入了LFS名字中的“日志”了。这里使用了一种叫做日志的特殊文件,相当于是一次写入操作的元数据。
在进行写入数据之前,我们先往要写入的位置的起始处写下一个小巧的日志文件,里面记录了本次要写入的所有内容,以及一些为了安全性考虑的数据。
然后,我们就正式开始了数据的写入……
在数据全部写入完成之后,我们再写下一个日志文件作为结尾,这样就可以保证我们的本次写入安全无误了。

如果中途出现了掉电情况

此时,再出现掉电我们就不用再担心了。因为日志文件帮我们记录了本次数据写入的目标。我们中间这部分数据写入的时候被中断了,我们就可以知道写入并没有被完成,那么就可以通过日志文件以及已经写入的内容来决定如何处理。
比如,如果掉电造成了磁盘写入了两个垃圾块,里面的数据完全没有意义,那么就直接把它们删掉吧(还有之前的日志文件)。
如果掉电之前已经成功写完了一些数据块以及它们的索引,那就可以保留下来这部分,或许还能做到在断点处继续写入作业。

为什么要有结尾的日志

或许你会想到,为什么全部写完之后还要再写一个结尾的日志,难道这些东西不能一起写进去吗?不可以!
这个结尾的日志就相当于一个写入结束的保证机制,它必须在前面的内容全部写入完毕并且经过检查之后再写入。这就是安全性。
试想,如果我们直接把数据块和结尾的日志一起提交给硬盘发起一次IO请求,那好像结果也是一样的?
其实并不是。当我们把数据一块为单位交给磁盘的时候,在我们的现象之中,磁盘应该是按照顺序在磁盘中写入的,但其实可能是有一定先后顺序的,这个顺序由硬盘决定。比如它有可能先在尾巴的位置写入了结尾的日志,这个时候发生了掉电。结尾日志已经写下,但是前面的数据还没有写完,这个时候我们就无法察觉到错误的发生了。

如果写入日志文件的时候掉电了

奇怪的情况真的是层出不穷,听我说老兄,如果写入日志文件的时候掉电了,那我可要用靴子狠狠的踢电源的屁股!
玩笑归玩笑,如果真的发生了这种古怪的情况呢?
首先,日志文件的写入操作可以原子化吗?
原子化就是说让它变成一个完全不可分的操作,要么操作成功,要么完全没有操作,这可行吗?
那我们就需要知道硬盘写入的最小单位是多少,只要我们的日志文件小于这个大小,就可以视为一次原子化的写入了。以LFS的目标平台:机械硬盘(磁盘)来说,最小的存储单位是扇区,一个扇区的大小是514字节。
那这个大小还是比较小的,或许不能装得下一个日志文件。毕竟日志文件包含了如此多的东西:要写入的每一个块、它们的顺序、其他的元数据……我们不能把它当作一个原子化的写入。
那就要采取第二种方法了,其实也非常简单:加入一个结束符。
这个解决方法和在段的结尾加入一篇日志如此之相似,我们就不仔细讲解了。如果结束符没有被写入,说明日志文件根本就没有写完,那么我们直接把它清理掉就好了。

文件系统的结构

在讲完LFS的存取方法之后,就只剩下最后一个需求了,也是作为一个文件系统最基本的需求:我们如何管理器这些文件,并且给出一个目录结构呢?

inode

我们将引入一个称为inode的数据结构,作为对数据块的直接索引,我们通过它就可以找到想要的数据在哪里了。
实际上inode的内容是比较复杂的,包括了一系列所管理的块的元数据,还有指向他们的硬指针。为了便于管理和维护这种结构,还专门插入了一种叫做“bitmap”的数据结构,用于管理inode和块的填充情况。这个在这里就不详细说明了。
首先我们明确的一个问题就是:既然要查询Inode,我们的目的就一定是找到它管理的数据,所以我们就直接把inode和它管理的数据放到一起,便于硬盘的调度。
inode与数据

imap

但是我们怎么找到 inode 在哪里呢?
那应该是需要全盘扫描,但是这样操作就太慢了。所以我们要用另外一个东西去索引 inode,这就是Imap。在日常使用的时候,文件系统会把imap直接缓存到内存里,这样就可以高速获取到inode的位置。
与LFS之前的机制相同,imap的写入仍然是日志式的,防止掉电或者系统崩溃。

CR

但是我们怎么找到 imap 在哪里呢?
等等,似乎开始了一个套娃游戏。没错,虽然用把imap缓存到内存的方法可以解决开机的时候寻找inode的问题,但是我们现在似乎也需要全盘扫描出imap在哪里啊?虽然经过了这两级的索引,imap的数量应该已经比inode又少了一个数量级。
答案是再引入一个叫做CR的文件!不过我们的套娃游戏就此结束了,因为imap的数量级已经是个位数的CR文件能承受的了的了,LFS会生成两个一模一样的CR文件,索引了所有的imap,固定的放在磁盘的头部和尾部。套娃游戏结束!
所以再整理一下现在的LFS如何运行吧:开机之后,系统找到磁盘开头或结尾的CR,检查它的内容是否被破坏,然后把其中的imap缓存到内存之中。当我们发起一个读请求的时候,系统就可以从内存中的imap中找到对应的inode的位置,在磁盘中通过inode内部的信息再获取到数据块的具体位置,提取出数据。

CR写坏了怎么办?

这个问题就比较复杂了,如果处理不好也很危险。正是因为怕它写坏了,LFS才搞出来两个CR放在开头和结尾,按照一个严格的协议每次只写入其中一边,并且附带上时间戳。然后进行同步。这样如果写入遇到问题,那错误的地方就可以从对方身上获取,或者直接清除。

目录的实现

怎么实现给用户展现的目录结构呢?
其实,目录也是一种文件。它记录了这个界面下方有哪些文件。所以说,我们可以把它当作一个带有特殊标记的数据块,同样存储在inode之中。
下面展示了一个通过目录找到文件的例子:
首先通过imap找到了索引对应目录的inode,inode给出目录数据块的具体位置,我们从目录数据块取得了目录内某文件的具体信息,返回到imap寻找索引该文件的inode,再次通过inode找到该文件的数据块本身。

一些优化

硬盘写满了怎么办

我们知道,LFS是优先在硬盘空闲的地方写入的,而不是深入到每一个碎片里面去管理。那么如果写到了硬盘的结尾怎么办?
这个时候就要触发LFS的垃圾清理机制:

空间清理机制

回收日志的空间

首先,我们使用日志文件,是为了保护写入业务,防止它遭遇断电等特殊情况导致的文件损坏。但是在写入业务完全完成之后,日志文件也就没多大用了。那么我们就可以把它清理掉。
但是如果随写随清理的话,这样会有什么影响呢?可以设想一下,写入阶段,磁盘一定处于使用的高峰期,用户会希望写入的速度尽可能加快。这个时候如果我们在一部分写入业务完成之后,要额外抽调出磁盘资源去清理日志文件,就会对接下来的接入速度造成一定影响。
所以,我们在完成业务之后,可以直接给没用了的日志文件打上一个可清理的标记,而不是立刻清理。等到硬盘空闲的时候或者没有空间的时候,再把它们真的清理掉。

清理已经不可用的数据

我们知道LFS总是优先在空余的地方写入,那么旧的数据就先晾在一边不管了。等到需要清理的时候,可以轻易的通过数据对于inode的反向链接找到一个Inode,然后根据inode上面现在链接的目标或者是时间戳判断它是不是废弃的。inode的有效性同样可以通过imap判断。
而这样势必会产生大量的碎片化存储。LFS解决的方式是,直接把旧的数据全部提取出来。其中废弃掉的就直接清除掉,仍然有用的数据就整理成新的块和段落,重新写入磁盘,这样不但清理了旧数据,还解决了磁盘碎片化的问题。

文章创作不易,感兴趣的话请持续关注
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇