NUMA-Aware 執(zhí)行引擎論文解讀
最近翻 DuckDB 的執(zhí)行引擎相關(guān)的 PPT(Push-Based-Execution[1]) 時(shí)，發(fā)現(xiàn)了這篇論文：Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age[2]。印象中在執(zhí)行引擎相關(guān)的文章中看到他好幾次；且 NUMA 架構(gòu)對(duì)于現(xiàn)代數(shù)據(jù)庫(kù)架構(gòu)設(shè)計(jì)非常重要，但我對(duì)此了解尚淺，因此便找來(lái)讀一讀。
從題目中也可以看到，論文最主要關(guān)鍵詞有兩個(gè)：
NUMA-Aware
Morsel-Driven
據(jù)此，大致總結(jié)下論文的中心思想：
多核時(shí)代，由于部分 CPU 和部分內(nèi)存的綁定關(guān)系，CPU 訪問(wèn)內(nèi)存是不均勻（NUMA）的。也即，對(duì)于某一個(gè) CPU 核來(lái)說(shuō)，本機(jī)上一部分內(nèi)存訪問(wèn)延遲較低，另一部分內(nèi)存延遲要高。
傳統(tǒng)火山模型，使用 Exchange 算子來(lái)進(jìn)行并發(fā)。其他算子并不感知多線程，因此也就沒(méi)辦法就近內(nèi)存調(diào)度計(jì)算（硬件親和性）。也即，非 NUMA-local。
為了解決此問(wèn)題，論文在數(shù)據(jù)維度：對(duì)數(shù)據(jù)集進(jìn)行水平分片，一個(gè) NUMA-node 處理一個(gè)數(shù)據(jù)分片；對(duì)每個(gè)分片進(jìn)行垂直分段（Morsel），在 Morsel 粒度上進(jìn)行并發(fā)調(diào)度和搶占執(zhí)行。
在計(jì)算維度：為每個(gè) CPU 預(yù)分配一個(gè)線程，在調(diào)度時(shí)，每個(gè)線程只接受數(shù)據(jù)塊（Morsel）分配到本 NUMA-node 上的任務(wù)；當(dāng)線程間子任務(wù)的執(zhí)行進(jìn)度不均衡時(shí)，快線程會(huì)”竊取“本應(yīng)調(diào)度到其他線程的任務(wù)，從而保證一個(gè) Query 的多個(gè)子任務(wù)大約同時(shí)完成，而不會(huì)出現(xiàn)”長(zhǎng)尾“分片。
背景鋪墊
論文中出現(xiàn)了一些名詞，如果不了解其內(nèi)涵，可能很難對(duì)論文的一些關(guān)鍵設(shè)計(jì)點(diǎn)理解到位，因此這里對(duì)相關(guān)概念和背景做了一些鋪墊。
NUMA
NUMA，是 Non-Uniform Memory Access 的縮寫，即非一致性內(nèi)存訪問(wèn)架構(gòu)。傳統(tǒng) UMA （一致性訪存）架構(gòu)比較好理解，它也是我們通常以為的內(nèi)存訪問(wèn)模型——所有 CPU core 訪問(wèn)本機(jī)所有內(nèi)存的延遲是一致的（下圖源）：
但在多核（現(xiàn)在常用的服務(wù)器動(dòng)不動(dòng)就是 50+ core）時(shí)代，內(nèi)存訪問(wèn)總線會(huì)”爭(zhēng)用“非常嚴(yán)重，從而造成內(nèi)存延遲迅速增高。于是，便有了 NUMA 架構(gòu)——將單機(jī)內(nèi)存切分成幾塊，分別和一些 CPU 進(jìn)行綁定。一組綁定的 CPU 和內(nèi)存通常稱為一個(gè) NUMA-node 或者 NUMA socket。
上圖只是一個(gè)示意圖，通常一個(gè) NUMA-node 會(huì)有很多個(gè) CPU core，而非上圖中的一個(gè)。那么，本 NUMA-node 的訪問(wèn)就是 Local Access，對(duì)其他 NUMA-node 的內(nèi)存訪問(wèn)就是 Remote Access，后者通常要比前者慢幾倍。
上面代碼是通過(guò) numactl 命令查看的一個(gè)物理機(jī)的 NUMA 情況?？梢钥闯鲈撐锢頇C(jī)一共有 56 核，分為兩個(gè) NUMA-node，每個(gè) 28 核，每個(gè) NUMA-node 有 128G 內(nèi)存，local access 和 remote access 訪問(wèn)延遲比大概是 10: 21。
通常來(lái)說(shuō)，操作系統(tǒng)盡量將線程和其使用的內(nèi)存分配到同一個(gè) NUMA-node 中，尤其是只需要小內(nèi)存的線程。但對(duì)于數(shù)據(jù)庫(kù)這種遇到大內(nèi)存（buffer pool）的系統(tǒng)來(lái)說(shuō)，內(nèi)存分配很容易跨 ?NUMA-node，因此需要專門設(shè)計(jì)。
在分布式環(huán)境下，一個(gè)機(jī)器節(jié)點(diǎn)本質(zhì)上就是一組CPU + 一塊內(nèi)存的資源容器；而在單機(jī)上，一個(gè) NUMA-node 也是如此。因此，以看待分布式調(diào)度算法的思想（將計(jì)算調(diào)度到存儲(chǔ)旁）看待本論文，很多地方或可更易理解。
火山模型
火山模型是最傳統(tǒng)、經(jīng)典的一種數(shù)據(jù)庫(kù)執(zhí)行引擎模型。在火山模型中，SQL 語(yǔ)句會(huì)轉(zhuǎn)化成一棵算子樹(shù)，其中每個(gè)算子都實(shí)現(xiàn)了 open-next-close 接口；通過(guò)自上而下的（對(duì) next）樹(shù)形遞歸調(diào)用，完成數(shù)據(jù)的處理。
火山模型中的算子有個(gè)特點(diǎn)，就是不感知其所處理的數(shù)據(jù)在哪塊內(nèi)存、也不感知自己運(yùn)行在哪個(gè) CPU 上，甚至不感知是否為并行執(zhí)行。當(dāng)然，為了利用多核性能，可以擴(kuò)展火山模型，通過(guò) Exchange 算子來(lái)實(shí)現(xiàn)類似 partition→parallel processing→merge 的 shuffle 操作，從而將算子樹(shù)進(jìn)行并發(fā)執(zhí)行。Exchange 算子可以插入算子樹(shù)的任何一個(gè)位置，從而改變局部并發(fā)。除此之外，其他算子都不會(huì)感知并行運(yùn)行細(xì)節(jié)。這種模型的優(yōu)點(diǎn)在于，簡(jiǎn)潔優(yōu)雅、表達(dá)能力強(qiáng)。但在多核時(shí)代，這種模型顯然沒(méi)有照顧到 NUMA 架構(gòu)特點(diǎn)。
對(duì)于上述火山模型，我們通常將其執(zhí)行模式稱為基于拉（”pull-based“）的。因?yàn)槲覀兌紗?wèn)從算子樹(shù)的根節(jié)點(diǎn)要數(shù)據(jù)，而根節(jié)點(diǎn)會(huì)遞歸的向孩子節(jié)點(diǎn)要數(shù)據(jù)，直到葉子節(jié)點(diǎn)（通常是各種 scan 節(jié)點(diǎn)）。整體，就像從根節(jié)點(diǎn)往外”拉“數(shù)據(jù)一樣。
與基于拉的模式相對(duì)，我們還有基于推（”push-based“）的執(zhí)行模式。就像在代碼中將遞歸轉(zhuǎn)化為迭代一樣，push-base 就是直接從葉子節(jié)點(diǎn)開(kāi)始執(zhí)行，在算子執(zhí)行完生成新的數(shù)據(jù)后，會(huì)往數(shù)據(jù)下游算子（算子樹(shù)中的父節(jié)點(diǎn)）推數(shù)據(jù)。
這兩者最大的不同在于，pull-based 是不需要進(jìn)行算子級(jí)別的調(diào)度的，所有數(shù)據(jù)都是”需求倒逼生產(chǎn)“，下游一步步問(wèn)上游要；而 push-based 則需要一個(gè)全局調(diào)度器來(lái)協(xié)調(diào)上下游的數(shù)據(jù)生產(chǎn)消費(fèi)關(guān)系——在下游能夠接受數(shù)據(jù)時(shí)，將上游吐出來(lái)的數(shù)據(jù)推給下游。
Pipeline
在 push-based 的模式下，我們通常會(huì)將算子樹(shù)切分成多個(gè)線性的流水線（ Pipeline），并以 Pipeline （下圖中虛線部分）的粒度進(jìn)行執(zhí)行調(diào)度。每個(gè) pipeline 也可稱為 pipeline segment，即整個(gè)算子樹(shù)的一部分。
Pipeline 的切口處，我們通常稱之為 Pipeline Breaker——即 Pipeline 進(jìn)行不下去，要進(jìn)行切分了。如果你恰好對(duì) Spark 的執(zhí)行 Stage 劃分有所了解，就會(huì)發(fā)現(xiàn)他們?cè)硎且粯拥摹?Shuffle 處進(jìn)行切分。而 Join 處通常會(huì)發(fā)生 shuffle。
morsel
morsel 是本論文提出的一個(gè)類似”數(shù)據(jù)塊“的概念，可以理解為關(guān)系數(shù)據(jù)庫(kù)中的多個(gè)行（row）或者多個(gè)元組（tuple），這是本論文的最小調(diào)度和單元，對(duì)應(yīng)下文中相同顏色標(biāo)出的部分。
若想理解 morsel，可以對(duì)比 CPU 的時(shí)間片。只有將 CPU 切換成一塊塊大小合適的時(shí)間片段，我們才能更加方便的設(shè)計(jì)利用率高（更容易做均衡調(diào)度）、可搶占（單塊時(shí)間片完成后而不必等待整個(gè)任務(wù)完成，便可調(diào)入其他任務(wù)占用時(shí)間片）、帶優(yōu)先級(jí)（執(zhí)行新的時(shí)間片時(shí)，按優(yōu)先級(jí)選擇任務(wù)）的各種調(diào)度算法。
內(nèi)容概要
morsel 驅(qū)動(dòng)執(zhí)行
論文首先舉了 σ...(R) >< A σ...(S) >< B σ...(T) 的三張表進(jìn)行 inner join 的例子，其中 S 和 T 是小表。則在 Join 時(shí)對(duì)其 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í)行過(guò)程。
結(jié)合之前 Pipeline 的背景知識(shí)，可以推斷出該執(zhí)行計(jì)劃會(huì)被劃分為三個(gè) Pipeline，分別是 HashTable(T) 的構(gòu)建 、HashTable(S) 的構(gòu)建 Pipeline 和 R 的探測(cè)。下面分別來(lái)說(shuō)：
HashTable 的構(gòu)建。兩個(gè) HashTable 的構(gòu)建過(guò)程是類似的，以 HashTable(T) 為例，構(gòu)建過(guò)程又會(huì)分為兩個(gè)階段：
階段一（Phase 1）：將 T 的 scan 輸出按 morsel 粒度均勻分發(fā)給幾個(gè) CPU core 的 storage area，本質(zhì)上是 Partition 的過(guò)程。
階段二（Phase 2）：每個(gè) CPU core 對(duì)應(yīng)的線程去掃描被分派的數(shù)據(jù)分片（包含很多 morsel），構(gòu)建一個(gè)全局（跨線程）HashTable，本質(zhì)上是 Merge 的過(guò)程。
為了并行的對(duì)數(shù)據(jù)進(jìn)行處理，通常都會(huì)有個(gè)數(shù)據(jù)分片階段——按某種方式將一個(gè)輸入流變成多個(gè)輸入流。正如在 MapReduce 之前有個(gè) split 的過(guò)程。
第二個(gè)階段會(huì)涉及跨線程的數(shù)據(jù)寫入，因此需要對(duì) HashTable 這個(gè)跨線程的全局?jǐn)?shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)做一些優(yōu)化：
在階段一確定 HashTable 的大小，一次性預(yù)分配 HashTable，避免 HashTable 動(dòng)態(tài)增長(zhǎng)造成的
只將數(shù)據(jù)的指針插入 HashTable，避免跨線程的數(shù)據(jù)拷貝。
HashTable 使用無(wú)鎖結(jié)構(gòu)，降低多線程插入時(shí)爭(zhēng)用造成的性能下降。
HashTable 的探測(cè)。在 HashTable(T) 和 HashTable(S) 構(gòu)建完成后，就會(huì)開(kāi)始對(duì) R 表的探測(cè)。R 表在掃描后，其數(shù)據(jù)也會(huì)被分派到多個(gè) NUMA-node 上去，進(jìn)行并行的探測(cè)，探測(cè)完成后也會(huì)輸出到線程所在的 NUMA-local。
如果探測(cè)之后還有其他的算子，比如 Top、Filter、Limit 等等，也會(huì)被調(diào)度到 Probe 輸出所在 NUMA-node 上進(jìn)行執(zhí)行。
不同于火山模型，這些算子（比如上圖中的 HashJoin）要感知并行，并需要進(jìn)行同步。
關(guān)于 Dispatcher 的實(shí)現(xiàn)和一些具體算子的實(shí)現(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
題圖故事
本文來(lái)自我的小報(bào)童付費(fèi)專欄《系統(tǒng)日知錄》，專注分布式系統(tǒng)、存儲(chǔ)和數(shù)據(jù)庫(kù)，有圖數(shù)據(jù)庫(kù)、代碼解讀、優(yōu)質(zhì)英文播客翻譯、數(shù)據(jù)庫(kù)學(xué)習(xí)、論文解讀等等系列，歡迎喜歡我文章的朋友訂閱??專欄：https://xiaobot.net/p/system-thinking，你的支持對(duì)我持續(xù)創(chuàng)作優(yōu)質(zhì)文章非常重要。下面是當(dāng)前文章列表：
圖數(shù)據(jù)庫(kù)系列
圖數(shù)據(jù)庫(kù)資料匯總
Memgraph 系列（二）：可串行化實(shí)現(xiàn)
Memgraph 系列（一）：數(shù)據(jù)多版本管理
【圖數(shù)據(jù)庫(kù)系列四】與關(guān)系模型的“緣”與“爭(zhēng)”
【圖數(shù)據(jù)庫(kù)系列三】圖的表示與存儲(chǔ)
【圖數(shù)據(jù)庫(kù)系列二】 Cypher 初探
【圖數(shù)據(jù)庫(kù)系列一】屬性圖模型是啥、有啥不足???
數(shù)據(jù)庫(kù)
譯：數(shù)據(jù)庫(kù)五十年來(lái)研究趨勢(shì)
譯：數(shù)據(jù)庫(kù)中的代碼生成（Codegen in Databas...
Facebook Velox 運(yùn)行機(jī)制解析
譯：Factorization & Great Ideas from Database Theory
分布式系統(tǒng)架構(gòu)（二）—— Replica Placement
【好文薦讀】DuckDB 中的流水線構(gòu)建
譯：時(shí)下大火的向量數(shù)據(jù)庫(kù)，你了解多少？
數(shù)據(jù)處理的大一統(tǒng)——從 Shell 腳本到 SQL 引擎
存儲(chǔ)
存儲(chǔ)引擎概述和資料匯總???
譯：RocksDB 是如何工作的
RocksDB 優(yōu)化小解（二）：Prefix Seek 優(yōu)化
大規(guī)模系統(tǒng)中使用 RocksDB 的一些經(jīng)驗(yàn)
代碼&編程
影響我寫代碼的三個(gè) “Code”???
Folly 異步編程之 futures
關(guān)于接口和實(shí)現(xiàn)
C++ 私有函數(shù)的 override
ErrorCode 還是 Exception ？
Infra 面試之?dāng)?shù)據(jù)結(jié)構(gòu)（一）：阻塞隊(duì)列
數(shù)據(jù)結(jié)構(gòu)與算法（四）：遞歸和迭代
每天學(xué)點(diǎn)數(shù)據(jù)庫(kù)系列
【每天學(xué)點(diǎn)數(shù)據(jù)庫(kù)】Lecture #05：數(shù)據(jù)壓縮
【每天學(xué)點(diǎn)數(shù)據(jù)庫(kù)】Lecture #05：負(fù)載類型和存儲(chǔ)模型
【每天學(xué)點(diǎn)數(shù)據(jù)庫(kù)】Lecture #04：數(shù)據(jù)編碼
【每天學(xué)點(diǎn)數(shù)據(jù)庫(kù)】Lecture #04：日志構(gòu)型存儲(chǔ)
【每天學(xué)點(diǎn)數(shù)據(jù)庫(kù)】Lecture #03：Data Layout
【每天學(xué)點(diǎn)數(shù)據(jù)庫(kù)】Lecture #03: Database and OS
【每天學(xué)點(diǎn)數(shù)據(jù)庫(kù)】Lecture #03：存儲(chǔ)層次體系
【每天學(xué)點(diǎn)數(shù)據(jù)庫(kù)】Lecture #01：關(guān)系代數(shù)
【每天學(xué)點(diǎn)數(shù)據(jù)庫(kù)】Lecture #01：關(guān)系模型
【每天學(xué)點(diǎn)數(shù)據(jù)庫(kù)】Lecture #01：數(shù)據(jù)模型
雜談
數(shù)據(jù)庫(kù)面試的幾個(gè)常見(jiàn)誤區(qū) ??
生活工程學(xué)（一）：多輪次拆解??
系統(tǒng)中一些有趣的概念對(duì)
系統(tǒng)設(shè)計(jì)時(shí)的簡(jiǎn)潔和完備
工程經(jīng)驗(yàn)的周期
關(guān)于“名字”拿來(lái)
