基于低沖突幫助機制的快速無等待哈希表算法

李鵬飛，張坤龍，康超凡

（天津大學計算機科學與技術學院，天津300072）

基于低沖突幫助機制的快速無等待哈希表算法

李鵬飛，張坤龍，康超凡

（天津大學計算機科學與技術學院，天津300072）

針對現(xiàn)有無等待哈希表算法未充分利用哈希表的固有并行性，造成線程之間存在高沖突和高冗余的問題，提出一種快速無等待哈希表算法。利用可凍結集合思想簡化哈希表操作，采用CAS原子指令保證插入、刪除與查找操作均為無等待。根據哈希表結構改進幫助機制，使得哈希桶的實現(xiàn)為無等待，只有在擴展哈希表時哈希桶之間才提供幫助。實驗結果表明，該算法能降低線程操作間的沖突，提高幫助操作的并行度，當查找率為0、鍵值范圍為0～256且線程數為8時，其吞吐率是現(xiàn)有無等待哈希表算法的2.5倍。

并發(fā)數據結構；哈希表；無等待；可線性化；可擴展

1 概述

在各種并發(fā)數據結構中，哈希表因能夠在常數時間內完成操作而得到應用廣泛。哈希表按照存儲結構可分為封閉地址（closed address）哈希表和開放地址（open address）哈希表。前者元素存儲在稱為桶（bucket）的結構中，桶中可存放多個元素；后者元素存儲在槽（slot）中，一個槽只能存放一個元素。哈希表通過散列函數將操作分散到不同的桶或槽，這使得彼此間的操作沒有沖突，這就是固有并行性。如果哈希表能動態(tài)地擴張和收縮，則具有可擴展性。

2014年，Liu Yujie等人提出了動態(tài)可擴展的非阻塞封閉地址哈希表算法［1］，包括無鎖（lock-free）哈希表算法和無等待（wait-free）哈希表算法。無鎖和無等待［2］都具有非阻塞特性：一個線程的延遲不會影響其他線程的操作。其中無等待的演進性最強，它保證即使在其他線程干擾的情況下，每個線程都能在有限步內完成。

研究發(fā)現(xiàn)，雖然文獻［1］中的無等待哈希表算法是目前性能最好的算法，但其性能卻受到抑制。原因是該算法存在過多不必要的幫助，而且利用全局計數器來協(xié)調幫助造成了高爭用。為了提升性能，文獻［1］采用快路徑慢路徑（Fastpath/Slow path）機制［3］。其核心思想是盡可能地運行在無鎖階段（快路徑），無等待階段（慢路徑）只是用來保證無等待特性，以此提升性能。然而，這種提升方法并沒有從根本上解決無等待算法的性能瓶頸問題。為此，本文提出一種新的無等待哈希表算法，該算法要求哈希桶的實現(xiàn)是無等待的，并且只在哈希表調整時才提供幫助，從而充分利用哈希表的固有并行性。

2 相關工作

哈希表一直是熱門的研究課題。在順序數據結構中，哈希表算法層出不窮。然而，在共享數據結構中，并發(fā)環(huán)境下，非阻塞的哈希表算法仍是屈指可數。

文獻［4］提出無鎖封閉地址哈希表算法。該算法使用改進的Harris無鎖鏈表［5］作為桶，通過散列函數將操作映射到相應桶上進行。算法能和內存管理方法相適應。然而，該算法不是可擴展的。

文獻［6］提出動態(tài)可擴展的無鎖封閉地址哈希表算法。但是該算法基于DCAS（Double Compare and Sw ap）原子指令［7］，DCAS在目前硬件結構中還不支持，而且軟件模擬開銷太大。

文獻［8］提出動態(tài)可擴展的無鎖開放地址哈希表算法。該算法在調整時有2個表：當前的舊哈希表和擴展后的新哈希表。在功能調整過程中，先標記舊哈希表中的數據元素，然后將標記的元素拷貝到新哈希表中，最后將完成拷貝的舊哈希表元素設置為特殊值，表示已被遷移。哈希表的操作在當前的舊哈希表上進行，一旦發(fā)現(xiàn)被標記的數據元素，就參與調整操作。調整結束后，新的哈希表成為當前的舊哈希表。該算法是真正意義上的可擴展哈希，可是該文中并沒有給出算法的性能信息。

文獻［9］提出無鎖開放地址哈希表算法。該算法不具有可擴展性，但是可以重復利用元素刪除后的空間，是空間有效的。

文獻［10］提出遞歸有序劃分可擴展哈希表算法，該算法的擴展方式為：不在桶內插入元素，而是在元素間插入桶。算法基于一個無鎖的有序鏈表［5］和一個目錄結構。鏈表中的元素分為數據元素和索引元素，這兩者之間用最高位區(qū)分。元素按照它們的二進制比特位反轉后排序，這樣索引元素就實現(xiàn)了數據元素的有序劃分。算法先在目錄結構上找到相應的桶（沒有則建立），然后通過桶找索引元素，若該索引元素的父索引還沒建立，就遞歸建立。但是該算法并沒有提供收縮的特性，而且索引元素一經建立就永不刪除，并且算法還對內存的大小做了假設。

文獻［11］采用完美哈希（perfect hash）的思想構造無等待可擴展哈希映射算法，能輕易實現(xiàn)哈希表。該算法使用一個桶數組，結構類似樹：每個桶要么是一個數據項（葉子結點），要么指向一個數組（中間結點）。然而，算法實現(xiàn)的哈希表大小有上限，不是嚴格意義上可擴展的。

文獻［12］提出無鎖布谷哈希算法。布谷哈希（cuckoo hash）是開放地址哈希算法，使用2個獨立的哈希表，每個哈希表有不同的散列函數。布谷哈希處理沖突時將某個表里存在的元素剔除，將新元素放入，而后將剔除的元素在另一個表上做類似操作，重復這個過程直到找到空槽將元素放入。無鎖布谷哈希算法使用邏輯時鐘策略解決查找丟失問題。插入操作使用幫助機制，保證了非阻塞特性。然而，該算法沒有提供可擴展的功能，而且在最壞情況下，查找操作并不能在常數時間內完成。

動態(tài)可擴展的非阻塞封閉地址哈希表算法［1］的實現(xiàn)建立在抽象的可凍結集合上?？蓛鼋Y集合提供凍結操作，集合在凍結之后，任何更新操作將會失敗?？蓛鼋Y集合可以由當前最新的無序鏈表實現(xiàn)［13］，也可以使用數組實現(xiàn)，以提高緩存特性。該算法有新表和舊表2個操作位置，2個表中的桶都由可凍結集合實現(xiàn)。在哈希表調整時，凍結舊表中的相應桶，使用寫時復制（copy on w rite）機制，將桶中元素遷移至新表中的桶。元素遷移完后，新建一個空表，根據調整是擴張還是收縮設定空表的大小，然后將舊表置為空。此時新表成為“舊”表，新建的空表成為“新”表。算法通過哈希表在調整時維護新表和舊表的不變式關系，保證了操作的正確性。

3 算法設計

3.1 基本設計思想

無等待算法被認為是低效和難以實現(xiàn)的［14］，其很大原因在于幫助機制的設計［15］。大多數幫助機制存在兩大缺陷：高沖突和高冗余［3］。在執(zhí)行自己的操作之前，先幫助其他的線程，通常造成線程之間的高沖突。其實在大多數情況下，如果給定足夠的時間，一個線程能自己完成操作。幫助機制必須設計成操作順序一致，即并發(fā)幫助某個操作的線程執(zhí)行過程是一樣的，而該操作只能被正確的執(zhí)行一次，這樣就造成了高冗余。

文獻［1］中的無等待算法使用一個全局共享的幫助數組，通過優(yōu)先級決定幫助的次序，從而保證無等待特性。每個線程在完成自己的操作之前先掃描幫助數組，幫助完成優(yōu)先級比自己高的操作。這種幫助機制沒有考慮到封閉地址哈希表這種特殊的數據結構：哈希表具有雙重結構，包括哈?？蚣芎痛娣艛祿氐耐?。使用這種幫助機制，本來映射到不同桶上毫不相干的2個操作因為優(yōu)先級的原因而不得不建立聯(lián)系，沒有充分利用哈希表的固有并行性，造成線程之間的高沖突和高冗余。

本文采用文獻［1］的可凍結集合思想，使用CAS（Com pare and Sw ap）原子指令來實現(xiàn)無等待特性。為了更充分地利用哈希表的固有并行性，算法重新設計了幫助機制，具體表現(xiàn)在以下2個方面：（1）算法要求桶的實現(xiàn)必須是無等待的。然而與此不同的是文獻［1］中桶的實現(xiàn)只要求無阻塞，一些快速的無鎖鏈表算法，比如無鎖鏈表算法［5］、LFList鏈表算法［13］與自組織鏈表算法［16］等均能夠適用。（2）只有在哈希表進行調整時，哈希表上才提供幫助，而且只有調整線程才能幫助其他未完成操作的線程。這樣在不同桶上做操作的線程之間不會相互干擾，降低了沖突，而只在必要時才提供幫助的策略提升了操作的并行度。

3.2 算法描述

3.2.1 集合中使用的結構

集合中使用的結構具體如下：

3.2.2 哈希表中使用的結構

哈希表中使用的結構具體如下：

3.3 算法分析

在文獻［1］的基礎上，可凍結集合算法中，record FSet增加了共享數組B，用于同一桶內的線程間相互幫助。函數Invoke是提供給上層的接口，插入和刪除操作在FSet上通過調用Invoke而發(fā)生作用，更新集合（L50～L51，L50表示算法中代碼的第50行，下同），然后通過GetResponse獲取操作結果。查找操作通過調用HasM ember獲得查找結果。只有當FSet中的元素需要遷移時才會調用Freeze。Freeze操作首先將可凍結標記置為true，隨后調用DoFreeze凍結集合。Invoke中發(fā)現(xiàn)可凍結標記改變（L6），也幫助做凍結操作（L7）。

在哈希表算法中，插入和刪除操作通過調用Apply獲得相應的桶，若桶為空，則先進行收集（L90）。Apply調用期間，除了在同一個桶上調用Invoke而幫助相關線程之外，未做其他不相干的操作，提高了并行度。如果達到某種條件（L54，L59），則調用Resize對哈希表作調整（L55，L60）。Resize操作首先調用InitBucket對當前表（新表）做收集，將舊表中的元素遷移到新表中空的桶中（L97）。然后將指向舊表的指針置為空（L78），此時元素已全部遷移完成。最后新建一個空表，表的大小根據調整類型選擇（L79），通過CAS原子操作使其成為新表（L82），收集后的表相應地成為舊表。

如果給定足夠的時間，一個線程可能已經完成而并不需要其他線程的幫助：只有在必要時提供幫助才是合理的?；诖耍碌臒o等待哈希表算法增加了函數HelpWhenResize（L108～L114），這是整個算法的關鍵。文獻［1］中的算法不論操作是否在同一個桶上，只要優(yōu)先級高于自己，就無條件幫助完成，很多時候這種幫助是不必要的。這樣做的原因是為了保證無等待特性：防止其他線程在不斷地調整而導致自己的操作始終不能完成的情況發(fā)生。函數HelpWhen Resize掃描哈希表的共享數組A中發(fā)布的操作（L109～L110），如果操作沒完成（L111）且在當前桶上操作（L113），則在桶上幫助完成（L114）。函數HelpWhenResize只在調整時被調用（L77），不會出現(xiàn)線程由于調整干擾而不能完成的情形。

4 正確性證明

在并發(fā)環(huán)境下，正確性既包含了安全性（safety），也包含了活性（liveness）。所謂安全性，是指該數據結構實現(xiàn)了一個抽象數據結構，例如集合，并且實現(xiàn)是可線性化的（linearizable）［17］。并發(fā)系統(tǒng)的一次執(zhí)行過程可以采用經歷（history）模型來描述。經歷是方法調用事件和響應事件的一個有限序列?？删€性化隱含的基本思想是每個并發(fā)經歷都等價于某個順序經歷，這樣就將并發(fā)過程映射為順序過程。所謂活性，也叫演進性，在使用鎖的結構上指的是無死鎖，無饑餓；在不使用鎖的結構上指的是非阻塞特性。本文將從可線性化性和無等待特性2個方面進行證明。

4.1 可線性化特性

定義 集合中的元素來自哈希表新表、舊表中的元素，從哈希表元素到集合元素的映射關系定義如下：

（1）若新表中的桶b不為空，則桶b中元素屬于集合。

（2）若新表中的桶b為空，且新表的大小是舊表的2倍，則舊表中滿足L99～L100的桶中元素屬于集合。

（3）若新表中的桶b為空，且舊表的大小是新表的2倍，則舊表中滿足L102～L104的2個桶中元素屬于集合。

引理1 插入或刪除操作的可線性化的點在Invoke返回true時刻，即操作完成時刻L49。

引理2 查找操作的可線性化的點：若桶不是凍結的，則取在HasM ember（L71）上；否則，桶一定被某個Freeze操作凍結，可線性化的點取Freeze將凍結標記fflag設置為true（L19）或獲取哈希表新表（L63）這2個操作中發(fā)生較晚的一個。

定理1 哈希表實現(xiàn)的抽象數據結構是集合。

證明：由引理1可知，在可線性化點對桶（FSet）進行插入操作：要么桶里沒有插入操作的元素（L43結果為true），于是桶里增加了一個元素（L44）；要么L43結果為false，桶與先前一樣。在可線性化點對桶進行刪除操作：要么桶里沒有刪除操作的元素（L47結果為false），桶與先前一樣；要么L47結果為true，于是桶里減少了一個元素（L47）。對于查找操作，由引理2可知，在調用HasM ember（b，k）返回操作結果時，對于操作的桶b（一定不為空），可能出現(xiàn)以下情況：（1）桶b沒有被凍結，則桶b所在的表要么是新表，要么是舊表且新表的相應桶為空；由定義可知，相關元素在桶b中。（2）桶b被凍結，則桶b所在的表一定是舊表或已過時（既不是新表，又不是舊表）。若桶被凍結在執(zhí)行L63之前，則執(zhí)行L63時，將從L66獲得桶b，由定義可知，相關元素在桶b中。若桶被凍結在執(zhí)行L63之后，則直到桶b被凍結的時刻，桶b在舊表中且新表的相應桶為空，由定義可知，相關元素在桶b中。

4.2 無等待特性

引理3 一旦FSet的凍結標記fflag設置為true，則經過有限的操作步，F(xiàn)Set將被凍結（即執(zhí)行L33成功）。

引理4 成為FSet的操作節(jié)點（執(zhí)行L12成功）的更新操作節(jié)點，在有限步內不是自己完成就是別人幫助完成。

定理2 集合算法是無等待的。

證明：觀察3.2節(jié)中的集合算法，發(fā)現(xiàn)只有函數DoFreeze與函數Invoke中有while循環(huán)。只有將凍結標記置為true才會調用函數DoFreeze，根據引理3，函數DoFreeze將在有限步內完成。函數Invoke中退出循環(huán)的條件是當前操作完成或該集合被凍結（L5）。若集合沒被凍結，當前操作執(zhí)行L12不能成功的原因是其他線程不斷地干擾。假設線程總數為P，因為有幫助數組B，線程調用Invoke都會掃描一遍數組（L3），操作完成的線程再次運行時一定會發(fā)現(xiàn)這個未完成的操作，則最多經過P次操作完成，未完成的操作一定成為FSet的操作節(jié)點，由引理4可知，當前操作能在有限步內完成。若集合被凍結，則直接退出循環(huán)。

定理3 哈希表算法是無等待的。

證明：觀察3.2節(jié)中的哈希表算法，發(fā)現(xiàn)只有函數Apply中有while循環(huán)。函數Apply不能結束的原因是操作始終沒有完成。若哈希表沒有發(fā)生調整，則每次調用函數Invoke將作用在同一個桶上，由定理2可知，函數Apply將在有限步內完成。若哈希表發(fā)生調整，函數HelpW henResize將掃描整個幫助數組（L109），調整線程將幫助未完成的操作。

5 實驗與結果分析

實驗在4核8線程（3.5 GHz，一級緩存64 KB，二級緩存256 KB）64 bit英特爾i7-4770K機器上進行，算法全都用Java實現(xiàn)。實驗環(huán)境：Linux操作系統(tǒng)CentOS release 6.5，Java版本1.7.0-60。

實驗的4個算法均是無等待的。其中，WFList是文獻［1］中的算法，用文獻［13］中的無鎖無序鏈表實現(xiàn)桶；FastWFList是本文提出的算法，用文獻［13］中的無等待無序鏈表實現(xiàn)桶；WFArray是文獻［1］中算法的數組實現(xiàn)；FastWFA rray是本文算法的數組實現(xiàn)。

實驗以吞吐率作為性能指標，為了避免調整操作對算法性能的影響，插入與刪除操作的比率相同。操作數據在鍵值范圍內隨機生成。初始時哈希表中預先插入個數為鍵值范圍一半的數據。實驗參數如下：（1）函數contains，insert，remove的調用百分比有2種情況：1）0，50%，50%；2）80%，10%，10%。根據函數調用比例，線程隨機地選擇操作類型，主要考察沖突、爭用的高低對算法性能的影響。（2）線程數目為1～8。（3）鍵值范圍為0～256，0～65 536。主要考察鍵值范圍大小對算法性能的影響。以上共4組實驗，每組實驗運行5次，每次運行5 s，最終結果取平均值。實驗數據的標準偏差可忽略。實驗結果見圖1～圖4。

圖1 查找率為0、鍵值范圍為0～256時的算法吞吐率

圖2 查找率為0、鍵值范圍為0～65 536時的算法吞吐率

圖3 查找率為80%、鍵值范圍為0～256時的算法吞吐率

圖4 查找率為80%、鍵值范圍為0～65 536時的算法吞吐率

從圖1～圖4可以看出，本文算法的性能優(yōu)于文獻［1］算法，無論是鏈表實現(xiàn)還是數組實現(xiàn)。在相同的鍵值范圍，查找率大的吞吐率較高。原因是查找并不改變集合元素，沒有線程間的相互干擾，而且查找也不需要幫助，在相同時間內所做的操作更多。查找率為0時，各線程之間的競爭激烈。在圖1中，隨著線程數的增加，新算法的性能與文獻［1］算法的性能差距越來越大，在線程數為8時吞吐率是其2.5倍。查找率為80%時，插入操作與刪除操作發(fā)生沖突的概率較低，本文算法利用固有并行的優(yōu)勢減弱，提升的幅度降低。

在圖2中，當線程數大于4時，本文算法的性能曲線趨于平緩，原因值得進一步研究。在小鍵值時，桶用數組實現(xiàn)的一類算法性能優(yōu)于桶用鏈表實現(xiàn)的一類算法，而在大鍵值時情況正相反，可能是數組利用的緩存效應在大鍵值時優(yōu)勢不明顯。

6 結束語

本文分析了無等待哈希表算法性能差的原因，根據哈希表的結構改進幫助機制，提出一種快速無等待哈希表算法，能更充分地利用哈希表的固有并行性。實驗結果表明，該算法提高了無等待哈希表算法的性能下界，最好時是已知最快算法的2.5倍。下一步工作是分析大鍵值范圍下本文算法性能趨于平緩的原因，以及在實際應用中使用并發(fā)數據結構，并結合多核并行運算的優(yōu)勢，進一步提高吞吐性能。

［1］ Liu Yujie，Zhang Kunlong，Spear M.Dynamic-sized Nonblocking Hash Tables［C］//Proceedings of 2014 ACM Symposium on Principles of Distributed Computing.Paris，F(xiàn)rance：ACM Press，2014：242-251.

［2］ Herlihy M.Wait-free Synchronization［J］.ACM Transactions on Programming Languages and Systems，1991，13（1）：124-149.

［3］ Kogan A，Petrank E.A Methodology for Creating Fast Wait-free Data Structures［C］//Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming.New York，USA：ACM Press，2012：141-150.

［4］ M ichael M M.High Performance Dynamic Lock-free Hash Tables and List-based Sets［C］//Proceedings of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures.New York，USA：ACM Press，2002：73-82.

［5］ Harris T L.A Pragmatic Implementation of Non-blocking Linked-lists［C］//Proceedings of the 15th International Conference on Distributed Computing.Berlin，Germany：Springer，2001：300-314.

［6］ Greenwald M.Two-handed Emulation：How to Build Nonblocking Implementations of Complex Data-structures Using DCAS［C］//Proceedings of the 21st Annual Symposium on Principles of Distributed Computing.New York， USA：ACM Press，2002：260-269.

［7］ Luchangco V，Moir M，Shavit N.Nonblocking k-comparesingle-swap［C］//Proceedings of the 15th Annual ACM Symposium on Parallel Algorithms and Architectures. New York，USA：ACM Press，2003：314-323.

［8］ Gao Hui，Groote J F，Hesselink W H.Lock-free Dynamic Hash Tables w ith Open Addressing［J］. Distributed Computing，2005，18（1）：21-42.

［9］ Purcell C，Harris T.Non-blocking Hashtables with Open Addressing［C］//Proceedings of the 19th International Conference on Distributed Computing.Berlin，Germany：Springer，2005：108-121.

［10］ Shalev O，Shavit N.Split-ordered Lists：Lock-free Extensible Hash Tables［J］.Journal of the ACM，2006，53（3）：379-405.

［11］ Feldman S，Laborde P，Dechev D.Concurrent Multilevel Arrays：Wait-free Extensible Hash Maps［C］// Proceedings of International Conference on Embedded Computing System s：Architectures，Modeling，and Simulation.Washington D.C.，USA：IEEE Press，2013：155-163.

［12］ Nguyen D N，Tsigas P.Lock-free Cuckoo Hashing［C］// Proceedings of the 34th International Conference on Distributed Computing Systems.Washington D.C.，USA：IEEE Computer Society，2014：627-636.

［13］ Zhang Kunlong，Zhao Yujiao，Yang Yajun，et al.Practical Non-blocking Unordered Lists［C］//Proceedings of the 27th International Conference on Distributed Computing. Berlin，Germany：Springer，2013：239-253.

［14］ Herlihy M，Shavit N.多處理器編程的藝術［M］.金 海，胡 侃，譯.北京：機械工業(yè)出版社，2009.

［15］ Herlihy M，Luchangco V，Moir M.Obstruction-free Synchronization：Double-ended Queues as an Example［C］// Proceedings of the 23rd International Conference on Distributed Computing Systems.Washington D.C.，USA：IEEE Computer Society，2003：522-529.

［16］ 陳春光，張坤龍，譚龍飛，等.并發(fā)非阻塞自組織鏈表算法［J］.計算機工程，2013，39（8）：31-37.

［17］ Herlihy M P，W ing J M.Linearizability：A Correctness Condition for Concurrent Objects［J］.ACM Transactions on Programming Languages and System s，1990，12（3）：463-492.

編輯 陸燕菲

Fast Wait-free Hash Table Algorithm Based on Low-conflict Help Mechanism

LI Pengfei，ZHANG Kunlong，KANG Chaofan
（School of Computing Science and Technology，Tianjin University，Tianjin 300072，China）

Existing wait-free hash table algorithms do not take full advantage of the inherent parallelism of hash table，which results in the high redundancy and conflict between threads.In order to solve the problem，this paper proposes a fast wait-free hash table algorithm.It makes use of the freezable set to simplify the operations of hash table.And the Com pare and Swap（CAS）primitive is applied to realize the wait-free of insertion，deletion and search operations.It improves the help mechanism based on the structure of hash table to realize the wait-free of hash buckets.In order to avoid the conflics between the operations on different buckets，the help is given only when the hash table extends.Experimental results show that the algorithm can reduce the conflict between thread operation，and improve the parallelism of help operation.W hen the percentage of lookup is 0，the data range is 0～256 and the thread number reaches 8，throughput of the proposed algorithm is 2.5 times than the existing wait-free hash table algorithm.

concurrent data structure；hash table；wait-free；linearizability；extensibility

李鵬飛，張坤龍，康超凡.基于低沖突幫助機制的快速無等待哈希表算法［J］.計算機工程，2015，41（11）：52-58.

英文引用格式：Li Pengfei，Zhang Kunlong，Kang Chaofan.Fast Wait-free Hash Table Algorithm Based on Low-conflict Help Mechanism［J］.Computing Engineering，2015，41（11）：52-58.

1000-3428（2015）11-0052-07

A

TP311.1

10.3969/j.issn.1000-3428.2015.11.010

國家自然科學基金資助項目（61303021）；水利部公益性行業(yè)科研專項基金資助項目（201401033）。

李鵬飛（1990-），男，碩士研究生，主研方向：并發(fā)數據結構，數據庫技術；張坤龍，副教授、博士；康超凡，碩士研究生。

2014-10-05

2014-12-15 E-m ail：lpf2013@tju.edu.cn