计算机网络体系结构

分层的网络体系结构

分层的优点

• 各层互相独立
  • 将建造一个网络的问题分解为多个可处理的部分，一层解决一部分问题
• 灵活性好
  • 任何层发生变化时，只要接口不变，上下层都不受影响
• 结构上可分割开
  • 各层都可以采用最合适的技术实现
• 易于实现和维护
• 能促进标准化工作

理论模型（OSI参考模型）

• 20世纪70年代国际标准化组织(ISO)制定
• 按网络功能划分为7层

实际架构（TCP/IP 体系架构）

• ARPANET发展而来，有TCP和IP两个核心的协议
• 四层，但不严格的划分层，这样应用可以跨层使用网络

• 细腰结构是网络体系结构模型中最典型的特征
  • IP 可应用在各式各样的网络上
  • 各式各样的应用可以承载在IP 之上
• 分层模型中的相关概念
  • 实体：任何可以发送或接受信息的硬件或软件进程
  • 对等实体：位于不同系统中的同一层内相互交互的实体
  • 网络协议：为进行网络中的数据交换建立的规则、标准或约定，控制两个对等实体进行通信的规则的集合
  • 服务：由下层向上层通过层间接口提供
  • 服务接口：同一系统内相邻两层的实体进行交互的地方，成为服务访问点（SAP）
  • 数据传输通道
    • 数据发送都是由上层传到下层，接收则由下层传到上层
    • 层间是虚通信，最下层是实际通信
  • 多路复用/多路分解
    • 发送端多个高层会话复用一条底层连接，在接收端再进行分解
    • 逐层进行封装和解封

计算机网络的性能

速率/比特率

• 比特是计算机中数据量的单位
  • 1bit即1个二进制数字（0或1）
• 网络技术中的数据率即数字信道上的传送数据的速率
• 单位（b/s）

带宽

• 计算机网络中，带宽即数字信道所能传送到的最高数据率
• 网络的带宽：在一段特定的时间内网络所能传送的比特数
  • 以特定带宽传送的比特可以看作有一定的宽度

吞吐量

• 吞吐量即单位时间内通过某个网络（或信道、接口）的数据量

• 带宽和吞吐量

  • 带宽一般指链路上每秒能传输的比特数
  • 吞吐量表示系统的测量性能，即每秒实际传输的比特

• 计算：Throughput = Transfer_size / Transfer_time

  • Transfer_time = RTT + (1/Bandwidth) * Transfer_size
    • 发请求并返回数据的时间 RTT
    • 把数据传到网上的时间
  • 传输更大量的数据有助于提高吞吐量
    • 当数据量趋于无限大时，吞吐量将接近网络带宽 ## 时延/延迟

• 时延：数据从网络的一端传送到另一端所花费的时间

• 往返时间（RTT）：数据从网络的一端传到另一端并返回所花费的时间

• 时延由四部分组成

  • 发送时延：发送数据时，数据块从结点进入到传输介质所需要的时间
    • 发送时延 = 数据块长度 / 发送速率
  • 传播时延：电磁波在信道中需要传播一定的距离而花费的时间
    • 不同介质的信道中传播的速度不同（光纤 \(2\times10^8m/s\)，电缆\(2.3\times10^8m/s\)
    • 传播时延 = 信道长度 / 信号在信道上的传播速率
  • 处理时延：主机或路由器在收到分组时进行一些必要的处理所花费的时间
    • 比如分析分组首部、差错检验、查找路由
  • 排队时延：结点在队列中等待产生的时延

• 注意：

  • 我们能提高的是数据的发送速率，而不是数据在链路中传输的速率

  • 提高链路带宽可以降低数据的发送时延

时延带宽积

• 时延带宽积 = 时延 * 带宽，即以比特为单位的链路长度
• 代表了第一个比特到达终点时，发送端发出的尚未达到接收端的比特数

Internet的组成

端系统

端系统的概念

• 连接在因特网上的所有主机，运行应用程序
• 主机之间的通信，即主机A的某个进程（运行着的程序）和主机B上的另一个进程进行通信

端系统间的通信方式

• 客户-服务器方式（Client/Server）
  • 基本概念
    • 描述的是进程之间服务和被服务的关系
    • 客户和服务器指通信中涉及的两个应用进程
    • 客户是服务的请求方，服务器是服务的提供方
  • 客户端
    • 被用户调用后运行，打算通信时主动向远地服务器发起通信（请求服务），必须知道服务器程序的地址
    • 不需要特殊的硬件和复杂的操作系统
  • 客户端
    • 专门用来提供某种服务的程序，可同时处理多个远地或本地客户的请求
    • 系统启动后即自动调用并一直不断地运行着，被动地等待并接受来自各地的客户的通信请求，不需要知道客户程序的地址
    • 一般需要强大的硬件和高级的操作系统支持
• 对等方式（P2P，Peer-to-Peer）
  • 两个主机通信时，不区分服务请求方，还是服务提供方，进行平等和对等的连接通信
  • 本质上仍然是使用客户服务器方式，只是对等连接中的每一个主机既是服务器又是客户

接入网

• 将端系统连接到边缘路由器的物理链路
  • 边缘路由器是端系统到任何其它远程系统的路径上的第一台路由器
• 使用接入网的集中环境
  • 家庭接入
    • 数字用户线（基于电话线路）
    • 电缆
    • 光纤到户（FTTH）
    • 拨号
    • 卫星
  • 企业接入
    • 局域网 LAN 接入
    • 无线局域网接入
  • 广域无线网络接入（4G/5G）

网络核心

• Internet网络核心组成
  • 十多个第一层ISP和数十万个较低层ISP组成
  • 内容提供商也创建自己的网络，直接在可能的地方与ISP互联

计算机网络的起源与发展

电路交换

传统的电路交换的电信网生存性和容错性弱

电路交换的特点

• 面向连接

• 必须经过以下三个步骤

  • 建立连接（占用通信资源）
  • 通话（始终占用通信资源）
  • 释放连接（归还通信资源）

电路交换的缺点

• 电路交换方式传送计算机数据效率低
  • 计算机数据具有突发性
    • 传送数据的时间不到10%，甚至低于1%
  • 面向连接的方式进行传输导致资源浪费
    • 被占用的通信线路绝大部分时间都是空闲的

分组交换

分组交换的原理

• 发送端
  • 把较长的报文划分成较短的、固定长度的数据段
  • 每一个数据段前面添加上首部构成分组
    • 分组是互联网中传送的数据单元
    • 每个首部都包含地址等控制信息
  • 以此把各分组发送出去
• 中间节点：通过存储转发的形式将分组逐跳转发至目的地
  • 中间结点即分组交换网中的分组交换机
    • 专门负责转发分组的计算机（路由器、二层交换机等）
  • 每个分组交换机根据收到的分组的首部中的地址信息，把分组转发到下一个交换机
    • 以存储转发的方式
  • 一个分组经历的一系列分组交换机和通信链路称为通过该网络的路径
• 接收端
  • 收到分组之后剥去分组的首部，把数据恢复成为原来的报文

分组交换的优点

• 高效
  • 动态分配传输带宽，对通信链路逐段占用，充分使用链路的带宽
• 灵活
  • 以分组为单位，查找路由和传送
• 迅速
  • 不必先建立连接就能向其他主机发送分组
• 可靠
  • 自适应的路由选择，使网络有很好的生存性

分组交换的缺点

• 时延
  • 处理时延：逐跳决策，每个中间结点都需要进行路由查找
  • 排队时延：分组在各结点存储转发时需要排队
• 附加开销
  • 分组必须携带报头（首部），造成一定开销

交换技术的比较

电路交换

• 面向连接，报文的比特流连续地从源到终点，像在一个管道中传输

报文交换

• 在电报通信是采用，同样是基于存储转发原理
• 整个报文先传送到相邻节点，全部存储下来后查找转发表，转发到下一个结点

分组交换

• 单个分组（整个报文的一部分）传送到相邻结点，存储下来后查找转发表，转发到下一结点

互联网概述

基本概念

• 链路
  • 物理直连介质：同轴电缆、双绞线、光纤、无线电频谱等
  • 网络连通有不同的层次，最底层的是一个或多个计算机通过物理介质直连
• 结点
  • 被连接的计算机/其他硬件
    • 主机（端系统）：PC、服务器、智能手机、智能家电、传感器等
    • 网络内部交换结点：交换机、AP、基站、路由器等
• 云形图
  • 计算机网络中重要的图标，表示任意类型的网络
  • 将网络的内部结点与使用网络的外部结点分开
• 直连链路
  • 所有的结点都是直连的
• 交换网络
  • 若干结点和链路组成，主机间接连通
  • 主机：支持用户运行应用程序
  • 交换结点：存储和转发分组
• 互联网
  • 网络的网络，路由器将网络和网络互连
  • 网络可以由网络的嵌套组成
    • 通过将云互联成更大的云，递归构建任意大的网络

WAFL —— NetApp的文件服务器

WAFL：Write Anywhere File Layout —— NetApp 设计的企业级文件系统

1. 设计目标
   • 请求服务速度快：吞吐率(op/s)更多，I/O带宽更高
   • 支持大文件系统，且文件系统不断增长
   • 高性能软件RAID
   • 宕机后快速恢复
2. 独特之处
   • 磁盘布局受 LFS 启发
   • 引入快照
   • 使用 NVRAM 记录日志（写前日志）

inode、间址块和数据块

1. WAFL 使用4KB块
   • inode：借鉴 UNIX FS
   • 16个指针（64B）用于文件块索引
2. 文件大小 <= 64B
   • 文件数据直接存储在 inode中
3. 文件大小 <= 64KB
   • inode存储在16个指向数据块的指针
4. 文件大小 <= 64MB
   • inode存储在16个指向间址块的指针
   • 每个间址块存储1024个指向数据块的指针
5. 文件大小 > 64MB
   • inode存储在16个指向二级间址块的指针

WAFL的磁盘布局

1. 主要数据结构
   • 一个根 inode：整个FS的根，位于磁盘上固定位置
   • 一个inode file：包含所有inode
   • 一个block map file：指示所有空闲块
   • 一个i-node map file：指示所有空闲inode

为什么将元数据存储于文件中？

1. 元数据块可以写在磁盘上任何位置
   • 这是"WAFL"名字的由来，Write Anywhere File Layout
2. 使得动态增加文件系统的大小变得容易
   • 增加一个磁盘会引发inode个数的增加
   • inode保存在文件，扩展inode文件大小即可
3. 能够通过 Copy-on-Write 来创建快照
   • COW：未写前共享数据，写时拷贝
   • 新的数据和元数据都可以COW写到磁盘上的新位置
   • 固定元数据位置无法使用COW，否则无法定位元数据

快照（snapshot）

1. 快照是文件系统的一个只读版本 – 1993 年提出
   • 成为文件服务器必备特性
2. 快照用法
   • 系统管理员配置快照的个数和频率
   • 最初系统能支持 20 个快照
   • 用快照可以恢复其中任何一个文件

快照的实现

WAFL：所有的块构成一棵树

1. 创建快照
   • 复制根 inode
   • 新的根 inode 用于当前的 Active FS
   • 旧的根 inode 指向快照
2. 创建快照之后
   • 第一次写一个块: 把从它到根的数据块都复制（COW）
   • Active FS 的根 inode 指向新数据块
   • 写数据块
   • 后续对这些数据块的写不再触发 COW
3. 每个快照都是一个一致状态的只读 FS

快照数据结构

Block Map File —— 每个 4KB 磁盘块对应一个 32位的表项

1. 表项值为0：该块为空闲块
2. 第0位=1：该块属于活动文件系统
3. 第1位=1：该块属于第一个快照
4. 第2位=1：该块属于第二个快照

...

快照创建

1. 问题
   • 创建快照时，除了拷贝根inode，需要把缓存的文件块写回磁盘
   • 此时，可能仍然有很多文件写请求到来
   • 若这些写请求都不处理，会导致文件系统长时间挂起
2. WAFL的解决方案
   • 在创建快照前，将块缓存中的脏块标记为"in-snapshot"，表示要写回磁盘
   • 所有对"in-snapshot"缓存块的修改请求被挂起
   • 没有标记为"in-snapshot"的缓存数据可以修改（即处理写请求），但不能写回磁盘
   • 本质：区分需要被写回的脏块和其他块，减少挂起的写请求数量
   • 步骤
     • 为所有"in-snapshot"的缓存块分配磁盘空间
       • 包括数据、inode
     • 更新 block map file
       • 对每个表项，将 Active FS位的值（即1）拷贝到新快照位
     • 刷回
       • 把所有的"in-snapshot"缓存块写到它们新的磁盘位置
       • 每写回一个块，重启它上面被挂起文件请求
     • 复制根inode
   • 性能较快

快照删除

1. 删除快照的根inode
2. 清除block map file中的位
   • 对于block map file的每一个表项，清除与该快照对应的位

文件系统一致性

1. 定期创建一致点
   • 一致点：存储控制器中使用 NVRAM 缓存的数据被刷回磁盘，并更新了文件系统中相应的指针
   • 每10秒创建一个一致点
   • 特殊的内部快照，用户不可见
2. 在一致点之间的多个请求
   • 第i个一致点
   • 若干写操作
   • 第 i+1 个一致点（自动增长）
   • 若干写操作
   • ...
3. 宕机恢复
   • 将文件系统恢复到最后一个一致点
   • 最后一个一致点之后到宕机前的写操作：靠日志进行恢复

非易失RAM（Non-Volatile RAM）

1. NVRAM
   • 闪存：写比较慢 vs NVRAM
   • 带电池的 DRAM：快
     • 电池容量有限，持续时间不长
     • DRAM容量有限
2. 日志写入 NVRAM
   • 记录自上一个一致点以来的所有写请求
   • 正常关机：先停止 NFS 服务，再创建一个快照，然后关闭 NVRAM
   • 宕机恢复：用 NVRAM 中的日志来恢复从最后一个一致点以后的修改
3. 使用两个日志
   • 一个日志写回磁盘时，另一个日志写入 NVRAM 中缓冲
   • 可以避免写日志时，无法处理新的写请求

安全保护

安全与保护

1. 数据机密性：未经许可，不能看到数据
   • 任何用户不能读写其他用户的文件
2. 数据完整性：未经许可，不能修改或删除数据
   • 数据在网络传输过程中被拦截和修改，可以采用加密
3. 系统可用性：干扰系统使得它不可用
   • 给一个服务器发送大量的请求

保护：策略与机制

1. 安全策略：定义目标，即要达到的效果
   • 通常是一组规则，定义可接受的行为和不可接受的行为
   • 例子
     • /etc/password 文件只有 root 能写
     • 每个用户最多只能用 50GB 的磁盘空间
     • 任何用户都不允许读其他用户的 mail 文件
2. 机制：用什么样的方法来达到目标

保护机制

1. Authentication（身份认证）
   • 验明身份
     • UNIX：密码/口令
     • 类比机场：身份证或护照
2. Authorization（授权）
   • 决定"A是不是准许做某件事"
   • 通常使用角色（role）定义授予的操作权限，使用简单的数据库保存角色定义
3. Admission Control（访问控制）
   • 做出“访问是否准许”的决定
   • 有时和系统承载压力相关联，系统负载高时，进行访问控制

身份认证

1. 通常是用密码来验证
   • 一串字符（字母 + 数字）
   • 用户必须记住密码
2. 密码是以加密形式存储
   • 使用一种单向的“安全Hash”算法
3. 缺点
   • 每个用户都要记很多密码
   • 弱密码风险，"dictionary attack"

访问控制表（ACL）

1. 每个对象有一个 ACL 表
   • 定义每个用户的权限
   • 每个表项为 <user,privilege>
2. 简单，大多数系统都采用
   • UNIX 的 owner,group,other
3. 实现
   • ACL 实现在内核中
   • 在登录系统时进行身份验证
   • ACL 存储在每个文件中或文件元数据中
   • 打开文件时检查 ACL

Capabilities

1. 超级用户具有特权，可以执行高权限操作
   • 例如passwd,chown,chmod等
2. 权能：将超级用户特权细分，分成不同的、细粒度权限
   • CAP_CHOWN: 对文件 UIDs 和 GIDs 做修改
   • CAP_KILL: 绕过发送信号时的权限检查
   • CAP_NET_ADMIN: 执行多种网络有关的操作
3. 可以为每个线程独立设置权能
4. 实现
   • 权能表保存在内核

访问控制

1. 需要一个可信权威
   • 进行访问控制
   • ACL或权能表都需要保护
2. 内核是一个可信权威
   • 内核什么事可以做
   • 如果有 bug ，整个系统都可能被破坏
   • 它越小、越简单越好
3. 安全的强度由保护系统链上最薄弱的环节决定

一些简单的攻击

1. 滥用合法权利
   • UNIX: root能做任何事情
     • 例如：读你的 mail 文件, 以你的身份发送email, 把你的邮箱删除, ...
2. 拒绝服务（DoS）
   • 耗尽系统所有资源
   • 例如
     • 运行一个 shell 脚本：while (1) {mkdir foo; cd foo;}
     • 运行一个 C 程序：while (1) {fork(); malloc(1000)[40]=1;}
3. 偷听
   • 侦听网络上传输的包

数据备份

1. FS要求
   • FS给用户提供持久化的数据存储
   • 文件一直要保存完好，除非用户显式删除它们
2. 威胁一：设备损坏
   • 磁盘块损坏
   • Superblock损坏：整个FS丢失
   • bitmap、inode table损坏：无法管理空间和inode
   • 数据块损坏：目录、文件、间址块都无法读写

备份与恢复

1. 物理备份与恢复：设备级
   • 将磁盘块逐一拷贝到另一个磁盘上（备份盘）
   • 全复制：原始盘与备份盘在物理上一模一样
   • 增量备份：只拷贝发生变化的块，与上次备份相比
   • 例如：使用dd进行磁盘备份
2. 逻辑备份与恢复：文件系统级
   • 遍历文件系统目录树，从根目录开始
   • 把指定的目录和文件拷贝到备份磁盘
   • 在备份过程中验证文件系统结构
   • 恢复时可以将指定的文件或目录树恢复出来
   • 也有两种方式
     • 全备份：备份整个文件系统
     • 增量备份：只备份发生变化的文件/目录

物理备份 vs 逻辑备份

1. 物理备份
   • 忽略文件和文件系统结构，处理过程简洁，备份性能高
   • 文件修改时只用备份修改的数据块，不用备份整个文件
   • 不受文件系统限制
2. 逻辑备份
   • 备份文件时，文件块可能分散在磁盘上，备份性能受影响
   • 文件修改时需要备份整个文件
   • 受文件系统限制，按文件粒度备份，保证完整性

宕机一致性保证

1. 威胁二：宕机或掉电
   • 硬件掉电
   • 软件bugs导致宕机：驱动或文件系统bug
   • 导致文件缓存中的脏数据没有写回磁盘：目录块、inode 、间址块、数据块
2. 挑战
   • 宕机可能发生在任意时刻
   • 在性能与可靠性之间进行取舍
     • 宕机使得内存中的数据全部丢失
     • 缓存越多的数据 -> 性能越好
     • 缓存越多的数据 -> 宕机时丢失的数据越多
   • 一个文件写操作往往修改多个块
     • 磁盘只能保证原子写一个扇区
     • 如何保证修改多个块的原子性？

宕机的影响

1. 创建文件：在当前目录 /home/xj 下创建文件 testfile
   • 需写回4个块，在磁盘不同位置
     • inode bitmap
     • 文件inode
     • 目录块：含目录项<"testfile", ino>
     • 目录inode：修改size，mtime等
   • 宕机时，没有全部写回 -> FS不一致
     • 写回顺序可能是任意的
     • 目录块没写回：有inode，没目录项
     • 文件inode没写回：有目录项，没inode
2. 写文件：在 /home/xj/testfile 末尾写入一个数据块（Append）
   • 需写回3个块，在磁盘的不同位置
     • 文件inode：修改size，mtime等
     • data-block bitmap
     • 数据块本身
   • 宕机时，没有全部写回 -> FS不一致 & 数据与元数据不一致
     • 写回顺序可能是任意的
     • FS不一致：文件inode 和 data-block bitmap 中有一个没写回
     • 数据与元数据不一致：文件inode 和 数据块没有都写回
3. 写回方案一：先写元数据、后写数据（同上例）
   • 路径解析"/home/xj/testfile" || 宕机 -> 数据与元数据一致
   • 分配数据块，写bitmap || 宕机 -> 数据与元数据一致（FS不一致，有垃圾块）
   • 写inode（直接指针、大小等） || 宕机 -> 数据与元数据不一致
   • 写数据块 || 宕机 -> 数据与元数据一致

先写元数据，宕机后可能出现数据与元数据不一致

4. 写回方案二：先写数据、后写元数据（同上例）
   • 路径解析"/home/xj/testfile" || 宕机 -> 数据与元数据一致
   • 分配数据块，写bitmap || 宕机 -> 数据与元数据一致（FS不一致，有垃圾块）
   • 写数据块 || 宕机 -> 数据与元数据一致
   • 写inode（直接指针、大小等） || 宕机 -> 数据与元数据一致

先写数据，宕机后可能i-node指向旧版本，但数据与元数据是一致的

宕机一致性保证

宕机一致性的分类

1. FS一致性
   • 文件系统自身的数据结构（称为FS元数据）一致
     • Superblock,bitmap(inode和data)，inode，目录项
     • 可能导致FS不一致：修改多个元数据的操作
       • 创建/删除文件、创建/删除目录、重命名、硬链接、符号链接、...
       • 写文件
2. 数据与元数据一致性
   • 文件元数据（inode和间址块）和文件块一致
   • 数据与元数据不一致：写文件
3. 数据一致性
   • 一次写多个数据块
   • 数据不一致：写文件
4. 宕机一致性保证
   • 一个操作包含多个修改：要么全部写到磁盘，要么都没写到磁盘

宕机一致性的总结

1. 通用方法：按自底向上顺序进行修改（Ordered Write）
   • 文件的数据块 -> 文件的inode -> 目录的数据块 -> 目录的inode
     • 写回所有的数据块（有文件缓存）
     • 修改文件的inode，并把它写回磁盘
     • 修改目录块（目录项），并把它写回磁盘
     • 修改目录的inode，并把它写回磁盘
     • 沿路径向上，直到无修改的目录
2. 不足
   • 宕机后仍然可能产生垃圾块（FS不一致），也可能有目录和文件不一致（文件修改了，目录没有改）
   • FS不一致可以通过运行一致性检查工具（例如fsck）清理垃圾块
3. 理想情况
   • 保证一致性的修改，而且不留下垃圾块
   • 三个一致性保证

fsck：Unix FS一致性检查工具

1. 检查并试图恢复FS的一致性
   • 不能解决所有问题，比如数据与元数据不一致
2. 检查Superblock
   • 如果fs size < 已分配块，认为它损坏，切换到另一个 Superblock 副本
3. 检查块位图
   • 重构已使用块信息：扫描磁盘上所有的 inode 和间址块
4. 检查 inode 位图
   • 重构已使用 inode 信息：扫描磁盘上所有目录的目录项
5. 检查 inode
   • 通过 type 域的值（普通文件，目录，符号链接）来判断 inode 是否损坏
   • 如果损坏，则清除该 inode 及它对应的 bitmap 位
6. 检查 nlink 域
   • 遍历 FS 的整个目录树，重新计算每个文件的链接数（即指向它的目录项个数）
   • 没有目录项指向的 inode ，放到 lost+found 目录下
7. 检查数据块冲突
   • 是否有两个(或更多)的 inode 指向同一数据块
   • 如果有 inode 损坏，则清理 inode，否则把该数据块复制一份
8. 检查数据块指针
   • 指针是否越界(> 磁盘分区大小)
   • 删除该指针
9. 不足
   • 恢复时间与 FS 大小成正比
     • 即使只修复几个块，也需要扫描整个磁盘和遍历 FS 目录树
     • 会导致丢数据：inode 损坏、数据块或间址块损坏

事务和日志文件系统

事务：一组操作，需要具有原子性 —— 要么所有操作都成功完成，要么一个操作也不曾执行过

事务的应用 —— Write-Ahead Log（写前日志）

1. 写前日志
   • 在实际进行写操作前，先把写操作记日志
   • 记录日志时使用事务
2. 前提
   • 日志中记录的所有修改必须是幂等的
   • 每个事务有唯一的编号 TID
   • 必须有办法确认写磁盘完成
     • TxB 和 日志记录可以同时发给磁盘，TxE最后发送，使用 Write Barrier
     • 使用 fsync 保证写盘完成

具体步骤

1. Begin Transaction（开始事务）
   • 开始一条日志项，写一个日志开始标记 TxB，标明一个事务开始
2. 事务中的修改
   • 所有修改都写日志
   • 事务日志中需要标明事务编号 TID
3. Commit（提交事务）
   • 写一个日志结束标记 TxE，标明一个事务成功完成
4. Checkpoint（检查点）
   • Commit 之后，把该事务中的修改全部写到磁盘上
5. 清除日志
   • Checkpoint 写完后，清除相应的日志项

宕机恢复（Replay）

1. 宕机后扫描写前日志中的日志项，对于每条日志项
   • 如果磁盘上只有日志开始标记 TxB，没有结束日志 TxE，则什么也不做
   • 如果日志项是完整的（同时有 TxB 和 TxE），则按日志重做（Redo Log），然后再清除日志
2. 前提假设
   • 写到磁盘上的日志数据都是正确的
   • 宕机后没有磁盘损坏

日志文件系统（Journaling File System）

1. 用写前日志来记录所有写操作

   • 创建/删除文件、创建/删除目录、重命名、硬链接、符号链接...
   • 写文件

2. 第一个日志文件系统：Cedar FS[1987]

3. 很多商用文件系统都使用写前日志：NTFS、JFS、XFS、Linux ex2/3/4...

4. 宕机恢复

   • 按日志重做一遍
   • 简单、高效
     • 恢复时间与日志大小成正比
   • 日志必须是等幂的

日志文件系统：数据日志（data journaling）

1. 记录所有修改的日志：数据 & 元数据
2. 例如：在一个文件末尾追加一个数据块
   • 修改文件的inode，修改bitmap，写数据块
3. 流程
   • 写日志：TxB、inode日志、bitmap日志、数据块日志
   • 提交日志 commit：写 TxE
   • Checkpoint：实际修改磁盘上的inode、bitmap、数据块
   • 清除日志
4. 日志开销
   • 所有数据块写两次磁盘

日志文件系统：元数据日志（metadata journaling）

1. 只记录元数据的修改的日志
2. 例如：在一个文件末尾追加一个数据块
   • 修改文件的inode，修改bitmap，写数据块
3. 流程
   • 写数据块
   • 写日志：TxB、inode日志、bitmap日志
   • 提交日志 commit：写 TxE
   • Checkpoint：实际修改磁盘上的inode、bitmap
   • 清除日志
4. 日志开销
   • 只有元数据写两次磁盘，所有数据块只写一次磁盘

日志文件系统总结

1. 性能问题
   • 增加额外的写磁盘开销：每个日志都要同步写磁盘（fsync）
   • 写放大
     • 即使只修改一个块中少量内容（十几字节），也需要写日志
     • Bitmap中一个bit修改，也要对bitmap block写日志
2. 改进办法
   • 批量写日志：以牺牲可靠性换取性能
     • 宕机仍然可能丢数据，但不会损坏FS一致性
     • 例如，再同一个目录下创建和写入多个文件
   • 用 NVRAM 来保存日志，实现快速同步写
3. 可靠性
   • 无法应对硬件故障，比如磁盘扇区坏
4. 日志管理
   • 需要多大的日志？
     • 日志只在宕机恢复时需要
     • 日志过小，很快占满日志空间，无法接受新日志
     • 日志过大，导致恢复时间长
   • 方法
     • 顺序地、Append-only 写，循环使用日志空间（Circular Log）
     • 定期做 checkpoint ：把缓存里的修改内容刷回磁盘
     • checkpoint 之后，可以释放日志所占空间

日志结构文件系统（LFS —— Log-Structured File System）

1. 思想
   • 想写日志那样顺序地写磁盘
2. 具体机制
   • 每次写文件块写到新位置（日志末尾）：out-of-place update（vs in-place update）
   • 不需要 bitmap 来管理空闲空间
   • 文件块采用多级索引（同FFS）：文件块位置记录在 inode中
   • 每次写文件采用一致性修改：先写文件块，再写inode
3. 大粒度顺序写
   • 起因：小粒度写不能发挥磁盘带宽
   • Segment：大粒度的内存 buffer
     • 缓存多个写，一次把整个 Segment 写回磁盘
     • 写回时仍然遵循 先写文件块，再写inode 的原则

读inode

1. UFS 和 FFS
   • 通过ino来计算出inode的位置
2. LFS
   • 每次写文件块，都要写 inode
   • 每次会写到新的位置，即一个文件的 inode 在磁盘没有固定位置

imap

1. 记录 ino->inode 磁盘地址，只记录最新的inode地址
2. 怎么存
   • 磁盘上的固定位置
   • 每次写文件，都要修改 imap
   • 写日志与写imap需要长距离寻道，性能比 FFS 还差
3. LFS的改进方法
   • imap块随文件块和i-node一起写到日志中
   • CR(Change Region)：记录每个imap块的最新磁盘地址
   • CR位于磁盘上固定位置：有两个CR，分别位于磁盘的头和尾

关于目录：目录采用与文件一样的方式来写

读文件

1. 假设 LFS 刚挂载，内存里什么也没有
   • 先读 CR，把 CR 缓存在内存，以后就不用读了
   • 根据 ino ，知道它所在的磁盘块
   • 查 CR 得到 imp 块的磁盘地址
   • 读 imap 块，得到 ino 对应的 inode 的磁盘地址
   • 读 inode，查文件块索引，得到文件块的磁盘地址
   • 读文件块

修改文件

1. 修改 /home/os/foo 的第一块
   • 原来的数据块变为无效 -> 垃圾
2. 在 /home/os/foo 末尾追加写一块
   • 原来的inode变为无效 -> 垃圾

垃圾回收

1. 原理
   • 后台进程cleaner周期性地检查一定数量的segment
   • 把每个segment中的活块拷贝到新的segment中
     • 如何判断活块？
       • segment summary block
         • 记录每个数据块的ino和文件内偏移
         • 位于 segment 的头部
       • 通过查segment summary block、imap和文件索引可以得到当前块的地址
   • M个segment的活块占据N个新的segment
2. 何时回收
   • 周期性回收
   • 空闲时：无访问或访问少
   • 磁盘快满的时候
3. 回收什么样的segment
   • 热segment：块频繁被重写
   • 冷segment：部分死块、部分稳定块（不重写）
   • 优先回收冷segment，推迟回收热segment（直至该segment里的数据块都被重写过）

宕机恢复

1. LFS的最新修改在日志末尾
2. CR记录第一个 segment 和最后一个 segment 的磁盘地址
   • 每个segment指向下一个segment
3. CR更新
   • 写CR的第一个块，带时间戳
   • 写CR本身内容
   • 写CR最后一个块，带时间戳
   • 周期性地将CR刷盘（30s）
   • 两个CR（磁盘头和尾）交替写，减少CR更新时宕机的影响
4. CR一致性保证
   • 第一个块和最后一个块的时间戳一致
5. 恢复方式
   • 使用最后一次且一致的 Checkpoint Region
     • 时间戳最新的 & 完整的CR
     • 可以获得最后一次 Checkpoint 时的 CR 内容，包括 imap 等数据结构的地址
   • CR 周期性刷盘，此时 CR 内容可能已过时，即最后一次 Checkpoint 后的磁盘写没有被恢复
   • 恢复优化（回滚）
     • 使用最后一次修改的 CR（不一定是一致的）重构最新的文件修改
       • 根据 CR 找到日志末尾（有记录），检查后续写的 segment
       • 将其中有效的更新恢复到文件系统，例如，将 segment summary block 中记录的 inode 更新到 imap 中
   • 恢复快
     • 无需fsck，无需扫描磁盘
     • 秒级 vs 小时级

文件块索引结构

文件块索引：连续分配

1. 分配连续的磁盘块给文件
   • 文件粒度分配
   • bitmap：找到N个连续的"0"
   • 链表：找到 size>=N 的区域
2. 文件元数据
   • 记录第一个块的地址
   • 块的个数N
3. 优点
   • 顺序访问性能高
   • 随机访问时定位数据块也较容易
4. 缺点
   • 不知道文件最终多大，无论创建时，还是写数据块的时候
   • 文件难以变大
   • 外部碎片化

文件块索引：链表结构

1. 分配不连续的磁盘块给文件
   • 块粒度分配
2. 文件元数据
   • 记录第一个块的地址
   • 每个块指向下一个块的地址
   • 最后一个块指向NULL
3. 优点
   • 无外部碎片，而且文件变大很容易
   • 空闲空间链表：与文件块类似
4. 缺点
   • 随机方式性能极差：定位数据块需按指针顺序遍历链表
   • 可靠性差：一个坏块意味着其余的数据全部丢失
   • 块内要保存指向下一块的指针，有效数据大小不一定是2的幂次

文件块索引：文件分配表（FAT）

1. 一张有N的项的表，假设磁盘有N块
   • 每个磁盘块有一个表项：要么为空，要么为该文件下一块的地址
   • 位于磁盘分区的头部
2. 文件元数据
   • 记录第一块的地址：链表头指针
   • 每个磁盘块全部存数据，无指针
3. 优点
   • 简单
   • 文件块为2的幂次
4. 缺点
   • 随机访问性能不好
     • 定位数据需要查找FAT表
   • 浪费空间
     • 需要额外的空间存储FAT表

文件块索引：单机索引

1. 文件元数据
   • 用户定义文件长度上限 max size
   • file header: 一个指针数组指向每个块的磁盘地址
2. 优点
   • 文件在限制内可变大
   • 随机访问性能高：数据块直接定位
3. 缺点
   • 不灵活，文件长度难以事先知道

文件块索引：两级索引

1. 思路：
   • 采用可变段分配
   • 段内的块连续分配，段间运行不连续
2. 文件元数据
   • 小文件有10个指针，指向10个可变长度段（base,size）
   • 大文件有10个间接指针，每个指向可变长度的间址块
3. 优点
   • 支持文件变大
4. 缺点
   • 段间碎片

文件块索引：多级索引（UNIX）

1. 块粒度分配
2. 文件元数据：13个指针
   • 10个直接指针
   • 第11个指针：一级间接指针
   • 第12个指针：二级间接指针
   • 第13个指针：三级间接指针
3. 优点
   • 小文件访问方便
   • 支持文件变大
4. 缺点
   • 文件有上限
   • 存在大量寻道

文件块索引：Extents

1. Extent是若干个连续磁盘块（长度不固定）
   • 同一Extent中的所有块：要么多少空闲块，要么都属于某个文件
   • Extent：<starting block, length>
2. XFS提出的方法
   • 无论文件块还是空闲块都采用Extents来组织
     • 块大小为8KB
     • Extent的大小 <= 2M个块
   • 文件块索引
     • 采用B+树，中间结点记录文件块号和子节点的磁盘块地址
     • 叶节点记录文件快好和其所属的Extent
   • 文件元数据
     • 记录B+树的根结点地址

目录项的组织结构

目录访问

1. 路径解析
   • 在目录里查找指定目录项：文件名
2. 修改目录
   • 创建/删除目录、创建/删除文件、硬链接、符号链接、重命名
   • 在目录里添加/删除目录项
3. 读目录
   • 扫描目录内容

目录项的组织结构

1. 线性表
   • 原理
     • <文件名,ino> 线性存储
       • 每一项不定长：<ino,名字长度，下一项起始偏移，名字>
     • 创建文件
       • 先查看有没有重名文件
       • 如果没有，在表末添加一个entry: <ino,newfile>
     • 删除文件
       • 用文件名查找
       • 删除匹配的entry
       • 紧缩：将之后的entry都向前移动
   • 优点
     • 空间利用率高
   • 缺点
     • 大目录性能差：线性查找，目录项数据从磁盘读取，磁盘的I/O多
     • 删除时的紧缩很耗时
2. B+树
   • 原理
     • 在磁盘上使用B树索引目录的数据块
     • 用B树来存储<文件名,ino>，以文件名排序（字典序）
     • 创建/删除/查找：通过B树实现
   • 优点
     • 大目录性高：B树的查找减少磁盘的I/O
   • 缺点
     • 小目录不高效
     • 占用更多空间
     • 实现复杂
3. 使用哈希表索引
   • 原理
     • 在VFS中使用哈希表索引目录项
     • 用哈希表将文件名映射到ino
       • hash_func(filename) -> hval -> 哈希桶
       • 在哈希桶中线性查找 filename
     • 创建/删除需要分配/回收空间
   • 优点
     • 简单
     • 查找速度快
   • 缺点
     • 哈希表空间不好估计
       • 表较大浪费空间
       • 表小容易产生大量哈希冲突

创建文件或目录

例子：创建文件/home/os22/fs02.ppt

1. 解析父目录"/home/os22"，得到其ino，假设为100
2. 读取其i-node，检查用户是否具有创建的权限
3. 根据i-node，读取父目录的内容
4. 查找是否已经存在名字为"fs02.ppt"的目录项
5. 如果找到，同时flag为目录，则返回失败，否则转11
6. 为"fs02.ppt"分配一个空闲的inode，假设其ino为116
7. 填充inode的内容ino,size,uid,gid,ctime,mode...
8. 在父目录的内容中添加一个目录项<"fs02.ppt",116>
9. 修改父目录的inode:size,atime,mtime
10. 把修改写到磁盘"fs02.ppt"的inode、父目录的inode、父目录内容
11. 创建一个打开文件结构，指向"fs02.ppt"的inode
12. 分配一个空闲的打开文件结构指针，指向打开文件结构
13. 返回指针的数组下标

删除文件或目录

例子：删除文件/home/os22/fs02.ppt

1. 路径解析父目录"/home/os22"，得到其ino为100
2. 读取其i-node，检查用户是否具有删除的权限
3. 根据i-node，读取父目录的内容
4. 查找是否已经存在名字为"fs02.ppt"的目录项
5. 如果不存在，则返回失败
6. 得到"fs02.ppt"的ino为116
7. 如果nlink为1，则释放inode及文件块，否则nlink-1
8. 在父目录的内容中删除目录项<"fs02.ppt",116>
9. 修改父目录的inode:size,atime,mtime
10. 把修改写到磁盘：inode、父目录inode、父目录内容、空闲块
11. 返回

文件缓存

例如：解析路径"/home/foo"，并读/写，会产生大量I/O

1. 读根目录的i-node和它的第一块
2. 读home目录的i-node和它的第一块
3. 读foo文件的i-node和它的第一块 / 创建文件foo并写其第一块

文件缓存（File buffer cache/page cache）

1. 使用内核空间的一部分内存来缓存磁盘块
2. 读操作read()：先检查该块是否在缓存中
   • 在：将缓冲块的内容拷贝到用户buffer
   • 不在：
     • 分配一个缓存块（可能需要替换）
     • 把磁盘块读到缓冲
     • 再把缓存块拷贝到用户buffer
3. 写操作write()：先检查该块是否在缓存中
   • 在：将用户buffer的内容拷贝到缓冲块
   • 不在：
     • 分配一个缓存块（可能需要替换）
     • 把用户buffer的内容拷贝到缓存块
   • 将该缓存块写回磁盘（根据缓存管理策略）
4. 缓存设计问题
   • 缓存什么、缓存大小、何时放进缓存、替换谁、写回策略

缓存什么

1. 不同类型的块
   • i-nodes
   • 间址块
   • 目录
   • 文件块

缓存大小

1. 文件缓存与进程使用的虚存竞争有限的内存空间
2. 两种方法
   • 固定大小：用特权命令设置文件缓存大小
   • 可变大小：
     • 文件缓存和VM都按需申请内存：页替换
     • 文件缓存大小不可控

替换谁

1. 为什么缓存位于内核空间
   • DMA
     • DMA数据传输
   • 多用户进程
     • 共享缓存
2. 通常的替换策略
   • 全局LRU
   • 进程工作集

何时放进缓存

1. 何时放进缓存：按需取 vs 预取
2. 文件访问具有局部性
   • 时间局部性
   • 空间局部性
3. 最优
   • 在要用之前搞好预取进来
4. 通常的策略
   • 针对顺序访问的预取：访问第i块时，预取随后的k个块
     • 文件块尽量分配连续的磁盘块
     • Linux采用的方法
   • 针对inode的预取：在读取目录项时，同时读取对应的inodes
5. 高级策略
   • 预取同一目录下所有的小文件

写回策略

1. 写操作
   • 数据必须写到磁盘才能持久化
2. 缓存中的数据何时写到磁盘上
   • Write Through
     • 每个写操作，不仅更新缓存块，而且立即更新磁盘块
     • 好处：简单&可靠性高，最新数据都落盘
     • 坏处：磁盘写没有减少
   • Write Back
     • 每个写操作，只更新缓存块，并将其标记为脏块
     • 之后再将它写到磁盘
     • 写操作快 & 减少磁盘写：缓存吸纳多次写，批量写磁盘
3. 写回的复杂性
   • 丢数据
     • 宕机时，缓存中的“脏”数据将全部丢失
     • 推迟写磁盘 -> 更好的性能，但损失更大
   • 什么时候写回磁盘
     • 当一个块被替换出缓存时
     • 当文件关闭时
     • 当进程调用fsync时
     • 固定的时间间隔（Unix是30s）
   • 问题
     • 执行写操作的进程并不知道数据什么时候落盘了
       • 通过fsync：用户显式写回数据
     • 不能保证不丢数据：宕机或掉电可能发生在任何时候

文件系统 vs 虚存

1. 相似点
   • 位置透明性：用户不感知物理地址
   • 大小无关性：固定粒度分配（块/页），不连续分配
   • 保护：读/写/执行权限
2. FS 比 VM 容易的地方
   • FS的地址转换可以慢
   • 文件比较稠密（空洞少），经常是顺序访问
   • 进程地址空间非常稀疏，通常是随机访问
3. FS 比 VM 难的地方
   • 路径解析可能引入多次I/O
   • 文件缓存的空间（内存）总是不够的
   • 文件大小差距大：很多不足10KB，有些又大于GB
   • FS的实现必须是可靠的

虚存页表 vs 文件块索引

1. 页表
   • 维护进程地址空间与物理内存的映射关系
   • 虚页号 -> 物理页框号
   • 查检访问权限、地址合法性
   • 硬件实现地址转换，如果映射关系在TLB中，很快完成转换
2. 文件块索引
   • 维护文件块与磁盘块之间的映射关系
   • 文件块号 -> 磁盘逻辑块号
   • 查检访问权限、地址合法性
   • 软件（OS）实现地址转换，可能需要多次磁盘I/O

FFS（Unix文件系统）

最初的 Unix FS

1. 简单的磁盘布局
   • 文件块大小 = 扇区大小 = 512B
   • i-node区在前，数据区灾后
   • 空闲块/inode链表：Superblock中记录头指针
2. 文件块索引采用三级间指，目录采用线性表
3. 存在的问题
   • 带宽很低：顺序访问只有20KB/s，即2%的磁盘带宽

导致带宽低的原因

1. 数据块的存储位置
   • 数据块存储在内层的柱面
   • inode 存储在外层的柱面
2. 频繁长距离寻道
   • inode 与其数据块离得很远
   • 同一目录里的文件，其inode也离得很远
   • 一个文件的数据块散布在磁盘上任意位置
     • 即使顺序读写文件 -> 随机磁盘 I/O
3. 未考虑给文件分配连续磁盘块
   • 空闲块采用链表组织
   • 链表上相邻的块，其物理地址不连续
4. 小粒度访问多
   • 采用512B的小块
   • 无法发挥磁盘带宽

BSD FFS（Fast File System）

1. 大文件块：4KB/8KB vs 512B
   • 数据块大小记录在Superblock中
   • 空间利用率问题
     • 小文件
     • 大文件的最末一块可能非常小
   • FFS的解决办法
     • 数据块划分为若干更小的子块
     • 子块为512B，每块8/16个子块
2. Bitmap：取代空闲块链表
   • 尽量连续分配
   • 预留 10% 的磁盘空间

FFS的磁盘布局

1. 柱面组（Cylinder Group）
   • 柱面：所有盘片上半径相同的磁道构成一个柱面。
   • CG：每N个连续的柱面为一个CG
   • 把磁盘划分为若干柱面组，将文件和目录分散存储于每个柱面组
   • 每个CG类似于一个 Sub FS
     • 包含Superblock，空闲inode bitmap，空闲块bitmap，inode表，数据块

FFS的放置策略

1. 减少长距离寻道
   • 原则：把相关的东西放在同一CG
2. 目录放置
   • 选择CG：目录个数少 & 空闲inode个数多 & 空闲块多
3. 文件放置
   • 文件inode选择其目录所在的CG
   • 文件块选择其inode所在的CG
     • inode与文件块一起读的概率是只读inode的4倍
4. 大文件处理
   • 应避免它占满一个CG
   • inode所在CG：存放前10个磁盘块（直接指针指向）
   • 每个间址块及其指向的块放在同一CG（4MB）
   • 不同间址块及其指向的块放在不同CG

FFS的效果

1. 性能提升
   • 读写性能和CPU利用率提升
   • 小文件性能提升
2. 进一步的优化空间
   • 块粒度分配和多级索引，大文件访问不高效
     • 用 Extent 来描述连续的数据块
   • 元数据采用同步写，影响小文件性能
     • 异步写，并保证一定的顺序
     • 日志

文件系统基础

1. 为什么我们需要文件系统
   • 持久化保存数据需求（Persistence）
   • 进程结束、关机/关电、宕机/掉电
   • 使用持久化存储设备：磁盘、SSD等
2. FS 是对持久化数据存储的抽象
   • 给用户/程序开发者提供一个逻辑上的持久化存储
     • 文件、目录形式
     • 简单、易理解、操作方便
   • 将复杂的、公共的管理功能从用户程序中移出
     • 存储设备管理，例如磁盘
     • 数据管理，即程序持久化数据的组织和增删改查
3. 对FS的基本需求
   • 能够保存大量（复杂多样）的信息 -> 管理问题
   • 多个进程同时访问 -> 并发控制问题
   • 多用户共享数据 & 私有数据 -> 安全保护问题

文件系统的用户视图

1. 文件：数据组织的单位
   • 文件是命名的字节数组
   • 用户将数据组织成文件，根据文件名来访问对应的数据
   • FS不感知文件的内容：使用文件的进程负责解析内容
2. 目录：文件组织的单位
   • 一组文件和目录的命名集合
   • 父目录、子目录
   • 同一目录下没有重名的
3. 名字空间：树形层次结构
   • 文件系统的逻辑视图

文件

1. 文件名：由字母、数字及某些特殊字符组成的字符串
   • 用户根据文件名来访问文件
   • 文件扩展名：描述文件的用途
2. 文件属性
   • 文件大小、所有者、时间戳、访问权限
   • 文件逻辑地址：0..fsize-1，指示数据在文件中的位置
3. 文件内容：无结构
   • OS将文件视为无结构的字节数组
   • 程序开发者可以定义任意结构的文件
4. 文件的类型
   • 常规文件、目录文件、设备文件、可执行文件
5. 文件的访问
   • 打开文件 & 文件描述符
   • 当前位置：文件内部的逻辑地址，范围是[0,fsize-1]
   • 访问方式（Access Mode）：读，写，执行
6. 文件的访问模式（Access Pattern)
   • 顺序访问
     • 从头到尾依次访问每个文件块
     • 顺序访问文件 不等于 磁盘上顺序访问扇区
   • 随机访问
     • 每次随机访问一个文件块
   • 按关键字访问
     • 查找包含关键字的文件及段落
     • 文件系统本身不提供此功能，需要借助应用程序完成
     • 与之相比，数据库自身可以实现按关键字查找记录

目录

1. 路径
   • 根目录 & 当前工作目录
   • . : 当前目录
   • .. : 根目录
   • 绝对路径 vs 相对路径
2. 目录：一种特殊的文件
   • 命中 & 属性
   • 目录和文件用相同的数据结构（inode）
     • 通过一个标志（i_mode）来区分文件和目录
   • 目录内容：描述它所包含的目录和文件集合
     • 有结构：逻辑上是一张表
     • 目录项：每个成员一项
     • 不同的FS采用不同的结构
     • 由FS负责维护和解析目录内容
     • 访问目录 vs 访问文件：通过不同的syscall实现

链接

1. 硬链接
   • 为文件共享提供的一种手段
     • 为文件创建一个新名字，无数据拷贝
     • 多个名字可以指向同一个文件
     • 一个文件可以同时拥有多个名字，甚至位于多个目录中
   • 限制
     • 不能跨文件系统
     • 不能链接目录
2. 符号链接
   • 另一种文件共享的手段
     • 创造一个普通文件，内容为目标地址的路径（绝对路径/相对路径）

文件系统内部结构

虚拟文件系统 和 物理文件系统

1. 虚拟文件系统
   • 同时挂载不同类型的FS
     • SUNFS访问本地的磁盘
     • SUN NFS访问远端服务器的FS
   • 实现FS接口和通用功能
2. 物理文件系统
   • 磁盘布局、数据结构、磁盘空间管理、名字空间管理等
3. 虚拟文件系统开关表
   • 用于物理文件系统的挂载与卸载
   • 每一种类型的文件系统有一个表项
     • 文件系统类型的名字
     • 初始化函数指针，用于 mount
     • 清除函数指针，用于 umount
   • 例子: mount -t ext4 /dev/sdb /home/os
     • 前提：
       • 文件系统类型ext4必须事先加载进内核
       • 挂载目录 /home/os 必须要已经创建好
     • 步骤
       • 根据文件系统类型，查VFS开关表，找到该ext4类型FS的初始化函数，即ext4_mount()
       • 调用ext4_mount
         • 读取superblock
         • 读取根目录i-node
       • 初始化一些内存数据结构

文件系统主要数据结构

i-node

inode：描述文件/目录，也成为文件元数据

1. 每个文件用一个i-node来描述
2. 文件元数据
   • mode: 文件类型和访问权限
   • size: 文件大小
   • nlinks: 硬链接数
   • uid: 所有者的user id
   • gid: 所有者的group id
   • ctime: 文件创建的时间戳
   • atime: 上一次访问文件的时间戳
   • mtime: 上一次修改文件的时间戳
3. ino：inode number，即i-node的ID，唯一标识一个文件（在一个FS内）
4. 文件块的索引信息：文件块的磁盘位置信息
   • <offset,count> -> 磁盘上的位置 （文件块# -> 磁盘逻辑块# LBN）
   • 不同的FS采取不同的索引机制

目录项（dentry）

dentry: 目录项，记录文件和inode的对应关系

1. 目录内容为它所包含的所有子目录和文件的名字及其ino
   • 不包含子目录的内容
2. 逻辑上，目录是一张映射表
   • 目录项(dentry): 文件名 -> ino
3. 物理上，目录项是一个字节数组
   • 文件名不等长，数组每一项不等长
4. 路径解析
   • 根据路径名，获得其ino
   • 逐级目录查找
   • 例子: /home/os/fs01.ppt
     • 从根目录开始，查找/home的ino
     • 在home目录下查找os的ino
     • 再os目录下查找fs01.ppt的ino
     • 根据fs01.ppt的ino，找到其数据块，进行读写操作

打开文件表（Open-file table）

打开文件表：记录进程打开的文件信息

1. 打开文件，通过 fd = open(path,flags,mode)实现
2. 打开文件表: Open-file table
   • 通过打开文件表（在内存中）把进程与文件的i-node进行关联
   • 路径名解析和权限检查，得到path的ino，读出它的inode（保存在磁盘上）
   • 将磁盘i-node拷贝到一个内存i-node结构中，在打开文件表中增加一项，包含以下内容
     • 文件的Reference Count
     • 当前文件的偏移量
     • 文件的访问模式
     • 内存inode结构的指针

文件描述符表：File Descriptor Table

1. 每个进程有一个文件描述符表
   • 指针数组，每个指针指向打开文件表中的一项，表示一个打开文件
   • 该指针在文件描述符表中的下表，即文件描述符fd

超级块（superblock）

superblock: 描述文件系统基本信息

1. 定义一个文件系统
   • 数据块的大小
   • i-node的大小
   • 数据块总数
   • i-node总数
   • 根目录ino
   • i-node表的起始地址
   • Block Bitmap的起始地址
   • i-node Bitmap的起始地址
2. 当前状态
   • 数据块的使用状态：已使用的块数、预留的块数、剩余的块数...
   • i-node的使用状态：已使用的i-node数、预留的i-node数、剩余的i-node数...

文件系统的磁盘布局

Boot Block | Superblock | Block Bitmap | i-node Bitmap | I-node Array | Data Blocks

1. 引导块
   • 启动OS的代码
2. Superblock：定义一个FS
   • FS的相关信息
3. 空闲空间管理相关的信息
   • Block Bitmap
   • i-node Bitmap
4. i-node表
   • 每个i-node描述一个文件或目录
5. 数据块
   • 文件块或目录块

固态硬盘SSD（Solid State Drive）

闪存组织

1. 闪存（Flash Memory）
   • 1984：NOR flash
   • 1987：NAND flash
   • 1992：SSD
2. NOR flash vs NAND flash
   • NOR是字节寻址，NAND是页寻址
   • NOR读延迟比NAND低100x
   • NOR擦除时间比NAND高300x
   • NOR用于取代ROM，存可执行代码
   • NAND用于大量持久化存储设备
3. 信息存储方式
   • SLC：1 bit/cell 2个值 0/1
   • MLC：2 bit/cell 4个值 00/01/10/11
   • TLC：3 bit/cell 8个值
   • QLC：4 bit/cell 16个值

NAND闪存组织

1. Flash package
   • 多个 die
2. Die
   • 多个 Plane/Bank
3. Plane/Bank
   • 很多块（擦除块）
   • 一些寄存器
4. 块（Block/Erase Block）
   • 很多页
5. 页（Page）
   • 由数据区与OOB(Out of Band)区构成
   • 数据区用于存储实际数据
   • OOB区用于记录
     • ECC
     • 状态信息：Erased/Valid/Invalid
     • Logic Page Number
   • 页大小
     • SLC通常为2KB_{8KB，TLC通常为4KB}16KB
   • 块大小
     • SLC通常为128KB、256KB...
     • TLC通常为2MB、4MB...

闪存的操作接口

1. 读：Read a page
   • 读的粒度是页
   • 读很快，读延迟在几十微秒
   • 读延迟与位置无关，也与上一次读的位置无关（和磁盘不同）
2. 擦除：Erase a block
   • 把整个块写成全1
   • 擦除的粒度是块，必须整块擦除
   • 很慢：擦除时间为几个毫秒
   • 需软件把块内有效数据拷贝到其它地方
3. 写：Program a page
   • 擦除后才能写，因为写只能把1变成0
   • 写的粒度是页
   • 写比读慢，比擦除快，写延迟在几百微秒

页的状态

1. 初始状态为Invalid
2. 读时，不改变页的状态
3. 擦除时，块内所有页的状态变为Erased
4. 写时，只能写状态为Erased的页，写后页状态变为Valid

闪存的性能和可靠性

1. 性能
   • 写延迟比读高10倍以上
   • 写延迟波动幅度大
   • 擦除很慢：约为磁盘定位延迟
   • 延迟随密度增加而增长
2. 可靠性
   • 磨损：擦写次数有上限，随密度增加而减少
   • 干扰：读写一个页，相邻页中一些位的值发生翻转
3. 闪存特性
   • 读延迟很低：随机读的性能远优于磁盘
   • 写慢：必须先擦除再写，约为磁盘写（ms级）
   • 磨损：每个块擦写次数有上限

基于闪存的SSD

1. 用很多闪存芯片来构成一个持久化存储设备SSD
2. 多个闪存芯片：并行I/O，提高I/O性能
3. 与主机的接口：提供标准块设备接口
4. 数据缓存和缓冲：SRAM/DRAM
5. 闪存控制器（硬件）和FTL（固件）：控制逻辑
   • 主机命令转换成闪存命令（Read/Erase/Program）
   • 逻辑块地址转换成闪存的物理地址（页/块）
   • 缓存替换

FTL

最简单的FTL：直接映射

1. Direct Mapping
   • 逻辑块的第N块直接映射到物理的第N页(假设逻辑块与物理页都为4KB）
2. 读操作容易：读逻辑第k页
   • 读物理第k页
3. 写操作麻烦：写逻辑第k页
   • 第k页所在闪存块（记为B0）
   • 把B0整个块读出来
   • 把B0整个块擦除
   • B0中的旧页和新的第k页：以顺序方式一页一页再写入B0
4. 缺陷：写性能极差
   • 每写一个页，要读整个块、擦除整个块、写整个块
   • 写放大

FTL改进：异地更新

1. 核心思想：异地更新（out-of-place update）
   • 不再执行原地更新
   • 每次写页，写到一个新位置（新的物理页地址）
2. 页级映射
   • 页级映射表：LPN -> 物理页地址PPN
     • 整个放在内存中
     • 持久化：利用页的OOB区来保存映射表
     • 随着写页而被写到闪存
     • 掉电或重启，扫描OOB区来恢复映射表
   • 优点：
     • 性能好：减少写放大
     • 可靠性好：映射关系被自动写入闪存
   • 问题：
     • 重写产生垃圾页
       • 每次写到新位置，导致原先页的内容无效
     • 内存开销大
       • 映射表全部放内存
       • 映射表的大小与SSD容量成正比
3. 写一个逻辑页k
   • 寻找一个空闲页p（例如当前擦除块中下一个空闲页p）
   • 在映射表中记录：逻辑页k -> 物理页p
4. 读一个逻辑页k
   • 查映射表，获得逻辑页k对应的物理页地址p
   • 读物理页p

垃圾回收

1. 思想
   • 选择一个含垃圾页的块
   • 把其中的有效页拷贝到其他块中（先读再重写）
   • 回收整个块，并把它擦除
2. 如何判断有效页？
   • 每个物理页记录它对应的逻辑页地址（OOB区）
   • 查映射表，如果映射表记录的 PPN=该页，是有效页
3. 问题：开销非常大
   • 有效页需要拷贝：先读再重写
   • 开销与有效页所占的比例成正比
4. 解决办法：超配（over-provisioning）
   • 实际物理空间比用户所见空间更大：多15%~45%
     • 例如，用户看到100GB的SSD，实际上内部是120GB
     • GC时将数据写入 over-provisioning space，减少对性能的影响
   • GC一般在SSD后台执行，尽量再设备不忙时执行，但是受限于空闲页的数量
     • 空闲页不足的时候，即使设备忙也需要开始执行GC

块级映射（Block-Level Mapping）

1. 块级映射
   • 逻辑地址空间划分为chunk，chunk size = 擦除块（物理块）size
   • 映射表：chunk# -> 擦除块（物理块）地址 PBN
2. 读一个逻辑页
   • 逻辑页地址 = chunk# || 偏移
   • 用chunk#查映射表，获得相应的擦除块地址PBN
   • 物理页地址 = PBN || 偏移
3. 问题：小规模写性能差
   • 写粒度小于擦除块：拷贝有效页（读 & 写），导致写放大
   • 小写很常见：擦除块通常较大（大于256KB）

混合映射（Hybrid Mapping）

1. 思想
   • 将擦除块（物理块）划分为两类：数据块和日志块
   • 写逻辑页时都写入日志块
   • 数据块采用块级映射，数据映射表
   • 日志块采用页级映射，日志映射表
   • 适当的时候把日志块合并为数据块
2. 读一个逻辑页
   • 先查日志映射表，按页级映射的方法
   • 如果没找到，再查数据映射表，按块级映射的方法

合并方式

1. Switch Merge
   • 直接把日志块转成数据块：前提是整个日志块的页序与原数据块中的页序一致
   • 把原来的数据块回收擦除
   • 优点：开销低，只修改映射表信息，无数据拷贝
2. Partial Merge
   • 把数据块中有效页拷贝到日志块：日志块中页序与原数据块中的页序一致
   • 把日志块转成数据块，把原来的数据块回收擦除
   • 有数据拷贝开销
3. Full Merge
   • 分配一个新的日志块，从数据块和日志块分别拷贝有效页到新日志块
   • 把新日志块转成数据块
   • 把原来的数据块和日志块都回收擦除
   • 开销很大：需要拷贝整个物理块的数据（读 & 写）

磨损均衡

1. 目标
   • 让所有块被擦除的次数近似
2. 动态磨损均衡
   • 每次写时，选择擦除次数较少或最少的空闲块
   • 局限性：不同数据的修改频率不同
     • 例子：只写一次的数据（static data），很少写的数据（cold data）
3. 静态磨损均衡
   • 动态磨损均衡不考虑不会被回收的物理块，例如长时间不被修改的物理块（写冷块）
   • 不再被写，不再有磨损
   • 解决办法：FTL定期重写冷块，将其写入磨损较多的块

总结

1. SSD FTL的主要功能
   • 地址映射
   • 垃圾回收
   • 磨损均衡
   • 请求调度
   • 缓存管理
   • 坏块管理

磁盘

1. 持久化的、大容量的、低成本的存储设备：机械、速度慢
   • 多种尺寸：3.5",2.5"
   • 多种容量：100GB ~ 14TB
   • 多种接口
2. 典型的磁盘控制器
   • 与主机的接口
     • SATA,ATA: 面向对延迟、吞吐率要求不高，大容量的场景
     • SAS,SCSI/Ultra-SCSI: 面向低延迟，高吞吐率，高可靠场景
     • FC: Fiber Channel
   • 缓冲：缓冲数据
   • 控制逻辑
     • 读写请求
     • 请求调度
     • 缓存替换
     • 坏块检测和重映射
3. 磁盘的结构
   • 盘片：一组
     • 按固定速率旋转
   • 磁道（Track）
     • 位于盘片表面的同心圆
     • 用于记录数据的磁介质
     • bit沿着每条磁道顺序排列
   • 扇区（Sector）
     • 磁道划分为固定大小的单元，一般为512字节
   • 磁头：一组
     • 用于读写磁道上的数据
   • 磁臂：一组
     • 用于移动磁头（多个）
   • 柱面（Cylinder）
     • 由所有盘片上半径相同的磁道组成
   • Zone
     • 不同磁道的扇区个数不同：外道多，内道少
     • 所有柱面划分为Zone，同一个Zone中每条磁道的扇区数相同
     • 1000-5000个柱面/Zone，其中几个为备用柱面（Spare Cylinder）

磁盘扇区（Sector）

1. 扇区的创建
   • 磁盘格式化
   • 逻辑块地址映射到物理块地址
2. 扇区的格式
   • 头部：ID，损坏标志位，...
   • 数据区：实际用于存储数据的区域，典型大小为 512B
   • 尾部：ECC校验码
3. 坏扇区
   • 发现坏扇区 -> 先用ECC纠错
   • 如果不能纠错，用备用扇区替代
   • 坏的扇区不再使用
4. 磁盘容量
   • 格式化损耗20%左右：每个扇区的头部和尾部 + 坏扇区
5. 读写操作（读写某个柱面的某个扇区）
   • 定位柱面，移动磁臂使磁头对准柱面 -> 寻道seek
   • 等待扇区旋转到磁头下方 -> 旋转 rotation
   • 进行数据读写 -> 数据传输 transfer

磁盘性能

1. 有效带宽 = 数据量 / 耗时

2. 耗时

   • 寻道时间（Seek Time）
     • 把磁头移动到目标柱面的时间
     • 典型：3.5 ~ 9.5ms
   • 旋转延迟（Rotation Delay）
     • 等待目标扇区旋转到磁头下方的时间
     • 典型：7200 ~ 15000 RPM
   • 数据传输时间（Data Transfer Time）
     • 典型传输带宽：70~250 MB/Sec

3. 例如：假设磁盘的 BW = 100MB/s,seek=5ms,rotation=4ms

   • 访问 1KB 数据的总时间 = 5ms + 4ms + 1KB/(100MB/s) = 9.01ms
   • 有效带宽 = 1KB / 9.01ms 远小于 100MB/s
   • 一次传输多少数据有效带宽才能达到磁盘带宽的90%
     • size = BW(rotation + seek)0.9/(1-0.9) = 8.1MB
   • 对于小粒度的访问，时间主要花在寻道时间和旋转时间上
     • 磁盘的传输带宽被浪费
     • 缓存：每次读写邻近的多个扇区，而不是一个扇区
     • 调度算法：减少寻道开销

4. 磁盘缓存

   • 磁盘内通过少量 DRAM 来缓存最近访问的块
     • 典型大小为 64~256MB
   • 由控制器管理，OS无法控制
   • 块替换策略：LRU
   • 优点：如果访问具有局部性，则读性能受益
   • 缺点：需要额外的机制来保障写的可靠性

磁盘调度算法

磁盘寻道算法FIFO(FCFS)

1. 例子
   • 请求到达顺序：11 -> 1 -> 36 -> 16 -> 34 -> 9 -> 12
   • FIFO服务顺序：11 -> 1 -> 36 -> 16 -> 34 -> 9 -> 12
   • FIFO寻道总距离：10 + 35 + 20 + 18 + 25 + 3 = 111
2. 好处
   • 公平性
   • 磁盘请求的服务顺序是应用可以续期的
3. 坏处
   • 请求到来的随机性，经常长距离地寻道
   • 可能发送极端情况，比如需要横扫整个磁盘

磁盘寻道算法SSF(Shortest Seek First)

1. 方法
   • 选择磁头移动距离最短的请求（需要缓冲一部分请求）
   • 计入旋转时间
2. 例子
   • 请求到达顺序：11 -> 1 -> 36 -> 16 -> 34 -> 9 -> 12
   • SSF服务顺序：11 -> 12 -> 9 -> 16 -> 1 -> 34 -> 36
   • SSF寻道总距离：1 + 3 + 7 + 15 + 33 + 2 = 61
3. 好处
   • 减少寻道时间
4. 坏处
   • 可能产生饥饿

电梯调度(SCAN/LOOK)

1. 方法
   • 磁头按一个方向到另一端，再折回，按反方向回到这端，不断往返
   • 只服务当前移动方向上寻道距离最近的请求
   • LOOK：如果磁盘移动方向上没有请求，就折回
2. 例子
   • 请求到达顺序：11 -> 1 -> 36 -> 16 -> 34 -> 9 -> 12
   • SCAN服务顺序：11 -> 12 -> 16 -> 34 -> 36 -> 9 -> 1
   • SCAN寻道总距离：1 + 4 + 18 + 2 + 27 + 8 = 60
3. 好处
   • 消除饥饿、请求的服务时间有上限
4. 坏处
   • 反方向的请求需等到更长时间

环路电梯调度(C-SCAN/C-LOOK)

1. 方法
   • 将SCAN改为折回时不服务请求，立即回到磁盘最外层重新向内扫描
   • 寻道类似连起来成一个环
2. 好处
   • 服务时间趋于一致
3. 坏处
   • 折回时不干事

磁盘调度算法对比

1. 调度算法
   • FIFO：实现简单，但寻道时间长
   • SSF：贪心算法，可能造成饥饿现象（距离初始磁头位置较远的请求长期得不到服务）
   • SCAN/LOOK：减少饥饿
   • C-SCAN/C-LOOK：减少SCAN算法返回时的扫描开销
2. 磁盘I/O请求缓冲
   • 把请求缓冲在控制器缓冲区
   • 缓冲时间取决于缓冲区大小
3. 进一步的优化
   • 既寻道最短，又旋转延迟最短

RAID(Redundant Array of Independent Disks)

1. 主要思想
   • 由多个磁盘构成一个存储设备
2. 好处
   • 提高性能：多个磁盘并行工作
   • 增加容量：聚合多个磁盘的空间
   • 提高可靠性：数据冗余，有磁盘损坏时，数据不损坏
3. 坏处
   • 控制器变得复杂
4. 牵扯的问题
   • 多块盘做块映射：逻辑块LBN -> <磁盘#,块#>
   • 如何通过冗余机制保护数据可靠性

RAID-0

RAID Level 0

1. 以条带（Stripe）为粒度映射到N块磁盘（轮转方式），条带宽度为N，即有N个条（strip）组成
2. 1个Strip=K个块，即1个条由K个块组成
3. 容量
   • N * 单个磁盘容量（无冗余）
4. 可靠性
   • （单个磁盘可靠性）^ N
5. 性能：
   • 带宽：N * 单个磁盘带宽
   • 延迟：单个磁盘延迟

RAID Level 1

1. 以镜像的形式存储
   • 镜像级别R：数据保存R份
2. 通常与RAID-0结合使用
   • RAID-01 或 RAID-10
3. 容量
   • (N * 单个磁盘容量) / R
4. 可靠性
   • 容忍任何一个磁盘坏
   • 特殊情况下可以容忍N/R的磁盘坏
5. 性能
   • 写带宽：(N * 单个磁盘带宽) / R
   • 读带宽：N * 单个磁盘带宽
   • 延迟：单个磁盘延迟

RAID Level 4

1. 条带化 + 1个校验块
   • 所有校验块在同一块磁盘上（校验盘）
   • 缺点：校验盘为写性能瓶颈，易损坏
2. 每次写数据都需要更新校验快
   • 方法一：读所有的数据盘
     • 并行读所有磁盘的对应块
     • 计算新校验块
     • 并行写新块和新校验块
   • 方法二：读一个数据盘和校验盘
     • 并行读旧块和旧校验块
     • 计算新校验块
       • Pnew = (Bold ^ Bnew) ^ Pold
     • 并行写新块和新校验块
3. 容量
   • (N - 1) * 单个磁盘容量
4. 可靠性
   • 容忍任何一块磁盘坏
   • 用XOR重构坏盘数据
5. 延迟
   • 读延迟等于单个磁盘的延迟
   • 写延迟约等于2倍单个磁盘的延迟
6. 带宽
   • 读带宽 = (N-1)*单个磁盘带宽
   • 校验盘为写瓶颈，所有校验块串行写

RAID Level 5

1. 条带粒度映射 + 1个校验块
   • 校验块分散在不同磁盘上
   • Rebuild：复杂 & 速度慢
2. 写带宽
   • 写并行：校验块并行写
   • 写带宽：(N*单个磁盘带宽) / 4
3. 读带宽
   • 正常状态：只读数据块
   • 读带宽：N*单个磁盘带宽

其他RAID级别

1. RAID Level 2
   • 按位为粒度映射 + ECC
   • 每4位 + 3位海明码
   • 所有磁盘同步读写：寻道 + 旋转
2. RAID Level 3
   • 按位为粒度映射 + Parity位
   • 已知坏磁盘时，可纠错
3. RAID Level 6
   • 条带粒度映射 + 2个校验块
   • 能容忍两块磁盘同时坏

卷管理（Volume Manager）

1. 虚拟块设备
   • 在多个磁盘上创建一个或多个逻辑卷
   • 逻辑卷：一个虚拟块设备
   • 采用RAID技术将逻辑卷的块地址映射到物理设备
2. 好处
   • 提供虚拟的容量和性能
   • 容错
3. 实现
   • OS内核的逻辑卷管理
     • Windows MacOS Linux等
   • 存储设备控制器（存储系统）
     • EMC Hitachi HP IBM NetApp
     • 接口：PCIe iSCSI FC等