申毅杰 曾 丹 熊 勁

(計算機體系結(jié)構(gòu)國家重點實驗室(中國科學(xué)院計算技術(shù)研究所) 北京 100190) (中國科學(xué)院大學(xué) 北京 100049)

海量數(shù)據(jù)中蘊藏著巨大的價值.分析海量數(shù)據(jù)、挖掘其中的潛在價值，能夠為企業(yè)帶來巨大的收益.例如風(fēng)險預(yù)測、精準營銷、商品推薦等.數(shù)據(jù)分析的常用平臺是傳統(tǒng)數(shù)據(jù)庫.然而，隨著數(shù)據(jù)量的急劇增長，數(shù)據(jù)庫已無法適應(yīng)大數(shù)據(jù)時代的需求，大數(shù)據(jù)處理系統(tǒng)應(yīng)運而生.近年來，Spark[1-3]系統(tǒng)被廣泛地應(yīng)用在生產(chǎn)環(huán)境中.截至2019年，Spark最大的集群已有8 000節(jié)點，單個job處理的數(shù)據(jù)量可達到數(shù)千萬億字節(jié)[4].在進行數(shù)據(jù)分析時，用戶經(jīng)常使用的接口是Spark SQL[5].Spark SQL接收用戶輸入的SQL語句，將其翻譯成由RDD(resilient distributed dataset)[3]構(gòu)成的有向無環(huán)圖(directed acyclic graph, DAG)，提交給Spark執(zhí)行引擎執(zhí)行.

RDD[3]是Spark中對分布式數(shù)據(jù)集的基本抽象.Partition是RDD中數(shù)據(jù)在集群節(jié)點間分布的最小粒度，也是RDD在集群上被并行處理的基本粒度.一個Spark SQL的查詢，會被翻譯成查詢計劃.查詢計劃是一棵算子樹(operator tree).算子樹上的每個節(jié)點是一個算子(operator),表示對數(shù)據(jù)的一種操作。比如，F(xiàn)ilter算子表示基于條件對數(shù)據(jù)篩選，Sort算子表示基于屬性對數(shù)據(jù)排序.算子樹會被轉(zhuǎn)化為由多個RDD組成的有向無環(huán)圖(DAG).Spark的DAG Scheduler按照相鄰RDD間是否需要數(shù)據(jù)重分布(repartition)，將DAG劃分為一到多個Stage.每個Stage包含對數(shù)據(jù)集的一部分操作.對每個Stage，Spark在集群中啟動一到多個任務(wù)(task)，每個任務(wù)處理一個Partition內(nèi)的數(shù)據(jù).

在實際的數(shù)據(jù)分析場景中，存在著很多重復(fù)計算.尤其是在交互式查詢中，查詢語句之間可能僅僅是參數(shù)不同，后續(xù)查詢語句通常會根據(jù)之前的查詢結(jié)果不斷修正參數(shù).Microsoft研究表明[6]，其日志挖掘應(yīng)用中約有30%的重復(fù)計算，其內(nèi)部數(shù)據(jù)分析平臺SCOPE上有80%的重復(fù)計算[7].近年來，有很多研究工作都致力于減少重復(fù)計算[7-20]，以減少資源的浪費，提升系統(tǒng)的性能.

減少重復(fù)計算通常有2種方式：合并公共計算和數(shù)據(jù)重用技術(shù).合并公共計算[20-22]針對并發(fā)查詢場景，將并發(fā)執(zhí)行的查詢?nèi)蝿?wù)之間相同的部分加以合并，使得相同部分只需計算一次，計算結(jié)果傳遞給各個查詢.但它只適用于并發(fā)場景下，使用范圍非常有限.數(shù)據(jù)重用技術(shù)則是將重復(fù)計算的結(jié)果保存下來，供后續(xù)計算重用.在選擇數(shù)據(jù)保存時，有人工選擇[23-25]和系統(tǒng)自動選擇[9-14]2種方式.相比之下，自動選擇方式有著更大的靈活性與準確度.自動數(shù)據(jù)重用技術(shù)最初用于傳統(tǒng)數(shù)據(jù)庫，如Vectorwise[9]，MonetDB[10]，Microsoft SQL Server[16]等.后來這一技術(shù)也被應(yīng)用于大數(shù)據(jù)處理平臺，如PigReuse[20]，CloudView[7]等.這些研究表明，自動數(shù)據(jù)重用技術(shù)能夠帶來性能收益.對于單條查詢來說，可達到10%～80%的性能提升[9]，從整個系統(tǒng)來看，可達到30%的性能提升[26].

Spark也實現(xiàn)了2種數(shù)據(jù)重用：RDD緩存和共享文件.這2種方式都依賴于用戶選擇緩存數(shù)據(jù)，屬于人工選擇緩存數(shù)據(jù)的方式，且在Spark SQL場景下有著一定的局限性：1)RDD緩存只能用于相同RDD對象之間的數(shù)據(jù)重用.而用戶每提交一條SQL語句，都會產(chǎn)生新的RDD DAG，即使提交相同的SQL語句，也會產(chǎn)生不同的RDD對象，因此該方式對查詢語句之間的重用計算無效.2)共享文件的緩存單位是RDD粒度，在數(shù)據(jù)規(guī)模較大時不能很好地利用緩存空間，且會導(dǎo)致頻繁替換，緩存效率較低.

為了減少重復(fù)計算，本文將自動數(shù)據(jù)重用技術(shù)應(yīng)用在Spark SQL中.自動數(shù)據(jù)重用技術(shù)需要解決4個關(guān)鍵問題：重復(fù)計算的識別、數(shù)據(jù)緩存位置、緩存數(shù)據(jù)的選擇和數(shù)據(jù)重用粒度.在已有的工作中，這4個關(guān)鍵問題都有著不同的解決方案.

在重復(fù)計算的識別上，主要是通過查詢匹配與改寫來識別重復(fù)計算.查詢匹配目前主要有3種方法：SQL字符串匹配[27]、規(guī)范化查詢模板[11,13,15]和基于算子的匹配[9,28].前2種方式都只能重用整條查詢的執(zhí)行結(jié)果，而基于算子的匹配能重用查詢的中間結(jié)果，重用機會大.另外，不同的SQL語句可以表示相同的計算，而SQL字符串匹配不能識別出這類重復(fù)計算.規(guī)范化查詢模板則由于表達能力的限制，導(dǎo)致能夠識別出重復(fù)計算有限.本文采用基于算子的匹配，以識別出更多的重復(fù)計算.

在重用數(shù)據(jù)的緩存位置上，已有的工作都是使用單一介質(zhì)(內(nèi)存或者磁盤)[9-15].但是在大數(shù)據(jù)場景下，內(nèi)存容量小、磁盤數(shù)據(jù)傳輸速度慢，都存在一定的局限性.本文采用混合介質(zhì)存儲以揚長避短，最大化系統(tǒng)的重用收益.

在緩存數(shù)據(jù)的選擇上，基于規(guī)則的選擇[13-14]考慮的因素較為單一，相比之下，基于收益模型的選擇[9-12]能夠更為準確地評估數(shù)據(jù)的重用價值.但是，現(xiàn)有的收益模型都沒有考慮數(shù)據(jù)讀寫引入的時間開銷，也沒有考慮混合存儲介質(zhì)上數(shù)據(jù)速度的不同，因此現(xiàn)有的模型都不能準確地評估重用收益.本文提出了新的重用收益模型，不僅考慮了數(shù)據(jù)讀寫的時間開銷，而且針對混合介質(zhì)，考慮了在不同介質(zhì)上數(shù)據(jù)讀寫時間的差異，能夠更為準確地評估數(shù)據(jù)的重用收益.

在數(shù)據(jù)重用粒度上，傳統(tǒng)數(shù)據(jù)庫中多采用算子粒度重用[9-13].算子粒度重用是把算子執(zhí)行的結(jié)果緩存下來，緩存替換時以一個算子的完整執(zhí)行結(jié)果為粒度進行替換.在分布式場景下，算子的計算結(jié)果由分布于多臺機器上的Partition組成.本文提出了Partition粒度的數(shù)據(jù)重用，即數(shù)據(jù)重用和緩存替換都是以Partition為粒度.在分布式場景下，所有機器上緩存空間不會同時耗盡.只要有一臺機器的緩存耗盡，算子粒度就需要替換某個(或某些)算子的所有Partition.而Partition粒度則只需替換緩存耗盡的那個機器上的Partition.因此，相比于算子粒度，Partition粒度的數(shù)據(jù)重用能減少不必要的替換，提高數(shù)據(jù)的緩存效率和緩存空間的利用率.

基于以上分析，針對Spark SQL，本文提出了基于收益模型的自動數(shù)據(jù)重用機制.針對混合介質(zhì)，提出了感知異構(gòu)介質(zhì)的收益模型用于自動識別重用收益大的數(shù)據(jù)，并采用細粒度的數(shù)據(jù)重用方式以提高數(shù)據(jù)的緩存效率及緩存空間的利用率，充分發(fā)揮數(shù)據(jù)重用的優(yōu)勢.基于Spark SQL和TackyonFS，本文實現(xiàn)了具有數(shù)據(jù)重用功能的Criss系統(tǒng)，能夠根據(jù)歷史負載自動識別出重復(fù)計算，并基于收益模型選擇重用收益大的數(shù)據(jù)自動緩存，供后續(xù)計算重用，提升系統(tǒng)的查詢處理性能.實驗結(jié)果表明，Criss的查詢性能比原始Spark SQL提升了46%～68%.

1 基于收益模型的數(shù)據(jù)重用機制

數(shù)據(jù)重用的前提是識別出重復(fù)計算.在傳統(tǒng)數(shù)據(jù)庫中，基于算子的匹配與改寫方案在重復(fù)計算的識別度、重用機會和匹配開銷方面都有較好的表現(xiàn)，本文采用這種方案，將其應(yīng)用在大數(shù)據(jù)場景下.

為了在有限空間中緩存重用價值大的數(shù)據(jù)，本文提出了針對混合介質(zhì)的收益模型用于評估數(shù)據(jù)的重用收益.一方面，基于大數(shù)據(jù)場景，采用混合介質(zhì)構(gòu)建緩存空間，相比于內(nèi)存，提供更多的容量；相比于磁盤，在一定程度上提高數(shù)據(jù)的讀寫速度，從而提高系統(tǒng)整體的性能收益.另一方面，針對混合介質(zhì)，提出一種感知異構(gòu)存儲介質(zhì)的收益模型用于選擇重用數(shù)據(jù)以及緩存數(shù)據(jù)的管理.

在數(shù)據(jù)重用粒度上，目前的方案都是算子粒度的數(shù)據(jù)重用，然而，在分布式場景下，算子的計算結(jié)果由分布于多個機器的Partition組成，且這些Partition是并行處理的，這使得細粒度的數(shù)據(jù)重用成為可能，因此，本文提出了基于Partition粒度的數(shù)據(jù)緩存與重用策略，以提高緩存效率及緩存空間的利用率.

基于以上思路，本文設(shè)計了具有數(shù)據(jù)重用功能的查詢處理系統(tǒng)，其系統(tǒng)架構(gòu)如圖1所示.在將查詢語句翻譯成查詢計劃(算子樹)后，將查詢計劃與歷史查詢負載進行匹配以識別重復(fù)計算.而且，根據(jù)匹配結(jié)果，對查詢計劃進行修改.

Fig. 1 System architecture圖1 系統(tǒng)架構(gòu)

對于查詢計劃中的每個算子，其修改體現(xiàn)在3個方面：

1) 是否自動緩存計算結(jié)果.根據(jù)收益模型計算重用收益，對于重用收益大的算子，在執(zhí)行過程中自動緩存其結(jié)果.

2) 是否進行數(shù)據(jù)重用.若算子的計算結(jié)果已在緩存空間中，則修改其計算邏輯為從緩存空間中讀取數(shù)據(jù)，而無需再進行重復(fù)的計算.

3) 是否需要收集統(tǒng)計信息.在選擇計算結(jié)果進行緩存時，依據(jù)的標準是收益模型，而收益模型在計算重用收益時需要獲得算子的統(tǒng)計信息，因此需要在執(zhí)行過程中添加統(tǒng)計信息收集功能.為了減少信息收集的開銷，對于已經(jīng)有統(tǒng)計信息的算子，在執(zhí)行過程中不必收集.

對查詢計劃修改之后，將其提交給執(zhí)行引擎.執(zhí)行引擎根據(jù)情況進行相應(yīng)的操作：或?qū)⑺阕拥挠嬎憬Y(jié)果緩存起來，或直接讀取緩存中的數(shù)據(jù)，或收集算子的統(tǒng)計信息.緩存空間采用內(nèi)存和磁盤混合存儲.數(shù)據(jù)在緩存空間足夠時直接存放，優(yōu)先存放在內(nèi)存.空間不足時進行替換.對于磁盤中的數(shù)據(jù)，當(dāng)其重用收益增大時，考慮將其遷入內(nèi)存.為了在有限空間中緩存重用收益大的數(shù)據(jù)，還需要對緩存數(shù)據(jù)進行管理.

下面從重復(fù)計算的識別、收益模型(包括信息收集)、數(shù)據(jù)緩存、數(shù)據(jù)重用和緩存數(shù)據(jù)管理5個方面介紹本文的數(shù)據(jù)重用機制.

1.1 重復(fù)計算的識別

本文采用基于算子的匹配與改寫方案識別重復(fù)計算，使用一個樹結(jié)構(gòu)(QTree)存儲歷史負載.QTree中每個節(jié)點表示一個算子，包含一個全局ID、算子的信息及其統(tǒng)計信息.其中，ID與緩存空間中的數(shù)據(jù)一一對應(yīng)，用于緩存數(shù)據(jù)定位；算子信息用于算子匹配；統(tǒng)計信息用于收益模型.

當(dāng)系統(tǒng)新接收1條查詢語句時，將其查詢計劃與QTree中保存的歷史查詢計劃進行匹配，找出重復(fù)計算，進而找到可以重用的數(shù)據(jù).匹配采用自底向上的方式進行，因為只有子算子都匹配成功，才能保證父算子的輸入數(shù)據(jù)相同，這時再對父算子進行匹配.如果匹配成功，就認為該算子與QTree上算子的計算結(jié)果相同，它可以重用QTree上算子的計算結(jié)果.對于匹配成功的算子，只需更新相應(yīng)算子的統(tǒng)計信息；對于匹配不成功的算子，將其插入QTree中.圖2顯示了系統(tǒng)在接收2條查詢計劃時QTree的變化情況.初始時QTree為空，只有1個根節(jié)點.用戶提交第1條查詢計劃時，其算子都未在QTree上找到匹配算子，因此，將第1條查詢計劃的所有算子都插入QTree.當(dāng)用戶提交第2條查詢計劃時，Project和Scan算子都在QTree上找到匹配算子，而Aggregate未找到匹配算子，只需將它插入QTree中.

Fig. 2 An example of QTree structure圖2 QTree組織結(jié)構(gòu)示例

1.2 收益模型

收益模型用于評估數(shù)據(jù)的重用收益.從理論上來講，數(shù)據(jù)每被重用1次，獲得的收益為算子的計算時間Texec與直接重用算子結(jié)果的時間Tload的差值.在算子引用次數(shù)為ref的情況下，緩存數(shù)據(jù)的重用收益為ref×(Texec-Tload).在自動數(shù)據(jù)重用技術(shù)下，有重用價值的數(shù)據(jù)被自動緩存下來，因此緩存數(shù)據(jù)的重用收益還需減去數(shù)據(jù)寫入緩存的時間開銷Tstore，即ref×(Texec-Tload)-Tstore.其中Tload和Tstore分別為數(shù)據(jù)加載(從緩存中讀取)和存儲(寫入緩存)的時間.它們可以通過算子結(jié)果的數(shù)據(jù)量size除以存儲介質(zhì)帶寬bw近似計算得到，即Tload=Tstore=sizebw.而Texec需要在運行時收集算子的執(zhí)行時間.另一方面，算子通常具有時間局部性，最近出現(xiàn)過的算子越有可能再次出現(xiàn)，緩存其結(jié)果帶來的重用收益就越大，即最近訪問時間與重用收益成正相關(guān).算子的最近訪問時間recency為當(dāng)前時間與系統(tǒng)啟動時間的差值.綜上所述，本文構(gòu)建的收益模型為

Benefit=recency×(ref×(Texec-Tload)-Tstore)=

recency×(ref×(Texec-sizebw)-sizebw).

收益模型的建立依賴于統(tǒng)計信息，因此系統(tǒng)還需要具有信息收集的功能.其中，算子的引用次數(shù)ref和最近訪問時間recency在進行查詢計劃匹配時可以得到；算子的計算時間Texec和計算結(jié)果的數(shù)據(jù)量size在運行時獲??；存儲帶寬bw可以根據(jù)系統(tǒng)環(huán)境獲取.

由于本文使用混合介質(zhì)構(gòu)建緩存空間，根據(jù)存儲介質(zhì)的不同，在計算重用收益時帶寬的設(shè)置不一樣.系統(tǒng)中有3個地方需要計算重用收益：

1) 選擇自動緩存結(jié)果的算子.根據(jù)統(tǒng)計信息計算重用收益，選擇重用收益大的算子在此次執(zhí)行過程中自動緩存其結(jié)果.由于計算收益時結(jié)果尚未緩存，無法得知將會被緩存在何種介質(zhì)上.為了減少緩存開銷，本文基于最壞的情況考慮，即假設(shè)數(shù)據(jù)會被緩存在磁盤，若此時數(shù)據(jù)的重用收益仍然很高，本文才會進行緩存，因此在選擇自動緩存結(jié)果的算子時帶寬設(shè)置為磁盤帶寬.

2) 緩存空間不足進行替換時.本文采用基于收益模型的數(shù)據(jù)管理策略，優(yōu)先緩存重用收益大的算子結(jié)果.在替換過程中需要計算重用收益.對于緩存空間中已有的數(shù)據(jù)，根據(jù)其具體的緩存位置設(shè)置帶寬；對于當(dāng)前待緩存的數(shù)據(jù)，根據(jù)其候選存儲位置設(shè)置相應(yīng)的帶寬.

3) 磁盤數(shù)據(jù)遷入內(nèi)存時.負載的變化會導(dǎo)致算子的重用收益發(fā)生變化，緩存在磁盤中的數(shù)據(jù)的重用收益可能會大于內(nèi)存中的數(shù)據(jù)，例如算子引用次數(shù)增多.因此，當(dāng)重用磁盤中的數(shù)據(jù)時，考慮將其遷入內(nèi)存.此時需要重新計算重用收益，帶寬設(shè)置為內(nèi)存帶寬，即假設(shè)將其存放在內(nèi)存能夠帶來的重用收益，以此去跟內(nèi)存中數(shù)據(jù)的重用收益相比較，當(dāng)內(nèi)存空間充足或者通過替換可以釋放足夠空間時，將此數(shù)據(jù)遷入內(nèi)存.

1.3 數(shù)據(jù)緩存

數(shù)據(jù)緩存包含2個方面的內(nèi)容，選擇重用收益大的數(shù)據(jù)在查詢執(zhí)行過程中自動緩存以及為數(shù)據(jù)建立算子索引.

1) 選擇數(shù)據(jù)緩存的依據(jù)是收益模型.對于當(dāng)前執(zhí)行的查詢語句，對其查詢計劃樹中的每個算子的重用收益進行評估，緩存各分支重用收益最大的算子.

2) 為數(shù)據(jù)建立算子索引.由于數(shù)據(jù)緩存下來的目的是為了后續(xù)重用，因此需要有一種方式能夠根據(jù)算子找到對應(yīng)的緩存數(shù)據(jù)，本文為歷史負載中的每個算子生成一個唯一的ID標識，在緩存算子的數(shù)據(jù)時，建立算子ID與其數(shù)據(jù)之間的關(guān)聯(lián).

1.4 數(shù)據(jù)重用

在改寫查詢計劃時，對于每個算子，先根據(jù)其ID在緩存空間中尋找數(shù)據(jù).若找到，則改寫查詢計劃為從緩存空間中加載數(shù)據(jù).本文的數(shù)據(jù)重用是基于Partition粒度的，可能存在一個算子只有部分Partition數(shù)據(jù)在緩存空間的情況.所以在進行數(shù)據(jù)重用時，使用bitmap表示算子的每個Partition的數(shù)據(jù)是否可以重用.若可以重用，則直接讀取緩存空間中的數(shù)據(jù)，否則進行重新計算.

1.5 緩存數(shù)據(jù)管理

本文利用混合介質(zhì)構(gòu)建緩存空間，并采用基于收益模型的Partition粒度緩存管理策略.當(dāng)空間充足時，數(shù)據(jù)優(yōu)先存放在內(nèi)存，其次存放在磁盤.當(dāng)空間不足時，進行替換.數(shù)據(jù)存儲的基本單位是Partition.因此還需要維護緩存空間Partition的信息.數(shù)據(jù)的重用收益會發(fā)生變化，因此對于磁盤上的數(shù)據(jù)，當(dāng)其重用收益增大時，考慮將其遷入內(nèi)存.下面將從寫入策略、替換策略、Partition信息的維護和磁盤數(shù)據(jù)遷入內(nèi)存4個方面介紹本文的方案.

1) 寫入策略.數(shù)據(jù)寫入的基本單位是Partition.為Partition的所有數(shù)據(jù)申請空間，若內(nèi)存空間足夠，則將其放入內(nèi)存；當(dāng)內(nèi)存空間不足時有2種選擇，即替換內(nèi)存中的數(shù)據(jù)和存放在磁盤.由于本文基于收益模型進行替換，在替換時需要獲取緩存空間所有數(shù)據(jù)的重用收益，替換出重用收益小的數(shù)據(jù)，替換開銷較大.因此本文采用后一種方案，當(dāng)內(nèi)存空間不足時將數(shù)據(jù)存放在磁盤，若磁盤空間仍不足，則表示申請空間失敗，需要進行替換.

2) 替換策略.當(dāng)空間不足時，根據(jù)收益模型替換緩存空間中重用收益小的算子結(jié)果，優(yōu)先替換內(nèi)存中的數(shù)據(jù).若不能滿足空間需求，則替換磁盤中的數(shù)據(jù).內(nèi)存中被替換出的數(shù)據(jù)存放在磁盤，磁盤中被替換的數(shù)據(jù)直接刪除.

3) Partition信息的維護.在替換時根據(jù)收益模型替換出重用收益小的Partition.收益模型依賴于統(tǒng)計信息，因此在緩存空間中需要維護Partition的統(tǒng)計信息.另外，還需要建立Partition與數(shù)據(jù)之間的關(guān)聯(lián)，從而保證正確的替換.

4) 磁盤數(shù)據(jù)遷入內(nèi)存.當(dāng)磁盤中數(shù)據(jù)的重用收益增大時會考慮將其遷入內(nèi)存.具體方法是從內(nèi)存申請所需空間，若空間不足，則觸發(fā)內(nèi)存替換.通過替換仍不能滿足要求時，則放棄遷入內(nèi)存.如果能夠緩存在內(nèi)存，那么就將磁盤中的數(shù)據(jù)移動到內(nèi)存.

2 Criss系統(tǒng)實現(xiàn)

本文基于Spark SQL平臺實現(xiàn)了第1節(jié)中的數(shù)據(jù)重用方案，該系統(tǒng)稱為Criss系統(tǒng)，如圖3所示：

Fig. 3 The implementation of Criss system圖3 Criss系統(tǒng)實現(xiàn)圖

Criss系統(tǒng)對Spark SQL的修改主要體現(xiàn)在4個方面：

1) 增加Query Graph組件用于識別重復(fù)計算.Query Graph維護系統(tǒng)的歷史負載，負責(zé)對翻譯后的查詢計劃進行匹配與改寫.由于查詢計劃的改寫依賴于收益模型，在Query Graph中還需維護算子的統(tǒng)計信息.

2) Spark SQL根據(jù)改寫后的查詢計劃生成新的RDD DAG.添加信息收集、數(shù)據(jù)重用、計算結(jié)果自動緩存3個功能.

3) 在Spark執(zhí)行引擎中添加統(tǒng)計信息收集功能，統(tǒng)計信息用于收益模型.

4) 利用TachyonFS[29]存儲重用數(shù)據(jù).TachyonFS是一個基于內(nèi)存的分布式文件系統(tǒng)，且提供分層存儲的功能[30].用戶可以配置使用內(nèi)存、SSD和磁盤中的一種或者多種介質(zhì).為了實現(xiàn)基于收益模型的Partition粒度緩存數(shù)據(jù)管理策略，還需要對TachyonFS進行修改.

在Criss系統(tǒng)中，SQL語句的執(zhí)行流程為：

1) Spark SQL接收用戶輸入的SQL語句，將其翻譯成查詢計劃.

2) 將查詢計劃發(fā)送給Query Graph組件進行匹配，Query Graph根據(jù)歷史負載對查詢計劃進行改寫，即標記每個算子是否自動緩存計算結(jié)果、是否進行數(shù)據(jù)重用、是否收集運行時信息.

3) Spark SQL接收到改寫后的物理計劃后生成新的RDD DAG.對于需要自動緩存計算結(jié)果的算子，設(shè)置其輸出RDD的StorageLevel為OFF_HEAP，表示將計算結(jié)果存在Tachyon上；對于可以重用數(shù)據(jù)的算子，生成新的RDD從緩存空間加載數(shù)據(jù)；對于需要收集運行時信息的算子，在其執(zhí)行邏輯中插入具有信息收集功能的代碼.

4) 將上一步生成的RDD DAG提交給執(zhí)行引擎執(zhí)行，根據(jù)RDD的執(zhí)行邏輯進行統(tǒng)計信息收集、數(shù)據(jù)重用和計算結(jié)果緩存.在緩存數(shù)據(jù)時，若空間不足會產(chǎn)生替換，替換的依據(jù)是收益模型，優(yōu)先保存重用收益大的數(shù)據(jù)，因此TachyonFS還需從Query Graph處獲取統(tǒng)計信息.當(dāng)有需要收集統(tǒng)計信息的算子時，在Query執(zhí)行完后會將統(tǒng)計信息發(fā)送給Query Graph進行更新.

2.1 物理計劃改寫

本文在Spark SQL系統(tǒng)中添加新的組件Query Graph用于識別重復(fù)計算.識別重復(fù)計算需要存儲歷史查詢負載.在Query Graph中采用如1.1節(jié)所述的樹結(jié)構(gòu)QTree來存儲.

除了存儲歷史查詢負載以識別重復(fù)計算之外，Query Graph還需要根據(jù)識別的結(jié)果對當(dāng)前查詢計劃進行改寫，包括：1)為匹配成功的算子添加數(shù)據(jù)重用功能；2)選擇此次執(zhí)行過程中需要自動緩存的計算結(jié)果；3)為沒有統(tǒng)計信息的算子添加信息收集功能.為此，在當(dāng)前查詢計劃的每個算子中添加3個布爾類型的屬性(reuse，cache，collect)，分別表示在執(zhí)行過程中是否重用數(shù)據(jù)、是否自動緩存數(shù)據(jù)、是否收集運行時統(tǒng)計信息.另外，算子還需包含一個全局唯一的ID，QTree中的算子亦使用此ID.當(dāng)算子可以重用數(shù)據(jù)時，根據(jù)此ID即可在緩存空間中找到對應(yīng)數(shù)據(jù).當(dāng)算子的計算結(jié)果需要自動緩存時，此ID決定了數(shù)據(jù)在緩存空間中存放位置(文件名)；當(dāng)需要收集運行時統(tǒng)計信息時，此ID保證了在任務(wù)執(zhí)行完后將統(tǒng)計信息保存在QTree中相應(yīng)的節(jié)點.

對于算子不完全匹配的情況，本文通過改寫查詢計劃創(chuàng)造出數(shù)據(jù)重用機會.對于Project算子，當(dāng)前待匹配算子記為A.若在QTree中存在類型為Project的算子B，使得算子A的Project條件為算子B的Project條件的子集，且算子B的數(shù)據(jù)已在緩存中，則表示算子A的結(jié)果可以在算子B結(jié)果的基礎(chǔ)上再次進行Project操作得到.為此，查詢計劃改寫為在算子A與其子算子之間插入新的算子B.

對于Exchange算子，其功能是對子算子的數(shù)據(jù)進行重劃分，并將劃分后的數(shù)據(jù)分發(fā)給不同的機器進行處理.例如根據(jù)連接操作的鍵(join key)進行劃分，那么不同表中具有相同連接操作鍵的記錄會被發(fā)送到相同的機器，使得連接操作在這些機器上可以并行執(zhí)行.在Spark SQL中用戶可以設(shè)置劃分的數(shù)目，若僅僅因為用戶設(shè)置數(shù)目的不同而導(dǎo)致Exchange算子的數(shù)據(jù)不能夠重用，則會喪失很多重用機會.為此本文在Exchange算子不匹配的情況下會判斷是否是因為劃分數(shù)目不同引起的.若是，則對查詢計劃進行改寫，在原Exchange算子和其子算子之間插入一個新的Exchange算子.

2.2 信息收集

收益模型中需要Texec和size運行時收集統(tǒng)計信息.然而，收集信息會在一定程度上影響查詢語句的執(zhí)行效率.為此本文只有在算子無統(tǒng)計信息時進行收集.對于需要收集統(tǒng)計信息的算子，在其執(zhí)行流程中插入信息統(tǒng)計功能代碼.

1) 任務(wù)內(nèi)部獨立收集統(tǒng)計信息.任務(wù)執(zhí)行時，在迭代過程中獲取算子從原始數(shù)據(jù)產(chǎn)生輸出每行數(shù)據(jù)的時間及輸出每行數(shù)據(jù)的數(shù)據(jù)量.

2) 匯總統(tǒng)計信息.由于任務(wù)在執(zhí)行完后會將執(zhí)行結(jié)果發(fā)送給Spark的任務(wù)調(diào)度器DAG Scheduler，調(diào)度器根據(jù)任務(wù)的執(zhí)行結(jié)果進行下一步的調(diào)度.利用這一點，本文對執(zhí)行結(jié)果的格式進行修改，將任務(wù)內(nèi)部收集的統(tǒng)計信息添加進執(zhí)行結(jié)果中發(fā)送給調(diào)度器.同時，本文在調(diào)度器里增加少量代碼，對各個任務(wù)的統(tǒng)計信息進行匯總.另外，本文對Spark SQL應(yīng)用程序的Driver進行了修改，在查詢計劃執(zhí)行完畢后，Driver從調(diào)度器中獲取統(tǒng)計信息，并發(fā)送給Query Graph模塊.Query Graph模塊根據(jù)ID對QTree中涉及到的算子的統(tǒng)計信息進行更新.

2.3 數(shù)據(jù)緩存

Query Graph在進行查詢計劃匹配時，對于在QTree中匹配節(jié)點有統(tǒng)計信息的算子，基于收益模型計算其重用收益.對于重用收益大的算子，將其cache屬性為true，表示在此次執(zhí)行過程中自動緩存.

對于需要自動緩存的算子，在生成RDD DAG片段時，設(shè)置其輸出RDD的StorageLevel為OFF_HEAP，表示在執(zhí)行過程中將數(shù)據(jù)緩存在Tachyon中.

原始Spark的OFF_HEAP方式只支持應(yīng)用程序內(nèi)同一RDD對象的數(shù)據(jù)重用.為了支持不同RDD對象數(shù)據(jù)的重用，本文擴展了Spark的OFF_HEAP緩存機制.對于在Spark SQL場景下需要自動緩存數(shù)據(jù)的RDD，更改其輸出RDD的name屬性為operator_operatorId_splitIndex，其中operatorId為算子在QTree中算子的ID，具有全局唯一性，因而可以用于不同RDD對象之間的數(shù)據(jù)重用.

本文將緩存數(shù)據(jù)存放在TachyonFS中，每個Partition的數(shù)據(jù)存為一個文件.緩存空間的數(shù)據(jù)組織如圖4所示，采用有3級目錄結(jié)構(gòu).全局目錄下存放算子目錄(operatorId)，算子目錄下存放Partition數(shù)據(jù)文件.

Fig. 4 Organization of cached data圖4 緩存空間數(shù)據(jù)組織方式

2.4 緩存數(shù)據(jù)管理

本文在Tachyon中實現(xiàn)基于收益模型的Parti-tion粒度的管理策略.為此，本文對Tachyon進行擴展，主要包括：

1) 寫入數(shù)據(jù)時以Partition為粒度.

2) 空間不足發(fā)生替換時以Partition為粒度，且替換依據(jù)為收益模型.

3) 向外提供將磁盤上的Partition數(shù)據(jù)遷入內(nèi)存的接口.當(dāng)引用次數(shù)增多導(dǎo)致磁盤數(shù)據(jù)的重用收益增大時，由上層Spark系統(tǒng)調(diào)用將其遷入到內(nèi)存，提高數(shù)據(jù)傳輸速度，進一步增加重用收益.

3 性能評測

為了評價數(shù)據(jù)重用機制在Spark SQL中的性能，本文采用TPC-H Benchmark[31]對Criss系統(tǒng)與原始Spark SQL系統(tǒng)的查詢性能進行評測，并對本文所提出的關(guān)鍵技術(shù)進行評測，包括混合介質(zhì)、收益模型和Partition粒度重用.通過與現(xiàn)有技術(shù)的對比，表明了本文所提出的方法更適合Spark SQL查詢分析.

3.1 測試負載及測試平臺

本文使用TPC-H來評測Criss系統(tǒng)的性能.測試中數(shù)據(jù)總量為100 GB.為了模擬實際場景中的重復(fù)計算，我們采用TPC-H的Query Stream的執(zhí)行模式，順序執(zhí)行100條查詢語句.由于實際應(yīng)用中，有些重復(fù)計算來自于多次執(zhí)行相同的查詢語句，另一些重復(fù)計算則來自于多條查詢之間有交集(即查詢計劃樹的一部分是相同的)，例如多條查詢都對同一張表做相同的篩選(Filter)或計算(Sort或Aggregation).為了評測不同的重復(fù)計算場景，我們用TPC-H的22條查詢語句構(gòu)造出100條查詢語句，分別模擬以下不同的場景：

1) Random-QS.該負載模擬局部性差的場景，即重復(fù)執(zhí)行的查詢語句呈隨機分布.從TPC-H的22條查詢語句中隨機選擇共100條語句.有的語句會重復(fù)多次，但不同語句的重復(fù)次數(shù)不相同，何時重復(fù)執(zhí)行也不相同.

2) Zipf-QS.該負載模擬局部性強的場景，即大部分操作都集中在少數(shù)的熱點查詢語句上.從TPC-H的22條查詢語句中按照Zipf分布選擇共100條語句.

3) Random-QS-v.該負載模擬查詢語句之間有交集的情形.對TPC-H中的每一條查詢語句，通過改變參數(shù)，產(chǎn)生與原始查詢語句匹配率約為60%和30%的2條語句，最終有66條查詢語句.然后，從這66條語句中隨機選擇共100條語句，并控制每條語句的出現(xiàn)不超過2次，以消除查詢語句完全匹配的影響.

本文的測試平臺為4臺物理機器搭建的Spark和Tachyon集群.每臺機器有12個物理核，32 GB內(nèi)存，3塊1 TB的數(shù)據(jù)盤，運行在64位CentOS系統(tǒng)上，內(nèi)核版本為2.6.32，Java版本為1.7.0.集群中1臺機器作為Spark和Tachyon的master節(jié)點，其余機器作為worker節(jié)點.原始數(shù)據(jù)存儲在HDFS中，對應(yīng)的Hadoop版本為2.2.0，塊大小設(shè)置為256 MB，副本數(shù)為3.Spark的版本為1.5.1，集群中1個節(jié)點上同時運行的任務(wù)數(shù)最多為16，每個節(jié)點內(nèi)存設(shè)置為30 GB，Shuffle時Partition總數(shù)目為200.Tachyon的版本為0.7.1，Block大小為128 MB.

3.2 重用收益評測

本小節(jié)對Criss系統(tǒng)的性能進行評測，使用如3.1節(jié)所述的3種負載，3種負載下算子的重復(fù)率分別為81%，85%，62%.緩存空間總?cè)萘吭O(shè)置為300 GB.在Random-QS和Zipf-QS負載下，內(nèi)存空間容量設(shè)置為3 GB.而在Random-QS-v負載下，算子的重復(fù)率較低，表明負載中對算子的訪問越分散，那么，由收益模型選擇進行自動緩存的數(shù)據(jù)就越多，因此內(nèi)存容量設(shè)置為18 GB.

圖5給出了Criss和Spark SQL在3種負載下的總執(zhí)行時間，Criss系統(tǒng)分別可以帶來約46%，68%，58%的性能提升.

Fig. 5 Reuse benefit evaluation圖5 重用收益評測

3.3 混合介質(zhì)評測

對于混合介質(zhì)策略，為了表明混合介質(zhì)相比于單一介質(zhì)更適合大數(shù)據(jù)場景，本文擴展了Criss系統(tǒng)，使其也可以使用內(nèi)存或者磁盤單一介質(zhì)構(gòu)建緩存空間，然后評測了Criss系統(tǒng)在3種配置下的性能表現(xiàn)：Criss-Hybrid，Criss-Disk，Criss-Mem，分別對應(yīng)于混合介質(zhì)、單一磁盤介質(zhì)和單一內(nèi)存介質(zhì).

如圖6所示，混合介質(zhì)存儲相比于單一磁盤能夠提升7%～13%的性能，相比于單一內(nèi)存能夠提升10%～27%的性能.

Fig. 6 Comparison of storage medium圖6 存儲介質(zhì)對比

在Criss系統(tǒng)中，會自動緩存重用收益大的算子的計算結(jié)果，重用這些算子的結(jié)果能減少重復(fù)計算，提升系統(tǒng)的性能.然而算子結(jié)果的緩存會帶來額外的開銷，體現(xiàn)在2個方面：1)將算子結(jié)果寫入緩存介質(zhì)上的存儲開銷.2)每緩存一個算子的結(jié)果就會減慢系統(tǒng)的執(zhí)行，這是因為Spark SQL的執(zhí)行是Pipeline方式.每獲取一行數(shù)據(jù)，就對其進行操作，而每緩存一個算子的結(jié)果意味著需要打破這種Pipeline執(zhí)行方式，先獲取算子的結(jié)果存入緩存介質(zhì)，然后再繼續(xù)后面的執(zhí)行任務(wù)，因此會減慢系統(tǒng)的執(zhí)行.

圖7～9分別顯示了3種負載在不同介質(zhì)下緩存空間的存儲和重用情況，分別從算子和數(shù)據(jù)量的角度進行了對比.由于Random-QS-v負載下緩存空間容量不足，會出現(xiàn)算子的部分Partition數(shù)據(jù)重用的情況，因此在此負載下僅對比了數(shù)據(jù)量.

Fig. 7 Cached and reused statistics of Random-QS圖7 Random-QS緩存空間存儲和重用情況

Fig. 8 Cached and reused statistics of Zipf-QS圖8 Zipf-QS緩存空間存儲和重用情況

從圖7～9中可以看出：

Fig. 9 Cached and reused statistics of Random-QS-v圖9 Random-QS-v緩存空間存儲和重用情況

1) 3種負載下，磁盤與混合介質(zhì)的表現(xiàn)都一致，但由于混合介質(zhì)把一部分數(shù)據(jù)存放在內(nèi)存，能夠節(jié)省這部分數(shù)據(jù)存入時的寫開銷以及重用時的讀開銷，因此系統(tǒng)整體性能高于磁盤.在3種負載下，混合介質(zhì)方案寫入內(nèi)存中的數(shù)據(jù)的比例和從內(nèi)存中重用數(shù)據(jù)的比例如表1所示:

Table 1Data Cached Ratio and Reused Ratio for

Hybrid Storage

表1 混合介質(zhì)方案下數(shù)據(jù)在內(nèi)存中的存儲及重用比例

%

2) 在Random-QS和Random-QS-v負載下，內(nèi)存比混合介質(zhì)緩存和重用了更少的算子結(jié)果.這2種負載下，使用單一內(nèi)存介質(zhì)時，緩存空間的容量成為瓶頸.從理論上來講，內(nèi)存緩存了更少的算子結(jié)果，節(jié)省了緩存開銷，但是重用更少的算子意味著更少的重用收益.

在Random-QS負載下，本文選取了在混合介質(zhì)和內(nèi)存配置下緩存情況不同而重用情況相同的Query集合以比較緩存開銷，選取了在2種配置下緩存情況相同而重用情況不同的Query集合以比較重用收益.實驗結(jié)果顯示，混合介質(zhì)相比于內(nèi)存額外重用算子結(jié)果所帶來的性能收益和額外緩存算子結(jié)果帶來的緩存開銷分別為84 min和5 min，額外緩存的算子結(jié)果帶來的重用收益大于其緩存開銷.而內(nèi)存受限于容量的大小不能緩存更多有價值的數(shù)據(jù)，因此性能低于混合介質(zhì).

在Random-QS-v負載下，混合介質(zhì)配置下由收益模型選擇需要緩存的數(shù)據(jù)總量已超出了緩存空間的容量，即需要緩存的數(shù)據(jù)總量至少為300 GB.而使用單一內(nèi)存介質(zhì)時，只能緩存18 GB的數(shù)據(jù)，占需緩存數(shù)據(jù)總量的比例不到6%，在存儲過程中發(fā)生了頻繁的替換，導(dǎo)致其存儲效率不高.本文選取重用情況相同而緩存情況不同的Query集合進行統(tǒng)計，發(fā)現(xiàn)在混合介質(zhì)配置下這些Query的執(zhí)行時間總和為1.7 h，而內(nèi)存配置下執(zhí)行時間總和為2.1 h，內(nèi)存的緩存開銷大于混合介質(zhì)，而內(nèi)存又重用了更少的數(shù)據(jù)，因此最終的性能不如混合介質(zhì).

3) 在Zipf-QS負載下，內(nèi)存比混合介質(zhì)緩存和重用了更多的算子結(jié)果.這是因為，根據(jù)1.2節(jié)的收益模型，緩存數(shù)據(jù)的開銷為Tstore=sizebw.在存儲介質(zhì)為內(nèi)存時，由于內(nèi)存帶寬大，因此會緩存大量的數(shù)據(jù)到內(nèi)存.而對于混合介質(zhì)，由于bw的計算是按照混合介質(zhì)帶寬的最壞情況，即磁盤帶寬進行計算的，因此在混合介質(zhì)中緩存的數(shù)據(jù)反而更少.而且，內(nèi)存額外緩存的3個算子結(jié)果中，只有一個后續(xù)被重用了，且重用時帶來的性能收益小于1 s，抵消不了其額外緩存數(shù)據(jù)的開銷，因此整體性能不如混合介質(zhì).

綜上所述，使用磁盤單一介質(zhì)時，緩存空間存儲與重用的情況與混合介質(zhì)一致，但由于其加載速度慢，緩存數(shù)據(jù)帶來的重用收益比混合介質(zhì)小，因此系統(tǒng)的整體性能不如混合介質(zhì)；使用內(nèi)存單一介質(zhì)時，在緩存空間容量充足的情況下，緩存開銷較大，在緩存空間容量不足的情況下，重用收益較小，因此系統(tǒng)的整體性能也不如混合介質(zhì).

3.4 收益模型評測

在選擇需要緩存的數(shù)據(jù)時，本文使用如1.2節(jié)所述的收益模型.與已有研究工作的收益模型不同的是，本文考慮了緩存數(shù)據(jù)讀寫時間的影響，能更為準確地評估重用收益.為了評測收益模型，本文將Recycler[9]的收益模型實現(xiàn)在Criss系統(tǒng)中.Recycler中使用ref×costsize表示數(shù)據(jù)的重用收益，其中ref表示算子的引用率,cost表示執(zhí)行時間,size表示數(shù)據(jù)量的大小.本節(jié)對本文的收益模型Criss-Benefit與Recycler中的收益模型Criss-Recycling進行了性能對比評測.

圖10顯示了負載在不同收益模型下的執(zhí)行時間，從圖10中可以看出，本文的收益模型Criss-Benefit相比于Recycler中的收益模型Criss-Recycling能夠提升10%～25%的性能.

為了進一步觀察本文收益模型的優(yōu)勢所在，圖11～13顯示了緩存空間數(shù)據(jù)緩存與重用的情況，與3.3節(jié)類似，對于Random-QS和Zipf-QS從算子

Fig. 10 Comparison of benefit model圖10 收益模型對比

角度和數(shù)據(jù)量2個角度進行對比，而對于Random-QS-v，僅從數(shù)據(jù)量角度進行對比.測試結(jié)果表明：

1) 在Random-QS和Zipf-QS負載下，Criss-Recycling均比Criss-Benefit緩存和重用了更多的算子結(jié)果.Criss-Recycling緩存了更多的算子結(jié)果，有更多的緩存開銷，然而，重用了更多的算子結(jié)果會有更多的重用收益.

本文選取了在2種收益模型配置下緩存情況不同而重用情況相同的Query集合以比較緩存開銷，選取了在2種配置下緩存情況相同而重用情況不同的Query集合以比較重用收益.2種負載下，Criss-Recycling相比于Criss-Benefit額外重用算子結(jié)果所帶來的性能收益以及額外緩存算子結(jié)果帶來的緩存開銷如表2所示.從表2可以看出Criss-Recycling額外緩存的算子結(jié)果帶來的緩存開銷大于性能收益，其收益模型緩存了很多重用價值低的數(shù)據(jù)，因此整體性能不如Criss-Benefit.

Fig. 11 Cached and reused statistics of Random-QS圖11 Random-QS緩存空間存儲和重用情況

Fig. 12 Cached and reused statistics of Zipf-QS圖12 Zipf-QS緩存空間存儲和重用情況

本文詳細分析了Random-QS負載下Criss-Recycling額外緩存的算子結(jié)果，發(fā)現(xiàn)其額外緩存數(shù)據(jù)的14個算子中，有13個在使用本文的收益模型時計算出的重用收益小于0，即計算開銷小于緩存開銷，而Criss-Benefit只緩存重用收益大于0的數(shù)據(jù)，相比之下，Criss-Recycling沒有這個限制，因此Criss-Recycling額外緩存了重用價值低的數(shù)據(jù)，這也說明了本文的收益模型能夠更為準確地選擇重用價值大的數(shù)據(jù).

Fig. 13 Cached and reused statistics of Random-QS-v圖13 Random-QS-v緩存空間存儲和重用情況

Table 2Extra Performance Gains and Cache Cost ofCriss-Recycling

表2 Criss-Recycling額外的性能收益及緩存開銷min

WorkloadPerformance Gain due to Reusing Data Performance Cost due to Caching DataRandom-QS930Zipf-QS1430

2) 在Random-QS-v負載下，Criss-Benefit與Criss-Recycling緩存的數(shù)據(jù)一致，但重用的算子結(jié)果比Criss-Recycling少.二者緩存的數(shù)據(jù)總量均達到了緩存空間的容量，緩存空間容量受限，根據(jù)收益模型選擇的算子結(jié)果不能夠全部存放，只能保留重用收益大的數(shù)據(jù)，不同收益模型對重用收益的評估標準不同，因此最后保留的數(shù)據(jù)也不一樣.

本文選取緩存情況相同而重用情況不同的Query集合進行統(tǒng)計以比較重用收益，發(fā)現(xiàn)在Criss-Recycling配置下這些Query的執(zhí)行時間總和為4.6 h，而在Criss-Benefit配置下執(zhí)行時間總和為3 h，Criss-Benefit的性能收益大于Criss-Recyling，說明Criss-Benefit在緩存空間中所保留數(shù)據(jù)的重用收益較大，顯示了本文收益模型的有效性.

3.5 重用粒度的評測

與算子粒度重用相比，Partition粒度重用能夠充分地利用緩存空間，提高存儲效率.為了對這2種重用粒度進行性能對比評測，本文在Criss系統(tǒng)中也實現(xiàn)了算子粒度重用(Criss-Operator).

圖14顯示了3種負載下本文的Partition粒度重用和算子粒度重用的性能，測試結(jié)果表明：

1) 在Random-QS和Zipf-QS負載下，Partition粒度重用只比算子粒度重用的性能稍好一些.這是因為，在空間充足的情況下，算子粒度重用只比Partition粒度重用多一些管理開銷，即需要等待算子的所有Partition都緩存下來，而Partition粒度重用則不需要.

2) 在Random-QS-v負載下，Partition粒度重用比算子粒度重用性能高49%.此時根據(jù)收益模型選擇的數(shù)據(jù)不能夠全部存放，算子粒度重用會引起頻繁的替換，導(dǎo)致緩存效率低及緩存空間利用率不高的問題.在此負載下，算子粒度比Partition粒度替換更多的數(shù)據(jù)，分別為76 GB和45 GB，因此存儲效率低.另外，本文觀察了Partition粒度下重用的118 GB數(shù)據(jù)，發(fā)現(xiàn)有25 GB的數(shù)據(jù)來自于算子的部分Partition被重用，算子的少量Partition被替換了出去.而在算子粒度下這些算子的所有Partition都會被替換出去，從而不能受益于大部分Partition的重用.本文選取緩存情況相同而重用情況不同的查詢語句進行統(tǒng)計，發(fā)現(xiàn)在Partition粒度下這些語句的執(zhí)行時間總和為1.7 h，而在算子粒度下執(zhí)行時間總和為4 h，說明算子粒度下所保留數(shù)據(jù)的整體重用收益較低.

Fig. 14 Comparison of reuse grain圖14 重用粒度對比

4 相關(guān)工作

4.1 重復(fù)計算的識別

識別重復(fù)計算是進行數(shù)據(jù)重用的前提，目前的研究工作主要是通過查詢匹配與改寫完成，查詢匹配用于識別完全相同的計算，查詢改寫能夠增加重用機會.查詢匹配目前主要有三大類方式:SQL字符串匹配、規(guī)范化查詢模板、基于算子的匹配.

1) SQL字符串匹配[17,27].SQL語句表達為符合一定語法的字符串，SQL字符串匹配是對多條SQL語句進行字符串匹配，如果它們的字符串相同，則說明它們是相同的計算.因此，只需要執(zhí)行其中一條語句，它的執(zhí)行結(jié)果就可以被其他語句重用.Shang[17]通過計算SQL字符串的Hash值來加速匹配，即僅當(dāng)Hash值匹配時才需對字符串進行匹配.這種方式雖然提高了匹配速度，但是，SQL字符串匹配只是查詢匹配的充分條件，即使2條SQL語句的字符串不相同，它們也可能執(zhí)行相同的計算.

2) 規(guī)范化查詢模板[11,13,15].這種方法是定義一個查詢模板，并按模板重寫每條查詢，即根據(jù)具體的查詢來填充模板中的各個元素.通過對重寫后的查詢語句進行匹配來識別重復(fù)計算.但是，與SQL字符串匹配類似，規(guī)范化查詢模板也是基于整條查詢語句的匹配.它們都只能重用查詢的最終結(jié)果，無法識別查詢語句間有交集的情形，無法重用查詢的中間結(jié)果.并且，不是所有的查詢都能用規(guī)范化模板來表示，因此，其應(yīng)用場景有限.例如，廣泛使用的連接查詢有多種類型，包括內(nèi)連接(inner join)、左外連接(left outer join)、完全外連接(full outer join)等.不同類型的連接查詢產(chǎn)生不同的計算結(jié)果，而Hawc[11]中的規(guī)范化模板并不能夠區(qū)分不同類型的連接查詢.

3) 基于算子的匹配[7,9,13,16,18,20,28].數(shù)據(jù)處理系統(tǒng)在執(zhí)行SQL查詢時，會將其翻譯成查詢計劃.查詢計劃是由算子組成的樹結(jié)構(gòu)，表示數(shù)據(jù)的處理流程.基于算子的匹配則是自底向上逐個匹配查詢計劃樹中的各個算子.算子匹配的條件是算子類型相同且表達式相同.算子匹配成功說明是相同的計算，即重復(fù)計算.與前面2種方法不同，基于算子的匹配能夠識別查詢語句間有交集的情形(稱為部分匹配)，即查詢計劃樹中的一部分是相同的計算.因此，該方法能夠重用查詢的中間結(jié)果，而不僅僅是整條查詢的最終結(jié)果.而且，查詢計劃樹表達了數(shù)據(jù)處理流程，即使2條查詢的SQL字符串不同，如果它們執(zhí)行相同的計算，它們的查詢計劃樹就是相同.因此，基于算子的匹配能夠識別出更多的重復(fù)計算.

鑒于基于算子的匹配有上面3個優(yōu)勢，本文的Criss系統(tǒng)采用該方法.

4.2 數(shù)據(jù)緩存位置

由于傳輸速度(即帶寬)不同，數(shù)據(jù)緩存在不同存儲介質(zhì)上帶來的重用收益也不同.內(nèi)存的帶寬高，但容量較小，能夠容納的緩存數(shù)據(jù)量較少，多用于單機場景[9-10,12,27].相比于內(nèi)存，磁盤雖然帶寬低，但其容量很大，能夠緩存更多的數(shù)據(jù)，因此更適合數(shù)據(jù)規(guī)模較大的場景，在傳統(tǒng)數(shù)據(jù)庫[11,13]和大數(shù)據(jù)平臺上[14-15,17]都有應(yīng)用.在大數(shù)據(jù)平臺上，大多利用HDFS來存儲緩存數(shù)據(jù).利用HDFS提供的文件接口，緩存和管理數(shù)據(jù)非常簡便.HDFS為了容錯采用了多副本機制.但是，在數(shù)據(jù)重用場景下數(shù)據(jù)丟失了可以重新計算，不必存儲多個副本.多副本機制對于數(shù)據(jù)重用場景來說反而導(dǎo)致了磁盤空間的浪費.

現(xiàn)有的數(shù)據(jù)重用只采用單一的存儲介質(zhì)，而對于緩存重用數(shù)據(jù)，內(nèi)存和磁盤各有其優(yōu)劣.本文的Criss系統(tǒng)采用混合存儲的方案，揚長避短，充分發(fā)揮各存儲介質(zhì)的優(yōu)勢，以提高系統(tǒng)的整體重用收益.具體來講，將重用收益大的數(shù)據(jù)存放在內(nèi)存，重用收益較小的數(shù)據(jù)存放在磁盤.在受益于內(nèi)存的高速數(shù)據(jù)傳輸能力的同時，利用磁盤緩存更多的數(shù)據(jù)，最大化緩存空間的重用收益.

4.3 緩存數(shù)據(jù)的選擇

緩存數(shù)據(jù)選擇方法主要有兩大類：基于規(guī)則的選擇和基于收益模型的選擇.

1) 基于規(guī)則的選擇.系統(tǒng)制定出一定的規(guī)則，在查詢執(zhí)行的過程中符合規(guī)則的計算結(jié)果都會被緩存下來[7,13-14,16,18].ReStore[14]根據(jù)算子類型選擇緩存數(shù)據(jù)，即選擇那些計算開銷大、輸入數(shù)據(jù)量大而結(jié)果數(shù)據(jù)量小的算子(例如Filter和Join)，將它們的計算結(jié)果進行緩存.但是，根據(jù)表達式的不同，算子會有多種形式，而這種方法對于同類算子沒有區(qū)分度.例如，F(xiàn)ilter算子在篩選條件很緊時，結(jié)果數(shù)據(jù)量才很小，重用收益才大.DynaMat[13]提出了3種規(guī)則，分別根據(jù)LRU,LFU和計算結(jié)果大小對緩存空間中的數(shù)據(jù)進行管理.SCOPE[7]，SQL Server[16]，SparkCruise[18]使用簡單的啟發(fā)函數(shù)(例如TopK)進行緩存數(shù)據(jù)選擇.這些方案考慮的因素都比較單一，往往不能選擇出最有價值的數(shù)據(jù)進行緩存.

2) 基于收益模型的選擇.根據(jù)多種因素，建立收益模型來評估計算結(jié)果的重用收益，根據(jù)重用收益大小進行緩存數(shù)據(jù)的管理，以提高緩存空間的整體重用收益.目前的研究工作中所考慮的因素有計算開銷[9-13,15,27]、算子類型[11]、數(shù)據(jù)量[9,12-13,27]、更新率[12]、引用次數(shù)[9,11,13]或者引用率[12,27]、最近訪問時間[11]等.例如，Recycler[8]中的收益模型為ref×costsize，其中ref表示計算結(jié)果的引用次數(shù)，cost表示計算結(jié)果的執(zhí)行時間，size表示計算結(jié)果的數(shù)據(jù)量.

相比于基于規(guī)則的選擇方法，基于收益模型的選擇方法能夠更為準確地評估數(shù)據(jù)的重用收益.但是，現(xiàn)有的收益模型都沒有考慮數(shù)據(jù)讀寫時間的影響.數(shù)據(jù)的每一次重用都需要從緩存介質(zhì)上讀取數(shù)據(jù)到應(yīng)用程序內(nèi)存，且在重用之前還需要將數(shù)據(jù)寫入緩存介質(zhì)上.在數(shù)據(jù)規(guī)模較大時，數(shù)據(jù)讀寫時間對重用性能的影響也較大.而且，數(shù)據(jù)讀寫時間，不僅與數(shù)據(jù)量有關(guān)，還受存儲介質(zhì)傳輸速度的影響.在不同的存儲介質(zhì)上數(shù)據(jù)讀寫時間是不相同的.現(xiàn)有的收益模型沒有考慮采用混合存儲介質(zhì)，也沒考慮不同介質(zhì)下的不同數(shù)據(jù)讀寫時間.本文提出了的重用收益模型，不僅考慮了數(shù)據(jù)讀寫時間的影響，而且針對混合介質(zhì)，考慮了不同介質(zhì)上數(shù)據(jù)讀寫時間的差異.因此，本文提出的收益模型更為精準.

4.4 數(shù)據(jù)重用粒度

在傳統(tǒng)數(shù)據(jù)庫中，多采用算子粒度的數(shù)據(jù)重用[7,9-13,16,27].查詢語句的查詢計劃樹中各算子產(chǎn)生的計算結(jié)果不可細分，只能作為一個整體存儲與重用.在進行數(shù)據(jù)替換時，也是以算子為單位進行，即算子的結(jié)果作為整體替換，而不能只替換算子結(jié)果的一部分.后來出現(xiàn)的分布式大數(shù)據(jù)處理平臺在應(yīng)用數(shù)據(jù)重用技術(shù)時，也沿用了基于算子粒度的方式[14-15,17-18,20].

在大數(shù)據(jù)場景下，基于算子粒度的重用方式逐漸凸顯出局限性.一方面，分布式大數(shù)據(jù)處理平臺采用并行處理，算子的計算結(jié)果是分布于集群中的多臺機器上，由很多Partition組成；另一方面，基于算子粒度的緩存管理不能充分利用所有機器上的緩存空間，降低系統(tǒng)的整體效率.因為集群中各個機器運行的任務(wù)并不一樣，它們處理的數(shù)據(jù)也不一樣，隨著不斷地執(zhí)行各種任務(wù)，各個機器上緩存空間的使用率通常是不相同的，有的機器緩存空間滿了，其他機器的緩存空間還充足.如果基于算子粒度的緩存就不能充分利用各個機器的緩存空間.而本文提出Partition粒度的數(shù)據(jù)重用，采用更細粒度的緩存替換，能夠更充分緩存空間，提到系統(tǒng)的整體效率.

4.5 其他重用方法

HashStash[19]提供了一種特別的重用角度，與其他相關(guān)工作和本文的方法都不同，它將重用的機會鎖定在算子內(nèi)部數(shù)據(jù)結(jié)構(gòu)——Hash表上，通過分析查詢計劃發(fā)現(xiàn)緩存Hash表的機會，并在查詢優(yōu)化階段對查詢計劃進行改寫，以重用緩存的Hash表.在選擇緩存的Hash表時，它也使用了基于收益模型的評估方法.

5 結(jié)束語

針對分布式大數(shù)據(jù)處理平臺，以減少重復(fù)計算為目標，本文提出了基于收益模型的數(shù)據(jù)重用機制：1)采用基于算子的匹配與改寫方法識別重復(fù)計算；2)針對混合介質(zhì)，提出一種新的收益模型，更為準確地評估數(shù)據(jù)的重用收益；3)利用數(shù)據(jù)集分布存儲的特性，提出了Partition粒度的數(shù)據(jù)重用，以提升數(shù)據(jù)的存儲效率和緩存空間的利用率.我們基于Spark SQL平臺實現(xiàn)了具有數(shù)據(jù)重用功能的Criss系統(tǒng).實驗結(jié)果表明，本文提出的數(shù)據(jù)重用技術(shù)顯著提升了查詢性能，與Spark SQL相比，查詢性能提升了46%～68%.