基于閃存的索引機制研究.pdf

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

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

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

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

5、統(tǒng)基于閃存的緩沖區(qū)算法給臟頁面特殊優(yōu)先級以減少隨機寫，在這類算法應用場景中，樹型索引內部結點比葉子結點更易被替換出緩沖區(qū)，因為內部結點比葉子結點有更高的干凈概率。另一方面，內部結點比葉子結點訪問頻率高很多，替換出這些結點會降低命中率。論文提出了綜合頁面訪問概率、訪問臨近信息以及頁面是否為臟來選擇替換頁面的算法，成功解決了上述問題。
　　本論文的貢獻點如下:
　　(1)提出了隨著訪問模式動態(tài)調整的自適應線性哈希索引(Self-

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

7、寫傾向的set，保留其日志區(qū)以保持批量更新效率。此外，在合并日志區(qū)到對應bucket時，通過粗粒度寫操作來利用SSD內部并行特性，從而提升寫帶寬。
　　(2)分析了線性哈希的溢出鏈與分裂點的關系，并在SAL-hashing的基礎上提出了一個高內存效率的數據結構，使幾乎每一個bucket上的查詢只需要一次讀操作，查詢效率與可擴展哈希相當。此外，還討論了SAL-hashing對事務支持和故障恢復的能力。
　　(3)提出了一種適應