薛 翔,沈斯杰,陳 榕

(上海交通大學 軟件學院 并行與分布式系統(tǒng)研究所,上海 200240) E-mail:xuexiang8201950@gmail.com

1 引 言

隨著信息技術不斷發(fā)展,企業(yè)對大數(shù)據(jù)的存儲和處理能力要求與日俱增.傳統(tǒng)關系型數(shù)據(jù)庫對于海量數(shù)據(jù)處理的日漸乏力,推動了非關系型數(shù)據(jù)庫(NoSQL)的發(fā)展*https://db-engines.com/en/ranking.NoSQL以鍵值對的形式存儲數(shù)據(jù),具有結構簡潔、擴展性強等優(yōu)點,能夠支持高效且原子性的點查詢.然而,對于范圍查詢則往往需要借助額外的數(shù)據(jù)結構和設計以提高查詢效率.

范圍查詢是數(shù)據(jù)庫支持的重要功能之一,即基于給定表中某一列上的范圍條件查詢目標列的結果.包含范圍查詢的請求常見于各類應用場景中.例如,在線事務處理(OLTP)基準測試TPC-C中,5種事務類型中的4種包含范圍查詢,占總查詢量的55%;在線分析處理(OLAP)基準測試TPC-H中,22種查詢類型中的18種包含范圍查詢,占總查詢量的81.8%.如無二級索引或存儲優(yōu)化技術的支持,范圍查詢需遍歷表中所有數(shù)據(jù),導致查詢效率低下.因此,現(xiàn)有的系統(tǒng)通過對列建立索引,維護索引列到主鍵的映射,以提供對該列范圍查詢的能力,為上層提供更加豐富、執(zhí)行效率更高的查詢語義.

提高范圍查詢效率主要從優(yōu)化索引查詢過程和加快命中數(shù)據(jù)獲取兩個方面入手.Yesquel[2]、SLIK[3]、Nitro[4]和Cell[5]等系統(tǒng)針對索引查詢過程進行優(yōu)化,其核心思想在于提高索引查詢過程的并發(fā)性.通過水平[2]或垂直[3]劃分二級索引結構到各個計算節(jié)點,或者使用并發(fā)友好的數(shù)據(jù)結構[4]作為二級索引,讓并發(fā)查詢請求在索引劃分出的不同部分上處理.這種方法能夠提高索引查詢的并發(fā)性,但當范圍條件命中大量數(shù)據(jù)時,序列化及傳輸數(shù)據(jù)的過程成為范圍查詢效率的瓶頸[1],此時優(yōu)化索引查詢過程只能達到有限效果.

為加快命中數(shù)據(jù)的獲取,HyperDex[6]和Replex[7]等系統(tǒng)將表數(shù)據(jù)在索引列上劃分范圍并分區(qū)存儲.在索引列上的范圍查詢,其命中的數(shù)據(jù)聚集在若干分區(qū)中,范圍條件不重疊的查詢會從不同的分區(qū)獲取數(shù)據(jù).這種存儲上的優(yōu)化方法一定程度上能夠提高命中數(shù)據(jù)的局部性,從而降低傳輸所需的序列化成本,同時也提高了獲取數(shù)據(jù)階段中查詢的并行性.但由于分區(qū)內(nèi)的數(shù)據(jù)以行為單位散列存儲,而范圍查詢通常只需獲取部分列上的數(shù)據(jù)[19],解析并序列化目標列的開銷仍然較大,導致獲取命中數(shù)據(jù)的速度仍有提升空間.

圖1 使用二級索引的查詢過程Fig.1 Range search with secondary index

為提高分布式數(shù)據(jù)庫的范圍查詢效率,本文提出使用索引式備份的范圍查詢方法.通過對備份數(shù)據(jù)以索引列重構為索引式備份,使其參與到范圍查詢過程中.備份數(shù)據(jù)首先以列存儲的方式組織表數(shù)據(jù),再將每列上的數(shù)據(jù)都按照索引列值排序,構成索引式備份.范圍查詢時,使用合適的索引式備份定位目標列上的命中數(shù)據(jù),并傳輸?shù)奖镜剡M行計算.由于列數(shù)據(jù)聚集且有序存儲,定位命中數(shù)據(jù)所需的索引查詢開銷與命中數(shù)據(jù)量無關,同時傳輸?shù)男蛄谢杀据^低,能夠有效地提升數(shù)據(jù)的傳輸速度.

基于DrTM+R[9,11]系統(tǒng)實現(xiàn)的混合查詢模型在TPC-H*http://www.tcp.org/hspec.html[12]基準測試中,范圍查詢性能可以提升平均28.5倍,后續(xù)計算步驟的時間能夠減少80.8%,整體性能提升達到8.4-16.7倍.

本文首先介紹了背景知識及相關范圍查詢優(yōu)化技術(第2章);其次,說明備份架構及索引式備份重構過程(第3章);如何使用重構后的索引式備份進行范圍查詢(第4章);測試性能、可擴展性及優(yōu)化效果(第5章);最后進行總結(第6章).

2 背景介紹

鍵值對存儲以其結構簡潔、可擴展性強等優(yōu)點,被使用在許多成熟的數(shù)據(jù)存儲系統(tǒng)中,如BigTable[10],Redis*https://redis.io/,Memcached*https://memcached.org等.以上系統(tǒng)將表中每行數(shù)據(jù)轉(zhuǎn)換成鍵值對,使用“二級索引-哈希表-鍵值對”三級結構來支持非主鍵列上的范圍查詢.如圖1,先使用范圍條件在索引樹中遍歷,得到范圍內(nèi)命中的主鍵;然后對命中主鍵,在哈希表中查詢,得到本地或遠端的數(shù)據(jù)存儲地址;最后,通過本地訪存和遠端讀取的方式,獲取范圍條件命中的數(shù)據(jù),進行計算.

使用這種結構支持的范圍查詢,其開銷主要來自于索引查詢和數(shù)據(jù)獲取.現(xiàn)有系統(tǒng)也主要針對這兩方向進行優(yōu)化.

2.1 索引查詢優(yōu)化技術

為提高索引查詢效率,現(xiàn)有研究針對二級索引的設計和查詢方法進行優(yōu)化.

SLIK[3]將索引樹按照索引列的范圍垂直切分成indexlet,維護在分配有獨立計算資源的索引節(jié)點中.這種方法讓查詢索引的過程能夠得到足夠的計算資源,索引查詢步驟的可擴展性較強.不同于SLIK的水平切分,Yesquel[2]分析Web應用的查詢特點,將索引樹垂直切分:高層子樹被緩存在所有計算節(jié)點中,底部子樹與其索引的數(shù)據(jù)劃分給各個計算節(jié)點進行維護.在讀多寫少的應用場景中,可以樂觀假設本地高層索引樹緩存的有效性,減少遠端查詢索引的次數(shù),從而提高索引查詢的速度.Nitro[4]使用無鎖跳表(lock-free skiplist)實現(xiàn)二級索引.相比索引樹,無鎖跳表支持細粒度的讀寫操作,以更高的并發(fā)性提升分布式系統(tǒng)的范圍查詢效率.Cell[5]將維護在server上的索引樹劃分為多個meganode.當client檢測到server負載較高時,利用遠程直接內(nèi)存訪問(RDMA)的單邊讀取和內(nèi)核旁路的特性讀取meganode到本地實現(xiàn)對索引樹的查詢,讓系統(tǒng)整體的處理能力得到提升.

這類方法通過提高索引查詢過程的并發(fā)性讓系統(tǒng)處理范圍查詢的效率更高,但在范圍條件命中的數(shù)據(jù)量較大、數(shù)據(jù)傳輸序列化的成本成為主要瓶頸時[1],單獨優(yōu)化索引查詢過程的做法,只能使整體性能得到有限的提升.

2.2 數(shù)據(jù)獲取優(yōu)化技術

為更快獲取命中范圍條件的數(shù)據(jù)以進行后續(xù)計算,系統(tǒng)可優(yōu)化數(shù)據(jù)存儲的方式.

HyperDex[6]系統(tǒng)將鍵值對按照不同列上的屬性值范圍劃分多維子空間,并規(guī)定屬性值范圍到子空間的映射(hyperspace hashing),同屬性值范圍的數(shù)據(jù)被映射到同樣的數(shù)據(jù)節(jié)點,使用本地二級索引進行管理.這種映射關系保證滿足條件的數(shù)據(jù)只存儲在少數(shù)節(jié)點中,避免了與無關節(jié)點通信帶來的不必要開銷.觀察到為實現(xiàn)特定索引列上更快的范圍查詢,表數(shù)據(jù)應以該列進行分區(qū)[7],因此Replex提出將備份數(shù)據(jù)按照索引列分區(qū)存儲.這種方法提高命中數(shù)據(jù)局部性的同時能一定程度上減少傳輸時的序列化時間.

圖2 系統(tǒng)備份架構圖Fig.2 Distribution of primary & backup data

數(shù)據(jù)分區(qū)后使用哈希表進行散列存儲,分區(qū)內(nèi)的數(shù)據(jù)散列存放、相對無序.同時,由于范圍查詢只需要獲取目標列上的數(shù)據(jù),導致解析目標列數(shù)據(jù)的成本隨著命中數(shù)據(jù)的增多而上升.這使得命中數(shù)據(jù)傳輸過程成為范圍查詢的瓶頸.

理想情況下,使用列式存儲[12,13]能極大減少序列化成本.但列式存儲要求將行數(shù)據(jù)以列拆分,系統(tǒng)在處理點查詢時需要將分散的列數(shù)據(jù)重組,對點查詢性能影響較大[13].

3 索引式備份

為說明使用索引式備份的范圍查詢方法,本章先對高可用系統(tǒng)的備份架構進行介紹并給出相關定義(3.1),然后介紹索引式備份重構過程(3.2).

3.1 備份數(shù)據(jù)分布

如圖2.數(shù)據(jù)以塊進行組織,主數(shù)據(jù)塊默認對應三個備份數(shù)據(jù)塊,分布在不同的節(jié)點上,例如主數(shù)據(jù)塊P1對應的備份數(shù)據(jù)塊為B1-1、B1-2和B1-3.表中每一行在主塊中轉(zhuǎn)換為鍵值對并用哈希表散列存取.在分布式環(huán)境中,表數(shù)據(jù)被分區(qū)存放到若干主塊.定義主塊的第i個(i≤3)備份塊共同組成備份組(backup group),因此每個備份組包含完整的數(shù)據(jù)內(nèi)容.

處理查詢請求時,查詢請求被劃分為子請求交給各個計算節(jié)點,節(jié)點處理本地主塊包含的數(shù)據(jù),得到子請求結果,最后將子請求結果匯總,得到最終查詢結果.

在上述的分布式架構中,傳統(tǒng)方法會在每個主塊上建立二級索引,維護索引列到主鍵的映射.點查詢直接使用哈希表定位命中數(shù)據(jù);范圍查詢則先查詢該二級索引,得到主鍵集合后再使用哈希表定位數(shù)據(jù).

本文提出的索引式備份查詢方法,避免在主塊上建立索引.對于任一主數(shù)據(jù)塊,將其第i個備份塊中的某表數(shù)據(jù)按照該表第i個索引列重構.完成塊中所有表數(shù)據(jù)重構過程的備份塊稱為索引式備份.因此,表在同一備份組中以相同的索引列重構.查詢時,節(jié)點在對應的遠端索引式備份上查詢,傳輸命中的目標列數(shù)據(jù)至本地,完成范圍查詢.每個節(jié)點默認只對本地主數(shù)據(jù)包含的內(nèi)容進行查詢,得到本地查詢結果后,匯總得到最終結果.

3.2 索引式備份重構過程

結合重構備份數(shù)據(jù)的思想和列存儲使數(shù)據(jù)聚集的特性,備份數(shù)據(jù)被重構為適合處理索引列上范圍查詢的格式.本節(jié)首先介紹重構過程使用的樹結構,然后分步介紹重構過程.

支持重復key的B+樹內(nèi)部結點和葉子結點如圖3所示.

圖3 索引樹結點Fig.3 Internal and leaf node in index tree

內(nèi)部結點與普通B+樹相同.葉子結點中,每個key對應鏈表地址vl和偏移量offset.vl指向的鏈表存放該key所有value;偏移量offset表示該key對應的所有value在列數(shù)據(jù)域中的起始位置.

使用上述樹結構可幫助備份數(shù)據(jù)的重構.初始時,備份數(shù)據(jù)是主數(shù)據(jù)的鏡像副本.重構過程如下:

步驟1.指定索引列.根據(jù)表中需要范圍查詢的列,應用層為每個備份數(shù)據(jù)指定索引列;

步驟2.建立索引樹.對每個備份建立索引樹,遍歷其所有行數(shù)據(jù),提取索引列值作為key、行數(shù)據(jù)地址作為value插入上述索引樹中.遍歷完成后,該索引樹即維護該備份數(shù)據(jù)中“索引列值-行數(shù)據(jù)地址”的映射關系,索引列值在葉子層有序排列,相同索引列值的行數(shù)據(jù)地址存放在鏈表中;

步驟3.劃分列數(shù)據(jù)域.如圖4第1步,在內(nèi)存中劃分多個列數(shù)據(jù)域(灰色矩形),記錄其基地址(紅色箭頭).

步驟4.以索引列重排數(shù)據(jù).順序遍歷索引樹葉子層中所有的key,通過vl指向的value list定位行數(shù)據(jù),解析每列的值,順序存放到對應列數(shù)據(jù)域中,如圖4第2步,然后將索引列值在索引列數(shù)據(jù)域中首次出現(xiàn)的位置填入葉子節(jié)點中該項的偏移量offset.

圖4 列數(shù)據(jù)域劃分及數(shù)據(jù)重排過程Fig.4 Assign column region and reorder data

圖4中.原表有cid,name,age三列,備份數(shù)據(jù)將age作為索引列重構.劃分列數(shù)據(jù)域后,同列屬性值將聚集存放(步驟3);然后按照索引列age中的值排序存放,其他列數(shù)據(jù)以相同順序排列并存儲(步驟4).索引樹中,key為18的項對應的offset為0,表示age為18所有表行,其列值被連續(xù)存放到相應列數(shù)據(jù)域中,相對列數(shù)據(jù)域基地址的偏移量為0.30對應的offset為2,以此類推.

重構后,表數(shù)據(jù)按列存儲,且以索引列排序.在其上按照索引列進行范圍查詢時,命中的列數(shù)據(jù)聚集存放在連續(xù)內(nèi)存中.

4 使用索引式備份的范圍查詢方法

將所有備份數(shù)據(jù)重構完成后,即可在其上進行范圍查詢.下文首先介紹基本的范圍查詢方法(4.1);然后針對多范圍條件查詢進行特殊處理(4.2);最后給出分布式查詢場景的兩種優(yōu)化方法(4.3、4.4).

4.1 基本范圍查詢

計算節(jié)點接收到查詢請求后,對其進行解析.對于解析得到的范圍條件,選擇合適的索引式備份,利用RDMA單邊讀取操作在其上進行范圍查詢.

例如,在圖2中,node1解析查詢請求中的范圍條件,確定以該范圍列進行重構的索引式備份(如B1-2).然后,通過多次RDMA單邊讀取操作定位并讀取命中該范圍條件的數(shù)據(jù)至本地.

查詢索引式備份時,首先,為范圍條件的上下兩界,分別查詢索引式備份中的索引樹,得到邊界值的offset范圍.由于目標列結果順序存放在連續(xù)內(nèi)存中,通過“基址+偏移”的方法即可定位目標列結果的起始地址和終止地址(基址為目標列數(shù)據(jù)域的基地址,偏移由offset和該列數(shù)據(jù)大小確定).最終,將該地址范圍內(nèi)的數(shù)據(jù)一次性讀取到計算節(jié)點本地內(nèi)存中.圖5給出了在圖4重構的索引式備份上查詢“年齡在18到40歲以內(nèi)所有客戶的姓名”的過程.

不同于將表以索引列分區(qū)的存儲方法,索引式備份將同列數(shù)據(jù)聚集并有序存放,定位命中數(shù)據(jù)后一次性讀取到本地即可,傳輸時間只和數(shù)據(jù)總量有關,且具有批次效應;使用索引式備份處理范圍查詢,同時使用主數(shù)據(jù)處理點查詢,避免了列式存儲上執(zhí)行點查詢需重組行數(shù)據(jù)的缺點.

圖5 索引式備份上的范圍查詢過程Fig.5 Range search on indexed backup

4.2 單表多范圍條件查詢

基于索引式備份的單表多范圍條件查詢可直接轉(zhuǎn)化成多次單范圍查詢.每次單范圍查詢都讀取命中的目標列和主鍵列數(shù)據(jù)至本地,所有單范圍查詢完成后,使用主鍵列數(shù)據(jù)進行本表連接操作(JOIN),過濾得到的對應目標列數(shù)據(jù)進入后續(xù)的處理流程.

這種查詢方式會導致目標列數(shù)據(jù)“冗余傳輸”問題,即通過單范圍查詢讀取到的目標列數(shù)據(jù),一部分會在其主鍵JOIN后被過濾掉,不參與之后的處理流程,從而產(chǎn)生不必要的數(shù)據(jù)傳輸成本.當命中數(shù)據(jù)量更大、目標列數(shù)量更多或JOIN選擇度更高時,“冗余傳輸”開銷會更加明顯.例如,TPC-H Q6中,在表LINEITEM上對三個索引列各有一個范圍條件.比例系數(shù)為1的條件下三個范圍分別命中約91、163、275萬條數(shù)據(jù).目標列extendedprice、discount單位大小為4 byte,主鍵列8 byte,傳輸量約81MB,傳輸時間約25ms.但JOIN過濾后只有11.4萬條數(shù)據(jù)會進入后續(xù)處理步驟,約93.5%的傳輸時間屬于“冗余傳輸”開銷.

圖6 無JOIN范圍查詢本地優(yōu)化Fig.6 Optimization on remote range search w/o join

“冗余傳輸”問題的關鍵在于,區(qū)別于單范圍條件查詢,單表上多范圍條件查詢后需要額外的本表JOIN步驟進行過濾.只有過濾后得到的目標列數(shù)據(jù)子集才會進行后續(xù)處理,而過濾掉的目標列數(shù)據(jù)會被丟棄.因此,如何在單范圍查詢時就避免傳輸這部分數(shù)據(jù)是解決“冗余傳輸”問題的關鍵.

由于在對主鍵JOIN之前,無法得知哪些目標列數(shù)據(jù)是會被JOIN過濾的.因此,在單范圍查詢階段可以只請求主鍵列,將目標列數(shù)據(jù)的獲取推遲至JOIN步驟之后,即“推遲結果列數(shù)據(jù)獲取”.此時,由于本地的主數(shù)據(jù)塊同樣含有完整的內(nèi)容,我們可以將通過JOIN過濾的主鍵在主數(shù)據(jù)塊上進行本地點查詢,得到目標列數(shù)據(jù).

因此,針對單表多范圍條件查詢的“冗余傳輸”問題,設計多范圍查詢處理過程如下:

步驟1.記錄目標列.計算節(jié)點接收多范圍查詢請求,記錄目標列;

步驟2.多次單范圍查詢主鍵列.將請求轉(zhuǎn)換成若干單范圍條件查詢,只請求命中的主鍵列數(shù)據(jù).依次遠端查詢對應的索引式備份,得到多個條件下的主鍵;

步驟3.JOIN.對步驟2得到的主鍵進行JOIN;

步驟4.獲取目標列數(shù)據(jù).使用JOIN過濾得到的主鍵在本地主數(shù)據(jù)塊上進行點查詢,解析得到步驟1中記錄的目標列數(shù)據(jù).完成多范圍查詢過程.

實現(xiàn)過程中,為了區(qū)分普通單范圍查詢和多范圍查詢的子步驟,在多范圍查詢方法的實現(xiàn)中移除對于目標列的讀取請求;經(jīng)測試,JOIN后在主數(shù)據(jù)塊上使用哈希表點查詢需要的時間,短于“冗余傳輸”的時間.

4.3 無JOIN范圍查詢本地優(yōu)化

處理單表上單范圍條件的查詢時,例如TPC-H Q1,由于不需要進行本表或跨表JOIN操作,查詢成本主要來自范圍查詢的耗時.此時,從遠端索引式備份傳輸命中數(shù)據(jù)到本地的時間成為這類查詢的瓶頸.

如圖6所示,無論計算節(jié)點統(tǒng)一選擇遠端備份進行查詢(實線箭頭),還是統(tǒng)一選擇本地屬于備份組的備份進行查詢(虛線箭頭),都能涵蓋完整的數(shù)據(jù)內(nèi)容.兩者區(qū)別只在于每個計算節(jié)點的工作量是“本節(jié)點維護的數(shù)據(jù)”還是“其它節(jié)點維護的數(shù)據(jù)”,并不會影響最終匯總的結果.因此,可讓所有計算節(jié)點統(tǒng)一在“遠端主數(shù)據(jù)在本地的索引式備份”上進行查詢,將遠端范圍查詢轉(zhuǎn)化為本地范圍查詢,減少數(shù)據(jù)傳輸帶來的開銷.

4.4 點查詢本地優(yōu)化

計算節(jié)點在處理子請求過程中,有時需要從其他節(jié)點維護的主數(shù)據(jù)塊中進行點查詢,例如TPC-H Q3,Q14等.然而頻繁的遠端點查詢會累積產(chǎn)生較高的延遲.當節(jié)點本地有遠端主數(shù)據(jù)塊的備份,且該備份未被重構時,可支持主鍵上的點查詢.此時,如圖7,對遠端主數(shù)據(jù)的點查詢(指向P2、P3實線箭頭)可轉(zhuǎn)換為對本地其備份的點查詢(指向B2、B3虛線箭頭),減少頻繁遠端讀取帶來的開銷.當本地沒有遠端主數(shù)據(jù)(如P4)的備份,或備份被重構時,則無法本地處理這部分點查詢.

圖7 點查詢本地優(yōu)化Fig.7 Optimization on remote point search

5 測試與分析

5.1 實驗環(huán)境

本文所有實驗均在由8臺多核服務器組成的集群上完成,單節(jié)點配置:12核Intel Xeon E5-2650處理器,128GB內(nèi)存和40Gbps InfiniBand網(wǎng)絡).我們基于DrTM+R[9]系統(tǒng)實現(xiàn)了索引式備份查詢方法,并使用B+樹索引查詢方法作為對比.DrTM+R是使用鍵值存儲模式的高可用分布式事務處理系統(tǒng),具有完整的備份與恢復過程.為測試范圍查詢效果,實驗在多核集群環(huán)境下使用TPC-H基準測試進行了整體性能測試(5.2)和可擴展性測試(5.3),并對比了兩種優(yōu)化方法的效果(5.4).TPC-H中計算負載和數(shù)據(jù)規(guī)模通過比例因子(Scale Factor,SF)進行配置,相關數(shù)據(jù)說明如表1.

表1 實驗數(shù)據(jù)集Table 1 Experimental data sets

5.2 性能測試

圖8(a)以TPC-H Q1為例,在4臺服務器的配置下,增加每臺服務器線程數(shù)和比例因子SF時,使用B+樹索引范圍查詢和基于索引式備份范圍查詢的耗時及后續(xù)計算時間的對比.索引式備份方法相對于B+樹索引方法,范圍查詢性能可以提升平均28.5倍;且由于命中數(shù)據(jù)的局部性更好,后續(xù)計算步驟的時間能夠減少80.8%,整體性能達到8.4～16.7倍.

圖8 總體性能提升及可擴展性Fig.8 Speedup & scalability

使用傳統(tǒng)B+樹索引方法的范圍查詢開銷主要來自于大量的遠端點查詢請求,而使用索引式備份的方法在定位命中的索引列offset范圍后,對一個目標列上的數(shù)據(jù)只需單次讀取即可全部取回,范圍查詢開銷主要來自于數(shù)據(jù)傳輸.在增加計算負載時(1*1、1*2、1*3),兩種方法以不同的原因,范圍查詢時間線性增加.索引式備份方法得到的目標列數(shù)據(jù)聚集存放,極大提高了處理數(shù)據(jù)的局部性,在其上進行后續(xù)計算的速度更快.

當線程數(shù)和SF等比例增加時,如圖8(a)中1*1、2*2、3*3的對比,索引式備份方法范圍查詢時間線性上升.這是由于多線程同時從遠端傳輸數(shù)據(jù)時,競爭網(wǎng)絡傳輸帶寬所致.

5.3 可擴展性測試

圖8(b)比較了TPC-H中部分包含范圍條件的查詢隨著服務器數(shù)的增加,整體計算時間的變化.由于三備份的設置,服務器數(shù)從4開始增加.因為JOIN過程不屬于本文的主要優(yōu)化,為避免計算時間受到多線程同時JOIN從而產(chǎn)生資源競爭導致效率降低的影響,測試只增加服務器數(shù)量.

如圖所示,對于部分查詢,增加服務器同時增加負載,查詢延遲保持不變(Q1,Q6,Q15).

對于需要在兩個表間進行JOIN操作的查詢請求,先執(zhí)行表A上的范圍查詢,得到表A上命中的數(shù)據(jù).然后提取每條命中的行中,外鍵到表B的列值,以此點查詢存儲在本地或遠端服務器上的表B的內(nèi)容.在無數(shù)據(jù)熱點的情況下,點查詢落在本地和遠端的比例和服務器數(shù)相關.在服務器增多的情況下,點查詢請求更多地會在遠端某服務器上,能落到本地表B數(shù)據(jù)的點查詢比例會降低.因此,隨著服務器數(shù)的增加,對于需要跨機器JOIN的查詢,查詢延遲會略有增加(Q3,Q14).

總體來說,在這種增加服務器的同時等比例增加負載的環(huán)境下,查詢延遲保持相對穩(wěn)定,擴展性較好.

5.4 查詢本地優(yōu)化的效果

圖9分別展示了使用無JOIN范圍查詢本地優(yōu)化和點查詢本地優(yōu)化的效果.

圖9 使用查詢本地優(yōu)化的效果Fig.9 Effect of using local backup to search

對于無JOIN類的范圍查詢本地優(yōu)化(圖9(a)),優(yōu)化前,Q1和Q15平均處理時間分別為70.3ms和30.6ms,其中數(shù)據(jù)傳輸耗時占43.7%和97.8%.優(yōu)化后,由于不需要從遠端傳輸范圍查詢命中數(shù)據(jù),而是直接在本地索引式備份上查詢,因此處理時間分別縮短至39.6ms和0.64ms.

對于點查詢本地優(yōu)化(圖9(b)),優(yōu)化前,Q3和Q14所有遠端點查詢都從遠端主數(shù)據(jù)塊上讀取.優(yōu)化后,部分遠端點查詢請求可在本地其備份數(shù)據(jù)塊上查詢.由于增加服務器而每臺服務器點查詢總量不變,能使用本地備份優(yōu)化的點查詢比例降低,因此隨著服務器數(shù)量的增加,優(yōu)化效果減弱.在4到8臺服務器的配置下,處理時間減少20.9%至55.3%.

6 結 論

隨著大數(shù)據(jù)時代的到來,如何構建處理能力更強、可擴展性更高的分布式內(nèi)存數(shù)據(jù)庫成為研究熱點.本文通過對已有范圍查詢優(yōu)化方法的分析,結合重構備份和列存儲的思想,提出了利用索引式備份加速范圍查詢的方法,并通過推遲結果列數(shù)據(jù)獲取解決了多范圍查詢“冗余傳輸”的問題.使用索引式備份支持的范圍查詢方法在不影響原有點查詢效率的基礎上,提高了范圍條件命中數(shù)據(jù)的局部性,能有效降低數(shù)據(jù)傳輸開銷并提高后續(xù)計算的效率.基于新型高可用內(nèi)存數(shù)據(jù)庫DrTM+R實現(xiàn)的索引式備份查詢方法在TPC-H基準測試上的評測結果顯示,索引式備份查詢方法相對于B+樹索引方法可使范圍查詢達到8.4至16.7倍的性能提升,且具有較好的可擴展性.