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

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

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

【相似文獻(xiàn)】

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

1 潘鵬;盧炎生;彭祥禮;;基于位置變化的軌跡單元?jiǎng)澐旨八饕龣C(jī)制[J];小型微型計(jì)算機(jī)系統(tǒng);2006年11期

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

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

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

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

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

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

8 張，

本文編號(hào)：1333154