多核系統(tǒng)并發(fā)哈希表研究

多核系統(tǒng)并發(fā)哈希表研究隨著多處理器技術(shù)的日臻成熟以及集成到單個(gè)處理器上的處理器核心數(shù)量的日趨增加,計(jì)算機(jī)的運(yùn)算能力的瓶頸不斷被打破,同時(shí)這也為設(shè)計(jì)具有高可擴(kuò)展性的并發(fā)數(shù)據(jù)結(jié)構(gòu)以及開發(fā)基于多核架構(gòu)的高性能軟件系統(tǒng)提出了挑戰(zhàn)。并發(fā)哈希表是一種重要的并發(fā)數(shù)據(jù)結(jié)構(gòu),因其處理元素的開銷為常數(shù)時(shí)間的特性被廣泛應(yīng)用于多核架構(gòu)的軟件系統(tǒng)開發(fā)。在并發(fā)哈希表的設(shè)計(jì)、優(yōu)化以及應(yīng)用中,處理器的體系結(jié)構(gòu),緩存一致性協(xié)議,內(nèi)存帶寬,內(nèi)存訪問延遲以及多線程的同步機(jī)制都對(duì)其性能產(chǎn)生重大影響。本文針對(duì)基于多核系統(tǒng)的并發(fā)哈希表做了如下工作:首先,設(shè)計(jì)了用于并發(fā)哈希表的測(cè)試、評(píng)估的統(tǒng)一測(cè)試框架CHTBench。CHTBench是目前第一個(gè)用于并發(fā)哈希表性能比較與評(píng)估的,能保證測(cè)試結(jié)果公平性與客觀性的測(cè)試框架。它提供統(tǒng)一的測(cè)試接口,具有可配置的線程與核的映射關(guān)系,能夠測(cè)試不同規(guī)模的數(shù)據(jù)集以及數(shù)據(jù)集中更新操作的比重等。此外,CHTBench使用sspfd進(jìn)行延遲的測(cè)算,綜合考察不同并發(fā)哈希表線程擴(kuò)展性,查詢和更新吞吐量等宏觀指標(biāo)。結(jié)合其它的工具,如likwid對(duì)緩存命中率,內(nèi)存帶寬,跨內(nèi)存節(jié)點(diǎn)通信開銷等微觀指標(biāo)進(jìn)行分析以及sspfd對(duì)各種操作類型的延遲進(jìn)行比較。使用CHTBench可以為并發(fā)哈希表的評(píng)估和比較提供相對(duì)公平的測(cè)試環(huán)境。第二,基于CHTBench測(cè)試框架對(duì)現(xiàn)有的幾種具有代表性的并發(fā)哈希表在四個(gè)不同的多核系統(tǒng)上進(jìn)行了深入的剖析。對(duì)并發(fā)哈希表的評(píng)估選用的性能指標(biāo)涵蓋宏觀和微觀兩個(gè)層面,包括吞吐量的線程擴(kuò)展性,延遲,分層內(nèi)存結(jié)構(gòu)對(duì)性能的影響,不同線程與核映射方式之間的性能差異,同步機(jī)制的性能評(píng)估以及內(nèi)存消耗。通過對(duì)上述指標(biāo)的分析,找出現(xiàn)有并發(fā)哈希表設(shè)計(jì)方法中存在的問題以及可能的性能瓶頸,分析總結(jié)了8條設(shè)計(jì)、優(yōu)化并發(fā)哈希表的最佳實(shí)踐原則,為將來進(jìn)一步設(shè)計(jì)基于多核系統(tǒng)的、具有高可擴(kuò)展性的并發(fā)哈希表奠定理論和實(shí)踐基礎(chǔ)。根據(jù)對(duì)比現(xiàn)有文獻(xiàn)以及相關(guān)研究工作,我們對(duì)于并發(fā)哈希表的評(píng)估所用的方法和涉及的評(píng)估指標(biāo)是迄今為止最全面的。第三,使用Intel限制性事務(wù)內(nèi)存(RTM)實(shí)現(xiàn)了基于硬件事務(wù)內(nèi)存的緩存行哈希表。使用全局鎖實(shí)現(xiàn)了基于RTM的緩存行哈希表。實(shí)驗(yàn)評(píng)估結(jié)果表明,當(dāng)數(shù)據(jù)集的規(guī)模大于最后一級(jí)緩存容量時(shí),基于RTM的緩存行哈希表的性能是使用傳統(tǒng)的細(xì)粒度鎖方法實(shí)現(xiàn)的緩存行哈希表的120%。使用硬件事務(wù)內(nèi)存進(jìn)行并發(fā)哈希表的設(shè)計(jì)真正做到了粗粒度鎖方法的簡(jiǎn)便與細(xì)粒度鎖方法的高性能的有機(jī)結(jié)合。同時(shí),為了消除IntelTSX的Lemming效應(yīng)對(duì)性能的影響,設(shè)計(jì)了兩種軟件輔助方法:軟件輔助的鎖省略方法(SLR)和軟件輔助的沖突管理方法(SCM)。實(shí)驗(yàn)結(jié)果表明,這兩種方法對(duì)基于RTM的緩存行哈希表性能的提升比使用Intel官方推薦的RTMRetry機(jī)制更明顯。最后,使用不完整鍵Cuckoo哈希方法設(shè)計(jì)并實(shí)現(xiàn)了支持多線程并發(fā)的Cuckoo過濾器。這是迄今為止第一款支持多線程并發(fā)的過濾器實(shí)現(xiàn),同時(shí)也是第一款基于硬件事務(wù)內(nèi)存的過濾器。原始的布隆過濾器不支持刪除操作,實(shí)現(xiàn)刪除操作需要引入額外的空間開銷,通過使用不完整鍵Cuckoo哈希方法,通過哈希函數(shù)生成指紋,利用Cuckoo哈希表多路組相連能夠存儲(chǔ)多個(gè)相同的指紋信息的特點(diǎn)實(shí)現(xiàn)了刪除操作,不額外增加過濾器的空間開銷。使用基于IntelRTM的讀寫鎖實(shí)現(xiàn)了多線程并發(fā)的Cuckoo過濾器。實(shí)驗(yàn)評(píng)估表明,并發(fā)Cuckoo過濾器的初始化速度是使用單個(gè)線程初始化的10倍,查詢操作的性能是單個(gè)線程的38倍,處理