理解Dhara的架构和设计

Dhara 是一个针对资源受限的系统设计的用于管理 Nand Flash 的 FTL，本文对它的架构和设计进行 简单介绍。

原项目地址：https://github.com/dlbeer/dhara

1. 功能特点

• 完美磨损均衡：任意两个块之间的擦除次数差异不超过1次;
• 支持Trim操作：不再需要的逻辑扇区可移除以提高性能；
• 数据完整性：逻辑扇区的写和移除具有原子性，意外掉电 发生后可从最后一个已同步状态回滚；
• 实时性：所有操作包括启动在最坏情况下的时间复杂度为O(log n) (假设坏块符合均匀分布， n 为 Flash 容量)。

2. 整体架构

作为一个log-structured FTL，Dhara 整体架构分层如下：

逻辑块映射作为FTL的顶层实现了对Nand Flash物理扇区读写 的抽象，使其可以按逻辑扇区的方式读写；此外，该层还通过 下层的日志结构机制实现坏块恢复和垃圾回收功能。

日志结构实现一个常驻Flash的队列，包含入队和出队两种基本 操作。入队时将页数据加上固定大小的标签（元数据）添加到队头； 出队时将页数据从队尾移除。

Nand 抽象层提供Flash操作相关接口，如读/写/擦除/页复制等。

3. 基本原理

3.1 Functional Radix Tree

将物理页号和逻辑扇区关联起来，考虑使用每层最多两个分支的 functional基数树，逻辑扇区地址位数为4，记录4个逻辑扇区0000， 0001，1000和1010的树如下所示：

假设需要更新键1010对应的值，需要新增与从根到叶对应的新节点， 其中所有的非叶节点，如果其对应的旧节点分支路径非空，则重复 使用该分支路径，如下图所示：

图中使用*标记的节点无法通过新的根节点到达，为待回收的垃圾。

3.2 Alt-pointer 队列

Dhara 实际使用alt-pointer队列来存储以上的基数树，考虑逻辑 扇区地址位数为4，树的深度H为4的情况，每增加一个逻辑扇区， 需要存储以下数据：

• {s0, s1, s2, …, s(H - 1)}: bit数组，表述逻辑扇区地址；
• {A0, A1, A2, …, A(H -1)}: alt-pointer数组；
• 该逻辑扇区存储的数据。

alt-pointer数组中的每一项Ak，要么为空，要么指向与该数组对应 的逻辑扇区地址共享前k bit的最新记录。以前面的基数树为例， 从仅有一条记录开始：

所有的alt-pointer均为空，因为此时还未有其他记录。现在增加 一条与逻辑扇区0000对应的记录：

新记录仅有一个非空的alt-pointer，指向前一条记录，两条记录 的逻辑扇区地址具有3个bit的共同前缀。同理，增加记录1010和1000， 注意第3和第4条记录与第0 bit对应的alt-pointer均指向第2条记录：

现在需要修改逻辑扇区1010的内容，添加一条新纪录：

现在与逻辑扇区1010对应的记录有两条，但仅有最右边的记录是有效的。 有效记录的查找方法如下：

• 从最右边（即最新）的记录开始
• for i = 0, 1, …, H - 1:
  • 如果当前记录为空：
    • 返回记录未找到（NOT-FOUND）
  • 如果目标扇区地址第i bit与当前记录的扇区地址第i bit 不同：
    • 跟随alt-pointer i，取它所指向的记录作为新的当前记录
• 返回当前记录

更新记录的方法类似与查找，在查找的过程中逐渐构建一个alt-pointer 数组A[H]：

• 从最右边（即最新）的记录开始
• for i = 0, 1, …, H - 1:
  • 如果当前记录为空：
    • 将数组A[H]中所有的元素置为空
    • 结束
  • 如果待更新目标记录的bit i 与当前记录的bit i不同：
    • 将A[i]设置为当前记录的页号
    • 跟随alt-pointer i，取它所指向的记录作为新的当前记录
  • 否则：
    • 将A[i]设置为当前记录的第i个alt-pointer

3.3 数据在Flash中的存储

假设某个Flash每个块有16个页，存储元数据（metadata）的页 为检查点（check point），3个存放逻辑扇区数据的页和1个检查点 构成一个检查组，则该Flash 块存放数据的形式如下：

其中data为用户数据，cp为前3个页的检查点metadata。

Dhara 使用一个循环队列来管理Flash中所有的页，更新逻辑扇区数据， 垃圾回收，坏块恢复等需要更新记录的操作会使队头或队尾指针移动。 在日志中添加记录时，只有完整写完一个检查组才认为记录已同步， 能够在经过掉电之后恢复。

检查点的数据组织形式如下：

cookie 记录在写该检查点时，FTL已保存的有效扇区数；

meta1, meta2, … metaN 是该检查点所在检查组数据页 对应的metadata，检查组包含4个页时，N为3。

检查点头部header内容如下：

• “Dha"是用于识别检查点头部的魔法数；
• epoch：记录循环队列形式的日志，队头指针经过Flash最后一个页 并回到开头的次数；
• tail：队尾所指向的页；
• bb_current：队头前方的坏快数量；
• bb_last：队头后方预计有多少个坏块。

Dhara映射结构中每个逻辑扇区对应Flash上的一个页，与数据页 对应的metadata记录逻辑扇区id和alt-pointer数组， 假设逻辑扇区地址位数占32位， 则检查点中每个metadata保存 4字节的id和32个alt-pointer，总共占132字节，形式如下：

3.4 垃圾回收

通过以上所述的alt-pointer队列，Dhara实现了日志结构，在 更新逻辑扇区数据时执行入队操作，在移除不再需要的记录 时执行出队操作以释放空间。

考虑状态如下所示的日志：

注意到最左侧即队尾的记录0001，按照在日志中查找记录0001 的流程，可在队首查找到一条更新的记录，队尾的0001为垃圾。

日志结构有这样的规律：在队尾的记录，如果它不是最新的记录， 那么它可以出队移除。

最左侧的0001出队之后，日志如下：

注意到记录0001也存在重复，但无效的记录不位于队尾。此时 可以执行一系列repack操作，取无效记录左侧的记录执行入队 操作，使左侧的记录也成为无效记录，如下：

此时位于左侧的记录0000和0001均为无效记录，依次执行出队 操作后最新的记录不再包含垃圾：

垃圾回收方法总结如下：

• 初始化S为日志最左侧记录的逻辑扇区地址
• 查找有效记录S得到它在日志中的位置，记为P
• 如果P在队列最左侧：
  • 重写S
• 最左侧记录出队

重复以上执行以上步骤足够多次后日志中所有的垃圾均可移除。

3.5 避免日志溢出

日志所能存放的最大记录数量，记为Cj，选择一个整数R >= 1， 称为GC速率（collection ratio），规定日志所能存放最多有 效记录数（即FTL能够管理的逻辑扇区数）如下：

Cm = Cj * R / (R + 1)

在日志操作过程中同时对有效记录数进行计数，确保有效记录数 始终不超过Cm。将日志当前长度记为Sj，当前有效记录数记为Sm， 每次写日志前，对比Sj和Sm，如果Sj >= Sm，则执行R次垃圾回收。

3.6 同步

日志每若干次入队操作后会周期性达到同步；在逻辑映射层提供了 立即同步的方法，需要同步时，可重复执行垃圾回收操作直到同步点。 如果日志中没有记录，在队头填充若干记录直到同步点。

3.7 坏块恢复

在日志执行入队操作时，如果出现坏块，需要进行恢复操作。 坏块恢复操作如下：对于坏块中所有已写记录，如果该记录 不是最新的，直接跳过，否则将其复制到队头的新块。坏块 中所有的有效记录完成移动后，如果还未达到同步点，在队头 填充记录到同步点。

3.8 无效记录移除

要从基数树中删除某个逻辑扇区对应的节点，查找该节点， 找到第一个符合这样条件的节点N：它包含一颗子树，该子树 仅包含指向待删除扇区的节点，符合该条件的节点N称为“delete-root”。 要删除目标逻辑扇区，执行此操作：重写一条包含delete-root 的新记录，这条新记录属于另外一个逻辑扇区，delete-root对应的 alt-pointer为空。

4. 参考

• Dhara: https://github.com/dlbeer/dhara