磁盘存储
基本概念
- 扇区(Sector): 盘片被分为若干扇区.
- 磁道(Track): 盘片上以盘片中心为圆心, 不同半径的同心圆.
- 柱面(Cylinder): 磁盘中, 不同盘片相同半径的磁道组成的圆柱.
- 磁头(Head): 每个磁盘有两个面, 每个面都有一个磁头.
磁盘组织
- 定位一个扇区, 需要的信息为: 柱面号, 磁头号, 扇区号.
- 现代磁盘驱动器可看作一个一维的逻辑块数组, 逻辑块为最小的传输单位.
磁盘访问时间
寻道时间
寻道时间是指把磁头从当前位置移动到指定磁道上需要的时间. 该时间为启动磁盘的时间 $s$ 与磁头移动 $n$ 条磁道所花费的时间之和.
\[T_s = v \times n + s\]旋转延迟时间
对于硬盘, 旋转速度为 $u$ (单位: 转/秒), 则旋转延迟时间为:
\[T_r = \frac{1}{2u}\]传输时间
传输时间是指把数据读出, 或向磁盘写入数据所经历的时间. 若磁盘旋转速度为 $u$ (单位: 转/秒), 每次读写的字节数为 $b$ , 磁道上的字节数为 $N$ , 则传输时间为:
\[T_t = \frac{b}{u\cdot N}\]总访问时间
\[T_{\text{all}}=T_s+T_r+T_t=v\cdot n+s+\frac{1}{2u}+\frac{b}{uN}\]其中, 最主要的因素为 $T_s$ 和 $T_r$ .
磁盘调度算法
先来先服务(FCFS)
按访问请求到达的先后次序来提供磁盘服务. 这样做有明显的缺陷: 效率低, 磁头反复移动, 增加了服务时间.
最短寻道时间优先(SSTF)
优先选择距当前磁头最近的访问请求进行服务, 主要考虑寻道优先. 这样做改善了磁盘平均服务时间, 但可能会导致”饥饿”.
扫描(SCAN)
当有访问请求时, 磁头按一个方向移动, 在移动过程中对遇到的访问请求进行服务. 到达最后一个柱面后, 调转方向, 为经过的访问请求服务, 如此反复.
这样的做法克服了SSTF的缺点, 既考虑了距离, 又考虑了时间. 但由于是摆动式的扫描方法, 两侧磁道被访问的频率仍低于中间磁道, 引发了不公平的现象.
循环扫描(C-SCAN)
与SCAN算法不同, C-SCAN到达最后一个柱面后, 立即带动磁头快速返回0号柱面, 返回时不为任何请求服务, 再从0号柱面开始向外扫描.
C-SCAN算法可以克服SCAN算法中对两端磁道请求的不公平.
查看(LOOK)与循环查看(C-LOOK)
SCAN 与 C-SCAN 总是扫描到最里或最外的磁道才调转.
可以将SCAN(或C-SCAN)改进为LOOK(或C-LOOK). 区别在于: 当移动方向上不再有请求时, 就调转方向, 不会一直移动到最里/最外磁道才调转.
磁盘可靠性 - RAID
RAID: Redundant Arrays of Inexpensive Disks. 廉价冗余磁盘阵列.
- 利用冗余技术来提高可靠性
- 利用并行提高性能
RAID是一种将多块独立磁盘按照不同方式组合起来形成的一个磁盘组, 从而提高比单个磁盘更高的存储性能和提供数据冗余的技术. 组成磁盘阵列的不同方式称为RAID级别. 数据冗余的功能是指用户数据一旦发生损坏, 利用冗余信息可以使得损失数据得以恢复, 从而保障用户数据的安全性.
- 成本低, 功耗小, 传输速率高.
- RAID与传统的大直径磁盘驱动器相比, 在同样的容量下, 价格要低许多.
- RAID让很多磁盘驱动器并行传输数据, 比单个磁盘驱动器提高几倍, 几十倍甚至上百倍的速率. 有效缓解了告诉的CPU与低速磁盘之间的矛盾.
- 容错
- 普通磁盘驱动器只能通过CRC校验码提供简单容错, RAID建立在每个磁盘驱动器的硬盘容错功能之上, 提供更高的安全性.
RAID0
条带化(Striping): 将一块连续的数据, 分成多个条带写到多个磁盘.
RAID0提供了并行交叉存取, 将数据条带化地存入多块磁盘, 提高了并发读写能力, 但无冗余校验能力.
RAID1
RAID1将每一块数据重复地存入两组磁盘, 两组磁盘互为镜像, 提高了可靠性, 但是有效容量减少了一半.
RAID10
- RAID0+1: 先条带化, 再镜像存储.
- RAID1+0: 先镜像存储, 再条带化.
这种技术下, 仅有一块磁盘损坏是不会引发数据丢失的. 下面讨论 $n(n\in\lbrace m\mid m=2k,k\in\mathbf{N}^+\rbrace)$ 块磁盘中, 有 $2$ 块磁盘损坏时, 数据丢失的概率.
对于RAID0+1, 当某一磁盘损坏时, 则与之位于同一个RAID0组内的磁盘也无法工作(并发读写无法进行), 另一RAID0组内, 任意磁盘的损坏都会导致整个磁盘系统的数据丢失. 这样, 导致其数据丢失的方法数为 $\displaystyle\binom{n/2}{1}\cdot\binom{n/2}{1}$ , 故损坏率为:
\[\left[\binom{n/2}{1}\cdot\binom{n/2}{1}\right]/\binom{n}{2}=\frac{n^2}{4}\cdot\frac{2}{n(n-1)}=\frac{n}{2n-2}\]对于RAID1+0, 当某一磁盘损坏时, 位于同一RAID1组的另一磁盘可以工作, 只有当同一组另一磁盘也损坏时, 才会导致整个磁盘系统的数据丢失. 这样, 导致其数据丢失的方法数为 $\displaystyle\binom{n/2}{1}$ , 故损坏率为:
\[\binom{n/2}{1}/\binom{n}{2}=\frac{n}{2}\cdot\frac{2}{n(n-1)}=\frac{1}{n-1}\]RAID2
RAID2采用海明码纠错的磁盘阵列, 将数据位交叉写入几个磁盘中. 按位条带化.
校验码
- 奇偶校验:
- 偶校验: $P=a_0\oplus a_1\oplus\dotsm\oplus a_{n-1}$
- 奇校验: $P=\lnot(a_0\oplus a_1\oplus\dotsm\oplus a_{n-1})$
- 海明码:
- 多重奇偶校验系统.
一般而言, 若海明码长为 $n$ , 信息承载位数为 $k$ , 监督位数为 $r=n-k$ , 则要求:
\[2^r\ge k+r+1\Leftrightarrow 2^r\ge n+1\]XOR数据恢复原理
可以证明:
- $\oplus$ 运算是符合交换律和结合律的.
-
若 $a_0=a_1\oplus a_2\oplus\dotsm\oplus a_{n-1}$ , 则有:
\[a_i=\bigoplus_{k\neq i}a_k\]
RAID容错的原理就是利用了XOR运算的这些特点. 例如: a, b, c, d为四块磁盘上的数据, 其中3个为应用信息数据, 剩余的一个为校验码. 则其中任意一个丢失时, 都可以利用其它三个做XOR运算得到. 实际上, 阵列控制器一般要先把磁盘分为若干条带, 然后再对每组条带做XOR运算.
RAID2的特点
- 并行读写, 各个驱动器并行工作.
- 使用海明码来进行错误检测和纠正, 数据传输率高.
- 需要多个磁盘来存放海明码, 冗余磁盘数量和数据磁盘数量的对数成正比.
RAID2是一种在多磁盘易出错环境中的有效选择, 并未被广泛使用.
RAID3
RAID3采用奇偶校验冗余磁盘阵列, 也采用数据位交叉, 阵列中只有一个校验盘.
- 将磁盘分组, 采用字节级别的条带, 读写需要访问所有磁盘.
- 校验盘一般采用奇偶校验.
- 简单地理解: 先将分布在各个数据盘上的一组数据加起来, 将和存放在校验盘上. 一旦某一个盘数据丢失, 只要将校验盘上的和减去正确盘上的数据, 得到的差就是错误盘上的数据.
RAID3 恢复数据的时间较长, 存在读写性能的水桶效应瓶颈.
RAID4
RAID4采用并行处理磁盘阵列: 一种独立传送磁盘阵列, 采用数据块交叉, 采用一个校验盘, 将数据按块交叉存储在多个磁盘上.
- 冗余代价与RAID3相同
- 访问数据的方法与RAID3不同
- 在RAID3中, 一次磁盘访问将对磁盘阵列中所有磁盘进行操作.
- 在RAID4中, 可以使用较少的磁盘参与操作, 以使磁盘阵列可以并行地进行多个数据的磁盘操作.
- 随机读快, 随机写慢.
RAID5
RAID5采用独立传送磁盘阵列: 采用数据块交叉和分布式冗余校验, 将数据和校验都分布地存放在各个磁盘中, 没有专门的奇偶校验驱动器.
RAID6
RAID6采用双维校验独立存取盘阵列: 数据以块交叉方式存放于各个磁盘中, 校验码均匀分布在所有磁盘中.
- 写入数据需要访问1个数据盘, 2个校验盘.
- 可容忍两个磁盘出错.
- 校验开销是RAID5的两倍.
提高磁盘I/O速度
提高 I/O 速度的主要途径:
- 提高磁盘性能
- 提高并行度
- 采用适当的调度算法
- 设置高速缓冲
缓存
- 磁盘高速缓存的形式
- 独立缓存(固定大小)
- 虚拟内存(可变大小)
- 数据交付
- 直接交付(拷贝)
- 指针交付(需进行内存管理)
- 置换算法
- 周期性写回
数据布局
- 优化物理块分布
- 连续摆放, 使得磁头移动距离最小.
- 优化索引结点的分布
- 将磁盘上所有的磁道分为若干组, 每一组内都有索引结点, 物理数据块和空闲盘块表, 使得索引结点和存放文件的数据块之间的距离最小.
其他方法
- 提前读
- 延迟写
- 虚拟磁盘
- 利用内存来仿真磁盘(RAM)
磁盘空间管理
可以视为对内存管理部分中闲置空间管理的补充.
主要有四种方法:
- 空闲表法
- 空闲链表法
- 位图法
- 成组链接法.
其中成组链接法示意图如下:
