行列混合存儲數(shù)據(jù)庫的數(shù)據(jù)分布自適應(yīng)優(yōu)化算法

行列混合存儲瞄庫的數(shù)據(jù)分布自適應(yīng)優(yōu)化算法王民川;趙冰;黃繼海【摘要】隨著數(shù)據(jù)量和數(shù)據(jù)類型的逐漸增加，用戶對數(shù)據(jù)存儲性能的要求和整體需求越來越高.當前數(shù)據(jù)分布算法因為受到成本及可擴展性的約束，無法達到用戶對存儲的要求.為此，提出一種新的行列混合存儲數(shù)據(jù)庫的數(shù)據(jù)分布自適應(yīng)優(yōu)化算法，給出數(shù)據(jù)分片、數(shù)據(jù)訪問頻率矩陣、拓撲結(jié)構(gòu)和最小支撐樹的定義，將總成本最小作為依據(jù)，判斷數(shù)據(jù)是否冗余分布，獲取行列混合存儲數(shù)據(jù)庫的利益函數(shù).找到一個使利益最大化的數(shù)據(jù)分布方案，通過迭代求取該問題的解.輸入相關(guān)參數(shù)，輸出的結(jié)果即為數(shù)據(jù)分布結(jié)果.實驗結(jié)果表明,所提算法讀寫能力和均衡性均較強.％Withthegradualincreaseintheamountofdataanddatatypes,userrequirementsfordatastorageperformanceandoveralldemandmoreandmorehigh,thecurrentdatadistributionalgorithmbecauseofthecostandscalabilityconstraints,cannotmeettheuserrequirementsforstorage.Forthis,anewadaptivedistributionoptimizationalgorithmranksmixedstoragedatabasewereputforward,definedatasliceanddataaccessfrequencymatrix,topologyandtheminimumspanningtree,theminimumtotalcostasthebasisforjudgingwhetherthedataredundancydistribution,accesslistofinterestfunctionmixedstoragedatabase.Tofindadatadistributionschemethatmaximizesthebenefits,thesolutionoftheproblemisobtainedbyiteration.Entertherelevantparameters,theoutputistheresultofthedatadistribution.Theexperimentalresultsshowthattheproposedalgorithmhasstrongabilityofreadingandwriting.【期刊名稱】《科學(xué)技術(shù)與工程》【年(卷)，期】2017(017)027【總頁數(shù)】6頁(P232-237)【關(guān)鍵詞】行列;存儲數(shù)據(jù)庫;數(shù)據(jù)分布;自適應(yīng);優(yōu)化【作者】王民川;趙冰;黃繼海【作者單位】中州大學(xué)，鄭州450000;中州大學(xué)，鄭州450000;中州大學(xué)，鄭州450000【正文語種】中文【中圖分類】TP301.6隨著網(wǎng)絡(luò)的迅猛發(fā)展，用戶量快速增長，對硬件資源及架構(gòu)提出了很高的要求，行列混合存儲數(shù)據(jù)庫應(yīng)運而生［1,2］。當前首先需要解決的存儲問題就是針對海量數(shù)據(jù)，如何有效實現(xiàn)數(shù)據(jù)分布，使得數(shù)據(jù)被高效地訪問，提高讀寫性能、可擴展性及可靠性［3—5］。近年來，在網(wǎng)絡(luò)應(yīng)用的驅(qū)動下，行列混合存儲數(shù)據(jù)庫發(fā)展迅速，有關(guān)數(shù)據(jù)分布的研究越來越多。文獻［6］利用規(guī)定的元數(shù)據(jù)服務(wù)器對數(shù)據(jù)庫中數(shù)據(jù)的分布位置進行判斷，把數(shù)據(jù)和分布位置的映射關(guān)系存儲至元數(shù)據(jù)中，通過元數(shù)據(jù)服務(wù)器進行整體調(diào)控。該方法能夠有效依據(jù)需求對數(shù)據(jù)分布進行管理，但因為整個存儲數(shù)據(jù)庫均使用同一份元數(shù)據(jù)，所以容易出現(xiàn)系統(tǒng)瓶頸，增加單點故障的發(fā)生率。文獻［7］通過確定性分布算法確定數(shù)據(jù)存儲位置，實現(xiàn)數(shù)據(jù)分布。在輸入不變的情況下，數(shù)據(jù)庫中任意節(jié)點均可通過某種方法獲取相同的數(shù)據(jù)存儲位置。該方法降低了管理方面的需求，充分利用節(jié)點資源，然而均衡性較差。文獻［8］提出一種基于哈希映射的數(shù)據(jù)分布算法，通過哈希形式將存儲節(jié)點映射至一個哈希圓環(huán)上，當數(shù)據(jù)出現(xiàn)時，利用哈希形式將其映射至同一圓環(huán)上，同時按照順時針的方向?qū)⑵溆成渲梁推渥罱拇鎯?jié)點上。該算法實現(xiàn)過程簡單，但寫性能不佳。針對上述算法的弊端，提出一種新的行列混合存儲數(shù)據(jù)庫的數(shù)據(jù)分布自適應(yīng)優(yōu)化算法。實驗結(jié)果表明，所提算法讀寫能力和均衡性均較強。行列混合存儲數(shù)據(jù)庫的數(shù)據(jù)分布方式主要包括無冗余分配與冗余分配兩種，二者均存在自身的優(yōu)缺點［9］，本節(jié)結(jié)合二者的優(yōu)點，提出一種有效的數(shù)據(jù)分布自適應(yīng)優(yōu)化算法。為了分析該問題，首先需給出幾個定義。定義1數(shù)據(jù)分片。數(shù)據(jù)分片即把行列混合存儲數(shù)據(jù)庫的全局關(guān)系分割為對應(yīng)的邏輯片段，其為存儲數(shù)據(jù)的基本單位［10,11］。假設(shè)事務(wù)Tk對分片F(xiàn)i進行讀和更新涉及的單元數(shù)據(jù)量分別用rki、uki進行描述，事務(wù)集合用T={T1,T2,...,Tz}進行描述，分片集合用F={F1,F2,...,Fm}進行描述，即可建立zxm的查詢矩陣R與更新矩陣U:定義2數(shù)據(jù)訪問頻率矩陣。假設(shè)兩個存取頻率矩陣用RM和UM進行描述，其是全部事務(wù)讀和更新頻率的體現(xiàn)［12］,公式如下：定義3拓撲結(jié)構(gòu)。在行列混合存儲數(shù)據(jù)庫中，用twk,j描述從事務(wù)Tk所處站點發(fā)送一個單元數(shù)據(jù)到站點Vj的通信代價，用vwi,j描述從站點Vi發(fā)送一個單元數(shù)據(jù)至站點Vj的通信代價。假設(shè)行列混合存儲數(shù)據(jù)庫的站點集合為V={V1,V2,...,Vn},則可建立nxn的通信代價矩陣CT:定義4最小支撐樹MST。針對某分片F(xiàn)i,依據(jù)其更新網(wǎng)絡(luò)圖可建立該分片的最小支撐樹MST(Fk)，使得所有站點在有數(shù)據(jù)更新的情況下，其最小更新傳播路徑均為MST(Fk)［13］。利用更新傳輸方式，針對各分片，可構(gòu)建以下映射：m：ZxVxV—{0,1}，也就是：針對既定分片及其分布狀態(tài)，所有分片均需和其復(fù)本保持一致［14］,則更新一個單元數(shù)據(jù)的通信代價如下：針對某分片F(xiàn)i,若沒有冗余分布在站點Vj上，則全部事務(wù)Tk對Vj站點上已分布的分片F(xiàn)i的訪問總代價COST(yij)為COST(yij)=ukixdkjxtwkj)式(8)中，a用于描述更新相對于檢索的成本比例；dkj代表Tk是否發(fā)自站點Vj,如果其值為0代表Tk發(fā)自站點Vj,也就是Tk和Vj之間無距離，否則二者之間有距離。將總代價最小作為依據(jù)，判斷數(shù)據(jù)是否冗余分布，獲取行列混合存儲數(shù)據(jù)庫的利益函數(shù)[15]:RCOST(yij)=(-dkj)vwlj]式(9)中，wlj用于描述分片F(xiàn)i在無冗余分布狀態(tài)下，站點Vi和Vj之間傳輸一個單元數(shù)據(jù)所需的代價；~dkj代表dkj取反。行列混合存儲數(shù)據(jù)庫的數(shù)據(jù)分布自適應(yīng)優(yōu)化算法就是找到一個使利益最大化的數(shù)據(jù)分布方案[16,17]，通過迭代求取該問題的解，詳細實現(xiàn)過程如下：輸入：R、U、RM、UM、CT。輸出：分片分布矩陣。確定初始分布矩陣Y0,將其中所有元素yij置0[18,19];針對各站點Vj,如果存在事務(wù)Tk，則將和Tk有關(guān)的全部分片F(xiàn)i分布至站點Vj,令yij=1。針對初始分布矩陣Y0,求出事物總成本：針對各元素yij,如果yij=1，通過式(8)求出在無冗余分布的狀態(tài)下，全部應(yīng)用Tk的訪問總成本COST(yij);如果yij=0，令COST(yij)=,建立成本矩陣C。依據(jù)成本矩陣C建立無冗余分布矩陣Y1。⑷針對Y1中各yij進行循環(huán)，若yij=0，同時和Y0相應(yīng)的yij=1時，通過式(9)求出消費收益RCOST(yij)。如果RCOST(yij)金，則yij=1,如果RCOST(yij)>￡,貝Uyij=o。其中，￡代表自定義常量［20］。最終矩陣Y1中的值yij代表分片分步的最終狀態(tài)，yij=1代表分片F(xiàn)i分布于站點Vj,yij=0代表分片F(xiàn)i不分布于站點Vj。行列混合存儲數(shù)據(jù)庫工作節(jié)點分別由15臺服務(wù)器構(gòu)成，主節(jié)點和從節(jié)點的配置情況分別用表1和表2進行描述。利用隨機數(shù)發(fā)生器形成1200個不同類型的數(shù)據(jù)，構(gòu)成行列混合存儲數(shù)據(jù)庫，利用數(shù)據(jù)分布算法將其分布至上述15個節(jié)點中。圖1描述的是當節(jié)點為5個、15個時，本文算法數(shù)據(jù)分布情況。分析圖1可以看出，在節(jié)點為5個時，通過本文算法分布的數(shù)據(jù)量和理想值有一定的差異，但差異不大，而在節(jié)點為15個的情況下，通過本文算法分布的數(shù)據(jù)量和理想值非常接近，說明本文算法分布效果好。為了驗證本文算法是否能夠有效處理過載節(jié)點，將哈希算法和遺傳算法作為對比。在進行實驗的過程中，令20個客戶端對15個行列混合存儲數(shù)據(jù)庫存儲節(jié)點中的對象發(fā)起請求。通過采集器對節(jié)點負載信息進行采集，每隔5s采集一次節(jié)點信息。圖2描述的是本文算法、哈希算法和遺傳算法對請求的平均響應(yīng)時間比較結(jié)果。分析圖2可知，哈希算法和遺傳算法的響應(yīng)時間波動相對較大，這主要是因為出現(xiàn)待分布數(shù)據(jù)時，這兩種算法的請求隊列不均，導(dǎo)致響應(yīng)時間時高時低，令平均響應(yīng)時間出現(xiàn)較大波動。而本文算法能夠有效處理待分布數(shù)據(jù)，可在很大程度上保證平均響應(yīng)時間的穩(wěn)定性。為了驗證本文算法的讀寫性能，將哈希算法和遺傳算法作為對比，將吞吐率作為衡量讀寫性能的指標進行測試，圖3描述的是三種算法吞吐率比較結(jié)果。分析圖3可以看出，在進行讀操作和寫操作時，本文算法的吞吐率分別為300op/s和380op/s左右，而在相同測試條件下，哈希算法和遺傳算法的吞吐率明顯低于本文算法，說明本文算法讀寫性能強。針對上述實驗，本節(jié)對帶寬與平均響應(yīng)時間進行統(tǒng)計，結(jié)果用表3進行描述。分析表3可知，經(jīng)本文算法處理后系統(tǒng)帶寬明顯高于哈希算法和遺傳算法，而響應(yīng)時間明顯低于哈希算法和遺傳算法。除此之外，為了進一步驗證本文算法的讀寫性能，本節(jié)還對不同并發(fā)度下隨機讀寫性能的吞吐率進行了測試，三種算法讀寫性能測試結(jié)果用圖4進行描述。圖4中的Worker數(shù)代表可配置參數(shù)，主要取決于請求的并發(fā)度有關(guān)，Worker數(shù)量越多說明并發(fā)請求越多。分析圖4可以看出，在Worker數(shù)逐漸上升的情況下，本文算法的吞吐率較哈希算法和遺傳算法均高出10%以上，說明本文算法讀寫性能高。一種性能高的數(shù)據(jù)分布算法需保證數(shù)據(jù)分布的均衡性，因為均衡的數(shù)據(jù)分布能夠避免部分節(jié)點因承載過重導(dǎo)致性能達到瓶頸的現(xiàn)象，提高節(jié)點使用周期。本節(jié)對本文算法、哈希算法和遺傳算法數(shù)據(jù)分布均衡性進行比較，表4和表5分別描述的是三種算法針對行列混合存儲數(shù)據(jù)庫中數(shù)據(jù)分布量和空間使用率最大值、最小值、平均值、標準差以及均衡度比較結(jié)果。分析表4和表5可以看出，采用本文算法后各節(jié)點數(shù)量在92~123個范圍內(nèi)，標準差是6.6，明顯低于哈希算法和遺傳算法，而均衡度為0.164，明顯高于哈希算法和遺傳算法。針對數(shù)據(jù)分布，采用本文算法的空間使用率明顯高于其它兩種算法，且均衡度也更高，說明本文算法均衡性較強。本文提出一種新的行列混合存儲數(shù)據(jù)庫的數(shù)據(jù)分布自適應(yīng)優(yōu)化算法，將總成本最小作為依據(jù)判斷數(shù)據(jù)是否冗余分布，獲取行列混合存儲數(shù)據(jù)庫的利益函數(shù)。找到一個使利益最大化的數(shù)據(jù)分布方案，通過迭代求取該問題的解，實現(xiàn)數(shù)據(jù)分布。實驗結(jié)果表明，所提算法讀寫能力和均衡性均較強。【相關(guān)文獻】1周世民，柴云鵬，王良，等.固態(tài)硬盤混合存儲數(shù)據(jù)庫的數(shù)據(jù)分布優(yōu)化算法.計算機工程2015;41(4):55—59ZhouShimin,ChaiYunpeng,WangLiang,etal.DataLayoutoptimizationalgorithmfordatabaseofhybridstoragewithsolidstatedrive.ComputerEngineering,2015;41(4):55—592MazhariSM,MonsefH,RomeroR.Ahybridheuristicandevolutionaryalgorithmfordistributionsubstationplanning.IEEESystemsJournal,2014;9(4):1—133薛忠斌，周炬，張延松，等.內(nèi)存列存儲數(shù)據(jù)庫中優(yōu)化的混合自適應(yīng)索引.計算機科學(xué)2015;42(11):28—31XueZhongbin,ZhouXuan,ZhangYansong,etal.Optimizedadaptivehybridindexingforin-memorycolumnstores.ComputerScience,2015;42(11):28—314潘穎.自適應(yīng)遺傳算法在分布式數(shù)據(jù)庫查詢優(yōu)化中的應(yīng)用.內(nèi)蒙古師大學(xué)報(自然科學(xué)版),2016;45(1):94—97PanYing.Applicationofqueryoptimizationbasedonadaptivegeneticalgorithmindistributeddatabase.JournalofInnerMongoliaNormalUniversity(NaturalScienceEdition),2016;45(1):94—975IngredientsAK.Anewhybridmodelbasedonanintelligentoptimizationalgorithmandadatadenoisingmethodtomakewindspeedpredication.MathematicalProblemsinEngineering,2015;2015(11):1—166程翔，劉升.云自適應(yīng)混合細菌覓食優(yōu)化算法.微電子學(xué)與計算機,2015;32(5):111—116ChengXiang,LiuSheng.Adaptivehybridbacterialforagingoptimizationalgorithmbasedoncloudtheory.Microelectronics&Computer,2015;32(5):111—1167WuZhizheng,LiYang,WangPei,etal.Dynamichead-diskinterfacemodelingandadaptivecontrolofahybridactuatorforopticaldatastoragesystems.InternationalJournalofOptomechatronics,2014;9(1):62—888王梅,邢露露，孫莉.混合存儲下的MapReduce啟發(fā)式多表連接優(yōu)化.計算機科學(xué)與探索,2014;8(11):1334—1344WangMei,XingLulu,SunLi.MapReducebasedheuristicmulti-joinoptimizationunderhybridstorage.JournalofFrontiersofComputerScience&Technology,2014;8(11):1334—13449張濱,樂嘉錦，孫莉，等.基于列存儲的大數(shù)據(jù)分析系統(tǒng)物化策略研究.計算機研究與發(fā)展,2015;52(5):1061—1070ZhangBin,LeJiajin,SunLi,etal.Materializationstrategiesinbigdataanalysissystembasedoncolumn-store.JournalofComputerResearchandDevelopment,2015;52(5):1061—107010LiP,DargavilleR,LiuF,etal.Data-basedstatisticalpropertyanalyzingandstoragesizingforhybridrenewableenergysystems.IEEETransactionsonIndustrialElectronics,2015;62(11):1—111周先存，黎明曦,陳振偉，等.基于層次混合的高效概率包標記WSNs節(jié)點定位算法.電子與信息學(xué)報,2014;36(2):384—389ZhouXiancun,LiMingxi,ChenZhenwei,etal.Anefficientprobabilisticpacketmarkingnodelocalizationalgorithmbasedonlayers-mixedinWSNs.JournalofElectronics&InformationTechnology,2014;36(2):384—38912趙新輝，李杰.大數(shù)據(jù)云存儲信息查詢路徑優(yōu)化仿真研究.計算機仿真,2016;33(8):181—184ZhaoXinhui,LIJie.Largedataquerypathoptimizationsimulationinformationstoredinthedatacloud.ComputerSimulation,2016;33(8):181—18413TanL,SunJ,TongX.AhybridparticleswarmoptimizationbasedmemeticalgorithmforDNAsequencecompression.SoftComputing,2015;19(5):1255—126814朱洪.循環(huán)橢圓曲線耦合一致分布混沌映射的混合圖像加密算法研究.科學(xué)技術(shù)與工程2014;14(8):222—227ZhuHong.Thestudyonimageencryptionalgorithmbasedonthecyclicellipticcurvecoupleduniformdistributionofchaoticmap.ScienceTechnologyandEngineering,2014;14(8):222—22715高菲菲.基于Gabor特征分解的高斯混合非線性濾波算法.科技通報,2015;31(12):88—90GaoFeifei.Gausshybridnonlinearfilterdesignbasedongaborfeaturedecomposition.BulletinofScienceandTechnology,2015;31(12):88—9016ZhangF,DongX,LiangJ,etal.Capacityoptimizationofhybridenergystoragesystembasedontargetdecompositionandcomplementaryfluctu