一種哈希資料庫的配置方法和裝置製造方法
2023-07-04 05:18:26 1
一種哈希資料庫的配置方法和裝置製造方法
【專利摘要】本發明實施例公開了一種哈希資料庫的配置方法，包括：在磁碟上開闢索引區和數據區，其中，所述索引區由p個大小相等的磁碟頁面組成；接收到Key-Value對的分配請求，將所述Key-Value對中m個Key分配至所述索引區的磁碟頁面中，且將所述Key-Value對中的n個Value分配至所述數據區中，m、n和p均為大於1的整數。本發明實施例還公開了一種哈希資料庫的配置裝置。採用本發明，提高哈希資料庫的訪問效率。
【專利說明】一種哈希資料庫的配置方法和裝置
【技術領域】
[0001]本發明涉及計算機領域，尤其涉及一種哈希資料庫的配置方法和裝置。
【背景技術】
[0002]隨著網絡的發展，信息呈現爆炸性增長，人類的數據達到前所未有的規模，這些超大規模的數據存儲和管理已經成為一大挑戰。基於DHT (Distributed Hash Table)技術的P2P (Pear to Pear)存儲系統擁有很高的擴展性，支持大規模的數據存儲，可以較好地應對這一挑戰，這種存儲系統的底層存儲引擎一般是Key-Value資料庫，以下簡稱K-V資料庫，即以鍵值對形式進行數據存儲和訪問的非關係型資料庫。其通常的數據訪問操作有插入，查找，刪除，數據訪問形式一般如下:put (key, &value), get (key, &value), delete(key),其中key為數據的唯一標識,value即為數據內容。下文中put, get, delete分別對應插入，查找和刪除操作。
[0003]變長Hash K-V資料庫是一種常見的哈希資料庫，這種資料庫可以存儲變長的Key和Value，其基本原理是通過哈希算法確定每個Key和Value的存儲位置，當遇到Hash衝突時，使用特定的數據結構和二叉樹算法來解決。其邏輯結構如圖1所示，圖1中，Hash K-V資料庫從邏輯上分為四個部分，分別為:Bucket Array:即Hash桶,其大小為Hash空間的大小，其中存儲的內容為每個鍵值對(Key Value pair)所對應的在存儲介質的位置；Key:即每個鍵值對的鍵，存儲key的值；Value:即每個鍵值對的值，存儲value的值；Ptr:即當Hash衝突發生時，存儲相同Hash值的下一個鍵值對的位置(或偏移量)；以上部件構成了Hash K-V資料庫的通用結構。
[0004]由於使用了哈希算法，根據哈希算法的固有特性，不同的輸入得到的哈希值可能相等，這種不定長Hash K-V資料庫在性能設計上的關鍵在於哈希衝突的處理方式。由於該資料庫採用二叉樹來解決衝突的Key-Value對，當數據量過大時，樹的深度會較大,每次需要讀取、更新葉子節點上的Key-Value時就需要在磁碟上隨機讀取整個二叉樹上的一些節點，造成了性能抖動過大，形成性能長尾，性能在數據量較大壓力較大時會出現急劇下降的情況。
【發明內容】
[0005]本發明實施例所要解決的技術問題在於，提供一種哈希資料庫的配置方法和裝置。可解決現有哈希資料庫的訪問效率低的不足。
[0006]為了解決上述技術問題，本發明提供了一種哈希資料庫的配置方法，包括:
[0007]在磁碟上開闢索引區和數據區，其中，所述索引區由p個大小相等的磁碟頁面組成；
[0008]接收到Key-Value對的分配請求,將所述Key-Value對中m個Key分配至所述索引區的磁碟頁面中，且將所述Key-Value對中的n個Value分配至所述數據區中，m、n和p均為大於I的整數。[0009]在第一種可能的實現方式中，所述將所述Key-Value對中m個Key分配至所述索引區的磁碟頁面中的步驟包括:
[0010]從m個Key中選取一個待分配Key進行哈希運算得到哈希值；
[0011]根據所述哈希值和磁碟頁面的數量p進行求模得到落入的磁碟頁面的序號；
[0012]將所述待分配Key存儲至所述序號對應的磁碟頁面。
[0013]結合第一方面的第一種可能的實現方式，在第二種可能的實現方式中，還包括:
[0014]在所述磁碟上開闢擴展區，其中，所述擴展區由q個大小相等的擴展頁面組成，q為大於I的整數；
[0015]若所述索引區中的磁碟頁面發生溢出時，將溢出的Key存儲至所述擴展頁面中。
[0016]結合第一方面的第二種可能的實現方式，在第三種可能的實現方式中，所述將待分配Key分配至所述序號對應的磁碟頁面的步驟包括:
[0017]若所述序號對應的磁碟頁面的剩餘容量小於所述待分配Key的長度；
[0018]在所述擴展區中查詢其剩餘容量大於所述待分配Key長度的擴展頁面；
[0019]將所述待分配Key存儲至所述擴展頁面中。
[0020]結合第一方面的第三種可能的實現方式，在第四種可能的實現方式中，還包括:
[0021]採用Bitmap技術管理所述擴展區中q個擴展頁面的分配和回收。
[0022]結合第一方面的第四種可能的實現方式，在第五種可能的實現方式中，還包括:
[0023]將哈希值相同的磁碟頁面及擴展頁面組成鍊表，其中磁碟頁面位於所述鍊表的頭部。
[0024]結合第一方面的第五種可能的實現方式，在第六種可能的實現方式中，還包括:
[0025]在所述磁碟開闢備份區，並將所述索引區和所述擴展區中的數據的副本拷貝至所述備份區，其中，所述備份區和所述索引區及擴展區不相鄰。
[0026]本發明第二方面提供了一種哈希資料庫的配置裝置，包括:
[0027]開闢模塊，用於在磁碟上開闢索引區和數據區，其中，所述索引區由p個大小相等的磁碟頁面組成；
[0028]分配模塊,用於接收到Key-Value對的分配請求,將所述Key-Value對中m個Key分配至所述索引區的磁碟頁面中，且將所述Key-Value對中的n個Value分配至所述數據區中，m、n和p均為大於I的整數。
[0029]在第一種可能的實現方式中，所述分配模塊包括:
[0030]計算單元,用於從m個Key中選取一個待分配Key進行哈希運算得到哈希值；
[0031]求模單元，用於根據所述哈希值和磁碟頁面的數量p進行求模得到落入的磁碟頁面的序號；
[0032]分配單元，用於將所述待分配Key存儲至所述序號對應的磁碟頁面。
[0033]結合第二方面的第一種可能的實現方式，在第二種可能的實現方式中，還包括:
[0034]溢出控制模塊，用於在所述磁碟上開闢擴展區，其中，所述擴展區由q個大小相等的擴展頁面組成，q為大於I的整數；若所述索引區中的磁碟頁面發生溢出時，將溢出的Key存儲至所述擴展頁面中。
[0035]結合第二方面的第二種可能的實現方式，在第三種可能的實現方式中，所述分配單元用於若所述序號對應的磁碟頁面的剩餘容量小於所述待分配Key的長度；[0036]在所述擴展區中查詢其剩餘容量大於所述待分配Key長度的擴展頁面；
[0037]將所述待分配Key存儲至所述擴展頁面中。
[0038]結合第二方面得第三種可能的實現方式，在第四種可能的實現方式中，還包括:
[0039]管理模塊，用於採用Bitmap技術管理所述擴展區中q個擴展頁面的分配和回收。
[0040]結合第二方面的第四種可能的實現方式，在第五種可能的實現方式中，還包括:
[0041]生成模塊，用於將哈希值相同的磁碟頁面及擴展頁面組成鍊表，其中磁碟頁面位於所述鍊表的頭部。
[0042]結合第二方面的第五種可能的實現方式，在第六種可能的實現方式中，還包括:
[0043]備份模塊，用於在所述磁碟開闢備份區，並將所述索引區和所述擴展區中的數據的副本拷貝至所述備份區，其中，所述備份區和所述索引區及擴展區不相鄰。
[0044]實施本發明，具有如下有益效果:
[0045]通過將哈希資料庫的Key-Value對中的Key和Value進行分離，分別存儲至磁碟上開闢的索引區和數據區，在接收到對哈希資料庫的操作請求時，避免產生大量的磁碟IO操作，在Key-Value對的數量較大時，磁碟IO操作的次數穩定，提高了哈希資料庫的操作效率。
【專利附圖】
【附圖說明】
[0046]為了更清楚地說明本發明實施例或現有技術中的技術方案，下面將對實施例或現有技術描述中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附圖僅僅是本發明的一些實施例，對於本領域普通技術人員來講，在不付出創造性勞動的前提下，還可以根據這些附圖獲得其他的附圖。
[0047]圖1是現有技術中哈希資料庫的結構示意圖；
[0048]圖2是本發明第一實施例的一種哈希資料庫的配置方法的流程示意圖；
[0049]圖3是本發明第二實施例的一種哈希資料庫的配置方法的流程示意圖；
[0050]圖4本發明實施例的磁碟及哈希資料庫的空間布局示意圖；
[0051]圖5是本發明第一實施例的一種哈希資料庫的配置裝置的結構示意圖；
[0052]圖6是本發明第二實施例的一種哈希資料庫的配置裝置的結構示意圖；
[0053]圖7是圖6中分配模塊的結構示意圖；
[0054]圖8是本發明第三實施例的一種哈希資料庫的配置裝置的結構示意圖。
【具體實施方式】
[0055]下面將結合本發明實施例中的附圖，對本發明實施例中的技術方案進行清楚、完整地描述，顯然，所描述的實施例僅僅是本發明一部分實施例，而不是全部的實施例。基於本發明中的實施例，本領域普通技術人員在沒有作出創造性勞動前提下所獲得的所有其他實施例，都屬於本發明保護的範圍。
[0056]參見圖2，為本發明第一實施例的一種哈希資料庫的配置方法的流程示意圖，在本實施例中，所述方法包括:
[0057]S101、在磁碟上開闢索引區和數據區，其中，所述索引區由p個大小相等的磁碟頁面組成。[0058]具體的，磁碟上的空閒空間處開闢索引區和數據區，索引區用於存儲哈希資料庫的Key-Value對中的Key,數據區用於存儲哈希資料庫的Key-Value對中的Value,Key-Value對中的Key和Value分離，其中，索引區由p個大小相等的磁碟頁面組成,每個磁碟頁面存儲哈希值相同的Key。例如，每個磁碟頁面的大小均為8K字節
[0059]S102、接收到Key-Value對的分配請求,將所述Key-Value對中的m個Key分配至所述索引區的磁碟頁面中，且將所述Key-Value對中的m個Value分配至所述數據區中
[0060]具體的，Key-Value對為哈希資料庫中預先配置的，Key與Value是多對一的關係，即至少一個Key與一個Value存在映射關係，Key-Value對中由m個Key和n個Value組成，m > n,將m個Key分配到索引區的p個磁碟頁面中，同時將n個Value分配到數據區中。
[0061]每個Key個長度為固定值，假設Key的長度均為IK字節，每個磁碟頁面的容量為8K字節，則索引區的每個磁碟頁面中可存儲8K/1K=8個Key，考慮到Key的描述信息需要佔用一定的存儲空間，實際上每個磁碟頁面可存儲的Key的數量為7個;m個Key分配到p個磁碟頁面中，具體分配方法為=Key經過哈希運算後求模落在某一個磁碟頁面中，如果哈希算法均勻性好，那麼每個Key落入到各個磁碟頁面的概率是相同的，概率都為1/p，指定某個磁碟頁面為空的概率為(1-1/p) ~m，空的磁碟頁面(即Key的數量為0的磁碟頁面)的數量為p* (1-1/p) ~m,當p, n的值足夠大時,空的磁碟頁面的數量約等於n* (1/e) ' (m/n)；指定某個磁碟頁面有k個Key的概率為C(m, k)*(l/p) ~k*(l_l/p) ~ (m-k) ,C(m, k)表示求組合數。假設Key的數量m=8000000,磁碟頁面的數量p=2621431,計算結果圖表1所示
[0062]
【權利要求】
1.一種哈希資料庫的配置方法，其特徵在於，包括: 在磁碟上開闢索引區和數據區，其中，所述索引區由P個大小相等的磁碟頁面組成； 接收到鍵-值Key-Value對的分配請求,將所述Key-Value對中m個Key分配至所述索引區的磁碟頁面中，且將所述Key-Value對中的n個Value分配至所述數據區中，m、n和P均為大於I的整數。
2.如權利要求1所述的方法，其特徵在於，所述將所述Key-Value對中m個Key分配至所述索引區的磁碟頁面中的步驟包括: 從m個Key中選取一個待分配Key進行哈希運算得到哈希值； 根據所述哈希值和磁碟頁面的數量P進行求模得到落入的磁碟頁面的序號； 將所述待分配Key存儲至所述序號對應的磁碟頁面。
3.如權利要求2所述的方法，其特徵在於，還包括: 在所述磁碟上開闢擴展區，其中，所述擴展區由q個大小相等的擴展頁面組成，q為大於I的整數； 若所述索引區中的磁碟頁面發生溢出時，將溢出的Key存儲至所述擴展頁面中。
4.如權利要求3所述的方法，其特徵在於，所述將待分配Key分配至所述序號對應的磁碟頁面的步驟包括: 若所述序號對應的磁碟頁面的剩餘容量小於所述待分配Key的長度； 在所述擴展區中查詢其剩餘容量大於所述待分配Key長度的擴展頁面； 將所述待分配Key存儲至所述擴展頁面中。
5.如權利要求4所述的方法，其特徵在於，還包括: 採用Bitmap技術管理所述擴展區中q個擴展頁面的分配和回收。
6.如權利要求5所述的方法，其特徵在於，還包括: 將哈希值相同的磁碟頁面及擴展頁面組成鍊表，其中磁碟頁面位於所述鍊表的頭部。
7.如權利要求6所述的方法，其特徵在於，還包括: 在所述磁碟開闢備份區，並將所述索引區和所述擴展區中的數據的副本拷貝至所述備份區，其中，所述備份區和所述索引區及擴展區不相鄰。
8.一種哈希資料庫的配置裝置，其特徵在於，包括: 開闢模塊，用於在磁碟上開闢索引區和數據區，其中，所述索引區由P個大小相等的磁碟頁面組成； 分配模塊，用於接收到Key-Value對的分配請求,將所述Key-Value對中m個Key分配至所述索引區的磁碟頁面中，且將所述Key-Value對中的n個Value分配至所述數據區中，m、n和p均為大於I的整數。
9.如權利要求8所述的裝置，其特徵在於，所述分配模塊包括: 計算單元，用於從m個Key中選取一個待分配Key進行哈希運算得到哈希值； 求模單元，用於根據所述哈希值和磁碟頁面的數量p進行求模得到落入的磁碟頁面的序號； 分配單元，用於將所述待分配Key存儲至所述序號對應的磁碟頁面。
10.如權利要求9所述的裝置，其特徵在於，還包括: 溢出控制模塊，用於在所述磁碟上開闢擴展區，其中，所述擴展區由q個大小相等的擴展頁面組成，q為大於I的整數；若所述索引區中的磁碟頁面發生溢出時，將溢出的Key存儲至所述擴展頁面中。
11.如權利要求10所述的裝置，其特徵在於，所述分配單元用於若所述序號對應的磁碟頁面的剩餘容量小於所述待分配Key的長度； 在所述擴展區中查詢其剩餘容量大於所述待分配Key長度的擴展頁面； 將所述待分配Key存儲至所述擴展頁面中。
12.如權利要求11所述的裝置，其特徵在於，還包括: 管理模塊，用於採用Bitmap技術管理所述擴展區中q個擴展頁面的分配和回收。
13.如權利要求12所述的裝置，其特徵在於，還包括: 生成模塊，用於將哈希值相同的磁碟頁面及擴展頁面組成鍊表，其中磁碟頁面位於所述鍊表的頭部。
14.如權利要求13所述的裝置，其特徵在於，還包括: 備份模塊，用於在所述磁碟開闢備份區，並將所述索引區和所述擴展區中的數據的副本拷貝至所述備份區，其中，所述備份區和所述索引區及擴展區不相鄰。
【文檔編號】G06F17/30GK103593477SQ201310627860
【公開日】2014年2月19日 申請日期:2013年11月29日 優先權日:2013年11月29日
【發明者】張雷, 鮑棟 申請人:華為技術有限公司