• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

    2015-11-01 23:25:04郭顯娥
    關(guān)鍵詞:山西大同鏈表磁盤

    郭顯娥

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

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

    郭顯娥

    (山西大同大學數(shù)學與計算機科學學院,山西大同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)返回寫入成功,當內(nèi)存中數(shù)據(jù)量大時,會被批量寫入磁盤文件;其次,在讀取數(shù)據(jù)時,優(yōu)先訪問內(nèi)存,如果未得到需要的數(shù)據(jù),則從磁盤文件讀取數(shù)據(jù),當返回錯誤信息時,則要調(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表。當存儲的數(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:拷貝當前鏈表到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:當鍵有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ā)送請求到其相鄰的立方體,當相鄰立方體收到請求后,會調(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].軟件學報,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

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

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

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

    猜你喜歡
    山西大同鏈表磁盤
    山西大同 黃花菜豐收在望
    《山西大同大學學報(自然科學版)》征稿簡則
    山西大同大學采礦研究所簡介
    山西大同邀客共賞“小黃花大產(chǎn)業(yè)”
    解決Windows磁盤簽名沖突
    電腦愛好者(2019年2期)2019-10-30 03:45:31
    基于二進制鏈表的粗糙集屬性約簡
    跟麥咭學編程
    修改磁盤屬性
    基于鏈表多分支路徑樹的云存儲數(shù)據(jù)完整性驗證機制
    磁盤組群組及iSCSI Target設(shè)置
    黄梅县| 太原市| 红桥区| 尤溪县| 青州市| 沅陵县| 广元市| 德庆县| 陕西省| 青河县| 长宁县| 巧家县| 澜沧| 天镇县| 遵化市| 新疆| 桦甸市| 马公市| 汉沽区| 亚东县| 巴中市| 岑溪市| 万年县| 丹寨县| 平顶山市| 邵阳县| 古田县| 邹平县| 海城市| 阜康市| 宝丰县| 乌拉特中旗| 四会市| 同仁县| 嘉祥县| 共和县| 常山县| 松潘县| 宁武县| 龙口市| 万源市|