云計算系統(tǒng)中Key-Value數(shù)據(jù)管理研究

郭顯娥

（山西大同大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院,山西大同037009）

云計算系統(tǒng)中Key-Value數(shù)據(jù)管理研究

郭顯娥

（山西大同大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院,山西大同037009）

Key-Value數(shù)據(jù)庫是應(yīng)用于云環(huán)境下的典型云存儲系統(tǒng)，基于key-value數(shù)據(jù)模型的研究對大數(shù)據(jù)管理或稱云數(shù)據(jù)管理系統(tǒng)提出了新的需求與挑戰(zhàn)，成為人們關(guān)注的熱點。本文對key-value數(shù)據(jù)模型與數(shù)據(jù)讀寫方式作了簡單介紹，引入了key-value索引機制，重點討論了key-value查詢操作，給出了關(guān)于多維點查詢的通用算法。

key-value數(shù)據(jù)模型；索引機制；查詢操作

隨著大數(shù)據(jù)、云計算、互聯(lián)網(wǎng)技術(shù)的發(fā)展，以PB（1014 terabytes）或EB（100萬TB）級的大數(shù)據(jù)（包括結(jié)構(gòu)化的、半結(jié)構(gòu)化的和非結(jié)構(gòu)化的）應(yīng)運而生，體現(xiàn)在電子商務(wù)、計算機仿真、社交網(wǎng)絡(luò)、物聯(lián)網(wǎng)、移動服務(wù)等眾多領(lǐng)域。傳統(tǒng)的關(guān)系數(shù)據(jù)庫在數(shù)據(jù)存儲、索引和查詢處理等方面很難實現(xiàn)高效性、靈活性和可擴展性，取而代之的是非關(guān)系型的、分布式的數(shù)據(jù)存儲系統(tǒng)NoSQL。NoSQL數(shù)據(jù)庫典型產(chǎn)品有:基于Hadoop HDFS的HBas，Amazon公司的Dynamo，Google公司的BigTable等。

在NoSQL數(shù)據(jù)庫中，數(shù)據(jù)的存儲采用弱關(guān)系的數(shù)據(jù)模型，即key-value數(shù)據(jù)模型。關(guān)于keyvalue數(shù)據(jù)模型的NoSQL數(shù)據(jù)庫系統(tǒng)研究，與NoSQL相關(guān)的關(guān)系云系統(tǒng)和MapReduce框架的相關(guān)研究，已成為人們關(guān)注的熱點[1-5]。本文將介紹key-value的數(shù)據(jù)模型與數(shù)據(jù)的讀寫方式，索引和查詢功能等，重點討論key-value查詢操作，并給出簡單的算法。

1 Key-Value數(shù)據(jù)管理

Key-Value數(shù)據(jù)管理功能，包括：key-value數(shù)據(jù)存儲、數(shù)據(jù)讀寫方式、索引機制與查詢功能。

1.1 Key-Value數(shù)據(jù)存儲

Key-Value數(shù)據(jù)存儲可以理解為＜key,value＞二元健值對，即一個key對應(yīng)一個value值，其中key值和value值的數(shù)據(jù)類型不限，或許key值為一個文件名，而value取值可以是相應(yīng)的文件，也許key值為一張圖片，而value是圖片對應(yīng)的拍攝時間、地點與主題等，更簡單的例子是一個ID號（key值）與對應(yīng)的教師信息（value值），用表1來描述。

表1 Key-Value 鍵值對

表1不是簡單的二維表，而是key與value的映射關(guān)系。Key-Value數(shù)據(jù)模型是基于健值對的數(shù)據(jù)存儲模型，采用分布式Hash，實現(xiàn)從key至value上的映射。

1.2 讀寫方式

key-value數(shù)據(jù)庫數(shù)據(jù)的讀寫方式，采用面向磁盤的讀寫方式。如圖1所示。

圖1 面向磁盤的讀寫方式

其工作原理是，首先數(shù)據(jù)被寫入內(nèi)存中，系統(tǒng)返回寫入成功，當(dāng)內(nèi)存中數(shù)據(jù)量大時，會被批量寫入磁盤文件；其次，在讀取數(shù)據(jù)時，優(yōu)先訪問內(nèi)存，如果未得到需要的數(shù)據(jù)，則從磁盤文件讀取數(shù)據(jù)，當(dāng)返回錯誤信息時，則要調(diào)用日志進行數(shù)據(jù)恢復(fù)。這種磁盤讀寫方式要求數(shù)據(jù)庫進行定期的數(shù)據(jù)合并，將過期的冗余數(shù)據(jù)刪除。

1.3 索引機制

基于key-value的存儲模型，其索引機制采用的是hash索引和B-tree索引等。

hash索引是指把關(guān)鍵值key直接映射到內(nèi)存地址，實現(xiàn)快速查詢，用公式表示為：ID=H(key)（H是哈希函數(shù)）。常見的有鏈接桶hash，可擴展hash，線性hash等。

B-tree稱為多路搜索平衡樹，由根節(jié)點，分支節(jié)點和葉子節(jié)點構(gòu)成，通常將數(shù)據(jù)存放于leaf node，而任何一個leaf node的最短路徑的長度是相同的。由B-tree索引相繼研究出R-tree索引與B+-tree索引等。

1.4 查詢功能

key-value數(shù)據(jù)查詢分為簡單查詢和復(fù)雜查詢。復(fù)雜查詢留給應(yīng)用層實現(xiàn)，常用的是MapRe?duce框架；簡單查詢包括單點查詢和多維點查詢，下面詳細介紹這兩種查詢。

1.4.1 單點查詢

單點查詢是通過對DB的操作完成的，即數(shù)據(jù)的查詢會按照key值，查詢到相關(guān)的Key-Value節(jié)點，如果沒有查詢到Key-Value節(jié)點，則說明數(shù)據(jù)不存在，如果查詢到Key-Value節(jié)點，那么判斷Key-Value 節(jié)點的狀態(tài)（set∕get∕delete），如果是 delete，則說明節(jié)點被刪除，否則，返回value給查詢者。

為了提高數(shù)據(jù)的查詢效率，在內(nèi)存建一張hash表。當(dāng)存儲的數(shù)據(jù)非常多的時候，系統(tǒng)會根據(jù)配置文件中設(shè)計的閥值，進行一次rebuild的過程，re?build的過程結(jié)束后，會在內(nèi)存生成hash結(jié)構(gòu)。

rebuild過程主要分為三步：排序、截斷、建立hash表。主要的數(shù)據(jù)結(jié)構(gòu)如下：

在HashDB上Key-Value鏈表達到rebuild的閥值時，會觸發(fā)rebuild線程的開啟，具體的re?build的過程為：

Step1：拷貝當(dāng)前鏈表到temp指針下，同時記下這時的Key-Value鏈表的頭指針。

Step2：排序，在排序的過程中，去掉冗余的節(jié)點。排序采用一種快排的方式。

Step3：截斷：把排好序的鏈表，從中間截斷，新建一個HashDB，把較大的那個鏈表交給這個新建的HashDB管理。

Step4：建立hash表：把Key-Value鏈表的最大值和最小值填寫到管理這個Key-Value鏈表的HashDB中，把在rebuild過程中，所有新增的數(shù)據(jù)按照新的hash值加入到這兩個Key-Value鏈表中。

至此，一次rebuild過程結(jié)束，同時刪除原來的Key-Value鏈表。

1.4.2 多維點查詢

定義1:當(dāng)鍵有2個值時，稱為二維點，鍵有多個值時，稱為多維點，這里以d維點(d＞2)為例，記為：key=(v1,...,vd)，涉及到多維點的查詢叫做多維點查詢，d維點查詢記為Qd(key)。

關(guān)于多維點查詢算法的設(shè)計思路：

先將多維數(shù)據(jù)進行劃分（劃分方案決定查詢的效率），采用降維的方法，逐維劃分；其次，根據(jù)劃分方案，將所有數(shù)據(jù)劃分為互不相交的立方體簇群，對于每一個簇群建立相應(yīng)的B-tree或R-tree索引；最后，將第二步產(chǎn)生的各個B-tree或R-tree合并，生成大的B-tree或R-tree樹進行查詢。

設(shè)B-tree上節(jié)點最小多維區(qū)域為：{[k1,m1],…,[kd,md]}，（i={1，2…,d}，ki≤vi≤mi）；Ni：表示包含key索引節(jié)點的立方體簇集；C：以key為中心、R為邊長的最大立方體；Ci:表示在i維度上劃分的子簇集。

多維點查詢算法描述為：

(4)for i=1 to d do∕∕（d是維數(shù)）將立方體C不斷分割

(5) 將C在第i個維度上根據(jù)ki和mi劃分成C0，C1和C2;∕∕C被Ni在各個維度上連續(xù)地劃分成若干子立方體簇群,搜索的范圍將從不同的維度進行分割并發(fā)出響應(yīng)到鄰居，即分割結(jié)束后其相鄰的范圍再進行空間分割。如果在該小立方體內(nèi)無法找到要查詢的范圍信息，則會發(fā)送請求到其相鄰的立方體，當(dāng)相鄰立方體收到請求后，會調(diào)用同樣的算法對內(nèi)部空間進行分割并索引，直到找到要查詢的范圍內(nèi)的節(jié)點并最終返回給客戶端。

多維點查詢的應(yīng)用，如基于地理位置的服務(wù)：輸入對象的經(jīng)度、緯度、時間就可以進行查詢；如圖片的共享服務(wù)；如網(wǎng)購服務(wù)等。

2 進一步的研究

為了擴大key-value數(shù)據(jù)存儲的應(yīng)用，增強key-value存儲數(shù)據(jù)庫系統(tǒng)的支持功能，例如海量數(shù)據(jù)的復(fù)雜查詢，分布式事務(wù)處理能力等。研究者需要進一步地關(guān)注以下問題：

（1）根據(jù)用戶的不同需求，結(jié)合云環(huán)境的特性，需要改進key哈希的數(shù)據(jù)分布模式，使其提供靈活的、可優(yōu)化的海量數(shù)據(jù)查詢定義模型，實現(xiàn)各種復(fù)雜查詢和數(shù)據(jù)分析。

（2）在云計算環(huán)境下，對海量數(shù)據(jù)的索引機制需要進一步思考。特別是在構(gòu)建全局索引，基于線性化技術(shù)的索引與基于HugeTable的索引等方面，需要新的研究成果。

（3）為了有效地支持大數(shù)據(jù)管理與查詢處理，將面向批處理的系統(tǒng)（基于MapReduce框架）和面向服務(wù)的系統(tǒng)（NoSQL數(shù)據(jù)庫）相結(jié)合的應(yīng)用問題，如Hadoop和Hbase相結(jié)合、Hadoop和PNUTS相結(jié)合；云環(huán)境下數(shù)據(jù)管理的數(shù)據(jù)安全問題；支持數(shù)據(jù)管理的支持系統(tǒng)的能耗問題等，都是目前研究的熱點。

3 結(jié)束語

隨著數(shù)據(jù)量呈指數(shù)級的增長，大數(shù)據(jù)、云計算、互聯(lián)網(wǎng)時代的到來，云計算得到了廣泛的應(yīng)用，Key-Value數(shù)據(jù)庫是應(yīng)用于云環(huán)境下的典型云存儲系統(tǒng)，被業(yè)界廣泛關(guān)注。本文利用較短的篇幅介紹了Key-Value的數(shù)據(jù)模型與數(shù)據(jù)的磁盤讀寫方式，引入了Key-Value的Hash索引與B-tree索引，較詳細地討論了Key-Value的單點查詢與多維點查詢功能，最后給出了基于Key-Value數(shù)據(jù)庫的進一步研究課題。

[1]申德榮,于戈.支持大數(shù)據(jù)管理的NoSQL系統(tǒng)研究綜述[J].軟件學(xué)報,2013,24(8):1786-1803.

[2]張峰.云計算應(yīng)用服務(wù)模式探討 [J].信息技術(shù)與信息化，2012（2）:81-83.

[3]金柏統(tǒng)，王振宇，許文君，等.基于云計算的數(shù)據(jù)管理[J].電子制作，2014（1）：127.

[4]孟燕，郭冬梅.云計算及基數(shù)據(jù)存儲與管理技術(shù)研究[J].信息技術(shù)與信息化，2012（7）：73-76.

[5]王珊,薩師煊.數(shù)據(jù)庫系統(tǒng)概論[M].4版,北京:高等教育出版社,2006.

Key-Value Data Management in Cloud Computing System

GUO Xian-e
（School of Mathematics and Computer Science,Shanxi Datong University,Datong Shanxi,037009)

Key-Value database is a typical cloud storage system applied within Cloud Computing environment.Based on re?searches on Key-Value data model,the new demands and challenges emerged for big data management,or Cloud Data Management be?came the new focal point of this area.This article started with a brief introduction on Key-Value data modeling and data input and out?put methods.Then with the combination of Key-Value index mechanism,the author emphasized on Key-Value indexing operation,pro?viding a general algorithm on Multidimensional Query.

Key-Value data model;index mechanism;query operation

TP311

A

1674-0874(2015)05-0001-03

2015-02-20

山西大同大學(xué)教研項目[X JY-2013207]；山西大同大學(xué)校級特色專業(yè)建設(shè)項目[X TS2004-01]）；山西省高等學(xué)校大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練項目[2 015344]

郭顯娥(1964-)，女，山西渾源人，碩士，教授，研究方向：數(shù)據(jù)挖掘。

〔責(zé)任編輯 高海〕