楊 柳，金培權(quán)

(中國科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,安徽 合肥 230027)

1 引言

在傳統(tǒng)的存儲(chǔ)體系結(jié)構(gòu)中，存儲(chǔ)系統(tǒng)借助易失性內(nèi)存DRAM提供高性能的數(shù)據(jù)訪問，利用性能較差但價(jià)格低廉的固態(tài)硬盤SSD(Solid State Disk)或者硬盤HDD(Hard Disk Drive)保證數(shù)據(jù)的持久性。相變存儲(chǔ)器PCM(Phase Change Memory)、自旋矩傳輸磁性存儲(chǔ)器STT-RAM(Spin Transfer Torque RAM)和可變電阻式存儲(chǔ)器RRAM(Resistive RAM)等非易失內(nèi)存NVM(Non-Volatile Memory)引入到計(jì)算機(jī)系統(tǒng)后，對現(xiàn)有的存儲(chǔ)體系結(jié)構(gòu)帶來了極大的影響[1-3]。與SSD相比，NVM支持按位尋址，讀寫延遲低，而且可以直接被CPU存取，因此可以作為內(nèi)存使用；與DRAM相比，NVM掉電數(shù)據(jù)不丟失，且存儲(chǔ)密度更高，因此能夠支持海量的數(shù)據(jù)存儲(chǔ)。目前，NVM離實(shí)用場景越來越近。2019年4月，DIMM接口的NVM(傲騰DCPMM)已正式投放市場，單片容量可達(dá)512 GB且單機(jī)可支持高達(dá)8 TB的NVM容量(https://www.intel.cn/content/www/cn/zh/architecture-and-technology/optane-dc-persistent-memory.html)。

Figure 1 Possible architecture involving NVM

理論上，在內(nèi)存架構(gòu)中引入NVM后可能形成3種架構(gòu)(如圖1所示)。第1種用NVM完全替代DRAM，如圖1a所示。但是，由于NVM與DRAM相比具有訪問時(shí)延高、寫次數(shù)有限和寫功耗大等缺點(diǎn)[4]，完全用NVM替代DRAM從目前看不是最佳選擇。第2種是層次型架構(gòu)，如圖1b所示。這種架構(gòu)需要把DRAM作為NVM的緩存，而NVM則作為DRAM的第2級內(nèi)存。這一架構(gòu)主要存在2個(gè)方面的問題：首先，由于DRAM只是作為NVM的緩存，因此系統(tǒng)可見的內(nèi)存僅為NVM的空間，在內(nèi)存空間使用上不合算；其次，這一架構(gòu)只是利用了NVM比DRAM容量大的優(yōu)點(diǎn)，操作系統(tǒng)的數(shù)據(jù)訪問依然還是通過DRAM，沒有充分利用NVM的非易失性特點(diǎn)。第3種架構(gòu)是平行架構(gòu)，即NVM和DRAM同時(shí)作為同一層次的主存使用，如圖1c所示。在這種架構(gòu)下，系統(tǒng)可用的內(nèi)存空間等于DRAM的容量和NVM的容量之和，而且操作系統(tǒng)可以感知2類內(nèi)存的特性，可以充分利用DRAM和NVM各自的優(yōu)點(diǎn)。從目前DRAM和NVM的發(fā)展趨勢來看，DRAM和NVM并存的異構(gòu)混合內(nèi)存架構(gòu)更具有可行性和發(fā)展前景。無論采用哪種混合內(nèi)存架構(gòu)，出發(fā)點(diǎn)都是要盡可能地同時(shí)發(fā)揮DRAM和NVM的優(yōu)勢。

在未來理想的情況下，隨著NVM容量的逐步增加和成本的下降，在異構(gòu)混合內(nèi)存架構(gòu)中，我們可以只使用DRAM和NVM來構(gòu)建內(nèi)存數(shù)據(jù)庫系統(tǒng)，以支持高性能的在線處理與存儲(chǔ)，而磁盤(DISK)則成為離線的歸檔存儲(chǔ)設(shè)備。這種情況下，主存和DISK之間的I/O操作就不再是決定系統(tǒng)性能的主要因素，這對傳統(tǒng)的數(shù)據(jù)庫管理系統(tǒng)提出了新的挑戰(zhàn)。因?yàn)閭鹘y(tǒng)的數(shù)據(jù)庫管理系統(tǒng)以DRAM+DISK的架構(gòu)為基礎(chǔ)，絕大部分的數(shù)據(jù)結(jié)構(gòu)和算法都以減少DRAM和DISK之間的I/O操作為主要目標(biāo)，因此不適合基于DRAM和NVM的異構(gòu)混合內(nèi)存架構(gòu)。

基于上述背景，本文重點(diǎn)研究傳統(tǒng)數(shù)據(jù)庫管理系統(tǒng)中的排序連接算法在異構(gòu)混合內(nèi)存架構(gòu)上的優(yōu)化問題。傳統(tǒng)的排序連接算法如果直接移植到異構(gòu)混合內(nèi)存架構(gòu)上不能充分發(fā)揮DRAM和NVM的特性，因此必須針對架構(gòu)的特性進(jìn)行重新設(shè)計(jì)。本文詳細(xì)分析了異構(gòu)混合內(nèi)存架構(gòu)對排序連接算法帶來的挑戰(zhàn)，提出了基于鍵值分離和鍵值去重的C-Join算法，并進(jìn)一步提出了C-Join算法的3種實(shí)現(xiàn)方式。最后的實(shí)驗(yàn)結(jié)果表明，本文提出的C-Join算法在異構(gòu)混合內(nèi)存架構(gòu)上的性能明顯優(yōu)于傳統(tǒng)排序連接算法，并且有效降低了DRAM的使用代價(jià)?？傮w而言，本文的主要工作和貢獻(xiàn)可總結(jié)為如下幾個(gè)方面：

(1)針對NVM可字節(jié)尋址和低延遲的特性，采用鍵值分離策略重新實(shí)現(xiàn)了傳統(tǒng)的排序連接算法。從目前文獻(xiàn)看，本文提出的鍵值分離的混合內(nèi)存排序連接策略具有一定的新意。

(2)在鍵值分離策略的基礎(chǔ)上，進(jìn)一步提出了面向異構(gòu)混合內(nèi)存架構(gòu)的新的排序連接算法C-Join和鍵值去重機(jī)制，通過減少連接中重復(fù)的鍵值來降低連接過程的內(nèi)存開銷，從而減少CPU需要處理的數(shù)據(jù)量，最終提升連接算法的時(shí)間性能。

(3)討論了C-Join算法的不同實(shí)現(xiàn)方式，提出了3種可能的策略，并進(jìn)行了對比實(shí)驗(yàn)。結(jié)果表明，鍵值分離策略可以有效減少DRAM的使用，同時(shí)提高了算法的性能，而C-Join算法的幾種實(shí)現(xiàn)方式均能夠在保證時(shí)間性能的前提下保持較高的內(nèi)存空間利用率。

2 相關(guān)工作

2.1 非易失內(nèi)存技術(shù)

非易失內(nèi)存是一種新型的存儲(chǔ)介質(zhì)，它不同于存儲(chǔ)器和磁盤，屬于存儲(chǔ)級內(nèi)存，既具有磁盤的特點(diǎn)，又具有內(nèi)存的特點(diǎn)。與傳統(tǒng)的DRAM和SRAM不同，新興的非易失性內(nèi)存，如相變存儲(chǔ)器(PCM)、電阻式記憶體(ReRAM)和鐵電存儲(chǔ)器(FRAM)，使用電阻存儲(chǔ)器來存儲(chǔ)具有更高密度和近零泄漏功率的信息。因此，NVM有希望成為構(gòu)建下一代主存和緩存的有主要技術(shù)[1-5]。

這些非易失性內(nèi)存雖然制作材料和制作工藝不同，但卻有著相似的特性，如表1所示，以PCM為例，與DRAM、機(jī)械硬盤和固態(tài)硬盤進(jìn)行比較。(1)它們具有高密度和低延遲的特點(diǎn)；(2)它們可以字節(jié)訪問并持久化數(shù)據(jù)；(3)它們都具有讀寫固有的不對稱特性[4,5]，寫延遲比讀延遲大得多，并且寫操作相比讀操作會(huì)消耗更多的能量；(4)NVM通常具有有限的寫耐久性。因此，在使用NVM時(shí)，有必要減少甚至避免寫操作。

2.2 排序連接算法

排序連接算法一般指排序歸并連接算法。為了將2個(gè)輸入表數(shù)據(jù)按照連接鍵進(jìn)行排序，算法先對輸入進(jìn)行劃分，然后對每個(gè)劃分進(jìn)行排序后多路歸并得到最終的排序結(jié)果，最后遍歷2個(gè)排序后的表得到最終的連接結(jié)果[6]。排序歸并連接的時(shí)間代價(jià)主要集中在排序過程中，在此過程中算法會(huì)對磁盤進(jìn)行大量的讀寫操作。通常來說排序連接算法的時(shí)間性能會(huì)比哈希連接算法差，但是排序連接的通用性更好，因?yàn)楣＿B接一般只能解決等值連接問題，而排序連接可以處理非等值連接問題。當(dāng)遇到選擇度為M∶N的連接問題時(shí)，哈希連接更是無能為力，而排序連接則可以完美地解決這類問題。另外，當(dāng)數(shù)據(jù)庫中關(guān)于連接問題的表數(shù)據(jù)已經(jīng)按照連接鍵排好序時(shí)，采取排序連接算法也能獲得非常好的性能。

2.3 連接算法優(yōu)化

自20世紀(jì)70年代以來，數(shù)據(jù)庫連接算法得到了廣泛的研究。目前對連接算法的研究主要集中在硬件優(yōu)化、并發(fā)執(zhí)行等方面。Li等人[7]提出了面向閃存的DigestJoin算法，利用固態(tài)硬盤高速的隨機(jī)讀能力減少了中間結(jié)果和數(shù)據(jù)處理量。Balkesen等人[8]通過對不同算法和體系結(jié)構(gòu)的實(shí)驗(yàn)分析比較發(fā)現(xiàn)，對硬件進(jìn)行優(yōu)化和參數(shù)調(diào)優(yōu)仍然很重要，具有硬件意識的連接算法比硬件無關(guān)的算法性能更好。Albutiu等人[9]設(shè)計(jì)了一個(gè)新的基于部分分區(qū)排序的大規(guī)模并行排序歸并MPSM(Massively Parallel Sort-Merge)連接算法，證明了MPSM在具有數(shù)十億對象的大型內(nèi)存數(shù)據(jù)庫上的競爭性能。Viglas[10]提出了Segment Sort、Hybrid Sort和LazySort等算法，通過將寫多讀少和寫少讀多的排序算法結(jié)合在一起使用，采用以讀換寫的方式使得總體的讀寫代價(jià)達(dá)到最小，在整體性能可觀的同時(shí)減少了對NVM的寫操作。

一些研究者針對面向NVM的連接算法優(yōu)化開展了研究。文獻(xiàn)[11]中研究者提出了數(shù)據(jù)庫虛擬分區(qū)連接算法，該算法通過虛擬分區(qū)的方式，避免了數(shù)據(jù)庫分區(qū)時(shí)的拷貝過程，大大減少了數(shù)據(jù)庫連接算法執(zhí)行過程中對NVM的寫操作。文獻(xiàn)[12]則研究了多關(guān)系連接算法在NVM內(nèi)存環(huán)境中的優(yōu)化方法，作者提出的NVjoin算法利用抽樣估計(jì)得到中間結(jié)果數(shù)最小的連接次序，該連接次序使得對多個(gè)關(guān)系執(zhí)行連接時(shí)，使用最少的內(nèi)存空間，并且連接過程中對NVM讀寫總數(shù)最少。但是，這些方法都是針對NVM Only的架構(gòu)，不同于本文所針對的異構(gòu)混合內(nèi)存架構(gòu)。

Table 1 Comparison of several storage medias

在面向DRAM和NVM異構(gòu)混合內(nèi)存架構(gòu)的連接算法方面，Yang等人[13]在2019年提出了一種新的Hash連接算法BF-Join。BF-Join重新設(shè)計(jì)了Hash分區(qū)的數(shù)據(jù)結(jié)構(gòu)，使用NVM在Hash連接過程中存儲(chǔ)構(gòu)建表和探測表的數(shù)據(jù)，以避免向NVM寫入數(shù)據(jù)。BF-Join還引入了布隆過濾器來加速連接過程，并將布隆過濾器設(shè)計(jì)為一個(gè)Cacheline的大小，從而減少BF-Join連接過程中的緩存丟失。從現(xiàn)有文獻(xiàn)看，目前還沒有直接針對基于DRAM和NVM異構(gòu)混合內(nèi)存架構(gòu)排序連接算法的優(yōu)化工作。

3 C-Join算法

本節(jié)介紹面向異構(gòu)混合內(nèi)存架構(gòu)的新型排序連接算法C-Join。C-Join的主要設(shè)計(jì)思想包括2個(gè)方面，即鍵值分離和鍵值去重，下面分別加以討論。

3.1 鍵值分離策略

DRAM和NVM是2種各有特點(diǎn)的存儲(chǔ)設(shè)備，它們的優(yōu)勢和缺點(diǎn)也都很明顯。DRAM的讀寫性能非常好，但是受限于容量和能耗；NVM的容量能耗可觀，并且讀寫性能與DRAM相當(dāng)，但是讀寫不對稱且寫耐久有限。一個(gè)主要的問題是如何在基于DRAM和NVM混合內(nèi)存的系統(tǒng)中平衡二者的使用，以達(dá)到最優(yōu)的性價(jià)比和最佳的性能。NVM由于在寫入方面有著過多的局限(寫速度相對慢、寫能耗相對高、寫耐久有限)，所以不能作為經(jīng)常寫入的設(shè)備，與此同時(shí)DRAM就理所當(dāng)然地成為了處理數(shù)據(jù)結(jié)構(gòu)中需要經(jīng)常讀寫的內(nèi)存設(shè)備，而NVM的容量大的特點(diǎn)使得其更適合作為多讀的內(nèi)存存儲(chǔ)設(shè)備。

為了使排序連接算法適合異構(gòu)混合內(nèi)存架構(gòu)，本文首先提出基于鍵值分離策略的排序連接思路。通過鍵值分離，將一條記錄拆分為鍵(key)和值(value)，然后在NVM中維護(hù)整條記錄或者只維護(hù)值，而在DRAM中維護(hù)鍵和指向原記錄的指針。該策略不僅大大減少了DRAM的使用量，也減少了CPU需要處理的數(shù)據(jù)量，從而提升性能。

鍵值分離的策略最早是在2017年在針對閃存存儲(chǔ)優(yōu)化的Wiskey[14]系統(tǒng)中提出的，本文受到Wiskey的啟發(fā)，首次將鍵值分離策略與排序連接算法相結(jié)合，并用于優(yōu)化異構(gòu)混合內(nèi)存架構(gòu)上的排序連接性能。當(dāng)2個(gè)表R和S在基于DRAM和NVM的異構(gòu)混合內(nèi)存架構(gòu)上執(zhí)行排序連接時(shí)，按照傳統(tǒng)的排序連接算法，需要把輸入的表數(shù)據(jù)存儲(chǔ)在NVM中，然后將每條記錄〈key,value〉復(fù)制到DRAM中進(jìn)行排序，排序完成后再對表R和S進(jìn)行連接操作。而在基于鍵值分離的排序連接算法中，仍將原始表數(shù)據(jù)存儲(chǔ)在NVM中，但是在執(zhí)行排序和連接操作時(shí)采用〈key,rowid〉形式來代表整條記錄，即只將鍵和記錄指針讀入到DRAM中進(jìn)行處理，記錄的值則仍然保留在NVM中。該方式可以有效減少DRAM的使用量，也可以減少CPU處理的數(shù)據(jù)量，因此有助于提高排序連接的性能。

3.2 鍵值去重策略

排序連接算法的基本思想很簡單，首先將輸入的2個(gè)表排序，排序完成后再進(jìn)行連接操作。不同于哈希連接算法只能解決等值連接的問題，排序連接算法還可以處理不等關(guān)系的連接問題，其根源在于排序連接算法中的連接操作是在已經(jīng)排好序的數(shù)據(jù)上執(zhí)行的，而排序操作也是算法中最重要的部分。一般來說算法會(huì)使用通用的快速排序、堆排序、歸并排序等排序算法，這些算法確實(shí)可以高效地完成排序操作，但是對于選擇度為M∶N的連接問題來說，還可以進(jìn)一步優(yōu)化。

選擇度為M∶N意味著在表R中的1條記錄在S表中可能會(huì)有多條(超過1條)記錄與之相匹配，反之亦然。也就是說，在表R和S中有多個(gè)key相同而value不同的記錄。如果按照傳統(tǒng)的方式執(zhí)行算法，這些記錄〈key,value〉都需要被傳輸?shù)紻RAM中進(jìn)行排序操作，因此存在著大量重復(fù)的數(shù)據(jù)拷貝，即key的多次拷貝。本文在鍵值分離策略的基礎(chǔ)上，進(jìn)一步提出鍵值去重策略，通過去除重復(fù)的鍵來進(jìn)一步降低DRAM的使用代價(jià)。

在選擇度為M∶N的連接問題中，輸入的表數(shù)據(jù)中可能有多個(gè)key相同而value不同的記錄，為了能夠減少key的重復(fù)拷貝，本文采取對具有相同key的記錄進(jìn)行合并的方式來組織數(shù)據(jù)。算法1給出了基于鍵值分離和鍵值去重的C-Join算法流程。首先，為了對表R和S中相同key的記錄合并，分別為它們分配了2個(gè)桶數(shù)組bucketsR和bucketsS，這2個(gè)桶數(shù)組的個(gè)數(shù)是按照連接鍵的上閾值Kmax設(shè)定的。接著,遍歷2個(gè)表的每條記錄，通過key可以確定它所屬的那個(gè)桶，然后將之插入到該桶中，在插入時(shí)使用〈key,rowid〉的形式來表征完整的記錄。當(dāng)2個(gè)表的記錄都插入到對應(yīng)的桶中時(shí)，整個(gè)排序操作也已經(jīng)完成。接著，進(jìn)行連接操作，桶數(shù)組bucketsR和bucketsS中連接鍵相同的桶是互相匹配的數(shù)據(jù)，而那些空的桶則跳過，最終得到連接的結(jié)果。

算法1C-Join

Input:R,S;

Output:none。

1 mallocKmaxbucketsbucketsR;

2foreach record inRdo

3 insert 〈key,rowid〉 intobucketsR[key];

4endfor

5 mallocKmaxbucketsbucketsS;

6foreach record inSdo

7 insert 〈key,rowid〉 intobucketsS[key];

8endfor

9foreach bucket inbucketsRdo

10 find the mathing bucket inbucketsS;

11endfor

3.3 C-Join的3種實(shí)現(xiàn)方式

在C-Join算法中，桶的數(shù)據(jù)結(jié)構(gòu)是整個(gè)算法中的關(guān)鍵部分，桶的設(shè)計(jì)方案也會(huì)直接影響算法在執(zhí)行過程中的DRAM代價(jià)和時(shí)間性能。因此，本節(jié)針對桶的設(shè)計(jì)提出3種實(shí)現(xiàn)方案，即鏈?zhǔn)浇Y(jié)構(gòu)、線性結(jié)構(gòu)和預(yù)分配線性結(jié)構(gòu)。

(1)鏈?zhǔn)浇Y(jié)構(gòu)(C-Join-Chained)。如圖2所示，在鏈?zhǔn)綄?shí)現(xiàn)中，桶由一個(gè)key形成的頭節(jié)點(diǎn)以及后面跟著的若干個(gè)rowid節(jié)點(diǎn)組成，節(jié)點(diǎn)之間以指針相連，這樣的數(shù)據(jù)組織形式的優(yōu)點(diǎn)在于方便靈活，可以靈活地?cái)U(kuò)展桶的大小，但是由于指針太多會(huì)對空間利用率和性能造成一定的影響。

Figure 2 C-Join-Chained

(2)線性結(jié)構(gòu)(C-Join-Linear)。線性實(shí)現(xiàn)方案的思路如圖3所示，與鏈?zhǔn)綄?shí)現(xiàn)相比，線性實(shí)現(xiàn)在rowid的管理上采用了線性數(shù)組的形式，這樣的組織形式減少了指針的占用空間，并且在訪問數(shù)據(jù)時(shí)避免了由指針帶來的多次尋址問題，從而縮短了算法的執(zhí)行時(shí)間。但是，其缺點(diǎn)在于該種實(shí)現(xiàn)方式必須事先分配一個(gè)合理大小的空間以容納所有的記錄，這往往會(huì)帶來一部分的空間浪費(fèi)。

Figure 3 C-Join-Linear

(3)預(yù)分配線性結(jié)構(gòu)(C-Join-Premalloc)。線性實(shí)現(xiàn)中需要提前分配一個(gè)合理大小的空間，帶來了一些內(nèi)存空間的浪費(fèi)，因此，希望找到一種方法能夠提前準(zhǔn)確地分配一個(gè)空間使之剛好能夠容納所有的記錄。要想達(dá)到這個(gè)效果，那么就必須要知道每個(gè)桶所需容納的記錄的數(shù)量，而數(shù)據(jù)庫中一般沒有這項(xiàng)參數(shù)。因此，只能先讀取一遍數(shù)據(jù)，以統(tǒng)計(jì)每個(gè)桶中記錄的數(shù)量，然后再分配每個(gè)桶的空間，這樣就避免了一部分的內(nèi)存浪費(fèi)。但是，同時(shí)也會(huì)造成時(shí)間性能的下降，因?yàn)槎嘧x取了一遍數(shù)據(jù)。具體數(shù)據(jù)結(jié)構(gòu)如圖4所示，與線性實(shí)現(xiàn)的結(jié)構(gòu)基本相同，只是減少了桶中不必要的空間浪費(fèi)，使得整個(gè)桶空間變得非常緊湊。

Figure 4 C-Join-Premalloc

從理論上來看，鏈?zhǔn)浇Y(jié)構(gòu)除了在使用上比較靈活外，在內(nèi)存空間和運(yùn)行時(shí)間方面表現(xiàn)都不會(huì)很好。而當(dāng)表數(shù)據(jù)每個(gè)獨(dú)特key出現(xiàn)次數(shù)比較接近而且已知出現(xiàn)次數(shù)的上限時(shí)，采用線性結(jié)構(gòu)比較好，至于更普遍的情況則是采用預(yù)分配線性結(jié)構(gòu)比較好。

4 實(shí)驗(yàn)結(jié)果

4.1 實(shí)驗(yàn)設(shè)置

本文所有的實(shí)驗(yàn)都是在安裝了Ubuntu 18.04系統(tǒng)的筆記本電腦上執(zhí)行的。該電腦的處理器為Intel? CoreTMi5-4210U CPU @ 1.70 GHz 2.40 GHz，L1、L2、L3緩存大小分別為128 KB、512 KB和3 MB。DRAM內(nèi)存大小為12 GB。由于排序連接算法的所有實(shí)驗(yàn)均不涉及到NVM的寫操作，所以在實(shí)驗(yàn)中沒有模擬NVM的寫延遲，而NVM讀延遲與DRAM相當(dāng)，所以可以用DRAM來模擬NVM。在實(shí)驗(yàn)中主要考察算法的時(shí)間性能和DRAM的代價(jià)。

由于目前還沒有基于異構(gòu)混合內(nèi)存系統(tǒng)上的排序連接算法，所以實(shí)驗(yàn)中主要對比C-Join算法與傳統(tǒng)的排序連接算法(SortJoin)。為了更細(xì)致地測試鍵值分離與鍵值去重策略的性能，本文單獨(dú)實(shí)現(xiàn)了基于鍵值分離的排序連接算法，記為SortJoin-V。同時(shí)也對比了采用了鍵值分離和鍵值去重的C-Join算法的3種實(shí)現(xiàn)方式。所有對比的算法如下所示：

(1)傳統(tǒng)排序連接算法(SortJoin)。這個(gè)算法不使用鍵值分離而是使用〈key,value〉整條原始數(shù)據(jù)執(zhí)行算法，其中使用的排序算法是快速排序算法。

(2)鍵值分離的排序連接算法(SortJoin-V)。該算法與傳統(tǒng)排序連接算法類似，只不過采用了鍵值分離策略，使用〈key,rowid〉來表征整條數(shù)據(jù)。

(3)C-Join-Chained(CJoin-C)。C-Join-Chained是C-Join 3種實(shí)現(xiàn)方式的一種，它采用了鏈?zhǔn)浇Y(jié)構(gòu)來組織桶，桶中的〈rowid〉以指針相連。

(4)C-Join-Linear(CJoin-L)。C-Join-Linear是C-Join 3種實(shí)現(xiàn)方式的一種，它采用了線性數(shù)組結(jié)構(gòu)來組織桶，桶中的〈rowid〉存儲(chǔ)在一個(gè)地址連續(xù)的空間中。

(5)C-Join-Premalloc(CJoin-P)。C-Join-Premalloc是C-Join 3種實(shí)現(xiàn)方式的一種，它與C-Join-Linear類似，但是對桶的大小采用預(yù)分配的方式進(jìn)行設(shè)置，使得空間更加緊湊。

上述所有算法都使用了相同的NVM和DRAM設(shè)置。表R和表S都在NVM上維護(hù)，所有中間數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu)都在DRAM上維護(hù)。由于在連接過程中不會(huì)對NVM上的表數(shù)據(jù)進(jìn)行寫操作，因此，排序連接算法的實(shí)驗(yàn)中只關(guān)注DRAM的使用量和運(yùn)行時(shí)間。

在工作負(fù)載方面，使用與Balkesen等人[8,15]和Albutiu等人[9]類似的工作負(fù)載生成方式。文獻(xiàn)中大多采用key加payload的方式，key的大小一般為4 B或8 B。在本文實(shí)驗(yàn)將記錄的key和rowid設(shè)為8 B，而value的默認(rèn)大小設(shè)置為1 024 B，在比較鍵值分離的排序連接算法實(shí)驗(yàn)中，將通過改變value的大小來觀察算法在內(nèi)存用量和運(yùn)行時(shí)間方面的表現(xiàn)。N表示表R和表S中獨(dú)特的key的數(shù)量，KR和KS分別表示表R和表S中每個(gè)獨(dú)特key出現(xiàn)的次數(shù)，表R和表S的記錄數(shù)量分別為N×KR和N×KS，其中N設(shè)置為100 000，KR和KS分別設(shè)置為10和20。

4.2 SortJoin vs.SortJoin-V

(1)DRAM代價(jià)：如圖5和圖6所示，采用了鍵值分離策略的SortJoin-V的DRAM使用量大大減少，而且隨著value的增大，SortJoin-V的DRAM使用量不再增加。當(dāng)N增大時(shí)，SortJoin-V的DRAM使用量雖然略有增加，但是與傳統(tǒng)的SortJoin相比完全可以忽略不計(jì)。與SortJoin相比，SortJoin-V大幅減少了DRAM使用量(SortJoin的DRAM使用量約為SortJoin-V的16倍)。從圖5和圖6中可以得到一個(gè)結(jié)論，SortJoin-V對DRAM內(nèi)存空間的使用更加高效，而且當(dāng)輸入數(shù)據(jù)規(guī)模不斷增大時(shí)，SortJoin-V會(huì)節(jié)省更多的DRAM空間。

Figure 5 DRAM usage of SortJoin and SortJoin-V with different value

Figure 6 DRAM usage of SortJoin and SortJoin-V with different N

(2)運(yùn)行時(shí)間：排序連接算法的運(yùn)行時(shí)間如圖7和圖8所示，SortJoin的運(yùn)行時(shí)間比SortJoin-V的運(yùn)行時(shí)間高出約2.4倍，而且隨著數(shù)據(jù)規(guī)模的增大，SortJoin-V的運(yùn)行時(shí)間增長速度也比SortJoin的運(yùn)行時(shí)間增長速度更為緩慢，這表明采用了鍵值分離策略的排序連接算法在運(yùn)行時(shí)間方面更有優(yōu)勢。

Figure 7 Running time of SortJoin and SortJoin-V with different value

Figure 8 Running time of SortJoin and SortJoin-V with different N

4.3 C-Join vs.SortJoin-V

在這一節(jié)中，將SortJoin-V作為基準(zhǔn)與C-Join的3種實(shí)現(xiàn)方式進(jìn)行對比，具體結(jié)果如圖9和圖10所示。

Figure 9 DRAM usage of C-Join and SortJoin-V with different N

Figure 10 Running time of of C-Join and SortJoin-V with different N

從圖9中可以看出，與SortJoin-V相比，CJoin-L和CJoin-P的DRAM使用量更低，而其中CJoin-P的最低，在最好情況下比SortJoin-V節(jié)省了13.3%的DRAM空間。這主要?dú)w功于CJoin-P的預(yù)分配策略，這也與本文之前的分析相符合。從圖10中可以看到，CJoin-L是4種算法中執(zhí)行時(shí)間最短的，最多比SortJoin-V節(jié)約了27.8%的時(shí)間，運(yùn)行時(shí)間最高的則是采用了大量指針的CJoin-C，而CJoin-P由于需要提前讀一次表數(shù)據(jù)，所以性能略有下降，與SortJoin-V的性能相當(dāng)?？偟膩碚f，C-Join實(shí)現(xiàn)方式中的CJoin-L和CJoin-P表現(xiàn)比較出色，特別是CJoin-L在DRAM使用量和時(shí)間性能方面都要比SortJoin-V更好。

4.4 KR對C-Join算法的影響

由于C-Join算法的核心思想是通過減少數(shù)據(jù)中重復(fù)的key來達(dá)到內(nèi)存空間的節(jié)省和時(shí)間性能的提升的，所以KR和KS(KR和KS分別表示表R和表S中每個(gè)獨(dú)特key出現(xiàn)的次數(shù))會(huì)對C-Join的2個(gè)評估指標(biāo)產(chǎn)生影響。圖11和圖12展示了不同KR時(shí)DRAM使用量和運(yùn)行時(shí)間的變化(這里我們只使KR變化，而KS設(shè)置成KR的2倍)。

Figure 11 DRAM usage of C-Join and SortJoin-V with different KR

Figure 12 Running time of C-Join and SortJoin-V with different KR

從圖11和圖12可以觀察到，隨著KR的增大，CJoin-L和CJoin-P在DRAM使用量方面增加得較為緩慢，在運(yùn)行時(shí)間方面，CJoin-L的增速也是4種算法中最低的。綜合來看，CJoin-L的實(shí)現(xiàn)方式可以很好地應(yīng)對不同KR的連接問題，在內(nèi)存使用量和運(yùn)行時(shí)間方面其性能都超過了SortJoin-V，而CJoin-P雖然使用的內(nèi)存空間更少，但是在運(yùn)行時(shí)間方面卻沒有優(yōu)勢。

5 結(jié)束語

本文針對基于DRAM和NVM的異構(gòu)混合內(nèi)存架構(gòu)提出了一種基于鍵值分離和鍵值去重策略的新型排序連接算法C-Join。鍵值分離的策略可以充分發(fā)揮NVM的獨(dú)特特性和DRAM的高性能優(yōu)勢，從而能夠有效減少DRAM使用量，提升連接性能。鍵值去重策略則通過消除連接過程中重復(fù)的鍵值拷貝進(jìn)一步降低了DRAM的代價(jià)。本文在算法設(shè)計(jì)的基礎(chǔ)上，進(jìn)一步給出了C-Join算法的3種實(shí)現(xiàn)方式，通過采用不同的桶數(shù)據(jù)結(jié)構(gòu)來執(zhí)行C-Join算法。在模擬數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，鍵值分離的策略能夠有效地縮短連接時(shí)間和降低DRAM代價(jià)。C-Join算法的3種實(shí)現(xiàn)方式均能夠進(jìn)一步優(yōu)化DRAM代價(jià)和時(shí)間性能。