一種適應(yīng)GPU的混合訪問(wèn)緩存索引框架?

張鴻駿,武延軍,張 珩,張立波

1(中國(guó)科學(xué)院 軟件研究所,北京 100190)

2(中國(guó)科學(xué)院大學(xué),北京 100049)

在系統(tǒng)軟件與高性能數(shù)據(jù)應(yīng)用中,散列表(hash table)是一類重要和常見(jiàn)的數(shù)據(jù)索引結(jié)構(gòu).通過(guò)把關(guān)鍵碼值(key value)映射到表中一個(gè)內(nèi)容位置來(lái)訪問(wèn)對(duì)應(yīng)的數(shù)據(jù)記錄,以大幅度加快數(shù)據(jù)查找的速度.在內(nèi)存關(guān)系型數(shù)據(jù)庫(kù)[1-3]和關(guān)鍵碼值類型數(shù)據(jù)庫(kù)[4,5]領(lǐng)域,散列表作為核心的系統(tǒng)組件提供了關(guān)鍵的數(shù)據(jù)索引接結(jié)構(gòu),通過(guò)映射函數(shù)將數(shù)據(jù)索引至對(duì)應(yīng)位置.具體地,網(wǎng)絡(luò)、云計(jì)算和物聯(lián)網(wǎng)服務(wù)的重要系統(tǒng)組件[6],基于鍵值的內(nèi)存緩存系統(tǒng),如memcached[5]、Ramcloud[7]和MemC3[8],都采用了散列表來(lái)提供內(nèi)存內(nèi)的高性能數(shù)據(jù)索引服務(wù).內(nèi)存緩存系統(tǒng)通過(guò)將數(shù)據(jù)從相對(duì)內(nèi)存訪問(wèn)速度慢的磁盤等存儲(chǔ)介質(zhì)加載入內(nèi)存,以提升應(yīng)用程序?qū)?shù)據(jù)訪問(wèn)的性能.由于內(nèi)存通常不能容納所有數(shù)據(jù),當(dāng)內(nèi)存空間滿時(shí),緩存替換系統(tǒng)通過(guò)緩存替換算法踢出部分緩存數(shù)據(jù)為新數(shù)據(jù)提供空間.

在散列表的現(xiàn)有工作中,基于cuckoo 算法的散列表CHT(cuckoo hash table)[9]通過(guò)將原有單一數(shù)據(jù)映射到多個(gè)桶(bucket)中.CHT 代替了傳統(tǒng)散列表的映射與鏈表式操作的方法,具有快速訪問(wèn)與節(jié)省空間的特征,在散列表管理[10-12]和數(shù)據(jù)存儲(chǔ)系統(tǒng)[4,8,13-16]上得到了廣泛的應(yīng)用與研究.

典型的CHT 不支持插入和查詢操作同時(shí)發(fā)生.它將數(shù)據(jù)通過(guò)兩種不同的散列算法映射到兩個(gè)不同的桶中,每個(gè)桶中有4 個(gè)槽(slot)允許存放數(shù)據(jù).每個(gè)數(shù)據(jù)對(duì)應(yīng)一組鍵值數(shù)據(jù)(key-value pair).在執(zhí)行插入操作時(shí),判斷映射桶中是否有空閑槽,如果有,則進(jìn)行插入;如果沒(méi)有空閑槽,則通過(guò)對(duì)現(xiàn)有單元中存儲(chǔ)數(shù)據(jù)進(jìn)行散列與替換獲得空閑槽進(jìn)行插入.進(jìn)而,如果在鍵值對(duì)數(shù)據(jù)插入時(shí)需要替換槽中數(shù)據(jù),CHT 會(huì)隨機(jī)選擇一個(gè)待替換鍵值對(duì)KV′進(jìn)行置換,通過(guò)散列算法計(jì)算KV′對(duì)應(yīng)另一可選桶,將KV 放入原有KV′所在槽中;如果另一可選桶有空閑槽,則將KV′放入該空間槽中;如果該桶沒(méi)有空閑槽,則在該桶內(nèi)隨機(jī)選擇一個(gè)槽中的數(shù)據(jù)按相同方式繼續(xù)進(jìn)行置換,直至找到空閑槽.裝載率是存儲(chǔ)數(shù)據(jù)數(shù)量與散列表槽數(shù)量的比值,用于衡量散列表當(dāng)前負(fù)載情況.當(dāng)裝載率高時(shí),由于剩余空閑槽數(shù)量少,插入操作中數(shù)據(jù)置換頻發(fā),導(dǎo)致CHT 頻繁訪問(wèn)內(nèi)存,同時(shí)CPU 中出現(xiàn)大量臨時(shí)性緩存,散列表性能受到影響.

在基于鍵值的內(nèi)存緩存系統(tǒng)中,這類系統(tǒng)主要的工作負(fù)載特點(diǎn)是讀操作相比寫操作更為頻繁[17,18].當(dāng)讀操作的請(qǐng)求未命中時(shí),系統(tǒng)將讀操作請(qǐng)求的數(shù)據(jù)寫入內(nèi)存緩存[19].當(dāng)未命中的讀操作請(qǐng)求數(shù)量增多時(shí),由于頻繁寫入緩存未命中的數(shù)據(jù),導(dǎo)致了基于鍵值的內(nèi)存緩存系統(tǒng)工作負(fù)載引入了更多的替換操作.當(dāng)散列表裝載率高時(shí),基于鍵值的內(nèi)存緩存系統(tǒng)CHT 頻發(fā),導(dǎo)致了大量?jī)?nèi)存訪問(wèn),降低了緩存系統(tǒng)整體性能.因此,基于鍵值的內(nèi)存緩存系統(tǒng)散列索引方法在減少寫操作訪問(wèn)內(nèi)存的同時(shí),需要保證系統(tǒng)的命中率,減少寫操作數(shù)量.隨著內(nèi)存緩存數(shù)據(jù)量的大幅增加,在多核CPU 上并行散列表結(jié)構(gòu)的索引系統(tǒng)已經(jīng)逐漸出現(xiàn)性能瓶頸,亟需進(jìn)一步改進(jìn)散列表的高性能和可擴(kuò)展性.

硬件的發(fā)展與變遷推動(dòng)著系統(tǒng)軟件的演化[20].隨著GPU 硬件計(jì)算能力和并發(fā)性能的提升,更多的系統(tǒng)任務(wù)在GPU 上運(yùn)行.鍵值存儲(chǔ)緩存系統(tǒng)和關(guān)系型數(shù)據(jù)庫(kù)中的CHT 相關(guān)工作,在GPU 等硬件的性能上得到了一定的提升[10,21-24].然而,現(xiàn)有的CHT 在多核CPU 和GPU 硬件上的并行優(yōu)化方法中,系統(tǒng)在獲取數(shù)據(jù)時(shí)的操作并不高效,計(jì)算系統(tǒng)的性能仍然受到內(nèi)存帶寬的限制[25-28].首先,由于散列表的稀疏性和隨機(jī)性,在訪問(wèn)數(shù)據(jù)保存在芯片緩存后,下次訪問(wèn)之前,被其他訪問(wèn)的數(shù)據(jù)替換逐出芯片緩存,導(dǎo)致芯片緩存的低效利用以及大量獲取數(shù)據(jù)的內(nèi)存訪問(wèn),從而系統(tǒng)性能受到影響.Xie 等人[29,30]提出了針對(duì)GPU 的cache bypassing 方法來(lái)減少芯片緩存的低效使用.其次,在采用GPU 硬件作為計(jì)算核心單元時(shí),在CPU 與GPU 內(nèi)存之間的頻繁數(shù)據(jù)傳輸引入了更多的系統(tǒng)中斷、進(jìn)程切換、驅(qū)動(dòng)調(diào)用等額外開(kāi)銷.因此,減少散列表內(nèi)存訪問(wèn)次數(shù)與減少數(shù)據(jù)在GPU 訪存與內(nèi)存之間的頻繁移動(dòng)仍是優(yōu)化散列表系統(tǒng)性能的重要途徑.

在上述背景下,本文提出了一種適應(yīng)GPU 的混合訪問(wèn)緩存索引框架CCHT(cache cuckoo hash table).該索引框架可應(yīng)用于緩存替換系統(tǒng)進(jìn)行索引管理.CCHT 通過(guò)多級(jí)緩存索引數(shù)據(jù)結(jié)構(gòu)與支持并發(fā)讀寫的緩存插入查詢算法實(shí)現(xiàn)了較低的內(nèi)存訪問(wèn)次數(shù).多級(jí)索引數(shù)據(jù)結(jié)構(gòu)在提供了索引位置信息與全部緩存踢出優(yōu)先隊(duì)列信息的同時(shí),提供了散列表桶內(nèi)踢出優(yōu)先隊(duì)列.支持并發(fā)讀寫的緩存插入查詢算法,給出了在內(nèi)存緩存系統(tǒng)中插入和查詢數(shù)據(jù)時(shí)散列表的操作方法.包括:當(dāng)散列表桶內(nèi)索引存儲(chǔ)空間滿與全局存儲(chǔ)空間滿時(shí)的踢出算法和插入查詢時(shí)桶內(nèi)踢出隊(duì)列與全局踢出隊(duì)列的更新算法.本文根據(jù)內(nèi)存緩存系統(tǒng)的命中率與索引空間占用開(kāi)銷,分別提出了命中率相對(duì)更高的雙重LRU CCHT 與緩存空間開(kāi)銷占用相對(duì)更小的粗粒度LRU CCHT.其中,雙重LRU CCHT 通過(guò)兩個(gè)緩存踢出優(yōu)先級(jí)隊(duì)列,在全局踢出與桶內(nèi)踢出過(guò)程中獨(dú)立使用,實(shí)現(xiàn)了高緩存命中率.粗粒度LRU CCHT 方法則僅通過(guò)一個(gè)緩存踢出優(yōu)先級(jí)隊(duì)列,在全局踢出與桶內(nèi)踢出過(guò)程中共同使用,在保證了緩存命中率的同時(shí),進(jìn)一步減少了優(yōu)先級(jí)隊(duì)列對(duì)索引空間的占用開(kāi)銷.本文將CCHT 在GPUCPU 異構(gòu)環(huán)境下進(jìn)行了實(shí)現(xiàn),并為減少內(nèi)存帶寬的占用與GPU 的訪問(wèn)次數(shù),提出了基于外存計(jì)算系統(tǒng)(out-of-core)的多級(jí)索引數(shù)據(jù)結(jié)構(gòu).通過(guò)這種結(jié)構(gòu),實(shí)現(xiàn)了在CCHT 的請(qǐng)求處理過(guò)程中,在CPU 與GPU 內(nèi)存間僅傳輸鍵數(shù)據(jù),避免了值數(shù)據(jù)占用GPU 內(nèi)存空間以及帶寬資源.通過(guò)實(shí)驗(yàn)驗(yàn)證,當(dāng)緩存空間大小與散列表比值為80%時(shí),插入與全局負(fù)載的平均訪存次數(shù)分別最高降低了30.39%和32.91%;當(dāng)緩存空間大小與散列表比值為90%時(shí),分別降低了94.63%和97.29%.這表明,CCHT 在散列表高裝載率的情況下,仍能提供較低的內(nèi)存訪問(wèn)次數(shù),保證了緩存替換系統(tǒng)的性能.在CPUGPU 異構(gòu)環(huán)境上的實(shí)驗(yàn)說(shuō)明,CCHT 相對(duì)其他數(shù)據(jù)索引方法,在系統(tǒng)吞吐性能上得到了提升,驗(yàn)證了采用的多級(jí)索引數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)方法的有效性.

1 相關(guān)工作

Cuckoo 散列是一種高效空間利用率的開(kāi)放尋址方法[9].它對(duì)每個(gè)對(duì)象指定多個(gè)候選散列表桶位置,同時(shí)允許將已存儲(chǔ)的對(duì)象替換到其他候選桶位置中.SILT[13]通過(guò)兩種散列方法實(shí)現(xiàn)了空間的高占用率,但受到了散列表大小的限制,不能應(yīng)用于大存儲(chǔ)空間的內(nèi)存緩存中.MemC3[8]在保證空間高利用率的同時(shí),通過(guò)標(biāo)簽與優(yōu)化鎖機(jī)制,消除了對(duì)散列表尺寸大小的限制.Hopscotch hashing[14]和Cache-oblivious hashing[15]通過(guò)增加索引指針空間保證訪問(wèn)并發(fā)性,提高了吞吐性能.Li 等人[31]通過(guò)硬件事務(wù)內(nèi)存(HTM)與粗粒度鎖機(jī)制,實(shí)現(xiàn)了訪問(wèn)的高并發(fā).FlashStore[15]通過(guò)Cuckoo 散列將一個(gè)對(duì)象映射到16 個(gè)桶位置上,提高了插入時(shí)對(duì)象尋找空閑槽的幾率.Kirsch 等人[16]采用附加隱藏空間減少了插入尋找空閑空間的開(kāi)銷.

在CPUGPU 異構(gòu)環(huán)境上CHT 實(shí)現(xiàn)的研究過(guò)程中,Horton table[10]采用了附加空間與附加散列映射函數(shù)的方式,代替了原有無(wú)空閑槽時(shí)進(jìn)行的替換方法.Stadium hashing[11]采用了CPU 和GPU 混合使用的方式以提升性能,即將鍵(key)存儲(chǔ)在GPU 中,值(value)存儲(chǔ)在CPU 內(nèi)存中.它通過(guò)添加票板(ticket board)的輔助數(shù)據(jù)結(jié)構(gòu)來(lái)區(qū)分對(duì)于CPU 和GPU 的操作,同時(shí)允許對(duì)同一散列表的并發(fā)讀寫操作.Barber[12]采用了相似的位映射結(jié)構(gòu)實(shí)現(xiàn)了兩個(gè)壓縮類散列表.Xie 等人[29,30]采用GPU 上程序編譯和插樁的方式靜態(tài)或動(dòng)態(tài)地指定臨時(shí)或不常用的數(shù)據(jù)跳過(guò)部分芯片緩存,以減少芯片緩存的頻繁置換.

實(shí)際應(yīng)用中,散列表被廣泛用于各種類型的系統(tǒng)軟件及數(shù)據(jù)處理程序.很多內(nèi)存鍵值存儲(chǔ)系統(tǒng)通過(guò)應(yīng)用于GPU 上的散列表來(lái)加速鍵數(shù)據(jù)的查找[23,32,33].早期實(shí)現(xiàn)在GPU 上的散列表用于數(shù)據(jù)庫(kù)操作、圖形處理和計(jì)算機(jī)視覺(jué)[34-38].在內(nèi)存數(shù)據(jù)庫(kù)中,有很多相關(guān)的工作在CPU 平臺(tái)[39-42]、GPU 平臺(tái)[43-45]和Xeon Phi 平臺(tái)[21,46]上對(duì)散列表進(jìn)行優(yōu)化.

2 研究背景

本節(jié)介紹了我們工作的基礎(chǔ).其中,第2.1 節(jié)描述了CHT 的基本概念,第2.2 節(jié)給出了CHT 的典型實(shí)現(xiàn)方式,第2.3 節(jié)描述了基于LRU 的緩存替換策略,第2.4 節(jié)給出了CUDA 編程技術(shù)的基本概念.

2.1 CHT基本概念

典型的CHT 包含兩種散列方法對(duì)鍵值數(shù)據(jù)(KV)進(jìn)行映射[9].圖1 給出了兩個(gè)典型的插入場(chǎng)景,即將兩個(gè)不同的鍵值數(shù)據(jù)KV1和KV2插入到CHT 中.其中,行號(hào)標(biāo)明了散列索引的位置信息,每個(gè)位置的桶內(nèi)按照典型的CHT 設(shè)置有4 個(gè)槽對(duì)鍵值數(shù)據(jù)進(jìn)行存儲(chǔ).例如,H1和H2表示兩個(gè)獨(dú)立的散列方法,每個(gè)鍵值數(shù)據(jù)可以通過(guò)這兩種散列方法映射到兩個(gè)不同的候選位置上.對(duì)于KV1,映射到位置0 和位置2,對(duì)于KV2,映射到位置3 和位置5.當(dāng)插入KV1時(shí),通過(guò)兩種散列方法找到對(duì)應(yīng)的候選位置0 和2,這兩個(gè)位置的桶中均有空閑槽用于插入新的鍵值數(shù)據(jù).根據(jù)具體CHT 的算法,選擇0 或2 位置的桶加以插入.

Fig.1 Set KV1 and KV2 on a CHT圖1 在CHT 中插入KV1 和KV2

當(dāng)插入KV2時(shí),通過(guò)兩種散列方法找到對(duì)應(yīng)位置3 和5,發(fā)現(xiàn)位置3 和位置5 的桶中已無(wú)空閑槽.當(dāng)遇到此種情況時(shí),CHT 會(huì)在候選位置的桶中選擇一個(gè)槽內(nèi)的鍵值數(shù)據(jù)進(jìn)行踢出,將新的數(shù)據(jù)放入該槽內(nèi),同時(shí)通過(guò)散列方法計(jì)算踢出鍵值數(shù)據(jù)的另一候選位置,如果有空閑槽,則放入,如果沒(méi)有,則重復(fù)踢出置換操作,直至找到空閑的槽.典型的CHT 設(shè)有踢出置換次數(shù)閾值,當(dāng)達(dá)到閾值后,停止踢出替換操作,CHT 進(jìn)行擴(kuò)容.CHT 踢出置換操作的引入,使CHT 中的空閑槽能更多地被使用,從而使得CHT 的負(fù)載率可以大于95%.在KV2的插入場(chǎng)景中,由于對(duì)應(yīng)候選位置3 和位置5 的桶中已無(wú)空閑槽,則隨機(jī)選擇位置5 桶中槽內(nèi)值為o的鍵值數(shù)據(jù)進(jìn)行踢出置換,將KV2放入原有位置5 桶中o對(duì)應(yīng)的槽中.通過(guò)散列方法計(jì)算o的另一候選桶位置為1,查詢位置1 的桶,發(fā)現(xiàn)無(wú)空閑槽,則繼續(xù)選擇一個(gè)鍵值數(shù)據(jù)d進(jìn)行踢出置換,將o放在原有d的槽空間中.再對(duì)d進(jìn)行散列值計(jì)算,查看另一候選位置4 的桶,有空閑槽.將d放入空閑槽中,結(jié)束本次插入操作.Li 等人[29]證明了采用寬度優(yōu)先,直至找到一條可以置換的路徑查找策略,是一種有效的踢出置換方式.

當(dāng)進(jìn)行查詢時(shí),通過(guò)H1與H2計(jì)算散列值,查找對(duì)應(yīng)位置的桶中槽內(nèi)鍵值數(shù)據(jù),通過(guò)遍歷與比較槽內(nèi)鍵數(shù)據(jù)來(lái)獲取存儲(chǔ)的值數(shù)據(jù).

CHT 僅支持同一種任務(wù)類型同時(shí)發(fā)生,如并發(fā)插入操作或并發(fā)查詢操作.當(dāng)插入和查詢操作同時(shí)發(fā)生時(shí),插入操作可能因無(wú)空閑槽,發(fā)生置換操作.此時(shí),若查詢正在置換的目標(biāo)數(shù)據(jù),或查詢的目標(biāo)數(shù)據(jù)在未正確返回前,目標(biāo)數(shù)據(jù)置換入另一桶中的槽內(nèi),將造成對(duì)已索引數(shù)據(jù)的查詢失敗.當(dāng)發(fā)生上述兩種情況導(dǎo)致插入與查詢同時(shí)進(jìn)行時(shí),散列表即喪失了數(shù)據(jù)完整性.CCHT 相對(duì)于CHT 移除了無(wú)空閑槽時(shí)的置換操作,因此,支持插入和查詢操作并發(fā)執(zhí)行,提升了散列表的并發(fā)性能.

2.2 CHT的典型實(shí)現(xiàn)

CHT 在實(shí)際應(yīng)用中的性能,受到大量參數(shù)的影響.在CHT 中,關(guān)鍵的散列函數(shù)個(gè)數(shù)與每個(gè)位置中的存儲(chǔ)空間個(gè)數(shù)影響了CHT 的負(fù)載率及訪問(wèn)的延遲.當(dāng)增加CHT 中散列函數(shù)個(gè)數(shù),允許鍵值數(shù)據(jù)映射到更多的位置上時(shí),由于對(duì)請(qǐng)求數(shù)據(jù)的候選地址變多,因此查找空閑槽的機(jī)會(huì)變大.這種多散列函數(shù)的方式可以有效地提升CHT的負(fù)載率.但當(dāng)進(jìn)行查找操作時(shí),由于散列函數(shù)的增多,導(dǎo)致需要查看更多位置的桶與槽,進(jìn)而導(dǎo)致了訪問(wèn)延遲的增高與處理器中cache line 中加載次數(shù)的增多.在實(shí)際使用過(guò)程中,CHT 的散列函數(shù)設(shè)置成在能夠保證槽的充分利用和高負(fù)載率的同時(shí),還能有效縮短查找時(shí)間,降低訪問(wèn)延遲.

在CHT 中,增加每個(gè)桶內(nèi)槽空間的數(shù)量,可以有效提升負(fù)載率.當(dāng)桶內(nèi)槽數(shù)量增加時(shí),在一次插入和讀取操作的過(guò)程中訪問(wèn)單一桶中槽的數(shù)量增多,從而減少了第2 次或者更多次的散列操作,有效增加了CHT 的負(fù)載率.在CHT 實(shí)際應(yīng)用中,大部分的設(shè)計(jì)采用了每個(gè)桶配有4 個(gè)或8 個(gè)槽空間[9].采用這種配置的原因是一個(gè)處理器中的cache line 可以一次緩存一個(gè)或者兩個(gè)位置的數(shù)據(jù).如果每個(gè)桶中使用更多的槽,在進(jìn)行鍵值數(shù)據(jù)比較時(shí),將導(dǎo)致更多的處理器cache line 加載,訪問(wèn)延遲有所增加.

CHT 的主要特性是能夠提供快速的查詢.在響應(yīng)讀取請(qǐng)求時(shí),最大的查找空間數(shù)為n×s,其中,n為散列函數(shù)個(gè)數(shù),s為單個(gè)桶中對(duì)應(yīng)的槽空間個(gè)數(shù).對(duì)于桶中用于槽的存儲(chǔ)區(qū)域,采用定長(zhǎng)存儲(chǔ)空間的分配方式,方便通過(guò)數(shù)組或者向量的方式對(duì)數(shù)據(jù)進(jìn)行訪問(wèn).這種方式使CHT 更易于在不同處理器架構(gòu)上進(jìn)行實(shí)現(xiàn),如CPU、GPU 和Xeon Phi.

2.3 基于LRU的緩存替換策略

在內(nèi)存緩存系統(tǒng)中,系統(tǒng)將部分?jǐn)?shù)據(jù)從持久化存儲(chǔ)介質(zhì)緩存到內(nèi)存中,用來(lái)降低數(shù)據(jù)訪問(wèn)延遲.由于內(nèi)存的存儲(chǔ)空間有限,小于所有的數(shù)據(jù)存儲(chǔ)空間需求,當(dāng)內(nèi)存緩存空間占滿時(shí),需要通過(guò)緩存替換策略踢出已緩存數(shù)據(jù),獲取空閑空間存放新的緩存數(shù)據(jù).緩存替換策略保證了更有價(jià)值的緩存數(shù)據(jù)留在內(nèi)存中,通常采用命中率來(lái)衡量其有效性.在系統(tǒng)實(shí)現(xiàn)時(shí),通常將增加訪問(wèn)吞吐與延遲作為綜合的考量指標(biāo).在實(shí)際使用中,需根據(jù)不同的應(yīng)用負(fù)載選擇適合的替換策略.如在Web 應(yīng)用的場(chǎng)景下,最近熱門的數(shù)據(jù)被頻繁訪問(wèn),則適用最近最少使用(LRU)替換算法[7,8].

LRU 算法是典型的緩存替換算法.其核心思想是將最近訪問(wèn)的數(shù)據(jù)單元作為最有價(jià)值單元,需要替換時(shí),踢出距離上次訪問(wèn)最長(zhǎng)時(shí)間的數(shù)據(jù)單元.LRU 算法流程如圖2 所示,LRU 算法的數(shù)據(jù)單元存儲(chǔ)空間上限為4,存儲(chǔ)空間右側(cè)為最近訪問(wèn)的數(shù)據(jù),同時(shí),對(duì)于每個(gè)數(shù)據(jù)單元標(biāo)記操作的時(shí)間標(biāo)簽,操作包含插入與讀取操作.在執(zhí)行第1 步～第4 步時(shí),在存儲(chǔ)空間未滿的狀態(tài)下,依次將數(shù)據(jù)單元A,B,C,D插入到存儲(chǔ)空間中.在第5 步時(shí),由于存儲(chǔ)空間已滿,LRU 算法選擇距離上次訪問(wèn)最長(zhǎng)時(shí)間的數(shù)據(jù)單元A進(jìn)行踢出,并插入新數(shù)據(jù)單元E;在第6 步時(shí),由于數(shù)據(jù)單元B被訪問(wèn),將數(shù)據(jù)單元B移至存儲(chǔ)空間最右側(cè),同時(shí)更新時(shí)間標(biāo)簽;第7 步時(shí),需要插入新數(shù)據(jù)單元F,由于存儲(chǔ)空間已滿,與第5 步相同,此步踢出最左側(cè)數(shù)據(jù)單元C,將F放入最右側(cè)存儲(chǔ)空間中.LRU 由于存在算法實(shí)現(xiàn)簡(jiǎn)單、在一定場(chǎng)景下命中率高、對(duì)應(yīng)用性能影響小的特點(diǎn),被緩存替換系統(tǒng)廣泛使用,如memcached[5]、memC3[8]、MICA[4]等.

Fig.2 Using LRU replacement police manages data items圖2 通過(guò)LRU 緩存替換策略管理數(shù)據(jù)單元

LRU 算法在實(shí)現(xiàn)過(guò)程中,通常采用鏈表和時(shí)間戳兩種方式.采用鏈表方式進(jìn)行實(shí)現(xiàn)時(shí),通常與鄰接散列表結(jié)合使用[5],通過(guò)數(shù)據(jù)單元內(nèi)的指針快速訪問(wèn)散列表和LRU 算法管理的數(shù)據(jù)結(jié)構(gòu).采用時(shí)間戳的方式,常用于固定單元大小的索引結(jié)構(gòu),通過(guò)對(duì)時(shí)間戳的比較,選取最早訪問(wèn)的數(shù)據(jù)單元進(jìn)行踢出[47].

2.4 CUDA編程技術(shù)

計(jì)算統(tǒng)一設(shè)備架構(gòu)(compute unified device architecture,簡(jiǎn)稱CUDA)是顯卡廠商N(yùn)VIDIA 推出的并行計(jì)算架構(gòu),已逐步發(fā)展成為NVIDIA GPU 的編程標(biāo)準(zhǔn)規(guī)范.

CUDA 提供了基于標(biāo)準(zhǔn)C 語(yǔ)言的編程模型,支持對(duì)GPU 操作相關(guān)的關(guān)鍵字與結(jié)構(gòu)體.基于CUDA 的GPU編程程序中包含CPU Host 端執(zhí)行代碼與GPU Device 端代碼,程序中的兩部分代碼通過(guò)CUDA 的編譯器自動(dòng)地分為兩部分進(jìn)行編譯與鏈接[48].

CUDA 支持程序開(kāi)發(fā)人員編寫稱為內(nèi)核(kernel)的設(shè)備方法代碼.內(nèi)核被GPU 以單指令多線程(single instruction multiple thread,簡(jiǎn)稱SIMT)形式執(zhí)行.在程序執(zhí)行過(guò)程中,加載一個(gè)內(nèi)核方法相當(dāng)于調(diào)用內(nèi)核方法,同時(shí),程序開(kāi)發(fā)人員需要指定對(duì)應(yīng)的GPU 空間網(wǎng)格(grid)執(zhí)行.一個(gè)網(wǎng)格包含多個(gè)線程塊(block),構(gòu)成一個(gè)二維空間,每個(gè)塊中包含多個(gè)線程,構(gòu)成一個(gè)三維空間.每個(gè)GPU 中的線程都通過(guò)線程標(biāo)識(shí)符(thread id)進(jìn)行標(biāo)識(shí).在一個(gè)塊中的線程可以通過(guò)柵欄實(shí)現(xiàn)同步.

GPU 線程在內(nèi)核方法執(zhí)行過(guò)程中獲得GPU 內(nèi)存的訪問(wèn)權(quán)限.每個(gè)線程對(duì)存儲(chǔ)的操作包括讀寫私有寄存器和本地內(nèi)存.內(nèi)核方法中的本地變量被自動(dòng)地分配到寄存器或者內(nèi)存中.GPU 其他內(nèi)存中的變量可以通過(guò)接口創(chuàng)建與管理.在CUDA 程序中可能包含多個(gè)內(nèi)核,所有的操作都可以應(yīng)用于每一個(gè)內(nèi)核.在下文介紹的CCHT 設(shè)計(jì)與實(shí)現(xiàn)過(guò)程中,將所有的CHT 與替換操作全部實(shí)現(xiàn)于內(nèi)核中,以提高程序的執(zhí)行效率,同時(shí)面向單一的處理器實(shí)現(xiàn)能夠更方便地向其他平臺(tái)進(jìn)行移植.

3 基于不同索引空間占用緩存索引CCHT 方法

在本節(jié)中,我們主要介紹了基于不同索引空間占用的緩存索引方法的設(shè)計(jì)與實(shí)現(xiàn),包括索引結(jié)構(gòu)設(shè)計(jì)與緩存替換算法.其中,第3.1 節(jié)給出了面向內(nèi)存緩存的散列索引分析,第3.2 節(jié)描述了雙重LRU 索引訪問(wèn)方法,第3.3節(jié)描述了粗粒度LRU 索引訪問(wèn)方法.

3.1 面向內(nèi)存緩存的散列索引分析

在內(nèi)存緩存系統(tǒng)中,散列索引與緩存替換策略一般分別加以實(shí)現(xiàn)[5,8].散列索引用于對(duì)內(nèi)存中的緩存數(shù)據(jù)進(jìn)行索引,在緩存系統(tǒng)處理查詢請(qǐng)求時(shí)可快速訪問(wèn)目標(biāo)數(shù)據(jù).常見(jiàn)的散列索引,如本文提到的應(yīng)用于MemC3[8]中的CHT 和memcached[5]中的開(kāi)散列(open hashing)方法.替換策略用于當(dāng)內(nèi)存緩存被所需緩存數(shù)據(jù)存儲(chǔ)已滿時(shí),有新的數(shù)據(jù)需要進(jìn)行緩存,則在已緩存數(shù)據(jù)中通過(guò)某一策略選擇待踢出數(shù)據(jù),進(jìn)行替換.常用的緩存索引方法有本文中提到的LRU、FIFO(先進(jìn)先出算法)、LFU(最近最常使用算法)、CLOCK(時(shí)鐘算法)[49].其中,LRU 由于實(shí)現(xiàn)簡(jiǎn)單,維護(hù)方便,策略符合一般工作負(fù)載需求而被廣泛使用.

當(dāng)通過(guò)CHT 進(jìn)行數(shù)據(jù)索引時(shí),每個(gè)數(shù)據(jù)對(duì)應(yīng)兩個(gè)可選的桶,如果兩個(gè)桶中已無(wú)空閑槽,則需要在兩個(gè)位置中選擇隨機(jī)槽內(nèi)數(shù)據(jù)進(jìn)行置換,之后根據(jù)置換出的鍵值數(shù)據(jù)進(jìn)行散列值計(jì)算,可能會(huì)導(dǎo)致更多次的訪存操作,如第2.1 節(jié)中所述.在內(nèi)存緩存系統(tǒng)中,緩存數(shù)據(jù)無(wú)持久化存儲(chǔ)需求.緩存替換策略可根據(jù)多維度指標(biāo),如命中率、訪問(wèn)延遲、空間占用率、吞吐等踢出緩存數(shù)據(jù).因此,我們?cè)O(shè)計(jì)了內(nèi)置緩存策略的CCHT,即在內(nèi)存緩存系統(tǒng)中,以CHT 為基礎(chǔ),當(dāng)索引散列表需要進(jìn)行踢出置換時(shí),調(diào)用緩存替換策略,進(jìn)行踢出.我們依據(jù)索引開(kāi)銷與命中率需求實(shí)現(xiàn)了兩種方法,在后文中將分別加以描述.

3.2 雙重LRU CCHT緩存索引方法

CCHT 設(shè)計(jì)的核心思路是通過(guò)添加桶內(nèi)緩存隊(duì)列操作移除CHT 原有的無(wú)空閑槽時(shí)進(jìn)行的置換操作,達(dá)到減少內(nèi)存訪問(wèn)和支持插入與查詢操作并發(fā)執(zhí)行的目的.

雙重LRU CCHT 緩存索引結(jié)構(gòu)與典型的LRU CHT 的結(jié)構(gòu)類似.如圖3 所示,在結(jié)構(gòu)中通過(guò)散列表對(duì)鍵值數(shù)據(jù)進(jìn)行索引.每個(gè)散列值對(duì)應(yīng)一個(gè)桶,每個(gè)桶中包含有固定數(shù)量的槽.每個(gè)槽中包含有鍵值數(shù)據(jù),占用標(biāo)示,兩個(gè)用于桶內(nèi)LRU 的槽指針,兩個(gè)用于全局LRU 的槽指針.其中,與典型的LRU CHT 結(jié)構(gòu)不同的是增加用于桶內(nèi)LRU 的槽指針.為方便理解與后續(xù)方法描述,我們?cè)趫D3 中對(duì)每個(gè)桶添加時(shí)間戳標(biāo)簽,該時(shí)間戳等同于每個(gè)桶中LRU 隊(duì)列隊(duì)尾單元的時(shí)間戳,標(biāo)記每個(gè)桶中現(xiàn)有最早放入元素的時(shí)間.

Fig.3 Double LRU CCHT structure圖3 雙重LRU 的CCHT 緩存索引結(jié)構(gòu)

在通過(guò)CCHT 向內(nèi)存緩存中插入鍵數(shù)據(jù)key 和值數(shù)據(jù)value 時(shí),如算法1 所示.如果內(nèi)存緩存中有空閑緩存空間,通過(guò)散列函數(shù)Hash1(key)得到對(duì)應(yīng)的散列值H1,檢查H1對(duì)應(yīng)的桶中是否有空閑槽.如果有空閑槽,則將鍵值數(shù)據(jù)插入該槽,更新占用標(biāo)記,并將該槽置于全局LRU 隊(duì)列隊(duì)首和桶內(nèi)LRU 隊(duì)列隊(duì)首;如果沒(méi)有空閑槽,則通過(guò)Hash2(key)計(jì)算得到散列值H2,檢查對(duì)應(yīng)桶中是否有空閑槽,如果有空閑槽,則進(jìn)行上述相同操作.如果H1和H2對(duì)應(yīng)的桶中都沒(méi)有空閑槽,則比較timestamp,選擇時(shí)間戳較小的桶.如果H2的時(shí)間戳較小,說(shuō)明散列值H2對(duì)應(yīng)的桶中LRU 隊(duì)尾的槽相對(duì)散列值H1對(duì)應(yīng)的桶中LRU 隊(duì)尾的槽更久沒(méi)有被訪問(wèn).踢出散列值H2對(duì)應(yīng)的桶中LRU 隊(duì)尾的槽,包括釋放對(duì)應(yīng)的鍵值數(shù)據(jù),在全局LRU 隊(duì)列與桶內(nèi)LRU 隊(duì)列中進(jìn)行踢出.將待插入的鍵值數(shù)據(jù)插入該槽中,并將該槽置于全局LRU 隊(duì)列和桶內(nèi)LRU 隊(duì)列隊(duì)首.如果插入鍵值數(shù)據(jù)時(shí),內(nèi)存緩存中無(wú)空閑緩存空間,則需要先通過(guò)全局LRU 隊(duì)列踢出隊(duì)尾槽對(duì)應(yīng)的鍵值數(shù)據(jù)與LRU 隊(duì)列槽指針.

通過(guò)CCHT 查詢方法與第2.1 節(jié)中描述的通過(guò)CHT 進(jìn)行查詢類似,如算法2 所示.在返回查詢結(jié)果的同時(shí),如CCHT 中包含所需查詢的鍵值數(shù)據(jù),則將鍵值數(shù)據(jù)對(duì)應(yīng)的槽放置在全局LRU 隊(duì)列隊(duì)首和桶內(nèi)LRU 隊(duì)列隊(duì)首.

通過(guò)雙重LRU CCHT,將原有鍵值數(shù)據(jù)插入過(guò)程中的踢出置換操作變?yōu)榫彺嫣鎿Q,去除了由于置換操作引發(fā)的內(nèi)存訪問(wèn)次數(shù)和查詢空閑槽的時(shí)間.雙重LRU CCHT 通過(guò)全局LRU 隊(duì)列和桶內(nèi)LRU 隊(duì)列獨(dú)立使用保證了內(nèi)存緩存系統(tǒng)的命中率.這種方法相對(duì)于LRU CHT,增加了用于桶內(nèi)LRU 隊(duì)列的指針存儲(chǔ)空間開(kāi)銷.因此,我們提出了粗粒度LRU CCHT,相對(duì)雙重LRU CCHT,節(jié)省了指針占用存儲(chǔ)空間的開(kāi)銷.

算法1.雙重LRU CCHT 插入算法.

算法2.雙重LRU CCHT 查詢算法.

3.3 粗粒度LRU CCHT方法

為了節(jié)省CCHT 中指針占用的存儲(chǔ)空間,我們提出了粗粒度LRU CCHT 方法,如圖4 所示.相對(duì)雙重LRU CCHT 索引結(jié)構(gòu),取消了用于全局LRU 隊(duì)列的槽指針,添加了基于桶的LRU 隊(duì)列操作.每個(gè)桶中包含有兩個(gè)桶指針,用于維護(hù)粗粒度的LRU 隊(duì)列.

當(dāng)通過(guò)粗粒度LRU CCHT 方法進(jìn)行插入操作和查詢成功后,將對(duì)應(yīng)桶放置于桶LRU 隊(duì)首,對(duì)應(yīng)的索引單元放置于桶內(nèi)LRU 隊(duì)首.當(dāng)插入數(shù)據(jù)時(shí),若內(nèi)存緩存中無(wú)空閑緩存空間,則選擇桶LRU 隊(duì)列中位于隊(duì)尾的桶,選擇隊(duì)尾桶中的桶內(nèi)LRU 隊(duì)列隊(duì)尾的槽進(jìn)行鍵值數(shù)據(jù)的踢出與釋放.

粗粒度LRU CCHT 方法通過(guò)桶LRU 算法取代了雙重LRU CCHT 方法與LRU CHT 方法中的全局LRU 索引.相對(duì)于雙重LRU CCHT,減少了2×m×(s-1)個(gè)槽指針占用,其中,m為CCHT 內(nèi)桶的個(gè)數(shù),s為單個(gè)桶中槽的個(gè)數(shù),為CCHT 節(jié)省了索引存儲(chǔ)開(kāi)銷.

Fig.4 Coarse LRU CCHT structure圖4 粗粒度LRU CCHT 緩存索引結(jié)構(gòu)

4 CCHT 在面向CPUGPU 異構(gòu)環(huán)境上的實(shí)現(xiàn)

根據(jù)第3 節(jié)中CCHT 的方法描述,本節(jié)主要介紹了CCHT 在CPUGPU 異構(gòu)環(huán)境上進(jìn)行的實(shí)現(xiàn).其中,第4.1節(jié)描述了面向CPUGPU 異構(gòu)存儲(chǔ)下的多級(jí)數(shù)據(jù)索引結(jié)構(gòu),第4.2 節(jié)給出了異構(gòu)環(huán)境下CCHT 的應(yīng)用接口函數(shù),第4.3 節(jié)描述了CCHT 的實(shí)現(xiàn)細(xì)節(jié),第4.4 節(jié)給出了CCHT 在實(shí)現(xiàn)過(guò)程中的優(yōu)化.

4.1 異構(gòu)存儲(chǔ)下的多級(jí)索引數(shù)據(jù)結(jié)構(gòu)

在現(xiàn)實(shí)應(yīng)用中,如圖數(shù)據(jù)、日志數(shù)據(jù)及視頻數(shù)據(jù)為值數(shù)據(jù)的散列表值數(shù)據(jù)存儲(chǔ)空間開(kāi)銷大.以GPU 內(nèi)存為散列表的處理設(shè)計(jì)與性能受到了系統(tǒng)PCI 總線帶寬和GPU 內(nèi)存大小的限制.因此,我們采用了基于外存計(jì)算系統(tǒng)的方式設(shè)計(jì)了多級(jí)索引數(shù)據(jù)結(jié)構(gòu).在存儲(chǔ)空間初始化時(shí),在CPU 內(nèi)存中分配連續(xù)的存儲(chǔ)空間.在對(duì)GPU 上散列表進(jìn)行操作時(shí),用CPU 上原始值數(shù)據(jù)對(duì)應(yīng)的索引序列值進(jìn)行表示,減少了GPU 內(nèi)存空間的占用及PCI-E 帶寬傳輸開(kāi)銷.

鍵值數(shù)據(jù)在CPU 和GPU 的分布如圖5 所示.如插入鍵值數(shù)據(jù)對(duì)KV1,值數(shù)據(jù)V1存儲(chǔ)在CPU 內(nèi)存的連續(xù)值存儲(chǔ)區(qū),位置標(biāo)識(shí)ID 為0;鍵數(shù)據(jù)K1與索引位置ID 值0,通過(guò)系統(tǒng)總線傳輸至GPU 內(nèi)存中,并存儲(chǔ)在對(duì)應(yīng)散列值桶中的空閑槽內(nèi).當(dāng)查詢KV3時(shí),將K3通過(guò)系統(tǒng)總線傳輸至GPU 內(nèi)存中,待查詢完成后,通過(guò)總線返回對(duì)應(yīng)位置標(biāo)識(shí) ID 值 2.通過(guò)多級(jí)CPUGPU 異構(gòu)值索引結(jié)構(gòu),有效地減少了GPU 中內(nèi)存的占用和總線帶寬占用.在GPU 內(nèi)存中,除查詢必須的鍵數(shù)據(jù),僅包含值數(shù)據(jù)的位置標(biāo)識(shí)外,相對(duì)于原始值數(shù)據(jù),減少了有限GPU 空間內(nèi)存的占用.在請(qǐng)求處理時(shí),插入與查詢的值數(shù)據(jù)均不通過(guò)總線傳輸至GPU 內(nèi)存,有效地避免了因值數(shù)據(jù)過(guò)大造成的總線帶寬占用以及性能損耗.

Fig.5 The CCHT data structure under CPUGPU圖5 CPUGPU 下的CCHT 數(shù)據(jù)結(jié)構(gòu)

4.2 異構(gòu)環(huán)境下CCHT的應(yīng)用接口函數(shù)

CCHT 實(shí)現(xiàn)的方法主要包含接入庫(kù)函數(shù),數(shù)據(jù)存儲(chǔ)區(qū)域初始化函數(shù)及操作散列表的GPU kernel(核)函數(shù).我們采用的CUDA 9.1 版本的GPU 編程框架,代碼行數(shù)共計(jì)1 385 行,其中接入庫(kù)函數(shù)與數(shù)據(jù)存儲(chǔ)區(qū)域初始化函數(shù)為324 行,GPU kernel 函數(shù)為953 行,其余為宏定義及全局變量索引.

實(shí)現(xiàn)的方法與功能描述見(jiàn)表1 和表2.表1 給出了在CPU 上實(shí)現(xiàn)的函數(shù),主要包含用于其他CPU 程序調(diào)用進(jìn)行鍵值操作的接入庫(kù)函數(shù)、CPU 與GPU 存儲(chǔ)區(qū)域索引與內(nèi)容初始化的數(shù)據(jù)初始化函數(shù),以及向GPU kernel函數(shù)提交任務(wù)與鍵值數(shù)據(jù)的函數(shù).CPU 上的函數(shù)主要向其他程序提供了鍵值數(shù)據(jù)操作的接口,對(duì)GPU 上的kernel 函數(shù)進(jìn)行了封裝,實(shí)現(xiàn)了其他程序調(diào)用時(shí)對(duì)GPU 操作的透明化.表2 給出了GPU 上的kernel 函數(shù).主要包含了GPU 用于接收與解析CPU 提交鍵值操作任務(wù)和數(shù)據(jù)的global 函數(shù)、散列表操作的device 函數(shù)、緩存隊(duì)列踢出操作的device 函數(shù).GPU 上實(shí)現(xiàn)的kernel 函數(shù)用于在GPU 存儲(chǔ)區(qū)域中的散列表上處理對(duì)應(yīng)的鍵值數(shù)據(jù).

Table 1 Interface and implemented methods on CPU表1 CPU 接口與實(shí)現(xiàn)函數(shù)

Table 2 Kernel method on GPU表2 GPU 核函數(shù)

CCHT 在GPU 上的操作僅包括CCHT_set、CCHT_get、CCHT_del 和CCHT_evict 這4 個(gè)分支核函數(shù)操作,符合GPU 以單指令多線程(single instruction multiple thread,簡(jiǎn)稱SIMT)形式執(zhí)行.CCHT 在CPUGPU 異構(gòu)環(huán)境下執(zhí)行可以獲得更好的并發(fā)性能.

4.3 實(shí)現(xiàn)細(xì)節(jié)

在數(shù)據(jù)存儲(chǔ)區(qū)域初始化時(shí),采用malloc 與cudaMalloc 分配所需存儲(chǔ)區(qū)域.其中包含了在CPU 上執(zhí)行緩存操作與鍵值數(shù)據(jù)的存儲(chǔ)區(qū)域、GPU 執(zhí)行結(jié)果返回的存儲(chǔ)區(qū)域;在GPU 上接受執(zhí)行操作與鍵值數(shù)據(jù)的存儲(chǔ)區(qū)域、以槽為單元的散列表鍵值數(shù)據(jù)存儲(chǔ)區(qū)域、桶中標(biāo)識(shí)的存儲(chǔ)區(qū)域及散列表操作執(zhí)行結(jié)果的存儲(chǔ)區(qū)域.在完成分配后,通過(guò)memset 與cudaMemset 實(shí)現(xiàn)數(shù)據(jù)存儲(chǔ)區(qū)域的初始化.

在CPU 上操作鍵值數(shù)據(jù)的函數(shù),將其他程序調(diào)用傳遞進(jìn)的鍵值數(shù)據(jù)與操作,復(fù)制至CPU內(nèi)存中的鍵值數(shù)據(jù)與任務(wù)的緩沖隊(duì)列中.所有操作鍵值數(shù)據(jù)的函數(shù)共用同一數(shù)據(jù)與任務(wù)緩沖隊(duì)列,允許任務(wù)緩沖隊(duì)列中包含多個(gè)寫操作和多個(gè)讀操作.當(dāng)達(dá)到向GPU 提交任務(wù)數(shù)的閾值時(shí),則調(diào)用flush_ops 函數(shù),通過(guò)global 函數(shù)CCHT_process 向GPU 傳遞數(shù)據(jù)及相應(yīng)的操作標(biāo)識(shí).當(dāng)向GPU 提交的任務(wù)執(zhí)行完成后,將結(jié)果返回至指定的存儲(chǔ)區(qū)域.在CPU 上運(yùn)行的程序?qū)Y(jié)果進(jìn)一步處理,如判斷讀操作是否命中、更新可用緩存空間大小等.

在GPU 上執(zhí)行核函數(shù)時(shí),每個(gè)核函數(shù)線程執(zhí)行單一任務(wù)及鍵值數(shù)據(jù)操作,根據(jù)GPU 線程的全局id 進(jìn)行指定,CCHT_process 接受傳遞進(jìn)入GPU 內(nèi)存的鍵值數(shù)據(jù)及任務(wù)數(shù)據(jù),并根據(jù)任務(wù)數(shù)據(jù)的標(biāo)識(shí)進(jìn)行解析,以獲取操作類型.對(duì)不同的散列表操作選擇調(diào)用CCHT_set、CCHT_get 或CCHT_del,完成后將結(jié)果返回至指定的GPU內(nèi)存存儲(chǔ)區(qū)域.當(dāng)內(nèi)存緩存空間已滿時(shí),CPU 傳遞的寫操作的任務(wù)數(shù)據(jù)包含替換操作與寫操作,GPU 在調(diào)用CCHT_evict 執(zhí)行踢出操作后,再調(diào)用CCHT_set 進(jìn)行寫操作.

4.4 優(yōu)化細(xì)節(jié)

CCHT 采用任務(wù)批處理提交方式.在其他程序調(diào)用接入庫(kù)函數(shù)時(shí),將傳入的鍵值數(shù)據(jù)及對(duì)應(yīng)的操作復(fù)制到鍵值數(shù)據(jù)與操作的緩沖區(qū),當(dāng)達(dá)到批處理提交的任務(wù)數(shù)閾值時(shí),將鍵值數(shù)據(jù)及操作提交至GPU 核函數(shù),由GPU線程根據(jù)線程id 并發(fā)對(duì)相應(yīng)操作的鍵值數(shù)據(jù)進(jìn)行處理.通過(guò)任務(wù)批處理提交的方式,減少了CPU 與GPU 間內(nèi)存的訪問(wèn)與傳輸頻次,減少了PCI-E 總線的訪問(wèn),同時(shí)能夠充分利用GPU 多線程的并發(fā)性,提升散列表任務(wù)的處理性能.

通過(guò)GPU 執(zhí)行維度參數(shù)配置實(shí)現(xiàn)單一warp 中執(zhí)行一種指令.在CCHT 中,指令分支出現(xiàn)于各線程運(yùn)行g(shù)lobal 函數(shù)CCHT_process 后,需要根據(jù)散列表操作類型,調(diào)用不同的device 函數(shù).如果采用同一warp 中混合多種操作,將導(dǎo)致由warp divergence 引發(fā)的同一warp 中的不同散列表操作類型將順序執(zhí)行.我們通過(guò)限定同一warp 執(zhí)行單一線程實(shí)現(xiàn)避免指令分支造成的同步等待.雖然同一warp 中僅執(zhí)行單一線程影響了GPU 的并發(fā)性能,但基于warp 粒度的并發(fā)仍能達(dá)到很好的吞吐效果,這一點(diǎn),在后文的第5.5 節(jié)中得到了驗(yàn)證.

在鍵值數(shù)據(jù)與任務(wù)緩存區(qū)的實(shí)現(xiàn)上,采用了混合與復(fù)用的方式.所有操作的鍵值數(shù)據(jù)與任務(wù)共享一個(gè)連續(xù)的緩沖區(qū).在返回結(jié)果時(shí),將數(shù)據(jù)返回至提交任務(wù)的數(shù)據(jù)緩沖區(qū)中.這種混合與復(fù)用的實(shí)現(xiàn)方式減少了CPU 與GPU 內(nèi)存的空間開(kāi)銷,釋放了更多內(nèi)存空間用于鍵值數(shù)據(jù)的存儲(chǔ).同時(shí),相對(duì)多段緩存區(qū)的設(shè)計(jì),連續(xù)的內(nèi)存訪問(wèn)操作比例增大,減少了因?yàn)閿?shù)據(jù)存儲(chǔ)在多段緩存區(qū)域造成的內(nèi)存訪問(wèn).

基于CUDA 原生的原子操作鎖機(jī)制.在CCHT 中,包含并發(fā)寫入、讀取槽數(shù)據(jù)與變更LRU 隊(duì)列的操作,需要對(duì)每個(gè)槽和LRU 隊(duì)列進(jìn)行讀寫鎖設(shè)計(jì).即需要支持多個(gè)線程同時(shí)操作數(shù)據(jù)可以獲得更好的并發(fā)性能,防止因鎖等待導(dǎo)致單個(gè)線程任務(wù)延遲過(guò)長(zhǎng).我們?cè)贕PU 內(nèi)存中設(shè)置了鎖標(biāo)識(shí)數(shù)據(jù),默認(rèn)值為0.對(duì)于寫操作,采用了原子atomicMax()方法實(shí)現(xiàn),返回現(xiàn)有標(biāo)識(shí)數(shù)據(jù),并將標(biāo)識(shí)數(shù)據(jù)更新為現(xiàn)有標(biāo)識(shí)數(shù)據(jù)與置入數(shù)據(jù)的最大值.在置入數(shù)據(jù)值為1 的情況下:當(dāng)返回值為0 時(shí),表明鎖空閑,完成后通過(guò)atomicExch()置0 解鎖;當(dāng)返回值不為0 時(shí),表明有其他讀或?qū)懢€程正在訪問(wèn)數(shù)據(jù).對(duì)于讀操作,基于atomicAdd()的方法進(jìn)行實(shí)現(xiàn),返回現(xiàn)有標(biāo)識(shí)數(shù)據(jù),并將標(biāo)識(shí)數(shù)據(jù)更新為現(xiàn)有標(biāo)識(shí)數(shù)據(jù)與置入數(shù)據(jù)之和.當(dāng)返回值模2 值不為0 時(shí),表明有寫線程正在訪問(wèn)數(shù)據(jù);當(dāng)返回值模2 結(jié)果為0 時(shí),表明無(wú)其他寫線程訪問(wèn)數(shù)據(jù).成功占用鎖并完成操作后,通過(guò)atomicSub()方法釋放當(dāng)前讀線程對(duì)鎖占用.通過(guò)上述方法實(shí)現(xiàn)了允許同一時(shí)間單一寫操作或多個(gè)讀操作同時(shí)進(jìn)行.基于CUDA原生的原子操作鎖機(jī)制代替了CUDA 傳統(tǒng)原子數(shù)據(jù)操作賦值方法,打破了對(duì)依賴CUDA 庫(kù)函數(shù)的原子操作數(shù)據(jù)大小的上限限制.在CCHT 的GPU 端處理任務(wù)請(qǐng)求過(guò)程中,線程同一時(shí)刻僅可能獲取單個(gè)槽的鎖,不會(huì)因?yàn)槎鄠€(gè)鎖資源同時(shí)搶占而造成死鎖.

5 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)在CPU+GPU 異構(gòu)服務(wù)器上進(jìn)行,其中,CPU 為Intel(R)Core(TM)i7-6700K,四核4.00Ghz 主頻,內(nèi)存DDR4 32GB,GPU 為NVIDIA GeForce GTX 1080Ti,顯存11GB.

實(shí)驗(yàn)中采用YCSB[50]生成的數(shù)據(jù)集進(jìn)行測(cè)試,數(shù)據(jù)鍵值的長(zhǎng)度為24B,值類型為100B,插入數(shù)據(jù)集的規(guī)模為3×106個(gè)元素.數(shù)據(jù)操作請(qǐng)求包括3 種典型的工作負(fù)載,Zipf、latest、uniform.其中,Zipf 工作負(fù)載分布偏度為0.99,latest 工作負(fù)載為最近使用的數(shù)據(jù)請(qǐng)求,uniform 工作負(fù)載查詢的數(shù)據(jù)概率相同.每個(gè)工作負(fù)載請(qǐng)求中包含兩類插入與查詢操作比值,分別為全部是查詢操作以及查詢操作占比50%.根據(jù)內(nèi)存緩存典型運(yùn)行環(huán)境特征[12],在查詢返回丟失后,進(jìn)行插入操作.在實(shí)驗(yàn)過(guò)程中,首先進(jìn)行數(shù)據(jù)集加載與緩存預(yù)熱操作,然后再進(jìn)行工作負(fù)載請(qǐng)求操作.

為了對(duì)CCHT 應(yīng)用性能進(jìn)行驗(yàn)證,我們實(shí)現(xiàn)了以CCHT 為核心的緩存替換系統(tǒng)原型.為了對(duì)比,還實(shí)現(xiàn)了另外3 種緩存索引算法:LRU CHT、LRU 開(kāi)散列表(LRU open hash)、隨機(jī)CHT(random CHT),其中,LRU CHT 與隨機(jī)CHT 在CPUGPU 異構(gòu)平臺(tái)下進(jìn)行對(duì)比驗(yàn)證.LRU 開(kāi)散列表由于動(dòng)態(tài)分配數(shù)據(jù)空間的特性不適用于CPUGPU 異構(gòu)平臺(tái)的初始化固定存儲(chǔ)空間,我們?cè)贑PU 平臺(tái)進(jìn)行了實(shí)現(xiàn)與對(duì)比驗(yàn)證.設(shè)置CCHT 與CHT 的散列值長(zhǎng)度為24,每個(gè)散列值對(duì)應(yīng)的桶包含4 個(gè)索引存儲(chǔ)單元.CHT 的踢出替換操作上限為5 000 次.CCHT 批處理的閾值設(shè)為2 000.散列表裝載率由緩存空間大小與散列表最大索引數(shù)量的比值來(lái)表示.

5.1 插入平均訪存

插入平均訪存是指在進(jìn)行數(shù)據(jù)集加載與緩存預(yù)熱操作過(guò)程中的平均訪問(wèn)內(nèi)存次數(shù).本文中,latest、zipf、uniform 工作負(fù)載預(yù)熱與加載的數(shù)據(jù)內(nèi)容與順序相同,實(shí)驗(yàn)結(jié)果如圖6所示.當(dāng)緩存空間大小與散列表比值大于60%時(shí),雙重 LRU CCHT 與粗粒度 LRU CCHT 均顯著低于其他算法.當(dāng)緩存空間大小與散列表大小比值為 80%時(shí),雙重 LRU CCHT 與粗粒度LRU CCHT 的平均訪存次數(shù)對(duì)比LRU CHT 均降低了30.39%.當(dāng)緩存空間大小與散列表大小比值為90%時(shí),雙重LRU CCHT 與粗粒度LRU CCHT 的平均訪存次數(shù)對(duì)比LRU CHT 均降低了94.63%.說(shuō)明CCHT的兩種方法能夠有效地減少內(nèi)存訪問(wèn)次數(shù),當(dāng)緩存空間大小與散列表大小比值較高時(shí),CCHT 對(duì)比CHT 去除了踢出與替換操作,大幅度地減少了散列表的訪問(wèn)次數(shù),從而減少了內(nèi)存訪問(wèn)次數(shù).

Fig.6 Average memory access per insert with Hash table size圖6 插入平均訪存次數(shù)隨緩存空間大小變化

5.2 全局平均訪存

全局平均訪存是指在工作負(fù)載測(cè)試集加載過(guò)程中的平均訪問(wèn)內(nèi)存次數(shù).圖7 描述了在6 種不同的工作負(fù)載下,5 種緩存索引算法的全局平均訪問(wèn)內(nèi)存次數(shù)隨緩存空間大小發(fā)生變化的實(shí)驗(yàn)結(jié)果.

Fig.7 Average memory access per request with hash table size圖7 全局平均訪存次數(shù)隨緩存空間大小的變化

當(dāng)緩存空間大小與散列表比值大于60%時(shí),雙重LRU CCHT 與粗粒度LRU CCHT 均低于其他算法.其中,當(dāng)query 占比為50%時(shí),雙重LRU CCHT 與粗粒度LRU CCHT 的效果對(duì)比LRU CHT 更加明顯地減少了平均訪問(wèn)內(nèi)存次數(shù).在latest,query 50%、zipf,query 50%、uniform,query 50%中的70%、80%、90%,雙重LRU CCHT平均降低了10.59%、32.86%、97.25%,粗粒度LRU CCHT 平均降低了9.50%、32.91%、97.29%.原因是在query占比為50%的工作負(fù)載中,有大量的插入操作.隨著緩存空間的增加,LRU CHT 和隨機(jī)CHT 方法需要更多的踢出替換操作以獲得空閑的索引空間,導(dǎo)致了大量的內(nèi)存訪問(wèn).而雙重LRU CCHT 和粗粒度LRU CCHT 隨著緩存空間的增加,沒(méi)有訪問(wèn)更多的索引位置.

5.3 命中率

命中率是指在工作負(fù)載測(cè)試集加載過(guò)程中,查詢成功的次數(shù)占所有查詢次數(shù)的比值.圖8 描述了在6 種不同的工作負(fù)載下,5 種緩存索引算法的命中率.在zipf 和uniform 分布的4 種工作負(fù)載中,雙重LRU CCHT 和粗粒度LRU CCHT 與LRU CHT 的命中率表現(xiàn)相同,命中率均隨著緩存空間的增加而增加.其中,雙重LRU CCHT與LRU CHT 的命中率差值最大不超過(guò)0.12%,粗粒度LRU CCHT 與LRU CHT 的命中率差值最大不超過(guò)0.22%.在latest 分布的兩種工作負(fù)載中,雙重LRU CCHT 與LRU CHT 的命中率差值最大不超過(guò)0.18%,粗粒度LRU CCHT 與LRU CHT 的命中率差值最大不超過(guò)0.56%.CCHT 中引入了在散列表桶內(nèi)無(wú)空閑槽時(shí),通過(guò)桶內(nèi)LRU 算法踢出槽用于插入操作.CCHT 相對(duì)LRU CHT 和LRU 開(kāi)散列表增加了緩存踢出次數(shù),導(dǎo)致了命中率的偏差.同時(shí),由于采用了基于LRU 隊(duì)列的踢出策略,保證了CCHT 的命中率相對(duì)CHT 偏差要小.

Fig.8 Cache hit radio with hash table size圖8 命中率隨緩存空間大小的變化

5.4 索引開(kāi)銷分析

索引開(kāi)銷是指,在存儲(chǔ)過(guò)程中,當(dāng)緩存空間已滿時(shí),LRU 隊(duì)列中槽索引指針的數(shù)目.CCHT 在移除CHT 置換操作的同時(shí),引入了用于LRU 隊(duì)列的槽指針?biāo)饕臻g開(kāi)銷.本節(jié)實(shí)驗(yàn)分析了雙重LRU CCHT 與粗粒度LRU CCHT 在不同緩存空間大小情況下的索引開(kāi)銷,見(jiàn)表3.當(dāng)緩存空間大小與散列表大小比值大于等于30%時(shí),粗粒度LRU CCHT 的開(kāi)銷明顯小于雙重LRU CCHT 的開(kāi)銷.當(dāng)緩存空間大小與散列表大小的比值為90%時(shí),粗粒度LRU CCHT 比雙重LRU CCHT 減少了31.71%.當(dāng)比值小于等于20%時(shí),粗粒度LRU CCHT 索引開(kāi)銷大于雙重LRU CCHT 的開(kāi)銷,原因是粗粒度LRU 的一部分索引開(kāi)銷來(lái)源于散列表散列值對(duì)應(yīng)桶之間的索引,沒(méi)有隨緩存空間大小的變化而變化.當(dāng)緩存空間增大后,使用的槽增多,索引開(kāi)銷主要來(lái)源于槽間的鏈接索引.而雙重LRU CCHT 的全局LRU 隊(duì)列的槽索引開(kāi)銷大于粗粒度LRU CCHT 的開(kāi)銷,導(dǎo)致了兩種CCHT 算法的開(kāi)銷比值逐漸增加.

Table 3 The point count with different cache size for CCHT表3 CCHT 在不同緩存大小情況下的指針?biāo)饕_(kāi)銷

5.5 CCHT在CPUGPU上的吞吐性能

我們將CCHT 在CPU+GPU 異構(gòu)服務(wù)器環(huán)境上的吞吐性能進(jìn)行了實(shí)驗(yàn).在CPUGPU 異構(gòu)環(huán)境上的吞吐性能是指CCHT 每秒鐘處理的請(qǐng)求數(shù).在80%緩存空間占比的工作負(fù)載下,性能實(shí)驗(yàn)結(jié)果如圖9 所示.在不同的工作負(fù)載中,CCHT 相對(duì)LRU CHT、Random CHT 和LRU 開(kāi)散列表均有顯著的性能提升,最高達(dá)126.43 倍、143.17倍和1.78 倍.其中,造成LRU CHT 和Random CHT 性能最低的原因是對(duì)于CHT 的讀寫請(qǐng)求只能順序執(zhí)行,無(wú)法并發(fā)執(zhí)行,進(jìn)而導(dǎo)致每次操作類型切換時(shí),需要通過(guò)PCI-E 總線進(jìn)行數(shù)據(jù)傳輸,帶來(lái)了頻繁的內(nèi)核上下文切換與驅(qū)動(dòng)調(diào)用,最終導(dǎo)致了性能的大幅度降低,甚至遠(yuǎn)低于CPU 平臺(tái)上的LRU 開(kāi)散列算法的性能.相對(duì)于LRU CHT,CCHT 支持了所有操作類型的并發(fā)執(zhí)行,最大程度地利用了GPU 上的流處理器等硬件并發(fā)資源,同時(shí)有效減少了CPU 與GPU 之間由于頻繁的數(shù)據(jù)傳輸帶來(lái)的額外開(kāi)銷;去除了寫操作在高負(fù)載率下頻發(fā)的置換操作,減少了GPU 處理過(guò)程中的內(nèi)存訪問(wèn)次數(shù),使散列表索引訪問(wèn)性能得到提升.

Fig.9 Performance on workloads with 80% cache space size/hash table size圖9 在80%緩存空間工作負(fù)載中的性能表現(xiàn)

5.6 CCHT在CPUGPU上的延遲

我們將CCHT 在CPU+GPU 異構(gòu)服務(wù)器環(huán)境上的延遲進(jìn)行了實(shí)驗(yàn).延遲實(shí)驗(yàn)包括在CPU+GPU 異構(gòu)服務(wù)器環(huán)境上的數(shù)據(jù)傳輸延遲和單次操作的平均延遲.其中,數(shù)據(jù)傳輸延遲表示散列表在運(yùn)行過(guò)程中單次調(diào)用GPU時(shí),數(shù)據(jù)在CPU 和GPU 內(nèi)存間傳輸?shù)难舆t時(shí)間.在CCHT 中具體是指調(diào)用GPU 處理散列表請(qǐng)求時(shí),請(qǐng)求數(shù)據(jù)與操作命令緩沖區(qū)由CPU 內(nèi)存拷貝到GPU 內(nèi)存和請(qǐng)求結(jié)果由GPU 內(nèi)存拷貝到CPU 內(nèi)存的時(shí)間總和.數(shù)據(jù)傳輸延遲時(shí)間見(jiàn)表4,4 種散列表在各工作負(fù)載中單次調(diào)用GPU 數(shù)據(jù)傳輸?shù)囊?guī)模相同,我們采用以80%緩存空間占比的latest、query 100%工作負(fù)載為代表進(jìn)行實(shí)驗(yàn)驗(yàn)證.其中,雙重LRU CCHT 和粗粒度LRU CCHT 的數(shù)據(jù)傳輸延遲均高于LRU CHT 和隨機(jī)CHT,原因是CCHT 采用了批處理操作,允許散列表在GPU 上大規(guī)模并發(fā)處理請(qǐng)求.以實(shí)驗(yàn)設(shè)置的批處理閾值2 000 為例,CCHT 在調(diào)用GPU 時(shí),單次的傳輸數(shù)據(jù)包括2 000 個(gè)操作數(shù)據(jù)和操作請(qǐng)求類型,平均單個(gè)操作數(shù)據(jù)和操作請(qǐng)求類型的傳輸延遲遠(yuǎn)低于LRU CHT 和隨機(jī)CHT.

Table 4 CPUGPU data transfer delay表4 CPUGPU 數(shù)據(jù)傳輸延時(shí)

進(jìn)一步地,我們對(duì)單次操作的平均延遲進(jìn)行了對(duì)比評(píng)估,即散列表處理單次請(qǐng)求在CPU 或GPU 環(huán)境上的平均延遲時(shí)間.其中,LRU 開(kāi)散列表為單次請(qǐng)求處理在CPU 環(huán)境上的平均延遲時(shí)間,其余散列表為單次請(qǐng)求處理在GPU 環(huán)境上的平均延遲時(shí)間.單次操作的平均延遲如圖10 所示.雙重LRU CCHT 和粗粒度LRU CCHT 的延遲時(shí)間高于其他散列表,原因是CCHT 實(shí)現(xiàn)了GPU 上大規(guī)模的并發(fā)操作,雖然通過(guò)warp 分配避免了分支等待的延遲開(kāi)銷,但各線程間仍存在著對(duì)于槽和LRU 隊(duì)列鎖的競(jìng)爭(zhēng)操作,以及在同一次批處理中的同步開(kāi)銷,即執(zhí)行完操作的線程需等待未執(zhí)行完操作的線程完成后一同返回.這類操作均帶來(lái)了額外的開(kāi)銷,導(dǎo)致了延遲的增加.同時(shí),從實(shí)驗(yàn)結(jié)果可以看出,粗粒度LRU CCHT 的延遲同樣高于雙重LRU CCHT.這是因?yàn)榇至６萀RU CCHT 在全局和桶內(nèi)共用的同一LRU 隊(duì)列均在GPU 環(huán)境上進(jìn)行操作,相對(duì)雙重LRU CCHT 僅桶內(nèi)鎖在GPU環(huán)境上進(jìn)行操作,粗粒度LRU CCHT 存在更多的鎖競(jìng)爭(zhēng).LRU CHT 和隨機(jī)CHT 雖然低于前兩者,但由于受高負(fù)載下可能發(fā)生插入操作出現(xiàn)頻繁槽數(shù)據(jù)置換的影響,單次延遲最高達(dá)到了143μs,遠(yuǎn)高于平均延遲時(shí)間.LRU 開(kāi)散列表由于沒(méi)有鎖競(jìng)爭(zhēng)以及運(yùn)行在CPU 環(huán)境上,延遲時(shí)間在0.36μs～0.49μs.

Fig.10 Latency on workloads with 80% cache space size/hash table size圖10 在80%緩存空間工作負(fù)載中的延遲表現(xiàn)

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

數(shù)據(jù)索引的性能依賴于平均訪問(wèn)內(nèi)存數(shù).傳統(tǒng)的CHT 數(shù)據(jù)索引在緩存中應(yīng)用時(shí),當(dāng)緩存空間大小與CHT空間比值較高時(shí),CHT 頻繁的踢出替換方法增加了內(nèi)存訪問(wèn)數(shù),進(jìn)而對(duì)緩存性能造成了影響.本文分析了基于鍵值的內(nèi)存緩存系統(tǒng)命中率與索引開(kāi)銷因素,依據(jù)索引指針開(kāi)銷給出了雙重LRU CCHT 和粗粒度LRU CCHT,提供了用于CPUGPU 環(huán)境下減少總線傳輸與GPU 內(nèi)存占用的多級(jí)索引數(shù)據(jù)結(jié)構(gòu),并在CPUGPU 異構(gòu)環(huán)境下加以實(shí)現(xiàn).通過(guò)實(shí)驗(yàn)驗(yàn)證,CCHT 在保證緩存命中率的同時(shí),能夠有效地減少內(nèi)存訪問(wèn)次數(shù),在GPU 上有良好的可擴(kuò)展性與吞吐性能.

未來(lái)的工作我們希望進(jìn)一步優(yōu)化索引指針的開(kāi)銷,提升緩存的命中率.在GPU 的實(shí)現(xiàn)方法中,考慮通過(guò)優(yōu)化槽單元鎖和LRU 隊(duì)列鎖以提升并發(fā)插入的性能,在散列任務(wù)提交任務(wù)隊(duì)列前識(shí)別任務(wù)類型,預(yù)先分配任務(wù)執(zhí)行所在的warp,達(dá)到同一warp 中并發(fā)執(zhí)行多個(gè)散列表操作,并達(dá)到線程粒度的并發(fā)性能,提升GPU 硬件資源利用率.