蔣 捷 楊 仝，2 張夢瑜 代亞非 黃 亮 鄭廉清

1(北京大學信息科學技術學院 北京 100871) 2(國防科學技術大學高性能計算協(xié)同創(chuàng)新中心 長沙 410073) 3(94782部隊65分隊 杭州 310021) 4(西京學院控制工程系 西安 710123)

(jiangjiecs@pku.edu.cn)

DCuckoo：基于片內(nèi)摘要的高性能散列表

蔣 捷1楊 仝1，2張夢瑜1代亞非1黃 亮3鄭廉清4

1(北京大學信息科學技術學院 北京 100871)2(國防科學技術大學高性能計算協(xié)同創(chuàng)新中心 長沙 410073)3(94782部隊65分隊 杭州 310021)4(西京學院控制工程系 西安 710123)

(jiangjiecs@pku.edu.cn)

散列表(Hash table)由于其支持高效的記錄更新與檢索操作，在計算機相關的各個領域中有著廣泛的應用.但散列表有2個明顯的缺點：沖突和低效的內(nèi)存利用.最小完美散列使用N個位置存儲N條記錄，解決了沖突和空間效率的問題，但該算法不支持增量的更新.目標是設計一種高效的散列表，能夠支持高速查詢、最壞情況可以保證的高速更新、高效的空間使用以及動態(tài)的容量改變.結(jié)合 Cuckoo 散列和 d-left 散列的實現(xiàn)，提出了一個新的散列表設計方案——DCuckoo.DCuckoo 使用多級子表并應用了 Cuckoo 散列中移動已有元素的機制以提高裝載率，且只保留了最末級子表的指針以減少空間浪費.為了進一步優(yōu)化查詢性能，DCuckoo 在片內(nèi)內(nèi)存中使用指紋和位圖作為摘要，在查詢時先匹配指紋，以減少對片外內(nèi)存的訪問次數(shù).對 DCuckoo 進行了一系列實驗，與其他5種散列表進行比較，發(fā)現(xiàn) DCuckoo 達到了設計目標，并且在各項指標上均好于已有的散列表設計.

散列表；檢索；指紋；片內(nèi)內(nèi)存；鍵值存儲

散列表(Hash table)是根據(jù)關鍵字直接訪問元素存儲位置的一種數(shù)據(jù)結(jié)構(gòu).由于散列表支持高效的查詢和更新操作，所以被廣泛應用于各個領域之中，如 IP 查找[1-4]、負載均衡[5-6]、鍵值存儲系統(tǒng)(key value store)[7-8]等.散列函數(shù)在本質(zhì)上是將元素從大的定義域映射到小的值域上的一種變換，因此多個元素被映射到同一個位置是不可避免的，在散列表中這種情況被稱為沖突(collision).當沖突發(fā)生時，插入散列表的記錄將被放到其他位置，這會影響散列表的插入查詢效率以及內(nèi)存利用效率.因此，散列表算法設計中需要考慮的一個重要因素就是如何減少沖突與解決沖突.

散列表的設計主要有4 個目標：

1) 高效的查詢操作.查詢操作主要是對元素鍵(key)的比較，由于這一操作涉及到的內(nèi)存訪問相對散列值的計算時間需要消耗更多的指令周期.因此，可以用訪存次數(shù)作為查詢性能評價的指標.

2) 高效的更新操作.在插入元素的過程中，需要檢測待插入元素是否已經(jīng)存在，因此也涉及元素鍵值的比較，同樣可以用更新時訪存次數(shù)的多少作為衡量標準.

3) 高效的空間利用率.很多散列表設計為了保證性能需要一些桶為空，這就造成一定的空間浪費.此外，指針的使用也會占據(jù)一定的空間.一個高效的散列表應當盡可能減少這些空間浪費，提高內(nèi)存利用率.

4) 支持動態(tài)的容量改變.在很多應用中，插入散列表的元素規(guī)模是在不斷變化的，因此散列表也需要動態(tài)地改變?nèi)萘恳员苊饪臻g浪費或性能下降，而改變?nèi)萘坎僮鞯臅r間與空間代價希望盡可能的小.

目前針對散列表的設計已有大量的研究，但這些研究都存在著一些缺陷，尚未有研究能同時解決以上4個問題.開散列法使用鏈表解決沖突，但指針的引入造成了一定的空間浪費.閉散列法依照探測序列安放元素，但其插入操作可能會失敗.Cuckoo散列[9]為每個元素提供2個候選位置，在插入過程中若發(fā)生沖突會移動已有元素的位置，但這一過程中可能需要移動大量的元素造成性能低下.而 d-left 散列[10]則通過為元素提供更多的候選位置提高裝載率，其缺點在于查詢時需要依次探測這些候選位置，即訪存次數(shù)較多.完美散列[11]為給定的集合生成散列函數(shù)，避免了沖突的存在，但構(gòu)造完美散列函數(shù)開銷較大，所以并不適用于需要更新的散列表.

以 d-left 散列為代表的多選擇(multi-choice)散列最大的問題就是其較多的訪存次數(shù).文獻[12-14]借助片內(nèi)內(nèi)存(on-chip memory)高速訪問的特點存儲散列表的摘要信息.在查詢散列表前首先查詢摘要，獲得“元素可能在哪個桶中”這一信息，再查詢片外(off-chip)的散列表，從而減少了訪存次數(shù)，加快了查詢速度.這一類研究中多使用布隆過濾器(Bloom filter)[15]作為片內(nèi)摘要，但其缺點在于布隆過濾器不支持刪除操作.

本文結(jié)合Cuckoo散列、d-left散列以及片內(nèi)摘要的思想，提出了一種新的散列表設計方案——DCuckoo.DCuckoo以d-left散列為基礎，即使用d個子表，每個元素在每個子表中都有一個候選位置，并在這d個子表中運用Cuckoo散列移動元素的機制，從而實現(xiàn)較高的裝載率；為了減少指針造成的空間浪費，只保留最后一級子表的指針并減小該子表的長度；同時在片內(nèi)內(nèi)存中使用指紋(fingerprint)和位圖(bitmap)作為摘要信息以減少對片外數(shù)據(jù)的訪問，在支持高效的查詢操作的同時也支持了刪除操作.

本文實現(xiàn)了DCuckoo算法對并對其進行了實驗，并與其他5種散列表設計進行了比較，結(jié)果表明DCuckoo算法實現(xiàn)了引言第2段所述的前3個設計目標：查詢平均查找長度約為1；更新平均查找長度最壞情況可控；裝載率達到95%實現(xiàn)了高效的空間利用.而多級子表的結(jié)構(gòu)天然支持動態(tài)容量的改變：只需要動態(tài)地改變子表數(shù)量而無需重構(gòu)整個散列表.因此，DCuckoo實現(xiàn)了以上4個設計目標.

1 相關工作

1.1Cuckoo散列

Cuckoo散列[9]使用2個散列函數(shù)h1(x)和h2(x)，將元素映射到2個不同的位置，即每個元素有2個候選位置.Cuckoo散列的原理如下：插入某元素x時，若2個候選位置中至少有一個為空，則將元素直接插入；若2個位置都被其他元素占據(jù)，則任意選擇一個元素將其“踢出”(kick)，并在此位置插入x，被踢走的元素y則需要去查看它的另一個候選位置，若該位置為空，則直接插入，否則繼續(xù)將占據(jù)這個位置的元素踢走，將y插入，重復這一踢的過程直到所有的元素都被插入到表中，或者踢的次數(shù)達到一定的上限(如500次)，這也是該算法被命名為布谷鳥(Cuckoo)的原因.

通過這種方式，散列表中的元素位置不斷被調(diào)整到合適的空位，因此可以實現(xiàn)較高的裝載率(gt;95%)，且其查詢十分簡單：最多只需要探測2個位置.Cuckoo 散列的不足之處在于：1)更新低效且可能產(chǎn)生更新失??；2)盡管Cuckoo散列最壞情況只需要2次記錄探測，但平均情況下也需要1.5次，而理想的查詢訪存次數(shù)應當為1，也即 Cuckoo 散列的平均查詢性能較差.

1.2d-left散列

與Cuckoo散列不同，d-left散列[10]使用d個散列子表，而非一個完整的散列表，每一個子表都有一個與之對應的散列函數(shù)hi(x).所以任意元素在每一個子表中都有一個候選位置，且由于散列函數(shù)不同，元素在每個子表中的位置往往不同.因此當2個元素在某一個子表中沖突時，在很大概率下這2個元素不會在其他子表中沖突，因此d-left散列同樣可以實現(xiàn)較高的裝載率(gt;90%).該算法中每一個子表都是一個標準的鏈式散列表，用于解決多級子表不能處理的沖突.當插入一個元素x時，算法從左到右依次檢查每一級子表，若hi(x)的位置為空，則將x直接插入到這個子表中；若所有的候選位置都被其他元素所占據(jù)，則選擇一個鏈表長度最短(負載最小)的桶插入.而查詢時，算法依然從左到右依次探測每一個候選位置，直到找到合適的元素.無論是在插入還是查詢，算法總是從左到右依次探測各級子表，雖然這一策略導致各個子表的裝載率并不相同，但由于元素總是優(yōu)先被插入到最左邊，所以實際上查詢時從左到右的順序可以減少所需記錄探測的數(shù)量.

該算法通過多候選位置降低了沖突的概率，但缺點在于每次查詢也需要探測多個候選位置，造成查詢性能的低下.此外，d-left的每一個桶中都包含一個鏈表，而在實際的應用中這些指針往往為空缺，也需要占據(jù)一定的內(nèi)存空間，造成了空間浪費.

1.3使用片內(nèi)摘要的散列表

一般的散列表規(guī)模較大，只能存儲在片外內(nèi)存(off-chip memory)中，相對于散列值的計算，對內(nèi)存的訪問需要消耗更多的CPU指令周期.以d-left為代表的多選擇散列通過多候選位置的方式提高了散列表的裝載率，同時帶來的問題是查詢時對片外訪問的需求增加.片內(nèi)內(nèi)存(on-chip memory)具有容量小、速度快的特點.由于容量小，片內(nèi)內(nèi)存并不能容納完整的散列表，但可以存儲散列表的摘要(summary)，為片外內(nèi)存中散列表的搜索提供一些指引，如“元素可能在哪些位置出現(xiàn)”這一類信息.在查詢一個元素時，首先檢索片內(nèi)內(nèi)存的摘要[16]，獲得候選查詢位置的集合，再在片外內(nèi)存的散列表中的檢索集合中的每一個位置.

Song等人[14]首先在散列表中應用這一方法，他們提出了一種基于片內(nèi)摘要的散列表FHT(fast Hash table).FHT包含一個鏈式散列表和k個散列函數(shù)，即每個元素在散列表中有k個位置，片內(nèi)使用計數(shù)布隆過濾器(counting Bloom filter[17])作為摘要.FHT是用布隆過濾器的方式十分巧妙：在構(gòu)造散列表的過程中，插入一個元素都需要在其每個候選位置插入一個該元素的副本，并將該元素插入到片內(nèi)的布隆過濾器中；當所有元素插入完畢后，對每一個元素只保留計數(shù)布隆過濾器中最小計數(shù)器位置對應的副本，其他k-1個副本全部刪除.這樣在查詢時，只需要檢索最小計數(shù)器位置的元素即可.

Segmented 散列[12]使用d個子表，類似d-left散列，每個子表的長度相同.該算法在片內(nèi)為每個子表構(gòu)建了一個布隆過濾器，用來表示元素是否在某個子表中存在.向某子表插入一個元素時，也需要向該子表對應的布隆過濾器插入元素.在查詢時，只檢索布隆過濾器報告存在的子表即可.

Peacock散列[13]也使用布隆過濾器作為片內(nèi)摘要，但Peacock中每個子表的長度不同，各級子表的長度呈等比數(shù)列的關系依次遞減，第1級子表容量最大，作為主表.插入時從主表開始為元素尋找合適的位置，因此后面的子表主要是為了解決前面子表的沖突.這種設計方式使得大部分元素存儲在主表之中(90%)，因此在片內(nèi)不為主表設置布隆過濾器，每次檢索都要檢查主表，起到了節(jié)省片內(nèi)空間的效果.

2 DCuckoo算法

受到Cuckoo散列、d-left散列以及片內(nèi)摘要的啟發(fā)，本文提出了一個新的散列表設計DCuckoo.為方便理解，本節(jié)將對DCuckoo分為3個版本進行介紹，每一個版本都改進了上一個版本的缺點，并在最后針對散列表容量的動態(tài)調(diào)整提出了解決方案.

2.1DCuckoo1——結(jié)合d-left和Cuckoo散列

與d-left類似，DCuckoo1使用d個散列子表，每一個子表大小相同，均為標準的鏈式散列，原理圖如圖1所示:

Fig. 1 DCuckoo1 structure圖1 DCuckoo1原理圖

當插入一個元素x時，DCuckoo1首先從左到右檢查x在所有d個子表中的候選位置h1(x)，h2(x)，…，hd(x)是否有空位，如果有空位則直接插入，如果沒有則進行一系列的“踢”操作——移動散列表中已有的元素，使所有的元素在散列表中找到合適的位置.DCuckoo中所采用的踢操作與Cuckoo散列類似，只是候選位置從2個變成了d個.插入元素x時，若x在d個候選位置中沒有找到空位，首先查看其他元素是否可以通過一次移動找到合適的位置，若有則移動該元素，若沒有則隨機地從這d個候選位置中選出一個，用x將原先位于這個位置的元素y置換出，再對元素y進行插入操作.若在進行了θ次隨機踢操作之后仍無法為元素找到合適的位置，則將目前未被插入的元素插入到對應候選位置的鏈表長度最短的鏈表中.

對DCuckoo1的查詢與d-left相同，從左到右依次檢查d個子表以及對應的鏈表，若找到匹配的元素則直接返回.

通過d-left多候選位置與Cuckoo散列移動元素機制的結(jié)合，DCuckoo1實現(xiàn)高裝載率，同時避免了Cuckoo散列潛在的插入失敗的問題.但DCuckoo1也繼承了d-left的缺點：大量指針的使用造成空間浪費；查詢時需要探測多個候選位置造成性能下降.這2個問題將分別在DCuckoo2和DCuckoo3中得到解決.

2.2DCuckoo2——減少指針的數(shù)量

如1.2節(jié)所述，存儲指針需要消耗一定的內(nèi)存空間，而實際上大部分指針都不會被使用到，但算法依然為存儲指針預留了空間.因此，DCuckoo2只在最后一級子表中保留指針，并縮小該子表的長度，從而大幅度減少了指針的需求量.在插入元素時，若不能通過移動元素的方式為元素找到合適的空間，則將元素插入到最后一級子表的鏈表中.

2.3DCuckoo3——使用片內(nèi)摘要優(yōu)化查詢和插入

DCuckoo3以指紋鏡像作為摘要，而非用布隆過濾器.布隆過濾器的問題在于其不支持刪除操作，雖然可以使用計數(shù)布隆過濾器解決這一問題，但這會增加復雜性.一個指紋對應由連續(xù)r位(bit)組成的一段內(nèi)存空間，計算一個關鍵字的指紋時相當于對這個關鍵字進行了一次散列操作，將其映射到[0, 2r)這個空間中.因此指紋是對原關鍵字的一個摘要，它用很小的空間記錄該關鍵字的信息.指紋可能會產(chǎn)生沖突，即一個指紋可能會對應多個關鍵字.DCuckoo3為片外的所有子表建立一個指紋鏡像，即片外的每一個桶都對應片內(nèi)一個指紋.在查詢一個關鍵字時，先檢查片內(nèi)的指紋鏡像中對應的指紋是否與該關鍵字的指紋相匹配，若匹配，再到片外的子表中去檢索該關鍵字，從而大幅度減少了查詢操作所需要的訪存次數(shù).由于指紋可能會產(chǎn)生沖突，指紋匹配并不一定代表片外對應位置的桶中存儲著與該關鍵字匹配的元素，也即指紋的方式也具有一定的假陽性，與指紋的長度有關.

由于最后一級子表中可能存在著鏈表，而該子表中對應的指紋鏡像只能提供位于桶中元素的信息，所以在查詢時，如果在指紋報告元素存在的位置沒有找到對應元素，則一定需要檢查最后一級子表對應的鏈表，因為該鏈表的信息沒有在摘要中表示.當查詢操作所查詢的元素不在散列表中時，這會造成大量額外的訪存.對于這一問題，DCuckoo3針對最后一級子表對應的指紋鏡像做一些額外的處理：這些指紋比標準的指紋多1位，用來表示片外子表中是否包含鏈表.在檢索時，若這一位為0，則無需對鏈表進行額外的探測.

片內(nèi)摘要也可以用來優(yōu)化插入效率.在插入1個元素時，首先在片內(nèi)摘要中查找該元素對應的d個位置是否都有指紋，若某位置無指紋意味著對應的片外桶中沒有元素，可以直接插入.通過這種方式，插入元素所需的訪存次數(shù)可以大幅減少.DCuckoo3最終原理圖如圖2所示：

Fig. 2 DCuckoo3 structure圖2 DCuckoo3原理圖

2.4子表動態(tài)調(diào)整

在很多應用中，需要插入到散列表中的元素集合可能會發(fā)生很大的變化，這時最開始的散列表可能就會顯得過大或過小.處理這一問題最簡單的方法是重建整個表，很多散列表使用這一方法進行重構(gòu)，如Cuckoo散列、開散列散列表等.整體重構(gòu)的處理方式缺點在于需要消耗大量的計算資源與內(nèi)存空間，因為重構(gòu)需要消耗大量的時間，而在這過程中系統(tǒng)應避免阻塞在重構(gòu)過程中，所以重構(gòu)的實現(xiàn)往往是在新的地址空間創(chuàng)建一個新的更大或更小的散列表，此時舊的散列表繼續(xù)支持查詢操作，當新表建立完畢后，再將舊表拋棄.得益于多級散列表的結(jié)構(gòu)，在DCuckoo中可以很容易實現(xiàn)增加或者刪除一個子表，避免因為鏈表長度過長或者裝載率過高造成的潛在的性能下降問題.具體操作如下：當鏈表元素總數(shù)超過某一閾值或者整體散列表的裝載率超過某一閾值時，增加一級散列子表，并將之前最后一級子表中鏈表上的元素進行重新插入操作；當散列表的整體裝載率低于某一閾值時，為了避免空閑的桶造成的空間浪費，移除其中的某一級子表，并將該子表上的元素進行一次重新插入操作.因此DCuckoo可以很方便地支持散列表的重構(gòu)操作.

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

實驗中采用隨機生成的數(shù)據(jù)集，數(shù)據(jù)關鍵字的長度為8B，值類型為32b整形(int)，插入數(shù)據(jù)集的規(guī)模為106個元素.查詢數(shù)據(jù)集符合Zipf分布(在鍵值存儲的實際應用場景中，查詢請求大多符合Zipf分布[18])，規(guī)模為107個元素，Zipf分布偏度(skewness)為0.99，與數(shù)據(jù)庫測試中經(jīng)常使用的YCSB相同[19].

散列表設置方面，DCuckoo實現(xiàn)使用8級散列子表，最后一級子表的長度為普通子表長度的一半，指紋長度為15 b；在插入過程中如果發(fā)生沖突，只允許一次移動元素而不允許盲踢操作(θ=0).為了方便比較，本文另外實現(xiàn)了其他5種散列算法：開散列法(open hashing)、雙散列法(double hashing)、Cuckoo散列、d-left散列、FHT，其中雙散列和Cuckoo散列另外使用了一個大小與原始散列表大小相同的鏈式散列表用于解決沖突；為保證插入性能可控，雙散列最大探測長度為16，Cuckoo散列踢操作上限為500次.d-left散列使用8級子表，F(xiàn)HT使用8個散列函數(shù).實驗結(jié)果表明DCuckoo在裝載率、查詢效率等方面均優(yōu)于已有的散列表設計，具體結(jié)果如下所示.

3.1裝載率

在這一實驗中對所有的6種散列表使用相同的數(shù)據(jù)集，所有散列表大小均為插入數(shù)據(jù)集規(guī)模的1.05倍，即每個散列表包含1.05×106個桶，每插入10 000個元素后記錄此時散列表的裝載率，結(jié)果如圖3所示.可以看到，DCuckoo、雙散列法、Cuckoo都達到了非常理想的裝載率，分別為95.17%，95.20%，95.18%，表明幾乎所有的元素都在散列表中(滿裝載率約為100/105≈95.24%).但雙散列法和Cuckoo散列都使用了額外的鏈式散列表用于解決沖突.裝載率高意味著使用相同數(shù)量的桶可以容納更多的元素，因此在插入相同數(shù)量元素的情況下，裝載率高的散列表可以預先分配更少的片外內(nèi)存空間.裝載率隨插入元素數(shù)量的變化如圖3所示：

Fig. 3 Load factor with number of insertions圖3 裝載率隨插入元素數(shù)量的變化

3.2查詢平均訪存

圖4表示了將同樣的元素插入到不同規(guī)模的散列表之后散列表的查詢性能.橫坐標代表散列表中桶的總數(shù)與插入元素數(shù)目的比值，縱坐標表示散列表構(gòu)造完畢后一次查詢所需的訪存次數(shù).可以看到DCuckoo在所有實驗條件下都能達到接近1的平均查詢訪存次數(shù)，而其他散列表只有在散列表足夠大的情況下才能達到這一水平.

Fig. 4 Average memory access with Hash table size圖4 查詢平均訪存次數(shù)隨散列表大小的變化

3.3插入平均訪存

插入性能的實驗過程同裝載率測試，即在構(gòu)建散列表的不同階段進行測試，如圖5所示.可以看到隨著散列表逐漸變滿，各個散列表的插入性能都有所下降，開散列法的插入訪存相對穩(wěn)定，這是因為在不考慮重復插入的情況，沖突發(fā)生時開散列法只需要將新建的元素放到散列表表頭即可.DCuckoo在插入前9×105個元素時性能最優(yōu)，盡管在最后有所下降，但擴充子表的方式可以保證最壞情況下可控.而Cuckoo散列由于最多可能執(zhí)行500次踢操作，隨著表中元素數(shù)目增多，插入性能會劇烈下降.插入平均訪存次數(shù)隨插入元素數(shù)量的變化如圖5所示:

Fig. 5 Average memory access per insertion圖5 插入平均訪存次數(shù)的變化

3.4DCuckoo盲踢次數(shù)對沖突元素數(shù)目的影響

在3.1～3.3節(jié)的實驗中，DCuckoo算法中不允許進行盲踢操作，若不能通過移動一個元素成功插入，則直接將元素插入到最后一級子表的鏈表之中.本文在不同的數(shù)據(jù)集下對盲踢次數(shù)與沖突元素數(shù)目之間的關系進行了實驗，結(jié)果如表1所示：

Table 1 Number of Collision Items After θ Blind Kicks表1 θ次盲踢后沖突元素數(shù)目

從表1可以看到，當散列表大小為插入元素數(shù)目的1.05倍時，4次盲踢之內(nèi)就可以幾乎將所有的元素插入到散列表中，從而避免查詢時對鏈表的訪問帶來的性能開銷.

3.5不同數(shù)據(jù)集對查詢性能的影響

本節(jié)的實驗主要探究服從不同分布的查詢數(shù)據(jù)集以及插入數(shù)據(jù)集的順序?qū)Cuckoo查詢性能的影響.當DCuckoo不允許盲踢時，待插入元素若不能找到合適的位置，則會被直接放入鏈表，因此后插入的元素更有可能被放入到鏈表中.當查詢數(shù)據(jù)集不是均勻分布時，插入的順序可能會對查詢性能產(chǎn)生影響，實驗結(jié)果如表2所示.其中順序插入(in order)指按查詢數(shù)據(jù)集元素出現(xiàn)頻數(shù)從高到低插入，逆序插入(reversed order)指按頻數(shù)從低到高插入，亂序插入(out-of-order)即插入順序與頻數(shù)無關.

Table 2 The Results with Different Dataset for DCuckoo表2 DCuckoo在不同數(shù)據(jù)集下的實驗結(jié)果

從表2可以看出，當不允許盲踢時，查詢性能受插入順序影響較大；而當允許盲踢6次時，平均查詢訪存則與插入順序無關，且都達到了理想的水平(約1次).這是由于一方面盲踢減少了在鏈表上的元素數(shù)目，另一方面后插入元素不再直接插入鏈表，即鏈表上的元素與插入順序無關.

這一實驗結(jié)果表明的另一個問題是，出現(xiàn)在鏈表中的高頻元素會影響查詢性能，因此進一步的優(yōu)化可犧牲一定的空間為元素標記“熱度”，定期將“熱度”較高的元素從鏈表中移出，以提高查詢性能.

4 結(jié)束語

本文結(jié)合了Cuckoo散列和d-left散列，提出了一種新的散列表DCuckoo，并在其上應用片內(nèi)摘要以優(yōu)化查詢插入性能.經(jīng)過一系列的實驗發(fā)現(xiàn)DCuckoo達到了設計目標，即高效更新、高效查詢、內(nèi)存冗余少、支持動態(tài)擴展，并優(yōu)于已有的散列表設計.

未來的工作我們希望能夠?qū)Cuckoo應用到實際的系統(tǒng)之中，如鍵值存儲系統(tǒng).盡管對鍵值存儲系統(tǒng)的研究已有很多，且也有基于CPU-GPU異構(gòu)平臺上的研究[8,20-22]，但這些研究都只對作為核心的散列表進行了很小的改動.因此，可以對現(xiàn)有鍵值存儲系統(tǒng)的散列表進行替換，以追求更高的空間利用率以及查詢性能.

[1]Broder A, Mitzenmacher M. Using multiple Hash functions to improve IP lookups[C]Proc of IEEE INFOCOM 2001. Piscataway, NJ: IEEE, 2001: 1454-1463

[2]Yang Tong, Xie Gaogang, Sun Xianda, et al. Towards practical use of Bloom filter based IP lookup in operational network[C]Proc of 2014 IEEE Network Operations and Management Symp (NOMS). Piscataway, NJ: IEEE, 2014: 1-4

[3]Yang Tong, Xie Gaogang, Li Yanbiao, et al. Guarantee IP lookup performance with FIB explosion[J]. ACM SIGCOMM Computer Communication Review, 2015, 44(4): 39-50

[4]Waldvogel M, Varghese G, Turner J, et al. Scalable High Speed IP Routing Lookups[M]. New York: ACM, 1997

[5]Adler M, Chakrabarti S, Mitzenmacher M, et al. Parallel randomized load balancing[C]Proc of the 27th Annual ACM Symp on Theory of Computing. New York: ACM, 1995: 238-247

[6]Mitzenmacher M. The power of two choices in randomized load balancing[J]. IEEE Trans on Parallel and Distributed Systems, 2001, 12(10): 1094-1104

[7]Mitchell C, Geng Yifeng, Li Jinyang. Using one-sided RDMA reads to build a fast, CPU-efficient key-value store[C]Proc of USENIX ATC’13. Berkeley, CA: USENIX Association, 2013: 103-114

[8]Zhang Kai, Wang Kaibo, Yuan Yuan, et al. Mega-KV: A case for GPUs to maximize the throughput of in-memory key-value stores[J]. Proceedings of the VLDB Endowment, 2015, 8(11): 1226-1237

[9]Pagh R, Rodler F F. Cuckoo hashing[C]Proc of the 9th European Symp on Algorithms. Berlin: Springer, 2001: 121-133

[10]V?cking B. How asymmetry helps load balancing[J]. Journal of the ACM, 2003, 50(4): 568-589

[11]Fredman M L, Komlós J, Szemerédi E. Storing a sparse table with 0 (1) worst case access time[J]. Journal of the ACM, 1984, 31(3): 538-544

[12]Kumar S, Crowley P. Segmented Hash: An efficient Hash table implementation for high performance networking subsystems[C]Proc of the 2005 ACM Symp on Architecture for Networking and Communications Systems. New York: ACM, 2005: 91-103

[13]Kumar S, Turner J, Crowley P. Peacock hashing: Deterministic and updatable hashing for high performance networking[C]Proc of IEEE INFOCOM 2008. Piscataway, NJ: IEEE, 2008: 101-105

[14]Song Haoyu, Dharmapurikar S, Turner J, et al. Fast Hash table lookup using extended Bloom filter: An aid to network processing[J]. ACM SIGCOMM Computer Communication Review, 2005, 35(4): 181-192

[15]Bloom B H. Spacetime trade-offs in Hash coding with allowable errors[J]. Communications of the ACM, 1970, 13(7): 422-426

[16]Yang Tong, Liu Alex Xiangyang, Shahzad M, et al. A shifting Bloom filter framework for set queries[J]. Proceedings of the VLDB Endowment, 2016, 9(5): 408-419

[17]Fan Li, Cao Pei, Almeida J, et al. Summary cache: A scalable wide-area Web cache sharing protocol[J]. IEEEACM Trans on Networking, 2000, 8(3): 281-293

[18]Atikoglu B, Xu Yuehai, Frachtenberg E, et al. Workload analysis of a large-scale key-value store[C]Proc of SIGMETRICS 2012. New York: ACM, 2012: 53-64

[19]Cooper B F, Silberstein A, Tam E, et al. Benchmarking cloud serving systems with YCSB[C]Proc of the 1st ACM Symp on Cloud Computing. New York: ACM, 2010: 143-154

[20]Deyannis D, Koromilas L, Vasiliadis G, et al. Flying memcache: Lessons learned from different acceleration strategies[C]Proc of Computer Architecture and High Performance Computing (SBAC-PAD). Piscataway, NJ: IEEE, 2014: 25-32

[21]Hetherington T H, Rogers T G, Hsu L, et al. Characterizing and evaluating a key-value store application on heterogeneous CPU-GPU systems[C]Proc of IEEE ISPASS 2012. Piscataway, NJ: IEEE, 2012: 88-98

[22]Hetherington T H, O’Connor M, Aamodt T M. MemcachedGPU: Scaling-up scale-out key-value stores[C]Proc of the 6th ACM Symp on Cloud Computing. New York: ACM, 2015: 43-57

JiangJie, born in 1994. Master candidate. Received his bachelor degree from Peking University in 2016. His main current research interests include Hash tables and KV stores.

YangTong, born in 1982. PhD. Research assistant at the School of Electronics Engineering and Computer Science, Peking University. Member of CCF. His main research interests include IP lookups, Bloom filters, sketches and KV stores.

ZhangMengyu, born in 1995. Master candidate. Received her bachelor degree from the University of International Business and Economics in 2017. Her main research interests include Hash tables.

DaiYafei, born in 1958. PhD. Professor at the School of Electronics Engineering and Computer Science, Peking University. Member of IEEE. Distinguished member of CCF. Her main research interests include networked and distributed systems, P2P computing, network storage, and online social networks.

ZhengLianqing, born in 1963. PhD. Professor at the Department of Control Engineering, Xijing University. His main research interests include computer application technologies.

DCuckoo:AnEfficientHashTablewithOn-ChipSummary

Jiang Jie1, Yang Tong1,2, Zhang Mengyu1, Dai Yafei1, Huang Liang3, and Zheng Lianqing4

1(School of Electronics Engineering and Computer Science, Peking University, Beijing 100871)2(Collaborative Innovation Center of High Performance Computing, National University of Defense Technology, Changsha 410073)3(Military 9478265, Hangzhou 310021)4(Department of Control Engineering, Xijing University, Xi’an 710123)

Hash tables are extensively used in many computer-related areas because of their efficiency in query and insertion operations. However, Hash tables have two disadvantages: collisions and memory inefficiency. To solve these two disadvantages, minimal perfect Hash table usesNlocations to storeNincoming elements. However, MPHT doesn’t support incremental updates. Therefore, in this paper, combining Cuckoo hashing and d-left hashing, we propose a novel Hash table architecture called DCuckoo, which ensures fast query speed, fast update speed in worst cases, efficient utilization of memory and dynamic capacity change. In DCuckoo, multiple sub-tables and Cuckoo hashing’s mechanism of transferring existing elements are used to improve the load factor. Pointers except for ones in the last sub-table are eliminated for less wasted space. Also, in order to optimize the query performance, fingerprints and bitmaps are used as a summary in on-chip memory to reduce off-chip memory accesses. The bucket will be probed only if the corresponding fingerprint is matched in on-chip memory. We conduct a series of experiments to compare the performance of DCuckoo and other five Hash table schemas. Results demonstrate that DCuckoo eliminates shortcomings of both Cuckoo hashing and d-left hashing, hence DCuckoo achieves the four design goals.

Hash table; lookup; fingerprint; on-chip memory; key-value store

his master degree from Information Science and Electronic Engineering Department of Zhejiang University in 2011. His main research interests include computer networks.

2016-11-02；

2017-02-21

國家自然科學基金項目(61232004, 61672061)；國家quot;九七三quot;重點基礎研究發(fā)展計劃基金項目(2014CB340400)；國家重點研發(fā)計劃項目(2016YFB1000300)；中國科學院先導科技專項課題(XDA06040602)

This work was supported by the National Natural Science Foundation of China (61232004, 61672061), the National Basic Research Program of China (973 Program) (2014CB340400), the National Key Research and Development Program of China (2016YFB1000300), and the Strategy Leading Science and Technology Projects of Chinese Academy of Sciences (XDA06040602).

楊仝(yang.tong@pku.edu.cn)

TP391