[發明專利]一種快速的鍵值數據庫的系統及建立方法

有效

• 申請號: 201810019205.2
• 申請日: 2018-01-09
• 公開（公告）號: CN108388569B
• 公開（公告）日: 2021-07-20
• 發明（設計）人: 陳潔;孔軍;胡海洋;姜濤;胡華
• 申請（專利權）人: 杭州電子科技大學
• 主分類號: G06F16/21
• 分類號: G06F16/21;G06F16/22
• 代理公司: 杭州君度專利代理事務所(特殊普通合伙) 33240
• 代理人: 朱月芬

1.一種快速的鍵值數據庫的系統，其特征在于構建了一種新的數據存儲結構，在單文件情況下實現快速讀寫文件型鍵值對；

該系統包括索引模塊、存儲模塊、讀取模塊、校驗模塊、索引重建模塊、數據回滾模塊、數據精簡模塊和日志模塊；

該系統新的數據存儲結構實現了將索引文件和數據文件的合并；每個數據庫文件包含連續的三部分數據：頭部分Header、數據部分Data和索引部分Index；其中數據部分和索引部分的長度均不固定，均由若干個鍵值數據對逐個往后排列構成；數據庫文件的存儲結構為{Header,Data_i,Index_j|i＝1,2..,n,j＝1,2…,m}；

數據庫文件的存儲結構具體大小設置及功能定義如下：

Data_i：用于保存數據，其結構為一個大小不固定的鍵值對(D_K_i，D_V_i)，D_K_i為鍵，其結構包含D_K_Len_i和D_K_Key_i，其中D_K_Key_i用于存儲數據的唯一編號，D_K_Len_i用于存儲D_K_Key_i所記錄的編號的大小；D_V_i為值，其結構包含D_V_Len_i和D_V_Value_i，其中D_V_Value_i用于存儲數據的具體內容，D_V_Len_i用于存儲D_V_Key_i所記錄的數據的大小；D_K_Len_i和D_V_Len_i都是經過壓縮的整數，其所占用的存儲空間的大小是不固定的；

Index_j：用于保存索引數據，即索引表，其結構與Data_i一致，為一個大小不固定的鍵值對(I_K_j，I_V_j)，其中，I_K_j包含I_K_Len_j和I_K_Con_j兩部分；其中I_K_Con_j＝(Prefix_j,Timestamp_j,Prev_j)用于記錄第j個索引表的上下文信息，Prefix_j為一個標記性的字符串作為索引的標記，占7個字節的存儲空間；Timestamp_j為時間戳，用于表示數據記錄的時間點，占8個字節的存儲空間；Prev_j用于記錄上個索引表所在的位置，占8個字節的存儲空間；I_K_Len_j占1字節的存儲空間，用于記錄I_K_Con_j的長度；I_V_j包含I_V_Len_j,I_V_Info_j兩部分，I_V_Len_j用于記錄I_V_Info_j的長度；I_V_Info_j為索引表的內容，記錄了所有的索引信息，其結構也為若干個鍵值對，即{(I_key_q,I_value_q)|q＝1,2…,p}；其中I_key_q＝(I_key_Len_q,I_key_k_q)，其中I_key_k_q用于記錄數據的唯一編號，即與數據庫文件中Data_i部分的D_K_Key_i一致；I_key_Len_q用于記錄I_key_k_q的大小；I_value_q＝(I_value_Len_q,I_value_offset_q)，其中I_value_offset_q用于記錄數據的內容在文件中的偏移量，即Data_i部分的D_V_i在數據庫文件中的偏移量；I_value_Len_q用于記錄數據的大小即Data_i部分的D_V_Len_i；

Header：用以保存索引表的當前位置即最后一個Index_j所在的位置，默認大小為8個字節；當索引表數據更新時，Header數據會發生相應變化作為索引校驗的依據；

所述的索引模塊，其作用是在內存中建立鍵數據到文件中的值數據保存位置的映射關系；存儲模塊，其作用是通過追加的方式對數據進行增加、修改和刪除操作，以提高數據操作的效率；讀取模塊，其作用是根據鍵數據在索引模塊中進行檢索，若沒有查到記錄，則返回錯誤信息；若查到記錄，則根據記錄的值數據的位置到對應文件中讀取數據并返回；校驗模塊，其作用是為了實現多進程/線程對同一個數據庫文件的共享，在某一進程/線程獲得文件控制權后必須對文件格式和索引數據進行校驗；若最新的校驗信息和當前內存里的索引數據相同，則不需要刷新索引數據；否則，則從數據庫文件中讀取最新的索引數據更新到內存中；在整個過程中若沒有出現文件數據解析錯誤，則視為文件格式校驗通過；索引重建模塊，其作用是在文件損壞或者數據回滾和精簡操作時，需要重建索引數據；重建索引時直接從頭開始掃描整個數據庫文件，在索引中記錄鍵數據和值數據的保存位置；數據回滾模塊，其作用是將數據庫回滾至指定的時間點，恢復該時間點的所有數據和狀態，并拋棄指定時間點之后的所有修改；由于數據是按照時間順序存儲的，只需要拋棄時間點之后的數據即可，之前的數據無需更改；數據精簡模塊，其作用是根據輸入的時間點，把指定時間點之前的被刪除或修改的歷史數據刪除，并把剩余數據重新排列消除碎片；日志模塊，其作用是從文件中提取數據庫的修改記錄并返回。

2.根據權利要求1所述的一種快速的鍵值數據庫的系統的建立方法，具體實現包括如下步驟：

步驟(1).在數據庫文件中進行數據的讀取和刪除時，獲取數據的唯一編號；同時在進行數據的寫入、修改時，獲取數據的唯一編號和數據內容；

步驟(2).根據文件頭部記錄的索引表的位置，讀取數據庫文件中的索引表，并對索引數據的正確性進行校驗；若索引數據已損壞，則采取步驟(3)重建索引表；在索引表重建后或索引數據校驗無損時，執行步驟(4)進行數據讀取，或執行步驟(5)進行數據的增加、刪除或修改；

步驟(3).若索引數據已損壞，則重建索引表；

步驟(4).在索引表校驗或重建后，如需要讀取數據，則根據用戶輸入的鍵數據，在索引表中查詢對應的值數據在數據庫文件中的存儲位置信息，再根據該存儲位置在數據庫文件中讀取對應的值數據；

步驟(5)在索引表校驗或重建后，如需增加、刪除或修改數據，則根據用戶輸入的鍵值對數據，以追加方式將該鍵值對數據寫入數據庫文件；具體執行步驟如下：

步驟(5.1)刪除步驟(2)獲取的原有的索引信息；

步驟(5.2)在當前數據文件結尾以追加方式記錄鍵值對數據；新增和修改鍵數據對應的值數據時，記錄其最新的鍵值對數據；對于刪除鍵數據的情況，記錄一個帶空值的鍵值對數據；

步驟(5.3)在當前數據文件結尾以追加方式記錄新操作的上下文信息；

步驟(5.4)將鍵數據在數據庫文件中的位置信息添加到索引表，并將新的索引表同樣以追加方式寫入數據庫文件；

步驟(6)如需獲得數據庫文件的修改日志，首先根據數據庫文件頭的索引表位置，讀取最新的時間戳和上一個數據記錄的位置，并依時間逆序獲得所有的數據操作記錄即日志；

步驟(7)如需將數據庫進行回滾操作，則首先由用戶指定需要回滾到的時間，然后由系統遍歷步驟(6)得到的數據庫日志，得到該時間對應的數據位置，刪除該位置之后的所有數據，并依照步驟(3)中的方法，為留存數據上重建索引表；

步驟(8)如需要對部分舊數據進行精簡，則首先需要用戶指定的進行精簡的時間點；然后系統遍歷步驟(6)得到的數據庫日志，得到指定時間對應的數據位置并對之前的數據進行精簡；依照步驟(3)中的方法，重建該時間點之前所有數據的索引表；數據精簡的具體步驟如下：

步驟(8.1)依照步驟3重建該時間點之前的所有數據的索引表；

步驟(8.2)保留索引表中的數據，刪除所有修改或刪除的數據；將該時間點之后的數據整體前移，填補精簡后的空白；

步驟(8.3)更正索引表中的數據的位置信息。