[發(fā)明專利]基于GPU分組LSM樹索引的方法

有效

• 申請?zhí)枺?/td>: 202010836000.0
• 申請日: 2020-08-19
• 公開（公告）號: CN112000846B
• 公開（公告）日: 2021-07-20
• 發(fā)明（設計）人: 谷峪;李萬;李傳文;李芳芳;于戈
• 申請（專利權）人: 東北大學
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/903;G06F16/245
• 代理公司: 沈陽東大知識產權代理有限公司 21109
• 代理人: 李在川

本發(fā)明提供一種基于GPU分組LSM樹索引的方法，涉及GPU數據庫技術領域。本發(fā)明首先將數據進行預處理，當value為變長時，在GPU上進行查詢時不能很好的利用緩存而且數據傳輸代價也會增大。本發(fā)明針對以上情況，將數據中的Key和Value進行分離，GPU中僅僅存放Value的地址，真正的Value存放在內存中。針對LSM插入速度慢的問題，本發(fā)明將原來的LSM樹每一層分為多個組，每個組都是一個有序數組，合并到下一層的時候通過GPU上大量的線程并行的歸并。由于將LSM樹進行分組，意味著查詢需要花費更高的代價。為了提高查詢速度，本發(fā)明在GPU上設計了一種適應于GPU結構的布隆過濾器，通過布隆過濾器減少了大量不必要的查詢開銷。

技術領域

本發(fā)明涉及GPU數據庫技術領域，尤其涉及一種基于GPU分組LSM樹索引的方法。

背景技術

隨著大數據時代的到來，數據總量和數據訪問量都在爆炸式的增長。傳統(tǒng)的關系型數據庫已經不能夠滿足這種高并發(fā)的訪問場景。而Nosql數據庫不依賴于關系數據庫的傳統(tǒng)結構且更加靈活和方便，因此非常適用于云存儲,電子商務和web訪問等。鍵值(Key-Value,KV)是Nosql數據庫的基本類型,通過GET,PUT,DELETE等簡單的接口就能對大量非結構化的數據進行讀寫。

目前主流的Nosql數據庫的索引結構都是日志結構合并樹(log-sturctre mergetree,LSM Tree)。LSM樹是重要的數據結構之一。它被廣泛用于levelDB，rocksDB，Cassandra等NoSql數據庫中。LSM樹是一種多層的結構，它的基本思想是先將數據的修改或者插入保存在內存中，當內存達到容量限制再將這些操作順序寫入磁盤，磁盤中的樹在后臺會進行定期的合并操作，最后以歸并的方式合并成一棵大樹。相比于其它索引結構例如B樹，它在數據的插入，刪除修改方面有極高的速度。由于LSM樹的這種分層結構，查詢也會在內存和磁盤上進行多次二分查找，這樣就明顯的降低了它的查詢速度。因此LSM樹適用于寫入遠大于讀取的場景。相比于內存上的數據結構，LSM樹這種磁盤上的數據結構性能的瓶頸在于磁盤IO上。

先前的工作都是針對磁盤IO問題也就是LSM樹的讀寫放大問題進行優(yōu)化的，例如WiscKey進行KV分離，降低寫Value的代價。PebblesDB通過弱化全局有序來降低寫放大。

相比于磁盤上的數據結構，內存中的數據結構性能在于算法的時間復雜度和并發(fā)線程的數量。而GPU的大量線程和高速的帶寬就非常適合于處理LSM這種數據結構。由于GPU的多核處理器使用SIMD執(zhí)行方法大大提高了數據處理速度并減少數據響應時間，許多索引結構已經在GPU上實現了高性能，例如Harmonia，SlabHash等。目前在GPU上實現的索引結構主要分為兩大類，基于hash的索引和基于樹的索引。基于hash索引的結構能夠進行快速的插入刪除更新和點查找，但不能像基于樹的索引結構支持范圍查找。而且對于更新操作許多GPU索引結構不是動態(tài)的更新，而是在GPU上重新構建索引結構。GPULSM樹是首個在GPU上實現的LSM樹索引結構但是它的插入查詢等操作也沒有很好的和GPU硬件結構匹配。

發(fā)明內容

針對現有技術的不足，本發(fā)明提供一種基于GPU分組LSM樹索引的方法，將LSM樹每一層分為多個組，數據在組內有序，在組間無序。當某一層數據滿了的時候通過GPU上的大量線程并行的歸并到下一層中。而針對LSM樹查詢速度慢的問題，本發(fā)明通過布隆過濾器排除掉了大量不必要的查詢，提高了查詢效率。

為解決上述技術問題，本發(fā)明所采取的技術方案是：

一種基于GPU分組LSM樹索引的方法，包括以下步驟：

步驟1：對Key-Value數據進行預處理，將數據在內存中進行鍵值Key和數據Value的分離；

將Value存放在內存中，同時在內存中用哈希表存儲Value和對應的地址，查詢時以O(1)的時間復雜度定位Value；分離之后將Key和Value的地址拷貝到GPU的全局內存中；