contributed by < linjohnss >
Linux 核心提供一套 Resizable, Scalable, Concurrent Hash Table,名為 rhashtable
(見 include/linux/rhashtable.h 及 lib/rhashtable.c),描述於論文〈Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming〉。摘譯 LWN 文章,並佐以原論文,描述 rhashtable 何以落實高效的並行雜湊表,搭配撰寫 Linux 核心模組作為試驗
在 Linux 的 file system 中,利用 hash table 儲存 mount 的 root dentry ,因此 lookup_mount
可以利用 hash_get
取得 mount 的 root dentry
Linux 核心支援多種資料壓縮的方法,而 hash table 在其中扮演重要的角色。hash table 儲存 encode 過後的片段資料,在進行資料壓縮過程中,可以用快速的找出重複的資料
在 linux/lib/842/842_compress.c
中,利用 hash table 找尋是否有重複的 index
hash table 雖然相較於 linked list 能更快速的搜索目標,但需要避免碰撞發生造成效能損失。為了應付此問題,除了改進 hash function,對於 hash table 的大小估計同樣重要,太小的會成性能損失;太大會造成空間的浪費。為 hash table 選擇正確的大小並不容易,在 Linux 核心中有許多 hash table 其大小是在系統初始化時進行簡單的估計。然而,儘管猜測是完美的,工作負載也會隨時間而變化。此時,一個 resizable 的 hash table 即可解決此問題。
但是若要同時達到 concurrent 與 resizable,不對 hash table 進行 blocking 是很難達成的。在 2010 年,Josh Triplett、Paul McKenney 和 Jonathan Walpole 在 USENIX ATC 發表一篇名為〈Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming〉 的論文,描述了該問題解決方案。
在 Linux 核心的網路模組中,RDS 使用 rhashtable 儲存 ip 地址與 port
linux/net/rds/bind.c
Relativistic hash table 與普通 hash table 類似,同樣都是由包含 link list 的 bucket 組成。
若發現目前的 hash table 的空間太大,希望能縮小 hash table
此演算法放寬每個 bucket 內的 link list 必須為同一個 index 的限制,使 link list 可以臨時包含不同 index 的 node,確保在 resizing 時不會找不到 node,並且可以避免複製 link list,論文稱其為 "hash chains imprecise"
為簡單起見,rhashtable 透過整數因子限制 resizing 改變桶的數量。例如,將 bucket 的數量加倍或減半。這保證了兩個約束:
隨著 hash table 中的 node 數量增加,每個 bucket 的平均深度會增加,造成查找效率降低,因此需要擴張大小
注意,此時新的兩個 bucket 只有連接的第一個 node 為正確的,但由於舊的 link list 仍將 node 接在一起,所以此時新的 hash table 查找成果仍為正確,只是需要花費較多走訪時間
4.) 更改前一項中的 next 指標,指向下一個匹配的 node:
在另一個 RCU 寬限期過去之前,不能對此 list 進行任何更改,否則在 list 中的 reader 可能最終會出現在錯誤的位置。
假設尋找綠色 node 的 reader 可能正在查看從列表中修補出來的藍色 node,但是,由於該 node 的 next 指標保持不變,因此 reader 不會 derailed。而尋找藍色 node 的 reader 從一開始就不會看到更改的 node,因此它們也是安全的。
該演算法通過更改不尋找將 "unzip" 的 node 的 reader 的可見指標來工作。只要每個 RCU 寬限期只更改列表中的一個指標,這個屬性就成立,並且當 reader 通過它時,list 可以安全地 unzip。
如果 hash table 很長,則此過程可能需要相當長的時間。但是調整大小操作應該比較少,而 reader 存取 table 的頻率很高。所以,對於一個存取量足夠大的 table,額外的努力最終是值得的,在經常有 reader 存取的路徑中將得到了很多倍的回報。
現階段我們可以利用以 RCU 為基礎的 hash table 使插入、刪除與查找並行執行。而引入額外的 resizing 操作,也同樣需要做到與其他操作同步。
原先若要進行 resize 操作,需阻止 table 的更新直到 resize 完成。但是,我們可以處理在 resizing 產生的中間狀態,從而提前運行並行更新 table,這可以避免 concurrent 時的過度延遲。
In the simplest case, concurrent updates can continue to block until the resize completes;however, concurrent updates can potentially run earlier if they carefully handle the intermediate states produced by the resizer. For a sufficiently large hash table, this may prove necessary to avoid excessive delays on concurrent updates.
關於在 resizing 同時插入與刪除主要可以分為兩種情形:
論文中有更多的實做細節,包含針對記憶體分配的 "Resizing in Place" 與優化 hash 分配的 "Keeping Buckets Sorted" 本節就暫不描述
rcuhashbash-resize 為論文創建一個為了可調整大小的 hash table 的測試工具和基準測試框架。首先創建一個具有指定 bucket 數量的 hash table,並向其中添加包含從 0 到指定上限的整數值的元素。然後它啟動 reader 執行緒和調整大小執行緒,這些執行緒記錄 thread-local 統計資料,以避免需要額外的同步。當測試完成時,rcuhashbash-resize 停止所有執行緒,匯總它們記錄的統計數據,並通過 kernel message buffer 顯示結果。
rhashtable 的實現在 Linux 核心 3.17 版開始加入,這使得 hashtable 可以調整大小,並同時允需 reader 與 writer 同時存取。此篇將描述在 3.17 版中所看到的 "rhashtable" 的 kernel API。
rhashtable 最初是為了在網路子系統中使用而被創建的,但當時的開發者 Thomas Graf 明白 rhashtable 將會獲得更廣泛的使用。因此,他們設計一系列的前置參數,來擴張 rhashtable 的 API 的使用可能,只要完成設置,後續對 table 的操作就會相對簡單了。
首先,我們可以看到 rhashtable
的結構包含 rhashtable_params
,因此需要先定義參數結構
以下為 rhashtable_params
的定義:
nelem_hint
是對錶中將存儲多少元素的猜測(它用於計算初始的 table 大小)。key_len
和 key_offset
描述了 key 的字節大小和它在結構中的 offset(應該用 offsetof() 獲得)。head_offset
是 hashed object 中 rhash_head 結構的 offset。hash_rnd
是 hash function 中使用的隨機種子;如果為零,則 rhashtable 將生成一個隨機種子。max_shift
是用於設置 table 的最大大小;它的值是 table 大小以 2 為底的對數。hashfn
是執行的 hash function;通常它可以設置為 arch_fast_hash()
,在<linux/hash.h>
中有定義。obj_hashfn
是 hash 整個 hash object 的函式。如果已提供 key_len
和 key_offset
,則不需要 obj_hashfn
。如果計算 hash 需要比查看 object 更為複雜,則可以提供這個函式來完成這項工作(並且 key_len
應該設置為零)。grow_decision
和 shrink_decision
提供自動調整 table 大小的函式。如果這些函式返回真值,則表的大小將適當的加倍或減半。另外,rhashtable
提供了兩個可用的函式:rht_grow_above_75()
和 rht_shrink_below_30()
。這些函式會力求保持 table 30% 到 75% 的滿度。mutex_is_held
如果當前持有 protecting mutex,則返回 true。用於除錯和追蹤,確保在呼叫修改 table 的函式時保持鎖定。後續就可以使用 rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params)
來分配一個 rhashtable
,另外也有,rhashtable_destroy(const struct rhashtable *ht)
來釋放 rhashtable
concurrent inserts 與 removes 必須進行 blocking,直到收縮演算法完成發布新 hash table 並等待 reader 結束存取舊 table
文章提到,後需提交的 patch 將會把調整大小的操作移到單獨的執行序中,所以將不再需要在上述函式中分配記憶體空間。因此,gfp_flags
參數將被刪除。而我們也可以看到在 6eba82 已刪除此參數
原先沒有像論文描述的對每個 bucket 用 lock 保護 ,加入對每個 bucket 的 spinlock,可以增加並行效率。並且將 expansion 與 shrinking 加到允許從 atomic context 插入和刪除的 warker queue,達到延遲 resizing 使插入和刪除可能與它並行發生,僅在 bucket unzip 或被 link 才短暫暫停
我在 Linux 核心發現從 v4 開始有一個用於測試 rhashtable
的 module test_rhashtable.c
我嘗試將 rhashtable.c 複製下來,並將其掛載到核心
首先,確認 Linux 核心版本為 5.13
從 test_rhashtable.c 的程式碼來看,他是使用 __init
and __exit
macros 去實做。因此我參考 Linux 核心模組運作原理 中掛載 hello 的方式
Makefile
產生 test_rhashtable.ko 之後,可將其掛載:
dmesg 命令可顯示核心訊息
test_rhashtable.c
的目的是測量操作的時間與正確性,主要分為三個部份:
而 resizing 的部份會在 rhashtable_init
時利用 rht_deferred_worker
使 table 在測試時自動調整大小,其作法是用 rht_grow_above_75()
與 rht_shrink_below_30()
判斷要擴張還是縮小
rhashtable.h
自 v3.17 到 v5.13,已從 200 多行增加至 1200 多行程式碼,有眾多的 API 擴增與改進,以下針對幾項test_rhashtable.c
有使用到的進行說明。
由於 rhashtable.h
自 2014 年實現在 Linux 核心以後被大量使用,因此微小的更改可能需要大量的重新編譯。所以 0eb71a 將 rhashtable-types.h
拆分出來,內容只包含主要的型態宣告,後續只須引入 rhashtable-types.h
即可,進而減少大型的重新編譯。
v5.13 的 rhashtable 參數相較 v3.17 的更加簡單易用,多了可以自動對 table 進行收縮的參數 automatic_shrinking
原先的 Lookup,需要有 RCU 確保並行的正確性,但是若有其他機制保證目標的存在,則可以使用 rhashtable_lookup_fast
加快運行時間
程式碼提供 rcuhashbash.c
與 rcuhashbash-resize.c
,這裡主要先測試 rcuhashbash-resize.c
編譯後會出現很錯誤,接下來就是一個一個 debug
從 linux kernel 程式碼中找到 cpu_clock()
是定義在 linux/sched/clock.h
,因此引入該函式庫
hlist_for_each_entry_rcu(tpos, pos, head, member)
,而根據 v5.13 的 rculist.h
已改為 hlist_for_each_entry_srcu(pos, head, member, cond)
,故將程式碼根據新的定義進行修改產生 rcuhashbash.ko 之後,可將其掛載:
dmesg 命令可顯示核心訊息
編譯成功後執行,若將 resize 開啟仍出現問題
發現是 resize 在 grow 時誤用了 node
,應該改為 entry->node
,就沒問題了
利用 ktime_get_ns()
紀錄分配 kthread_run()
與 kthread_stop()
的時間,計算 end - start
即為執行時間,並將其寫入 rcuhashbash_print_stats
作輸出
論文提供的測試平台主要是想測試 rhashtable 在發生 resizing 時,多個 reader read hit 的次數,用於比較 scalability。
Module 的參數包含:
test
:測試的演算法(rcu, ddds, rwlock)readers
:reader 線程的數量resize
:是否開啟 resizingshift1
:原始 table 大小shift2
:調整的 table 大小entries
:table 內條目的數量rcuhashbash_table
的結構包含用於計算 index 的 mask
與由 hlist_head
組成的 buckets
陣列。而 stats
結構為每個 reader 執行緒需要紀錄的統計變數
接著,程式會根據設定的參數先建立好 hashtable,並利用 hlist_add_head
插入 entries
個條目,然後分配 reader thread 與 resize thread 分別執行 rcuhashbash_read_thread
與 rcuhashbash_resize_thread
當 module exit 時,會停止所有執行緒,統計每個 reader thread 的 stats
,並釋放 table
與 thread_stats
分別調整三中不同演算法(rcu, ddds, rwlock)與 reader
的數量,比較每秒 lookup hit 的次數,而 resizer 在過程中會不斷調整 table 的大小,從 213 擴張到 214 再收縮回去(2 倍)
針對三中不同演算法,依序執行 1,2,4, 8, 16 個 readers
利用 shell script 固定每次測試時間為 30 秒
固定大小在 214, 比較不同演算法的查找次數
resize thread 會不斷在 213 到 214 之間調整 table 大小,比較在 resizing 時不同演算法的查找次數
比較固定大小在 213 與 214 還有 resize 時,使用 RP 演算法的查找次數
論文所使用的實驗環境為 24 個 hardware-supported threads,所以它選擇使用 1, 2, 4, 8, 16 作為測試的 reader 數量,使運行的線程都比支持的硬體還少。
Our test system had two Intel “Westmere” Xeon DP
processors at 2.4GHz, each of which had 6 hardware
cores of two logical threads each, for a total of 24
hardware-supported threads.
另外,論文觀察到 16 個 readers 與線性增長的預期偏差,可能是由於超過了 12 個處理器核的限制,而論文測試 16 readers 的性能似乎比 8 readers 的性能高出大約 50%,這與充分利用 12 個 cores 的預期線性增長一致
而本研究的實驗環境為 8 核 16 個硬體執行緒,但在 8 個 readers 就產生偏差,16 個 readers 發生瓶頸,可能原因是我在測試時仍有其他 process 在運作
本研究從最初的論文出發,說明 rhashtable 的動機、原理,再來介紹 Thomas Graf 在 Linux 核心的首次實作,以及至今 rhashtable.h
的演化,最後撰寫 Linux 核心模組作為試驗,得出以下結論: