[發(fā)明專利]一種工作負(fù)載自適應(yīng)單層LSMT的鍵值數(shù)據(jù)索引方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202010244527.4
• 申請(qǐng)日: 2020-03-31
• 公開（公告）號(hào): CN111475507B
• 公開（公告）日: 2022-06-21
• 發(fā)明（設(shè)計(jì)）人: 陳珂;周信靜;壽黎但;駱歆遠(yuǎn);伍賽;江大偉;陳剛
• 申請(qǐng)（專利權(quán)）人: 浙江大學(xué)
• 主分類號(hào): G06F16/22
• 分類號(hào): G06F16/22;G06K9/62;G06N3/04;G06N3/08
• 代理公司: 杭州求是專利事務(wù)所有限公司 33200
• 代理人: 邱啟旺

本發(fā)明公開了一種工作負(fù)載自適應(yīng)單層LSMT的鍵值數(shù)據(jù)索引方法。該方法對(duì)傳統(tǒng)的日志結(jié)構(gòu)合并樹(Log?Structured?Merge Tree，LSMT)進(jìn)行了優(yōu)化，去除了多層設(shè)計(jì)和固定內(nèi)存表容量設(shè)計(jì)，引入了單層LSMT和動(dòng)態(tài)容量?jī)?nèi)存表的設(shè)計(jì)。該方法將寫入首先將寫操作以順序的方式寫入存儲(chǔ)設(shè)備上的日志文件中，再修改內(nèi)存表。當(dāng)內(nèi)存表的大小達(dá)到了容量限制，轉(zhuǎn)換成一個(gè)只讀內(nèi)存表，并在后臺(tái)線程中將只讀內(nèi)存表表合入存儲(chǔ)設(shè)備上的單層LSMT結(jié)構(gòu)中。在此基礎(chǔ)上，本方法能夠根據(jù)工作負(fù)載中的鍵值讀寫分布自動(dòng)優(yōu)化存儲(chǔ)結(jié)構(gòu)。該索引方法能夠同時(shí)降低對(duì)存儲(chǔ)設(shè)備的讀寫放大，提升系統(tǒng)吞吐和存儲(chǔ)設(shè)備壽命。同時(shí)針對(duì)工作負(fù)載做出自適應(yīng)的優(yōu)化，進(jìn)一步提升系統(tǒng)性能。

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

本發(fā)明屬數(shù)據(jù)庫系統(tǒng)技術(shù)領(lǐng)域，具體地涉及一種工作負(fù)載自適應(yīng)單層LSMT的鍵值數(shù)據(jù)索引方法。

背景技術(shù)

基于日志結(jié)構(gòu)合并樹(Log-Structured-Merge Tree，LSMT)的鍵值存儲(chǔ)系統(tǒng)，由于其優(yōu)秀的處理密集寫能力，被廣泛應(yīng)用在數(shù)據(jù)密集型互聯(lián)網(wǎng)應(yīng)用中。但是現(xiàn)有基于LSMT的存儲(chǔ)系統(tǒng)一般都存在著放大問題和工作負(fù)載無感知的問題。放大問題是指用戶請(qǐng)求讀取/寫入的數(shù)據(jù)量要遠(yuǎn)小于系統(tǒng)實(shí)際需要在存儲(chǔ)設(shè)備上讀取/寫入的數(shù)據(jù)量，可以采用放大因子來量化這個(gè)問題。工作負(fù)載無感知的問題指的是現(xiàn)有LSMT系統(tǒng)無法根據(jù)工作負(fù)載中的讀寫分布對(duì)存儲(chǔ)結(jié)構(gòu)做出更加合適的優(yōu)化。

為了解決讀寫放大問題，研究者提出了許多方法，但是這些方法一般犧牲了讀放大來換取寫放大的降低(如WiscKey、PebblesDB)，無法保證讀寫都高效。而對(duì)于工作負(fù)載無感知的問題，也很少有研究者對(duì)其進(jìn)行研究和解決。

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

針對(duì)現(xiàn)有技術(shù)的不足，本發(fā)明提出一種在塊存儲(chǔ)設(shè)備上的工作負(fù)載自適應(yīng)鍵值數(shù)據(jù)索引方法。該方法能有效降低讀寫放大，同時(shí)根據(jù)工作負(fù)載能做出自適應(yīng)的存儲(chǔ)結(jié)構(gòu)優(yōu)化，進(jìn)一步讀降低延遲。

本發(fā)明的目的是通過以下技術(shù)方案實(shí)現(xiàn)的：一種工作負(fù)載自適應(yīng)單層LSMT的鍵值數(shù)據(jù)索引方法，具體包括以下步驟：

(1)對(duì)LSMT存儲(chǔ)結(jié)構(gòu)進(jìn)行修改設(shè)計(jì)，包括以下子步驟：

(1.1)去除LSMT多層結(jié)構(gòu)的中間層，保留最后一層，并將最后一層作為存儲(chǔ)層L₀；將原先固定容量的內(nèi)存表換成動(dòng)態(tài)容量?jī)?nèi)存表，所述動(dòng)態(tài)容量?jī)?nèi)存表的容量值為M，引入實(shí)數(shù)參數(shù)R，R＞1，滿足|L₀|為當(dāng)前存儲(chǔ)層的數(shù)據(jù)量。

(1.2)將存儲(chǔ)層L₀根據(jù)鍵范圍分區(qū)成N個(gè)子鍵空間l₁,l₂,…,l_N，所述子鍵空間不重疊，且每個(gè)子鍵空間l_i(1≤i≤N)的數(shù)據(jù)均存儲(chǔ)在獨(dú)立的存儲(chǔ)文件中。每個(gè)子鍵空間l_i(1≤i≤N)最多存儲(chǔ)T個(gè)來自所述動(dòng)態(tài)容量?jī)?nèi)存表對(duì)該子鍵空間內(nèi)的數(shù)據(jù)的更新Run，并且記γ(l_i)為所述子鍵空間l_i所含有的Run集合，|γ(l_i)|為集合大?。凰鯮un的鍵值數(shù)據(jù)按照鍵順序排序，并且一個(gè)子鍵空間的Run之間可重疊；所述T≥1。