本文要介紹的是 2018 年 OSDI 期刊中的論文 —— Arachne: Core-Aware Thread Management[^1]，這篇論文通過引入處理器感知的線程管理器 Arachne[^2] 提高應(yīng)用程序的性能，通過在 Memcached 中引入新的線程管理器，我們可以將 Memcached 的吞吐量提高 37%、降低 10 倍的尾延遲并且在與其他應(yīng)用程序混合部署時(shí)也幾乎不會帶來性能上的損耗。今天我們來看一看論文中基于處理器感知的線程管理器如何幫助應(yīng)用程序?qū)崿F(xiàn)低延遲和高吞吐量。

想要同時(shí)實(shí)現(xiàn)低延遲和高吞吐量不是一件簡單的事情，在傳統(tǒng)的線程管理或者協(xié)程管理器中，上層的應(yīng)用程序不清楚底層的調(diào)度策略，應(yīng)用程序自己無法決定會跑在哪個(gè) CPU 上。因?yàn)榇蠖鄶?shù)的場景不需要考慮極端的性能，代碼的可維護(hù)性和可讀性相比更加重要，這種關(guān)注點(diǎn)分離的設(shè)計(jì)方式能夠降低應(yīng)用程序的復(fù)雜性，所以它能夠?yàn)殚_發(fā)者提供便利。

應(yīng)用程序想要實(shí)現(xiàn)低延遲和高吞吐量就一定要通過虛擬資源管理它們的并行性，而現(xiàn)在它們沒有辦法告訴操作系統(tǒng)需要多少 CPU 資源，也無法直接確定線程和 CPU 之間的綁定關(guān)系。想要實(shí)現(xiàn)低延遲和高吞吐量，每個(gè)應(yīng)用程序都應(yīng)該能夠根據(jù)負(fù)載動態(tài)決定需要多少 CPU 資源并且可以控制線程和 CPU 的綁定關(guān)系。

處理器感知線程管理會為應(yīng)用程序提供 CPU 等信息，將對 CPU 的部分控制權(quán)開放給應(yīng)用開發(fā)者以滿足應(yīng)用程序在性能上的需求、不過因?yàn)?Linux 等操作系統(tǒng)沒有直接提供易用的接口，所以 Arachne 使用了如下圖所示的架構(gòu)實(shí)現(xiàn)處理器感知的線程管理，整個(gè)系統(tǒng)不需要修改操作系統(tǒng)內(nèi)核，它依賴操作系統(tǒng)提供的接口實(shí)現(xiàn)處理器感知，也可以與不使用 Arachne 的應(yīng)用程序一起運(yùn)行：

圖 1 - Arachne 架構(gòu)

 

Arachne 中包含了三個(gè)重要的組件，分別是仲裁者、運(yùn)行時(shí)和策略，其中仲裁者是運(yùn)行在 Linux 上的守護(hù)進(jìn)程，所有使用 Arachne 的應(yīng)用程序都會利用它提供的運(yùn)行時(shí)庫通過 Socket 與守護(hù)進(jìn)程通信，我們將依次介紹這三個(gè)組件的作用和原理。

仲裁者

核心仲裁者(Core Arbiter)是 Arachne 的核心組件，它是應(yīng)用程序和操作系統(tǒng)的中間層，主要負(fù)責(zé)控制系統(tǒng)中的 CPU 并將這些資源合理地分配給不同的應(yīng)用程序，該系統(tǒng)包含三個(gè)特點(diǎn)：

• 在用戶態(tài)基于 Linux 的機(jī)制實(shí)現(xiàn)了 CPU 管理;
• 可以與不使用 Arachne 的應(yīng)用程序同時(shí)存在;
• 使用協(xié)作式的方法管理內(nèi)核，包括優(yōu)先級管理和內(nèi)核搶占;

仲裁者使用 Linux 的 cpuset 特性將內(nèi)核分成管理的內(nèi)核和未被管理的內(nèi)核，未被管理的內(nèi)核會分配給機(jī)器上的其他應(yīng)用程序，而被管理的內(nèi)存會分配給使用 Arachne 的進(jìn)程。

圖 2 - 拆分 CPU 資源

 

這種方案可以與現(xiàn)有的進(jìn)程運(yùn)行方式兼容，我們不需要修改內(nèi)核，就可以直接利用 Linux 現(xiàn)有的特性管理 CPU 資源。

優(yōu)先級管理

當(dāng)應(yīng)用程序啟動時(shí)，它會調(diào)用 setRequestedCores: 方法通過 Socket 向仲裁者請求 CPU 資源，該方法的參數(shù)是一個(gè)數(shù)組，從左到右依次表示八種不同優(yōu)先級的 CPU：

0 0 1 2 0 0 0 0 

仲裁者使用了比較簡單的優(yōu)先級管理策略，高優(yōu)先級的請求可以覆蓋低優(yōu)先級的請求，因?yàn)闆]有其他調(diào)度器的分時(shí)復(fù)用機(jī)制，并且調(diào)度基本都是協(xié)作式的，所以部分應(yīng)用程序只要申請高優(yōu)先級的資源就可以餓死其他進(jìn)程，Arachne 中并沒有解決這個(gè)問題，雖然它提出可以通過鑒權(quán)防止惡意資源申請，但是這仍然無法解決饑餓問題。

資源申請

當(dāng)應(yīng)用程序想要向仲裁者申請 CPU 資源時(shí)，會經(jīng)歷如下所示的幾個(gè)步驟：

1. 應(yīng)用程序在發(fā)出 setRequestedCores: 后會即創(chuàng)建與請求核數(shù)相同的內(nèi)核線程(Kernel Thread);
2. 調(diào)用 blockUntilCoreAvailable: 阻塞這些線程等待仲裁者分配資源;
3. 當(dāng)仲裁者決定為這些線程分配資源時(shí)，它會通過 cpuset 綁定線程和 CPU、通知并喚醒應(yīng)用程序的內(nèi)核線程，操作系統(tǒng)會負(fù)責(zé)將當(dāng)前線程調(diào)度到綁定的 CPU 上;
4. Arachne 運(yùn)行時(shí)中的內(nèi)核線程隨后會在調(diào)度器中為其他的用戶線程分配合適的資源;

每一個(gè)基于 Arachne 運(yùn)行時(shí)的應(yīng)用程序中都會啟動對應(yīng)數(shù)量的內(nèi)核線程，運(yùn)行時(shí)中的調(diào)度器會決定執(zhí)行哪些用戶態(tài)線程，該模型與 Go 語言的 G-M-P 模型也比較相似[^3]，它們的初衷都是盡可能降低線程切換帶來的額外開銷，但是 Arachne 提供了對資源更細(xì)粒度的控制：

圖 3 - Arachne 線程模型

 

需要注意的是仲裁者和應(yīng)用程序之間的通信機(jī)制是不同的，應(yīng)用程序會通過 Socket 訪問仲裁者，而仲裁者發(fā)出的請求都是通過共享內(nèi)存。這是因?yàn)閼?yīng)用程序在發(fā)出請求后可以陷入休眠等待響應(yīng)或者資源的分配，但是 Socket 是相對比較昂貴的操作，所以仲裁者會通過共享內(nèi)存請求應(yīng)用程序。

Arachne 使用了協(xié)作的方式進(jìn)行調(diào)度，當(dāng)仲裁者需要回收資源時(shí)，應(yīng)用程序可以延遲一段時(shí)間釋放 CPU;如果應(yīng)用程序超過 10ms 都沒有釋放資源，仲裁者就會通過 cpuset 將資源分配給其他程序，沒有主動釋放的程序會看到性能明顯地下降。

運(yùn)行時(shí)

Arachne 的運(yùn)行時(shí)實(shí)現(xiàn)了老生常談的用戶態(tài)線程，但是這里的用戶態(tài)線程針對特定的場景做出了優(yōu)化，它主要支持細(xì)粒度的計(jì)算，其中包括大量生命周期極短的線程，例如常見的 HTTP/RPC 服務(wù)，它們會創(chuàng)建單獨(dú)的線程處理外部的請求。

圖 4 - HTTP 服務(wù)與線程

 

大多數(shù)的線程操作都需要在多個(gè) CPU 之間通信，而跨核的通信會導(dǎo)致緩存缺失(Cahce Miss)，緩存缺失大概需要 50 ~ 200 個(gè) CPU 循環(huán)，這也是影響 Arachne 運(yùn)行時(shí)性能的主要因素。為了解決緩存缺失帶來的性能影響，運(yùn)行時(shí)會在數(shù)據(jù)傳輸時(shí)并行執(zhí)行其他的指令，優(yōu)化 CPU 緩存以提升用戶態(tài)線程的性能。線程的創(chuàng)建和調(diào)度是運(yùn)行時(shí)的關(guān)鍵操作，優(yōu)化這些操作的性能就可以降低延遲并提高吞吐量。

線程創(chuàng)建

多數(shù)的用戶態(tài)線程管理器都會在同一個(gè) CPU 上創(chuàng)建線程并使用工作竊取(Work-stealing)[^4]平衡多個(gè) CPU 上的負(fù)載，但是工作竊取對于存在時(shí)間較短的線程來說是非常昂貴的，所以我們希望在線程創(chuàng)建時(shí)立刻觸發(fā)負(fù)載均衡，將線程創(chuàng)建在其他的核心上;同時(shí)，為了減少程序中的緩存丟失，Arachne 將每一個(gè)線程的上下文都綁定了特定的 CPU 上，只有在仲裁者回收時(shí)才可能發(fā)生處理器遷移，大多數(shù)的線程在創(chuàng)建之后就不會觸發(fā)遷移。當(dāng)應(yīng)用程序創(chuàng)建新的線程時(shí)：

1. 運(yùn)行時(shí)會在多個(gè) CPU 中隨機(jī)選擇兩個(gè);
2. 在上述兩個(gè) CPU 中選擇活躍線程數(shù)較少的 CPU;
3. 將線程開始的方法地址和參數(shù)拷貝到上下文中;

每個(gè) CPU 上都有對應(yīng)的 maskAndCount 變量，其中存儲著正在執(zhí)行的線程和當(dāng)前 CPU 上的線程數(shù)。為了減少線程的緩存丟失，我們使用單獨(dú)的緩存塊(Cache Line)存儲線程所有信息，這樣創(chuàng)建線程最少只需要觸發(fā)四次緩存丟失，分別是讀取maskAndCount、傳輸函數(shù)地址、參數(shù)和調(diào)度信息，能夠最大限度的減少開銷。

線程調(diào)度

傳統(tǒng)的調(diào)度模型會在運(yùn)行時(shí)中引入準(zhǔn)備隊(duì)列(Ready Queue)保存可執(zhí)行的線程，例如：Linux 和 Go 語言的調(diào)度器[^5]，但是如果準(zhǔn)備隊(duì)列是跨 CPU 的，那么增加或者刪除任務(wù)時(shí)都需要修改多個(gè)變量以及獲取共享鎖，這都會觸發(fā)緩存丟失進(jìn)而影響性能。

圖 5 - 線程調(diào)度

 

為了減少程序中的緩存丟失，Arachne 的調(diào)度器不會使用準(zhǔn)備隊(duì)列，它會持續(xù)檢查當(dāng)前 CPU 上的所有活躍線程直到發(fā)現(xiàn)可以運(yùn)行的線程，因?yàn)橐韵碌膬蓚€(gè)原因，這個(gè)看起來非常簡單的輪訓(xùn)機(jī)制實(shí)際上非常高效：

在同一時(shí)間，單個(gè) CPU 上應(yīng)該只會包含少數(shù)幾個(gè)線程上下文;

當(dāng)前線程一定會由其他核心喚醒，因?yàn)榭绾说膫鬏敃砭彺鎭G失，而在觸發(fā)緩存丟失時(shí)可以并行掃描全部上下文不會帶來過大的開銷;

因?yàn)榫€程可能處于阻塞狀態(tài)等待特定的執(zhí)行條件滿足，所以上下文中會包含 wakeupTime，即線程多久后需要被喚醒;線程可以通過 block(time) 和 signal(thread) 兩個(gè)方法改變 wakeupTime 通知調(diào)度器當(dāng)前線程的狀態(tài)和喚醒時(shí)間。

核心策略

為了能夠讓應(yīng)用程序?qū)?CPU 有更細(xì)粒度的控制，Arachne 不會在運(yùn)行時(shí)中指定 CPU 的使用策略，如何使用 CPU 都是由獨(dú)立的策略模塊確定的，Arachne 中的一些默認(rèn)核心策略如果不能滿足應(yīng)用程序的需求，它們還可以實(shí)現(xiàn)一些自定義的策略滿足特定的需求。

圖 6 - 線程類

 

與 Linux 調(diào)度器中的調(diào)度類比較相似，當(dāng)應(yīng)用程序創(chuàng)建新的用戶線程時(shí)，它需要指定該線程的類，核心策略會根據(jù)調(diào)度類選擇 CPU 執(zhí)行。默認(rèn)的核心策略中包含兩個(gè)線程類，分別是獨(dú)占的(Exclusive)和正常的(Normal)，前者會為線程保留整個(gè) CPU 資源，而后者會在多線程之間分享資源。

資源預(yù)估

默認(rèn)的核心策略中包含動態(tài)的 CPU 資源預(yù)估功能，它會使用以下的三個(gè)參數(shù)根據(jù)過去一段時(shí)間的負(fù)載和 CPU 使用情況調(diào)整當(dāng)前應(yīng)用程序申請的資源：

• 負(fù)載因子(Load Factor) — 當(dāng)運(yùn)行正常線程的所有 CPU 負(fù)載達(dá)到特定的閾值時(shí)，向仲裁者申請額外的 CPU;
• 時(shí)間間隔(Interval) — 用于預(yù)估占用資源的 CPU 采樣區(qū)間，默認(rèn)為過去的 50ms，這可以決定策略對負(fù)載變換的敏感程度;
• 滯后因子(hysteresis Factor) — 記錄每次提升負(fù)載前的資源利用率，并根據(jù)該利用率減少申請的 CPU 資源;

作為 Arachne 中的默認(rèn)策略，它提供的一定是相對簡單的、普適的模型，我們可以根據(jù)自己的需求調(diào)整策略中的三個(gè)參數(shù)，也可以實(shí)現(xiàn)其他的策略。

總結(jié)論文的最后在線程的創(chuàng)建、控制權(quán)轉(zhuǎn)移等常見的調(diào)度原語方面對比了 Arachne、std::thread、Go 和 uThreads 幾種具有相似功能的線程管理器，Arachne 在幾個(gè)方面都有不錯(cuò)的表現(xiàn)：

Benchmark	Arachne	std::thread	Go	uThreads
Thread Creation	217 ns	13329 ns	444 ns	6132 ns
One-Way Yield	93 ns	-	-	79 ns
Null Yield	12 ns	-	-	6 ns
Condition Notify	281 ns	4962 ns	483 ns	4976 ns
Signal	282 ns	-	-	-

表 1 - 調(diào)度原語的開銷對比

正如我們在文章中提到的，Arachne 與其他線程管理器使用了完全不同的設(shè)計(jì)思路，因?yàn)槲覀兊哪康氖浅浞掷?CPU 資源，所以應(yīng)用程序需要對資源有著更細(xì)粒度的掌握和控制，其他的線程管理器都會盡可能地屏蔽底層的實(shí)現(xiàn)細(xì)節(jié)，讓上層只關(guān)注內(nèi)部的一些邏輯，我們從軟件工程的角度也不能說誰對誰錯(cuò)，但是在真正追求極致的性能時(shí)，一定清楚對下一層甚至下兩層的信息，在線程調(diào)度器這個(gè)場景下就是 CPU 資源的詳細(xì)使用情況。

本文轉(zhuǎn)載自微信公眾號「 真沒什么邏輯」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系 真沒什么邏輯公眾號。