[發明專利]一種工作負載自適應單層LSMT的鍵值數據索引方法

有效

• 申請號: 202010244527.4
• 申請日: 2020-03-31
• 公開（公告）號: CN111475507B
• 公開（公告）日: 2022-06-21
• 發明（設計）人: 陳珂;周信靜;壽黎但;駱歆遠;伍賽;江大偉;陳剛
• 申請（專利權）人: 浙江大學
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06K9/62;G06N3/04;G06N3/08
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 邱啟旺

1.一種工作負載自適應單層LSMT的鍵值數據索引方法，其特征在于，具體包括以下步驟：

(1)對LSMT存儲結構進行修改設計，包括以下子步驟：

(1.1)去除LSMT多層結構的中間層，保留最后一層，并將最后一層作為存儲層L₀；將原先固定容量的內存表換成動態容量內存表，所述動態容量內存表的容量值為M，引入實數參數R，R1，滿足|L₀|為當前存儲層的數據量；

(1.2)將存儲層L₀根據鍵范圍分區成N個子鍵空間l₁,l₂,…,l_N，所述子鍵空間不重疊，且每個子鍵空間l_i(1≤i≤N)的數據均存儲在獨立的存儲文件中；每個子鍵空間l_i(1≤i≤N)最多存儲T個來自所述動態容量內存表對該子鍵空間內的數據的更新Run，并且記γ(l_i)為所述子鍵空間l_i所含有的Run集合，|γ(l_i)|為集合大小；所述Run的鍵值數據按照鍵順序排序，并且一個子鍵空間的Run之間可重疊；所述T≥1；

(2)將所述動態容量內存表進行合并，具體為：當所述動態容量內存表的容量值超過M，將所述動態容量內存表轉換成只讀內存表，并在后臺線程中啟動合并過程，將所述只讀內存表合入存儲層L₀，同時，建立新的活動內存表，繼續處理前端讀寫請求；所述合并過程具體為：根據存儲層L₀的子鍵空間的范圍分區，將所述只讀內存表劃分成N個Run，記為r₁,r₂,…,r_N，其中r_i屬于l_i；然后將r_i寫入對應的子鍵空間l_i對應的存儲文件中；當一個子鍵空間l_i的數據量超過閾值β或|γ(l_i)|t時，將γ(l_i)合并成一個Run，即合并之后|γ(l_i)|＝1，并且根據數據量等分成兩個子鍵空間，當合并完成后，索引寫步驟完畢。

2.根據權利要求1所述鍵值數據索引方法，其特征在于，所述閾值β的取值為64MB。

3.根據權利要求1所述鍵值數據索引方法，其特征在于，該索引方法還包括自適應讀優化方法，包括以下子步驟：

(a)將作為t時刻所述子鍵空間l_i的讀熱度統計，對于t時刻的讀熱度獲為：

其中，為t-1至t時刻之間，對子鍵空間l_i的讀次數，α為衰減因子，0a1，且

(b)將作為t時刻所述子鍵空間l_i的寫熱度統計，對于t時刻的寫熱度為：

其中，為t-1至t時刻之間，對子鍵空間l_i的寫入次數，且I^(t)為當前時刻t與上一個時刻t-1之間流逝的時間；

(c)定期運行下述過程：首先根據寫熱度對子鍵空間進行聚類，分成四類，分別為：Cold、Warm、WriteBalanced、WriteHeavy；選擇寫熱度最低的Cold類的子鍵空間，然后根據讀熱度對所述Cold類的子鍵空間進行降序排序，并且過濾掉滿足如下條件的子鍵空間l_i：接著在這個排好序并過濾完畢的Cold類子鍵空間集合中選擇前P個，l₁,l₂,…,l_P，將每個子鍵空間l_i的γ(l_i)(1≤i≤P)集合合并成一個Run。