BTT - 块转换表¶
1. 简介¶
基于持久内存的存储能够以字节（或更准确地说，以缓存行）粒度执行 IO。然而，我们通常希望将这种存储公开为传统的块设备。用于持久内存的块驱动程序将完全做到这一点。但是，它们不提供任何原子性保证。传统的 SSD 通常在硬件中使用电容器中存储的能量来完成正在进行的块写入，或者在固件中使用电容器，从而提供针对损坏扇区的保护。我们没有持久内存的这种奢侈 - 如果写入正在进行中，并且我们遇到电源故障，则该块将包含旧数据和新数据的混合。应用程序可能没有准备好处理这种情况。
块转换表 (BTT) 为持久内存设备提供原子扇区更新语义，以便依赖于扇区写入不被损坏的应用程序可以继续这样做。BTT 将自身表现为堆叠的块设备，并为其元数据保留底层存储的一部分。其核心是一个重映射卷上所有块的间接表。它可以被认为是一个极其简单的文件系统，它只提供原子扇区更新。
2. 静态布局¶
可以布局 BTT 的底层存储在任何方面都没有限制。但是，BTT 将可用空间分成最大 512 GiB 的块，称为“Arena”。
每个 arena 的元数据都遵循相同的布局，并且 arena 中的所有引用都属于其内部（除了指向下一个 arena 的一个字段）。以下描述了“磁盘上”元数据布局
Backing Store +-------> Arena
+---------------+ | +------------------+
| | | | Arena info block |
| Arena 0 +---+ | 4K |
| 512G | +------------------+
| | | |
+---------------+ | |
| | | |
| Arena 1 | | Data Blocks |
| 512G | | |
| | | |
+---------------+ | |
| . | | |
| . | | |
| . | | |
| | | |
| | | |
+---------------+ +------------------+
| |
| BTT Map |
| |
| |
+------------------+
| |
| BTT Flog |
| |
+------------------+
| Info block copy |
| 4K |
+------------------+
3. 操作理论¶
a. BTT 映射¶
映射是一个简单的查找/间接表，它将 LBA 映射到内部块。每个映射条目为 32 位。最高有效两位是特殊标志，其余部分构成内部块号。
位 |
描述 |
|---|---|
31 - 30 |
错误和零标志 - 按以下方式使用 == == ====================================================
31 30 Description
== == ====================================================
0 0 Initial state. Reads return zeroes; Premap = Postmap
0 1 Zero state: Reads return zeroes
1 0 Error state: Reads fail; Writes clear 'E' bit
1 1 Normal Block – has valid postmap
== == ====================================================
|
29 - 0 |
映射到内部“后映射”块 |
一些后续将使用的术语
外部 LBA |
对上层可见的 LBA。 |
ABA |
Arena 块地址 - arena 内的块偏移/编号 |
前映射 ABA |
arena 的块偏移量，它是通过范围检查外部 LBA 来确定的 |
后映射 ABA |
从映射间接获得的“数据块”区域中的块号 |
nfree |
在任何给定时间维护的空闲块的数量。这是可以同时发生对 arena 的并发写入的数量。 |
例如，在添加 BTT 之后，我们表面化一个 1024G 的磁盘。我们获得对 768G 处的外部 LBA 的读取。这属于第二个 arena，并且在该 arena 贡献的 512G 块中，此块位于 256G 处。因此，前映射 ABA 为 256G。现在我们参考映射，并找出块 'X' (256G) 的映射指向块 'Y'，例如 '64'。因此，后映射 ABA 为 64。
b. BTT Flog¶
BTT 通过使每次写入成为“分配写入”来提供扇区原子性，即每次写入都转到“空闲”块。以 BTT flog 的形式维护空闲块的运行列表。'Flog' 是 “空闲列表”和 “日志” 这两个词的组合。flog 包含 'nfree' 个条目，并且一个条目包含
lba |
正在写入的前映射 ABA |
old_map |
旧的后映射 ABA - 在“此”写入完成后，这将是一个空闲块。 |
new_map |
新的后映射 ABA。映射将更新以反映此 lba->postmap_aba 映射，但是我们在此处记录它，以防我们必须恢复。 |
seq |
序列号，用于标记此 flog 条目的 2 个部分中的哪一个有效/最新。在正常操作下，它在 01->10->11->01（二进制）之间循环，而 00 表示未初始化状态。 |
lba’ |
备用 lba 条目 |
old_map’ |
备用旧后映射条目 |
new_map’ |
备用新后映射条目 |
seq’ |
备用序列号。 |
上述每个字段都是 32 位的，使一个条目为 32 字节。条目也被填充到 64 字节，以避免缓存行共享或别名。flog 更新的完成方式是，对于任何正在写入的条目，它：a. 基于序列号覆盖条目中的“旧”部分；b. 写入“新”部分，使得序列号最后写入。
c. 通道的概念¶
虽然 'nfree' 描述了一个 arena 可以并发处理的并发 IO 的数量，但 'nlanes' 是 BTT 设备整体可以处理的 IO 的数量
nlanes = min(nfree, num_cpus)
通道号是在任何 IO 开始时获得的，并且用于在 IO 期间索引所有磁盘上和内存中的数据结构。如果 CPU 的数量多于可用通道的最大数量，则通道将受到自旋锁的保护。
d. 内存中的数据结构：读取跟踪表 (RTT)¶
考虑这样一种情况，即我们有两个线程，一个进行读取，另一个进行写入。我们可能会遇到这样一种情况，即写入器线程会抓取一个空闲块来执行新的 IO，但（缓慢的）读取器线程仍在从中读取。换句话说，读取器查询了一个映射条目，并开始读取相应的块。写入器开始写入相同的外部 LBA，并完成了写入，更新了该外部 LBA 的映射以指向其新的后映射 ABA。此时，读取器（仍然）正在读取的内部后映射块已被插入到空闲块列表中。如果针对同一 LBA 有另一个写入进入，它可以抓取此空闲块并开始写入，导致读取器读取不正确的数据。为了防止这种情况，我们引入了 RTT。
RTT 是一个简单的、每个 arena 的表，带有 'nfree' 个条目。每个读取器将其正在读取的后映射 ABA 插入到 rtt[通道号] 中，并在读取完成后清除它。每个写入器线程在抓取空闲块后，都会检查 RTT 中是否存在该空闲块。如果后映射空闲块在 RTT 中，它将等待直到读取器清除 RTT 条目，然后才开始写入该块。
e. 内存中的数据结构：映射锁¶
考虑这样一种情况，即两个写入器线程正在写入相同的 LBA。以下步骤的顺序可能会发生竞争
free[lane] = map[premap_aba]
map[premap_aba] = postmap_aba
两个线程都可以使用相同的旧的、释放的 postmap_aba 更新各自的 free[lane]。这通过丢失一个空闲条目并在同时为两个通道复制另一个空闲条目而使布局不一致。
为了解决这个问题，我们可以有一个单一的映射锁（每个 arena），必须在执行上述序列之前获取该锁，但我们认为这可能太有争议了。相反，我们使用一个 (nfree) map_locks 数组，该数组由 (premap_aba modulo nfree) 索引。
f. 从 Flog 重建¶
启动时，我们会分析 BTT 日志（flog）以创建空闲块列表。我们会遍历所有条目，对于每个通道，在两个可能的“节”中，我们始终只查看最新的一个（基于序列号）。重建规则/步骤很简单
读取 map[log_entry.lba]。
如果 log_entry.new 与 map 条目匹配，则 log_entry.old 是空闲的。
如果 log_entry.new 与 map 条目不匹配，则 log_entry.new 是空闲的。（这种情况只能由断电/不安全关机引起）
g. 总结 - 读取和写入流程¶
读取
将外部 LBA 转换为 arena 编号 + pre-map ABA
获取通道（并获取 lane_lock）
读取 map 以获取此 pre-map ABA 的条目
将 post-map ABA 输入到 RTT[lane]
如果 map 中设置了 TRIM 标志，则返回零，并结束 IO（转到步骤 8）
如果 map 中设置了 ERROR 标志，则以 EIO 结束 IO（转到步骤 8）
从此块读取数据
从 RTT[lane] 中删除 post-map ABA 条目
释放通道（和 lane_lock）
写入
将外部 LBA 转换为 Arena 编号 + pre-map ABA
获取通道（并获取 lane_lock）
使用通道索引到内存中的空闲列表并获取新块、下一个 flog 索引、下一个序列号
扫描 RTT 以检查空闲块是否存在，如果存在则自旋/等待。
将数据写入此空闲块
读取 map 以获取此 pre-map ABA 的现有 post-map ABA 条目
写入 flog 条目：[premap_aba / old postmap_aba / new postmap_aba / seq_num]
将新的 post-map ABA 写入 map。
将旧的 post-map 条目写入空闲列表
计算下一个序列号并写入空闲列表条目
释放通道（和 lane_lock）
4. 错误处理¶
如果任何元数据由于错误或介质错误而不可恢复地损坏，则 arena 将处于错误状态。以下情况表明出现错误
信息块校验和不匹配（并且从副本恢复也失败）
所有内部可用块都没有被映射块和来自 BTT 日志的空闲块之和唯一且完全寻址。
从 flog 重建空闲列表会显示缺失/重复/不可能的条目
map 条目超出范围
如果遇到任何这些错误情况，则使用信息块中的标志将 arena 置于只读状态。
5. 用法¶
BTT 可以在 libnvdimm 子系统（pmem 或 blk 模式）公开的任何磁盘（命名空间）上设置。设置此类命名空间的最简单方法是使用“ndctl”实用程序 [1]
例如，使用 4k 扇区大小设置 btt 的 ndctl 命令行是
ndctl create-namespace -f -e namespace0.0 -m sector -l 4k
有关更多选项，请参阅 ndctl create-namespace --help。