本文關(guān)鍵詞：基于閃存的索引機制研究　出處：《中國科學技術(shù)大學》2017年博士論文　論文類型：學位論文

  更多相關(guān)文章： SSD 讀寫不對稱 內(nèi)部并行 線性哈希 緩沖區(qū)管理 B+-樹

【摘要】：隨著閃存存儲器制作工藝的不斷發(fā)展,閃存的存儲密度大幅提高,基于閃存芯片陣列的固態(tài)硬盤(Solid State Drive,SSD)應運而生并迅速普及于工業(yè)界的存儲系統(tǒng)和桌面PC。由于和傳統(tǒng)磁盤有相同的物理和邏輯接口,SSD被視為存儲系統(tǒng)革新的關(guān)鍵技術(shù),學術(shù)界和工業(yè)界都對SSD完全取代磁盤持樂觀態(tài)度。然而,SSD具有不同于磁盤的獨特特性,如閃存的寫前擦除機制,讀寫不均衡,擦除次數(shù)有限等,使得原有在磁盤上的數(shù)據(jù)管理算法不能充分發(fā)揮SSD的性能。因此,針對SSD特性研究設(shè)計適合于SSD上的數(shù)據(jù)管理新方法非常重要。索引對數(shù)據(jù)檢索至關(guān)重要,使用索引可快速訪問海量數(shù)據(jù)中的特定信息。傳統(tǒng)的索引機制是面向I/O對稱的磁盤設(shè)計,索引的更新造成大量隨機寫操作。由于閃存的隨機寫性能較差,如果將傳統(tǒng)的索引機制直接應用在閃存上,并不能獲得理想的性能提升。因此,近年來基于閃存的索引機制研究引起了學術(shù)界的重視。目前基于閃存的索引機制研究按索引結(jié)構(gòu)大致可分為三類:(1)基于閃存的哈希索引機制研究;(2)基于閃存的樹型索引機制研究;(3)基于閃存的位圖索引機制研究。已有研究都是以減少對閃存的隨機寫為目標,主要用到以讀換寫、批量更新、異位更新、及轉(zhuǎn)化隨機寫為連續(xù)寫等技術(shù)手段。本論文分析了已有研究關(guān)鍵技術(shù)的不足:(1)雖然減少了對SSD的隨機寫操作,但是造成了大量的額外讀操作,考慮到目前SSD內(nèi)部控制技術(shù)的成熟,讀寫差異相較之前大幅縮小,大量額外讀操作反而降低了總體性能;(2)在更新密集的數(shù)據(jù)集下表現(xiàn)出良好性能,但是在查詢密集數(shù)據(jù)集下性能與原索引差距明顯;(3)基本未考慮利用SSD內(nèi)部并行機制來進一步提升性能。因此,需要針對先進的讀寫差異接近的SSD,研究適應于更普適應用數(shù)據(jù)集的索引機制。本文聚焦于哈希索引和B+-樹,提出了隨著訪問模式動態(tài)調(diào)整的線性哈希,并進一步對該索引進行查詢優(yōu)化;本文還為讀寫優(yōu)化的B+-樹索引提供了理論基礎(chǔ)。提高索引讀寫性能,離不開緩沖區(qū),本論文討論了樹型索引訪問特性和面向閃存的緩沖區(qū)算法設(shè)計原則之間的矛盾。傳統(tǒng)基于閃存的緩沖區(qū)算法給臟頁面特殊優(yōu)先級以減少隨機寫,在這類算法應用場景中,樹型索引內(nèi)部結(jié)點比葉子結(jié)點更易被替換出緩沖區(qū),因為內(nèi)部結(jié)點比葉子結(jié)點有更高的干凈概率。另一方面,內(nèi)部結(jié)點比葉子結(jié)點訪問頻率高很多,替換出這些結(jié)點會降低命中率。論文提出了綜合頁面訪問概率、訪問臨近信息以及頁面是否為臟來選擇替換頁面的算法,成功解決了上述問題。本論文的貢獻點如下:(1)提出了隨著訪問模式動態(tài)調(diào)整的自適應線性哈希索引(Self-Adaptive Linear Hashing,SAL-hashing)。該索引使用了批量更新的技術(shù),同時引入了組(group)和集合(set)的概念來提升批量更新的效率。對索引的更新先緩存在內(nèi)存,然后以set為粒度向索引批量刷新更新操作到set對應的日志區(qū)。此外,該索引根據(jù)各set的訪問傾向性實時決定是否將日志區(qū)與對應的set合并。對于讀傾向的set,及時將日志區(qū)合并到set對應的bucket中,后續(xù)的查詢可以避免額外的讀日志區(qū);對于寫傾向的set,保留其日志區(qū)以保持批量更新效率。此外,在合并日志區(qū)到對應bucket時,通過粗粒度寫操作來利用SSD內(nèi)部并行特性,從而提升寫帶寬。(2)分析了線性哈希的溢出鏈與分裂點的關(guān)系,并在SAL-hashing的基礎(chǔ)上提出了一個高內(nèi)存效率的數(shù)據(jù)結(jié)構(gòu),使幾乎每一個bucket上的查詢只需要一次讀操作,查詢效率與可擴展哈希相當。此外,還討論了 SAL-hashing對事務支持和故障恢復的能力。(3)提出了一種適應于樹型索引的緩沖區(qū)算法,結(jié)合結(jié)點被訪問概率和訪問臨近信息權(quán)衡頁面冷熱,并根據(jù)頁面是否是臟頁面選擇替換頁。此外,該算法將臟頁面打包,采用粗粒度寫來批量刷新冷臟頁面,避免細粒度隨機寫操作。(4)針對本實驗室提出的讀寫優(yōu)化的B+-樹索引,完善了理論分析,討論了索引的并發(fā)訪問,并重新設(shè)計了實驗,同時給出詳細的結(jié)果分析。
【學位授予單位】：中國科學技術(shù)大學
【學位級別】：博士
【學位授予年份】：2017
【分類號】：TP333

【相似文獻】

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

1 潘鵬;盧炎生;彭祥禮;;基于位置變化的軌跡單元劃分及索引機制[J];小型微型計算機系統(tǒng);2006年11期

2 陳雍;謝旭升;魏根芽;;Oracle B*樹索引內(nèi)部機制及其應用的研究[J];計算機與現(xiàn)代化;2008年10期

3 高玉良;張濟強;白瑤;;基于Lucene的多索引搜索的研究與應用[J];電腦知識與技術(shù);2012年07期

4 陳仲肅;;淺談索引失效原因、對策及其應用[J];軟件;2012年07期

5 周英華;金培權(quán);岳麗華;龔育昌;;基于位置的web搜索索引研究[J];中國科學技術(shù)大學學報;2007年02期

6 趙娟娟;;嵌入數(shù)據(jù)庫索引機制及特點研究[J];硅谷;2011年02期

7 耿慶田;狄婧;常亮;趙宏偉;;基于B+樹的數(shù)據(jù)索引存儲[J];吉林大學學報(理學版);2013年06期

8 張，

本文編號：1333154