郭顯娥

（山西大同大學數學與計算機科學學院,山西大同037009）

云計算系統中Key-Value數據管理研究

郭顯娥

（山西大同大學數學與計算機科學學院,山西大同037009）

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

key-value數據模型；索引機制；查詢操作

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

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

1 Key-Value數據管理

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

1.1 Key-Value數據存儲

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

表1 Key-Value 鍵值對

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

1.2 讀寫方式

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

圖1 面向磁盤的讀寫方式

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

1.3 索引機制

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

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

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

1.4 查詢功能

key-value數據查詢分為簡單查詢和復雜查詢。復雜查詢留給應用層實現，常用的是MapRe?duce框架；簡單查詢包括單點查詢和多維點查詢，下面詳細介紹這兩種查詢。

1.4.1 單點查詢

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

為了提高數據的查詢效率，在內存建一張hash表。當存儲的數據非常多的時候，系統會根據配置文件中設計的閥值，進行一次rebuild的過程，re?build的過程結束后，會在內存生成hash結構。

rebuild過程主要分為三步：排序、截斷、建立hash表。主要的數據結構如下：

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

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

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

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

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

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

1.4.2 多維點查詢

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

關于多維點查詢算法的設計思路：

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

設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是維數）將立方體C不斷分割

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

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

2 進一步的研究

為了擴大key-value數據存儲的應用，增強key-value存儲數據庫系統的支持功能，例如海量數據的復雜查詢，分布式事務處理能力等。研究者需要進一步地關注以下問題：

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

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

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

3 結束語

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

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

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

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

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

[5]王珊,薩師煊.數據庫系統概論[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

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

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

〔責任編輯 高?！?/p>