1. 概述

ClickHouse是一個完全面向列式的分布式數據庫。數據通過列存儲，在查詢過程中，數據通過數組來處理(向量或者列)。當進行查詢時，操作被轉發到數組上，而不是在特定的值上。因此被稱為”向量化查詢執行”，相對于實際的數據處理成本，向量化處理具有更低的轉發成本。

這個設計思路并不是新的思路理念。歷史可以追溯到APL編程語言時代：A+, J, K, and Q。數組編程廣泛用于科學數據處理領域。而在關系型數據庫中：也應用了向量化系統。

在加速查詢處理上，有兩種的方法：向量化查詢執行和運行時代碼生成。為每種查詢類型都進行代碼生成，去除所有的間接和動態轉發處理。這些方法并不比其他方法好，當多個操作一起執行時，運行時代碼生成會更好，可以充分累用CPU執行單元和Pipeline管道。

向量化查詢執行實用性并不那么高，因為它涉及到臨時向量，必須寫到緩存中，并讀取回來。如果臨時數據并不適合L2緩存，它可能是一個問題。但是向量化查詢執行更容易利用CPU的SIMD能力。一個研究論文顯示將兩個方法結合到一起效果會更好。ClickHouse主要使用向量化查詢執行和有限的運行時代碼生成支持(僅GROUP BY內部循環第一階段被編譯)。

列

為了表示內存中的列(列的 chunks)，IColumn將被使用。這個接口提供了一些輔助方法來實現不同的關系操作符。幾乎所有的操作符都是非更改的：他們不能更改原有的列，但是創建一個新的更新的列。例如，IColumn::filter方法接受一個過濾器字節掩碼，同時創建一個新的過濾列。它被用在WHERE和HAVING的關系操作符上。額外的示例：IColumn::permute方法支持ORDER BY，IColumn::cut方法支持LIMIT等。

不同的IColumn實現(ColumnUInt8,ColumnString等)負責列的內存布局。<code>內存布局通常是一個連續的數組</code>。對于列的整型來說，它是一個連續的數組，如std::vector。對于String和Array列,這個是2個vectors:一個是所有的數組元素,連續放置,另一個是偏移量(offsets),位于每個數組的起始端。也有ColumnConst用于在內存中存儲一個值,但是它看起來像一個列。

數據域

然而, 它也可能工作在單獨的值上面。為了表示一個單獨的值。數據域使用.Fieldis 這是一個UInt64,Int64,Float64,StringandArray可區分的集合。IColumn 有operator[]方法來獲得n-th值作為一個數據域，insert[] 方法追加一個數據域到一個列的末尾。這些方法不是特別高效，因為他們需要處理臨時的數據域對象，它代表一個單獨的值。這是一個最高效的方法,例如insertFrom, insertRangeFrom等。

對于一個表，一個特定的數據類型，數據域沒有足夠的信息。例如 ,UInt8,UInt16,UInt32, 和 UInt64都用 UInt64表示。

抽象滲漏法則

IColumn有方法用于通用的關系型數據轉換，但是它并不能滿足所有需求。例如，ColumnUInt64沒有方法來計算2個列的加和，ColumnString沒有方法用于運行子字符串的搜索。一些進程是在IColumn之外實現的。

列中的不同函數能夠以一個通用的方式來實現，使用IColumn方法來抽取數據域值，或者在特定的方法下使用數據的內部內存布局在特定的IColumn上實現。為了完成這個，函數將被轉換成一個特定的IColumn類型，直接在內部進行處理。例如，ColumnUInt64有一個getData方法，將返回一個內存數組的引用，然后一個單獨的進程讀取或者直接填充這個數組。事實上，我們有一個抽象滲漏法則來允許不同進程的專用化。

數據類型

IDataType 負責序列化和反序列化: 讀寫這個列的值或者以二進制或文本的方式的值.IDataType 直接與表中的數據類型一致。例如，有DataTypeUInt32,DataTypeDateTime,DataTypeString等。

IDataType和IColumnare 互相是松耦合的。不同的數據類型能夠在內存中表示，通過相同的IColumn 實現.。例如,DataTypeUInt32和DataTypeDateTime都是通過ColumnUInt32或者ColumnConstUInt32來表示。另外，相同的數據類型通過不同的IColumn實現來表示. 例如,DataTypeUInt8 能夠通過ColumnUInt8或者ColumnConstUInt8.來表示。

IDataType 僅存儲元數據。例如，DataTypeUInt8 根本不保存任何數據 (除了 vptr) ，同時DataTypeFixedString 保存justN(確定的字符串大小)。

IDataType 對于不同的數據格式都有協助方法。示例是有些方法可以序列化一個值, 序列化一個值到 JSON，序列化一個值到 XML 格式。沒有直接的數據格式一一對應。例如，不同的數據格式Pretty和TabSeparated 能夠使用相同的serializeTextEscaped協助方法，在IDataType接口中。

數據塊

一個數據塊是一個容器，代表了內存中一個表的子集。它也是三元組的集合:(IColumn,IDataType,columnname). 在查詢執行過程中, 數據通過數據塊來處理. 如果你有一個數據塊， 我們有數據(在IColumn對象中), 我們有這個數據的類型(在IDataType中) 告訴我們怎樣處理此列，同時我們有此列名稱 (或者是原有列名, 或者是人工命名，得到計算的臨時結果)。

在一個數據塊中，當我們計算跨列某個函數時, 我們添加另外的帶有結果的列到數據塊中, 我們并不修改這個列，因為這些操作都是非變更的。然后，不需要的列將從數據塊中刪除，但不是修改。這個對于消除子表達式是便捷的。

數據塊為了每個處理的數據 Chunk 創建的。 對于相同的計算類型，列名稱和類型對于不同的數據塊將保持一致, 只有列數據保持變化。這樣有利于更好地從數據塊頭拆分數據，因為小的數據塊大小將有高的臨時字符串開銷，當拷貝 shared_ptrs 和 column names時。

數據塊流

數據塊流用于處理數據。我們使用數據塊的數據流從某處讀取數據，執行數據轉換或者寫入數據到某處。IBlockInputStream 有一個read方法獲取下一個數據塊。IBlockOutputStream 有一個write方法發送數據塊到某處。

數據流負責：

讀寫一個表。當讀寫數據塊時，此表將返回一個數據流。

實現數據格式。例如，如果你想要輸出數據以Pretty的格式到一個終端時。你將創建一個數據塊輸出流，然后格式化這個數據塊。

執行數據轉換。你有BlockInputStream 同時 想要創建一個過濾數據流。你創建FilterBlockInputStream，初始化它。然后當你從 FilterBlockInputStream拉取一個數據塊時，

將從數據流中獲得到一個數據塊，，過濾它，然后返回已經過濾的數據塊給你。查詢執行的 Pipeline 將展示這個方式。

有一些更加綜合的轉換。例如，當你從AggregatingBlockInputStream拉取數據時，它將從數據源上讀取所有的數據，聚合它，然后為你返回一個匯總數據流。另一個示例：UnionBlockInputStream接收很多輸入數據源和一些線程。它啟動了多個線程，從多個數據源中并行讀取數據。

數據塊流使用“pull” 的方式來控制數據流：當你從第一個數據流中拉取一個數據塊時，它從嵌套的數據流中拉取所需要的數據塊，整個執行 pipeline 將正常工作。其實“pull” 和 “push”都不是最佳方案，因為流控是隱式的，限制了不同特性的實現，如多個查詢的并行執行(一起合并多個 pipeline)。此限制是協程或者運行互相等待的外部線程。我們也能夠更多的可能性，如果我們進行顯式的流控：如果我們定位這個邏輯，從一個計算單元傳遞數據到外部的一個計算單元。

查詢執行流水線將在每個步驟創建臨時數據。我們將保持數據塊大小要足夠小，因此臨時數據要適合CPU緩存。假設，讀寫臨時數據幾乎是自由的，相對于其他計算來說。我們可以考慮一個替代方案，融合多個操作在 pipeline 中，讓 pipeline 盡可能小，刪除盡可能多的臨時數據。這個可以是一個優勢，也可能是個劣勢。例如，一個拆分 pipeline 將容易實現緩存中間數據，從類似的查詢中偷取中間數據，然后對于類似查詢，合并 pipeline。

格式

數據格式用數據塊流來實現。有種“顯示性”格式僅適用于數據輸出到客戶端，例如 Pretty 格式, 它僅提供 IBlockOutputStream。有輸入輸出格式，例如 TabSeparated 或JSONEachRow 。

也有行數據流: IRowInputStream和 IRowOutputStream. 他們允許你按照行來推/拉數據, 而不是通過數據塊. 他們僅被用于簡化面向行格式的實現。封裝器BlockInputStreamFromRowInputStream 和BlockOutputStreamFromRowOutputStream 允許你轉換面向行的數據流到面向數據塊的數據流。

I/O

對于面向字節的輸入/輸出。有 ReadBuffer 和 WriteBuffer 抽象類. 他們被用于替代C++ iostream。 不用擔心：每個成熟的 C++ 工程都用更優的類庫.

ReadBuffer 和 WriteBuffer 是一個連續的Buffer，游標指向Buffer的位置. 具體實現可能有或沒有內存。有個虛方法來用如下數據填充Buffer填充。 (對于ReadBuffer) 或者刷新Buffer到某處 (對于 WriteBuffer). 虛方法很少被調用。

Implementations of ReadBuffer/WriteBuffer 的實現被用于文件，文件描述和網絡套接字的處理，如實現壓縮 (CompressedWriteBuffer 用另外的 WriteBuffer 來初始化，在寫數據之前執行壓縮），或者用于其他目的 – 名稱ConcatReadBuffer, LimitReadBuffer, 和HashingWriteBuffer 等。

Read/WriteBuffers 僅用于處理字節，帶有格式化的輸入/輸出 (例如, 以decimal的方式寫入一個數字), 有一些函數是來自ReadHelpers 和WriteHelpers 頭文件的。
讓我們看一下當你想以Json的格式寫入結果集到標準輸出時發生了什么。你有一個結果集準備從IBlockInputStream獲取。你創建了 WriteBufferFromFileDescriptor(STDOUT_FILENO) 寫入字節到標準輸出. 你創建JSONRowOutputStream, 用 WriteBuffer來初始化, 寫入行到標準輸出。你在行輸出流之上創建 數據塊輸出流BlockOutputStreamFromRowOutputStream, 用IBlockOutputStream顯示它. 然后調用 copyData從IBlockInputStream 到 IBlockOutputStream來傳輸數據. 從內部來看, JSONRowOutputStream 將寫入不同的 JSON分隔符，調用 IDataType::serializeTextJSON 方法 引用到IColumn ，同時行數作為參數。然后，IDataType::serializeTextJSON將從 WriteHelpers.h調用一個方法：例如, 對于數字類型用writeText， 對于字符串類型用writeJSONString。

表

表通過IStorage接口來表示.對此接口不同的實現成為不同的表引擎. 例如 StorageMergeTree, StorageMemory, 等，這些類的實例是表。最重要的IStorage 方法是讀和寫操作. 也有alter, rename, drop, 等操作. 讀方法接受如下的參數：從表中讀取的列集合, AST 查詢, 返回需要的數據流的數量. 它返回一個或多個 IBlockInputStream 對象和有關數據處理階段的信息，在查詢的過程中在表引擎中完成。在大多數情況下，read方法負責從表中讀取特定的列，不進行后續的7數據處理。所有的進一步數據處理通過查詢中斷器來完成，這個在IStorage處理范圍之外。但是也有一些例外： - AST 查詢被傳遞到read方法，表引擎使用它來衍生對索引的使用， 同時從一個表中讀取少量數據. - 有時表引擎能夠處理數據到一個特定的階段。例如, StorageDistributed 能夠發送一個查詢到遠程服務器，讓他們處理數據到一個階段，即來自不同遠程服務器的數據能夠被合并，同時返回預處理后數據 查詢中斷器隨即結束對數據的處理。
表的read方法能夠返回多個IBlockInputStream 對象允許并行處理數據. 這些多個數據塊輸入流能夠從一個表中并行讀取數據. 然后你能夠用不同的轉換來封裝這些數據流(例如表達式評估，數據過濾) 能夠被單獨計算，同時在它們之上創建一個UnionBlockInputStream, 從多個數據流中并行讀取。
也有一些TableFunction. 有一些函數返回臨時的``IStorage 對象，用在查詢的 FROM 語句中.
為了快速建立一個印象，怎樣實現你自己的表引擎，如StorageMemory或StorageTinyLog。
作為read方法的結果, IStorage 返回 QueryProcessingStage – 此信息將返回哪個查詢部分已經在Storage中被計算. 當前，我們僅有非常粗粒度的信息。對于存儲來說，沒有方法說“我已經處理了Where條件中的表達式部分，對于此數據范圍” 。我們需要工作在其上。
解析器
一個查詢通過手寫的遞歸解析器被解析。例如， ParserSelectQuery遞歸調用如下的解析，對于不同的查詢部分。解析器創建了一個AST. 這個AST通過節點來表示，它是一個IAST實例。
由于歷史原因，解析器生成并沒有被使用。
中斷器
中斷器負責從一個AST上創建查詢執行Pipeline。有一些簡單的中斷器，例如 InterpreterExistsQuery和InterpreterDropQuery, 或者更復雜一些的 InterpreterSelectQuery. 此查詢執行pipeline是數據塊輸入個輸出流的結合體。例如，中斷SELECT 查詢的結果是IBlockInputStream 讀取結果集； INSERT 查詢的結果是 IBlockOutputStream 為了插入而寫入數據；and the result of interpreting the中斷 INSERT SELECT 查詢的結果是在第一次讀取時，返回一個空結果集, 但是同時從SELECT到INSERT拷貝數據。
InterpreterSelectQuery 使用了ExpressionAnalyzer和ExpressionActions 機制來查詢分析和轉換。 這是一個基于規則的查詢優。ExpressionAnalyzer 是有點亂的，應該被重寫: 不同的查詢轉換和優化應該被提取到不同的類，來允許模塊化的轉化和查詢。
函數
有一些普通函數和聚合函數。 對于聚合函數，請查看下一個章節。
普通函數并不能改變行的數量 – 他們單獨處理每個行。事實上，對于每個行，函數不能被調用，但是對于數據塊的數據可實現向量化查詢執行。
有一些 混合函數, 例如blockSize, rowNumberInBlock, 和runningAccumulate, 拓展了數據塊處理，違反了行的獨立性。
ClickHouse 有強類型，因此隱式類型轉換不能執行。如果函數不支持一個特定的類型綁定，異常將會拋出。但是函數能夠工作在很多不同的類型關聯。例如， plus 函數 (實現了 + 操作符) 能夠工作在任意的數字類型關聯：UInt8 + Float32, UInt16 + Int8, 等。一些變種函數能夠接收任意數量的參數，如concat 函數。
聚合函數
聚合函數是狀態函數。 他們積累傳遞的值到某個狀態, 允許你從這個狀態獲得結果。他們用IAggregateFunction來管理。狀態可以很簡單 (對于 AggregateFunctionCount 的狀態是一個單UInt64值) 或者相當復雜 (AggregateFunctionUniqCombined 的狀態是與線性數組相關, 一個哈希表， 一個 HyperLogLog 概率性數據結構)。
為了處理多個狀態，當執行一個高基數 GROUP BY 查詢, 狀態被分配在Arena中(一個內存池), 或者他們能夠以任意合適的內存分片被分配. 狀態可以有一個非細碎的構造器和析構器：例如， 復雜的聚合狀態能夠自己分配額外的內存，這塊需要注意，對于創建和銷毀狀態，同時傳遞他們的所屬關系，追蹤是誰和什么時候將銷毀這個狀態。聚合狀態能夠序列化和反序列化來跨網絡傳遞，在執行分布式查詢期間，或者如果沒有足夠的內存情況下，將他們寫入到磁盤. 他們甚至能夠存儲到表內，DataTypeAggregateFunction 允許增量聚合數據。

對于聚合函數狀態，序列化的數據格式目前不是版本化的。如果聚合狀態僅是臨時存儲，那是沒問題的。但是對于增量聚合，我們有AggregatingMergeTreetable 引擎，同時很多用戶已經在生產環境中使用他們了。這就是為什么我們應該增加向后兼容的支持，未來當為任意的聚合函數更改序列化格式時。

服務器

服務器實現了不同的接口：

• 對于任意的外部客戶端暴露一個HTTP接口 
• 對于本地客戶端暴露一個TCP 接口，在分布式查詢執行時，用于跨服務器通信 
• 一個接口用于傳輸同步數據 

從內部來講，這是一個基本的多線程服務器，沒有攜程, fibers, 等。服務器并沒有為高頻率短查詢來設計，而是為了處理低頻率的復雜查詢， 這兩種方式處理的數據量是不同的。對于查詢執行，服務器初始化上下文類，包括數據庫列表，用戶，訪問權限，設置，集群，處理列表，查詢日志，等。這個上下文環境被中斷器使用。對于服務器的TCP協議，我們維護了向前兼容和向后兼容：老客戶端能訪問新服務器，新客戶端能訪問老服務器。但是我們不想一直維護它們, 未來一年我們將停止對老版本的支持。對于外部應用，我們推薦使用 HTTP 接口，因為它比較簡單易用。TCP 協議與內部數據結構有很多關聯耦合：它使用一個內部結構來傳遞數據塊，使用自定義的幀來用于壓縮。 對于此協議我們沒有發布一個 C 的庫，因為它需要連接大部分 ClickHouse 的代碼庫, 這么做不實際。

分布式查詢執行

在一個集群設置中的服務器大部分是獨立的。你能夠在一個或所有的服務器上創建一個分布式表。此分布式表本身不存儲數據—在集群的多個節點上，僅提供一個"視圖"到所有的本地表。當你從分布式表進行查詢時，它重寫這個查詢，根據負載均衡的設置，選擇遠程節點，發送查詢給他們。分布式表請求遠程服務器來處理一個查詢到一個階段，此階段從不同的服務器中繼結果后進行合并。然后接收結果后合并這些結果。分布式表嘗試分布盡可能多的工作到遠程服務器，不能跨網絡發送太多的中繼數據。
當你進行 IN 或 JOIN 子查詢時，情況變得更加復雜一些，每個子查詢都使用一個分布式表。我們有不同的策略來執行這些查詢。對于分布式查詢執行，沒有一個全局的查詢規劃。每個節點有自己的本地查詢規劃作為任務的一部分。我們僅有一個簡化的一步分布式查詢執行：我們為遠程節點發送查詢，然后合并結果集。但是對于高基數的GROUP BY高難度查詢是并不可行的，或者大量臨時數據的 JOIN 查詢。ClickHouse并不支持這種查詢方式，我們需要進一步開發它。

合并樹

合并樹(MergeTree)是存儲引擎的族，通過主鍵來支持索引. 主鍵可以是列或表達式的任意 tuple。在MergeTree表中的數據被存儲在 “parts” 中. 每一部分按照主鍵順序存儲數據 (數據通過主鍵 tuple 來排序). 所有的表的列都在各自的column.bin文件中保存。 此文件由壓縮的數據塊組成。每個數據塊大小從64 KB 到 1 MB，依賴于平均值的大小。數據塊由列值組成，按順序連續放置。對于每一列，列值在同一個順序上 (順序通過主鍵來定義), 因此，對于對應的列，當你通過多列迭代以后來獲得值。
主鍵自身是"稀疏的"。它不定位到每個行 ，但是僅是一些數據范圍。 對于每個N-th行， 一個單獨的primary.idx 文件有主鍵的值, N 被稱為 index_granularity(通常情況下, N = 8192). 對于每個列, 我們有column.mrk 文件 ，帶有 “marks”標簽，對于數據文件中的每個N-th行，它是一個偏移量 。每個標簽都成成對兒出現的：文件中的偏移量到壓縮數據塊的起始端，解壓縮數據塊的偏移量到數據的起始端。 通常情況下，壓縮的數據塊通過"marks"標簽來對齊，解壓縮的數據塊的偏移量是0。對于primary.idx的數據通常主流在存儲中，對于column.mrk文件的數據放在緩存中。
當我們從MergeTree引擎中讀取數據時，我們看到了 primary.idx 數據和定位了可能包含請求數據的范圍， 然后進一步看column.mrk 數據，和計算偏移量從哪開始讀取這些范圍。因為稀疏性, 超額的數據可能被讀取。 ClickHouse 并不適合高負載的點狀查詢，因為帶有索引粒度行的整個范圍必須被讀取, 整個壓縮數據塊必須被解壓縮。我們構建的結構是索引稀疏的，因為我們必須在單臺服務器上維護數萬億條數據， 對于索引來說沒有顯著的內存消耗。因為主鍵是稀疏的，它并不是唯一的：在 INSERT時，它不能夠檢查鍵的存在。在一個表內，相同的鍵你可以有多個行。
當你插入大量數據進入MergeTree時，數據通過主鍵順序來篩選，形成一個新的部分。為了保持數據塊數是低位的，有一些背景線程周期性地查詢這些數據塊，將他們合并到一個排序好的數據塊。
這就是為什么稱為MergeTree。當然，合并意味著"寫入凈化"。所有的部分都是非修改的：他們僅創建和刪除，但是不會更新。當SELECT運行時，它將獲得一個表的快照。在合并之后，我們也保持舊的部分用于故障數據恢復，所以如果我們某些合并部分的文件損壞了，我們能夠根據原來的部分進行替換。MergeTree 不是一個LSM 樹，因為它不包含 “memtable” 和 “log”: 插入的數據直接寫入到文件系統。這個僅適合于批量的INSERT操作，并不是每行寫入，同時不能過于頻繁 – 每秒一次寫入是 OK 的，每秒幾千次寫入是不可以的。 我們使用這種方式是為了簡化，因為在生產環境中，我們主要以批量插入數據為主。MergeTree表只有一個(主)索引：沒有二級索引。它允許在一個邏輯表下的多個物理表示，例如，在多個物理表中存儲數據，甚至允許沿著原有的數據帶有預計算的表示。有MergeTree引擎作為背景線程來做額外的合并。示例是CollapsingMergeTree和AggregatingMergeTree。他們作為對更新的特定支持來看待。這些并不是真的更新，在背景合并運行時，因為用戶沒法控制時間，在MergeTreetable中的數據經常被存儲到多個部分，以非完全的合并形式。