--- tags: LINUX KERNEL, LKI --- # [Linux 核心設計](https://beta.hackfoldr.org/linux/): Scalability 議題 Copyright (**慣C**) 2019 [宅色夫](http://wiki.csie.ncku.edu.tw/User/jserv) ==[直播錄影](https://youtu.be/oTf6ZIWeYYA)== ## 點題 在處理器邁向多核後，擴展性 (scalability) 是衡量資訊系統整體效能的關鍵議題。倘若有一台伺服器，內置 2 顆處理器核 (core)，往往無法達到 2 倍單核處理器的工作能力，即便共同分擔工作使工作加速完成，然而處理器間需要進行協同溝通，後者一樣要耗佔執行處理的運算資源、記憶體的存取頻寬資源。因此，多核系統為了要讓效能盡可能獲得線性擴展，牽涉到底層的伺服器硬體連接架構，CPU 與記憶體間、CPU 與 CPU 間的傳輸頻寬是否夠大、傳遞是否夠快無延遲、傳輸路由是否夠有彈性等等，Linux 核心長期以來針對 scalability 做了大規模調整，本議程嘗試歸納整理。 :::success Wikipedia 對於 [scalability](https://en.wikipedia.org/wiki/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 關鍵考量。 ![](https://i.imgur.com/hEWU0I9.png) [ [電視辯論](https://youtu.be/ZAdnf1Oqcz8) ] 解決 scalability 的手法有 lock-free, sequence lock, RCU 等等。 ## 我們設定的場域 * [電信運營商 數據處理架構轉型中的思考](https://www.slideserve.com/zia-rodriguez/t-hinking-in-data-processing-architecture-transformation)，中國聯通 * 中國聯通、中國電信、中國移動合稱中國三大電信運營商 * 複習 [Linux 核心設計: RCU 同步機制](https://hackmd.io/@sysprog/H19V4eyfV) ![](https://i.imgur.com/btADggY.png) > 取自 [Digital Transformation with Amdahl’s & Gunther’s Law](https://medium.com/knoldus/digital-transformation-with-amdahls-gunther-s-law-3bb06d4e71dc) ## An Analysis of Linux Scalability to Many Cores * OSDI'10 論文: [An Analysis of Linux Scalability to Many Cores](http://pdos.csail.mit.edu/papers/linux:osdi10.pdf), MIT CSAIL * [投影片](https://www.usenix.org/legacy/events/osdi10/tech/slides/boyd-wickizer.pdf) * Geoffrey Challen 教授的[重點整理](https://www.ops-class.org/slides/2016-04-29-scaling/) / [解說錄影](https://youtu.be/F9z7zuezpzI) 研究貢獻 1. 提出 sloppy counters 方法用於解決 shared counter 不 scale 的問題 * 只修改 shared counter 裡頭造成 scale 問題的部分，而不用對所有引用該 counter 之處進行修改 2. 針對核心 scalability 測試集合 MOSBENCH 3. 各種改進 scalability 的技巧 4. 結論：不用修改典型核心來實現 scale 的目標 - [ ] 如何分析 Linux 的 scalability？ 實驗環境 - Linux 核心版本 2.6.35-rc5 - Linux 運作於 48 cores MOSBENCH: 7 個跑在 Linux 上的系統應用程式 - exim - 使用一個 master 行程來監聽 SMTP 請求，對每個新連接，fork 出一個新行程處理 - 新的行程負責接收郵件，將郵件隊列到一個目錄中（目錄中每個檔案對應於一個郵件)，接下來分發郵件到使用者郵件檔案，刪除目錄中的郵件，在 log 中記錄等等 - 每個行程需要 fork 兩次來發送一封郵件，單核運行花費 `69%` 的時間在核心中，包括行程建立和小檔案建立及刪除 - memcached - 單個 memcached 伺服器在多核中運行時，瓶頸在保護 key-value hash table 的內部 lock - 為避免這點，執行多個 memcached 伺服器，每個都有自己的 port，客戶端採用分散式存取策略，去存取這些服務端 - 單核時 `80%` 時間在核心中，主要包括 TCP/IP 網路堆疊 - Apache - 規劃每 core 運行一個行程，每個行程用一個 thread pool - thread pool 中一個執行緒負責接受連接，其他執行緒負責處理連接 - 單核運行時 Apache 花費 `60%` 的時間在核心上，對檔案系統、TCP/IP 網路堆疊的衝擊較大，因為其對每個請求都要打開並且統計一個檔案 - PostgreSQL - PostgreSQL 中有大量的資料結構共享和同步操作 - 將資料庫表格透過檔案形式保存，並被所有 PostgreSQL 行程共享存取 - 每個連接開一個行程，利用核心 lock 機制同步和負載均衡這些行程，並通過共享網絡介面的 TCP socket 和客戶端通訊 - 對於一個 read-only 測試來說，PostgreSQL 在單核上 `1.5%` 的時間在核心中，48 核 `82%` 的時間在核心 - gmake - 用 GNU make 搭配 GNU toolchain 編譯核心原始程式碼 - gmake 建立比 CPU 核數更多的行程並且大量讀寫檔案 - 單核時 `7.6%` 的時間在核心裡，但是整體耗時瓶頸在它所執行的編譯器上 - Psearchy - 用來索引和查詢網頁的工具 - pedsort 在每個核上執行一個索引器行程，行程間共享輸入檔案 - 每個核跑二個階段，第一階段是從工作隊列中拉出所輸入的檔案，讀檔並將每個單詞的位置輸入進每個核的 hash table 中，當 hash table 大到一定程度後，對其按照字母排序，寫到儲存空間裡頭的一個暫時索引檔裡頭，並繼續讀取取檔案。這個階段既是 CPU 密集的也是檔案系統密集的 - 採用排序的方式先處理大檔案，到工作隊列為空時，每個核合併它生成的所有臨時索引檔案，把單詞位置列表合併起來，產生一個保存了每個單詞位置的索引檔案及一系列的 BDB 檔案保存了每個單詞和它在檔案中的偏移量。這一階段主要是檔案系統密集 - 單核在核心中時間是 `1.9%`，48 核則是 `23%`，這是典型的 scalability 問題 - MapReduce - 臨時表格存放於主記憶體中，對核心的主記憶體分配和 page fault 處理有壓力，單核 `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 解法。 - [ ] Linux Scalability Problems 在瞭解 sloppy counters 之前，可參照[投影片](https://www.usenix.org/legacy/events/osdi10/tech/slides/boyd-wickizer.pdf) 第 21 到 47 頁，描述一個 Linux scalability 問題：讀取 mount table 時所造成，程式碼如下: ```cpp struct vfsmount *lookup_mnt(struct path *path) { struct vfsmount *mnt; spin_lock(&vfsmount_lock); mnt = hash_get(mnts, path); spin_unlock(&vfsmount_lock); return mnt; } ``` 要瞭解為什麼會造成 scalability problem還需瞭解 `spin_lock` / ` spin_unlock` 的實做，如下: ```cpp void spin_lock(spinlock_t *lock) { t = atomic_inc(lock->next_ticket); while (t != lock->current_ticket) ; /* Spin */ } void spin_unlock(spinlock_t *lock) { lock->current_ticket++; } struct spinlock_t { int current_ticket; int next_ticket; } ``` > 在 ARMv7 架構上，atomic 操作可透過 `ldrex` 和 `strex` 指令來實作。 依據 spin_lock 實作程式碼，`t` 代表某 core 拿到一個編號，若這個編號不等於目前可執行的編號就必須等待 (spin)。而 `spin_unlock` 則是某 core 執行完 critical section，告知其他 core 下個編號是多少。由於是 atomic 操作，所以 core 拿到的編號是唯一，不會有多個 cores 拿到相同編號的情形。 下表格展現這樣的情境: * core1/core2 正執行 `while (t != lock->current_ticket)` * core3 正執行 critical section | | 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)` 等待編號輪到自己。 ![](https://i.imgur.com/zYKu2sI.png) * 粉紅色部分代表正在等待正確編號的 cores * 紫色部分代表各個 core 獲得的編號 * 藍色代表正執行 `spin_unlock()` 藍色在執行` spin_unlock()`，就意味著更新 `lock->current_ticket`，而且各個正在等待正確編號的 cores，必須從全域記憶體中載入 `lock->current_ticket` 來比較是否與自己的編號相等。 本來可以並行 (concurrent) 執行的程式碼，因為 lock，造成循序 (sequential) 執行，並降低 scalability。 針對讀取 mount table，如何可提高 scalability 呢？乍看之下無法達成 (棋子 vs. 塞子) 但若利用 mount table 很少被修改的特性，就可變更程式碼如下: ```cpp= struct vfsmount *lookup_mnt(struct path *path) { struct vfsmount *mnt; if ((mnt = hash_get(percore_mnts[cpu()], path))) return mnt; spin_lock(&vfsmount_lock); mnt = hash_get(mnts, path); spin_unlock(&vfsmount_lock); hash_put(percore_mnts[cpu()], path, mnt); return mnt; } ``` 注意到第 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。 ![](https://i.imgur.com/TjmJ1XG.png) sloppy counters 是用此想法來設計。 - [ ] Sloppy Counters 解決核心在釋放物件時使用到 reference count 所面臨的問題。[投影片](https://www.usenix.org/legacy/events/osdi10/tech/slides/boyd-wickizer.pdf) 第 60 頁舉一個 reference count 的例子: ```cpp void dput(struct dentry *dentry) { if (!atomic_dec_and_test(&dentry->ref)) return; dentry_free(dentry); } struct dentry { … int ref; … }; ``` 此例也有 `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。參考[投影片](https://www.usenix.org/legacy/events/osdi10/tech/slides/boyd-wickizer.pdf)的第 74 到 87 頁。 ## Linux, Locking and Lots of Processors * [投影片](http://wiki.csie.ncku.edu.tw/linux/10-linux.pdf)，自第 149 頁起 * Multiprocessor Effect: Some fraction of the system’s cycles are not available for application work: - Operating System Code Paths - Inter-Cache Coherency traffic - Memory Bus contention - Lock synchronization - I/O serialization ## The Linux Scheduler: a Decade of Wasted Cores * 論文: [The Linux Scheduler: a Decade of Wasted Cores](http://www.ece.ubc.ca/~sasha/papers/eurosys16-final29.pdf) * [研究素材和程式碼](http://www.i3s.unice.fr/~jplozi/wastedcores/) * [簡報](http://www.i3s.unice.fr/~jplozi/wastedcores/files/extended_talk.pdf) * [閱讀筆記](https://zhuanlan.zhihu.com/p/30811263)
Last changed by  
 
sysprog
System Software Programming
4920

Read more

並行程式設計: 排程器

本講座嘗試運用 Linux 系統呼叫，建構使用者空間的任務排程器，探討 coroutine、執行緒、行程，及排程器的原理，隨後該任務排程器會擴充為支援搶佔式多工的實作，後者將進一步擴充以對應到多核處理器和 Linux 核心 CPU 排程器的原理。本講座以「做中學」的手法，讓參與者得以兼顧作業系統原理和排程器的具體設計議題。

4/19/2024
並行和多執行緒程式設計系列講座

從 Concurrency (並行) 和 Parallelism (平行) 的差異談起，再釐清 semaphore 和 mutex 一類的Synchronization (同步處理) 議題。本講座透過 POSIX Thread 探討 thread pool, Lock-Free Programming。lock-free 使用的 atomic 操作, memory ordering, thread pool, M:N threading model 等進階議題。

4/19/2024
事件驅動伺服器：原理和實例

資料整理: eecheng87, jservThe Evolution of Linux I/O Models:A Path towards IO_uring / 錄影

4/18/2024
從 CPU cache coherence 談 Linux spinlock 可擴展能力議題

本文涵蓋 spinlock 本身的效能和可擴展能力 (scalability) 議題

4/18/2024
Read more from sysprog
Published on HackMD