最近翻 DuckDB 的執(zhí)行引擎相關(guān)的 PPT(Push-Based-Execution[1]) 時，發(fā)現(xiàn)了這篇論文：Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age[2]。印象中在執(zhí)行引擎相關(guān)的文章中看到他好幾次；且 NUMA 架構(gòu)對于現(xiàn)代數(shù)據(jù)庫架構(gòu)設(shè)計非常重要，但我對此了解尚淺，因此便找來讀一讀。

從題目中也可以看到，論文最主要關(guān)鍵詞有兩個：

1. NUMA-Aware

2. Morsel-Driven

據(jù)此，大致總結(jié)下論文的中心思想：

1. 多核時代，由于部分 CPU 和部分內(nèi)存的綁定關(guān)系，CPU 訪問內(nèi)存是不均勻（NUMA）的。也即，對于某一個 CPU 核來說，本機(jī)上一部分內(nèi)存訪問延遲較低，另一部分內(nèi)存延遲要高。

2. 傳統(tǒng)火山模型，使用 Exchange 算子來進(jìn)行并發(fā)。其他算子并不感知多線程，因此也就沒辦法就近內(nèi)存調(diào)度計算（硬件親和性）。也即，非 NUMA-local。

3. 為了解決此問題，論文在數(shù)據(jù)維度：對數(shù)據(jù)集進(jìn)行水平分片，一個 NUMA-node 處理一個數(shù)據(jù)分片；對每個分片進(jìn)行垂直分段（Morsel），在 Morsel 粒度上進(jìn)行并發(fā)調(diào)度和搶占執(zhí)行。

4. 在計算維度：為每個 CPU 預(yù)分配一個線程，在調(diào)度時，每個線程只接受數(shù)據(jù)塊（Morsel）分配到本 NUMA-node 上的任務(wù)；當(dāng)線程間子任務(wù)的執(zhí)行進(jìn)度不均衡時，快線程會”竊取“本應(yīng)調(diào)度到其他線程的任務(wù)，從而保證一個 Query 的多個子任務(wù)大約同時完成，而不會出現(xiàn)”長尾“分片。

背景鋪墊

論文中出現(xiàn)了一些名詞，如果不了解其內(nèi)涵，可能很難對論文的一些關(guān)鍵設(shè)計點理解到位，因此這里對相關(guān)概念和背景做了一些鋪墊。

NUMA

NUMA，是 Non-Uniform Memory Access 的縮寫，即非一致性內(nèi)存訪問架構(gòu)。傳統(tǒng) UMA （一致性訪存）架構(gòu)比較好理解，它也是我們通常以為的內(nèi)存訪問模型——所有 CPU core 訪問本機(jī)所有內(nèi)存的延遲是一致的（下圖源）：

但在多核（現(xiàn)在常用的服務(wù)器動不動就是 50+ core）時代，內(nèi)存訪問總線會”爭用“非常嚴(yán)重，從而造成內(nèi)存延遲迅速增高。于是，便有了 NUMA 架構(gòu)——將單機(jī)內(nèi)存切分成幾塊，分別和一些 CPU 進(jìn)行綁定。一組綁定的 CPU 和內(nèi)存通常稱為一個 NUMA-node 或者 NUMA socket。

上圖只是一個示意圖，通常一個 NUMA-node 會有很多個 CPU core，而非上圖中的一個。那么，本 NUMA-node 的訪問就是 Local Access，對其他 NUMA-node 的內(nèi)存訪問就是 Remote Access，后者通常要比前者慢幾倍。

上面代碼是通過 numactl 命令查看的一個物理機(jī)的 NUMA 情況?？梢钥闯鲈撐锢頇C(jī)一共有 56 核，分為兩個 NUMA-node，每個 28 核，每個 NUMA-node 有 128G 內(nèi)存，local access 和 remote access 訪問延遲比大概是 10: 21。

通常來說，操作系統(tǒng)盡量將線程和其使用的內(nèi)存分配到同一個 NUMA-node 中，尤其是只需要小內(nèi)存的線程。但對于數(shù)據(jù)庫這種遇到大內(nèi)存（buffer pool）的系統(tǒng)來說，內(nèi)存分配很容易跨 ?NUMA-node，因此需要專門設(shè)計。

在分布式環(huán)境下，一個機(jī)器節(jié)點本質(zhì)上就是一組CPU + 一塊內(nèi)存的資源容器；而在單機(jī)上，一個 NUMA-node 也是如此。因此，以看待分布式調(diào)度算法的思想（將計算調(diào)度到存儲旁）看待本論文，很多地方或可更易理解。

火山模型

火山模型是最傳統(tǒng)、經(jīng)典的一種數(shù)據(jù)庫執(zhí)行引擎模型。在火山模型中，SQL 語句會轉(zhuǎn)化成一棵算子樹，其中每個算子都實現(xiàn)了 open-next-close 接口；通過自上而下的（對 next）樹形遞歸調(diào)用，完成數(shù)據(jù)的處理。

火山模型中的算子有個特點，就是不感知其所處理的數(shù)據(jù)在哪塊內(nèi)存、也不感知自己運行在哪個 CPU 上，甚至不感知是否為并行執(zhí)行。當(dāng)然，為了利用多核性能，可以擴(kuò)展火山模型，通過 Exchange 算子來實現(xiàn)類似 partition→parallel processing→merge 的 shuffle 操作，從而將算子樹進(jìn)行并發(fā)執(zhí)行。Exchange 算子可以插入算子樹的任何一個位置，從而改變局部并發(fā)。除此之外，其他算子都不會感知并行運行細(xì)節(jié)。這種模型的優(yōu)點在于，簡潔優(yōu)雅、表達(dá)能力強(qiáng)。但在多核時代，這種模型顯然沒有照顧到 NUMA 架構(gòu)特點。

對于上述火山模型，我們通常將其執(zhí)行模式稱為基于拉（”pull-based“）的。因為我們都問從算子樹的根節(jié)點要數(shù)據(jù)，而根節(jié)點會遞歸的向孩子節(jié)點要數(shù)據(jù)，直到葉子節(jié)點（通常是各種 scan 節(jié)點）。整體，就像從根節(jié)點往外”拉“數(shù)據(jù)一樣。

與基于拉的模式相對，我們還有基于推（”push-based“）的執(zhí)行模式。就像在代碼中將遞歸轉(zhuǎn)化為迭代一樣，push-base 就是直接從葉子節(jié)點開始執(zhí)行，在算子執(zhí)行完生成新的數(shù)據(jù)后，會往數(shù)據(jù)下游算子（算子樹中的父節(jié)點）推數(shù)據(jù)。

這兩者最大的不同在于，pull-based 是不需要進(jìn)行算子級別的調(diào)度的，所有數(shù)據(jù)都是”需求倒逼生產(chǎn)“，下游一步步問上游要；而 push-based 則需要一個全局調(diào)度器來協(xié)調(diào)上下游的數(shù)據(jù)生產(chǎn)消費關(guān)系——在下游能夠接受數(shù)據(jù)時，將上游吐出來的數(shù)據(jù)推給下游。

Pipeline

在 push-based 的模式下，我們通常會將算子樹切分成多個線性的流水線（ Pipeline），并以 Pipeline （下圖中虛線部分）的粒度進(jìn)行執(zhí)行調(diào)度。每個 pipeline 也可稱為 pipeline segment，即整個算子樹的一部分。

Pipeline 的切口處，我們通常稱之為 Pipeline Breaker——即 Pipeline 進(jìn)行不下去，要進(jìn)行切分了。如果你恰好對 Spark 的執(zhí)行 Stage 劃分有所了解，就會發(fā)現(xiàn)他們原理是一樣的——在 Shuffle 處進(jìn)行切分。而 Join 處通常會發(fā)生 shuffle。

morsel

morsel 是本論文提出的一個類似”數(shù)據(jù)塊“的概念，可以理解為關(guān)系數(shù)據(jù)庫中的多個行（row）或者多個元組（tuple），這是本論文的最小調(diào)度和單元，對應(yīng)下文中相同顏色標(biāo)出的部分。

若想理解 morsel，可以對比 CPU 的時間片。只有將 CPU 切換成一塊塊大小合適的時間片段，我們才能更加方便的設(shè)計利用率高（更容易做均衡調(diào)度）、可搶占（單塊時間片完成后而不必等待整個任務(wù)完成，便可調(diào)入其他任務(wù)占用時間片）、帶優(yōu)先級（執(zhí)行新的時間片時，按優(yōu)先級選擇任務(wù)）的各種調(diào)度算法。

內(nèi)容概要

morsel 驅(qū)動執(zhí)行

論文首先舉了 σ...(R) >< A σ...(S) >< B σ...(T) 的三張表進(jìn)行 inner join 的例子，其中 S 和 T 是小表。則在 Join 時對其 scan 后進(jìn)行 Build 構(gòu)建 HashTable；R 是大表，則在 S 和 T 的 HashTable 構(gòu)建完成后，掃描以 Probe。將 HashJoin 切成 HashBuild（構(gòu)建 HashTable）和 HashProbe（利用 HashTable 進(jìn)行匹配），是經(jīng)典的 HashJoin 的執(zhí)行過程。

結(jié)合之前 Pipeline 的背景知識，可以推斷出該執(zhí)行計劃會被劃分為三個 Pipeline，分別是 HashTable(T) 的構(gòu)建 、HashTable(S) 的構(gòu)建 Pipeline 和 R 的探測。下面分別來說：

HashTable 的構(gòu)建。兩個 HashTable 的構(gòu)建過程是類似的，以 HashTable(T) 為例，構(gòu)建過程又會分為兩個階段：

1. 階段一（Phase 1）：將 T 的 scan 輸出按 morsel 粒度均勻分發(fā)給幾個 CPU core 的 storage area，本質(zhì)上是 Partition 的過程。

2. 階段二（Phase 2）：每個 CPU core 對應(yīng)的線程去掃描被分派的數(shù)據(jù)分片（包含很多 morsel），構(gòu)建一個全局（跨線程）HashTable，本質(zhì)上是 Merge 的過程。

為了并行的對數(shù)據(jù)進(jìn)行處理，通常都會有個數(shù)據(jù)分片階段——按某種方式將一個輸入流變成多個輸入流。正如在 MapReduce 之前有個 split 的過程。

第二個階段會涉及跨線程的數(shù)據(jù)寫入，因此需要對 HashTable 這個跨線程的全局?jǐn)?shù)據(jù)結(jié)構(gòu)的實現(xiàn)做一些優(yōu)化：

1. 在階段一確定 HashTable 的大小，一次性預(yù)分配 HashTable，避免 HashTable 動態(tài)增長造成的

2. 只將數(shù)據(jù)的指針插入 HashTable，避免跨線程的數(shù)據(jù)拷貝。

3. HashTable 使用無鎖結(jié)構(gòu)，降低多線程插入時爭用造成的性能下降。

HashTable 的探測。在 HashTable(T) 和 HashTable(S) 構(gòu)建完成后，就會開始對 R 表的探測。R 表在掃描后，其數(shù)據(jù)也會被分派到多個 NUMA-node 上去，進(jìn)行并行的探測，探測完成后也會輸出到線程所在的 NUMA-local。

如果探測之后還有其他的算子，比如 Top、Filter、Limit 等等，也會被調(diào)度到 Probe 輸出所在 NUMA-node 上進(jìn)行執(zhí)行。

不同于火山模型，這些算子（比如上圖中的 HashJoin）要感知并行，并需要進(jìn)行同步。

關(guān)于 Dispatcher 的實現(xiàn)和一些具體算子的實現(xiàn)，就留待下篇了。

參考資料

[1]

Push-Based-Execution: https://dsdsd.da.cwi.nl/slides/dsdsd-duckdb-push-based-execution.pdf

[2]

Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age: https://15721.courses.cs.cmu.edu/spring2016/papers/p743-leis.pdf

題圖故事

本文來自我的小報童付費專欄《系統(tǒng)日知錄》，專注分布式系統(tǒng)、存儲和數(shù)據(jù)庫，有圖數(shù)據(jù)庫、代碼解讀、優(yōu)質(zhì)英文播客翻譯、數(shù)據(jù)庫學(xué)習(xí)、論文解讀等等系列，歡迎喜歡我文章的朋友訂閱??專欄：https://xiaobot.net/p/system-thinking，你的支持對我持續(xù)創(chuàng)作優(yōu)質(zhì)文章非常重要。下面是當(dāng)前文章列表：

圖數(shù)據(jù)庫系列

• 圖數(shù)據(jù)庫資料匯總

• Memgraph 系列（二）：可串行化實現(xiàn)

• Memgraph 系列（一）：數(shù)據(jù)多版本管理

• 【圖數(shù)據(jù)庫系列四】與關(guān)系模型的“緣”與“爭”

• 【圖數(shù)據(jù)庫系列三】圖的表示與存儲

• 【圖數(shù)據(jù)庫系列二】 Cypher 初探

• 【圖數(shù)據(jù)庫系列一】屬性圖模型是啥、有啥不足???

數(shù)據(jù)庫

• 譯：數(shù)據(jù)庫五十年來研究趨勢

• 譯：數(shù)據(jù)庫中的代碼生成（Codegen in Databas...

• Facebook Velox 運行機(jī)制解析

• 譯：Factorization & Great Ideas from Database Theory

• 分布式系統(tǒng)架構(gòu)（二）—— Replica Placement

• 【好文薦讀】DuckDB 中的流水線構(gòu)建

• 譯：時下大火的向量數(shù)據(jù)庫，你了解多少？

• 數(shù)據(jù)處理的大一統(tǒng)——從 Shell 腳本到 SQL 引擎

存儲

• 存儲引擎概述和資料匯總???

• 譯：RocksDB 是如何工作的

• RocksDB 優(yōu)化小解（二）：Prefix Seek 優(yōu)化

• 大規(guī)模系統(tǒng)中使用 RocksDB 的一些經(jīng)驗

代碼&編程

• 影響我寫代碼的三個 “Code”???

• Folly 異步編程之 futures

• 關(guān)于接口和實現(xiàn)

• C++ 私有函數(shù)的 override

• ErrorCode 還是 Exception ？

• Infra 面試之?dāng)?shù)據(jù)結(jié)構(gòu)（一）：阻塞隊列

• 數(shù)據(jù)結(jié)構(gòu)與算法（四）：遞歸和迭代

每天學(xué)點數(shù)據(jù)庫系列

• 【每天學(xué)點數(shù)據(jù)庫】Lecture #05：數(shù)據(jù)壓縮

• 【每天學(xué)點數(shù)據(jù)庫】Lecture #05：負(fù)載類型和存儲模型

• 【每天學(xué)點數(shù)據(jù)庫】Lecture #04：數(shù)據(jù)編碼

• 【每天學(xué)點數(shù)據(jù)庫】Lecture #04：日志構(gòu)型存儲

• 【每天學(xué)點數(shù)據(jù)庫】Lecture #03：Data Layout

• 【每天學(xué)點數(shù)據(jù)庫】Lecture #03: Database and OS

• 【每天學(xué)點數(shù)據(jù)庫】Lecture #03：存儲層次體系

• 【每天學(xué)點數(shù)據(jù)庫】Lecture #01：關(guān)系代數(shù)

• 【每天學(xué)點數(shù)據(jù)庫】Lecture #01：關(guān)系模型

• 【每天學(xué)點數(shù)據(jù)庫】Lecture #01：數(shù)據(jù)模型

雜談

• 數(shù)據(jù)庫面試的幾個常見誤區(qū) ??

• 生活工程學(xué)（一）：多輪次拆解??

• 系統(tǒng)中一些有趣的概念對

• 系統(tǒng)設(shè)計時的簡潔和完備

• 工程經(jīng)驗的周期

• 關(guān)于“名字”拿來