在處理器邁向多核後,擴展性 (scalability) 是衡量資訊系統整體效能的關鍵議題。倘若有一台伺服器,內置 2 顆處理器核 (core),往往無法達到 2 倍單核處理器的工作能力,即便共同分擔工作使工作加速完成,然而處理器間需要進行協同溝通,後者一樣要耗佔執行處理的運算資源、記憶體的存取頻寬資源。因此,多核系統為了要讓效能盡可能獲得線性擴展,牽涉到底層的伺服器硬體連接架構,CPU 與記憶體間、CPU 與 CPU 間的傳輸頻寬是否夠大、傳遞是否夠快無延遲、傳輸路由是否夠有彈性等等,Linux 核心長期以來針對 scalability 做了大規模調整,本議程嘗試歸納整理。
Wikipedia 對於 scalability 的說明:
A system whose performance improves after adding hardware, proportionally to the capacity added, is said to be a scalable system.
整體效能可隨著硬體的成長而比例性成長,重點是比例
許多 scalability 議題來自其中一個處理器核要使用另外一個處理器核所寫入的資料,進而導致大量的 cache coherence 開銷,二個處理器核競爭資料和 lock 是常見的狀況,恰好可對比於韓國瑜先生提出的「棋子」和「塞子 」觀點。於是,在多核處理器中的 cache coherence protocol 及其共享資料的處理機制,自然是 Linux 核心的 scalability 關鍵考量。
[ 電視辯論 ]
解決 scalability 的手法有 lock-free, sequence lock, RCU 等等。
研究貢獻
實驗環境
MOSBENCH: 7 個跑在 Linux 上的系統應用程式
69%
的時間在核心中,包括行程建立和小檔案建立及刪除80%
時間在核心中,主要包括 TCP/IP 網路堆疊60%
的時間在核心上,對檔案系統、TCP/IP 網路堆疊的衝擊較大,因為其對每個請求都要打開並且統計一個檔案1.5%
的時間在核心中,48 核 82%
的時間在核心7.6%
的時間在核心裡,但是整體耗時瓶頸在它所執行的編譯器上1.9%
,48 核則是 23%
,這是典型的 scalability 問題3%
在核心,48 核則為 16%
實驗中找出 Linux scalability problems,並列出對應的現有解法。
詳見該篇論文的 Figure 1 (第 5 頁)
第 4 章 Kernel Optimizations 提到為何對於 Linux scalability problems 所整理的方法還沒實作在標準的核心中,因這些問題對於 small-scale SMP 影響不明顯或在很多應用中靠著 I/O delays 來遮掩。
these solutions have not been implemented in the standard kernel is that the problems are not acute on small-scale SMPs or are masked by I/O delays in many applications.
Linux 在 reference-counted garbage collection 方面和管理許多資源上使用 shared counter,如果很多 cores 需要更新這些 counters,就會是 scalability 瓶頸所在。論文針對這個問題提出 sloppy counters 解法。
在瞭解 sloppy counters 之前,可參照投影片 第 21 到 47 頁,描述一個 Linux scalability 問題:讀取 mount table 時所造成,程式碼如下:
要瞭解為什麼會造成 scalability problem還需瞭解 spin_lock
/ spin_unlock
的實做,如下:
在 ARMv7 架構上,atomic 操作可透過
ldrex
和strex
指令來實作。
依據 spin_lock 實作程式碼,t
代表某 core 拿到一個編號,若這個編號不等於目前可執行的編號就必須等待 (spin)。而 spin_unlock
則是某 core 執行完 critical section,告知其他 core 下個編號是多少。由於是 atomic 操作,所以 core 拿到的編號是唯一,不會有多個 cores 拿到相同編號的情形。
下表格展現這樣的情境:
while (t != lock->current_ticket)
core0 | core1 | core2 | core3 | core1 | core2 | ||
---|---|---|---|---|---|---|---|
獲得的編號 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
已執行的編號 | * | * | * | ||||
目前執行的編號 | * |
一旦 core3 執行完 critical section,並執行 spin_unlock
,就會變成下表:
core0 | core1 | core2 | core3 | core1 | core2 | ||
---|---|---|---|---|---|---|---|
獲得的編號 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
已執行的編號 | * | * | * | * | |||
目前執行的編號 | * |
不要小看 t = atomic_inc(lock->next_ticket)
這道敘述,以 ARM 架構來說,處理 exclusive monitor 對應的硬體代價很大。投影片用測量硬體需花上 120-420 cycles 來帶過運作細節。若獲得的編號還不能執行時,則會一直執行此程式碼 while (t != lock->current_ticket)
等待編號輪到自己。
spin_unlock()
藍色在執行 spin_unlock()
,就意味著更新 lock->current_ticket
,而且各個正在等待正確編號的 cores,必須從全域記憶體中載入 lock->current_ticket
來比較是否與自己的編號相等。
本來可以並行 (concurrent) 執行的程式碼,因為 lock,造成循序 (sequential) 執行,並降低 scalability。
針對讀取 mount table,如何可提高 scalability 呢?乍看之下無法達成 (棋子 vs. 塞子) 但若利用 mount table 很少被修改的特性,就可變更程式碼如下:
在 kernel v3.13 之後,lookup_mnt() 以 RCU 取代 spin_lock。
注意到第 3 行 percore_mnts[cpu()]
, 意思是說各個 core 上對應的記憶體有各自的 mount table,若 path 在本地 core 上的 mount table 可找到的狀況,就直接讀取。倘若沒辦法直接在本地 mount table 找到的話,就從全域記憶體的 mount table 讀取並更新本地端的 mount table。
SMP Linux 讀取 mount table 會造成 scalability 問題的解法,終究是回歸本質,觀察程式行為,歸納出因為 mount table 很少被修改,所以可複製很多份至本地端記憶體來讀取,等到需要更新再更新全域記憶體的 mount table 及個別 core 的 mount table。
sloppy counters 是用此想法來設計。
解決核心在釋放物件時使用到 reference count 所面臨的問題。投影片 第 60 頁舉一個 reference count 的例子:
此例也有 dentry->ref
被拿來做 atomic_dec_and_test
操作,此運算是把 dentry->ref
減一,如果減到為 0
,就回傳 1
。所以執行到 dentry_free(dentry)
代表 dentry 這個物件該被被釋放。而 dentry->ref
是紀錄目前有多少個執行單元在使用這個物件,注意此物件的實例僅有一個。
上個讀取 mount table 的案例是,有個全域記憶體的資料存取。本例則是 dentry->ref
,對 dentry->ref
執行減一的 atomic 操作(atomic_dec_and_test
),然後判斷是否等於 0
。論文提出,硬體成本是 120 到 4000 cycles。
這問題就是各 cores 在 atomic_dec_and_test(&dentry->ref)
時,會花比較久的時間。解法是繼續觀察,論文歸納出核心很少需要釋放物件,所以可設計由各個 cores 自行維持的 "spare" (自用) references,且有個共享的 central counter。參考投影片的第 74 到 87 頁。