Modern OS & OS Concept -文件系统（file system）

1.背景

所有应用有存取信息的需求。存取信息的第一个问题是，进程运行的时候，它能存储有限数量的信息于它自己的地址空间中，这个存储的容量受限于虚拟地址空间的大小。但是对于某些应用来说远远不够。
第二个问题是保存进程地址空间的信息：进程正常运行结束后，保存在进程地址空间的信息会丢失。进程有些信息需要长久保存，甚至由于计算机崩溃而杀死进程，这个信息也不能丢失。
第三个问题，多个进程能同时访问这个信息。如果信息存在进程的地址空间，只有这个进程能访问。需要解决这个问题让信息本身独立于任何一个进程。
因此，对于长期信息存储，有三个必不可少的的要求：

• 必须能存大量的信息；
• 使用信息的进程终结后，信息还能存活；
• 多个进程能同时访问信息。

磁盘

• 一直以来用于长期存储，近些年SSD日益流行起来。
• 可以看作是一个线性的块序列，每个块大小固定；
• 支持两个操作：
  i)读block 号为K 的block；
  ii)写block 号为k的block。

但这些操作方式在大型的有需要应用程序和需要用户使用的系统中，都极其不方便。几个关键问题：

• 如何找到信息？
• 怎么防止一个用户访问另一个用户的信息？
• 如何知道磁盘的哪些block 是空闲的？

正如OS 从处理器概念抽象创建进程，从物理内存概念抽象出提供进程虚拟地址空间一样。OS 解决这个问题采用一种新的抽象：文件。进程，地址空间，文件是OS最重要的概念。

进程创建文件,磁盘上存放大量文件；
OS（文件系统）负责管理文件；

• 结构化文件；
• 命名；
• 保护文件；
• 文件系统视角：
  • 用户视角：用户如何命名文件，组织文件
  • 实现视角：文件是如何在磁盘中组织的

2.用户视角

2.1 文件命名

• 所有OS 都用1～8个字母；
• 用后缀作为名字的一部分；

2.2 文件结构

image.png

字节序列

• 最灵活，可以放任何内容

• UNIX和 windows采用这种

固定长度的记录

• 一个文件有一系列的记录组成；

• 每个记录有内部的结构

• 读操作返回一条记录，写操作则覆盖或追缴一条记录

• 现代OS 不在使用这种；

树形结构

• 文件有一个记录树组成，每个记录不必同样长度；
• 在记录的固定位置有key；
• 树按key 排序
• 可通过key 来查找记录；

2.3 文件类型

• 普通文件-包含用户信息
• 字符特殊的文件
• 块特殊文件-磁盘

2.4 文件属性-metadata

文件除了名字和文件中的数据外，还有相关其他的信息，文件属性。

image.png

2.5文件操作

create,delete,open,close,read,write,oppend,seek,get attributes,set attributes,rename

2.7 目录

层级结构

• 一级目录系统

  
  image.png

• 层级目录系统

  
  image.png

目录操作

create. delete, opendir, closedir, readdir, rename, link, unlink

3.文件系统实现

用户关心文件命名，可以对文件进行的操作，目录树长什么样及对目录的操作。文件系统的实现则关心文件和目录如何存储，磁盘恐怕如何管理，如何让每件事情工作得高效可靠。

3.1 文件系统layout

• 文件系统存储在磁盘上；

• 磁盘可分成一个或多个分区，每个分区有单独的文件系统；

  • MBR
    1）磁盘 sector 0
    2）用于引导启动计算机
    3）MBR的最后一部分是分区表;
    分区表记录每个分区的起始，结束地址;
    表中的其中一个分区会Mark成active状态；
    引导计算机时，BIOS会读并执行MBR，然后MBR会首先定位active 分区，然后执行该active分区的第一个block ,即boot block，然后执行它；
  • Boot block
    1）负责装载包含在该分区的OS；
    2）每个分区包含一个boot block, 即使它不包含可引导的OS
  • super block
    1）包含文件系统的所有关键参数
    magic number;
    文件系统的block 数量；
    其他关键管理信息
    2）计算机启动或者首次使用文件系统的时候会读进内存中

• 空闲空间管理
  以bitmap或者链表指针的形式

• inode 表
  每个文件一个inode, 描述该文件的所有信息

• 根目录
  包含文件系统树的根部

• 文件和目录

  
  image.png

3.2 文件的实现

• 连续分配
  优点：
  易于实现：只需要记录第一个block号,block 数
  读性能好，只需要一次寻道操作
  缺点：
  随着时间前进，磁盘空间会出现碎片化
  文件创建时需要知道文件大小；
  外部碎片化，需要压缩空间，开销大
  image.png

image.png

• 链表分配

  1. 每个文件以链表的方式将block联系起来存储
  2. 每个block的第一个dword指向下一个block
  3. 最后一个block的第一个dword指向0；
  4. 没有外部碎片化；
  5. 随机读很慢：定位一个文件的第n个block,需要从0到第n-1 block 逐个读，一次读一个;

  6. 文件的每个block 有几个字节由指向下一个block的地址占用着，读文件数据需要将block直接的有效数据拼接在一起，有拷贝的开销；

     
     image.png
     image.png

• 使用内存中的表的链表分配

  1. 链表分配的缺点可通过将每个block的指针放在内存中和放在一个内存的表（FAT）中消除；
  2. 将指针放在内存的表中；
  3. 随机访问会更快；

  4. 不适合大容量的磁盘：整个表必须一直在内存中，但会随着文件系统的容量增加而增大。

     
     image.png
     image.png
  • i-node
    1. 将指向数据block 的所有指针集合在一个地方，索引block；
    2. 每个文件有自己的索引block，包含一个元素是数据block的地址的数组;
    3. 用一个inode数据结构存放文件属性和block地址；
    4. 与使用内存中的表的链表分配相比，优势是，只有相应打开的文件的inode需要在内存中；
    5. k 个active 文件，每个inode占n(B),需要n*k(B) ;
    6. 支持小文件和大文件的机制：
       • 链式方案：
         i) 正常小文件只需要1个索引block 来存放文件的磁盘block 地址；
         ii) 为支持大文件，将多个索引block 链接在一起。如一个索引block 前面是100个数据block 地址，最后 一个地址为下一个索引block 的指针，对于小文件该值为NULL
       • 多级索引
         i) 大文件需要多个索引block，多级索引;
         ii) 第一级索引block 指向第二级索引block的集合;第二级索引block 指向文件数据block;
         iii) 可以类似有多级索引；

       • 链式索引和多级索引结合的方案：
         i) 基于UNIX 的文件系统采用的方案；
         ii) 文件inode中索引block 有15个指针；
         iii) 前12 个指针指向直接block，也就是数据block地址；（高达48KB 数据可以直接访问）
         ix)后面三个指针指向间接block；
         第一个指向single 间接block；
         第二个指向double间接block；
         第三个指向triple 间接block;

         
         image.png

image.png image.png

3.3 目录的实现

• 文件读之前，需要打开文件，文件打开OS使用文件名定位在磁盘的目录项；
• 目录项提供找到磁盘block 的信息；
  可使整个文件的磁盘地址信息（连续分配）
  or 第一个block 的地址号；（链表分配）
  or inode 号；

• 实现文件名字到定位文件数据的信息的映射；
  文件属性存在目录项里面；
  or 文件属性存在inode 中,目录项存inode号和文件名

  
  image.png
• 不同长度文件名处理
  固定文件头+变长文件名
  or 使用堆存放文件名，使用指针指向文件名
  image.png

3.4 日志结构文件系统（Log-structured FS）

• 动机
  1）磁盘cache 越来越快，多数读请求可通过文件系统cache；
  2）多数磁盘操作是小块的写，效率低
  3）写一个文件，目录inode，目录block,文件inode, 文件本身都必须写
• 优化写
  1）将整个磁盘当成一个大log；
  2）收集小size的写请求，定期的作为一个连续的segment写到磁盘log的最后；
  3）一个segment 可能包含inode, 目录block，数据block，所有都混合在一起；
  4）每个segment 的开始是一个segment summary, 对这个segment 内容的总结；
  5）可利用满带宽；
  6）inode 散落在整个log 中。而不是在磁盘的固定位置;
  7）inode map 定位inode
  inode号作为索引，得到的entry 指向inode 文件的inode;
  存在磁盘上;
  在内存中缓存起来用来定位inode;
  8）整理线程-垃圾回收，释放没有使用的空间；
  9）面对故障，很健壮；
  10）不兼容多数文件系统，不怎么使用

3.5 日志文件系统（Journaling FS）

在对文件系统的采取每一个动作前先记录一个日志，写到磁盘里，然后再执行这个动作 ，完成这个动作后，清除掉这个日志
系统崩溃发生在执行之前，可以重启后重新执行日志里的动作

4.文件系统管理和优化

4.1 磁盘空间管理

• 两种策略：分配连续的空间，分配不连续的空间
• 类似于内存空间管理，分段和分页
• 几乎所有文件系统将文件切分成多个固定大小的block,block 直接不必连续；
• 空闲block的管理
  • bitmap
    i）每个block 用1bit 表示
    若空闲，为1；
    若已分配，为0；
    2）CPU 提供位操作指令
    3）block 号计算 = 每个dw,bit的位数 * 为0的dw的个数 + 第一个为1的bit 的偏移
  • 链表
    1）将所有空闲block 链接在一起；
    2）将链表头指针放在文件系统特殊的位置，缓存在内存中；
    3）不容易获取连续的空间；
    4）没有浪费；
  • 分组
    修改链表来让第一个空闲的block，存放后面n-1个空闲block的地址 及下一个包含空闲block 地址的 block 地址；
  • 计数
    1）基于采用连续分配extents,空间经常连续分配，连续释放；
    2）存第一个空闲block 地址和后面空闲block的个数；
    3）空闲空间链表的每个entry包含地址和个数；
  • Trim 未使用的blocks
    1. HDD 能够原地覆盖更新，只需要空闲list
       • 释放block的时候，不需要特殊处理；
       • block上的数据仍然在，但没有文件指针指向它，直到被覆盖；
    2. NVM 设备不允许原地覆盖
       • 写之前需要擦除，擦除是以更大的块，并且很慢；
       • Trim 是一种文件系统通知NVM 设备一个page是空闲的机制
         GC；（free,但未trim）
         or 空闲,block 可以擦出;(free&&trim)

4.2文件系统效率和性能

效率依赖

• 磁盘分配，目录算法；
• 文件目录项存放数据的类型；
• metadata 数据结构的预分配，or 按需分配；
• 固定大小 or 可变大小的数据结构

性能

• 数据和metadata 一起靠近存放；
• buffer cache- 单独的一块内存用于频繁访问的block；
• 同步写请求
  i) APP 请求或OS需要
  ii) 不buffer和caching- write 必须落盘
• 异步写，更常见，可cache, 更快
• 顺序写优化技术
  i) free behind
  一旦请求下一个page，就将该page 从缓存中移除；
  之前的page 不可能再次使用并且浪费缓冲buffer空间;
  ii) read ahead (预读）
  请求页和它后续的页都读上来，并缓冲起来；
  这些后续的页很有可能会有请求要访问；
• page cache
  使用虚拟内存技术和地址来缓存页，而不是磁盘block;
  文件数据使用page cache;
  使用虚拟内存更高效，
• buffer cache
  缓存磁盘block，以文件系统block 为单位；
  文件系统IO 使用buffer cache;

• 统一buffer cache
  使用同样的page cache 缓存文件系统IO和文件数据，避免都double caching

  
  image.png

4.3 文件系统恢复

• 动机：系统崩溃可能导存储的文件系统数据结构之间不一致；
  1) 许多文件系统原地更新数据结构；
  2) 一个操作可能包含对多个数据结构的修改；
  3) 这些改动可能会被系统崩溃打断；
  4) 处于IO性能考虑，会cache更新，若在cache 落盘前系统崩溃；
• 恢复方法
  • 一致性检查
    1. 先检查，然后尝试修复；
    2. 扫描每个文件系统上所有metadata来确认文件系统是否一致；
    3. 但比较耗时；
    4. 应该每次系统启动时就扫描检查；
       • 可在文件系统metadata中记录状态；
       • 任何metadata 改变，对该状态置位，以指示metadata变动；
       • 所有metadata的更新落盘后，清除该位；
       • 若系统该状态位仍然是置位状态，需要一致性检查；
    5. unix 系统使用fsck 程序
  • 日志结构/日志文件系统
    • 将每个metadata的更新作为一个交易记录到文件系统中；
    • 所有交易写到一个日志里
      1. 一旦交易写到日志中，commit状态
      2. 可以在文件数据结构中回放日志entry里的操作；
    • 日志中的交易是异步更新到文件系统数据结构中的
      一旦完成交易，删除日志中的交易
    • 若系统崩溃，日志中的剩下的交易必须继续执行；
    • 更快从系统崩溃中恢复，消除了metadata 不一致的可能；
  • 文件系统备份
    • 处理两种情况：
      设备故障中恢复；
      误操作；
    • 备份一个设备的数据到另外一个设备中；
    • 然后从备份中恢复数据；
    • 增量备份
      第一次，做完整备份；
      后面每次都基于上一次备份做周期性增量备份；
      恢复需要从完整备份开始然后包含每次增量备份；