並發數據結構-1.7 查找樹

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

查找

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

任何查找樹的並發實現都可以通過用一個獨占鎖保護來完成。通過使用讀寫鎖對並發性能有一定提昇,讀寫鎖允許所有只讀(查找)操作並發地執行,因為讀操作是以共享模式持有鎖,然而更新(插入或删除)操作持有獨占模式的鎖,從而排斥其他所有操作。如果更新操作比較少,這還能接受,但是只要有適量的更新操作,那麼更新操作所持有的獨占鎖將產生線性的瓶頸,從而大大降低性能。通過使用細粒度的鎖策略——比如每個節點一個鎖,而不是整棵樹使用同一個鎖——這樣我們進一步地提昇了並發性能。

Kung和Lehman介紹了一種並發二分查找樹的實現:更新操作每次只擁有固定數量的節點鎖,並且這些鎖只排斥其他的更新操作,查詢操作從不會被阻塞。但是這種實現並沒有試圖保持查找樹平衡。在本節的其他部分,我們會關注平衡的查找樹,這將更具有挑戰性。

作為邁向實現更細粒度的同步平衡查找樹的第一步,我們可以注意到,讓一個引起任何修改的操作持有子樹的獨占鎖是可行的。這樣一來,修改操作可以並行地在不相交的子樹上被執行。在B+樹的背景下,我們簡要描述一些技術。回想B+樹,所有的關鍵字和數據被存儲在葉子節點;內部節點只維護路由信息,從而將更新操作引導至對應的葉子節點,而且,插入到葉子可能需要拆分葉子,反過來一個新的條目需要被添加到葉子節點的父親節點中,它(父親節點)自己可能也需要被拆分來適應新的條目。因此,一個插入操作可能導致修改從根到葉子的所有節點。然而這種行為是很少見的,所以使用完全獨占鎖住整個路徑來防止這種情况,是沒有意義的。

作為避免那種傳統的鎖策略的第一步,我們可以注意到,如果一個插入操作經過了一個不完全的內部B+樹節點,然後修改它,那麼其後的調整超越將不會越過這個節點(譯者注:即不會調整這個節點之上的節點)。在這種情况下,我們就說該節點的插入操作是安全的。當一個更新操作在樹中自上而下遍曆每個節點並鎖住每一個遍曆過的節點時遇到一個安全節點,它能够安全地釋放所有該節點的祖先上的鎖,因此,通過允許其他操作遍曆那些節點來提高了並發性。由於查找操作不會修改樹,能够沿著樹向下用lock coupling的策略(交接鎖),只要在子節點的鎖已經被獲取到,在其父親上的鎖就能够被釋放。因此,查找操作在任何時候最多持有2個鎖(共享模式下), 因而很少阻礙其他操作的執行。

這種方式仍然要求每個更新操作要獲取根節點的獨占鎖,且在讀取子節點時要持有鎖,子節點可能從磁盤讀取,所以根仍然是一個瓶頸。通過注意到大多數更新操作不將需要拆分或合並他們訪問過的節點,因此最終將釋放到葉子節點路徑上遍曆的所有節點上的獨占鎖。這個現象啟示了一個“樂觀的”方法,我們可以在共享模式下沿著樹向下獲取到那些鎖,僅獨占葉子節點鎖。如果葉子節點沒有必要拆分或合並,更新操作可以立即完成;在很少情况下,調整需要沿著樹向上傳播,我們可以釋放所有的鎖,然後重新嘗試上面描述的更悲觀的做法。作為其中一種選擇,我們可以用讀寫鎖來允許共享模式持有的鎖被”昇級”到獨占模式。這種方式,如果更新操作發現確實需要修改葉子節點以外的節點,它就可以將共享模式占有的鎖昇級為獨占模式,並且避免完全從樹根重新開始操作。上面的技術的各種組合都是可用的,因為樹根附近的節點更有可能和其他操作產生但更少可能被修改,而葉子附近的節點則相反。

當我們使用上面描述的更複雜的技術時,算法也會變得更複雜,並且很難避免死鎖,導致進一步複雜化。雖然如此,所有這些技術保持了操作獨占鎖他們修改的子樹的不變性,所以操作不會碰到他們在順序執行中沒有碰到的狀態。通過放寬這一要求,並發性和性能會得到顯著改善,代價是使得推論算法正確性會更困難。

當我們嘗試放寬嚴格的子樹鎖定方案時,我們遇到的關鍵難點是當一個操作跟隨指向子節點的指針沿著樹向下,該子節點由於並發操作的修改不再是正確子節點了。很多現在的技術已經允許操作從這種”混亂”中恢複,而不是完全避免它。

在B+樹背景下的一個重要的例子是Lehman和Yao,他們定義了B(link)樹::即B+樹中每個節點都帶有指向同一級別上的右鄰居的鏈接。這些鏈接讓我們將對一個節點的分裂和對其父親節點做調整來分裂分離開來。具體的,為了拆分一個節點n,我們可以創建一個新的節點n’到它的右邊,並且加上一個n到n’的鏈接。如果一個操作由於查找關鍵字比特置,沿著樹向下到達節點n,現在關鍵字比特置由於拆分而被節點n’覆蓋,操作可以簡單地從n到n‘的鏈接中恢複。這允許一個節點被拆分時,不會阻止並發操作訪問節點的父親節點。因此,更新操作不必在修改時鎖住整個子樹。實際上,在Lehman-Yao算法中,更新操作和查找操作使用交接鎖技術以便於沒有操作可以一次持有2個以上的鎖,這極大提高了並發性。該技術已經被進一步提煉,以至沒有操作可以一次可以持有1個以上的鎖。

Lehman和Yao沒有解决如何合並節點,而是允許删除操作時節點數未滿(譯者注:在傳統的B+樹中,删除操作需要合並條目數未達到要求的節點)。他們提出在多數情况下删除操作很少見,並且如果空間利用率成為問題,樹可以偶爾在“批處理”模式下,通過獨占鎖鎖住整個樹而被重組。Lanin和Shasha將合並操作並入删除操作,類似於之前實現中,插入操作拆分溢出的節點的方式。類似於Lehman-Yao的鏈接技術,這些實現用鏈接讓由於節點合並而到達一個空節點的錯誤操作得以恢複。

在所有上面討論的算法中,維護操作如節點拆分和合並都作為執行常規更新操作的一部分。沒有維護操作和常規操作之間的緊耦合,我們就不能保證嚴格的平衡屬性。然而,如果我們放寬平衡需求,我們可以將樹的維護操作從更新操作中分離出來,這樣帶來很多優勢,比需要保持查找樹嚴格平衡更有價值。比如說,B-link樹在實現壓縮過程中和常規操作並發執行來合並不足的節點。通過從常規操作中分離這些工作,它可以在不同處理器或在後臺的線程並發執行。

從常規的樹操作中分離再平衡的想法首先被建議使用在紅黑樹上,並且首先在AVL樹中實現來支持插入和查詢操作。這些實現通過將平衡分解得更小,局部的樹調整可以獨立完成來改善並發性。分析錶明通過做一些調整,該方案保證對於一棵N個節點的樹,每一個更新操作最多引起O(llogN)次再平衡操作。類似的結論對於B-trees和紅黑樹也是這樣。

唯一的非阻塞的平衡查找樹實現已經用動態軟件事務內存機制完成(譯者注:最近有了新的實現技術,見PODC2014和PPOPP2014)。這些實現使用那些將平衡操作作為常規操作一部分的順序代碼轉換而來的事務來完成。

上面簡短的調研只涉及到有關實現並發查找樹的基本問題和技術。再提一些很多改進和擴展的知識中的一小部分,[105]提出了在數據庫產品中用B+樹解决實際問題,比如失敗後恢複;[75]提出用廣義搜索樹(GiSTs)的並發實現來方便實現沒有精巧的並發控制的查找樹的設計,並提出幾種支持高效插入和删除一組值的樹。Pugh提出了它的skiplist隨機查找結構的一個並發版本。在skiplist中的期望查找時間與其元素個數是對數關系。skiplists主要的優勢時它們不要求再平衡:插入操作在一個隨機並且可保持查找樹平衡的方式中被完成。

並發查找樹和其他數據結構的實驗和分析的評估在[41, 67]中可以找到。

原創文章,轉載請注明: 轉載自並發編程網 – ifeve.com本文鏈接地址: 並發數據結構-1.7 查找樹

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