一種適應GPU的混合訪問緩存索引框架?

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

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

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

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

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

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

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

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

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

1 相關工作

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

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

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

2 研究背景

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

2.1 CHT基本概念

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

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

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

當進行查詢時,通過H1與H2計算散列值,查找對應位置的桶中槽內鍵值數據,通過遍歷與比較槽內鍵數據來獲取存儲的值數據.

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

2.2 CHT的典型實現

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

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

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

2.3 基于LRU的緩存替換策略

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

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

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

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

2.4 CUDA編程技術

計算統一設備架構(compute unified device architecture,簡稱CUDA)是顯卡廠商NVIDIA 推出的并行計算架構,已逐步發展成為NVIDIA GPU 的編程標準規范.

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

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

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

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

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

3.1 面向內存緩存的散列索引分析

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

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

3.2 雙重LRU CCHT緩存索引方法

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

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

Fig.3 Double LRU CCHT structure圖3 雙重LRU 的CCHT 緩存索引結構

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

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

通過雙重LRU CCHT,將原有鍵值數據插入過程中的踢出置換操作變為緩存替換,去除了由于置換操作引發的內存訪問次數和查詢空閑槽的時間.雙重LRU CCHT 通過全局LRU 隊列和桶內LRU 隊列獨立使用保證了內存緩存系統的命中率.這種方法相對于LRU CHT,增加了用于桶內LRU 隊列的指針存儲空間開銷.因此,我們提出了粗粒度LRU CCHT,相對雙重LRU CCHT,節省了指針占用存儲空間的開銷.

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

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

3.3 粗粒度LRU CCHT方法

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

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

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

Fig.4 Coarse LRU CCHT structure圖4 粗粒度LRU CCHT 緩存索引結構

4 CCHT 在面向CPUGPU 異構環境上的實現

根據第3 節中CCHT 的方法描述,本節主要介紹了CCHT 在CPUGPU 異構環境上進行的實現.其中,第4.1節描述了面向CPUGPU 異構存儲下的多級數據索引結構,第4.2 節給出了異構環境下CCHT 的應用接口函數,第4.3 節描述了CCHT 的實現細節,第4.4 節給出了CCHT 在實現過程中的優化.

4.1 異構存儲下的多級索引數據結構

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

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

Fig.5 The CCHT data structure under CPUGPU圖5 CPUGPU 下的CCHT 數據結構

4.2 異構環境下CCHT的應用接口函數

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

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

Table 1 Interface and implemented methods on CPU表1 CPU 接口與實現函數

Table 2 Kernel method on GPU表2 GPU 核函數

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

4.3 實現細節

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

在CPU 上操作鍵值數據的函數,將其他程序調用傳遞進的鍵值數據與操作,復制至CPU內存中的鍵值數據與任務的緩沖隊列中.所有操作鍵值數據的函數共用同一數據與任務緩沖隊列,允許任務緩沖隊列中包含多個寫操作和多個讀操作.當達到向GPU 提交任務數的閾值時,則調用flush_ops 函數,通過global 函數CCHT_process 向GPU 傳遞數據及相應的操作標識.當向GPU 提交的任務執行完成后,將結果返回至指定的存儲區域.在CPU 上運行的程序對結果進一步處理,如判斷讀操作是否命中、更新可用緩存空間大小等.

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

4.4 優化細節

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

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

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

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

5 實驗結果與分析

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

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

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

5.1 插入平均訪存

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

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

5.2 全局平均訪存

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

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

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

5.3 命中率

命中率是指在工作負載測試集加載過程中,查詢成功的次數占所有查詢次數的比值.圖8 描述了在6 種不同的工作負載下,5 種緩存索引算法的命中率.在zipf 和uniform 分布的4 種工作負載中,雙重LRU CCHT 和粗粒度LRU CCHT 與LRU CHT 的命中率表現相同,命中率均隨著緩存空間的增加而增加.其中,雙重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 中引入了在散列表桶內無空閑槽時,通過桶內LRU 算法踢出槽用于插入操作.CCHT 相對LRU CHT 和LRU 開散列表增加了緩存踢出次數,導致了命中率的偏差.同時,由于采用了基于LRU 隊列的踢出策略,保證了CCHT 的命中率相對CHT 偏差要小.

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

5.4 索引開銷分析

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

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

5.5 CCHT在CPUGPU上的吞吐性能

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

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

5.6 CCHT在CPUGPU上的延遲

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

Table 4 CPUGPU data transfer delay表4 CPUGPU 數據傳輸延時

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

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

6 結束語

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

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