NVM+DRAM混合内存架构下的连接算法优化

Optimizing Join Algorithms for NVM+DRAM-Based Hybrid Memory Architecture

非易失性内存(Non-Volatile Memory,NVM)具有按字节存取、非易失、存储密度高、能耗低等优点,因此被认为是替代DRAM的下一代内存技术.虽然目前NVM的存取速度远高于闪存,但还低于DRAM,并且还存在着读写不均衡等问题.因此,综合内存性能、存储密度、非易失性等因素,构建基于NVM和DRAM的混合内存系统是未来若干年内的可行方案.本论文以NVM+DRAM混合内存架构为基础,研究了混合内存架构下传统数据库磁盘连接算法的优化方法.由于传统的连接算法在混合内存架构和纯DRAM架构下的I/O代价相同,因此我们的主要目标是优化内存代价.在传统的磁盘连接算法中,中间过程产生的数据结构的读写次数存在着较大差别.如果将连接过程的中间数据结构以合适的策略存放在混合内存中,则有望降低连接算法的内存代价.基于这一思路,论文首先给出了一个形式化的数据结构(映像)部署模型,分析了连接算法内存代价的上下界及其成立条件并给出了证明,进而给出了基于最优部署模型的连接算法优化设计.最后,论文实现了4种连接算法,包括嵌套循环连接、排序连接、散列连接等3种经典连接算法以及面向内存数据库的虚拟分区连接算法,并对比了最优映像部署模型、最差映像部署模型和随机映像部署模型下各个连接算法的性能.实验结果证明,最优映像部署模型能显著提升4种连接算法在混合内存架构下的时间性能,并显著减少了NVM写总数.

Non-Volatile Memory(NVM)has been regarded as the main alternative of next main memory technologies to replace DRAM,due to its advantages of byte addressability,non-volatility,high density,and low power consumption.Although NVM is currently faster than flash memory,it has higher access latency than DRAM.In addition,the read/write latency of NVM is unbalanced.Therefore,considering all factors involving memory performance,storage density,and non-volatility,it is a feasible solution to construct a hybrid memory system based on NVM and DRAM.Based on such hybrid memory architecture,this paper investigates the optimization of join algorithms on the hybrid memory.As a specific join algorithm has the same I/O cost when running on the hybrid memory and the DRAM-only architecture,we focus on the reduction of memory cost.We noticed that the intermediate data structures of a join algorithm have different read/write operations.Thus,we can reduce memory cost of join algorithms on the hybrid memory by designing an appropriate way to place intermediate data structures on NVM or DRAM.Following this idea,we propose a formal Data Structure Placement Model(DSPM)to address this problem.We analyze the upper bound and lower bound of the memory cost and corresponding conditions,and present proofs.Then,we propose optimizations of join algorithms based on the optimal DSPM model.Finally,we implement four join algorithms including three traditional join algorithms(nested loops join,sort join,and hash join)and the virtual partition join for in-memory databases.We conduct comparative experiments to verify performance of the optimal DSPM model,the worst DSPM model,and the ransom DSPM model on the four join algorithms.The experimental results show that the optimal DSPM model can significantly improve the time performance and reduce NVM writes when integrated with the four join algorithms on the hybrid memory architecture.