基于闪存的索引机制研究

发布时间：2017-12-25 14:15

本文关键词：基于闪存的索引机制研究　出处：《中国科学技术大学》2017年博士论文　论文类型：学位论文

【摘要】：随着闪存存储器制作工艺的不断发展,闪存的存储密度大幅提高,基于闪存芯片阵列的固态硬盘(Solid State Drive,SSD)应运而生并迅速普及于工业界的存储系统和桌面PC。由于和传统磁盘有相同的物理和逻辑接口,SSD被视为存储系统革新的关键技术,学术界和工业界都对SSD完全取代磁盘持乐观态度。然而,SSD具有不同于磁盘的独特特性,如闪存的写前擦除机制,读写不均衡,擦除次数有限等,使得原有在磁盘上的数据管理算法不能充分发挥SSD的性能。因此,针对SSD特性研究设计适合于SSD上的数据管理新方法非常重要。索引对数据检索至关重要,使用索引可快速访问海量数据中的特定信息。传统的索引机制是面向I/O对称的磁盘设计,索引的更新造成大量随机写操作。由于闪存的随机写性能较差,如果将传统的索引机制直接应用在闪存上,并不能获得理想的性能提升。因此,近年来基于闪存的索引机制研究引起了学术界的重视。目前基于闪存的索引机制研究按索引结构大致可分为三类:(1)基于闪存的哈希索引机制研究;(2)基于闪存的树型索引机制研究;(3)基于闪存的位图索引机制研究。已有研究都是以减少对闪存的随机写为目标,主要用到以读换写、批量更新、异位更新、及转化随机写为连续写等技术手段。本论文分析了已有研究关键技术的不足:(1)虽然减少了对SSD的随机写操作,但是造成了大量的额外读操作,考虑到目前SSD内部控制技术的成熟,读写差异相较之前大幅缩小,大量额外读操作反而降低了总体性能;(2)在更新密集的数据集下表现出良好性能,但是在查询密集数据集下性能与原索引差距明显;(3)基本未考虑利用SSD内部并行机制来进一步提升性能。因此,需要针对先进的读写差异接近的SSD,研究适应于更普适应用数据集的索引机制。本文聚焦于哈希索引和B+-树,提出了随着访问模式动态调整的线性哈希,并进一步对该索引进行查询优化;本文还为读写优化的B+-树索引提供了理论基础。提高索引读写性能,离不开缓冲区,本论文讨论了树型索引访问特性和面向闪存的缓冲区算法设计原则之间的矛盾。传统基于闪存的缓冲区算法给脏页面特殊优先级以减少随机写,在这类算法应用场景中,树型索引内部结点比叶子结点更易被替换出缓冲区,因为内部结点比叶子结点有更高的干净概率。另一方面,内部结点比叶子结点访问频率高很多,替换出这些结点会降低命中率。论文提出了综合页面访问概率、访问临近信息以及页面是否为脏来选择替换页面的算法,成功解决了上述问题。本论文的贡献点如下:(1)提出了随着访问模式动态调整的自适应线性哈希索引(Self-Adaptive Linear Hashing,SAL-hashing)。该索引使用了批量更新的技术,同时引入了组(group)和集合(set)的概念来提升批量更新的效率。对索引的更新先缓存在内存,然后以set为粒度向索引批量刷新更新操作到set对应的日志区。此外,该索引根据各set的访问倾向性实时决定是否将日志区与对应的set合并。对于读倾向的set,及时将日志区合并到set对应的bucket中,后续的查询可以避免额外的读日志区;对于写倾向的set,保留其日志区以保持批量更新效率。此外,在合并日志区到对应bucket时,通过粗粒度写操作来利用SSD内部并行特性,从而提升写带宽。(2)分析了线性哈希的溢出链与分裂点的关系,并在SAL-hashing的基础上提出了一个高内存效率的数据结构,使几乎每一个bucket上的查询只需要一次读操作,查询效率与可扩展哈希相当。此外,还讨论了 SAL-hashing对事务支持和故障恢复的能力。(3)提出了一种适应于树型索引的缓冲区算法,结合结点被访问概率和访问临近信息权衡页面冷热,并根据页面是否是脏页面选择替换页。此外,该算法将脏页面打包,采用粗粒度写来批量刷新冷脏页面,避免细粒度随机写操作。(4)针对本实验室提出的读写优化的B+-树索引,完善了理论分析,讨论了索引的并发访问,并重新设计了实验,同时给出详细的结果分析。
【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TP333

【相似文献】