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

有效

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

1.一種基于GPU分組LSM樹索引的方法，其特征在于：包括以下步驟：

步驟1：對(duì)Key-Value數(shù)據(jù)進(jìn)行預(yù)處理，將數(shù)據(jù)在內(nèi)存中進(jìn)行鍵值Key和數(shù)據(jù)Value的分離；將Value存放在內(nèi)存中，同時(shí)在內(nèi)存中用哈希表存儲(chǔ)Value和對(duì)應(yīng)的地址，查詢時(shí)以O(shè)(1)的時(shí)間復(fù)雜度定位Value；分離之后將Key和Value的地址拷貝到GPU的全局內(nèi)存中；

步驟2：將數(shù)據(jù)插入到GPU分組LSM樹中；

所述GPU分組LSM樹中，所有數(shù)據(jù)均是按批進(jìn)行插入，假設(shè)每一批數(shù)據(jù)大小為b，數(shù)據(jù)組group的數(shù)量為g，因此GPU分組LSM中每一層都會(huì)有g(shù)個(gè)group且第i層有b*g⁽ⁱ⁺¹⁾個(gè)組，整個(gè)GPU分組LSM包含的數(shù)據(jù)都是b的整數(shù)倍；使用GPU的基數(shù)排序?qū)?shù)據(jù)進(jìn)行排序，并查看GPU分組LSM樹中第一層是否有空的組，有則將數(shù)據(jù)拷貝到該組中，沒有則觸發(fā)合并操作，使第一層為空然后將數(shù)據(jù)拷貝到第一層；

步驟3：進(jìn)行數(shù)據(jù)查詢時(shí)，進(jìn)行部分排序提高合并內(nèi)存訪問效率，確定需要排序比特位數(shù)量；

假設(shè)Key的長度位為B個(gè)比特，GPU分組LSM樹的大小為T，GPU緩存存放的Key的長度為K，Key的范圍長度為2^B，LSM樹中的每一個(gè)Key覆蓋的范圍是2^B/T*K，則該范圍的平均比特位個(gè)數(shù)為log₂(2^B/T*K)；若查詢中的內(nèi)存請(qǐng)求屬于高速緩存行的覆蓋范圍，則無論請(qǐng)求的Key是否排序，都是合并的內(nèi)存訪問；因此，當(dāng)查詢的Key位于同一高速緩存行中時(shí)，不對(duì)查詢進(jìn)行排序，使用以下公式計(jì)算排序的比特位數(shù)量N：

N＝B-log₂(2^B/T*K)

步驟4：對(duì)查詢的數(shù)據(jù)使用布隆過濾器篩選掉無關(guān)查詢；

步驟5：將訪問的數(shù)據(jù)加載到共享內(nèi)存中；查詢會(huì)訪問每一個(gè)group中的固定位置的數(shù)據(jù)，這些查詢數(shù)據(jù)會(huì)全部訪問這棵樹的根節(jié)點(diǎn)，數(shù)據(jù)訪問這棵樹的前L層數(shù)據(jù)，其中L為正整數(shù)；

步驟6：在GPU上對(duì)共享內(nèi)存中的數(shù)據(jù)進(jìn)行查詢，得到對(duì)應(yīng)的全局內(nèi)存中的位置，然后再到全局內(nèi)存中進(jìn)行查詢；由于GPU上存放的是Value的地址，因此查詢完成后會(huì)將查詢結(jié)果拷貝到內(nèi)存中去，再由CPU端進(jìn)行處理，通過查找Hash表取出對(duì)應(yīng)Value的值，這樣就完成了在GPU分組LSM樹上的查詢過程。

2.根據(jù)權(quán)利要求1所述的一種基于GPU分組LSM樹索引的方法，其特征在于，步驟4所述布隆過濾器SBF由M個(gè)哈希函數(shù)組成，M為正整數(shù)，每個(gè)哈希函數(shù)是獨(dú)立不相關(guān)的。