计算机应用   2017, Vol. 37 Issue (5): 1241-1245  DOI: 10.11772/j.issn.1001-9081.2017.05.1241
0

引用本文 

杨顺, 陈志广, 肖侬. Pmfs中目录项索引的实现[J]. 计算机应用, 2017, 37(5): 1241-1245.DOI: 10.11772/j.issn.1001-9081.2017.05.1241.
YANG Shun, CHEN Zhiguang, XIAO Nong. Implementation of directory index for Pmfs[J]. JOURNAL OF COMPUTER APPLICATIONS, 2017, 37(5): 1241-1245. DOI: 10.11772/j.issn.1001-9081.2017.05.1241.

基金项目

国家863计划项目(2015AA015305)

通信作者

杨顺,792454122@qq.com

作者简介

杨顺 (1992-), 男, 湖北荆州人, 硕士研究生, 主要研究方向:非易失存储器、文件系统;
陈志广 (1984-), 男, 湖北襄阳人, 助理研究员, 博士, CCF会员, 主要研究方向:高性能存储、高性能计算;
肖侬 (1969-), 男, 江西南昌人, 研究员, 博士生导师, 博士, CCF会员, 主要研究方向:高性能计算、大规模网络存储

文章历史

收稿日期:2016-07-15
修回日期:2016-12-07
Pmfs中目录项索引的实现
杨顺, 陈志广, 肖侬    
国防科学技术大学 计算机学院, 长沙 410073
摘要: 可字节寻址的非易失存储介质,如相变存储器等,使数据可以在内存级别持久化。由于非易失存储器(NVM)本身的读写延时非常低,系统软件开销成为了决定整个持久化内存系统性能的主要因素。Pmfs是一个专门为持久化内存所设计的文件系统,然而,Pmfs下的每个目录操作(打开、创建或删除)都会遍历目录下的所有目录项,导致了随文件数增长而线性增长的目录项查找开销。通过测试发现,在特定类型负载下这种开销成为了整个文件系统的瓶颈。针对该问题,在Pmfs中实现了持久化的目录项索引来加速目录操作。测试结果显示,基于单目录下100000文件的负载,该优化使得文件创建速度提高了12倍,带宽增加了27.3%。
关键词: 持久化内存    目录项索引    文件系统    非易失存储器    
Implementation of directory index for Pmfs
YANG Shun, CHEN Zhiguang, XIAO Nong     
College of Computer, National University of Defense Technology, Changsha Hunan 410073, China
Abstract: Emerging non-volatile, byte-addressable memories like phase-change memory can make data persistent at main memory level instead of storage. Since the read/write latency of Non-Volatile Memory (NVM) is very low, the overhead of software in a NVM system has become the main factor in determining the performance of the entire persistent memory system. Pmfs is a file system specifically designed for NVM. However, it still has an undesirable characteristic:each directory operation (create, open or delete) of Pmfs requires a linear search of the entire directory files, resulting in a cost linearly increased with the number of files in the directory. The performance of Pmfs under various workloads was evaluated and the test showed that the overhead of the directory operations had become the bottleneck of the whole system in some circumstance of particular workloads. To solve this problem, a persistent directory entry index was implemented in Pmfs to speed up directory operations. The experimental results show that under a single directory with 100 000 files, the file creation speed is increased by 12 times, the bandwidth is improved by 27.3%.
Key words: persistent memory    directory index    file system    Non-Volatile Memory (NVM)    
0 引言

随着可字节寻址的非易失存储器 (Non-Volatile Memory, NVM) 技术的不断成熟,大容量、低延时、高带宽的持久化内存系统呼之欲出,工业界和学术界都为此展开了大量工作。其中, Pmfs[1]是专为NVM设计的文件系统,它使用访存指令将数据直接存放在NVM中,从而绕开了传统文件系统的通用块层和块设备驱动层;同时,Pmfs使用了虚拟文件系统 (Virtual File System, VFS) 的就地执行 (eXcute In Place, XIP) 接口,绕开了页高速缓存 (pagecache),使得数据在持久化的过程中只需要一次拷贝,大幅度减少了数据存储的软件开销。

和Pmfs类似的工作还有Bpfs[2]、Scmfs[3]等,由于Pmfs的性能优势,许多工作将Pmfs作为性能对比的基准[7-8],或者在Pmfs上进行二次开发[4-5]。然而在Pmfs中, 每个目录操作 (打开、创建或删除) 都会遍历目录下的所有目录项,导致了随文件数增长而线性增加的目录项查询开销。由于NVM本身的读写延时非常低,在特定类型的负载下,目录项查询的开销成为了整个数据持久化过程中的瓶颈。

与传统的外存系统不同,Pmfs将数据从处理器通过内存总线持久化在NVM设备中,由于处理器对指令的重排和高速缓存 (cache) 对数据的暂存,数据的顺序性被破坏,因此,持久化数据的一致性无法得到保证。现有的工作主要通过处理器提供的clflush和fence指令[9]来保证数据持久化的顺序性。然而这些指令会带来较大的额外开销,在本文中这种为了保证数据一致性所带来的额外系统软件开销被称为一致性开销。虽然英特尔 (Intel) 已经提出了新的指令来减少这种一致性开销,但是还没有推出任何实际的产品。在Pmfs中实现的持久化目录项索引必定带来额外的写操作,增加了一致性开销。本文通过在不同负载下对Pmfs进行测试,分析了持久化目录项索引带来的一致性开销以及对文件系统整体性能的影响。测试结果显示,在单目录下100 000负载下,该优化使得Pmfs的文件创建速度增加了12倍, 带宽增加了27.3%。

本文的主要工作有以下3点:

1) 通过测试Pmfs在不同负载下的性能,发现在单目录下文件数量急剧增加时,目录操作 (打开、创建或删除) 成为了Pmfs的性能瓶颈。

2) 在Pmfs上增加了持久化目录项索引,该目录项索引能融入到所有以Pmfs为基础开发的系统中,如Nova[4]、Hinfs[5]等。

3) 分析了Pmfs在不同负载下,持久化目录项索引带来的一致性开销和文件系统整体性能的影响。

1 背景和动机 1.1 非易失存储器

当前主要的新型非易失存储器件包括相变存储器[6]、铁电存储器[7]、忆阻器[8]、自旋矩传输存储器[9]和三维堆叠的闪存[10]等。相对于动态随机读写存储器 (Dynamic Random Access Memory,DRAM), NVM在集成度、耗能等方面存在很大的优势。同时,NVM还具备与DRAM相近的读写性能和DRAM所不具备的非易失特性, 例如,STTRAM的读写延时都只需要20 ns。因此,近年来许多工作[1-5, 11-14]都在探究如何用NVM来构建同时提供内存级别的性能和非易失性的存储系统。

1.2 NVM中的数据一致性

作为外存系统中最重要的一个原则,数据一致性保证了当系统意外宕机时,数据可以被正确地恢复。为保证数据的一致性,一次写操作应该将数据全部写入到持久化设备中或者向上层应用返回失败信息,保证不会出现部分写入的情况。然而以连接在内存总线上的NVM作为持久化设备时,处理器只能保证64 b的原子写操作,因此在更新更大粒度的数据时,需要在软件层使用一定的策略来保证持久化数据的一致性。在传统的存储系统中,常见的策略有写时复制 (Copy On Write,COW)、日志等。这些策略先写数据备份,然后再修改数据本身,因此这些策略的前提是在一定程度上保证数据写入的顺序性。例如在更新一个B-树的某个节点且写入的数据大于64 b时,则需要使用COW策略,即先写入新的子节点数据,然后修改父节点的指针。如果先修改父节点指针,且系统意外宕机,数据将不能被正确恢复。

然而,当数据从处理器被写入到NVM时,数据会被处理器和内存控制器进行暂存和重排,因此,许多系统都使用fence (包括mfence和sfence) 和clfush的组合命令[15]来保证数据写入内存的顺序性。其中fence可以保证fence指令前的所有指令执行完之前,fence指令后的所有指令的执行都会被阻塞;另一方面,clfush则保证了将处理器的某个高速缓冲行立即刷写到内存中。这种指令组合虽然保证了数据写入的顺序性,但是clfush会失效高速缓存行,一次这样的组合指令的平均开销开销为250 ns[18]。由于NVM本身的低延时,这样的系统软件开销无法忽略不计。虽然Intel提出了新的指令组合 (CLWB/CLFLUSHOPT/ PCOMMIT)[16]来优化性能,但是还没有推出实际的产品。因此在设计NVM存储系统的上层软件时,如何减少这样的一致性开销十分重要。

1.3 目录项索引

在传统的文件系统中,目录项索引主要分为两大类:一类是缓存目录项索引[17],即把目录项索引存放在DRAM中,而不用存放在持久化设备中;另一类是持久化目录项索引,即目录项索引和其他文件元数据一样,需要被存放在持久化介质中,如Linux的原生文件系统EXT4中的Htree目录项索引,ReiseFs[18]中的B-树目录项索引。由于缓存目录项索引会消耗大量DRAM空间以及冷启动问题,本文在Pmfs中选择了持久化索引。

通过阅读Pmfs源码发现,Pmfs所采用的目录项数据结构和EXT文件系统一致,因此,本文在Pmfs目录项索引的实现中,采用了Htree数据结构。Htree是Btree的变种,具有和Btree相同的查询、删除、插入的时间复杂度;不同的是,Htree中所有的叶子节点高度完全相同。

1.4 相关工作和动机

目前,使用NVM持久化数据的系统主要可以分为三类: Nvheap[11]和Mnemosyne [12]通过操作系统的内存管理模块统一管理NVM和Dram,提供给程序员持久化的堆或栈;文献[1-5]使用文件系统来管理NVM,在文件系统层直接调用访存指令,而传统的文件系统则是经过通用块层,设备驱动层将生成相关Scsi或者NVMe指令,再通过相关传输协议发向持久化设备的控制器; PMBD[13]则是在设备驱动层来将数据流导向NVM,然而这种方式不能有效保证数据的一致性。

采用文件系统的方式来管理NVM对于应用程序有很好的兼容性,传统应用程序不需用任何更改即可使用以NVM作存储设备的系统中,因此,该方法受到了广泛关注。Pmfs作为众多NVM文件系统中的一种,以高性能和开创性成为了其他工作测试对比的基准[19-20],还有许多工作是直接在Pmfs上进行二次开发[4-5]

然而,通过测试发现,Pmfs在某些类型负载下性能急剧下降,这些负载的特点如表 1所示。

表 1 filebench中三种不同类型负载的特点描述和性能统计 Table 1 Features and performance statistics of three different types of load in filebench

表 1展现了这些负载的特点 (文件数100 000)。该测试分为两部分:第1部分为文件的预分配,性能指标为文件分配延时; 第2部分是一定比例的文件读、写、创建和删除操作,性能指标为平均带宽,这部分性能受到很多因素影响,如读写比例、平均文件大小、读写粒度等。从表 1中可以看出,webproxy的文件创建耗时相比其他两种类型负载大幅增加,webserver和webproxy的带宽远远低于fileserver。为了确认影响性能的关键因素,使用filebench自定义了6种负载 (如表 2所示,其中文件数100 000) 进行测试。

表 2 自定义不同类型负载的特点描述和性能统计 Table 2 Features and performance statistics of six self-defined different types of load

表 2测试结果可以看出,在其他因素相同时,随着目录宽度减少和文件大小增加,预分配延时降低,总带宽增加。当100 000文件全在一个目录下时,平均文件长度不同的两种类型负载 (表 2中的负载3和负载6) 的文件预分配耗时分别高达37 s和42 s,带宽也有大幅度下降,这很可能是由于线性的目录项查找开销所引起。为了证明这种猜想和解决该性能瓶颈,本文在Pmfs中实现了持久化目录项索引来加速文件目录操作,并测试分析了所实现的目录项索引对整个文件系统性能的影响和带来的一致性开销。

2 数据结构和实现 2.1 数据结构

Htree[21]是一种专为目录项索引设计的树形数据结构,和B-树类似,具有相同的查找、插入和删除的时间复杂度。不同的是,Htree中所有的叶子节点的深度完全相同。Htree使用文件名的hash作为键值来进行查找,叶子节点是目录项所在的数据块,而不是目录项本身。因此,目录项的查找过程可以分为两步:第1步是通过树形索引查找到目录项所在的数据块,第2步则是在数据块线性地查找目标目录项,这样的设计大大减少了索引块的数量。如果文件名出现了Hash冲突,则使用线性探测的方法沿叶子节点查找,可能跨越多个数据块。

图 1为Htree的一个快照,Block1中开头为“.”和“..”两个目录项,后面两个索引项分别指向Block2和Block3,这里的指针指向的是数据块在文件中的逻辑正文内容地址而不是物理地址。在Htree中之所以使用逻辑地址,本身是以额外的地址转换开销为代价,使得实现起来更加方便。而在Pmfs中,数据块在文件逻辑中的逻辑地址到物理地址转换只需要O(1) 的时间复杂度。

图 1 Htree结构示意图 Figure 1 Htree structure diagram

以查找图 3中的目录项file2为例,首先将文件名file2转换成hash值,然后在根索引块中行查找,得到Block3的逻辑。根据元数据中的目录项高度信息可以判断该Block3为数据块而不是索引块,继而通过遍历Block3即可找到file2。

2.2 实现

通过dir_index挂载选项可以打开Pmfs的目录项索引功能,具体可参考文献[22]的源码链接。

2.2.1 兼容性

该实现没有修改任何原有的数据结构,当目录项索引损坏时,依然可以使用遍历的方式来查找目录项,保证了不管以什么模式重新挂载使用或没有使用目录项索引的Pmfs文件系统,都可以正常工作。

2.2.2 一致性

在Pmfs中,使用轻量级日志和COW来保证目录项数据的一致性。该日志每一个目录项大小为64 B,其中48 B用来写日志数据,其他16 B为日志元数据。以增加目录项为例,Pmfs找到准备写入目录项的数据块块号和偏移量,先将该地址和要写入的数据写入日志,然后再写入目录项数据。在增加了持久化目录项索引后,则需要考虑如何保证索引和目录项数据的一致性。

由于索引块中的索引项必须保证一定的顺序,每次写入新的索引时会造成写放大效应,即需要写入该索引项和排在该索引项后面的所用索引项,再鉴于索引的树状结构,本文使用COW策略来保证目录项索引一致性,而不是使用Pmfs所提供的轻量级日志。

3 实验评估

本章将通过实验分析所增加的目录项索引对文件系统的两个方面的影响:

1) 持久化目录项索引对一致性开销的影响;

2) 目录项索引对文件系统整体性能的影响。

本文使用filebench标准测试工具,以及表 1中的负载来进行测试。这些负载的测试分为两个部分:第1部分是文件的预分配,所有负载的文件数量都为100 000,预分配数量为总文件数的80%,即80 000;第2部分则是通过一定比例的文件读、写、创建和删除操作来测试文件系统的IOPS (Input/Output Operations Per Second) 和带宽。本文通过测试在相同负载下,Pmfs在增加持久化目录项索引前后执行的fence和flush指令数量的变化来分析问题1);对于问题2),则通过相同负载的文件预分配耗时和平均带宽来分析。

本文使用DRAM来模拟NVM,即通过Linux的mmap启动选项从操作系统中隔离出一部分内存来供Pmfs使用。具体的实验环境配置如表 3所示。

表 3 测试环境配置参数 Table 3 Configuration parameters for test environment
3.1 一致性开销评估

本文通过在Pmfs中增加全局变量来统计每次测试中执行的fence和flush指令数量。由于每次执行fence和flush操作时会对该全局变量进行修改以及产生多线程环境下的同步开销,增加该统计功能的Pmfs性能会有所下降; 再者,由于Pmfs在增加持久化目录项索引项前后的性能发生变化,即使不考虑所增加的目录项索引导致的持久化操作,对于同一负载执行相同时间的一致性开销也会有较大变化。因此,这里的测试指标为Pmfs每读写1 MB数据,平均消耗的fence和flush指令的数量。

图 2是通过表 2中的负载所测得的测试结果。可以看到,负载4中的一致性开销在增加目录项索引前后的变化最大,fence和flush指令数量分别增加了9.6%和7.0%;而其他两种类型负载的一致性开销变化较小。这是因为负载4的目录宽度很大,会有较多的目录项索引,导致了额外的一致性开销。

图 2 自定义负载下Pmfs增加目录项索引前后一致性开销对比 Figure 2 Consistency cost statistics before and after adding directory index
3.2 整体性能评估

目录项索引带来的整体性能变化通过两个方面体现:一方面是Pmfs在相同负载下的文件创建速度的变化;另一方面是Pmfs在相同负载下平均带宽的变化。测试结果分别如图 3图 4所示,其中所有数据为多次测试的平均值。

图 3 表 1负载下Pmfs增加目录项索引前后性能对比 Figure 3 Performance statistics of three loads in Tab. 1
图 4 自定义负载下Pmfs增加目录项索引前后性能对比 Figure 4 Performance statistics of six loads in Tab. 2 before and after adding directory index

图 3描述了表 1中的三种负载的测试结果,可以看到,在增加了持久化目录项索引后,Pmfs在负载webproxy下的文件预分配延时降低了91.7%,带宽增加了25.3%。由于其他两种类型负载的目录宽带较小,因此目录项索引对性能影响较小,文件预分配耗时没有变化,带宽分别增加了1%和1.5%。图 4描述了目录项索引对表 2中自定义的6种负载的性能影响。从中可以看出,目录宽度为200 000的负载3和负载6性在增加目录项索引前后性能变化较大,它们的文件预分配耗时分别减少了91.9%和92.8%,带宽分别增加了27.3%和15.5%,而其他类型负载的各项性能略微提升。从图 3图 4中还可以看出,在无目录项索引时,负载webproxy,类型3和类型6的文件预分配延时远远高于其他负载。在增加目录项索引后,所有负载的该项指标基本一致,并且负载6的带宽也达到了6种负载增加目录索引前后的最大值。综上可见,在单目录下的文件数急剧增加时,文件系统的性能会大幅下降,通过增加目录项索引,对于单目录下100 000文件的负载,文件预分配耗时最多减少了92.8%, 带宽最多增加了27.3%。

4 结语

本文通过测试发现在单目录下文件量很大时,Pmfs的性能急剧下降,通过添加持久化的目录项索引,在带来了一定一致性开销的情况下,消除了目录项查找这一性能瓶颈。该优化适用于所有在Pmfs上进行二次开发的系统。

然而,在测试过程中发现,Pmfs还有很多地方存在性能瓶颈,如块分配器锁粒度太大导致并发写时的性能瓶颈。接下来,将不断地对Pmfs进行优化。只有这样经过多方优化后的Pmfs,在与传统文件系统对比时,才能体现出非易失内这种架构上的变化所带来的性能影响。

参考文献
[1] DULLOOR S R, KUMAR S, KESHAVAMURTHY A, et al. System software for persistent memory[C]//Proceedings of the 9th European Conference on Computer Systems. New York:ACM, 2014:Article No. 15.
[2] CONDIT J, NIGHTINGALE E B, FROST C, et al. Better I/O through byte-addressable, persistent memory[C]//Proceedings of the 22nd ACM Symposium on Operating Systems Principles. New York:ACM, 2009:133-146.
[3] FREITAS R F, WILCKE W W. Storage-class memory:the next storage system technology[J]. IBM Journal of Research & Development, 2008, 52(4/5): 439-447.
[4] XU J, SWANSON S. NOVA:a log-structured file system for hybrid volatile/non-volatile main memories[C]//Proceedings of the 14th USENIX Conference on File and Storage Technologies. Berkeley, CA:USENIX Association, 2016:323-338.
[5] OU J, SHU J, LU Y. A high performance file system for non-volatile main memory[C]//Proceedings of the 11th European Conference on Computer Systems. New York:ACM, 2016:Article No. 12.
[6] 刘波, 宋志棠, 封松林, 等. 我国相变存储器的研究现状与发展前景[J]. 微纳电子技术, 2007, 44(2): 55-61. ( LIU B, SONG Z T, FENG S L, et al. Current situation and developing trend on phase-change memory in China[J]. Micronanoelectronic Technology, 2007, 44(2): 55-61. )
[7] SCOTT J F.铁电存储器[M].朱劲松, 吕笑梅, 朱旻, 译.北京:清华大学出版社, 2004:1-200. ( SCOTT J F. Ferroelectric Memories[M]. ZHU J S, LYU X M, ZHU M, translated. Beijing:Tsinghua University Press, 2004:1-200. )
[8] 田晓波. 忆阻器电路特性与应用研究[D]. 长沙: 国防科学技术大学, 2009. ( TIAN X B. Study on the characteristic and application of memristor circuits[D]. Changsha:National University of Defense Technology, 2009. )
[9] HUAI Y. Spin-Transfer Torque MRAM (STT-MRAM):challenges and prospects[J]. AAPPS Bulletin, 2008, 18(6): 33-40.
[10] Breakthrough nonvolatile memory technology[EB/OL].[2016-08-10]. https://www.micron.com/about/emerging-technologies/3d-xpoint-technology.
[11] VOLOS H, TACK A J, SWIFT M M. Mnemosyne:lightweight persistent memory[J]. ACM SIGARCH Computer Architecture News, 2011, 39(1): 91-104. doi: 10.1145/1961295
[12] COBURN J, CAULFIELD A M, AKEL A, et al. NV-Heaps:making persistent objects fast and safe with next-generation, non-volatile memories[J]. ACM SIGPLAN Notices, 2011, 46(3): 105-118. doi: 10.1145/1961296
[13] HAHN S. A protected block device for persistent memory[C]//Proceedings of the 201430th Symposium on MASS Storage Systems and Technologies. Piscataway, NJ:IEEE, 2014:1-12.
[14] LU Y, SHU J, SUN L, et al. Loose-ordering consistency for persistent memory[C]//Proceedings of the 2014 IEEE 32nd International Conference on Computer Design. Piscataway, NJ:IEEE, 2014:216-223.
[15] BHANDARI K, CHAKRABARTI D R, BOEHM H J. Implications of CPU caching on byte-addressable non-volatile memory programming[EB/OL].[2016-06-20]. http://hpl.hp.com/techreports/2012/HPL-2012-236.pdf.
[16] Intel64 and IA-32 architectures software developer's manuals combined[EB/OL].[2016-10-08].http://www.intel.com.
[17] PHILLIPS D. A directory index for ext2[C]//Proceedings of the 5th Annual Linux Showcase & Conference. Berkeley, CA:USENIX Association, 2001:20.
[18] REISER H. ReiserFS v.3 Whitepaper[EB/OL].[2016-10-08].http://web. archive.org/web/20031015041320.
[19] SEHGAL P, BASU S, SRINIVASAN K, et al. An empirical study of file systems on NVM[C]//Proceedings of the 201531st Symposium on Mass Storage Systems and Technologies. Piscataway, NJ:IEEE, 2015:1-14.
[20] SHA H M, CHEN X, ZHUGE Q, et al. Designing an efficient persistent in-memory file system[C]//Proceedings of the 2015 IEEE Non-Volatile Memory System and Applications Symposium. Piscataway, NJ:IEEE, 2015:1-6.
[21] BSDDirhash[EB/OL].[2016-10-08]. http://groups.yahoo.com/group/freebsd-hackers/message/62664.
[22] dir-index-pmfs[Z/OL].[2016-10-08].https://github.com/dir-index-pmfs/dir-index-pmfs.