負載均衡相關的原理、場景和框架

我們描述負載均衡的系列文章一共三篇，第一篇是框架部分，即本文，主要描述了負載均衡相關的原理、場景和框架。后面的兩篇是對均衡代碼的情景分析，通過對load balance、task placement和active upmigration幾個典型的負載均衡來呈現(xiàn)其實現(xiàn)細節(jié)，稍后發(fā)布，敬請期待。

本文出現(xiàn)的內(nèi)核代碼來自Linux5.4.28，如果有興趣，讀者可以配合代碼閱讀本文。

一、什么是負載均衡

1、什么是CPU負載（load）

CPU負載是一個很容易和CPU利用率（utility）混淆的概念。CPU利用率是CPU忙閑的比例，例如在一個周期為1000ms的窗口中觀察CPU的情況，如果500ms的時間在執(zhí)行任務，500ms的時間處于idle狀態(tài)，那么在這個窗口中CPU的利用率是50%。

在CPU利用率沒有達到100%的時候，利用率基本上等于負載，一旦當CPU利用率達到了100%的時候，利用率其實是無法給出CPU負載的狀況，因為大家的利用率都是100%，利用率相等，但是并不意味著CPUs的負載也是相等的，因為這時候不同CPU上runqueue中等待執(zhí)行的任務數(shù)目不同，直覺上runque上掛著10任務的CPU承壓比掛著5個任務的CPU的負載要更重一些。因此，早期的CPU負載是使用runqueue深度來描述的。

顯然，僅僅使用runqueue深度來表示CPU負載是一個很粗略的概念，我們可以舉一個簡單的例子：當前CPU A和CPU B上都掛了1個任務，但是A上掛的任務是一個重載任務，而B上掛的是一個經(jīng)常sleep的輕載任務，那么僅僅從runqueue深度來描述CPU負載就有失偏頗了。因此，現(xiàn)代調(diào)度器往往使用CPU runqueue上task load之和來表示CPU load。這樣，對CPU負載的跟蹤就變成了對任務負載的跟蹤。

3.8版本的linux內(nèi)核引入了PELT算法來跟蹤每一個sched entity的負載，把負載跟蹤的算法從per-CPU進化到per-entity。PELT算法不但能知道CPU的負載，而且知道負載來自哪一個調(diào)度實體，從而可以更精準的進行負載均衡。

2、什么是均衡

對于負載均衡而言，并不是把整個系統(tǒng)的負載平均的分配到系統(tǒng)中的各個CPU上。實際上，我們還是必須要考慮系統(tǒng)中各個CPU的算力，讓CPU獲得和其算力匹配的負載。例如在一個6個小核+2個大核的系統(tǒng)中，整個系統(tǒng)如果有800的負載，那么每個CPU上分配100的負載其實是不均衡的，因為大核CPU可以提供更強的算力。

什么是CPU算力（capacity），所謂算力就是描述CPU的能夠提供的計算能力。在同樣的頻率下，一個微架構是A77的CPU顯然算力要大于A57的CPU。如果CPU的微架構都是一樣的，那么一個最大頻率是2.2GHz的CPU算力肯定是大于最大頻率是1.1GHz的CPU。因此，確定了微架構和最大頻率，一個CPU的算力就基本確定了。Cpufreq系統(tǒng)會根據(jù)當前的CPU util來調(diào)節(jié)CPU當前的運行頻率，但這并不能改變CPU算力。只有當CPU最大運行頻率發(fā)生變化的時候（例如觸發(fā)溫控，限制了該CPU的最大頻率），CPU的算力才會隨之變化。

此外，本文主要描述CFS任務的均衡（RT的均衡不考慮負載，是在另外的維度），因此在考慮CPU算力的時候，需要把CPU用于執(zhí)行rt和irq的算力去掉，使用該CPU可用于CFS的算力。因此，CFS任務均衡中使用的CPU算力其實一個不斷變化的值，需要經(jīng)常更新。為了讓CPU算力和任務負載可以對比，實際上我們采用了歸一化的方式，即系統(tǒng)中處理能力最強的CPU運行在最高頻率的算力是1024，其他的CPU算力根據(jù)微架構和運行頻率響應的調(diào)整其算力。

有了任務負載就可以得到CPU負載，配合系統(tǒng)中各個CPU的算力，看起來我們就可以完成負載均衡的工作，然而事情沒有那么簡單，當負載不均衡的時候，任務需要在CPU之間遷移，不同形態(tài)的遷移會有不同的開銷。例如一個任務在小核cluster上的CPU之間的遷移所帶來的性能開銷一定是小于任務從小核cluster的CPU遷移到大核cluster的開銷。因此，為了更好的執(zhí)行負載均衡，我們需要構建和CPU拓撲相關的數(shù)據(jù)結構，也就是調(diào)度域和調(diào)度組的概念。

3、調(diào)度域（sched domain）和調(diào)度組（sched group）

負載均衡的復雜性主要和復雜的系統(tǒng)拓撲有關。由于當前CPU很忙，我們把之前運行在該CPU上的一個任務遷移到新的CPU上的時候，如果遷移到新的CPU是和原來的CPU在不同的cluster中，性能會受影響（因為會cache flush）。

但是對于超線程架構，cpu共享cache，這時候超線程之間的任務遷移將不會有特別明顯的性能影響。NUMA上任務遷移的影響又不同，我們應該盡量避免不同NUMA node之間的任務遷移，除非NUMA node之間的均衡達到非常嚴重的程度。

總之，一個好的負載均衡算法必須適配各種cpu拓撲結構。為了解決這些問題，linux內(nèi)核引入了sched_domain的概念。

內(nèi)核中struct sched_domain來描述調(diào)度域，其主要的成員如下：

一旦形成了調(diào)度域，那么負載均衡就被限制在了該調(diào)度域內(nèi)，在該調(diào)度域內(nèi)進行均衡的時候不考慮系統(tǒng)中其他調(diào)度域的CPU負載情況，只考慮該調(diào)度域內(nèi)的sched group之間的負載是否均衡。對于base domain，其所屬的sched group中只有一個cpu，對于更高level的sched domain，其所屬的sched group中可能會有多個cpu core。內(nèi)核中struct sched_group來描述調(diào)度組，其主要的成員如下：

上面的描述過于枯燥，我們后面會使用一個具體的例子來描述負載如何在各個level的sched domain上進行均衡的，不過在此之前，我們先看看負載均衡的整體軟件架構。

二、負載均衡的軟件架構

負載均衡的整體軟件結構圖如下：

負載均衡模塊主要分兩個軟件層次：核心負載均衡模塊和class-specific均衡模塊。內(nèi)核對不同的類型的任務有不同的均衡策略，普通的CFS（complete fair schedule）任務和RT、Deadline任務處理方式是不同的，由于篇幅原因，本文主要討論CFS任務的負載均衡。

為了更好的進行CFS任務的均衡，系統(tǒng)需要跟蹤任務負載和CPU負載。跟蹤任務負載是主要有兩個原因：

（1）判斷該任務是否適合當前CPU算力。

（2）如果判定需要均衡，那么需要在CPU之間遷移多少的任務才能達到平衡？有了任務負載跟蹤模塊，這個問題就比較好回答了。

對CPU負載的跟蹤不僅要考慮每一個CPU的負載，還要匯聚cluster上所有負載，方便計算cluster之間負載的不均衡狀況。

為了更好的進行高效的均衡，我們還需要構建調(diào)度域的層級結構（sched domain hierarchy），圖中顯示的是二級結構。手機場景多半是二級結構，支持NUMA的服務器場景可能會形成更復雜的結構。通過DTS和CPU topo子系統(tǒng)，我們可以構建sched domain層級結構，用于具體的均衡算法。

有了上面描述的基礎設施，那么什么時候進行負載均衡呢？這主要和調(diào)度事件相關，當發(fā)生任務喚醒、任務創(chuàng)建、tick到來等調(diào)度事件的時候，我們可以檢查當前系統(tǒng)的不均衡情況，并酌情進行任務遷移，以便讓系統(tǒng)負載處于平衡狀態(tài)。

三、如何做負載均衡

1、一個CPU拓撲示例

我們以一個4小核+4大核的處理器來描述CPU的domain和group：

在上面的結構中，sched domain是分成兩個level，base domain稱為MC domain（multi core domain），頂層的domain稱為DIE domain。頂層的DIE domain覆蓋了系統(tǒng)中所有的CPU，小核cluster的MC domain包括所有小核cluster中的cpu，同理，大核cluster的MC domain包括所有大核cluster中的cpu。

對于小核MC domain而言，其所屬的sched group有四個，cpu0、1、2、3分別形成一個sched group，形成了MC domain的sched group環(huán)形鏈表。

不同CPU的MC domain的環(huán)形鏈表首元素（即sched domain中的groups成員指向的那個sched group）是不同的，對于cpu0的MC domain，其groups環(huán)形鏈表的順序是0-1-2-3，對于cpu1的MC domain，其groups環(huán)形鏈表的順序是1-2-3-0，以此類推。大核MC domain也是類似，這里不再贅述。

對于非base domain而言，其sched group有多個cpu，覆蓋其child domain的所有cpu。例如上面圖例中的DIE domain，它有兩個child domain，分別是大核domain和小核domian，因此，DIE domain的groups環(huán)形鏈表有兩個元素，分別是小核group和大核group。

不同CPU的DIE domain的環(huán)形鏈表首元素（即鏈表頭）是不同的，對于cpu0的DIE domain，其groups環(huán)形鏈表的順序是（0,1,2,3）--（4,5,6,7），對于cpu6的MC domain，其groups環(huán)形鏈表的順序是（4,5,6,7）--（0,1,2,3），以此類推。

為了減少鎖的競爭，每一個cpu都有自己的MC domain、DIE domain以及sched group，并且形成了sched domain之間的層級結構，sched group的環(huán)形鏈表結構。

2、負載均衡的基本過程

負載均衡不是一個全局CPU之間的均衡，實際上那樣做也不現(xiàn)實，當系統(tǒng)的CPU數(shù)量較大的時候，很難一次性的完成所有CPU之間的均衡，這也是提出sched domain的原因之一。

當一個CPU上進行負載均衡的時候，我們總是從base domain開始（對于上面的例子，base domain就是MC domain），檢查其所屬sched group之間（即各個cpu之間）的負載均衡情況，如果有不均衡情況，那么會在該cpu所屬cluster之間進行遷移，以便維護cluster內(nèi)各個cpu core的任務負載均衡。有了各個CPU上的負載統(tǒng)計以及CPU的算力信息，我們很容易知道MC domain上的不均衡情況。

為了讓算法更加簡單，Linux內(nèi)核的負載均衡算法只允許CPU拉任務，這樣，MC domain的均衡大致需要下面幾個步驟：

（1）找到MC domain中最繁忙的sched group；

（2）找到最繁忙sched group中最繁忙的CPU（對于MC domain而言，這一步不存在，畢竟其sched group只有一個cpu）；

（3）從選中的那個繁忙的cpu上拉取任務，具體拉取多少的任務到本CPU runqueue上是和不均衡的程度相關，越是不均衡，拉取的任務越多。

完成MC domain均衡之后，繼續(xù)沿著sched domain層級結構向上檢查，進入DIE domain，在這個level的domain上，我們?nèi)匀粰z查其所屬sched group之間（即各個cluster之間）的負載均衡情況，如果有不均衡的情況，那么會進行inter-cluster的任務遷移。基本方法和MC domain類似，只不過在計算均衡的時候，DIE domain不再考慮單個CPU的負載和算力，它考慮的是：

（1）該sched group的負載，即sched group中所有CPU負載之和；

（2）該sched group的算力，即sched group中所有CPU算力之和；

2、其他需要考慮的事項

之所以要進行負載均衡主要是為了系統(tǒng)整體的throughput，避免出現(xiàn)一核有難，七核圍觀的狀況。然而，進行負載均衡本身需要額外的算力開銷，為了降低開銷，我們?yōu)椴煌琹evel的sched domain定義了時間間隔，不能太密集的進行負載均衡。之外，我們還定義了不均衡的門限值，也就是說domain的group之間如果有較小的不均衡，我們也是可以允許的，超過了門限值才發(fā)起負載均衡的操作。很顯然，越高level的sched domain其不均衡的threashhold越高，越高level的均衡會帶來更大的性能開銷。

在引入異構計算系統(tǒng)之后，任務在placement的時候可以有所選擇。如果負載比較輕，或者該任務對延遲要求不高，我們可以放置在小核CPU執(zhí)行，如果負載比較重或者該該任務和用戶體驗相關，那么我們傾向于讓它在算力更高的CPU上執(zhí)行。為了應對這種狀況，內(nèi)核引入了misfit task的概念。一旦任務被標記了misfit task，那么負載均衡算法要考慮及時的將該任務進行upmigration，從而讓重載任務盡快完成，或者提升該任務的執(zhí)行速度，從而提升用戶體驗。

除了性能，負載均衡也會帶來功耗的收益。例如系統(tǒng)有4個CPU，共計8個進入執(zhí)行態(tài)的任務。這些任務在4個CPU上的排布有兩種選擇：

（1）全部放到一個CPU上；

（2）每個CPU runqueue掛2個任務。

負載均衡算法會讓任務均布，從而帶來功耗的收益。雖然方案一中有三個CPU是處于idle狀態(tài)的，但是那個繁忙CPU運行在更高的頻率上。而方案二中，由于任務均布，CPU處于較低的頻率運行，功耗會比方案一更低。

四、負載均衡場景分析

1、整體的場景描述

在linux內(nèi)核中，為了讓任務均衡的分布在系統(tǒng)的所有CPU上，我們主要考慮下面三個場景：

（1）負載均衡（load balance）。通過搬移cpu runqueue上的任務，讓各個CPU上的負載匹配CPU算力。

（2）任務放置（task placement）。當阻塞的任務被喚醒的時候，確定該任務應該放置在那個CPU上執(zhí)行。

（3）主動均衡（active upmigration）。當一個低算力CPU的runqueue中出現(xiàn)misfit task的時候，如果該任務持續(xù)執(zhí)行，那么負載均衡無能為力，因為它只負責遷移runnable狀態(tài)的任務。這種場景下，active upmigration可以把當前正在運行的misfit task向上遷移到算力更高的CPU上去。

2、Task placement

任務放置主要發(fā)生在：

（1）喚醒一個新fork的線程；

（2）Exec一個線程的時候；

（3）喚醒一個阻塞的進程。

在上面的三個場景中都會調(diào)用select_task_rq來為task選擇一個適合的CPU core。

3、Load balance

Load balance主要有三種：

（1）在tick中觸發(fā)load balance。我們稱之tick load balance或者periodic load balance。具體的代碼執(zhí)行路徑是：

（2）調(diào)度器在pick next的時候，當前cfs runque中沒有runnable，只能執(zhí)行idle線程，讓CPU進入idle狀態(tài)。我們稱之new idle load balance。具體的代碼執(zhí)行路徑是：

（3）其他的cpu已經(jīng)進入idle，本CPU任務太重，需要通過ipi將其idle的cpu喚醒來進行負載均衡。我們稱之idle load banlance，具體的代碼執(zhí)行路徑是：

如果沒有dynamic tick特性，那么其實不需要進行idle load balance，因為tick會喚醒處于idle的cpu，從而周期性tick就可以覆蓋這個場景。

4、Active upmigration

主動遷移是Load balance的一種特殊場景。在負載均衡中，只要運用適當?shù)耐綑C制（持有一個或者多個rq lock），runnable的任務可以在各個CPU runqueue之間移動，然而running的任務是例外，它不掛在CPU runqueue中，load balance無法覆蓋。為了能夠遷移running狀態(tài)的任務，內(nèi)核提供了Active upmigration的方法（利用stop machine調(diào)度類）。