filesystems - Flash Translation Layer 如何存储映射数据、不可用块和超级块?
问题描述
ftl
有非flash的私有存储空间吗?</p
>
如果没有,如何ftl
在避免wear leveling
.
其实我不知道里面有没有超级块ftl
,但是如果要定位映射数据和物理地址变化频繁的不可用块,可能需要某个物理地址。这个物理地址上的内容肯定会经常变化,如何避免这个物理地址的磨损均衡呢?
解决方案
这个问题有很多可能的解决方案,并且它与驱动器用于存储其数据的数据表示非常交织在一起,所以我相信它会因驱动器/制造商而有很大不同。我将概述一种可行的通用方法。
假设您设计了一个 FTL,它维护几个固定大小、仅附加的“日志”,为简单起见,我们总是有一个所有写入都附加到的“活动”日志。如果用户发出随机写入,则活动日志中 LBA 的顺序也将是随机的。当活动日志填满分配给它的所有空间时,它会“冻结”,我们将活动日志切换到闪存中其他地方的一些空日志。随着冻结日志中的数据变得陈旧,我们最终需要通过在擦除原始数据之前将任何仍然引用的块复制到不同的日志来对其进行垃圾收集,以便可以将其重新用于新的写入。
现在,对于每次写入日志,到目前为止,我们界面中的任何内容都不需要块正好是 4KiB(或其他),因此您可以在数据上附加一个小标题,告诉您它的 LBA 是什么,也许还有一些其他元数据-- 写入序列号,以便您可以判断它是否是块的最新副本,并且可能是用于读取完整性检查的校验和。写入完成后,您会使用已更新 LBA 的新位置(SSD 内的 RAM,显然不是计算机主 CPU 的 RAM)来更新映射的 RAM 内副本。
如果 FTL 崩溃或断电,您可以通过读取所有日志中的所有标头来重建映射。缺点是扫描日志会扩展O(number of logs * number of blocks per log)
,因此您可以以某种方式对其进行优化:
- 您可以自己将标头写入磁盘的单独部分,这样您就可以在不读取用户数据的情况下扫描它们(相同的 big-O 运行时,但在实践中要快得多)
- 您可以定期将映射的内存副本刷新到某个地方,以及最新的 IO 序列号,这样您只需读取自最新映射刷新以来写入的日志部分
- 您如何找到开始扫描的日志部分?对日志头中的 IO 序列号进行二进制搜索。所以现在启动运行时
O(number of logs * (log_2(number of blocks per log) + number of blocks that need to be scanned))
- 你怎么知道什么时候停止扫描?要么你认识到你读取的块中的所有数据都是 1,因为那部分日志还没有被写入,要么你认识到校验和和数据不匹配。
- 小优化:在干净关机期间,始终将地图写入flash,这样二分查找+扫描只需要在崩溃或不干净关机时进行。
- 您如何找到开始扫描的日志部分?对日志头中的 IO 序列号进行二进制搜索。所以现在启动运行时
到目前为止,这大大降低了您需要编写地图的频率,但是对于使用寿命很长的驱动器而言,将其覆盖到固定位置仍然可能过于频繁。为了解决这个问题,我们必须在我们写地图的地方循环:
- 最简单的解决方案是指定一小组 X 特殊日志来存储所有地图数据并像循环缓冲区一样写入它们,其中选择 X 以使地图更新持续到设备的预期生命周期。要在启动时在日志中查找最近的映射,您需要在这些日志中进行二进制搜索以找到最后写入的映射。所以启动=
O(X * log_2(number of maps per log) + runtime to scan the other logs if unclean shutdown)
。 - 可能是一种更优化的解决方案(但可能更复杂),将映射直接写入发生更新的日志中。然后你需要一些方法来找到映射在启动时的位置——最明显的方法是将映射写入每个活动日志的开头,或者你可以通过在块中添加反向指针来允许任意映射写入指向日志中最新地图的标题。
另一个方面是完整的地图刷新可能很昂贵,如果它干扰用户 IO 的性能,这会增加尾部延迟——允许增量更新会更好吗?那时您开始考虑使用诸如日志结构合并 (LSM) 树之类的东西来存储您的地图,这样每次增量写入都非常小,您可以分摊完整的地图写入成本。
显然,这个解释遗漏了许多微小的细节,但希望这足以让你开始。:-)
推荐阅读
- java - 如何为不同的分辨率更改 Java swing GUI?
- angular - 如何根据从下拉列表中选择的值禁用文本区域
- laravel - 在循环内添加字段 - Twig - OctoberCMS
- c# - 如何通过 Visual Studio 2008 在 azure DevOps 中构建 C# 代码?
- postgresql - 如何将 Postgres Hstore 数据类型转换为雪花对象或变体
- azure - 该地区德语到英语翻译的问题
- gitlab - 如何通过命令查看 gitlab 用户?
- google-cloud-platform - 将 Firebase 项目添加到 GCP 项目
- python-3.x - snowflake.connector.errors.InterfaceError:252005:无法转换当前行,原因:
返回带有错误集的结果 - node.js - Firestore:如何使用模拟器测试导出到存储?