contributed by <93i7xo2
>
Source: quiz2
本偏論文旨在提出一個 lock-free "Write-Rarely-Read-Many" maps,基於 Lock-Free Data Structures 提出的方法進行改良。
後者的設計是 writer 在寫入時 map
產生一份 map
副本,再修改副本對應的值;reader 讀取時增加型態為 map
指標的 reference count,相對的於結束時減少,為 0 時更新至新的 map
並刪除舊 map
。之所以要用指標而非 map
本身,原因在於 map
大小不定而指標是固定的。
原本只要使用 CAS 操作 reference count,但為了保證不會遇到執行緒 A 判斷要刪除 map
、而 B 正要讀取同一份 map
的情況,有幾種解決方式:
map
,無法保證該等待多久,糟糕的設計。map
進行關聯,使得在操作同樣 map
的執行緒知道 reference count 經過更動再重新嘗試。 DCAS 使用兩個不相鄰的 words ,然而實作 DCAS 的硬體非常少見且毫無效率。另一種是 CAS2 ,採用相鄰 words (應該是指 double-width compare-and-swap, DWCAS),同樣也是缺乏實作。雖然 DCAS 能用 CAS 合成,CAS 也有許多把戲,例如指標後方幾位元塞 reference count,但 Hazard Pointer 直接提出新的架構解決且保證 wait-free。
在 不考慮 compiler reordering 和 out-of-ouder execution 的前提下,Hazard Pointers 概念是:reader 將欲讀寫資料 map
使用 hazard pointer 包裝,加入與 writer 共享的 list (pHead_
),此 list 內的元素只增不減,因此排除 ABA problem。writer 在複製一份副本 map
進行增減,將舊 map
放到所處執行緒的 retired list,待舊 map
累積至一定數量,執行緒再掃描將 retired list 內無 reader 使用的 map
刪除。
hazard pointer 結構如下:
pHead_
& listLen_
: 紀錄 hazard pointer 及長度pNext_
: 指向下一個 hazard pointeractive_
: 設計上為可回收使用,由 reader 結束時標記為 0 而不釋放,供下一個 reader 使用。pHazard_
: 指向資料 map
的指標Scan
用來釋放沒有 hazard pointer 指向的 map
。
Acqurie
& Release
為 reader 建立及釋放 hazard pointer 的函式。
當任一執行緒想釋放 map
,呼叫 Retire
。等到 retired list 的 old map
達到一定數量 Retire
才會呼叫 Scan
進行清理。
利用 HPRecType
所提供的方法實作 WRRMMap
兩種操作 - Update
& Lookup
可能會好奇短短一行
為何要大費周章寫成
原因是只要保證指向 map 的 hazard pointer 建立,writer 就不可能在 Retire
時將其釋放,reader 可對其進行存取。另一方面 ptr
是 thread local variable,減少頻繁存取 pRec->pHazard_
的機會。
Scan
的 wait-free 屬性節錄 wiki
An algorithm is wait-free if every operation has a bound on the number of steps the algorithm will take before the operation completes.
原文假設 Scan
使用 hashtable 來儲存 hazard pointer,使其複雜度降到 。 為 retired list 進行清理的臨界值,N 個 writer 情況下最多有 個需要刪除。挑選 , 為 listLen
也就是 hazard pointer 總量,定 ,這樣一來每次 Scan
只會有 個被刪除。
Scan
也不需要仰賴其他執行緒的行為,本身而言也能在有限時間內完成(wait-free)。最後總結 Lookup
和 Update
都是 lock-free,reader 不干擾 writer ,而 writer 也能保證運行,更提到 Lookup
有 wait-free 的解法。
Source
Cited by 584
考慮一帶有 dummy node (head
, tail
) 的 ordered list,要進行 non-blocking insertion/deletion,每個 node 結構如下:
Insertion
先看 insertion,在 10 和 30 間想插入 20,得先將節點指向 30 (左),再將 10 的 next field 以 CAS 替換成節點 20 (右)。
Deletion
在 head
和 30 間刪除 10,若以 CAS 檢查 head.next == 10
然後替換成 30 ,無法預防在 10 和 30 間有新節點 20 插入,從而導致節點遺失。
本篇論文提出新的演算法為了解決此問題,將欲刪除的節點標記(mark),稱作 logically delete,之後再進行刪除(physically delete),而插入時所找到的左右節點彼此不能為被標記(marked)。論文使用節點的 next
儲存狀態,在 pointer 對齊的狀態下可使用 next 的 LSB,mark/unmark 都是操作此 bit。
以下就論文提出的四種操作進行說明。
考慮到一集合有三種操作
三種操作的返回值代表成功與否,在這裡用 single linked list 呈現集合,而在 list 的實作中三種操作都會使用到 Search 方法。
search
返回 left_node
及 right_node
,用來
left_node
及 right_node
間插入節點或是
right_node
無論用途為何,需滿足以下條件
left_node.key
search_key
right_node.key
left_node
與 right_node
皆為 unmarkedleft_node
相鄰 right_node
程式碼細分為 3 個 Stage 說明
Stage 1:
list->head
找尋 left_node
, right_node
list->head
, list->tail
皆為 unmarked,因此最差情況就是返回 head
& tail
search_key
right_node.key
Stage 2:
search
的另一個目的是找出相鄰 node,這一步是檢查是否相鄰。right_node
可能中途被其他 processer 標記 marked,因此再檢查一次。 left_node
的檢查,就留到使用到 search
的函式。
Conditions Maintained by Search:
…Nodes never become unmarked and so we may deduce that the right node was unmarked at that earlier point.
Stage 3:
若不相鄰,則將 left_node
與 right_node
間的 logically deleted 節點清除,作法是將 left_node.next
指向 right_node
。
left_node.next
是否有更改過,只要 left_node.next
不變就能保證先前檢查 left_node
和 right_node
間都是 logically deleted node,而可安心鏈結至 right_node
之後仿照 Stage 2. 檢查 right_node
的狀態
Stage 1+2+3
在 List::search
找到的 left_node
, right_node
間插入新節點,行 6 檢查右節點 key
是否與新節點重複
返回 false 代表無對應 key 的節點存在
List::find
尋找節點的過程right_node
非 logically deleted 再用 CAS 標記,與 List::insert
的 (C2) 一樣都是確保 search
之後獲得的節點在中途不會被其他 processor 所標記。left_node
連結到 right_node_next
完成移除(remove),可能成功或失敗。失敗原因之一可能如下
List::delete
實作刪除節點 R
search
,在 (C1) 將 L1 連結至 N2
List::search
實作刪除節點 N1
right_node
放進 retire list,補足 List::delete
和 List::search
沒有實作到的部份。論文並沒有針對這部份進行推演,而是用了其他方法證明正確性。基於上述兩篇論文,很清楚的看到 quiz2 是基於 Non-Blocking Linked-Lists 的實作,而在刪除節點時採用 Hazard Pointers 的作法。從 list_find
函數可以看出一些蹤跡。
__list_find
函數對應到 List::search
,除了 left node
和 right node
移到引數,原函式外的 right_node.key != search_key
檢查也實作在函數內,返回 boolean。
而符號與原論文些許不同外,型態也有所不同,但節點的狀態還是儲存在 next
欄位。 基於 hazard pointer 的規則,用到的節點均以 list_hp_protect_ptr
保護。
Thesis | quiz2 |
---|---|
left_node | prev |
right_node | curr |
t_next | next |
我們將原函式拆成幾個部份探討
初始化 prev
及 curr
,想像 prev
是指位在 head
前面的 unmarked node 底下的 next
欄位,而 curr
指向 head
。
14, 15 行的作用如在確保 curr
成功放入 hazard pointer,對應到如下的實作。之後多次見到此種用法。
再來找下一個 unmarked node
get_unmarked(next)
沒放入 hazard pointer 則跳出迴圈,不懂這裡的邏輯 list->tail
前一個節點跳出迴圈 curr
放入 hazard pointer21-24 行的問題後來由 RinHizakura 在 commit 83ef91 修正:
當
是 unmarked,就確定 curr
是 unmarked node,加上 prev
總共有兩個 unmarked node。
緊接著 29~34 行檢查 key
,若檢查沒過,繼續尋找下一個 unmarked node,同時將 prev
替換成 curr
這個最近發現的的 unmarked node。
原論文的方法是將 left_node
連結至 right_node
並沒有刪除節點,這裡在遍歷的過程中逐一刪除節點。
對照以下 Non-blocking Linked List 的實作
不難發現 list_insert
其實就是 List::insert
,除了 List:search
被 __list_find
取代而稍做調整。
list_hp_clear()
來釋放那些在 __list_find
加入 hazard pointer 的節點論文實作:
quiz2 實作:
對照發現 quiz2 只是把原本迴圈外的移除節點的部份搬進迴圈,在移除成功時呼叫 retire
等待未來刪除節點。
分成 2 個 stage:
Stage 1: 標記 unmarked right_node
(curr
)
Stage 2: