BTT - 块转换表

1. 简介

基于持久内存的存储能够以字节（或更准确地说，缓存行）粒度执行 IO。 但是，我们经常希望将此类存储公开为传统块设备。 持久内存的块驱动程序将完全做到这一点。 但是，它们不提供任何原子性保证。 传统的 SSD 通常在硬件中提供针对扇区撕裂的保护，使用电容器中存储的能量来完成正在进行的块写入，或者可能在固件中。 我们没有持久内存的这种奢侈 - 如果写入正在进行中，并且我们遇到电源故障，则该块将包含新旧数据的混合。 应用程序可能没有准备好处理这种情况。

块转换表 (BTT) 为持久内存设备提供原子扇区更新语义，以便依赖于扇区写入不被撕裂的应用程序可以继续这样做。 BTT 将自身表现为堆叠的块设备，并为元数据保留部分底层存储。 其核心是一个间接表，用于重新映射卷上的所有块。 它可以被认为是一个极其简单的文件系统，仅提供原子扇区更新。

2. 静态布局

可以布置 BTT 的底层存储在任何方面都不受限制。 但是，BTT 将可用空间分成最大 512 GiB 的块，称为“Arenas”。

每个 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

映射到内部“postmap”块

随后将使用的一些术语

外部 LBA

LBA 向上层公开。

ABA

Arena 块地址 - arena 中的块偏移量/编号

Premap ABA

arena 中的块偏移量，这是通过范围检查外部 LBA 决定的

Postmap ABA

从映射间接寻址后在“数据块”区域中获得的块号

nfree

在任何给定时间维护的空闲块数。 这是可以对 arena 进行的并发写入次数。

例如，在添加 BTT 之后，我们浮现一个 1024G 的磁盘。 我们得到对 768G 处外部 LBA 的读取。 这属于第二个 arena，并且在这个 arena 贡献的 512G 块中，这个块位于 256G。 因此，premap ABA 是 256G。 我们现在参考映射，并找出块 'X' (256G) 的映射指向块 'Y'，例如 '64'。 因此，postmap ABA 是 64。

b. BTT Flog

BTT 通过使每次写入都成为“分配写入”来提供扇区原子性，即每次写入都转到“空闲”块。 空闲块的运行列表以 BTT flog 的形式维护。 ‘Flog’ 是 “free list” 和 “log” 这两个词的组合。 flog 包含 ‘nfree’ 个条目，一个条目包含

lba

正在写入的 premap ABA

old_map

旧的 postmap ABA - 在 'this' 写入完成后，这将是一个空闲块。

new_map

新的 postmap ABA。 映射将更新以反映此 lba->postmap_aba 映射，但我们在此处记录它，以防我们需要恢复。

seq

序列号，用于标记此 flog 条目的 2 个部分中的哪一个有效/最新。 它在正常操作下在 01->10->11->01 (二进制) 之间循环，00 表示未初始化状态。

lba’

备用 lba 条目

old_map’

备用旧的 postmap 条目

new_map’

备用新的 postmap 条目

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 的映射以指向其新的 postmap ABA。 此时，读取器（仍然）正在读取的内部 postmap 块已插入到空闲块列表中。 如果另一个写入进入相同的 LBA，它可以获取此空闲块，并开始写入它，导致读取器读取不正确的数据。 为了防止这种情况，我们引入了 RTT。

RTT 是一个简单的、每个 arena 的表，具有 ‘nfree’ 个条目。 每个读取器都将其正在读取的 postmap ABA 插入到 rtt[lane_number] 中，并在读取完成后清除它。 每个写入器线程在获取空闲块后，都会检查 RTT 中是否存在它。 如果 postmap 空闲块位于 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 与映射条目匹配，则 log_entry.old 是空闲的。

  • 如果 log_entry.new 与映射条目不匹配，则 log_entry.new 是空闲的。 （这种情况只能由电源故障/不安全关机引起）

g. 总结 - 读取和写入流程

读取

  1. 将外部 LBA 转换为 arena 编号 + pre-map ABA

  2. 获取通道（并获取 lane_lock）

  3. 读取映射以获取此 pre-map ABA 的条目

  4. 将 post-map ABA 输入到 RTT[lane] 中

  5. 如果在映射中设置了 TRIM 标志，则返回零并结束 IO（转到步骤 8）

  6. 如果在映射中设置了 ERROR 标志，则以 EIO 结束 IO（转到步骤 8）

  7. 从此块读取数据

  8. 从 RTT[lane] 中删除 post-map ABA 条目

  9. 释放通道（和 lane_lock）

写入

  1. 将外部 LBA 转换为 Arena 编号 + pre-map ABA

  2. 获取通道（并获取 lane_lock）

  3. 使用通道索引到内存中的空闲列表并获得一个新块、下一个 flog 索引、下一个序列号

  4. 扫描 RTT 以检查是否存在空闲块，如果存在，则旋转/等待。

  5. 将数据写入此空闲块

  6. 读取映射以获取此 pre-map ABA 的现有 post-map ABA 条目

  7. 写入 flog 条目：[premap_aba / old postmap_aba / new postmap_aba / seq_num]

  8. 将新的 post-map ABA 写入映射。

  9. 将旧的 post-map 条目写入空闲列表

  10. 计算下一个序列号并写入空闲列表条目

  11. 释放通道（和 lane_lock）

4. 错误处理

如果任何元数据因错误或介质错误而无法恢复地损坏，则 arena 将处于错误状态。 以下条件指示错误

  • Info 块校验和不匹配（并且从副本恢复也失败）

  • 所有内部可用块都不能被映射块和空闲块（来自 BTT flog）的总和唯一且完全地寻址。

  • 从 flog 重建空闲列表会显示缺少/重复/不可能的条目

  • 映射条目超出范围

如果遇到任何这些错误情况，则使用 info 块中的标志将 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。

[1]: https://github.com/pmem/ndctl