多核處理器中并行自適應(yīng)索引算法優(yōu)化

袁 通,劉志鏡,劉 慧

(西安電子科技大學(xué)計算機學(xué)院,陜西西安 710071)

多核處理器中并行自適應(yīng)索引算法優(yōu)化

袁 通,劉志鏡,劉 慧

(西安電子科技大學(xué)計算機學(xué)院,陜西西安 710071)

針對現(xiàn)有的多核并行自適應(yīng)索引算法不能高效地利用多核處理器的并行資源,且不能較好處理順序查詢的問題,提出了一種改進的多核并行自適應(yīng)索引算法.該算法在優(yōu)化現(xiàn)有Refined Partition Merge算法的基礎(chǔ)上,將加鎖并行方法與Refined Partition Merge算法相結(jié)合,在索引中數(shù)據(jù)塊較少時,使用優(yōu)化的Refined Partition Merge算法,降低線程之間沖突的概率,減少線程等待時間,提高線程利用率.當(dāng)索引中數(shù)據(jù)塊較多時,使用加鎖并行方法,充分利用了多核處理器的并行資源.除此之外,還提出了一種提升自適應(yīng)索引魯棒性的優(yōu)化方法,使多核并行自適應(yīng)索引算法能夠適應(yīng)兩種常用查詢樣式.實驗結(jié)果表明,該算法使多核并行自適應(yīng)索引在查詢時間上明顯降低,使查詢速度提升25.7%～33.2%,并且能夠適應(yīng)多種常用查詢樣式.

自適應(yīng)索引;多核處理器;Database Cracking算法;數(shù)據(jù)庫系統(tǒng)

隨著海量數(shù)據(jù)時代的到來,系統(tǒng)數(shù)據(jù)庫的規(guī)模越來越大,如何快速檢索數(shù)據(jù)成為數(shù)據(jù)庫領(lǐng)域一個重要的課題.索引技術(shù)可以大幅提高檢索數(shù)據(jù)的效率,常用的索引包括:平衡二叉樹、B+樹索引、哈希索引[1]、ART樹索引[2]等.但這些索引技術(shù)有以下缺點:索引需要在查詢之前創(chuàng)建完成,這個過程消耗大量的時間和空間;索引需要涵蓋表中的所有行,即使其中的一些行極少的被查詢.

自適應(yīng)索引技術(shù)[3]自提出以來,受到了廣泛的關(guān)注[4-8],較好地解決了傳統(tǒng)索引的缺點.與傳統(tǒng)的索引不同,自適應(yīng)索引的核心思想是根據(jù)查詢條件動態(tài)地、自適應(yīng)地建立和優(yōu)化索引結(jié)構(gòu),索引的建立是查詢?nèi)蝿?wù)的一個部分.該技術(shù)對表中經(jīng)常查詢到的行會建立更好的索引,對那些沒有被查詢到的行不會建立索引.

當(dāng)今的中央處理器(Central Processing Unit,CPU)擁有更多的核心,每個核心擁有更多的線程.IBM推出了新一代的POWER 8處理器,支持12核心96線程,共享96 MB的三級緩存,這說明多核CPU具有廣闊的應(yīng)用前景.但目前對于多核并行自適應(yīng)索引技術(shù)的研究還不是很多,僅有的一些研究成果[4-5]也存在一定的不足.文獻[4]提出用加鎖的方式避免線程之間的沖突,實現(xiàn)并行索引,然而頻繁的加鎖和解鎖操作耗費了大量的時間.文獻[5]提出了Partition Merge算法,在該算法中所有線程每次共同處理一個查詢?nèi)蝿?wù).該算法雖然避免了頻繁的加鎖解鎖操作,但當(dāng)所有線程共同處理一個較小的查詢?nèi)蝿?wù)時,不能高效利用處理器并行資源,容易造成資源浪費.

針對上述問題,筆者提出了一種改進的多核并行自適應(yīng)索引算法,該算法在優(yōu)化傳統(tǒng)并行自適應(yīng)索引的基礎(chǔ)上,將加鎖并行方法與優(yōu)化的Refined Partition Merge算法相結(jié)合,充分利用了多核處理器的并行資源,取得良好的效果.除此之外,文中提出的優(yōu)化方法使自適應(yīng)索引能夠較好地適應(yīng)常用的兩種查詢樣式(隨機查詢和順序查詢),提升了自適應(yīng)索引的魯棒性.

圖1　Database Cracking算法流程示例

1　相關(guān)工作

Database Cracking算法[3]作為自適應(yīng)索引的核心被廣泛采用.Database Cracking首先將表中需要建立索引的數(shù)據(jù)復(fù)制到一個連續(xù)的空間作為索引的物理結(jié)構(gòu),其次根據(jù)每次查詢條件對索引進行重新劃分,重新劃分的過程類似快速排序,查詢的邊界點類似快速排序中的支點.最后還需要一個二叉樹來保存劃分信息(該二叉樹稱為Cracker index),樹節(jié)點〈X,Y〉表示在索引中從位置Y開始的所有數(shù)據(jù)都大于X.圖1給出了Database Cracking方法的基本流程.當(dāng)進行查詢(10,30)時,索引被劃分為了3塊:小于10的部分、(10,30)的部分、大于30的部分,其中(10,30)的部分作為查詢結(jié)果返回.節(jié)點〈10,2〉和〈30,7〉也同時保存在樹中.當(dāng)進行第2次查詢(25,40)時,(10,30)的塊再次被分成(10,25)和(25,30)兩塊,大于30的部分也被分成(30,40)和大于40的兩塊,其中,(25,30)和(30,40)兩塊作為查詢結(jié)果返回.同時,節(jié)點〈25,5〉和〈40,10〉也保存在樹結(jié)構(gòu)中以便后續(xù)查詢使用.Database Cracking算法的優(yōu)勢是:每次查詢只需處理索引中包含查詢邊界的兩個數(shù)據(jù)塊,并不需要處理整個查詢范圍之間的數(shù)據(jù)塊.所以當(dāng)查詢次數(shù)越多,索引被劃分的越細,索引中每塊數(shù)據(jù)越小,則索引被建立的越好,該范圍內(nèi)后續(xù)查詢所用的時間越短.

目前針對Database Cracking算法的研究主要在以下3個方面:提高算法收斂速度、提高算法魯棒性以及利用并行提高算法效果.Hybrid Cracking算法[6]結(jié)合了Adaptive Merging算法[7]和標(biāo)準(zhǔn)Database Cracking算法各自的優(yōu)勢,在保證較低初始化花銷的同時,提高了算法的收斂速度.Buffered-swapping算法[9]利用兩個堆結(jié)構(gòu)存儲需要交換元素,提升了算法的收斂速度.文獻[10]針對順序查詢樣式引出的問題,提出了DDR,DDC以及MDD1R等算法,以提高算法魯棒性,其中DDR算法取得了較好的效果.文獻[4]研究了并行Database Cracking算法,通過加鎖的方式避免線程間的沖突,實現(xiàn)算法并行化.文獻[5]提出了Refined Partition Merge算法,在該算法中所有線程每次共同處理一個查詢?nèi)蝿?wù).

2　多核并行自適應(yīng)索引優(yōu)化

2.1實驗環(huán)境

文中的實驗環(huán)境基于新型英特爾Sandy Bridge架構(gòu)的Xeon 8核處理器(E5-2670 2.6 GHz),每核包含2個線程.具體配置為:核數(shù)為8,線程數(shù)為16,一級緩存大小為每核32 KB;二級緩存大小為每核256 KB;三級緩存大小為共享20 MB;內(nèi)存大小為4×8 GB DDR3內(nèi)存(1 600 Hz);Cache line大小為64 B.

實驗采用與相關(guān)論文相同的數(shù)據(jù)集.該數(shù)據(jù)集有108條數(shù)據(jù),每條數(shù)據(jù)是大小為4 B的整型數(shù),108條數(shù)據(jù)在[0,108)范圍內(nèi)隨機產(chǎn)生且均勻分布.

采用的查詢格式為:SELECT SUM(R.A)FROM R WHERE Ql＜R.A＜Qh.

文中討論兩種查詢樣式:隨機查詢和順序查詢,這兩種查詢均為相關(guān)論文所討論的主要查詢方式.圖2給出隨機查詢樣式和順序查詢樣式,其中黑圈表示查詢下限Ql,白圈表示查詢上限Qh,兩種查詢的選擇率均為1%.

圖2　文中所用的兩種查詢樣式

2.2Refined Partition Merge算法的優(yōu)化

文獻[5]提出了Refined Partition Merge算法,所有線程共同處理一條查詢?nèi)蝿?wù).假設(shè)索引結(jié)構(gòu)中有S個元素,線程數(shù)量為T,現(xiàn)將索引結(jié)構(gòu)劃分為T塊.前T-1塊中,每塊含有S/T個元素,且由兩個不相鄰的子塊組成,每個子塊有S/(2T)個元素,每個子塊的位置對稱于索引中心位置的兩側(cè);第T塊含有剩余元素(考慮元素不能等分的情況),其元素連續(xù)的分布于索引中心位置兩側(cè),如圖3所示.在劃分階段,每一個線程負責(zé)一塊數(shù)據(jù),并行地執(zhí)行標(biāo)準(zhǔn)Database Cracking算法;在合并階段,將位置錯誤的元素進行位置交換,最終得到正確的Database Cracking結(jié)果.在該算法中每一個線程負責(zé)兩個不相連的數(shù)據(jù)子塊,這樣避免了Merge階段大量元素的交換,提高了合并階段的效率.

圖3　Refined Partition Merge算法示例

圖4　并行合并示例

在Refined Partition Merge算法中,合并階段是由一個線程獨立完成的,沒有充分利用處理器的并行資源.文中的優(yōu)化是對合并階段進行并行化處理,利用多路并行歸并的思想,分層將塊中位置錯誤的元素進行交換.在圖4中,L代表小于支點的數(shù)據(jù),H代表大于支點的數(shù)據(jù).塊1和塊2分別經(jīng)過Database Craking處理后,塊內(nèi)相對有序,塊間無序.如圖4所示,一個線程將塊1和塊2中位置錯誤的元素進行交換后,形成一個新塊,等待進行下一層的交換.每層之中的交換可以多線程并行處理,經(jīng)過多層交換以后最終得到元素位置正確的索引.圖4舉例說明并行合并過程,其中每層的交換可以并行處理,經(jīng)過兩層交換后得到最終正確的結(jié)果.

2.3改進的多核并行自適應(yīng)索引算法

在加鎖并行方法中,每一個線程每次負責(zé)一條查詢?nèi)蝿?wù),索引中的每一個數(shù)據(jù)塊有一個讀寫鎖,整個Cracker index(即保存劃分信息的二叉樹)有一個讀寫鎖,這些讀寫鎖避免了線程之間的沖突.當(dāng)一個線程對某一數(shù)據(jù)塊處理時,會對該數(shù)據(jù)塊加鎖.這時對數(shù)據(jù)塊進行任何操作的其他線程都會被阻塞,直至該數(shù)據(jù)塊被解鎖.算法對Cracker index允許多線程并行讀操作,但不允許并行寫操作.

圖5　兩種并行算法性能比較

以上兩種算法都有各自的優(yōu)缺點,圖5給出了兩種算法在8線程環(huán)境下進行1次至1 000次隨機查詢時分別所需的時間.從圖5可以看出,當(dāng)查詢次數(shù)較少時優(yōu)化Refined Partition Merge算法效果較好,當(dāng)查詢次數(shù)較多時加鎖并行Database Cracking算法效果較好.這是因為:當(dāng)查詢次數(shù)較少,索引中數(shù)據(jù)塊較少時,特別是前幾次查詢時,加鎖并行Database Cracking算法中線程之間沖突的概率增大,算法性能降低.以第1次查詢?yōu)槔f明:當(dāng)進行第1條查詢?nèi)蝿?wù)時,整個索引只是一整塊數(shù)據(jù),沒有任何劃分,此時只有一個線程可以工作,其余線程需要等待.這耗費了大量時間,浪費了并行資源,特別是當(dāng)索引數(shù)據(jù)特別大時.此時優(yōu)化Refined Partition Merge算法不會浪費其他線程的計算資源,所以取得較好的效果.當(dāng)查詢次數(shù)較多,索引中數(shù)據(jù)塊較多時,加鎖并行Database Cracking算法中線程之間沖突的概率較小,線程等待鎖的平均時間大大降低,所以此算法效率較高.然而此時,優(yōu)化Refined Partition Merge算法依然讓所有線程并行處理一個數(shù)據(jù)塊,即使該數(shù)據(jù)塊很小,這樣大部分時間花費到線程建立、數(shù)據(jù)分配等操作上,所以當(dāng)查詢次數(shù)增加,優(yōu)化Refined Partition Merge算法性能降低.文中提出了一種改進的多核并行自適應(yīng)索引方法.該方法將優(yōu)化Refined Partition Merge算法和加鎖并行Database Cracking算法相結(jié)合,在前幾次查詢時或者處理索引中較大的數(shù)據(jù)塊時,使用優(yōu)化的Refined Partition Merge算法,降低線程之間沖突的概率,減少線程等待時間,提高線程利用率.隨著查詢次數(shù)和索引中數(shù)據(jù)塊的增加,之后的查詢則使用加鎖解鎖方法,避免了Refined Partition Merge在處理索引中小數(shù)據(jù)塊時的不足.在此提出的優(yōu)化方法適用于同一數(shù)據(jù)集上的多次范圍查詢.當(dāng)查詢次數(shù)較少時,利用2.2節(jié)提出算法即可.

2.4提升算法魯棒性的優(yōu)化

魯棒性是自適應(yīng)索引算法一個關(guān)鍵的因素,強壯的魯棒性可以使文中算法適應(yīng)多種樣式的查詢.標(biāo)準(zhǔn)的Database Cracking算法(單線程)和加鎖并行Database Cracking算法(多線程)都不能很好的處理順序查詢.圖6給出了加鎖并行Database Cracking算法處理隨機查詢和順序查詢的實驗結(jié)果,從圖中可以看出,加鎖并行Database Cracking算法能夠很好處理隨機查詢,但對順序查詢處理效果不佳.主要因為:加鎖并行Database Cracking算法僅根據(jù)每個查詢的邊界對數(shù)據(jù)塊進行劃分.在順序查詢中,每次劃分將一個數(shù)據(jù)塊分為兩個大小相差很大的數(shù)據(jù)塊,其中一個數(shù)據(jù)塊很大,另一個卻很小.這使后續(xù)的查詢需要遍歷較大的數(shù)據(jù)塊,增加了開銷.

圖6　兩種查詢樣式的性能比較

圖7　劃分支點位置對性能的影響

針對上述問題,在DDR算法[10]的基礎(chǔ)上,提出了一種優(yōu)化方法.思路是:在改進的多核并行自適應(yīng)索引方法中,無論優(yōu)化Refined Partition Merge算法還是加鎖并行Database Cracking算法,在進行一次由查詢驅(qū)動的劃分后,都額外進行一次隨機劃分,并將產(chǎn)生的兩個新節(jié)點均加入Cracker index之中.

3　實驗結(jié)果及分析

3.1優(yōu)化Refined Partition Merge算法的實驗結(jié)果

為了驗證對原Refined Partition Merge算法的優(yōu)化效果,將優(yōu)化的算法(2.2節(jié))與原算法在不同線程數(shù)下進行了比較.實驗采用2.1節(jié)所述的數(shù)據(jù)集和隨機查詢樣式,實驗結(jié)果如圖8所示.從圖8可以看出:優(yōu)化后的算法與原算法相比,性能有所提高;當(dāng)線程數(shù)為1時,兩個算法所需時間一樣;當(dāng)線程數(shù)從8增加到16時,算法性能提升不明顯.這是因為,首先,采用了并行合并算法,減少了合并階段的時間消耗,算法性能得到了提升;其次,當(dāng)線程數(shù)為1時,不需要進行合并操作,所以兩個算法所需的時間相同;最后,由于實驗機器為8核16線程,總線資源和緩存資源按核分配.所以當(dāng)線程數(shù)量為16時,核內(nèi)線程之間會競爭總線、緩存等資源,所以,當(dāng)線程數(shù)從8增加到16時,算法性能提升不明顯.

圖8　優(yōu)化Refined Partition Merge算法的實驗結(jié)果

圖9　改進的多核并行自適應(yīng)索引算法實驗結(jié)果

3.2改進的多核并行自適應(yīng)索引算法的實驗結(jié)果

圖9給出了改進的多核并行自適應(yīng)索引算法(2.3節(jié))與其他兩種常用的并行自適應(yīng)索引算法在不同線程數(shù)量下的對比結(jié)果.實驗采用2.1節(jié)所述的數(shù)據(jù)集和隨機查詢樣式,文中算法在前5%次查詢(即前50次)使用優(yōu)化的Refined Partition Merge算法,剩余查詢使用加鎖并行Database Cracking算法.由圖9可以看出,文中算法與原有的算法相比,性能有了明顯的提高.這是由于在前50次查詢時使用優(yōu)化的Refined Partition Merge算法,提高了算法處理大數(shù)據(jù)塊時的效率;在剩余查詢時使用加鎖并行Database Cracking算法時,由于此時索引中數(shù)據(jù)塊較多,線程之間沖突的概率減小,且與優(yōu)化的Refined Partition Merge算法大幅減少了線程創(chuàng)建、數(shù)據(jù)分配等操作的開銷.當(dāng)線程數(shù)量為16時,核內(nèi)線程之間會競爭總線、緩存等資源,所以當(dāng)線程數(shù)從8增加到16時,算法性能提升不明顯.

3.3算法魯棒性優(yōu)化的實驗結(jié)果

圖10給出了算法魯棒性優(yōu)化(2.4節(jié))的實驗結(jié)果,實驗采用2.1節(jié)所述的數(shù)據(jù)集和順序查詢樣式.圖10進一步驗證了2.4節(jié)中加鎖并行Database Cracking算法不能很好的處理順序查詢的結(jié)論.實驗結(jié)果表明,并行DDR算法和文中優(yōu)化算法針對順序查詢時都取得了較好的效果,且文中優(yōu)化算法效果最好.這是因為:增加一次隨機劃分可以避免大數(shù)據(jù)塊的出現(xiàn)而影響后續(xù)查詢;文中優(yōu)化算法可以針對不同的劃分位置,選取更好的劃分策略(兩次Cracking-into-two操作或者一次Cracking-intothree操作),所以,文中算法比并行DDR算法性能有所提升.

圖10　算法魯棒性優(yōu)化實驗結(jié)果

4　結(jié)束語

為了解決多核并行自適應(yīng)索引算法不能高效地利用多核處理器的并行資源,且不能較好處理順序查詢的問題,筆者優(yōu)化了傳統(tǒng)的多核并行自適應(yīng)索引算法.在改進Refined Partition Merge算法的基礎(chǔ)上,將加鎖并行方法與改進的Refined Partition Merge算法相結(jié)合,在索引中數(shù)據(jù)塊較少時,使用優(yōu)化的Refined Partition Merge算法,降低線程之間沖突的概率,減少線程等待時間,提高線程利用率.當(dāng)索引中數(shù)據(jù)塊較多時,使用加鎖并行方法,充分利用了多核處理器的并行資源,且提高了算法的魯棒性.實驗證明了筆者提出方法的有效性和魯棒性.

[1]馬艷萍,姬光榮,鄒海林,等.數(shù)據(jù)依賴的多索引哈希算法[J].西安電子科技大學(xué)學(xué)報,2015,42(4):159-164. MA Yanping,JI Guangrong,ZOU Hailin,et al.Data-oriented Multi-index Hashing[J].Journal of Xidian University,2015,42(4):159-164.

[2]LEIS V,KEMPER A,NEUMANN T.The Adaptive Radix Tree:Artful Indexing for Main-memory Databases[C]// Proceedings of the 29th International Conference on Data Engineering.Washington:IEEE Computer Society,2013: 38-49.

[3]IDREOS S,KERSTEN M L,MANEGOLD S.Database Cracking[C]//3rd Biennial Conference on Innovative Data Systems Research.Asilomar:CIDR,2007:68-78.

[4]GRAEFE G,HALIM F,IDREOS S,et al.Concurrency Control for Adaptive Indexing[J].Proceedings of the VLDB Endowment,2012,5(7):656-667.

[5]PIRK H,PETRAKI E,IDREOS S,et al.Database Cracking:Fancy Scan,Not Poor Man’s Sort[C]//10th International Workshop on Data Management on New Hardware.New York:ACM,2014:25-32.

[6]IDREOS S,MANEGOLD S,KUNO H,et al.Merging What’s Cracked,Cracking What’s Merged:Adaptive Indexing in Main-memory Column-stores[J].Proceedings of the VLDB Endowment,2011,4(9):585-597.

[7]GRAEFE G,KUNO H.Self-selecting,Self-tuning,Incrementally Optimized Indexes[C]//13th International Conference on Extending Database Technology.New York:ACM,2010:371-381.

[8]IDREOS S,KERSTEN M,MANEGOLD S.Updating a Cracked Database[C]//2007 ACM SIGMOD International Conference on Management of Data.New York:ACM,2007:416-424.

[9]SCHUHKNECHT F,JINDAL A,DITTRICH J.The Uncracked Pieces in Database Cracking[J].Proceedings of the VLDB Endowment,2014,7(2):97-108.

[10]HALIM F,IDREOS S,KARRAS P,et al.Stochastic Database Cracking:Towards Robust Adaptive Indexing in Mainmemory Column-stores[J].Proceedings of the VLDB Endowment,2012,5(6):502-513.

(編輯:王 瑞)

Optimizing the parallel adaptive indexing algorithm on multi-core CPUs

YUAN Tong,LIU Zhijing,LIU Hui
(School of Computer Science and Technology,Xidian Univ.,Xi’an 710071,China)

An improved parallel adaptive indexing algorithm on multi-core CPUs is proposed to solve the problems that the parallel adaptive indexing algorithms cannot take full advantage of the CMP’s parallel execution resource,and properly process the sequential query pattern.Based on the optimization of the Refined Partition Merge algorithm,our improved parallel adaptive indexing algorithm combines the Parallel Database Cracking method with the Refined Partition Merge algorithm.In our algorithm,when fewer data chunks are in the index,we use the optimized Refined Partition Merge algorithm so as to reduce the probability of conflict between threads,decrease the waiting time,and increase the utilization of the threads,and when more data chunks are in the index,we use the Parallel Database Cracking method so as to take full advantage of the CMP’s parallel execution resources.Besides,we propose an optimization for the robustness,which makes our algorithm suitable for two common query patterns.Experiments show that our method can reduce the query time by 25.7%～33.2%,and suit with common query patterns.

adaptive indexing;multicore processors;database cracking algorithm;database system

TP392

A

1001-2400(2016)05-0057-06

10.3969/j.issn.1001-2400.2016.05.011

2015-07-22 網(wǎng)絡(luò)出版時間:2015-12-10

國家自然科學(xué)基金資助項目(61202177)

袁 通(1987-),男,西安電子科技大學(xué)博士研究生,E-mail:yuantongxd@gmail.com.

網(wǎng)絡(luò)出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20151210.1529.022.html