1. Redundant Array of Inexpensive Disks (RAID)

11 冗余磁盘阵列 RAID

<aside> 💡 日渐增长的持久存储需求

1. 性能
2. 可靠性 </aside>

A case for redundant arrays of inexpensive disks (RAID) | ACM SIGMOD Record

<aside> 💡 RAID - 一个“反向”的虚拟化

把多个 (不可靠的) 磁盘虚拟成一块非常可靠且性能极高的虚拟磁盘

</aside>

1.1 基本想法

在系统里多接入一块硬盘用于 Fault Tolerance (RAID-1)

• 假设有两块盘 $A, B$
  • 同样规格，共有 $n$ 块
• “镜像” 虚拟磁盘 $V$
  • $V_i \to \{ A_i, B_i \}$ ($1 \le i \le n$)

<aside> 💡 块读写

bread($i$)

• 可以从 $A$ 或 $B$ 中的任意一个读取

bwrite($i$)

• 同时将同样的数据写入 $A$, $B$ 的同一位置

容错，且读速度翻倍 (假设内存远快于磁盘)

</aside>

1.2 Design Space

<aside> 💡 两块磁盘的其他拼接方法

RAID (虚拟化) = 虚拟磁盘块到物理磁盘块的 “映射”

1. 顺序拼接
   • $V_1 \to A_1, V_2 \to A_2, \ldots, V_{n} \to A_{n}$
   • $V_{n+1} \to B_1, V_{n+2} \to B_2, \ldots, V_{2n} \to B_{n}$
2. 交错排列 (RAID-0): 把一个连续读/写分配成每一个磁盘的连续读/写
   • $V_1 \to A_1$, $V_2 \to B_1$
   • $V_3 \to A_2$, $V_4 \to B_2$
   • $V_{2i-1} \to A_{i}$, $V_{2i} \to B_i$

虽然不能容错，但可以利用好磁盘的带宽

</aside>

<aside> 💡 RAID-10 = RAID-0 over RAID-1

RAID: 允许 “多对多” 的映射 (一组映射称为 “条带”, stripe)

• A, B 组成 RAID-1 $X$ (容错)
  • $X_1 \to \{ A_1, B_1 \}$
  • $X_2 \to \{ A_2, B_2 \}$
• C, D 组成 RAID-1 $Y$ (容错)
  • $Y_1 \to \{ C_1, D_1 \}$
  • $Y_2 \to \{ C_2, D_2 \}$
• $X, Y$ 组成 RAID-0 (性能翻倍)
  • $V_1 \to X_1 \to \{ A_1, B_1 \}, V_2 \to Y_1 \to \{ A_2, B_2 \}$
  • $V_3 \to X_2 \to \{ A_2, B_2 \}, V_4 \to Y_2 \to \{ C_2, D_2 \}$ </aside>

1.3 RAID-4: Parity Disk

专门留一块磁盘作为奇偶校验盘。

• $\{V_1, V_2, V_3\} \to \{A_1, B_1, C_1, D_1\}$
• $V_1 \to A_1$, $V_2 \to B_1$, $V_3 \to C_1$ (不容错)
• $D_1 = V_1 \oplus V_2 \oplus V_3$ (奇偶校验)

<aside> 💡 性能分析

Sequential/random read: 3x (75% 总带宽)

Sequential write: 3x (75% 总带宽)

Random write (tricky)

• $D_1 = V_1 \oplus V_2 \oplus V_3$
• 写入任意 $V_1, V_2, V_3$都需要更新 $D_1$
  • 更新 $V_1$ 需要 readb($\{A_1,D_1\}$), writeb($\{A_1,D_1\}$) </aside>