非易失性內(nèi)存（Non-Volatile Memory,NVM）具有按字節(jié)存取、非易失、存儲密度高、能耗低等優(yōu)點(diǎn),因此被認(rèn)為是替代DRAM的下一代內(nèi)存技術(shù).雖然目前NVM的存取速度遠(yuǎn)高于閃存,但還低于DRAM,并且還存在著讀寫不均衡等問題.因此,綜合內(nèi)存性能、存儲密度、非易失性等因素,構(gòu)建基于NVM和DRAM的混合內(nèi)存系統(tǒng)是未來若干年內(nèi)的可行方案.本論文以NVM+DRAM混合內(nèi)存架構(gòu)為基礎(chǔ),研究了混合內(nèi)存架構(gòu)下傳統(tǒng)數(shù)據(jù)庫磁盤連接算法的優(yōu)化方法.由于傳統(tǒng)的連接算法在混合內(nèi)存架構(gòu)和純DRAM架構(gòu)下的I/O代價相同,因此我們的主要目標(biāo)是優(yōu)化內(nèi)存代價.在傳統(tǒng)的磁盤連接算法中,中間過程產(chǎn)生的數(shù)據(jù)結(jié)構(gòu)的讀寫次數(shù)存在著較大差別.如果將連接過程的中間數(shù)據(jù)結(jié)構(gòu)以合適的策略存放在混合內(nèi)存中,則有望降低連接算法的內(nèi)存代價.基于這一思路,論文首先給出了一個形式化的數(shù)據(jù)結(jié)構(gòu)（映像）部署模型,分析了連接算法內(nèi)存代價的上下界及其成立條件并給出了證明,進(jìn)而給出了基于最優(yōu)部署模型的連接算法優(yōu)化設(shè)計.最后,論文實(shí)現(xiàn)了4種連接算法,包括嵌套循環(huán)連接、排序連接、散列連接等3種經(jīng)典連接算法以及面向內(nèi)存數(shù)據(jù)庫的虛擬分區(qū)連接算法,并... 

【文章來源】：計算機(jī)學(xué)報. 2020,43(06)北大核心EICSCD

【文章頁數(shù)】：17 頁

【部分圖文】：

不同混合內(nèi)存大小下NVM寫次數(shù)對比

從圖6我們可以看出，在不同DRAM占比下，最優(yōu)部署方案仍然給出了三種方案中最少的NVM寫總數(shù)．當(dāng)DRAM占比從0.1變化到0.4時，最差部署方案的NVM總寫次數(shù)基本不發(fā)生變化，但SMJ算法的NVM總寫次數(shù)隨著DRAM比例提高而顯著減少．此外，隨機(jī)部署方案和最優(yōu)部署方案的總NVM寫次數(shù)在四種算法下都得到了顯著的削減，其中BNJ算法效果最為明顯，HHJ算法的增益效果最差．當(dāng)DRAM比例為0.1時，最優(yōu)方案能減少最差方案下算法BNJ/HHJ/SMJ/VRTPJ 21%/89%/23%/88%的NVM寫總數(shù)；當(dāng)DRAM比例達(dá)到0.4時，最優(yōu)方案下能減少最差方案下算法BNJ/HHJ/SMJ/VRTPJ 89%/94%/44%/98%的NVM寫總數(shù)．5.3.4 NVM寫延遲對性能的影響

如何在內(nèi)存架構(gòu)中合理地使用NVM是構(gòu)建支持NVM的計算機(jī)系統(tǒng)需要首先考慮的問題．目前國內(nèi)外提出的基于NVM的主存系統(tǒng)大致分為三種方案[8-10]．第一種用NVM完全替代DRAM[8]，如圖1(a）所示，但是由于NVM讀寫性能還達(dá)不到DRAM的水平，短期內(nèi)這種架構(gòu)難以成為主流．第二種是層次型架構(gòu)[9]，如圖1(b）所示．這種架構(gòu)需要把DRAM作為NVM的緩存，而NVM則作為DRAM的第二級內(nèi)存，例如Intel傲騰持久化內(nèi)存的Memory Mode*即為這一架構(gòu)．這一架構(gòu)存在兩個方面的問題．首先，由于DRAM只是作為NVM的緩存，因此系統(tǒng)可見的內(nèi)存僅為NVM的空間．假設(shè)系統(tǒng)配置了128GB的DRAM和512GB的NVM，實(shí)際系統(tǒng)能用的內(nèi)存只有NVM的512GB空間，因此在內(nèi)存空間使用上不合算．其次，這一架構(gòu)只是利用了NVM比DRAM容量大的優(yōu)點(diǎn)，操作系統(tǒng)的數(shù)據(jù)訪問依然還是通過DRAM，沒有充分利用NVM的非易失性特點(diǎn)．第三種架構(gòu)是平行的混合架構(gòu)，即NVM和DRAM同時作為同一層次的主存使用[10]，如圖1(c）所示．目前Intel的傲騰持久性內(nèi)存所支持的App-DirectMode*即為這一架構(gòu)．在這種架構(gòu)下，系統(tǒng)可用的內(nèi)存空間等于DRAM和NVM的容量之和，而且操作系統(tǒng)感知兩類內(nèi)存的特性（NVM非易失和DRAM掉電易失），可以充分利用DRAM和NVM各自的優(yōu)點(diǎn)．這一架構(gòu)主要的實(shí)現(xiàn)難點(diǎn)是需要操作系統(tǒng)和DBMS等在軟件層面做相應(yīng)的適配．本論文的工作主要針對圖1(c）所示的平行混合內(nèi)存架構(gòu)，另兩種架構(gòu)也有值得研究的價值，我們將在未來工作中進(jìn)一步探索．?dāng)?shù)據(jù)庫連接算法是數(shù)據(jù)庫物理查詢的必要組件，其時間性能對數(shù)據(jù)庫系統(tǒng)，特別是OLAP系統(tǒng)至關(guān)重要，因此近年來持續(xù)涌現(xiàn)出諸多針對新型內(nèi)存技術(shù)NVM優(yōu)化數(shù)據(jù)庫連接算法的工作[6,11-12]．因?yàn)镹VM寫延遲顯著高于讀延遲，針對NVM的連接算法優(yōu)化無非都是以額外的讀操作換取更少的寫操作，這種思路在純NVM內(nèi)存系統(tǒng)下能夠顯著提升連接時間性能，但是在混合DRAM和NVM內(nèi)存架構(gòu)下，這種思路無法充分利用DRAM和NVM的特性．由于DRAM讀寫時延較低，我們考慮對不同讀寫密集程度的數(shù)據(jù)對象進(jìn)行適應(yīng)性部署．考慮到連接算法的不同中間關(guān)系存在不同的讀寫頻度，如果能找到一種最優(yōu)的中間數(shù)據(jù)結(jié)構(gòu)在不同介質(zhì)上的部署方法，則有望達(dá)到混合內(nèi)存架構(gòu)下的連接算法代價的下界．本文的主要目的是優(yōu)化數(shù)據(jù)庫連接查詢算法在混合內(nèi)存架構(gòu)上的內(nèi)存讀寫代價．磁盤連接算法的代價包括磁盤I/O代價，內(nèi)存代價和CPU代價．對于特定的連接算法，無論運(yùn)行在混合內(nèi)存架構(gòu)上還是傳統(tǒng)DRAM的架構(gòu)上，I/O代價都是恒定的．與此同時，由于高密度的NVM的引入，混合內(nèi)存的大小預(yù)計會大大超過現(xiàn)有的DRAM大�。谶@種情況下，內(nèi)存代價將成為影響連接算法性能的主導(dǎo)因素[13]．基于此，本論文將著重優(yōu)化連接算法在混合內(nèi)存架構(gòu)上的內(nèi)存代價．由于NVM和DRAM的讀寫延遲不同，而且NVM存在讀寫延遲不對稱性，理論上通過設(shè)計合適的內(nèi)存分配策略，將算法中具有不同讀寫比例的數(shù)據(jù)結(jié)構(gòu)分配到這兩種內(nèi)存設(shè)備上，可以有效減少算法的總內(nèi)存讀寫代價．本論文的后續(xù)實(shí)驗(yàn)也證明了這一點(diǎn)．

【參考文獻(xiàn)】：
期刊論文
[1]面向非易失性存儲器的多表連接寫操作的優(yōu)化研究[J]. 馬竹琳,李心池,諸葛晴鳳,吳林,陳咸彰,姜煒文,沙行勉.  計算機(jī)學(xué)報. 2019(11)
[2]一個基于日志結(jié)構(gòu)的非易失性內(nèi)存鍵值存儲系統(tǒng)[J]. 游理通,王振杰,黃林鵬.  計算機(jī)研究與發(fā)展. 2018(09)
[3]基于非易失性存儲器的存儲系統(tǒng)技術(shù)研究進(jìn)展[J]. 舒繼武,陸游游,張佳程,鄭緯民.  科技導(dǎo)報. 2016(14)



本文編號：3247507