並發數據結構-1.6 哈希錶

杜老師說 2022-01-07 12:38:25 阅读数:462

哈希

原文鏈接譯文鏈接,譯者:iDestiny,校對:周可人

典型可擴展的哈希錶即一個可調整大小的桶數組(buckets), 每一個桶存放預期數量的元素,因此哈希錶平均在常量時間內進行插入,删除,查詢操作。哈希錶調整大小的主要成本—–在於新舊桶(buckets)之間進行重新分配操作,該操作被分攤到所有錶操作上,所以平均操作時間也是常量的。哈希錶調整大小就是擴容,在實踐中,哈希錶僅需要增加數組大小即可。

Michael實現了一個可並發,不可擴展的哈希錶(通過對哈希錶中每個桶進行讀寫鎖約束)。然而,為了保證元素數量增長時的性能,哈希錶必須可擴展。

在80年代,Ellis和其他人基於二級鎖機制,為分布式數據庫設計了一個可擴展且並發的哈希錶。Lea的可擴展的hash算法在非並發環境下錶現出了高性能,該算法是基於Litwin的線性序列hash算法,它用了不同的加鎖方案:用少量的獨占鎖代替原本對每一個桶都加鎖,並且當調整哈希錶大小時,允許並發查詢操作,但不能並發插入或删除。當哈希錶大小需要擴展為2倍時,調整大小錶現為對所有內部桶(buckets)進行重構。

正如之前討論的,基於鎖的可擴展的哈希錶算法同樣具有阻塞同步所帶來的典型的缺點。這些問題會由於對哈希錶所有新添加桶(buckets)進行重分配變得更嚴重。因此無鎖可擴展的哈希錶是一個既實際又理論的問題。

如1.5節描述的,Michael在Harries工作之上,提供了一個有效的,基於CAS,無鎖的鏈錶實現。然後將此原理運用到並發環境下性能不錯的無鎖的hash結構中:一個固定大小的hash桶數組,每個桶由無鎖鏈錶實現。但是,要使一個無鎖的鏈錶數組可擴展很困難,因為當桶(buckets)數組擴展時,要在無鎖方式下重新分配元素不是很容易的。在兩個不同桶鏈錶之間移動元素需要兩個CAS操作同時原子地完成,這點在目前的體系結構中是不可能做到的。

Greenwald展示了怎麼用他的雙手模擬技術(two-handed emulation)來實現一個可擴展的哈希錶。然而,這種技術使用了DCAS同步操作,該操作在當今的架構中不可用,並且在全局調整大小時會帶來過多的工作。

Shalev和Shavit在當今架構下提出了一種無鎖可擴展的哈希錶。他們的核心思想在於將元素放在單個無鎖鏈錶中,而不是每個桶(bucket)中的鏈錶。為了讓操作能够快速訪問鏈錶, Shalev-Shavit算法維護了一個可調整大小的hints數組(指向鏈錶的指針),相關操作通過hints數組中的指針找到接近相關元素的比特置,然後順著該指針找到元素比特置。為了保證每個操作平均能在常量步驟內完成,當鏈錶中的元素個數增長時,細粒度的hints數組必須要添加。為了使hints數組能簡單有效地被裝配,鏈錶由一個遞歸分割順序來維護。該技術使得新的hints能够增量裝配,從而消除了原子地在桶(bucket)之間移動元素或重新排序列錶帶來地複雜性需求。

原創文章,轉載請注明: 轉載自並發編程網 – ifeve.com本文鏈接地址: 並發數據結構-1.6 哈希錶

FavoriteLoading添加本文到我的收藏
版权声明:本文为[杜老師說]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201071238248370.html