[發(fā)明專利]LSM數(shù)據(jù)合并排序方法和裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 201410204080.2
• 申請(qǐng)日: 2014-05-14
• 公開（公告）號(hào): CN105095287B
• 公開（公告）日: 2018-09-28
• 發(fā)明（設(shè)計(jì)）人: 岳銀亮;張子剛;潘鋒烽;劉揚(yáng)寬
• 申請(qǐng)（專利權(quán)）人: 華為技術(shù)有限公司;中國科學(xué)院計(jì)算技術(shù)研究所
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 北京同立鈞成知識(shí)產(chǎn)權(quán)代理有限公司 11205
• 代理人: 劉芳

本發(fā)明實(shí)施例提供一種LSM數(shù)據(jù)合并排序方法和裝置，通過利用相鄰兩級(jí)之間SSTable的相似度，對(duì)相鄰兩級(jí)中鍵值相似度最高的一對(duì)SSTable進(jìn)行合并排序操作，因?yàn)椋I值相似度最高的一對(duì)SSTable內(nèi)存在相同的鍵值最多，也就是存在鍵值的舊版本最多，因此，根據(jù)鍵值相似度確定進(jìn)行合并排序操作的SSTable，能夠最早最多的刪除舊版本的鍵值，避免舊版本的鍵值在存儲(chǔ)設(shè)備中存儲(chǔ)較長(zhǎng)時(shí)間，占用存儲(chǔ)空間，從而，提高存儲(chǔ)空間的利用率。

技術(shù)領(lǐng)域

本發(fā)明實(shí)施例涉及計(jì)算機(jī)技術(shù)，尤其涉及一種日志結(jié)構(gòu)合并(Log StructuredMerge，以下簡(jiǎn)稱：LSM)數(shù)據(jù)合并排序方法和裝置。

背景技術(shù)

LSM是一種有序非本地更新的數(shù)據(jù)結(jié)構(gòu)，常用于大數(shù)據(jù)合并排序的數(shù)據(jù)結(jié)構(gòu)，其主要應(yīng)用于頻繁更新的數(shù)據(jù)索引，數(shù)據(jù)頻繁更新意味著存儲(chǔ)設(shè)備中有大量鍵值(key/value)存在兩個(gè)或更多版本。

通常，LSM有7級(jí)(level)，現(xiàn)有技術(shù)中，當(dāng)某級(jí)的數(shù)據(jù)大小超過預(yù)設(shè)閾值時(shí)，將該級(jí)中的某個(gè)鍵范圍(key Range)內(nèi)的排序字符串表(Sorted String Table，以下簡(jiǎn)稱：SSTable)與下一級(jí)中的相同的鍵范圍內(nèi)的SSTable 進(jìn)行合并排序(compact)操作，從而，實(shí)現(xiàn)對(duì)鍵值的壓縮和排序。SSTable 是指在一個(gè)鍵范圍內(nèi)存儲(chǔ)的鍵值的排序表。

然而，采用現(xiàn)有技術(shù)的方法，針對(duì)存儲(chǔ)設(shè)備中同一個(gè)鍵值不能及時(shí)刪除舊版本，導(dǎo)致存儲(chǔ)空間的利用率不高。

發(fā)明內(nèi)容

本發(fā)明實(shí)施例提供一種LSM數(shù)據(jù)合并排序方法和裝置，以提高存儲(chǔ)空間的利用率。

本發(fā)明實(shí)施例第一方面提供一種LSM數(shù)據(jù)合并排序方法，包括：

獲取相鄰兩級(jí)之間鍵值相似度最高的一對(duì)排序字符串表；

對(duì)所述一對(duì)排序字符串表進(jìn)行合并排序操作。

結(jié)合第一方面，在第一種可能的實(shí)現(xiàn)方式中，所述獲取相鄰兩級(jí)之間鍵值相似度最高的一對(duì)排序字符串表，包括：

以預(yù)設(shè)時(shí)間間隔獲取相鄰兩級(jí)之間鍵值相似度最高的一對(duì)排序字符串表。

結(jié)合第一方面，在第二種可能的實(shí)現(xiàn)方式中，所述獲取相鄰兩級(jí)之間鍵值相似度最高的一對(duì)排序字符串表，包括：

判斷所述相鄰兩級(jí)中的上一級(jí)存儲(chǔ)的數(shù)據(jù)大小是否超過預(yù)設(shè)閾值；

當(dāng)所述相鄰兩級(jí)中的上一級(jí)存儲(chǔ)的數(shù)據(jù)大小超過預(yù)設(shè)閾值時(shí)，則獲取相鄰兩級(jí)之間鍵值相似度最高的一對(duì)排序字符串表。

結(jié)合第一方面或第一種可能的實(shí)現(xiàn)方式或第二種可能的實(shí)現(xiàn)方式，在第三種可能的實(shí)現(xiàn)方式中，所述對(duì)所述一對(duì)排序字符串表進(jìn)行合并排序操作，包括：

從所述一對(duì)排序字符串表的相同的鍵值中確定舊版本的鍵值；

將所述舊版本的鍵值刪除；

對(duì)刪除所述舊版本之后的所述一對(duì)排序字符串表中的各鍵值進(jìn)行排序。

本發(fā)明實(shí)施例第二方面提供一種LSM數(shù)據(jù)合并排序裝置，包括：

獲取模塊，用于獲取相鄰兩級(jí)之間鍵值相似度最高的一對(duì)排序字符串表；

處理模塊，用于對(duì)所述一對(duì)排序字符串表進(jìn)行合并排序操作。

結(jié)合第二方面，在第一種可能的實(shí)現(xiàn)方式中，所述獲取模塊具體用于以預(yù)設(shè)時(shí)間間隔獲取相鄰兩級(jí)之間鍵值相似度最高的一對(duì)排序字符串表。

結(jié)合第二方面，在第二種可能的實(shí)現(xiàn)方式中，所述獲取模塊具體用于判斷所述相鄰兩級(jí)中的上一級(jí)存儲(chǔ)的數(shù)據(jù)大小是否超過預(yù)設(shè)閾值；當(dāng)所述相鄰兩級(jí)中的上一級(jí)存儲(chǔ)的數(shù)據(jù)大小超過預(yù)設(shè)閾值時(shí)，則獲取相鄰兩級(jí)之間鍵值相似度最高的一對(duì)排序字符串表。