這篇文章來自 SAP HANA 開發團隊，第一作者是 HANA 任務排程框架的主要開發者之一，不過他寫完這篇 paper 之後沒多久就跳去 Oracle 了。

很多我們熟悉的MPP系統排程方面都很粗糙，通常是所謂的靜態排程。比如，當前有N臺節點，每個節點有P個worker，就把整個任務切成N*P份。這種方法簡單粗暴，但現實世界的workload往往都是有skew的，效果可能差強人意。

本文介紹了 NUMA 的架構下如何實現 Adaptive 的任務排程，即，根據實際 Workload 的資源使用情況（主要是記憶體throughput和CPU），自動平衡各個 socket 上的負載，從而更有效的利用資源。為什麼標題中除了 task scheduling 還有 data placement 呢？這是因為很多工（比如scan）必須要放在資料所在的 socket 上，如果強行work stealing用其他socket去做，效果反而會下降，想真的做到平衡必須也要搬運資料才行。

基本概念

一張圖就可以說明白本文想做什麼事：Socket 1\2 的負載很高，我們透過 data replacement，

將 TBL2 從Socket 1 搬到 Socket 3 ，因為原本TBL2和TBL1都在吃 Socket 1 的資源

將 TBL3 拆分成 part1\2，拆一半給 Socket4，因為原本一個TBL3已經打滿了 Socket 2

將 TBL4 的 part1\2 合併成一個，因為 TBL4 基本沒啥負載

The Need For Adaptivity

文中把 Scan 分成 Scan IV （index vector） 和 Materialization （用 vid 取出對應的record資料） 兩個步驟，Scan IV 是 memory-intensive 的，而 Materialization 是 CPU-intensive 的。對於 memory-intensive 的 task，work stealing 不僅沒有卵用還可能會降低效能，因為 socket 之間的記憶體頻寬是有限的資源，一不小心還可能打滿對面 socket 的 memory controller。

作者又說了一通，不僅對於 Scan，Aggregation、Join 其實也都有 memory-intensive 的步驟，它們也一樣要 data placement 才能算的更快。

一句話總結下，要想負載均衡必須要搬資料，work stealing 沒有用。

跟蹤資源使用情況

文章首先把任務分成各種 Task Class，比如對於 Scan 運算元，他其中有兩個 Task 分別是 Scan IV 和 Scan Mat。 。對於每種 Task Class，我們觀察它memory throughput的歷史資料的指數平均值，以這個作為該 Task 的資源使用情況。

注意，所有 work stealing 的執行是不被統計的。我們想看的就是 task 本身的消耗。在我們的模型下 work stealing 應當被視作一個待最佳化的 bad case。

對 task class 的估計會被實時地彙總成 TBP （table partition） 和 TGP （table-group partition） 的資源消耗統計， 之後，一個後臺非同步 sample 執行緒又回每隔 100ms 彙總 socket 上的資源消耗統計。這些統計資料就是我們做 adaptive data placement 的依據。

上圖中列出了3種Task。RUH即Resource Utilization History （RUH），他記錄了資源消耗的歷史情況，包括 memory throughput （由 task 的估算 throughput 加總得到）和 CPU load （這裡僅僅用執行緒數表示）

上面說到，各種 task 的 memory throughput 是透過它的歷史 memory throughput 的指數平均數估算的，歷史的 memory throughput 是怎麼得到的呢？本文利用了 Intel 提供的硬體計數器，計數器前後數值的差值也就是當前這個core、當前這個時間片的 memory access 量，除以時間長度就得到了 throughput。

Adaptive Data Placement

負責資料遷移的模組稱為 Data Placer （DP），它是一個後臺非同步任務，每隔一段時間會啟動並檢查是否有什麼可以做的，比如 move 或 repartition。

DP 的目標是讓各個 socket 的負載更均衡（aka。 資源利用率更高），緩解單 socket 效能瓶頸；同時也要注意，不能因為 data placement 打滿記憶體頻寬。

DP 首先透過一系列的條件選出適合遷移的 TBP 或 TGP，稱之為 eligible RUH‘s owner。如果找不到，那就到此為止，下一次迴圈再看看。選擇 eligible 的過程如下：

下面這張表上是一些閾值之類的篩選條件：

下面這張圖是估算 move 或 repartition 能多大程度上改善不均衡：

具體演算法就不再說了，這邊寫的過於細節，有興趣的讀者請看paper。

Adaptive Task Stealing

這一節不是本文的核心工作，像是為了立意的完整性而補上的。之前說了那麼多 data placement 其實都是為了最佳化 scheduling，但是無論怎麼最佳化仍然還是會有 skew 的。這時候仍然需要 work stealing 來託底。

考慮到之前已經發現了一個fact：memory-intensive 的任務 work stealing 用處不大甚至可能會起到反效果，這裡作者嘗試去找一個 switch point，如果一個任務的 memory-intensive 程度大於這個點，那麼 work stealing 有效，否則無效。

聽起來似乎不難，但是這個 switch point 實際上很難界定，它和 workload 和硬體都有很大關係，文中只給出了一種基於試驗的測量方法（似乎沒有什麼實用價值）。

下面的圖中，橫軸 Power 表示乘法的次數，Power 越大代表 CPU-intensive 的程度越大、memory-intensive 的程度越小。可以看到，在圖中，三個配置下的最優 switch point （即綠線和藍線的交叉點）各不相同。