基于閃存的索引機(jī)制研究.pdf

1、隨著閃存存儲器制作工藝的不斷發(fā)展，閃存的存儲密度大幅提高，基于閃存芯片陣列的固態(tài)硬盤(Solid State Drive，SSD)應(yīng)運(yùn)而生并迅速普及于工業(yè)界的存儲系統(tǒng)和桌面PC。由于和傳統(tǒng)磁盤有相同的物理和邏輯接口，SSD被視為存儲系統(tǒng)革新的關(guān)鍵技術(shù)，學(xué)術(shù)界和工業(yè)界都對SSD完全取代磁盤持樂觀態(tài)度。然而，SSD具有不同于磁盤的獨(dú)特特性，如閃存的寫前擦除機(jī)制，讀寫不均衡，擦除次數(shù)有限等，使得原有在磁盤上的數(shù)據(jù)管理算法不能充分發(fā)揮SSD的性

2、能。因此，針對SSD特性研究設(shè)計(jì)適合于SSD上的數(shù)據(jù)管理新方法非常重要。
　　索引對數(shù)據(jù)檢索至關(guān)重要，使用索引可快速訪問海量數(shù)據(jù)中的特定信息。傳統(tǒng)的索引機(jī)制是面向I/O對稱的磁盤設(shè)計(jì)，索引的更新造成大量隨機(jī)寫操作。由于閃存的隨機(jī)寫性能較差，如果將傳統(tǒng)的索引機(jī)制直接應(yīng)用在閃存上，并不能獲得理想的性能提升。因此，近年來基于閃存的索引機(jī)制研究引起了學(xué)術(shù)界的重視。
　　目前基于閃存的索引機(jī)制研究按索引結(jié)構(gòu)大致可分為三類:(1)基于閃

3、存的哈希索引機(jī)制研究;(2)基于閃存的樹型索引機(jī)制研究;(3)基于閃存的位圖索引機(jī)制研究。已有研究都是以減少對閃存的隨機(jī)寫為目標(biāo)，主要用到以讀換寫、批量更新、異位更新、及轉(zhuǎn)化隨機(jī)寫為連續(xù)寫等技術(shù)手段。本論文分析了已有研究關(guān)鍵技術(shù)的不足:(1)雖然減少了對SSD的隨機(jī)寫操作，但是造成了大量的額外讀操作，考慮到目前SSD內(nèi)部控制技術(shù)的成熟，讀寫差異相較之前大幅縮小，大量額外讀操作反而降低了總體性能;(2)在更新密集的數(shù)據(jù)集下表現(xiàn)出良好性能，

4、但是在查詢密集數(shù)據(jù)集下性能與原索引差距明顯;(3)基本未考慮利用SSD內(nèi)部并行機(jī)制來進(jìn)一步提升性能。因此，需要針對先進(jìn)的讀寫差異接近的SSD，研究適應(yīng)于更普適應(yīng)用數(shù)據(jù)集的索引機(jī)制。本文聚焦于哈希索引和B+-樹，提出了隨著訪問模式動態(tài)調(diào)整的線性哈希，并進(jìn)一步對該索引進(jìn)行查詢優(yōu)化;本文還為讀寫優(yōu)化的B+-樹索引提供了理論基礎(chǔ)。
　　提高索引讀寫性能，離不開緩沖區(qū)，本論文討論了樹型索引訪問特性和面向閃存的緩沖區(qū)算法設(shè)計(jì)原則之間的矛盾。傳

5、統(tǒng)基于閃存的緩沖區(qū)算法給臟頁面特殊優(yōu)先級以減少隨機(jī)寫，在這類算法應(yī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)訪問頻率高很多，替換出這些結(jié)點(diǎn)會降低命中率。論文提出了綜合頁面訪問概率、訪問臨近信息以及頁面是否為臟來選擇替換頁面的算法，成功解決了上述問題。
　　本論文的貢獻(xiàn)點(diǎn)如下:
　　(1)提出了隨著訪問模式動態(tài)調(diào)整的自適應(yīng)線性哈希索引(Self-

6、AdaptiveLinear Hashing, SAL-hashing)。該索引使用了批量更新的技術(shù)，同時(shí)引入了組(group)和集合(set)的概念來提升批量更新的效率。對索引的更新先緩存在內(nèi)存，然后以set為粒度向索引批量刷新更新操作到set對應(yīng)的日志區(qū)。此外，該索引根據(jù)各set的訪問傾向性實(shí)時(shí)決定是否將日志區(qū)與對應(yīng)的set合并口對于讀傾向的set，及時(shí)將日志區(qū)合并到set對應(yīng)的bucket中，后續(xù)的查詢可以避免額外的讀日志區(qū);對于

7、寫傾向的set，保留其日志區(qū)以保持批量更新效率。此外，在合并日志區(qū)到對應(yīng)bucket時(shí)，通過粗粒度寫操作來利用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對事務(wù)支持和故障恢復(fù)的能力。
　　(3)提出了一種適應(yīng)