NVM+DRAM混合内存架构下的连接算法优化
发布时间：2021-06-24 17:14
非易失性内存（Non-Volatile Memory,NVM）具有按字节存取、非易失、存储密度高、能耗低等优点,因此被认为是替代DRAM的下一代内存技术.虽然目前NVM的存取速度远高于闪存,但还低于DRAM,并且还存在着读写不均衡等问题.因此,综合内存性能、存储密度、非易失性等因素,构建基于NVM和DRAM的混合内存系统是未来若干年内的可行方案.本论文以NVM+DRAM混合内存架构为基础,研究了混合内存架构下传统数据库磁盘连接算法的优化方法.由于传统的连接算法在混合内存架构和纯DRAM架构下的I/O代价相同,因此我们的主要目标是优化内存代价.在传统的磁盘连接算法中,中间过程产生的数据结构的读写次数存在着较大差别.如果将连接过程的中间数据结构以合适的策略存放在混合内存中,则有望降低连接算法的内存代价.基于这一思路,论文首先给出了一个形式化的数据结构（映像）部署模型,分析了连接算法内存代价的上下界及其成立条件并给出了证明,进而给出了基于最优部署模型的连接算法优化设计.最后,论文实现了4种连接算法,包括嵌套循环连接、排序连接、散列连接等3种经典连接算法以及面向内存数据库的虚拟分区连接算法,并...
【文章来源】：计算机学报. 2020,43(06)北大核心EICSCD
【文章页数】：17 页
【部分图文】：
不同混合内存大小下NVM写次数对比
从图6我们可以看出，在不同DRAM占比下，最优部署方案仍然给出了三种方案中最少的NVM写总数．当DRAM占比从0.1变化到0.4时，最差部署方案的NVM总写次数基本不发生变化，但SMJ算法的NVM总写次数随着DRAM比例提高而显著减少．此外，随机部署方案和最优部署方案的总NVM写次数在四种算法下都得到了显著的削减，其中BNJ算法效果最为明显，HHJ算法的增益效果最差．当DRAM比例为0.1时，最优方案能减少最差方案下算法BNJ/HHJ/SMJ/VRTPJ 21%/89%/23%/88%的NVM写总数；当DRAM比例达到0.4时，最优方案下能减少最差方案下算法BNJ/HHJ/SMJ/VRTPJ 89%/94%/44%/98%的NVM写总数．5.3.4 NVM写延迟对性能的影响
如何在内存架构中合理地使用NVM是构建支持NVM的计算机系统需要首先考虑的问题．目前国内外提出的基于NVM的主存系统大致分为三种方案[8-10]．第一种用NVM完全替代DRAM[8]，如图1(a）所示，但是由于NVM读写性能还达不到DRAM的水平，短期内这种架构难以成为主流．第二种是层次型架构[9]，如图1(b）所示．这种架构需要把DRAM作为NVM的缓存，而NVM则作为DRAM的第二级内存，例如Intel傲腾持久化内存的Memory Mode*即为这一架构．这一架构存在两个方面的问题．首先，由于DRAM只是作为NVM的缓存，因此系统可见的内存仅为NVM的空间．假设系统配置了128GB的DRAM和512GB的NVM，实际系统能用的内存只有NVM的512GB空间，因此在内存空间使用上不合算．其次，这一架构只是利用了NVM比DRAM容量大的优点，操作系统的数据访问依然还是通过DRAM，没有充分利用NVM的非易失性特点．第三种架构是平行的混合架构，即NVM和DRAM同时作为同一层次的主存使用[10]，如图1(c）所示．目前Intel的傲腾持久性内存所支持的App-DirectMode*即为这一架构．在这种架构下，系统可用的内存空间等于DRAM和NVM的容量之和，而且操作系统感知两类内存的特性（NVM非易失和DRAM掉电易失），可以充分利用DRAM和NVM各自的优点．这一架构主要的实现难点是需要操作系统和DBMS等在软件层面做相应的适配．本论文的工作主要针对图1(c）所示的平行混合内存架构，另两种架构也有值得研究的价值，我们将在未来工作中进一步探索．数据库连接算法是数据库物理查询的必要组件，其时间性能对数据库系统，特别是OLAP系统至关重要，因此近年来持续涌现出诸多针对新型内存技术NVM优化数据库连接算法的工作[6,11-12]．因为NVM写延迟显著高于读延迟，针对NVM的连接算法优化无非都是以额外的读操作换取更少的写操作，这种思路在纯NVM内存系统下能够显著提升连接时间性能，但是在混合DRAM和NVM内存架构下，这种思路无法充分利用DRAM和NVM的特性．由于DRAM读写时延较低，我们考虑对不同读写密集程度的数据对象进行适应性部署．考虑到连接算法的不同中间关系存在不同的读写频度，如果能找到一种最优的中间数据结构在不同介质上的部署方法，则有望达到混合内存架构下的连接算法代价的下界．本文的主要目的是优化数据库连接查询算法在混合内存架构上的内存读写代价．磁盘连接算法的代价包括磁盘I/O代价，内存代价和CPU代价．对于特定的连接算法，无论运行在混合内存架构上还是传统DRAM的架构上，I/O代价都是恒定的．与此同时，由于高密度的NVM的引入，混合内存的大小预计会大大超过现有的DRAM大小．在这种情况下，内存代价将成为影响连接算法性能的主导因素[13]．基于此，本论文将着重优化连接算法在混合内存架构上的内存代价．由于NVM和DRAM的读写延迟不同，而且NVM存在读写延迟不对称性，理论上通过设计合适的内存分配策略，将算法中具有不同读写比例的数据结构分配到这两种内存设备上，可以有效减少算法的总内存读写代价．本论文的后续实验也证明了这一点．
【参考文献】：
期刊论文
[1]面向非易失性存储器的多表连接写操作的优化研究[J]. 马竹琳,李心池,诸葛晴凤,吴林,陈咸彰,姜炜文,沙行勉. 计算机学报. 2019(11)
[2]一个基于日志结构的非易失性内存键值存储系统[J]. 游理通,王振杰,黄林鹏. 计算机研究与发展. 2018(09)
[3]基于非易失性存储器的存储系统技术研究进展[J]. 舒继武,陆游游,张佳程,郑纬民. 科技导报. 2016(14)
本文编号：3247507
【文章来源】：计算机学报. 2020,43(06)北大核心EICSCD
【文章页数】：17 页
【部分图文】：
不同混合内存大小下NVM写次数对比
从图6我们可以看出，在不同DRAM占比下，最优部署方案仍然给出了三种方案中最少的NVM写总数．当DRAM占比从0.1变化到0.4时，最差部署方案的NVM总写次数基本不发生变化，但SMJ算法的NVM总写次数随着DRAM比例提高而显著减少．此外，随机部署方案和最优部署方案的总NVM写次数在四种算法下都得到了显著的削减，其中BNJ算法效果最为明显，HHJ算法的增益效果最差．当DRAM比例为0.1时，最优方案能减少最差方案下算法BNJ/HHJ/SMJ/VRTPJ 21%/89%/23%/88%的NVM写总数；当DRAM比例达到0.4时，最优方案下能减少最差方案下算法BNJ/HHJ/SMJ/VRTPJ 89%/94%/44%/98%的NVM写总数．5.3.4 NVM写延迟对性能的影响
如何在内存架构中合理地使用NVM是构建支持NVM的计算机系统需要首先考虑的问题．目前国内外提出的基于NVM的主存系统大致分为三种方案[8-10]．第一种用NVM完全替代DRAM[8]，如图1(a）所示，但是由于NVM读写性能还达不到DRAM的水平，短期内这种架构难以成为主流．第二种是层次型架构[9]，如图1(b）所示．这种架构需要把DRAM作为NVM的缓存，而NVM则作为DRAM的第二级内存，例如Intel傲腾持久化内存的Memory Mode*即为这一架构．这一架构存在两个方面的问题．首先，由于DRAM只是作为NVM的缓存，因此系统可见的内存仅为NVM的空间．假设系统配置了128GB的DRAM和512GB的NVM，实际系统能用的内存只有NVM的512GB空间，因此在内存空间使用上不合算．其次，这一架构只是利用了NVM比DRAM容量大的优点，操作系统的数据访问依然还是通过DRAM，没有充分利用NVM的非易失性特点．第三种架构是平行的混合架构，即NVM和DRAM同时作为同一层次的主存使用[10]，如图1(c）所示．目前Intel的傲腾持久性内存所支持的App-DirectMode*即为这一架构．在这种架构下，系统可用的内存空间等于DRAM和NVM的容量之和，而且操作系统感知两类内存的特性（NVM非易失和DRAM掉电易失），可以充分利用DRAM和NVM各自的优点．这一架构主要的实现难点是需要操作系统和DBMS等在软件层面做相应的适配．本论文的工作主要针对图1(c）所示的平行混合内存架构，另两种架构也有值得研究的价值，我们将在未来工作中进一步探索．数据库连接算法是数据库物理查询的必要组件，其时间性能对数据库系统，特别是OLAP系统至关重要，因此近年来持续涌现出诸多针对新型内存技术NVM优化数据库连接算法的工作[6,11-12]．因为NVM写延迟显著高于读延迟，针对NVM的连接算法优化无非都是以额外的读操作换取更少的写操作，这种思路在纯NVM内存系统下能够显著提升连接时间性能，但是在混合DRAM和NVM内存架构下，这种思路无法充分利用DRAM和NVM的特性．由于DRAM读写时延较低，我们考虑对不同读写密集程度的数据对象进行适应性部署．考虑到连接算法的不同中间关系存在不同的读写频度，如果能找到一种最优的中间数据结构在不同介质上的部署方法，则有望达到混合内存架构下的连接算法代价的下界．本文的主要目的是优化数据库连接查询算法在混合内存架构上的内存读写代价．磁盘连接算法的代价包括磁盘I/O代价，内存代价和CPU代价．对于特定的连接算法，无论运行在混合内存架构上还是传统DRAM的架构上，I/O代价都是恒定的．与此同时，由于高密度的NVM的引入，混合内存的大小预计会大大超过现有的DRAM大小．在这种情况下，内存代价将成为影响连接算法性能的主导因素[13]．基于此，本论文将着重优化连接算法在混合内存架构上的内存代价．由于NVM和DRAM的读写延迟不同，而且NVM存在读写延迟不对称性，理论上通过设计合适的内存分配策略，将算法中具有不同读写比例的数据结构分配到这两种内存设备上，可以有效减少算法的总内存读写代价．本论文的后续实验也证明了这一点．
【参考文献】：
期刊论文
[1]面向非易失性存储器的多表连接写操作的优化研究[J]. 马竹琳,李心池,诸葛晴凤,吴林,陈咸彰,姜炜文,沙行勉. 计算机学报. 2019(11)
[2]一个基于日志结构的非易失性内存键值存储系统[J]. 游理通,王振杰,黄林鹏. 计算机研究与发展. 2018(09)
[3]基于非易失性存储器的存储系统技术研究进展[J]. 舒继武,陆游游,张佳程,郑纬民. 科技导报. 2016(14)
本文编号：3247507
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/3247507.html
