申毅杰 曾 丹 熊 勁

(計(jì)算機(jī)體系結(jié)構(gòu)國(guó)家重點(diǎn)實(shí)驗(yàn)室(中國(guó)科學(xué)院計(jì)算技術(shù)研究所) 北京 100190) (中國(guó)科學(xué)院大學(xué) 北京 100049)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.1 重復(fù)計(jì)算的識(shí)別

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

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

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

1.2 收益模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1) Spark SQL接收用戶(hù)輸入的SQL語(yǔ)句，將其翻譯成查詢(xún)計(jì)劃.

2) 將查詢(xún)計(jì)劃發(fā)送給Query Graph組件進(jìn)行匹配，Query Graph根據(jù)歷史負(fù)載對(duì)查詢(xún)計(jì)劃進(jìn)行改寫(xiě)，即標(biāo)記每個(gè)算子是否自動(dòng)緩存計(jì)算結(jié)果、是否進(jìn)行數(shù)據(jù)重用、是否收集運(yùn)行時(shí)信息.

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

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

2.1 物理計(jì)劃改寫(xiě)

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

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

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

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

2.2 信息收集

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 性能評(píng)測(cè)

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

3.1 測(cè)試負(fù)載及測(cè)試平臺(tái)

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

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

2) Zipf-QS.該負(fù)載模擬局部性強(qiáng)的場(chǎng)景，即大部分操作都集中在少數(shù)的熱點(diǎn)查詢(xún)語(yǔ)句上.從TPC-H的22條查詢(xún)語(yǔ)句中按照Z(yǔ)ipf分布選擇共100條語(yǔ)句.

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

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

3.2 重用收益評(píng)測(cè)

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

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

Fig. 5 Reuse benefit evaluation圖5 重用收益評(píng)測(cè)

3.3 混合介質(zhì)評(píng)測(cè)

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

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

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

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

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

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

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

從圖7～9中可以看出：

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

1) 3種負(fù)載下，磁盤(pán)與混合介質(zhì)的表現(xiàn)都一致，但由于混合介質(zhì)把一部分?jǐn)?shù)據(jù)存放在內(nèi)存，能夠節(jié)省這部分?jǐn)?shù)據(jù)存入時(shí)的寫(xiě)開(kāi)銷(xiāo)以及重用時(shí)的讀開(kāi)銷(xiāo)，因此系統(tǒng)整體性能高于磁盤(pán).在3種負(fù)載下，混合介質(zhì)方案寫(xiě)入內(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)存中的存儲(chǔ)及重用比例

%

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

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

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

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

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

3.4 收益模型評(píng)測(cè)

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

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

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

Fig. 10 Comparison of benefit model圖10 收益模型對(duì)比

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

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

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

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

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

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

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

Table 2Extra Performance Gains and Cache Cost ofCriss-Recycling

表2 Criss-Recycling額外的性能收益及緩存開(kāi)銷(xiāo)min

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

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

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

3.5 重用粒度的評(píng)測(cè)

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

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

1) 在Random-QS和Zipf-QS負(fù)載下，Partition粒度重用只比算子粒度重用的性能稍好一些.這是因?yàn)?，在空間充足的情況下，算子粒度重用只比Partition粒度重用多一些管理開(kāi)銷(xiāo)，即需要等待算子的所有Partition都緩存下來(lái)，而Partition粒度重用則不需要.

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

Fig. 14 Comparison of reuse grain圖14 重用粒度對(duì)比

4 相關(guān)工作

4.1 重復(fù)計(jì)算的識(shí)別

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.5 其他重用方法

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

5 結(jié)束語(yǔ)

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