摘要
为解决 Linux 内核传统路径检索日益凸显的开销问题，提出Staged Lookup以加速路径检索，通过动态缓存热目录来减少文件访问的时延。Staged Lookup的核心在于缓存频繁使用的目录项，从而避免从根节点重复遍历路径。不同于从根结点开始的检索操作， Staged Lookup扩展了搜索策略，允许从最近缓存的目录项向后或向前进行路径检索。在Linux内核版本3.14和5.4上部署Staged Lookup的原型，并开展实际系统测试。实验数据显示，相比于传统的路径检索方式，Staged Lookup能实现高达46.9%的性能提升。
Abstract
To solve the increasingly prominent cost of traditional path lookup strategy in the Linux kernel, Staged Lookup was proposed to accelerate path lookup by dynamically caching hot directories to reduce file access latency.The essence of Staged Lookup lay in caching frequently used directory entries, thus avoiding the repetitive traversal of paths from the root node. Unlike the retrieval operations that start from the root node, Staged Lookup expanded the search strategy to allow for forward or backward path lookup from the most recently cached directory entry. A prototype of Staged Lookup was deployed on Linux kernel versions 3.14 and 5.4 and subjected to real system tests. Experimental data indicates that Staged Lookup can achieve performance improvements of up to 46.9% compared to traditional path lookup methods.
Keywords
基于Linux 虚拟文件系统（virtual file system，VFS）的基本框架，文件访问通常可以分为处于VFS层的内存级操作，以及由VFS下层如文件系统、驱动等所管理的设备 I/O 操作。长期以来，由于常用的存储设备相比于内存具有更高数量级的访问时延，如机械硬盘、固态硬盘等，设备 I/O 通常占据文件访问的主要时间开销[1-2]。随着闪存、非易失内存等持久化存储设备的快速发展，其访存速度与内存的差距逐步拉近[3-5]，Suzuki 等研究了2000—2014年之间非易失内存（non-volatile memory，NVM）技术相关的论文[6]，NVM的访问时延和带宽普遍被认为与动态随机存取存储器（dynamic random access memory，DRAM）处于同一数量级，大量针对NVM的研究工作由于无法获取现成的NVM设备，甚至会采用DRAM来进行模拟。
在NVM技术的影响下，文件访问过程中，存储设备级的数据 I/O 时延将会被急剧减小[7]，相对应地，内存级的VFS操作所占据的时间占比将会被放大[8-9]，尤其对于小文件或小I/O的文件操作，这种影响更加明显。如何降低传统系统的软件开销成为文件系统性能优化的新挑战。作为文件操作最先发起的操作之一，降低路径检索的时间开销成为文件系统适配高速持久化存储设备的开端。
根据文件系统基准测试级iBench 的统计，近20%的系统调用需要进行路径检索[10]。研究表明，基于路径检索的系统调用在执行文件相关的应用指令（如 find、tar、du 以及 git-diff 等）的时间开销中占主要部分。以 find 指令为例，超过60% 的执行时间花在 open 操作上[11]；而对于 git-diff 指令，stat 操作占据主要的时间开销，无论open还是stat，路径检索都是其主要操作。图1展示了利用 LMBench 基准测试工具对4种基本的文件相关系统调用（stat、open/close、read 以及 write） 进行的测试，t为时延。需要指出的是，测试针对的是系统调用时延，并不涉及实际的数据I/O，此处read、write操作是往虚拟文件/dev/zero中写1 B的数据。测试结果表明，路径查找操作在上述调用中均占据了主要的系统调用时间开销。可以认为，在不考虑数据I/O的前提下，路径查找在文件访问过程中占据着极其重要的时间开销。而在数据I/O时延快速减小的当下，路径检索将占据越来越重要的时间开销地位。
图1部分系统调用针对不同深度文件路径的时延
Fig.1Latency of some system calls with different depth of paths
除了高开销，路径检索在文件操作中出现的频率也很高。以智能手机的文件浏览器File Explorer和垃圾清理应用NoxCleaner为例，它们每秒能产生高达10 000 条路径检索操作[12]。不仅是智能手机应用，大规模科学计算应用也会产生大量的路径检索。据国家超算无锡中心“神威·太湖之光”超级计算机的统计，每天有高达52.4%的操作需要进行路径检索[13-14]。这意味着“神威·太湖之光”超级计算机系统一天中有超过1 300万个路径检索请求，包含高达8 900万个路径分量的访问。进一步的分析发现，上述8 900万个路径分量访问请求仅涉及235个不同的目录/文件，换言之，少数目录被大量频繁重复地访问。
如何提高路径访问效率，直接影响到了应用的响应时间，目前主要有两种类型的优化思路：第一种是在文件系统层减小路径分量检索的时延[15-16]。比如，TableFS 通过额外添加对象存储的方式，加速元数据以及小文件的访问操作[17]。在并行与分布式文件系统中，研究人员通过采用扁平式命名空间[18]、命名空间快照[19]以及动态管理[20]等优化元数据管理的方法，降低路径检索时延。第二种优化路径检索的思路是针对各级目录项采用缓存技术。Tsai 等提出一种基于全路径哈希的目录缓存机制，用哈希表来缓存目录项[11]，但维护哈希表的开销较大；Shen等基于智能手机平台提出一种路径前缀缓存技术[12]，但该技术面临缓存命中率较低，且无法修改元数据等棘手问题。
在现有研究工作的基础上，本文发现路径检索的优化可以考虑另外两个因素：①相同应用访问的文件多位于同一个目录下[21]；②小文件的访问频次大多高于大文件[10，16，22]。基于上述发现，本文提出了名为Staged Lookup的分级缓存技术，以缩短文件检索的时延。Staged Lookup 通过缓存若干个被频繁访问的dentry目录项，采用多“起点”检索的方式，从而减少路径查找的时延。特别地，被缓存的频繁访问dentry结点被称为 pivot。在路径检索时，内核线程会在有限大小的pivot 池中选取一个最优的pivot作为起点进行检索。
Staged Lookup的主要挑战在于，如何选取最优的 pivot以及如何管理 pivot 池。为此，Staged Lookup采用了一个有序队列来组织pivot池并加速pivot的查找。除此，每个pivot 都记录其祖先dentry的权限信息，Staged Lookup 可以快速进行权限验证。值得注意的是，当目录的元数据被修改时（例如重命名），Staged Lookup 需要对pivot池进行维护。但由于pivot 数量有限，且维护操作可以采用异步的方式完成，实际产生的开销可以忽略。
本文主要的创新点包括：①提出了一种在Linux内核虚拟文件系统层的多层级路径检索优化策略Staged Lookup，其利用缓存频繁访问的目录并以此替代根结点作为路径检索起点的方式，减少重复dentry的查找；②分别在 Linux v3.14 和 v5.4 两个内核版本上实现了Staged Lookup 的原型系统，并利用真实服务器环境采集的路径检索负载开展测试；③利用一系列综合实验测试方法多角度评估Staged Lookup 原型的有效性和优化程度。
1 相关技术
1.1 路径检索操作
Linux 的路径检索操作主要发生在VFS层，而不是在具体底层文件系统上。当内核线程查找文件时，会切分路径的分量，即是一个个目录，然后逐个遍历并进行权限验证。为了避免频繁访问底层文件系统，Linux 内核在内存中维护了一个目录缓存，缓存中的每个单项都是一个dentry 结构体，记录着对应目录的元数据信息。为了方便查找dentry，内核维护了一个哈希表，把具有相同哈希值的dentry 放在同一个哈希桶中。在查找某个目录项时，内核线程会计算它的哈希值，继而找到对应的哈希桶，逐个比较桶中dentry 的父节点信息以及名字来确定目标 dentry。如果目录项不在目录缓存中，内核线程会向底层文件系统获取该目录的元数据，并建立对应的 dentry。
路径检索被频繁触发，而且涉及较多重复的目录查找，但Linux 内核从v3.x 到 v4.x 很少对路径检索的过程进行优化[11]，图2进一步利用LMBench探究v4.0 到v5.6 版本内核的路径检索时延，结果显示，路径深度越深，时延越高，相同路径深度情况下，时延趋势基本保持平稳，直到v4.15出现了阶跃，这是因为在v4.15 及以后的版本中，内核安装了内核页表隔离（kernel page table isolation， KPTI）补丁来应对两个重要漏洞：Meltdown[23] 和 Spectre[24]。这个补丁为内核和用户态页表提供了隔离，防止用户态应用利用旁路漏洞来获取内核数据。但在带来安全性的同时，KPTI 的引入对进出内核造成了4到5 倍的时延开销[25]，这也影响到路径检索的时延。
图2不同版本内核执行stat 的时延
Fig.2Latency of stat under different versions of Linux kernel
1.2 全路径索引
全路径索引不像Linux原生的逐级查找，是一种利用全路径哈希来直接索引目标文件的方式。这种方式既可以设计在文件系统层[26-29]，也可以在VFS 层[11]。全路径索引需要考虑如何有效地处理目录名、权限等元数据的修改，因为必然会带来哈希键[30]、值的维护。
在VFS层进行路径检索时，内核线程会先根据全路径计算哈希值，然后在哈希表上快速找到对应的dentry。但是一旦出现权限、名字被修改时，哈希表以及权限缓存中的所有相关条目都要被更新，这必然会对 rename、chmod 等操作的响应时间造成较大影响，时延开销会随着哈希表的大小而线性增长，达到几十倍甚至上百倍。
如何有效应对目录元数据的修改是全路径索引亟须解决的一个问题。文件系统层的全路径索引方式提出过一些解决办法，比如：BetrFS 用了两个Bε树来加速元数据更新[31]，后来提出Tree Surgery 来做进一步优化[27]。但在VFS 层，全路径索引仍然没有很好的处理办法。这驱使我们去重新思考在VFS层的路径检索优化，在减少检索时延的同时，更高效地处理元数据修改的问题。
2 Staged Lookup的设计
根据国家超算无锡中心“神威·太湖之光”超级计算机上的监控系统Beacon[22]的统计，检索的路径往往具有共同前缀，因为应用倾向于把文件放在同一个目录下。如果把最常被访问的前缀目录缓存起来，路径检索从这些目录开始而不是从根结点开始，可以避免很多冗余的目录遍历，从而加快路径检索的响应。本节主要介绍基于该思路Staged Lookup的设计方案。
Staged Lookup的设计目标，是通过减少冗余dentry 的访问，从而减少路径检索的时延。Staged Lookup 设计了一个名为pivot的数据结构，用于存储经常被访问的 dentry信息。路径检索的时候会选择一个pivot 作为起点而不是根结点（"/"）。图3展示了两个路径Path1和Path2的检索流程。当应用根据路径Path1检索文件foo时，Staged Lookup 选取pivot c1作为起点，经过 d1 找到 foo。在这个例子中，相比于内核中原生的流程（从根结点开始逐个遍历），Staged Lookup 把访问的目录数从原来的5个减少到了2个。
图3Staged Lookup 路径遍历举例
Fig.3Examples of Staged Lookup path traversal
不仅如此，Staged Lookup 还支持pivot的反向遍历，Staged Lookup 可以从某个pivot 开始，向上遍历它的若干祖先结点。当应用通过Path2路径检索文件bar时，Staged Lookup 选取pivot d2作为起点，反向找到 c2，然后再向下遍历d3和bar。在这个例子中，Staged Lookup 把访问的目录数从原来的5个减少到了3个。这个回滚操作，可以通过在pivot中记录其祖先信息来进行加速（详见2.2小节）。
2.1 Staged Lookup 架构
图4展示了Staged Lookup 的架构及工作流程，它包含两个模块（热度计数器、pivot管理器）和两个数据集合（候选集、pivot池）。
图4Staged Lookup的架构以及工作流程
Fig.4Architecture and workflow of Staged Lookup
每个dentry中都内嵌一个热度值，热度计数器用来管理dentry的热度值，每个dentry 在被访问的时候，热度值就会自增1，高热度值代表dentry被频繁访问，2.3.1小节会介绍如何更新维护热度值。而pivot管理器负责周期性地管理pivot池中的pivot。
候选集则实时动态地维护着若干拥有高热度值的dentry，作为下一周期的pivot候选。pivot池管理着所有的pivot，路径检索的时候，会在这里选取pivot作为起点
Staged Lookup在路径检索过程中可以分为两个阶段：阶段一为查找并选取一个最优的pivot作为路径检索起点，它一般是在所有pivot 中离目标文件最近的；阶段二为逐个遍历目标路径中剩余的分量，如果需要回滚，则先回滚到某个祖先结点再往下遍历。
2.2 选取最优pivot
Staged Lookup最大的优点在于它能灵活地选取路径检索的起点，而不是固定地从根结点开始。如何快速地选取最优的pivot（阶段一），决定了Staged Lookup的效率。 pivot池按照pivot的全路径字典序维护成一个有序队列，每个队列元素即是一个pivot，同时记录当前pivot与前一个pivot所共享的前缀长度（overlap值），通过这种机制可以减少大量的重复字符串比较。
图5展示了Staged Lookup选取最优pivot 的例子，假设要根据路径/a1/b1/c2/d2/e3/f3/foo 检索文件foo，Staged Lookup先拿目标路径与 pivot1的路径比较，c1不匹配转而与pivot2的路径比较，因为pivot1与pivot2共享前两个路径分量，所以直接从c2开始比较。同理相继与pivot3、pivot4比较，发现pivot4与pivot3没有重合前缀，因此pivot3（g3）就是要找的目标pivot。
图5查找最优pivot 过程
Fig.5Process of finding an optimal pivot
接着Staged Lookup 进入阶段二，它会从pivot3（g3）开始，往回滚一个结点到 f3，然后从 f3 再逐个遍历目标路径中剩余的分量。在这两个阶段中有一个优化是，在pivot 中记录它的祖先结点信息，Staged Lookup 可以在阶段一查找到 pivot3 的过程中，直接获取f3的信息，省略掉选取g3后往回滚到f3 的操作。这种优化下，Staged Lookup选取的最优pivot，一定是它或者它的祖先离目标文件最近的。
2.3 pivot的管理
前面介绍了如何使用pivot，本节将描述如何筛选和更新pivot。
2.3.1 热度值的维护
pivot是被频繁访问的目录结点，Staged Lookup 采用热度值这个属性去描述一个目录在最近时段内被访问的频次，为每个dentry都维护一个热度值。
当某个目录在一次路径检索中被访问时，其热度值就会自增1。另外，每个dentry 里记录了一个热度值的版本号，而内核也维护了一个周期性更新的全局版本号，当dentry 中的版本号与全局版本号匹配时，热度值才有效，否则会认为它过时并重置热度值，然后更新dentry中的版本号。
比如，当内核访问目录d1，Staged Lookup过程会检查d1的版本号，如果与全局版本号一致，d1的热度值加1，否则d1的热度值会被重置为1，再更新它的版本号。
全局版本号的更新，由pivot管理器在每次新周期到达时同步更新，周期时长是一个预设值，也是一个可以动态设置的值。
2.3.2 候选pivot的维护
在每个周期结束时，pivot管理器会被唤醒并进行pivot池更新。根据统计，一个本地文件系统会包含约100万个目录，显然遍历整个DCache找高热度的dentry是不可取的[12]。
Staged Lookup引入了一个候选集来维护若干个被频繁访问的dentry作为候选pivot，还设置了一个称为 least_popular_cand 的指针，指向候选集中“最少”被访问的dentry，其示意图见图6。在某个dentry被访问后，内核会把该dentry的热度值与 least_popular_cand所指dentry的热度值进行比较，如果后者加上一个阈值之和小于前者，least_popular_cand 所指dentry将会被当前dentry取代。阈值的作用是防止短时间内出现几个目录项交替地换入换出。
图6候选集示意图
Fig.6Schematic diagram of candidate set
举个例子，假设least_popular_cand 指向一个名为n1的dentry，阈值为tn，d1是当前被访问的目录项。当内核访问完d1后，会拿“d1的热度值”与“n1的热度值+tn”比较，如果前者较大，则n1会被移除，d1被插入候选集，同时 least_popular_cand 会指向d1。
least_popular_cand还会在候选集内部更新。每当候选集内某个dentry被访问并更新了热度值，它会被拿来跟least_popular_cand 所指dentry的热度值比较，least_popular_cand 会指向热度值较小者。
2.4 处理数据一致性
Staged Lookup的另一个重要问题就是元数据一致性，这个问题需要考虑两个场景：更新pivot池以及更新元数据。
2.4.1 更新pivot 池
pivot池的更新包括旧pivot的清除，以及生成新的pivot并插入。如果通过阻塞整个池来同步实现pivot的更新，会增加响应时延，Staged Lookup设置了一个辅助池来协同完成pivot 的更新。pivot 管理器在生成新pivot后会把它们插入到辅助池中，在这个过程中pivot 池保持它的工作状态，插入完成后，pivot管理器会交换两个池，辅助池变为新的 pivot池，原pivot池会变为辅助池并进入垃圾回收状态。内核中内置的读-拷贝-更新[32]（read copy update，RCU）机制被用来异步清理旧pivot，当旧pivot 没有被使用时，RCU回调函数会进行旧pivot 的释放。
2.4.2 更新元数据
元数据修改操作尤其是rename 和chmod 两种，会为Staged Lookup 带来一致性问题，所有相关的pivot 都要被处理。但相比于更新所有这些相关的pivot，Staged Lookup会直接删除清理，避免因阻塞更新带来的时间开销。因为pivot 的数量非常有限，所以是常数级的复杂度。
以图5为例，假设用户要把/a1/b1重命名为/a1/b2，所有相关的pivot，包括pivot1、pivot2和pivot3，都将会被标记为不可用，随后被异步地清理删除，但其他pivot不受影响。
而在周期更替期间，辅助池中新生成的pivot也可能会包含被修改的目录结点，Staged Lookup 会把整个辅助池都异步清理掉。
2.5 Staged Lookup 的开销
本节将分析 Staged Lookup 的各项主要开销。
2.5.1 检索的时间复杂度
路径检索时，内核原生方法会切分并解析每一个分量，分量会被扫描两次：一次用来计算哈希值，另一次用来验证dentry 名字。相似地，全路径索引也有两次类似的路径扫描。
对于Staged Lookup，参考图5的例子，有序队列以及overlap 值的设置，阶段一只遍历一次路径，而阶段二与内核原生方法一样，因此Staged Lookup 的基础时间复杂度要优于内核原生方法以及全路径索引。
2.5.2 移除pivot的时间开销
无论是pivot池周期性更新还是修改元数据，都需要清理pivot，主要是通过标记无效pivot 然后再清理。但考虑pivot 正在被使用的情况时，阻塞等待会影响响应时间，持续监听又会浪费线程资源。幸运的是，内核自带的RCU 机制提供了一种异步的方法来解决这个问题。在定义并关联一个回调函数后，内核每次产生RCU 软中断后，后台系统线程都会检查并执行回调函数。把pivot 的清理释放交给RCU，当前进程可以无须阻塞等待，因此移除pivot的时间开销仅为查找相关pivot 的时间。
2.5.3 内存占用
Staged Lookup在设计中，为 dentry 结构体创建了4个新成员，在32位和64位系统中分别占用18 B和30 B的空间。但新成员不是简单地插入到dentry 结构体中，因为会破坏dentry 的cacheline 对齐，而是占用了d_iname 成员的空间，它是一个字符数组，用来存储短文件名，但它本来就是个预留的空间，压缩d_iname并不会影响dentry的功能，因此dentry 并没有因为新成员而增加空间开销。
在候选集中，每个成员都是一个dentry，所以也没有额外的空间开销。主要的空间开销在于pivot池，在实验中，对于一个大小为16的pivot 池来说，总共占据约7 KB 的空间。
3 实验测试
本文将Staged Lookup与Linux 内核原生的路径检索方式（以下称为 Original Lookup）以及全路径索引[20]的方式（以下称为 Directory Cache）进行比较。实验中基于Linux 内核的v3.14 和v5.4 两个版本对 Staged Lookup 进行了部署，v3.14是为了与 Directory Cache 进行比较，v5.4是为了证明Staged Lookup 在新版本内核的有效性。
实验在一个单节点工作站上进行，该工作站配备了一个4核3.3 GHz 的Intel Xeon 处理器，8 GB RAM，以及一个1 TB 7200 RPM 的硬盘。工作站采用64位 Ubuntu 14.04 Server 系统，挂载 ext4 文件系统。Staged Lookup 的更新周期设置为2 s，pivot 池和候选集的大小为16。
3.1 检索性能基准测试
LMBench v3.0被选用作为benchmark 来测试 stat和 open操作的时延。
图7（a）展示了在3.14 版本内核环境下，stat或 open一个深度为8的路径时，各对比项的性能表现。与Original Lookup相比，Staged Lookup的stat和open操作分别减少了46.9%和 17%的时间开销；与Directory Cache相比，分别减少了39.4% 和10.2%的开销。
图7（b）展示了Original Lookup与Staged Lookup在5.6版本内核的环境下的性能表现，尽管KPTI补丁对响应时延有影响，相比于Original Lookup，Staged Lookup依然有明显的优势，Directory Cache没有参与对比，因为它无法兼容这个版本的内核，除非对它的开源代码进行大量的适配性修改。
图7路径检索时延LMBench测试
Fig.7Latency test of path lookup using LMBench
图8测试了Staged Lookup阶段一中pivot 数量对性能的影响，展示了Staged Lookup在阶段一中比较了不同数量的pivot后，响应时延的结果。横坐标N表示在阶段一中比较了各个数量的pivot后，阶段二仅需再遍历N个剩余分量完成检索。比如横坐标为6且pivot#=16，表示阶段一在比较了所有16个pivot后，在阶段二中还需遍历剩余的6个路径分量。对比Original Lookup，在最好的情况下（图8中横坐标为0且pivot#=1的组）Staged Lookup 减少了46.9% 的时间开销，然而在最坏情况（图8中横坐标为6且pivot#=16）下，Staged Lookup增加了将近10%的时间开销，因为在阶段一中查找了较多无效的pivot，同时还要遍历较多的剩余目录分量，这种情况一般出现在应用大量访问某些路径后，突然出现随机访问，这是Staged Lookup目前所不能很好应对的。
图8Staged Lookup阶段一的pivot数量对性能的影响
Fig.8The impact of the number of pivot in staged one gains of Staged Lookup on performance
3.2 真实应用负载的检索性能
基准测试之后，Staged Lookup会接受真实环境下的负载数据测试，进而进行性能评估，数据采集“神威·太湖之光”存储集群的客户端节点，利用“神威·太湖之光”的I/O监控系统 Beacon[22]，采集了4 d里真实应用对文件的访问行为，由于生产环境中不能随意修改服务器内核，实验是在测试机上建立了与存储集群上相同的目录树，让Staged Lookup重新执行相同的文件访问行为。
图9展示了Original Lookup、Staged Lookup和 Directory Cache3个对比项在测试中的时间开销，每个结果都是在相同的6次测试后取的平均值，每次测试都会清理 inode 缓存、目录项缓存以及页表缓存。以第二天的数据结果为例，相比于Original Lookup和 Directory Cache，Staged Lookup分别节省了29.6%和 21.3%的时间开销，Staged Lookup优胜于Original Lookup显然是因为它减少了冗余的路径分量遍历；而Directory Cache采用的全路径索引方式虽然查找较快，但它的缓存机制仅对再次访问的文件才有收益。相反，基于pivot的职能设计，Staged Lookup对第一次访问的文件同样有收益。根据对真实应用的观察，应用在运行过程中访问的文件，一般存放于相同的目录下，pivot能发挥较大的作用，因此Staged Lookup 比其他两个参照项，都具有较好的性能表现。
图9真实应用行为的路径检索时间开销
Fig.9The time cost of path lookup for real application behavior
3.3 元数据修改的性能
除了性能优化外，元数据修改操作的性能也需要被评估。为此，实验中建立了一棵6层高的目录树，包含有超过10 000个结点，前4层每个目录下包含10个子目录，第5层的目录下有若干个文件。在每轮测试之前，所有的缓存都会被清理，然后用 stat 操作对目录树上所有的结点进行访问，以创造热启动的环境。针对不同深度的目录，实验测试了重命名rename以及修改权限chmod操作。图10为重命名和修改权限的性能比较，其每个结果数据都是10轮测试后取的平均值，t的单位为μs。
图10重命名和修改权限的性能比较
Fig.10Performance comparison of rename and chmod system call
相比于 Original Lookup，理论上Staged Lookup 与 Directory Cache 因为引入了额外的机制，会在元数据修改中产生额外开销。图10结果表明，Directory Cache 方法引入了50~100倍的时间开销，这是因为修改目录元数据后，全路径索引对应的哈希表项都需要取遍历更新，哈希表越大，时间开销就越大，尤其在大访问量的服务器上，哈希表过大会产生难以接受的响应延迟。而 Staged Lookup 的时间开销几乎忽略不计，基本与 Original Lookup 持平。这是因为在修改目录元数据时，Staged Lookup 只需要处理有限数量的pivot，而且只是标记受影响的pivot，实际的清理工作由内核异步执行。
4 结论
本文提出了一种名为Staged Lookup的VFS路径检索优化方法，测试结果表明该方法能有效减少检索文件的时延。不同于内核原生的路径检索，Staged Lookup避免从目录树根节点（"/"）开始检索，而是从提前缓存被频繁访问的若干个dentry结点中选取一个作为路径检索起点，然后再逐个结点遍历最后找到目标文件。Staged Lookup 已经分别成功部署在 Linux v3.14和 v5.4两个内核版本上，相比内核原生的路径检索方式和全路径索引方式，Staged Lookup相应分别减少了高达 46.9% 和39.4%的stat操作时间开销，open操作也分别减少了17%和10.2%的时延。除此之外，Staged Lookup在应对基于真实应用负载的测试中，展现出29.6%的性能优势。而在维护元数据一致性所产生开销中，如rename、chmod等操作，Staged Lookup由于采用小规模缓存以及异步维护的方式，时间开销几乎与内核原生路径检索策略处于同一水平。
