基于非易失内存的高效索引方法及应用研究

发布时间：2020-10-27 13:35

　　 在大数据背景下,计算机系统对内存容量的需求越来越大。传统基于动态随机存取存储器(Dynamic Random Access Memory,DRAM)的内存系统在制造工艺和能耗上正面临着巨大的挑战,难以满足大数据时代的需求。随着材料和存储技术的迅速发展,以相变存储器(Phase Change Memory,PCM)和阻变存储器(Resistive Random Access Memory,RRAM)为代表的新型非易失内存(Non-Volatile Memory,NVM)开始出现。NVM具有掉电非易失、按字节修改寻址、快速访存、高存储密度、低静态功耗等优点,这些优良特性让NVM可以和DRAM一起组成混合内存系统,甚至在未来完全取代DRAM成为内存系统的主要存储介质。当NVM作为计算机内存的时候,高效的索引结构对于提升数据查询和空间管理的效率非常重要。然而,传统基于DRAM的索引结构并不能高效应用于新型NVM设备,因为它们既没有考虑NVM写性能较差和耐久性较低等缺陷,也无法保证系统意外断电情况下的数据一致性。本文探讨了基于NVM的索引结构面临的数据一致性、较差的写性能和较低的耐久性等问题,从单点查询和范围查询两个方面提出了解决方案,并从文件系统的角度给出了一种NVM索引结构的应用场景。本文的主要研究内容和创新点如下。针对传统哈希索引结构没有考虑到NVM存在的缺陷和数据一致性的问题,提出了一种基于NVM的高性能哈希索引结构Group hashing,减少了数据一致性带来的开销,降低了CPU Cache的失效率,提升了哈希索引的查找、插入和删除性能。Group hashing利用8字节原子写技术保证数据一致性,这样可以避免日志或者写时复制技术的使用,减少对于NVM的写操作以及一致性带来的额外开销。Group hashing提出了一种名为组内共享的技术,将哈希索引空间划分为多个地址连续的分组,把同一个分组内的哈希冲突单元存放到相匹配的分组里,在高效解决哈希冲突的同时降低了CPU Cache的失效率。此外,Group hashing还包含了一种组内再哈希的方法,降低了哈希冲突时在分组内搜索目标哈希单元带来的延迟,从而进一步提升哈希索引的查找性能。实验结果表明,Group hashing在三种真实负载下的查找、插入和删除性能和CPU Cache效率都要优于现有基于NVM的哈希索引结构。针对现有基于NVM的单一索引结构无法同时高效支持单点查询和范围查询这一问题,提出了一种基于NVM与DRAM结合的高性能混合索引方法HSHI,充分发挥了不同索引结构的优点,高效支持了范围查询,提升了混合索引的查找、插入和删除性能。HSHI使用哈希索引和跳跃表(Skiplist)组成混合索引:哈希索引作为主要索引位于NVM,用来处理查找、插入、删除等基本操作;跳跃表作为辅助索引位于DRAM,用来处理范围查询操作。HSHI对DRAM上的跳跃表采用异步更新机制,这样可以降低混合索引的写延迟。为了减少混合索引的一致性开销,HSHI利用8字节原子写保证数据一致性。此外,HSHI还使用了一种细粒度的锁机制来支持混合索引的并发访问。实验结果表明,HSHI能高效支持范围查询,而且在单线程和多线程负载下的查找、插入和删除操作性能都要优于现有支持范围查询的NVM索引结构。文件系统是索引结构应用的一个重要领域。针对传统文件系统日志技术无法高效应用于新型NVM设备的问题,提出了一种基于NVM的文件系统日志技术NJS,减少了文件系统的日志开销,提升了文件系统的写性能。为了减少对于NVM的写入数据量,NJS只将覆盖写数据和文件系统元数据写入到NVM,而追加写数据则直接写入文件系统。NJS提出了一种基于磨损感知的日志块分配方法,在每次分配空闲NVM日志块的时候,NJS都会选择磨损次数最少的日志块,从而提升NVM的使用寿命。NJS利用哈希索引管理NVM日志区域,并在此基础上提出了一种字节粒度的日志块更新策略,当NVM中的日志块需要更新的时候,NJS通过哈希索引寻找已有的旧版本日志块,利用旧版本实现就地更新,这样可以充分利用NVM按字节修改的特性。NJS还包含了一种垃圾回收机制用于回收无效日志块,可以减少日志数据写回到文件系统的频率,从而进一步提升文件系统的性能。实验结果表明,与采用Ramdisk作为日志设备的Ext4相比,NJS在不同负载下的吞吐量平均提升了57.1%。
【学位单位】：华中科技大学
【学位级别】：博士
【学位年份】：2019
【中图分类】：TP311.13;TP333
【文章目录】：
摘要
Abstract
1 绪论
    1.1 NVM研究背景和面临的挑战
    1.2 相关研究现状
    1.3 本文的主要研究内容和组织结构
2 基于非易失内存的高性能哈希索引结构
    2.1 研究背景和研究动机
    2.2 基于非易失内存的哈希索引总体设计
    2.3 哈希索引的基本操作算法
    2.4 时间复杂度分析
    2.5 性能评估与结果分析
    2.6 本章小结
3 基于非易失内存与DRAM结合的高性能混合索引方法
    3.1 研究背景和研究动机
    3.2 混合索引的总体设计
    3.3 混合索引的数据一致性保障方法
    3.4 性能评估与结果分析
    3.5 本章小结
4 基于非易失内存的文件系统日志技术
    4.1 研究背景和研究动机
    4.2 基于非易失内存的文件系统日志技术总体设计
    4.3 磨损感知的日志块分配策略
    4.4 基于非易失内存的文件系统日志技术的操作模块
    4.5 实验测试与结果分析
    4.6 本章小结
5 全文总结与展望
    5.1 主要成果
    5.2 研究展望
致谢
参考文献
附录1 攻读博士学位期间发表的学术论文目录
附录2 攻读博士学位期间申请的发明专利和其他成果
附录3 攻读博士学位期间参与的科研项目

【相似文献】

相关期刊论文 前10条

1 严赵峰;张为华;;面向大数据的索引结构研究进展[J];大数据;2019年04期

2 胡杰;何新华;吕庆星;;一种支持快速相似检索的多维索引结构[J];通讯世界;2016年07期

3 古毅;吴中福;魏丽;钟将;马金亮;;高维空间数据索引结构分析研究[J];计算机科学;2006年05期

4 冯玉才,曹奎,曹忠升;一种支持快速相似检索的多维索引结构[J];软件学报;2002年08期

5 侯臻燕;;〈化学亚结构索引〉用法简介[J];大学化学;1987年05期

6 黄恩祝;;索引系统结构的三个重要规律[J];图书馆学通讯;1988年01期

7 阳国贵;;一种支持多维空间数据管理的Quad-tree索引结构[J];计算机工程与科学;1989年03期

8 长孙妮妮;张毅坤;华灯鑫;邹子夏;陈浩;;一种基于B+树的混合索引结构[J];计算机工程;2012年14期

9 龙柏;孙广中;熊焰;陈国良;;一种基于多核机群架构的混合索引结构[J];电子学报;2011年02期

10 南国芳;黄才炎;杨挺;;基于混合索引结构的传感器网络查询系统仿真[J];系统仿真学报;2011年01期

相关博士学位论文 前10条

1 张晓祎;基于非易失内存的高效索引方法及应用研究[D];华中科技大学;2019年

2 张泽宝;空间数据库的索引技术研究[D];哈尔滨工程大学;2009年

3 王兴中;铁路调度指挥系统中数据存储体系及索引结构的研究[D];中国铁道科学研究院;2011年

4 赵伶俐;面向城镇化数据整合的数据索引方法研究[D];中南大学;2010年

5 阳国贵;对象关系数据库中若干关键技术的研究[D];中国人民解放军国防科学技术大学;2000年

6 周敏奇;基于格雷码的结构化对等计算系统及其数据管理[D];复旦大学;2008年

7 陈志坤;分布式环境下大数据组织与管理关键技术的研究[D];国防科学技术大学;2014年

8 张圣栋;虚拟计算环境中高效发布订阅系统研究[D];国防科学技术大学;2011年

9 张蓉;结构化对等计算机系统中的查询处理[D];复旦大学;2007年

10 黎志升;地理信息检索若干技术研究[D];中国科学技术大学;2009年

相关硕士学位论文 前10条

1 王章龙;Elasticsearch索引分片策略研究[D];重庆邮电大学;2019年

2 关凯胜;kNN查询中面向索引结构的聚类算法研究[D];广东工业大学;2019年

3 向文坤;面向推荐系统的可学习哈希索引模型研究[D];云南大学;2018年

4 易新;基于用户偏好约束的位置感知排序查询研究[D];重庆邮电大学;2019年

5 刘建坤;OBF-Index：基于Ordinal Bloom Filter的分布式多维索引[D];云南大学;2017年

6 杨旭敏;基于网格的移动对象轨迹混合索引结构[D];燕山大学;2018年

7 赵芳华;基于时态的通用位置感知排序查询研究[D];燕山大学;2018年

8 曹鸿源;重删环境下双B-树索引性能优化研究[D];中南民族大学;2018年

9 张娟;基于GPU的Hash索引结构的设计与实现[D];浙江大学;2018年

10 许伟;服务库多级索引模型性能分析[D];江苏大学;2017年

本文编号：2858588