在大數(shù)據(jù)背景下,計(jì)算機(jī)系統(tǒng)對(duì)內(nèi)存容量的需求越來(lái)越大。傳統(tǒng)基于動(dòng)態(tài)隨機(jī)存取存儲(chǔ)器(Dynamic Random Access Memory,DRAM)的內(nèi)存系統(tǒng)在制造工藝和能耗上正面臨著巨大的挑戰(zhàn),難以滿(mǎn)足大數(shù)據(jù)時(shí)代的需求。隨著材料和存儲(chǔ)技術(shù)的迅速發(fā)展,以相變存儲(chǔ)器(Phase Change Memory,PCM)和阻變存儲(chǔ)器(Resistive Random Access Memory,RRAM)為代表的新型非易失內(nèi)存(Non-Volatile Memory,NVM)開(kāi)始出現(xiàn)。NVM具有掉電非易失、按字節(jié)修改尋址、快速訪(fǎng)存、高存儲(chǔ)密度、低靜態(tài)功耗等優(yōu)點(diǎn),這些優(yōu)良特性讓NVM可以和DRAM一起組成混合內(nèi)存系統(tǒng),甚至在未來(lái)完全取代DRAM成為內(nèi)存系統(tǒng)的主要存儲(chǔ)介質(zhì)。當(dāng)NVM作為計(jì)算機(jī)內(nèi)存的時(shí)候,高效的索引結(jié)構(gòu)對(duì)于提升數(shù)據(jù)查詢(xún)和空間管理的效率非常重要。然而,傳統(tǒng)基于DRAM的索引結(jié)構(gòu)并不能高效應(yīng)用于新型NVM設(shè)備,因?yàn)樗鼈兗葲](méi)有考慮NVM寫(xiě)性能較差和耐久性較低等缺陷,也無(wú)法保證系統(tǒng)意外斷電情況下的數(shù)據(jù)一致性。本文探討了基于NVM的索引結(jié)構(gòu)面臨的數(shù)據(jù)一致性、較差的寫(xiě)性能和較低的耐久性等問(wèn)題,從單點(diǎn)查詢(xún)和范圍查詢(xún)兩個(gè)方面提出了解決方案,并從文件系統(tǒng)的角度給出了一種NVM索引結(jié)構(gòu)的應(yīng)用場(chǎng)景。本文的主要研究?jī)?nèi)容和創(chuàng)新點(diǎn)如下。針對(duì)傳統(tǒng)哈希索引結(jié)構(gòu)沒(méi)有考慮到NVM存在的缺陷和數(shù)據(jù)一致性的問(wèn)題,提出了一種基于NVM的高性能哈希索引結(jié)構(gòu)Group hashing,減少了數(shù)據(jù)一致性帶來(lái)的開(kāi)銷(xiāo),降低了CPU Cache的失效率,提升了哈希索引的查找、插入和刪除性能。Group hashing利用8字節(jié)原子寫(xiě)技術(shù)保證數(shù)據(jù)一致性,這樣可以避免日志或者寫(xiě)時(shí)復(fù)制技術(shù)的使用,減少對(duì)于NVM的寫(xiě)操作以及一致性帶來(lái)的額外開(kāi)銷(xiāo)。Group hashing提出了一種名為組內(nèi)共享的技術(shù),將哈希索引空間劃分為多個(gè)地址連續(xù)的分組,把同一個(gè)分組內(nèi)的哈希沖突單元存放到相匹配的分組里,在高效解決哈希沖突的同時(shí)降低了CPU Cache的失效率。此外,Group hashing還包含了一種組內(nèi)再哈希的方法,降低了哈希沖突時(shí)在分組內(nèi)搜索目標(biāo)哈希單元帶來(lái)的延遲,從而進(jìn)一步提升哈希索引的查找性能。實(shí)驗(yàn)結(jié)果表明,Group hashing在三種真實(shí)負(fù)載下的查找、插入和刪除性能和CPU Cache效率都要優(yōu)于現(xiàn)有基于NVM的哈希索引結(jié)構(gòu)。針對(duì)現(xiàn)有基于NVM的單一索引結(jié)構(gòu)無(wú)法同時(shí)高效支持單點(diǎn)查詢(xún)和范圍查詢(xún)這一問(wèn)題,提出了一種基于NVM與DRAM結(jié)合的高性能混合索引方法HSHI,充分發(fā)揮了不同索引結(jié)構(gòu)的優(yōu)點(diǎn),高效支持了范圍查詢(xún),提升了混合索引的查找、插入和刪除性能。HSHI使用哈希索引和跳躍表(Skiplist)組成混合索引:哈希索引作為主要索引位于NVM,用來(lái)處理查找、插入、刪除等基本操作;跳躍表作為輔助索引位于DRAM,用來(lái)處理范圍查詢(xún)操作。HSHI對(duì)DRAM上的跳躍表采用異步更新機(jī)制,這樣可以降低混合索引的寫(xiě)延遲。為了減少混合索引的一致性開(kāi)銷(xiāo),HSHI利用8字節(jié)原子寫(xiě)保證數(shù)據(jù)一致性。此外,HSHI還使用了一種細(xì)粒度的鎖機(jī)制來(lái)支持混合索引的并發(fā)訪(fǎng)問(wèn)。實(shí)驗(yàn)結(jié)果表明,HSHI能高效支持范圍查詢(xún),而且在單線(xiàn)程和多線(xiàn)程負(fù)載下的查找、插入和刪除操作性能都要優(yōu)于現(xiàn)有支持范圍查詢(xún)的NVM索引結(jié)構(gòu)。文件系統(tǒng)是索引結(jié)構(gòu)應(yīng)用的一個(gè)重要領(lǐng)域。針對(duì)傳統(tǒng)文件系統(tǒng)日志技術(shù)無(wú)法高效應(yīng)用于新型NVM設(shè)備的問(wèn)題,提出了一種基于NVM的文件系統(tǒng)日志技術(shù)NJS,減少了文件系統(tǒng)的日志開(kāi)銷(xiāo),提升了文件系統(tǒng)的寫(xiě)性能。為了減少對(duì)于NVM的寫(xiě)入數(shù)據(jù)量,NJS只將覆蓋寫(xiě)數(shù)據(jù)和文件系統(tǒng)元數(shù)據(jù)寫(xiě)入到NVM,而追加寫(xiě)數(shù)據(jù)則直接寫(xiě)入文件系統(tǒng)。NJS提出了一種基于磨損感知的日志塊分配方法,在每次分配空閑NVM日志塊的時(shí)候,NJS都會(huì)選擇磨損次數(shù)最少的日志塊,從而提升NVM的使用壽命。NJS利用哈希索引管理NVM日志區(qū)域,并在此基礎(chǔ)上提出了一種字節(jié)粒度的日志塊更新策略,當(dāng)NVM中的日志塊需要更新的時(shí)候,NJS通過(guò)哈希索引尋找已有的舊版本日志塊,利用舊版本實(shí)現(xiàn)就地更新,這樣可以充分利用NVM按字節(jié)修改的特性。NJS還包含了一種垃圾回收機(jī)制用于回收無(wú)效日志塊,可以減少日志數(shù)據(jù)寫(xiě)回到文件系統(tǒng)的頻率,從而進(jìn)一步提升文件系統(tǒng)的性能。實(shí)驗(yàn)結(jié)果表明,與采用Ramdisk作為日志設(shè)備的Ext4相比,NJS在不同負(fù)載下的吞吐量平均提升了57.1%。
【學(xué)位單位】：華中科技大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位年份】：2019
【中圖分類(lèi)】：TP311.13;TP333
【文章目錄】：
摘要
Abstract
1 緒論
    1.1 NVM研究背景和面臨的挑戰(zhàn)
    1.2 相關(guān)研究現(xiàn)狀
    1.3 本文的主要研究?jī)?nèi)容和組織結(jié)構(gòu)
2 基于非易失內(nèi)存的高性能哈希索引結(jié)構(gòu)
    2.1 研究背景和研究動(dòng)機(jī)
    2.2 基于非易失內(nèi)存的哈希索引總體設(shè)計(jì)
    2.3 哈希索引的基本操作算法
    2.4 時(shí)間復(fù)雜度分析
    2.5 性能評(píng)估與結(jié)果分析
    2.6 本章小結(jié)
3 基于非易失內(nèi)存與DRAM結(jié)合的高性能混合索引方法
    3.1 研究背景和研究動(dòng)機(jī)
    3.2 混合索引的總體設(shè)計(jì)
    3.3 混合索引的數(shù)據(jù)一致性保障方法
    3.4 性能評(píng)估與結(jié)果分析
    3.5 本章小結(jié)
4 基于非易失內(nèi)存的文件系統(tǒng)日志技術(shù)
    4.1 研究背景和研究動(dòng)機(jī)
    4.2 基于非易失內(nèi)存的文件系統(tǒng)日志技術(shù)總體設(shè)計(jì)
    4.3 磨損感知的日志塊分配策略
    4.4 基于非易失內(nèi)存的文件系統(tǒng)日志技術(shù)的操作模塊
    4.5 實(shí)驗(yàn)測(cè)試與結(jié)果分析
    4.6 本章小結(jié)
5 全文總結(jié)與展望
    5.1 主要成果
    5.2 研究展望
致謝
參考文獻(xiàn)
附錄1 攻讀博士學(xué)位期間發(fā)表的學(xué)術(shù)論文目錄
附錄2 攻讀博士學(xué)位期間申請(qǐng)的發(fā)明專(zhuān)利和其他成果
附錄3 攻讀博士學(xué)位期間參與的科研項(xiàng)目

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 嚴(yán)趙峰;張為華;;面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進(jìn)展[J];大數(shù)據(jù);2019年04期

2 胡杰;何新華;呂慶星;;一種支持快速相似檢索的多維索引結(jié)構(gòu)[J];通訊世界;2016年07期

3 古毅;吳中福;魏麗;鐘將;馬金亮;;高維空間數(shù)據(jù)索引結(jié)構(gòu)分析研究[J];計(jì)算機(jī)科學(xué);2006年05期

4 馮玉才,曹奎,曹忠升;一種支持快速相似檢索的多維索引結(jié)構(gòu)[J];軟件學(xué)報(bào);2002年08期

5 侯臻燕;;〈化學(xué)亞結(jié)構(gòu)索引〉用法簡(jiǎn)介[J];大學(xué)化學(xué);1987年05期

6 黃恩祝;;索引系統(tǒng)結(jié)構(gòu)的三個(gè)重要規(guī)律[J];圖書(shū)館學(xué)通訊;1988年01期

7 陽(yáng)國(guó)貴;;一種支持多維空間數(shù)據(jù)管理的Quad-tree索引結(jié)構(gòu)[J];計(jì)算機(jī)工程與科學(xué);1989年03期

8 長(zhǎng)孫妮妮;張毅坤;華燈鑫;鄒子夏;陳浩;;一種基于B+樹(shù)的混合索引結(jié)構(gòu)[J];計(jì)算機(jī)工程;2012年14期

9 龍柏;孫廣中;熊焰;陳國(guó)良;;一種基于多核機(jī)群架構(gòu)的混合索引結(jié)構(gòu)[J];電子學(xué)報(bào);2011年02期

10 南國(guó)芳;黃才炎;楊挺;;基于混合索引結(jié)構(gòu)的傳感器網(wǎng)絡(luò)查詢(xún)系統(tǒng)仿真[J];系統(tǒng)仿真學(xué)報(bào);2011年01期

相關(guān)博士學(xué)位論文 前10條

1 張曉祎;基于非易失內(nèi)存的高效索引方法及應(yīng)用研究[D];華中科技大學(xué);2019年

2 張澤寶;空間數(shù)據(jù)庫(kù)的索引技術(shù)研究[D];哈爾濱工程大學(xué);2009年

3 王興中;鐵路調(diào)度指揮系統(tǒng)中數(shù)據(jù)存儲(chǔ)體系及索引結(jié)構(gòu)的研究[D];中國(guó)鐵道科學(xué)研究院;2011年

4 趙伶俐;面向城鎮(zhèn)化數(shù)據(jù)整合的數(shù)據(jù)索引方法研究[D];中南大學(xué);2010年

5 陽(yáng)國(guó)貴;對(duì)象關(guān)系數(shù)據(jù)庫(kù)中若干關(guān)鍵技術(shù)的研究[D];中國(guó)人民解放軍國(guó)防科學(xué)技術(shù)大學(xué);2000年

6 周敏奇;基于格雷碼的結(jié)構(gòu)化對(duì)等計(jì)算系統(tǒng)及其數(shù)據(jù)管理[D];復(fù)旦大學(xué);2008年

7 陳志坤;分布式環(huán)境下大數(shù)據(jù)組織與管理關(guān)鍵技術(shù)的研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2014年

8 張圣棟;虛擬計(jì)算環(huán)境中高效發(fā)布訂閱系統(tǒng)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2011年

9 張蓉;結(jié)構(gòu)化對(duì)等計(jì)算機(jī)系統(tǒng)中的查詢(xún)處理[D];復(fù)旦大學(xué);2007年

10 黎志升;地理信息檢索若干技術(shù)研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2009年

相關(guān)碩士學(xué)位論文 前10條

1 王章龍;Elasticsearch索引分片策略研究[D];重慶郵電大學(xué);2019年

2 關(guān)凱勝;kNN查詢(xún)中面向索引結(jié)構(gòu)的聚類(lèi)算法研究[D];廣東工業(yè)大學(xué);2019年

3 向文坤;面向推薦系統(tǒng)的可學(xué)習(xí)哈希索引模型研究[D];云南大學(xué);2018年

4 易新;基于用戶(hù)偏好約束的位置感知排序查詢(xún)研究[D];重慶郵電大學(xué);2019年

5 劉建坤;OBF-Index：基于Ordinal Bloom Filter的分布式多維索引[D];云南大學(xué);2017年

6 楊旭敏;基于網(wǎng)格的移動(dòng)對(duì)象軌跡混合索引結(jié)構(gòu)[D];燕山大學(xué);2018年

7 趙芳華;基于時(shí)態(tài)的通用位置感知排序查詢(xún)研究[D];燕山大學(xué);2018年

8 曹鴻源;重刪環(huán)境下雙B-樹(shù)索引性能優(yōu)化研究[D];中南民族大學(xué);2018年

9 張娟;基于GPU的Hash索引結(jié)構(gòu)的設(shè)計(jì)與實(shí)現(xiàn)[D];浙江大學(xué);2018年

10 許偉;服務(wù)庫(kù)多級(jí)索引模型性能分析[D];江蘇大學(xué);2017年

本文編號(hào)：2858588