移动设备日志结构文件系统综述

杨梨花; 董勇; 邬会军; 谭支鹏; 王芳; 卢凯

doi:10.7544/issn1000-1239.202330789

移动设备日志结构文件系统综述

杨梨花^1,,
董勇^1, ,,
邬会军¹,
谭支鹏²,
王芳²,
卢凯¹

1.
国防科技大学计算机学院　长沙　410073
2.
信息存储系统教育部重点实验室（华中科技大学）　武汉　430074

基金项目: 全国重点实验室基金项目（2023-KJWPDL-11）；湖南省自然科学基金项目(2024JJ6471，2023RC3021)；国家自然科学基金项目（62306328，U22B2005）；高性能计算国家重点实验室基金项目（202101-03）

详细信息

作者简介:
杨梨花: 1994年生. 博士. 主要研究方向为计算机系统结构、文件系统、移动存储

董勇: 1980年生. 博士，研究员. 主要研究方向为计算机系统结构、并行I/O、文件系统

邬会军: 1991年生. 博士，助理研究员. 主要研究方向为并行文件系统、加速层文件系统、机器学习

谭支鹏: 1973年生. 博士，教授，博士生导师. 主要研究方向为计算机系统结构、大数据存储与管理、移动存储

王芳: 1972年生. 博士，教授，博士生导师. 主要研究方向为并行文件系统、基于非易失存储器件的新型存储系统、网络存储

卢凯: 1973年生. 博士，研究员，博士生导师. 主要研究方向为计算机系统结构、操作系统、安全性研究

通讯作者:
董勇（yongdong@nudt.edu.cn）

中图分类号: TP302.1
计量
- 文章访问数: 201
- HTML全文浏览量: 27
- PDF下载量: 83
出版历程
- 收稿日期: 2023-10-09
- 修回日期: 2024-06-18
- 录用日期: 2024-08-08
- 网络出版日期: 2024-08-15
- 刊出日期: 2024-12-31

Survey of Log-Structured File Systems in Mobile Devices

1.
College of Computer Science and Technology, National University of Defense Technology, Changsha 410073
2.
Key Laboratory of Information Storage System (Huazhong University of Science and Technology), Ministry of Education, Wuhan 430074

Funds: This work was supported by the National Key Laboratory Foundation of China (2023-KJWPDL-11), the Natural Science Foundation of Hunan Province of China (2024JJ6471, 2023RC3021), the National Natural Science Foundation of China (62306328, U22B2005), and the Foundation of State Key Laboratory of High Performance Computing (202101-03).

More Information

Author Bio:
Yang Lihua: born in 1994. PhD. Her main research interests include computer architecture, file system, and mobile storage

Dong Yong: born in 1980. PhD, professor. His main research interests include computer architecture, parallel I/O, and file system

Wu Huijun: born in 1991. PhD, assistant professor. His main research interests include parallel file system, burst buffer file system, and machine learning

Tan Zhipeng: born in 1973. PhD, professor, PhD supervisor. His main research interests include computer architecture, big data storage and management, and mobile storage

Wang Fang: born in 1972. PhD, professor, PhD supervisor. Her main research interests include parallel file systems, new storage systems based on non-volatile storage devices, and network storage

Lu Kai: born in 1973. PhD, professor, PhD supervisor. His main research interests include computer architecture, operating system, and security research

摘要

摘要:
NAND闪存（NAND flash）因为其大容量、轻便、抗震等优异特性，被广泛使用于移动设备. 面向闪存特性设计的闪存友好型文件系统（flash friendly file system，F2FS）是典型的日志结构文件系统（log-structured file system，LFS），它采用日志结构写机制提升了随机写性能，使用前滚恢复技术实现快速的一致性保护，经常被用作移动设备的文件系统. 文件系统因碎片化和段清理问题导致性能下降，而日志结构文件系统的异地更新机制和移动应用的高并发随机同步小写模式进一步加剧了碎片化，导致I/O请求响应变慢、设备运行卡顿. 首先介绍了移动设备日志结构文件系统的相关概念和内容，随后总结了日志结构文件系统碎片化和段清理问题的研究现状. 一方面分析了碎片产生的原因与影响，从预防碎片产生和重整碎片2个角度总结了减少碎片的研究工作. 另一方面分析了冷热数据混合对段清理的影响，从静态分类和动态分类2方面总结了冷热数据区分技术的研究现状，从管理数据分布和调整段清理时机、频率、对象2个角度总结了段清理的研究现状. 最后展望了移动设备日志结构文件系统研究的主要挑战和未来研究工作.
- 日志结构文件系统 /
- 移动存储 /
- 文件碎片 /
- 空闲空间碎片 /
- 段清理 /
- 冷热数据区分
Abstract:
NAND flash is widely utilized in mobile devices due to its excellent characteristics, including large capacity, light weight, and shock resistance. The flash friendly file system (F2FS), designed for flash features, is a typical log-structured file system (LFS). It employs a log-structured write mechanism to enhance random write performance, utilizes roll-forward recovery technology for fast consistency protection, and is commonly used as a file system for mobile devices. However, the performance of file system is impacted by fragmentation and segment cleaning. The out-of-place update mechanism of LFS and the small write mode of high-concurrency and random synchronization of mobile applications exacerbate fragmentation, leading to sluggish I/O request responses and device operation freezes. We initially introduce the relevant concepts and content of log-structured file systems in mobile devices. We then primarily outline the research status of fragmentation and segment cleaning of LFS. Firstly, we analyze the generation and impact of fragmentation, summarize the research work on reducing fragments from the perspectives of preventing fragments and reorganizing fragments. Secondly, we examine the impact of the mixed storage of hot and cold data on segment cleaning. Additionally, we summarize the research status of distinguishing hot and cold data from static and dynamic classification, and segment cleaning from the perspectives of managing data distribution and adjusting the timing, frequency, and objects of segment cleaning. Finally, we outline the main challenges and future research prospects of log-structured file systems in mobile devices.
- log-structured file system /
- mobile storage /
- file fragmentation /
- free space fragmentation /
- segment cleaning /
- hot and cold data distinction

HTML全文

融合机器学习与逻辑推理一直是人工智能（artificial intelligence, AI）领域长期存在且备受关注的问题. 为了克服当前机器学习方法的局限性，许多研究者倡导下一代人工智能需要将数据驱动的机器学习与知识驱动的推理（例如逻辑推理）相结合^[1]. 神经符号学习（neuro-symbolic learning，NeSy）^[2-3]和统计关系人工智能（statistical relational AI）^[4]是近年来这个方向的代表性工作，它们尝试基于一阶逻辑表示的领域知识构建神经网络结构或概率图模型. 另一方面，概率逻辑程序（probabilistic logic program，PLP）^[5]则尝试扩展一阶逻辑以容纳概率逻辑事实，从而实现概率推理.

反绎学习（abductive learning, ABL）^[6-7]是一种将机器学习模型与逻辑推理模型结合的新框架. 该框架可以同时保留双方的完整表达能力：机器学习模型将原始未标记输入数据（例如图像、文本）转换为符号表示的逻辑事实，称为伪标记（pseudo-label），这些伪标记被用作逻辑推理部分的输入. 而一阶逻辑推理模型试图对伪标记进行反绎推理（abductive reasoning），以修正逻辑事实的真值，并用于更新机器学习模型. 由于反绎学习保留了完整的逻辑推理能力，因此它可以直接利用一阶逻辑规则表示的背景知识库，并减少对大量标记数据的需求.

在现有的反绎学习方法中，根据最小化不一致性的原则，会为所有未标记样本生成相应的反绎标记（abduced label）. 具体来说，由于反绎推理是非确定性的，对于每个未标记的样本，可能存在多个反绎标记. 反绎学习基于最小化反绎标记和符号背景知识之间的不一致性的原则来选择最佳的反绎标记. 随后，这些反绎标记会被当作未标记样本的真实标记，与输入示例一起用于更新机器学习模型. 由于机器学习模型预测的伪标记可能存在错误，反绎推理也存在不确定性，因此得到的反绎标记也具有不确定性，不一定与真实标记相同.

反绎标记中可能存在不正确的标记，这可能损害机器学习模型的性能，并且很难被发现. 例如，在手写数字等式识别任务中，若将一个手写数字图片“1”错误地修改为“6”并用于训练机器学习模型. 由于这个错误标记的误导，更新后的模型可能会将很多与数字“1”相似的图片都识别为数字“6”. 这不仅会导致反绎学习的训练速度变慢，还可能使得其中的机器学习模型陷入局部最优解^[8-9]，无法收敛到最优. 由于输入的样本没有真实标记，难以发现隐藏在不确定反绎标记中的错误，这给学习带来了不少困难.

为了解决上述问题，本文定义并设计了针对反绎标记的不确定性. 由于反绎标记同时受到机器学习模型的伪标记以及逻辑推理的影响，我们同时考虑机器学习模型生成伪标记的模型不确定性以及反绎推理的推理不确定性对它的影响. 其中，模型不确定性由分类器输出的置信度（confidence）计算而来，而推理不确定性通过反绎逻辑推理得到的结果集合的大小进行估算. 基于上述反绎标记的不确定性，我们提出了一种带拒绝推理的反绎学习（abductive learning with rejection reasoning，ABL_r）方法. 该方法尝试过滤反绎学习中具有较大不确定性的反绎标记，即若遇到不确定的样本，ABL_r会拒绝反绎推理的结果并抛弃该样本. 我们在若干数据集上进行了实验，验证了本文提出的方法可以拒绝错误的反绎标记，不仅加速反绎学习训练，还能同时带来更好的性能.

1. 相关工作

神经符号学习^[2-3]提出将符号推理与神经网络相结合，以学习从环境中感知并对已感知的信息进行推理. 大多数NeSy方法采用端到端的深度神经网络来建模这一过程，其中使用符号表示的领域知识库构建神经网络结构^[2,10-11]. 然而，这类方法大多用分布式表示替代符号表示，并采用模糊算子近似逻辑推理. 因此，它们通常需要大量的标记训练数据.

PLP^[5]和统计关系学习（statistical relational learning, SRL）^[4,12] 试图在保留逻辑公式的同时为逻辑模型提供了概率语义. PLP通过扩展一阶逻辑使其能进行概率逻辑推理；SRL利用领域知识构建概率图模型结构进行统计推理. 这些方法通常需要直接的语义级别输入，难以应用于如图像等原始数据的输入.

近期，一些研究者提出了建立混合模型的想法，这些方法通常由一个用于机器学习的感知模型和一个用于逻辑推理的推理模型组成. 代表性框架包括DeepProbLog^[13]、反绎学习^[6-7]和神经语法符号模型（neural-grammar-symbolic model, NGS）^[14]. 这些方法中的感知模型负责学习将原始数据转换为原始逻辑事实，作为符号推理的输入；而推理模型则尝试基于给定的知识库推理并修改所感知到的逻辑事实的真值，以更新感知模型. 这2个系统的集成是通过反绎来实现的.

近年来，研究者提出了许多基于反绎学习的方法. ABL^[15]是第1个基于反绎学习框架实现的方法. SS-ABL^[16]将半监督学习与反绎学习结合，并成功应用于法律文书判决任务. GABL^[8]提出了在知识库为具体事实库（ground knowledge base）时的反绎策略及对应的反绎学习方法. Meta_Abd^[9]基于反绎学习，提出了同时学习机器学习模型和一阶逻辑知识库的方法. ABLSim^[17]提出使用集束搜索（beam search）结合相似度加速反绎学习中的一致性优化过程. ABL_nc^[18]提出在开放环境出现新概念时，可对反绎学习的知识库进行知识精化（knowledge refinement）. ABL-KG^[19]提出可以从大规模知识图谱中提取规则库作为反绎学习的知识库.

上述文献[8-9, 16-19]所述的反绎学习相关方法分别关注不同的问题设定，例如在知识库不完备的情况下，如何利用知识图谱或数据等作为知识库的来源. 一般而言，这些方法通过反绎推理修改标记后，会使用所有的反绎标记更新机器学习模型. 与上述方法不同，本文方法假设知识库已知，并选择性地挑选一部分反绎标记用于模型的更新，以提升训练效率和模型性能.

2. 基础知识

本文提出的方法主要基于反绎学习，下面对相关概念和基本知识进行介绍.

2.1 反绎推理

反绎推理是逻辑推理的一种基本形式，它尝试通过逻辑蕴含关系寻求一个假设，以解释观察到的现象. 为了更清晰地阐述，本文将逻辑符号表示为：“ $\wedge$ ”表示合取（逻辑与）；“ $\vee$ ”表示析取（逻辑或）； “ $\leftarrow$ ”表示蕴涵，即若“ $\leftarrow$ ”右侧的前提成立，则左侧的结论成立. 例如，考虑以下命题逻辑规则：

$草地湿\leftarrow 昨晚下雨\vee 洒水器开启 \text{，}$

(1)

$鞋子湿\leftarrow 草地湿 \text{，}\qquad\qquad\qquad\;\;$

(2)

$\qquad\;\;假\leftarrow 昨晚下雨\wedge 洒水器开启 \text{，}$

(3)

其中前2条规则（式（1）和式（2））阐明了草地和鞋子湿的原因，后一条规则（式（3））表明昨晚下雨和洒水器开启这2个命题不能同时为真. 当我们观察到鞋子湿时，式（2）表明草地湿也应该为真. 延续这个过程，根据式（1），昨晚下雨和洒水器开启都是2种可能的解释. 假如我们还观察到昨晚没有下雨，根据式（3），洒水器开启便是鞋子湿这个现象的唯一的解释. 上述例子描述了根据鞋子湿这一现象，反绎推理得到洒水器开启这一解释/假设的推理过程.

2.2 反绎学习框架

反绎学习^[6-7]是一个融合感知模型和推理模型的框架. 感知模型负责将原始输入数据 ${\boldsymbol{x}} \in \mathcal{X}$ 映射到离散符号 ${\boldsymbol{z}} \subseteq \mathcal{Z}$ ，其中 $\mathcal{X}$ 为输入空间， $\mathcal{Z}$ 为感知模型的输出空间； ${\boldsymbol{x}}$ 和 ${\boldsymbol{z}}$ 分别为输入示例和提取的符号组成的向量，其中 ${\boldsymbol{ x}} = ({x_1},{x_2}, … )$ 和 ${\boldsymbol{z}} = ({z_1},{z_2}, … )$ 分别表示 ${\boldsymbol{x}}$ 中的各个示例和相应的符号. 以手写等式识别任务为例，输入的等式图像是 ${\boldsymbol{x}}$ ，各个分割好的手写数字图像是 ${x_i}$ ；预测的等式符号序列是 ${\boldsymbol{z}}$ ，其中每个符号分别为 ${z_i}$ ；等式是否满足知识库表示为 $y = {\text{True}}$ 或 $y = {\text{False}}$ .

图 1 反绎学习框架的预测过程和训练过程

Figure 1. The predicting process and training process of abductive learning framework

下载: 全尺寸图片幻灯片

推理模型包含一个一阶逻辑规则知识库 $KB$ ，它可以接收符号序列 ${\boldsymbol{z}}$ 并通过逻辑推理得到最终输出 $y \in \mathcal{Y}$ . 例如，给定十进制整数的加法规则，当输入事实 ${\boldsymbol{z}} = (1, + ,1, = ,2)$ （记为“1+1=2”）时，推理模型将输出具体逻辑事实（ground fact） $y = {\text{True}}$ ，表示这是一个正确的等式；而当输入 ${\boldsymbol{z}}$ 为“2+9=10”时，其输出具体逻辑事实 $y = {\text{False}}$ ，表明这是一个不正确的等式. 图1（a）展示了在手写等式破解任务^[6]中预测过程的一个例子.

反绎学习的训练过程可以形式化为：给定未标记数据集 $X$ 、知识库 $KB$ 和最终期望的输出集合 $Y$ ，反绎学习旨在学习一个感知模型 $f:\mathcal{X} \mapsto \mathcal{Z}$ ，它能准确预测输入实例的标记，并且这些标记可以与 $KB$ 一起逻辑蕴涵（entail）得到 $y$ . 由于我们没有 ${\boldsymbol{z}}$ 的监督信息，因此类似于弱监督学习^[20]，我们将 ${\boldsymbol{z}}$ 称为伪标记.

反绎学习训练包括3个步骤：预测伪标记、反绎推理标记和更新模型. 首先，对输入数据 ${\boldsymbol{x}} \in X$ ，反绎学习使用感知模型 $f$ 获取预测伪标记 ${\boldsymbol{z}} = f\left( {\boldsymbol{x}} \right)$ . 然后，推理模型接收符号 ${\boldsymbol{z}}$ 并判断它们与一阶逻辑知识库 $KB$ 的一致性，若不一致，则通过反绎推理将伪标记 ${\boldsymbol{z}}$ 修改为 $\bar {\boldsymbol{z}}$ . 通常来说，存在几个与 $KB$ 一致的候选 $\bar {\boldsymbol{z}}$ . 推理模型基于最小化数据和知识库之间不一致性的原则，推理出最有可能正确的伪标记 $\bar {\boldsymbol{z}}$ . 最后，反绎学习将 $\bar {\boldsymbol{z}}$ 视为真实标记来更新感知模型，上述过程不断迭代重复. （b）展示了一个反绎学习例子，其中输入的具体事实真实标记是“2+9=11”且 $y = {\text{True}}$ . 感知模型 $f$ 预测了错误的伪标记 ${\boldsymbol{z}} =$ “2+9=10”. 反绎推理得到“2+9=11” “2+8=10” “1+9=10”等可能的结果，在最小化不一致性之后，选择 $\bar {\boldsymbol{z}} =$ “2+9=11”作为最终反绎标记并用于更新模型 $f$ .

3. 带拒绝推理的反绎学习方法ABL_r

本文提出了带拒绝推理的反绎学习方法ABL，其基本思想是在反绎学习中拒绝高不确定性的反绎标记，只用剩余较为确定的反绎标记及对应样本更新模型. 在本节，我们首先提出反绎标记的不确定性这个概念，并将其分为模型不确定性和推理不确定性，给出相应的设计. 随后介绍基于模型不确定性和推理不确定性的拒绝推理策略，该策略同时考虑反绎标记的模型不确定性和推理不确定性，并拒绝模型和推理不确定性均较高的样本. 最后介绍本文提出的ABL_r方法，该方法在反绎学习中利用了拒绝推理策略，并动态调节参数以控制拒绝样本的比例，使得训练样本数量保持在预设范围之内.

3.1 反绎标记的模型不确定性

由于反绎标记是由机器学习模型生成的伪标记修改而得，因此可以通过模型的输出计算得到反绎标记的模型不确定性. 具体而言，我们在计算模型不确定性时，用到机器学习模型输出的置信度. 机器学习模型的置信度是指模型对某个预测结果的可信程度或者预测的准确度，其取值范围为[0,1]. 在分类问题中，模型的置信度通常指模型对某个样本属于某个类别的概率估计值. 例如，对于一个二分类问题，模型对于某个样本预测其属于正类的概率为0.8，那么我们可以认为这个模型的置信度较高，因为它对预测结果比较自信. 而如果模型对于另一个样本预测其属于正类的概率为0.5，那么我们就认为这个模型的置信度比较低.

我们定义反绎标记 $\bar {\boldsymbol{z}}$ 的模型不确定性为：

${{Model Uncertainty}}\left( {\bar {\boldsymbol{z}}} \right) = 1 - \frac{1}{{\left| {\bar {\boldsymbol{z}}} \right|}}\mathop \sum \limits_{{{\bar {{z}}}_{{i}}} 为 \bar {\boldsymbol{z}}的元素} Conf\left( {{x_i},{{\bar {{z}}}_i}} \right)\text{，}$

(4)

其中， $Conf\left( {{x_i},{{\bar {{z}}}_i}} \right)$ 指的是模型 $f$ 输出的关于样本 ${x_i}$ 属于类别 ${\bar z_i}$ 的置信度， $\left| {\bar {\boldsymbol{z}}} \right|$ 是输入示例的个数. 式（4）等号右侧的 $\displaystyle\frac{1}{{\left| {\bar {\boldsymbol{z}}} \right|}}\mathop \sum \limits_{{{\bar {{z}}}_i} 为 \bar {\boldsymbol{z}}的元素} Conf\left( {{x_i},{{\bar {{z}}}_i}} \right)$ 计算的是机器学习模型对各个示例对应的反绎标记的平均置信度，若反绎标记的平均置信度越高，说明模型对对应的标记越自信，因此 ${{Model Uncertainty}}\left( {\bar {\boldsymbol{z}}} \right)$ 也越低. 通常情况下，若机器学习模型具有一定的预测能力，那么一个准确的反绎标记应该有较高的置信度以及较低的模型不确定性. 因此，可以根据模型不确定性的大小评估反绎标记的质量，并对反绎标记进行筛选，以确保反绎标记的可靠性.

3.2 反绎标记的推理不确定性

在引言中提到，反绎推理具有不确定性，推理模型可以通过逻辑推理得到若干反绎标记，因此，除了模型不确定性外，我们还可以从推理的角度描述反绎标记的不确定性，即推理不确定性. 例如，对于一个手写等式，如果现有的知识库可以反绎推理得到的反绎候选标记集合为{“1+1=2”}，由于集合内只有1个元素，说明在这种情况下，只有这个修改后的标记与知识库一致，也就是说，推理部分对推理结果的确定性非常高，因此可以直接将该标记作为反绎标记更新模型. 如果知识库反绎推理得到的反绎候选标记集合为{“1+1=2”,“1+2=3”,…}，共包含10个候选反绎标记，而在最小化不一致性时需要从中选择1个作为最终反绎标记，此时能选到样本对应真实标记的概率，与仅有1个候选标记的情况相比大大降低. 因此，我们可以通过反绎候选标记的集合的大小衡量推理部分的不确定性.

形式化地说，对一个训练样本，给定最终输出 $y$ 和知识库 $KB$ ，令 $A$ 为该样本反绎推理得到的所有与知识库一致的候选标记的集合，即 $A = \left\{ {\bar {\boldsymbol{z}}\mid KB \cup \bar {\boldsymbol{z}} \vDash y} \right\}$ ，我们可以定义反绎标记 $\bar {\boldsymbol{z}}$ 的推理不确定性为：

${ {Reasoning Uncertainty}}\left( {\bar {\boldsymbol{z}}} \right) = 1 - \frac{1}{{\left| A \right|}}\text{，}$

(5)

其中， $\left| A \right|$ 指的是该样本的反绎候选标记集合内的元素个数，而 $\displaystyle\frac{1}{{\left| A \right|}}$ 表示从集合 $A$ 中随机选1个反绎候选标记的概率. 与模型不确定性相同，推理不确定性的取值也是在[0,1]之间. 反绎推理得到的可能标记个数越多，从中能选中真实标记的概率越低，因此推理不确定性也就越高.

3.3 基于模型不确定性和推理不确定性的拒绝推理策略

在反绎学习中，我们需要同时考虑模型不确定性和推理不确定性的影响，以评估反绎推理结果的可靠性. 如果模型不确定性和推理不确定性都很低，则反绎标记是真实标记的可能性较高；如果模型不确定性和推理不确定性都较高，那么反绎结果很可能不可靠，给后续训练带来噪声，使得机器学习模型收敛速度变慢同时性能降低. 为了减少不可靠反绎标记对反绎学习的负面影响，我们需要根据反绎标记的不确定性，拒绝一部分推理得到的反绎标记.

我们设计了一种拒绝推理策略，即根据反绎标记的不确定性来决定是否接受该标记. 在这种策略中，我们根据模型不确定性和推理不确定性的程度分别定义2个阈值 ${\theta _{\text{m}}}$ 和 ${\theta _{\text{r}}}$ ，如果某个训练样本对应的反绎标记的模型不确定性和推理不确定性均大于该阈值，则将其拒绝，并将其从反绎学习本轮循环的训练数据集中移除. 阈值 ${\theta _{\text{m}}}$ 和 ${\theta _{\text{r}}}$ 的值越高，则被拒绝的样本越少，反之，其值越低，则被拒绝的样本数量越多. 具体来说，令 $\bar Z$ 为所有样本的反绎标记 $\bar {\boldsymbol{z}}$ 的集合，则需要拒绝的反绎标记集合为

$\begin{split} {\bar Z_{{\text{rej}}}} =\;& \{ \bar {\boldsymbol{z}} \in \bar Z\mid {{ModelUncertainty}}\left( {\bar {\boldsymbol{z}}} \right) > {\theta _{\text{m}}} \wedge\\ &{{ReasoningUncertainty}}\left( {\bar {\boldsymbol{z}}} \right) > {\theta _{\text{r}}}\} \text{，} \end{split}$

(6)

剩下的反绎标记用于训练，即

$\begin{split} {\bar Z_{{\text{use}}}} =\;& \bar Z \setminus {\bar Z_{{\text{rej}}}} = \{ \bar {\boldsymbol{z}} \in \bar Z\mid {{Model Uncertainty}}\left( {\bar {\boldsymbol{z}}} \right) \leqslant {\theta _{\mathrm{m}}} \vee\\ &{{Reasoning Uncertainty}}\left( {\bar {\boldsymbol{z}}} \right) \leqslant {\theta _{\mathrm{r}}}\} . \end{split}$

(7)

这个拒绝推理策略的思想是：当一个样本的模型不确定性和推理不确定性都高于对应阈值时，那么这个标记很可能是错误的或者不可靠的，因此我们拒绝该样本. 例如，考虑图1（b）中的手写等式任务，若反绎候选标记只有1个（“2+9=11”），说明推理部分的不确定性很低，这很可能是正确的标记，因此即便此时模型不确定性较高，也能用于更新模型；反之，若反绎标记的平均置信度很高（如0.9），说明模型对这个反绎标记非常自信，同样此时这很可能是正确的标记，因此即便此时推理不确定性较高，也可以相信这个伪标记；如果模型不确定性和推理不确定性都较高，此时该标记很可能包含噪声，因此拒绝该标记.

3.4 带拒绝推理的反绎学习

图2展示了带拒绝推理的反绎学习方法ABL_r的基本流程. 从图2可以看到，在反绎推理得到样本的反绎标记后，ABL_r会基于模型不确定性和推理不确定性的拒绝推理策略，来判断是否应该拒绝该反绎标记. 如果决定拒绝，那么在本轮循环暂不使用该样本；如果没有拒绝，那么将其视为真实标记更新机器学习模型.

图 2 ABL_r方法的训练过程

Figure 2. Training process of ABL_r

下载: 全尺寸图片幻灯片

在方法的具体实现中，ABL_r还引入了动态自适应阈值机制. 当训练刚开始时，通常此时机器学习模型输出的置信度较低. 如果直接将3.3节的拒绝推理策略应用于反绎学习，则大多数样本的模型不确定性都会较高，从而可能导致训练样本过少的问题. 若直接将模型不确定性阈值 ${\theta _{\text{m}}}$ 固定为一个较高的值，那么绝大部分反绎标记样本都会被接受，失去了拒绝的作用. 为了解决这个问题，ABL_r方法动态调整模型不确定性阈值 ${\theta _{\text{m}}}$ ，确保反绎样本的数量不会过少：给定训练样本的最低占比 $\rho$ ，如果根据阈值 ${\theta _{\text{m}}}$ 得到反绎标记后，其数量 $\left| {{{\bar Z}_{{\text{use}}}}} \right|$ 占总数 $\left| {\bar Z} \right|$ 的比例小于 $\rho$ ，那么将 ${\theta _{\text{m}}}$ 动态调整为能使 $\left| {{{\bar Z}_{{\text{use}}}}} \right| \geqslant \rho \left| {\bar Z} \right|$ 成立的最小阈值 ${\theta '_{\text{m}}}$ ，即 ${\theta '_{\mathrm{m}}} = \mathop {{\text{arg min}}}\limits_{{\theta _{\text{m}}}} \left| {{{\bar Z}_{{\text{use}}}}} \right|/\left| {\bar Z} \right| \geqslant \rho$ ，其中 ${\bar Z_{{\text{use}}}}$ 的定义为式（7）. 一般来说，超参数 $\rho$ 的值越大，调整后模型不确定性 ${\theta '_{\text{m}}}$ 的值越高. 通过此做法，ABL_r可以在训练开始时自动提高模型不确定性阈值 ${\theta _{\text{m}}}$ ，避免训练样本过少的问题.

ABL_r算法如算法1所示. 容易计算出，拒绝推理部分的时间复杂度为 $O\left( {\left| {\boldsymbol{z }}\right|} \right)$ ，空间复杂度为 $O\left( 1 \right)$ ，而不使用拒绝推理方法的时间和空间复杂度均为 $O\left( 1 \right)$ . 尽管采用拒绝推理导致时间复杂度增加，但得益于训练数据中噪声的减少，实际运行速度却有所提升. 值得注意的是，由于反绎学习是一个通用的框架，具有足够的灵活性，因此其中的机器学习模型 $f$ 可以是任何模型，如神经网络、决策树、随机森林等.

算法1. 带拒绝推理的反绎学习方法ABL_r.

输入：未标记数据 $X$ ，最终期望的输出 $Y$ ，知识库 $KB$ ，机器学习模型 $f$ ，阈值 ${\theta _{\text{m}}}$ ， ${\theta _{\text{r}}}$ ， $\rho$ ，迭代轮数 $T$ ；

输出：机器学习模型 $f$ .

① for $t = 1$ to $T$ do

② $Z = f\left( X \right)$ ；

③ $\bar Z = Abduce\left( {KB,Z,Y} \right)$ ；

④ ${\bar Z_{{\text{use}}}} = Filter\left( {\bar Z,{\theta _{\text{m}}},{\theta _{\text{r}}}} \right)$ ；/*根据式（7）计算*/

⑤ if $\left| {{{\bar Z}_{{\text{use}}}}} \right| < \rho \left| {\bar Z} \right|$ then

⑥ ${\bar Z_{{\text{use}}}} = Filter\left( {\bar Z,{\theta_{\text{m}}'},{\theta _{\text{r}}}} \right)$ ；/* ${\theta '_{\text{m}}}$ 为能使

$\left| {{{\bar Z}_{{\text{use}}}}} \right| \geqslant \rho \left| {\bar Z} \right|$ 成立的最小阈值*/

⑦ end if

⑧ $f = Update\left( {f,{X_{{\text{use}}}},{{\bar Z}_{{\text{use}}}}} \right)$ ；

⑨ end for

4. 实　　验

在本节中，我们通过在若干个数据集上进行实验，将本文提出的ABL_r方法与多种方法进行对比和分析，以验证本文所提出的方法的有效性.

4.1 实验数据

我们在神经符号学习领域的3个公开数据集上进行实验，包括Addition，HWF，HED. 表1提供了实验数据集的详细信息.

表 1 实验中所用数据集的基本信息

Table 1. Basic Information of the Datasets in the Experiments

数据集	训练样本数量	测试样本数量	类别数量	领域知识库
Addition	30000	10000	10	个位数加法规则
HWF	9000	2 000	13	加减乘除运算规则
HED	20000	2 000	12	多位数加法规则

下载: 导出CSV

| 显示表格

Addition^[13]数据集最初在DeepProbLog^[13]中被提出，其输入是一对MNIST图像，最终输出是它们的总和. 该数据集要求根据原始输入的手写数字图片和最终计算结果，学习一个能识别未见过手写数字的机器学习模型. 同时，我们还有关于个位数加法规则的一阶逻辑领域知识库.

HWF^[14]数据集包括手写的十进制式子以及它们的最终计算结果，如“1+4/3”. 与此同时，我们还有关于十进制数字的运算规则. 我们希望通过同时利用输入数据和领域知识，学习一个能准确识别手写数字/符号的分类器. 值得注意的是，由于原始论文中的HWF数据集包括长度为1的式子用作预训练模型，我们在实验中删除了这些式子. 因此，我们的运行结果与原文^[14]中的结果有所不同.

HED^[15]数据集源自于反绎学习^[15]论文中的手写等式破解任务. 该数据集的示例如所示，其输入包含十进制等式算术的图像，涵盖12个符号（ $0,1, \cdots , 9, + , =$ ），最终输出为其正确性标记. 此外，知识库包含关于如何进行十进制加法运算的符号规则，用于训练的等式的正确性标记（True或False）也以逻辑事实的形式提供. 与前2个数据集一样，我们希望通过同时利用数据和知识库学习一个能准确识别手写图像的分类器. 由于该任务较难，我们为每一类别提供2张带有标记的图片供模型预训练.

4.2 评价指标及基准模型

在本文研究中，由于主要目标是利用一阶逻辑领域知识库辅助学习机器学习模型，我们采用常用的评价指标准确率（accuracy）来评估机器学习模型的性能. 同时，为了验证本文方法对训练效率的影响，我们还统计了不同方法的运行时间. 在此，我们将运行时间定义为模型测试准确率达到目标值（Addition和HWF数据集为98%，HED数据集为97%）所需的时间.

我们将本文方法ABL_r与DeepProbLog^[13] ，NGS^[14]，ABL^[15]进行比较. DeepProbLog通过梯度下降方法融合概率逻辑推理和神经网络. NGS采用类似反绎的思想，将上下文无关语法作为知识库，并使用马尔可夫链蒙特卡罗采样，根据后验概率修改伪标记并更新模型. ABL通过反绎推理并最小化不一致性的思想修改标记，与ABL_r不同的是，这里的ABL没有采用拒绝推理策略.

在实验中，我们通过对训练数据进行了机器学习中广泛接受和使用的10折交叉验证来确定本文方法的超参数. 我们设定阈值 ${\theta _{\text{m}}} = 0.4,\rho = 0.8, {\theta _{\text{r}}} = 0.86$ . 所有方法均设置了30 min的限时，若30 min内没有收敛，则判定为超时. 我们在一台配置有Intel Xeon Gold 6248R CPU和Nvidia Tesla V100S GPU的服务器上进行了10次重复实验，并统计了平均值和标准差. 所有方法都共享相同的知识库和随机初始化的感知模型.

4.3 实验结果与分析

表2展示了ABL_r方法与其他对比方法在不同数据集上的准确率和训练时间对比. 可以看出，ABL_r方法在3个数据集上都取得了最高的准确率，并且相比其他方法用了更短的时间收敛.

表 2 实验中不同方法的感知准确率和训练时间

Table 2. Perception Accuracy and Training Time of Different Methods in the Experiments

评价指标	数据集	DeepProbLog	NGS	ABL	ABL_r (本文)
准确率/%	Addition	96.5±0.5	98.5±0.7	90.7±9.6	98.9±0.4
	HWF	32.2±0.6	99.5±0.3	99.7±0.1	99.9±0.1
	HED	83.7±6.4	96.7±5.4	97.0±0.2	97.5±0.1
训练时间/s	Addition	596±6	203±5	501±50	140±14
	HWF	超时	180±8	171±15	132±10
	HED	超时	606±68	608±83	557±61
注：黑体数值为最优值. “±”前后分别表示平均值和标准差.

下载: 导出CSV

| 显示表格

在Addition数据集中，4种方法都能达到90%以上的准确率. DeepProbLog能正常收敛，但却耗时最长，这是因为其对概率逻辑程序的梯度计算非常耗时. NGS具有与ABL类似的反绎思想，最终模型达到了较高的准确率，但由于其随机游走采样过程较耗时，因此比ABL_r方法花费的时间更长. ABL方法的性能较低，主要原因是有几次实验ABL陷入了局部最优且跳出较慢. 在陷入局部最优时，由于ABL将所有反绎标记用于训练，其对训练集中的部分错误反绎标记产生了过拟合，因此收敛较慢甚至偶尔一直停留在局部最优点. ABL_r方法通过拒绝部分不可靠的反绎结果，使得模型接受了较少的标记噪声，因此收敛更快且最终性能更好.

在HWF数据集的实验中，可以看到除了DeepProbLog之外的方法都收敛且达到了很高的准确率. 这是由于HWF数据集相比其他数据集更加简单，因此学习较为容易. DeepProbLog性能较低的原因主要是其推理效率太低，而HWF的知识库较为复杂，因此到达设定限时的时候，其仍在收敛过程中. 由于数据集较为简单，因此NGS，ABL，ABL_r在收敛速度上差别不大，ABL_r稍微比其他方法收敛快一些，同样说明拒绝部分样本后虽然数据集变小，但减少了错误标记的影响后反而提升了性能和速度.

HED是实验中难度最大的一个数据集，因此整体训练时间比其他任务长且最终准确率比其他任务低. 同样，我们的ABL_r方法在HED数据集上也取得了最高的准确率和最快的收敛速度. DeepProbLog在该数据集上表现欠佳，主要是由于数据集的复杂性导致模型的学习难度较大. 由于使用全部反绎标记，NGS和ABL方法也出现了过拟合错误反绎标记的问题，导致收敛较慢. ABL_r方法通过拒绝部分不可靠的反绎结果，更快地跳出局部最优，并达到更好的性能. 总体而言，ABL_r方法在这3个数据集上都表现出色，并且相比其他方法具有更好的准确率和训练效率.

4.4 消融实验分析

ABL_r方法综合考虑了模型不确定性和推理不确定性，并加入了动态自适应阈值机制. 为了深入研究这3个部分对最终效果的影响，我们设计了ABL_r方法中关于模型不确定性（model uncertainty, MU）、推理不确定性（reasoning uncertainty, RU）和动态阈值（dynamic threshold, DT）的消融实验. 在消融实验中，我们分别移除ABL_r方法的模型不确定性（w/o MU）、推理不确定性（w/o RU）和动态阈值（w/o DT）部分，以研究这3个部分对最终效果的贡献.

在消融实验中，我们比较了5种方法：

1）ABL基准方法（ABL）. 使用原始的ABL方法，即接受所有反绎标记和样本.

2）ABL_r基准方法（ABL_r）. 使用完整的ABL_r方法，即包括模型不确定性、推理不确定性和动态阈值.

3）移除模型不确定性（w/o MU）. 从ABL_r方法中移除模型不确定性部分，只保留推理不确定性和动态阈值部分.

4）移除推理不确定性（w/o RU）. 从ABL_r方法中移除推理不确定性部分，只保留模型不确定性和动态阈值部分.

5）移除动态阈值（w/o DT）. 从ABL_r方法中移除动态阈值部分，只保留模型不确定性和推理不确定性部分.

消融实验的结果如表3所示. 在本次实验中，我们统计了各种方法在测试准确率和反绎准确率2个方面的表现. 测试准确率衡量了机器学习模型在测试集上的最终预测能力，而反绎准确率则关注在第1轮中用于训练的反绎标记的准确率. 实验结果表明，与ABL方法相比，ABL_r在拒绝部分不可靠标记后，在3个数据集上的反绎准确率均有所提高，这说明我们的方法在减少错误反绎标记的比例方面取得了明显的效果. 此外，在分别去除模型不确定性和推理不确定性后，测试准确率都出现了一定程度的降低，这进一步说明，模型不确定性和推理不确定性部分对ABL_r方法的性能发挥了积极作用. 与此同时，大部分相应的反绎准确率也得到了提高，这进一步证实了拒绝样本能够提高真实标记的比例.

表 3 消融实验：不同方法的测试准确率和反绎准确率

Table 3. Ablation Study: Testing Accuracy and Abduced Accuracy of Different Methods %

准确率	数据集	ABL	ABL_r (本文)	w/o MU	w/o RU	w/o DT
测试	Addition	90.7±9.6	98.9±0.4	98.5±0.2	98.6±0.2	86.6±30.3
	HWF	99.7±0.3	99.9±0.1	99.8±0.1	99.8±0.1	99.8±0.1
	HED	97.0±0.2	97.5±0.1	97.1±0.3	82.4±20.1	84.5±24.0
反绎	Addition	56.5±13.0	59.8±6.9	61.7±6.7	55.7±8.2	57.7±18.4
	HWF	91.9±0.8	93.5±0.9	96.4±0.6	91.7±1.3	96.0±0.5
	HED	77.9±5.0	79.9±5.0	77.4±9.2	72.8±6.2	70.9±4.6
注：“±”前后分别表示平均值和标准差.

下载: 导出CSV

| 显示表格

我们还发现，在去除动态自适应阈值机制后，Addition和HED数据集的测试准确率明显下降. 经过进一步分析，我们发现这是由于在训练初期，模型输出的置信度普遍较低，从而导致大量样本被拒绝，这会使模型陷入局部最优，且性能无法得到有效提升. 这些消融实验充分说明了ABL_r方法中的3个关键部分，即模型不确定性、推理不确定性和动态自适应阈值机制，都对整体性能产生了积极的影响.

5. 总　　结

本文提出了一种反绎学习的提升方法，这个方法同时从模型不确定性和推理不确定性来衡量反绎标记的可靠性，并拒绝可能不可靠的推理结果. 实验结果表明，我们的方法能够有效地拒绝错误的反绎标记，从而加速反绎学习的训练过程，并提升机器学习模型的性能. 此外，这个方法具有良好的通用性，同样可以应用于其他基于反绎的方法. 尽管本文工作在评估反绎标记的模型不确定性和推理不确定性方面取得了一定的成功，但所采用的方法相对简单. 如何更精确地刻画反绎标记的不确定性，以便更准确地识别不可靠的反绎标记，仍是一个亟待进一步研究的问题.

作者贡献声明：黄宇轩负责提出方法、完成实验、撰写论文；姜远负责写作指导和修改审定.

图 1 移动设备存储系统的分层结构

Figure 1. Hierarchical structure of mobile device storage system

下载: 全尺寸图片幻灯片

图 2 F2FS的文件布局

Figure 2. File layout of F2FS

下载: 全尺寸图片幻灯片

图 3 F2FS主区的冷热数据分类

Figure 3. Hot data and cold data classification of F2FS main area

下载: 全尺寸图片幻灯片

图 4 日志结构文件系统中文件碎片和空闲空间碎片的产生

Figure 4. Generation of file fragmentation and free space fragmentation in log-structured file systems

下载: 全尺寸图片幻灯片

图 5 F2FS多线程并发写多个文件

Figure 5. F2FS multi-threaded writing of multiple files concurrently

下载: 全尺寸图片幻灯片

图 6 不同热度的数据混合存储导致空闲空间碎片增加

Figure 6. Increase of free space debris caused by the mixed storage of data with different hotness

下载: 全尺寸图片幻灯片

图 7 文件系统去碎片化示意图

Figure 7. Illustration of file system defragmentation

下载: 全尺寸图片幻灯片

图 8 文件碎片分割I/O请求示意图^[61]

Figure 8. Illustration of file fragmentation I/O requests^[61]

下载: 全尺寸图片幻灯片

表 1 使用F2FS的商用移动设备

Table 1 Commercial Mobile Devices Using the F2FS

生产年份	商用移动设备
2012―2015	摩托罗拉MSM8960 JBBL设备/ Droid/ G/ X系列
2014―2016	谷歌Nexus 9、摩托罗拉E LTE/Z、一加3T、华为Honor 8/ V8/ P9/ Mate 9
2018―2019	谷歌Pixel 3/3 XL、中兴Axon 10 Pro、三星Galaxy Note 10/Tab S6
2020―	基于Android 11的谷歌Pixel系列

下载: 导出CSV

表 2 文件系统碎片产生与影响的研究现状

Table 2 Research Status of Generation and Impact of File System Fragmentation

老化工具类型	工具名称	主要特点
合成负载生成器	Geriatrix	提出文件系统老化工具Geriatrix^[5]
	老化负载	利用文件系统快照产生碎片^[51]
	Iozone	研究F2FS中文件碎片对性能的影响^[52]
脚本执行实际应用	AutoAge	产生、衡量和减少文件碎片的方法^{[50, 53]}
脚本执行实际应用	Git-Benchmark	证实大多数文件系统都会老化^[4]
trace重播	MobiBench	使用MobiBench抓取应用trace 并重播^[12]

下载: 导出CSV

表 3 减少文件碎片的策略

Table 3 Strategies to Reduce File Fragmentation

研究角度	文件系统	主要特点
碎片产生前，预防碎片产生	XFS	预分配空间大小调整方法^[64]
	ext4	将块分配从写操作时间延迟到页刷新时间^[54]
	F2FS	多级阈值同步写方法^[66]
	F2FS	自适应选择严重碎片化文件的预留空间方法^[67−68]
碎片产生后，重整碎片	DFS	通过动态地重新定位和聚拢数据块减少碎片^[69]
	F2FS	段清理过程中基于inode号给有效块排序^[70]
	不受限	只对非常影响I/O性能的部分数据重整碎片^[61]
	ext4	在FTL实现无需复制数据的重整过程^[63]

下载: 导出CSV

表 4 区分数据热度的研究

Table 4 Research on Distinguishing Data Hotness

区分方法	方案	主要贡献
静态分类	WOLF^[74]	基于频率设计启发式算法分离活跃和不活跃数据
	hint^[75]	利用页缓存中隐藏信息动态识别文件系统中块的热度
	SFS^[6]	利用计数块的写次数和频率，获得分组标准分离冷热数据段
	HyLog^[79]	基于写代价模型的分离算法区分冷热页
动态分类	ASA-FTL^[80]	在Flash转换层使用数据聚类分离冷热数据
	HAML-SSD^[81]	基于更新频率和平均更新时间间隔，用聚类算法区分热度
	DAC^[82]	根据数据的访问频率对数据进行动态分类
	PCStream^[83]	基于数据生命周期使用聚类算法对程序上下文进行分组
	M2H^[84]	使用K均值聚类算法，基于文件块更新距离感知数据热度变化

下载: 导出CSV

表 5 日志结构文件系统优化段清理技术

Table 5 Optimizing Segment Cleaning Techniques for Log-structured File Systems

设计角度	方案	主要特点
清理发生前管理数据分布	ParaFS^[7]	基于闪存通道并行性设计2维数据分配
清理发生前管理数据分布	SCJ^[85−86]	使用日志记录段清理时文件系统的修改
调整段清理时机、频率、对象	Suspend-aware SC^[87]	挂起感知的后台段清理技术
	MWHFB^[66]	高检测频率的后台段清理策略
	RLBC^[88]	基于强化学习自适应决定何时触发后台段清理
	MOBC^[72]	基于剪枝的多目标深度强化学习的后台段清理方法
	FAGC^[73]	感知空闲空间碎片化程度的垃圾回收策略

下载: 导出CSV

参考文献(89)

[1]	Lee C, Sim D, Hwang J Y, et al. F2FS: A new file system for flash storage[C]// Proc of the 13th USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2015: 273−286
[2]	Rosenblum M, Ousterhout J K. The design and implementation of a log-structured file system[J]. ACM Transactions on Computer Systems, 1992, 10(1): 26−52 doi: 10.1145/146941.146943
[3]	Mathur A, Cao Mingming, Bhattacharya S, et al. The new ext4 filesystem: Current status and future plans[C/OL]// Proc of the Linux Symp. 2007, 2: 21- 2: 33. [2024-05-21]. https://giis.co.in/mathur-Reprint.pdf
[4]	Conway A, Bakshi A, Jiao Yizheng, et al. File systems fated for senescence? Nonsense, says science![C]// Proc of the 15th USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2017: 45−58
[5]	Kadekodi S, Nagarajan V, Ganger G R. Geriatrix: Aging what you see and what you don’t see. A file system aging approach for modern storage systems[C]// Proc of the 2018 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2018: 691−704
[6]	Min C, Kim K, Cho H, et al. SFS: Random write considered harmful in solid state drives// Proc of the 10th USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2012, 12: 1−12: 16
[7]	Zhang Jiacheng, Shu Jiwu, Lu Youyou. ParaFS: A log-structured file system to exploit the internal parallelism of flash devices[C]// Proc of the 2016 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2016: 87−100
[8]	Woodhouse D. JFFS: The journalling flash file system[C/OL]// Proc of the Ottawa Linux Symp. 2001 [2024-05-22]. http://pficheux.free.fr/eyrolles/linux_embarque/docs_externes/jffs2.pdf
[9]	Schierl A, Schellhorn G, Haneberg D, et al. Abstract specification of the UBIFS file system for flash memory[C]// Proc of the 2nd World Congress on Formal Methods. Berlin: Springer, 2009: 190−206
[10]	Lee K, Won Y. Smart layers and dumb result: IO characterization of an android-based smartphone[C]// Proc of the 10th ACM Int Conf on Embedded Software. New York: ACM, 2012: 23−32
[11]	Kim H, Agrawal N, Ungureanu C. Revisiting storage for smartphones[J]. ACM Transactions on Storage, 2012, 8(4): 14: 1−14: 25
[12]	Jeong S, Lee K, Lee S, et al. I/O stack optimization for smartphones[C]// Proc of the 2013 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2013: 309−320
[13]	Ji Cheng, Pan Riwei, Chang Lipin, et al. Inspection and characterization of app file usage in mobile devices[J]. ACM Transactions on Storage, 2020, 16(4): 25: 1−25: 25
[14]	Courville J, Chen Feng. Understanding storage I/O behaviors of mobile applications[C/OL]// Proc of the 32nd Symp on Mass Storage Systems and Technologies. Piscataway, NJ: IEEE, 2016 [2024-05-22]. https://ieeexplore.ieee.org/document/7897092
[15]	Li Jing, Badam A, Chandra R, et al. On the energy overhead of mobile storage systems[C]// Proc of the 12th USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2014: 105−118
[16]	Guo Weichao, Chen Kang, Feng Huan, et al. MARS: Mobile application relaunching speed-up through flash-aware page swapping[J]. IEEE Transactions on Computers, 2015, 65(3): 916−928
[17]	Zhu Yuhao, Halpern M, Reddi V J. Event-based scheduling for energy-efficient QoS (eQoS) in mobile Web applications[C]// Proc of the 21st Int Symp on High Performance Computer Architecture. Piscataway, NJ: IEEE, 2015: 137−149
[18]	Cruz L, Abreu R. EMaaS: Energy measurements as a service for mobile applications[C]// Proc of the 41st IEEE/ACM Int Conf on Software Engineering: New Ideas and Emerging Results. Piscataway, NJ: IEEE, 2019: 101−104
[19]	Kwon E, Han S, Park Y, et al. Reinforcement learning-based power management policy for mobile device systems[J]. IEEE Transactions on Circuits and Systems I: Regular Papers, 2021, 68(10): 4156−4169 doi: 10.1109/TCSI.2021.3103503
[20]	Yang Jingpei, Plasson N, Gillis G, et al. Don’t stack your log on my log[C/OL]// Proc of the 2nd Workshop on Interactions of NVM/Flash with Operating Systems and Workloads. Berkeley, CA: USENIX Association, 2014 [2024-05-22]. https://www.usenix.org/system/files/conference/inflow14/inflow14-yang.pdf
[21]	Jeong S, Lee K, Hwang J, et al. Androstep: Android storage performance analysis tool[C/OL]// Proc of the Software Engineering 2013-Workshopband. 2013: 327−340 [2024-05-22]. https://oslab.kaist.ac.kr/wp-content/uploads/esos_files/publication/conferences/international/AndroStep.pdf?ckattempt=1
[22]	Hahn S S, Lee S, Yee I, et al. FastTrack: Foreground app-aware I/O management for improving user experience of android smartphones[C]// Proc of the 2018 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2018: 15−28
[23]	Han Lei, Xiao Bin, Dong Xuwei, et al. DS-Cache: A refined directory entry lookup cache with prefix-awareness for mobile devices[C]// Proc of the 2019 Design, Automation, and Test in Europe Conf and Exhibition. Piscataway, NJ: IEEE, 2019: 1052−1057
[24]	Liang Yu, Li Qiao, Xue C J. Mismatched memory management of android smartphones[C/OL]// Proc of the 11th USENIX Workshop on Hot Topics in Storage and File Systems. Berkeley, CA: USENIX Association, 2019 [2024-05-22]. https://www.usenix.org/system/files/hotstorage19-paper-liang.pdf
[25]	Liang Yu, Li Jinheng, Ausavarungnirun R, et al. Acclaim: Adaptive memory reclaim to improve user experience in Android systems[C]// Proc of the 2020 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2020: 897−910
[26]	Mao Bo, Wu Suzhen, Jiang Hong, et al. Content-aware trace collection and I/O deduplication for smartphones[C/OL]// Proc of the 33rd Int Conf Massive Storage Systems and Technology. Piscataway, NJ: IEEE, 2017 [2024-05-22]. https://msstconference.org/MSST-history/2017/Papers/ContentAwareTraceCollection.pdf
[27]	Mao Bo, Zhou Jindong, Wu Suzhen, et al. Improving flash memory performance and reliability for smartphones with I/O deduplication[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 38(6): 1017−1027
[28]	Ji Cheng, Chang Lipin, Pan Riwei, et al. Pattern-guided file compression with user-experience enhancement for log-structured file system on mobile devices[C]// Proc of the 19th USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2021: 127−140
[29]	Ren Jinglei, Liang C J M, Wu Yongwei, et al. Memory-centric data storage for mobile systems[C]// Proc of the 2015 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2015: 599−611
[30]	Mohan J, Purohith D, Halpern M, et al. Storage on your smartphone uses more energy than you think[C/OL]// Proc of the 9th USENIX Workshop on Hot Topics in Storage and File Systems. Berkeley, CA: USENIX Association, 2017 [2024-05-20]. https://www.usenix.org/system/files/conference/hotstorage17/hotstorage17-paper-mohan.pdf
[31]	Carroll A, Heiser G. An analysis of power consumption in a smartphone[C/OL]// Proc of the 2010 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2010 [2025-05-22]. https://www.usenix.org/legacy/events/atc10/tech/full_papers/Carroll.pdf
[32]	Yoon C, Kim D, Jung W, et al. AppScope: Application energy metering framework for Android smartphone using kernel activity monitoring[C]// Proc of the 2012 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2012: 387−400
[33]	Olivier P, Boukhobza J, Senn E, et al. A methodology for estimating performance and power consumption of embedded flash file systems[J]. ACM Transactions on Embedded Computing Systems, 2016, 15(4): 79: 1−79: 25
[34]	Chung Y F, Lo Y T, King C T. Enhancing user experiences by exploiting energy and launch delay trade-off of mobile multimedia applications[J]. ACM Transactions on Embedded Computing Systems, 2013, 12(1s): 37: 1−37: 19
[35]	Nguyen D T, Zhou Gang, Qi Xin, et al. Storage-aware smartphone energy savings[C]// Proc of the 2013 ACM Int Joint Conf on Pervasive and Ubiquitous Computing. New York: ACM, 2013: 677−686
[36]	Huang J, Badam A, Chandra R, et al. WearDrive: Fast and energy-efficient storage for wearables[C]// Proc of the 2015 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2015: 613−625
[37]	Zhong Kan, Zhu Xiao, Wang Tianzheng, et al. DR. Swap: Energy-efficient paging for smartphones[C]//Proc of the 2014 Int Symp on Low Power Electronics and Design. Piscataway, NJ: IEEE, 2014: 81−86
[38]	Yan Kaige, Fu Xin. Energy-efficient cache design in emerging mobile platforms: The implications and optimizations[C]// Proc of the 2015 Design, Automation, and Test in Europe Conf and Exhibition. Piscataway, NJ: IEEE, 2015: 375−380
[39]	Chang Lipin, Sung Pohan, Chen Potsang, et al. Eager synching: A selective logging strategy for fast fsync() on flash-based Android devices[J]. ACM Transactions on Embedded Computing Systems, 2016, 16(2): 34: 1−34: 25
[40]	Lee E, Son I, Kim J S. An efficient order-preserving recovery for F2FS with ZNS SSD[C]//Proc of the 15th ACM Workshop on Hot Topics in Storage and File Systems. Berkeley, CA: USENIX Association, 2023: 116−122
[41]	Lee C G, Byun H, Noh S, et al. Write optimization of log-structured flash file system for parallel I/O on manycore servers[C]//Proc of the 12th ACM Int Conf on Systems and Storage. Berkeley, CA: USENIX Association, 2019: 21−32
[42]	Yeon J, Jeong M, Lee S, et al. RFLUSH: Rethink the flush[C]// Proc of the 16th USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2018: 201−210
[43]	Liang Yu, Ji Cheng, Fu Chenchen, et al. iTRIM: I/O-aware TRIM for improving user experience on mobile devices[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 40(9): 1782−1795
[44]	Feng Xiaolu, Chen Xianzhang, Li Ruolan, et al. CoDiscard: A revenue model based cross-layer cooperative discarding mechanism for flash memory devices[J]. Journal of Systems Architecture, 2022, 128: 102564 doi: 10.1016/j.sysarc.2022.102564
[45]	Seltzer M I, Smith K A, Balakrishnan H, et al. File system logging versus clustering: A performance comparison[C]// Proc of the 1995 USENIX Technical Conf. Berkeley, CA: USENIX Association, 1995: 249−264
[46]	Cheng Wen, Zheng Telong, Zeng Lingfang, et al. DPLFS: A dual-mode PCM-based log-structured file system[C]// Proc of the 40th Int Conf on Computer Design. Piscataway, NJ: IEEE, 2022: 324−331
[47]	Xu Jian, Swanson S. NOVA: A log-structured file system for hybrid volatile/non-volatile main memories[C]// Proc of the 14th USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2016: 323−338
[48]	Xu Jian, Zhang Lu, Memaripour A, et al. Nova-fortis: A fault-tolerant non-volatile main memory file system[C]// Proc of the 26th Symp on Operating Systems Principles. New York: ACM, 2017: 478−496
[49]	Liao Xiaojian, Lu Youyou, Xu Erci, et al. MAX: A multicore-accelerated file system for flash storage[C]// Proc of the 2021 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2021: 877−891
[50]	Ji Cheng, Chang Lipin, Hahn S S, et al. File fragmentation in mobile devices: Measurement, evaluation, and treatment[J]. IEEE Transactions on Mobile Computing, 2018, 18(9): 2062−2076
[51]	Smith K A, Seltzer M I. File system aging—Increasing the relevance of file system benchmarks[C]//Proc of the 1997 ACM SIGMETRICS Int Conf on Measurement and Modeling of Computer Systems. New York: ACM, 1997: 203−213
[52]	Liang Yu, Fu Chenchen, Du Yajuan, et al. An empirical study of F2FS on mobile devices[C/OL]// Proc of the 23rd Int Conf on Embedded and Real-Time Computing Systems and Applications. Piscataway, NJ: IEEE, 2017 [2024-05-22]. https://ieeexplore.ieee.org/document/8046304
[53]	Ji Cheng, Chang Lipin, Shi Liang, et al. An empirical study of file-system fragmentation in mobile storage systems[C]// Proc of the 8th USENIX Workshop on Hot Topics in Storage and File Systems. Berkeley, CA: USENIX Association, 2016: 76−80
[54]	KV A K, Cao Mingming, Santos J R, et al. Ext4 block and inode allocator improvements[C/OL]// Proc of the Linux Symp, Vol 1. 2008: 263−274 [2024-05-22]. https://landley.net/kdocs/mirror/ols2008v1.pdf#page=263
[55]	Sweeney A, Doucette D, Hu Wei, et al. Scalability in the XFS file system[C/OL]// Proc of the USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 1996 [2024-05-22]. https://www.cs.princeton.edu/courses/archive/fall11/cos518/papers/xfs.pdf
[56]	Rodeh O, Bacik J, Mason C. BTRFS: The Linux B-tree filesystem[J]. ACM Transactions on Storage, 2013, 9(3): 9: 1−9: 32
[57]	Bonwick J, Ahrens M, Henson V, et al. The Zettabyte file system[C/OL]// Proc of the 2nd USENIX Conf on File and Storage Technologies, Vol 215. Berkeley, CA: USENIX Association, 2003 [2024-05-22]. https://www.cs.hmc.edu/~rhodes/courses/cs134/fa20/readings/The%20Zettabyte%20File%20System.pdf
[58]	Jannen W, Yuan Jun, Zhan Yang, et al. BetrFS: A right-optimized write-optimized file system[C]// Proc of the 13th USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2015: 301−315
[59]	Yuan Jun, Zhan Yang, Jannen W, et al. Optimizing every operation in a write-optimized file system[C]// Proc of the 14th USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2016: 1−14
[60]	Conway A, Knorr E, Jiao Yizheng, et al. Filesystem aging: It’s more usage than fullness[C/OL]// Proc of the 11th USENIX Workshop on Hot Topics in Storage and File Systems. Berkeley, CA: USENIX Association, 2019 [2024-05-22]. https://www.usenix.org/system/files/hotstorage19-paper-conway.pdf
[61]	Park J, Eom Y I. FragPicker: A new defragmentation tool for modern storage devices[C]// Proc of the 28th Symp on Operating Systems Principles. New York: ACM, 2021: 280−294
[62]	Kesavan R, Curtis-Maury M, Devadas V, et al. Countering fragmentation in an enterprise storage system[J]. ACM Transactions on Storage, 2020, 15(4): 25: 1−25: 35
[63]	Hahn S S, Lee S, Ji Cheng, et al. Improving file system performance of mobile storage systems using a decoupled defragmenter[C]// Proc of the 2017 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2017: 759−771
[64]	Nakamura T, Komoda N. Pre-allocation size adjusting methods depending on growing file size[C]// Proc of the 5th IEEE Int Workshop on Storage Network Architecture and Parallel I/Os. Piscataway, NJ: IEEE, 2008: 19−25
[65]	Djordjevic B, Timcenko V. Ext4 file system in Linux environment: Features and performance analysis[J]. International Journal of Computers, 2012, 6(1): 37−45
[66]	Li Qi, Deng Aosong, Gao Congming, et al. Optimizing fragmentation and segment cleaning for CPS based storage devices[C]// Proc of the 34th ACM/SIGAPP Symp on Applied Computing. New York: ACM, 2019: 242−249
[67]	Yang Lihua, Wang Fang, Tan Zhipeng, et al. ARS: Reducing F2FS fragmentation for smartphones using decision trees[C]// Proc of the 2020 Design, Automation, and Test in Europe Conf and Exhibition. Piscataway, NJ: IEEE, 2020: 1061−1066
[68]	Yang Lihua, Tan Zhipeng, Wang Fang, et al. Improving F2FS performance in mobile devices with adaptive reserved space based on traceback[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2021, 41(1): 169−182
[69]	Ahn W H, Kim K, Choi Y, et al. DFS: A de-fragmented file system[C]// Proc of the 10th IEEE Int Symp on Modeling, Analysis and Simulation of Computer and Telecommunications Systems. Piscataway, NJ: IEEE, 2002: 71−80
[70]	Park J, Kang D H, Eom Y I. File defragmentation scheme for a log-structured file system// Proc of the 7th ACM SIGOPS Asia-Pacific Workshop on Systems. New York: ACM, 2016: 19: 1−19: 7
[71]	Park J, Eom Y I. Anti-aging LFS: Self-defragmentation with fragmentation-aware cleaning[J]. IEEE Access, 2020, 8: 151474−151486
[72]	Wu Chao, Cui Yufei, Ji Cheng, et al. Pruning deep reinforcement learning for dual user experience and storage lifetime improvement on mobile devices[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 39(11): 3993−4005 doi: 10.1109/TCAD.2020.3012804
[73]	Yang Lihua, Tan Zhipeng, Wang Fang, et al. FAGC: Free space fragmentation aware GC scheme based on observations of energy consumption[C/OL]// Proc of the 2023 Design, Automation, and Test in Europe Conf and Exhibition. Piscataway, NJ: IEEE, 2023 [2024-05-22]. https://ieeexplore.ieee.org/document/10137040
[74]	Wang Jun, Hu Yiming. WOLF—A novel reordering write buffer to boost the performance of log-structured file systems[C]// Proc of the 1st USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2002: 47−60
[75]	Kang D H, Eom Y I. Dynamic hot-cold separation scheme on the log-structured file system for CE devices[C]// Proc of the 2017 IEEE Int Conf on Consumer Electronics. Piscataway, NJ: IEEE, 2017: 428−429
[76]	Kang M, Choi S, Oh G, et al. 2R: Efficiently isolating cold pages in flash storages[J]. Proceedings of the VLDB Endowment, 2020, 13(12): 2004−2017 doi: 10.14778/3407790.3407805
[77]	Sun Penghao, You Litong, Zheng Shengan, et al. Learning-based data separation for write amplification reduction in solid state drives[C/OL]// Proc of the 60th ACM/IEEE Design Automation Conf. Piscataway, NJ: IEEE, 2023 [2024-05-22]. https://ieeexplore.ieee.org/abstract/document/10247795
[78]	张强,梁杰,许胤龙,等. 基于工作负载感知的固态硬盘阵列系统的架构设计与研究[J]. 计算机研究与发展,2019,56(4):755−766 Zhang Qiang, Liang Jie, Xu Yinlong, et al. Research of SSD array architecture based on workload awareness[J]. Journal of Computer Research and Development, 2019, 56(4): 755−766 (in Chinese)
[79]	Wang Wenguang, Zhao Yanping, Bunt R. HyLog: A high performance approach to managing disk layout[C]// Proc of the 3rd USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2004: 145−158
[80]	Xie Wei, Chen Yong, Roth P C. ASA-FTL: An adaptive separation aware flash translation layer for solid state drives[J]. Parallel Computing, 2017, 61: 3−17 doi: 10.1016/j.parco.2016.10.006
[81]	Li Bingzhe, Deng Chunhua, Yang Jinfeng, et al. HAML-SSD: A hardware accelerated hotness-aware machine learning based ssd management[C/OL]// Proc of the 2019 IEEE/ACM Int Conf on Computer-Aided Design. Piscataway, NJ: IEEE, 2019 [2024-05-22]. https://ieeexplore.ieee.org/document/8942140
[82]	Chiang M L, Lee P C H, Chang R C. Using data clustering to improve cleaning performance for flash memory[J]. Software: Practice and Experience, 1999, 29(3): 267−290 doi: 10.1002/(SICI)1097-024X(199903)29:3<267::AID-SPE233>3.0.CO;2-T
[83]	Kim T, Hong D, Hahn S S, et al. Fully automatic stream management for multi-streamed SSDs using program contexts[C]// Proc of the 17th USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2019: 295−308
[84]	Yang Lihua, Tan Zhipeng, Wang Fang, et al. M2H: Optimizing F2FS via multi-log delayed writing and modified segment cleaning based on dynamically identified hotnessn[C]// Proc of the 2021 Design, Automation, and Test in Europe Conf and Exhibition. Piscataway, NJ: IEEE, 2021: 808−811
[85]	Gwak H, Kang Y, Shin D. Reducing garbage collection overhead of log-structured file systems with GC journaling[C/OL]// Proc of the 2015 Int Symp on Consumer Electronics. Piscataway, NJ: IEEE, 2015 [2022-05-22]. https://ieeexplore.ieee.org/document/7177770
[86]	Gwak H, Shin D. SCJ: Segment cleaning journaling for log-structured file systems[J]. IEEE Access, 2021, 9: 142437−142448 doi: 10.1109/ACCESS.2021.3121423
[87]	Park D, Cheon S, Won Y. Suspend-aware segment cleaning in log-structured file system[C/OL]// Proc of the 7th USENIX Workshop on Hot Topics in Storage and File Systems. Berkeley, CA: USENIX Association, 2015 [2024-05-22]. https://www.usenix.org/system/files/conference/hotstorage15/hotstorage15-park.pdf
[88]	Wu Chao, Ji Cheng, Xue C J. Reinforcement learning based background segment cleaning for log-structured file system on mobile devices[C/OL]// Proc of the 15th IEEE Int Conf on Embedded Software and Systems. Piscataway, NJ: IEEE, 2019 [2024-05-22]. https://ieeexplore.ieee.org/document/8782508
[89]	Yu Chao. Support age-threshold based garbage collection for F2FS[EB/OL]. (2020-08-04)[2024-05-22]. https://lwn.net/Articles/828027/

施引文献(4)

期刊类型引用(2)

1.	张朋飞，程俊，张治坤，方贤进，孙笠，王杰，姜茸. 满足本地差分隐私的混合噪音感知的模糊C均值聚类算法. 电子与信息学报. 2025(03): 739-757 . 百度学术
2.	朱友文，唐聪，吴启晖，张焱. 个性化本地差分隐私机制的研究现状与展望. 南京航空航天大学学报. 2024(05): 784-800 . 百度学术