持久内存自适应基数树索引读写优化研究.pdf

华中科技大学硕士学位论文

摘要

新型持久内存（PersistentMemory，PM）因兼具内存的高性能字节访问模式与外

存的非易失性，为键值存储系统设计带来了新的机遇和挑战。键值存储系统的性能很

大程度上取决于所采用的索引结构，树索引因具备范围查询能力而被广泛应用。自适

应基数树基于普通内存设计，相比其他树索引具有更高的单点查询性能，但随着数据

规模变大，树的层级变高，有哪些信誉好的足球投注网站路径会变长，造成性能下降，在相对较慢的持久内存

上表现尤为明显。此外，树索引在并发场景下，结构发生变化时，大量持久内存读写

亦会阻塞正常访问，造成性能下降。

结合持久内存的读写特性，提出了基于持久内存的自适应基数树性能优化方法。

针对数据规模较大时自适应基数树索引压缩策略失效造成查询有哪些信誉好的足球投注网站路径长的问题，

结合常见负载的数据特征，提出分级压缩的方法降低树的高度，通过对不同层级结点

使用不同的压缩方式，缩短有哪些信誉好的足球投注网站路径，提高有哪些信誉好的足球投注网站性能，引入微型布隆过滤器进一步加

快负面有哪些信誉好的足球投注网站速度。针对持久内存索引结构化操作访问延迟较高的问题，提出选择持久

化及惰性预分裂机制，减少对持久内存的写入和读取次数，加速写入操作，降低并发

场景下的访问延迟。针对当前开源PMDK持久内存分配开销较大的问题，设计并实

现了支持变长空间分配的高效持久内存分配器，通过单次分配大块持久内存，减少申

请持久内存次数，降低并发场景下持久内存分配竞争开销。

基于上述优化方法实现了一个读写优化的持久内存自适应基数树索引原型

RWOART（ReadWriteOptimizedAdaptiveRadixTree）。实验结果表明，与其他支持

范围查询的持久内存索引结构相比，在多线程下读取性能提升了20%～491%，写入

性能提升了15%～400%，范围查询性能提升了25%～246%。

关键词：持久内存；键值存储；索引；自适应基数树；读写优化

I

华中科技大学硕士学位论文

Abstract

TheemergingPersistentMemory(PM)presentsnewopportunitiesandchallengesfor

thedesignofkey-valuestoragesystems,asitcombinesthehigh-performancebyte-level

accessmodeofmemorywiththenon-volatilityofexternalstorage.Theperformanceofkey-

valuestoragesystemslargelydependsontheadoptedindexstructure,andtreeindexesare

widelyusedduetotheirrangequerycapabilities.TheAdaptiveRadixTree(ART),whichis

designedbasedonordinarymemory,outperformsothertreeindexesintermsofsingle-point

queryperformance.However,asdatascalesup,theheightofthetreeincreases,andthe

searchpathbecomeslonger,resultinginperformancedegradation,whichisparticularly

evidentonrelativelyslowPersistentMemory.Inaddition,inconcurrentscenarios,whenthe

treestructurechanges,alargeamountofpersistentmemoryreadandwriteoperationscan

blocknormalaccess,leadingtoper