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

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

2 研究背景

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

2.1 CHT基本概念

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

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

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

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

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

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

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

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

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

2.3 基于LRU的緩存替換策略

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

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

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

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

2.4 CUDA編程技術(shù)

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

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

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

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

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

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

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

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

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

3.2 雙重LRU CCHT緩存索引方法

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

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

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

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

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

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

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

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

3.3 粗粒度LRU CCHT方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.3 實現(xiàn)細節(jié)

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

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

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

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

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

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

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

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

5 實驗結(jié)果與分析

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

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

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

5.1 插入平均訪存

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

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

5.2 全局平均訪存

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

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

當緩存空間大小與散列表比值大于60%時,雙重LRU CCHT 與粗粒度LRU CCHT 均低于其他算法.其中,當query 占比為50%時,雙重LRU CCHT 與粗粒度LRU CCHT 的效果對比LRU CHT 更加明顯地減少了平均訪問內(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%的工作負載中,有大量的插入操作.隨著緩存空間的增加,LRU CHT 和隨機CHT 方法需要更多的踢出替換操作以獲得空閑的索引空間,導(dǎo)致了大量的內(nèi)存訪問.而雙重LRU CCHT 和粗粒度LRU CCHT 隨著緩存空間的增加,沒有訪問更多的索引位置.

5.3 命中率

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

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

5.4 索引開銷分析

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

Table 3 The point count with different cache size for CCHT表3 CCHT 在不同緩存大小情況下的指針索引開銷

5.5 CCHT在CPUGPU上的吞吐性能

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

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

5.6 CCHT在CPUGPU上的延遲

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

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

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

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

6 結(jié)束語

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

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