关键词:
非易失性存储器
文件系统
可扩展哈希
高并发
摘要:
随着互联网技术的飞速发展,爆发式增长的数据给文件系统带来巨大的压力。新兴的非易失性内存NVM(Non-Volatile Memory),具有非易失性、可字节寻址、低延迟和读写速度接近内存等优势,为打破文件系统的性能瓶颈带来了希望。但现有的文件系统在应对海量数据时存在可扩展性差和并发度低等问题,难以有效发挥NVM设备的优势。可扩展哈希具有快速读写以及可动态扩展的优势,但由于其哈希目录和哈希桶也存在并发性低等问题,若直接与文件系统相结合并不能有效提高文件系统的并发性。因此,本文先后对可扩展哈希和文件系统进行优化,以提高文件系统的并发性为目标,研究与设计基于可扩展哈希的NVM文件系统。首先,分析当前可扩展哈希和文件系统面临的挑战,对可扩展哈希进行改进,并在此基础之上对文件系统的元数据管理算法进行了优化,设计了基于可扩展哈希的NVM文件系统的结构,包括面向NVM的高并发可扩展哈希模块和融入驱动的高并发元数据管理算法模块,通过有效发挥NVM存储设备读写速度快等优势,提高文件系统的并发性,满足对海量数据并发访问的要求。接着,针对当前可扩展哈希中哈希目录并发性差、哈希桶管理效率低等问题,研究并设计了面向NVM的高并发可扩展哈希。设计了基于惰性扩展的哈希目录,将哈希目录扩展时的加锁粒度缩小为导致扩展的单个哈希目录项,提高可扩展哈希的并发性。设计了扩张率计算算法,通过动态决定二次扩展哈希目录的大小,在降低哈希目录扩展频率的同时,避免不必要的哈希目录扩展。设计了基于组的哈希桶管理算法,将现有可扩展哈希目录下挂载的单个哈希桶分解为多个桶,并增加桶目录,提高哈希桶管理的并发度。同时改变哈希桶内哈希键的管理方式,缩小插入哈希键时的加锁粒度,减少哈希桶的分裂几率,从而提高可扩展哈希的并发度。设计了基于分层存储的哈希目录恢复策略,将哈希目录和哈希桶分布存储在DRAM和NVM中,在有效利用DRAM和NVM存储设备各自优势提高访问速度的同时,保证可扩展哈希中数据的一致性。在Intel开源的NVM存储设备驱动中,嵌入了所设计的算法,实现了面向NVM的高并发可扩展哈希原型NEHASH,使用测试工具YCSB进行了测试和分析,结果表明NEHASH比现有的哈希方案CCEH、LEVEL和CUCKOO具有更高的并发度,在多线程环境下能最大提高16.5%的读吞吐率和19.3%的写吞吐率。最后,针对文件系统I/O软件栈过长以及元数据管理算法效率低、并发性差的问题,并在面向NVM的高并发可扩展哈希基础上,研究和设计了融入驱动的高并发元数据管理算法。将文件系统的元数据管理功能嵌入NVM设备驱动中以缩短I/O软件栈,并给出融入驱动的高并发元数据管理算法的结构。设计了基于Fs_simhash的元数据Key-Value对生成策略,将文件和目录的访问路径转换为哈希值,构建Key-Value对来存储哈希值与对应元数据的存储地址,提高元数据的查询效率;在局部敏感哈希函数的基础上设计Fs_simhash函数,使得相邻的访问路径转换后的哈希值相近,为提高元数据的存储和查找性能提供支撑。设计了基于NEHASH的元数据管理策略,针对文件和目录的不同访问特性,对NEHASH的数据桶进行分解,并以不同的哈希函数对文件和目录的路径进行转换,在提高单个元数据查询效率的同时,有效的保证了范围查询、遍历等局部性较强操作的效率。在Intel开源的NVM存储设备驱动基础上,实现了融入驱动的高并发元数据管理算法原型HANVFS,使用Filebench、Fio和IOzone三种测试工具对HANVFS的读写吞吐率和读写带宽进行测试,结果表明HANVFS与在PMEM上加载的NOVA文件系统相比最大能提高30.6%的读写吞吐率与24.7%的读写带宽。