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

【相似文獻】

相關期刊論文 前10條

1 嚴趙峰;張為華;;面向大數(shù)據(jù)的索引結構研究進展[J];大數(shù)據(jù);2019年04期

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

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

4 馮玉才,曹奎,曹忠升;一種支持快速相似檢索的多維索引結構[J];軟件學報;2002年08期

5 侯臻燕;;〈化學亞結構索引〉用法簡介[J];大學化學;1987年05期

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

7 陽國貴;;一種支持多維空間數(shù)據(jù)管理的Quad-tree索引結構[J];計算機工程與科學;1989年03期

8 長孫妮妮;張毅坤;華燈鑫;鄒子夏;陳浩;;一種基于B+樹的混合索引結構[J];計算機工程;2012年14期

9 龍柏;孫廣中;熊焰;陳國良;;一種基于多核機群架構的混合索引結構[J];電子學報;2011年02期

10 南國芳;黃才炎;楊挺;;基于混合索引結構的傳感器網(wǎng)絡查詢系統(tǒng)仿真[J];系統(tǒng)仿真學報;2011年01期

相關博士學位論文 前10條

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

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

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

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

5 陽國貴;對象關系數(shù)據(jù)庫中若干關鍵技術的研究[D];中國人民解放軍國防科學技術大學;2000年

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

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

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

9 張蓉;結構化對等計算機系統(tǒng)中的查詢處理[D];復旦大學;2007年

10 黎志升;地理信息檢索若干技術研究[D];中國科學技術大學;2009年

相關碩士學位論文 前10條

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

2 關凱勝;kNN查詢中面向索引結構的聚類算法研究[D];廣東工業(yè)大學;2019年

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

4 易新;基于用戶偏好約束的位置感知排序查詢研究[D];重慶郵電大學;2019年

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

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

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

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

9 張娟;基于GPU的Hash索引結構的設計與實現(xiàn)[D];浙江大學;2018年

10 許偉;服務庫多級索引模型性能分析[D];江蘇大學;2017年

本文編號：2858588