在現(xiàn)代數(shù)據(jù)庫管理系統(tǒng)（DBMS）中，并行執(zhí)行是實現(xiàn)高性能和高可用性的核心策略之一。它允許數(shù)據(jù)庫系統(tǒng)利用多核CPU和多個存儲設(shè)備，同時處理多個任務(wù)或單個復(fù)雜任務(wù)的多個部分，從而顯著提升數(shù)據(jù)處理能力。

并行執(zhí)行的好處

并行執(zhí)行為數(shù)據(jù)庫系統(tǒng)帶來了多方面的顯著優(yōu)勢。

性能提升

• 吞吐量（Throughput） ：系統(tǒng)在單位時間內(nèi)可以處理更多查詢和數(shù)據(jù)，即每秒運行的查詢數(shù)量更多。
• 延遲（Latency） ：單個查詢的執(zhí)行時間可以大幅縮短，因為任務(wù)可以同時進行。這對于需要快速響應(yīng)的應(yīng)用程序尤為重要。
• 響應(yīng)性與可用性提升 ：并行執(zhí)行使得系統(tǒng)即使在某個線程因等待磁盤I/O而阻塞時，其他線程也能繼續(xù)運行，處理內(nèi)存中的數(shù)據(jù)，從而保持系統(tǒng)的活躍和響應(yīng)速度。
• 潛在的總擁有成本（TCO）降低 ：通過更有效地利用硬件資源，系統(tǒng)可以在更少的硬件上完成更多工作，減少硬件采購、軟件許可、部署勞動力和能源消耗等總成本。這意味著購買擁有更多核心的新機器時，數(shù)據(jù)庫系統(tǒng)可以充分利用其優(yōu)勢。

并行數(shù)據(jù)庫與分布式數(shù)據(jù)庫的區(qū)別

雖然并行數(shù)據(jù)庫和分布式數(shù)據(jù)庫都旨在通過跨多個資源分布數(shù)據(jù)庫來提高性能，但它們之間存在關(guān)鍵的區(qū)別，本課程主要關(guān)注并行數(shù)據(jù)庫。

并行數(shù)據(jù)庫（Parallel DBMS）

• 資源物理位置 ：資源（如CPU、磁盤）彼此物理距離非常近。例如，同一機架單元內(nèi)的機器，或具有多個CPU插槽的服務(wù)器。
• 通信方式 ：資源之間通過高速、高帶寬的內(nèi)部互連（如CPU插槽之間的互連）進行通信。
• 通信假設(shè) ：通信被認(rèn)為是快速、廉價且可靠的，消息不會丟失或亂序。

分布式數(shù)據(jù)庫（Distributed DBMS）

• 資源物理位置 ：資源可以彼此相距很遠。例如，在同一數(shù)據(jù)中心的不同機器，或位于全球不同地區(qū)的服務(wù)器。
• 通信方式 ：資源之間通過較慢且不可靠的通信通道（如公共廣域網(wǎng)）進行通信。
• 通信假設(shè) ：通信成本和潛在問題（如消息丟失、延遲）必須被考慮和處理。

對于應(yīng)用程序而言 ：無論是并行數(shù)據(jù)庫還是分布式數(shù)據(jù)庫，都應(yīng)向應(yīng)用程序呈現(xiàn)為單個邏輯數(shù)據(jù)庫實例。這意味著SQL查詢在任何一種系統(tǒng)上都應(yīng)該產(chǎn)生相同的結(jié)果，并且無需重寫應(yīng)用程序或SQL語句。

數(shù)據(jù)庫進程模型

DBMS的進程模型定義了系統(tǒng)如何組織其內(nèi)部結(jié)構(gòu)，以支持來自多用戶應(yīng)用程序的并發(fā)請求。一個“工作者（worker）”是DBMS中負(fù)責(zé)執(zhí)行任務(wù)并返回結(jié)果的組件，它可以是進程或線程。

歷史上和當(dāng)前存在三種主要的進程模型。

方法一：每個工作者一個進程（Process per DBMS Worker）

這是最基本的方法，每個工作者都是一個獨立的操作系統(tǒng)（OS）進程。

優(yōu)點 ：如果某個工作者進程崩潰，通常不會導(dǎo)致整個系統(tǒng)崩潰，提高了系統(tǒng)的彈性。在早期（1970-1990年代），由于缺乏標(biāo)準(zhǔn)的線程API，這種方法在不同操作系統(tǒng)上的可移植性更好，因為fork和join是通用的OS原語。

缺點/挑戰(zhàn)

• 進程開銷大 ：OS進程的創(chuàng)建和上下文切換開銷（context switch overhead）比線程高得多。
• 共享數(shù)據(jù)復(fù)雜 ：每個進程通常有獨立的內(nèi)存地址空間，若要共享全局?jǐn)?shù)據(jù)結(jié)構(gòu)（如緩沖池），需要操作系統(tǒng)提供的共享內(nèi)存機制（shared memory）來協(xié)調(diào)，這增加了復(fù)雜性。

示例：IBM DB2、Postgres（早期版本）、Oracle等老舊系統(tǒng)。

方法二：進程池（Process Pool）

這是“每個工作者一個進程”方法的延伸。系統(tǒng)維護一個預(yù)先創(chuàng)建好的工作者進程池，當(dāng)有新的連接或請求到來時，調(diào)度器（dispatcher）從池中分配一個空閑進程來處理。

優(yōu)點 ：避免了為每個新連接即時fork進程的開銷。池中的進程可以更好地協(xié)同工作，實現(xiàn)一定程度的查詢并行性。

缺點 ：仍然依賴OS調(diào)度器和共享內(nèi)存機制。可能對CPU緩存局部性（cache locality）不利，因為一個連接的后續(xù)請求可能由不同的進程處理。

示例 ：IBM DB2、Postgres（2015年切換到此模型）。

方法三：每個工作者一個線程（Thread per DBMS Worker）

這是現(xiàn)代DBMS最常見的做法，整個數(shù)據(jù)庫系統(tǒng)運行在一個單獨的OS進程中，而工作者由進程內(nèi)部的多個線程表示。

優(yōu)點

• 開銷小 ：線程的創(chuàng)建和上下文切換開銷遠低于進程。
• 共享數(shù)據(jù)簡便 ：所有線程共享同一地址空間，簡化了全局?jǐn)?shù)據(jù)結(jié)構(gòu)（如緩沖池）的訪問和管理，無需復(fù)雜的共享內(nèi)存機制。
• DBMS更精細(xì)的調(diào)度控制 ：DBMS可以自己管理線程調(diào)度，對任務(wù)的執(zhí)行有更細(xì)粒度的控制，因為它可以全局了解所有任務(wù)和可用資源。

缺點 ：一個線程的崩潰可能導(dǎo)致整個DBMS進程的崩潰，因此要求代碼質(zhì)量極高。

示例 ：IBM DB2、Microsoft SQL Server、MySQL、Oracle（2014年）。

重要提示 ： 采用多線程架構(gòu)并不意味著DBMS自動支持查詢內(nèi)并行（intra-query parallelism） 。例如，MySQL 5.7是一個多線程DBMS，但其本身不能將單個查詢分解為多個線程并行執(zhí)行（此功能可能在8.0版本中得到改進）。

查詢內(nèi)并行（Intra-Query Parallelism）

查詢內(nèi)并行旨在通過并行執(zhí)行單個查詢的操作來提高其性能，這對于長時間運行的分析型查詢（OLAP）特別有用。

查詢計劃中的操作符可以被視為生產(chǎn)者/消費者模型：一個操作符（生產(chǎn)者）生成數(shù)據(jù)，并將其傳遞給其上方的操作符（消費者）。并行化算法適用于所有關(guān)系型操作符。

有三種主要的查詢內(nèi)并行方法。

方法一：算子內(nèi)并行 / 水平并行（Intra-Operator / Horizontal Parallelism）

概念 ：將單個操作符分解成多個獨立的執(zhí)行片段（fragments），每個片段在不同的線程上并行地處理輸入數(shù)據(jù)的不同子集。例如，對于一個掃描操作符，可以有多個掃描實例在不同線程上并行掃描表的不同部分。

核心機制：Exchange Operator

• DBMS會在查詢計劃中人工插入一種特殊的“交換操作符（Exchange Operator）”來協(xié)調(diào)和合并子操作符的結(jié)果。
• 發(fā)明者 ：由發(fā)明 Volcano 迭代器模型和 B+ 樹書籍的 Goetz Graefe 提出。
• 類型 ：

Gather（匯聚） ：將來自多個工作者的結(jié)果合并成一個單一的輸出流。這是最常見的類型，因為查詢的最終結(jié)果通常需要匯聚成一個單一的輸出返回給應(yīng)用程序。

Repartition（重新分區(qū)） ：根據(jù)數(shù)據(jù)的值重新組織多個輸入流，并將它們分發(fā)到多個輸出流。這允許DBMS在數(shù)據(jù)已經(jīng)按某種方式分區(qū)后，根據(jù)需要重新分區(qū)數(shù)據(jù)。

Distribute（分發(fā)） ：將單個輸入流拆分成多個輸出流，通常用于將數(shù)據(jù)分發(fā)給多個工作者進行并行處理。例如，在 Grace Hash Join 的構(gòu)建階段，可以將單個輸入流分發(fā)到不同的哈希桶。

方法二：算子間并行 / 垂直并行 / 流水線并行（Inter-Operator / Vertical / Pipelined Parallelism）

概念 ：不同的操作符在獨立的線程中同時運行，通過“流水線”的方式將數(shù)據(jù)從一個階段直接傳遞到下一個階段，而無需中間結(jié)果的物化（materialization）。

工作原理 ：下游操作符（消費者）在收到上游操作符（生產(chǎn)者）發(fā)出的元組后立即開始處理，形成一個數(shù)據(jù)流動的管道。例如，一個 Join 操作符的輸出可以立即作為 Projection 操作符的輸入。

應(yīng)用場景 ：這種方法在流處理系統(tǒng)（如Spark Streaming、Apache Flink）中廣泛使用，也適用于數(shù)據(jù)庫系統(tǒng)。

方法三：Bushy 并行（Bushy Parallelism）

概念 ：可以視為算子間并行的一種擴展。它允許工作者同時執(zhí)行查詢計劃中不同分支（或“灌木狀”結(jié)構(gòu)）的多個操作符。

特點 ：通常在查詢計劃包含多個獨立的Join操作時體現(xiàn)，每個 Join 可以由不同的工作者并行執(zhí)行，然后通過 Exchange 操作符匯聚結(jié)果。

以上三種并行方法并非互斥， DBMS 可以根據(jù)查詢、硬件和數(shù)據(jù)特點，組合使用這些技術(shù)以達到最佳性能。

I/O 并行：解決磁盤瓶頸

如果磁盤 I/O 成為主要瓶頸，那么僅僅增加 CPU 核心和線程并不能提升性能，甚至可能因為多個工作者同時爭搶磁盤資源而使情況惡化。因此，為了充分利用并行計算能力，需要實現(xiàn) I/O 并行。

I/O 并行化的基本思想是將數(shù)據(jù)庫系統(tǒng)的數(shù)據(jù)和文件分散存儲在多個存儲設(shè)備上。

多磁盤并行（Multi-Disk Parallelism）

概念 ：通過操作系統(tǒng)或硬件配置，將DBMS的文件存儲在多個物理存儲設(shè)備上。

實現(xiàn)方式 ：可以通過存儲設(shè)備（Storage Appliances）或 RAID（Redundant Array of Independent Disks，獨立磁盤冗余陣列） 配置來實現(xiàn)。

RAID

• RAID 0 (Stripping - 條帶化) ：數(shù)據(jù)被分成塊，并以輪詢（round-robin）方式寫入不同的磁盤。這提高了I/O吞吐量，但沒有冗余。
• RAID 1 (Mirroring - 鏡像) ：每個數(shù)據(jù)塊都在至少兩個磁盤上保存完整的副本，提供數(shù)據(jù)冗余。讀取性能可以并行化，但寫入成本較高。

透明性 ：對DBMS是透明的。DBMS感知不到底層是多個磁盤，因此它無法基于底層磁盤布局來優(yōu)化查詢計劃。

數(shù)據(jù)庫分區(qū)（Database Partitioning）

概念 ：DBMS主動將數(shù)據(jù)分解成不相交的子集，并將其分配給不同的磁盤位置。與RAID不同， DBMS知道數(shù)據(jù)的分區(qū)方式和物理位置 。

優(yōu)點 ：緩沖池管理器（Buffer Pool Manager）知道頁的磁盤位置，因此可以智能地進行I/O調(diào)度。

理想狀態(tài) ：分區(qū)對于應(yīng)用程序應(yīng)該是透明的。應(yīng)用程序訪問邏輯表，無需關(guān)心數(shù)據(jù)具體存儲在哪里。

兩種主要分區(qū)方法

• 垂直分區(qū)（Vertical Partitioning）

概念 ：將表的屬性（列）存儲在不同的物理位置（如不同的文件或磁盤卷）。類似于列式存儲，但可能不具備列式存儲的所有優(yōu)化（如壓縮、列式查詢執(zhí)行）。

實現(xiàn) ：需要存儲元組ID信息，以便在查詢時將不同列的數(shù)據(jù)重新組合成完整的記錄。

適用場景 ：當(dāng)查詢通常只訪問表的少數(shù)幾列時，可以減少I/O量。

• 水平分區(qū)（Horizontal Partitioning）

概念 ：將表的元組（行）根據(jù)某個分區(qū)鍵（partitioning key）分成不相交的段，并存儲在不同的分區(qū)中 。這通常被稱為 分片（sharding） ，盡管在并行數(shù)據(jù)庫中更多是指單機內(nèi)的數(shù)據(jù)分布。

實現(xiàn)方式 ：可以通過哈希分區(qū)（Hash Partitioning）、范圍分區(qū)（Range Partitioning）或謂詞分區(qū)（Predicate Partitioning）等方式實現(xiàn)。

優(yōu)勢 ：當(dāng)查詢只需要訪問特定元組時，可以直接定位到包含該元組的分區(qū)進行I/O操作。多個工作者可以同時并行地操作不同的分區(qū)，從而提高I/O效率。

關(guān)于索引（B+樹）的影響 ：在水平分區(qū)下， DBMS知道每個元組屬于哪個分區(qū) 。因此，當(dāng)進行索引查找（如B+樹）時，系統(tǒng)可以根據(jù)查詢條件中的分區(qū)鍵，直接確定目標(biāo)元組可能存在的分區(qū)，然后只在該分區(qū)（對應(yīng)的磁盤）上進行查找。這意味著 不需要進行“系統(tǒng)內(nèi)查找所有分區(qū)”的操作 ，而是可以精準(zhǔn)定位。B+樹等索引在并行環(huán)境中面臨的挑戰(zhàn)更多是并發(fā)控制方面（如閂鎖搶占和耦合 latch crabbing/coupling），這屬于并行執(zhí)行中的協(xié)調(diào)開銷，而不是分區(qū)本身導(dǎo)致了索引查找的低效。