數據庫索引，一個排序故事

RapidResponse平台以目的驅動為基礎數據庫引擎我們在Kinaxis開發的。在數據庫引擎團隊中，我們維護並不斷改進數據庫引擎。我們經常解決與性能、並行和內存管理相關的問題。

本博客討論的是我在Kinaxis數據庫引擎團隊開始工作時遇到的第一個問題。任務很簡單:加速我們的一個索引構建器。讓我們來看看我們用來提高性能的一些實用技術。

問題的細節

索引是一種數據結構，它可以加速某些數據訪問操作的性能。

索引構建器是一個代碼組件，負責從數據庫的磁盤表示構建內存中索引。

下麵是關於這個特定索引構建器的更多細節:
•內存中的索引被實現為b樹。
•索引必須執行良好的插入和搜索。
•索引項基本上是64位整數。
•索引構建器掃描一堆數據文件，提取索引條目，並構建b樹。
•被掃描的數據文件大小不均勻，每個文件包含隨機數量的索引項。
•數據文件中的索引條目是未排序的，並且包含重複的條目。
•預期的索引大小有很大的差異。一個典型的索引索引可能包含1個、幾個或數千個條目。上限是1000萬條左右。

原始實現

索引構建器的原始實現如下所示:

1)單個線程掃描所有數據文件，提取索引條目，逐個插入到b樹中。

這個實現中有兩件事非常昂貴:

1)文件掃描速度慢。
2)一個一個地往b樹中插入數據很慢，而且很難並行化。

改進1:文件掃描並行化

第一個改進是並行化文件掃描。

1)將文件掃描分配到工作線程池中。
2)每個工作線程從其分配的數據文件集合中提取索引項，並將它們推入私有工作緩衝區。
3)從工作緩衝區中取出索引項，逐個插入到b樹中。

並行文件掃描可以更好地利用文件存儲設備的吞吐量，大大減少文件掃描時間。我們還可以在文件掃描和插入到b樹之間啟用一些並行性。然而，性能仍然主要受到插入b樹的限製，b樹必須序列化。

改進2:自底向上構建b樹

是什麼導致b樹插入緩慢?插入操作必須:遍曆樹，為樹節點動態分配內存，並重新平衡樹。我們能找到更快的方法來構建b樹嗎?

首先，讓我們觀察一下，與使用插入構建平衡b樹相比，構建和排序類數組數據結構的速度要快得多。例如，讓我們使用c++標準庫作為參考來比較這些操作。
•基於數組的方法使用std::vector, std::sort和std::unique。
•基於樹的方法使用std::set。

示例代碼:sort_vs_tree.cpp constexpr size_t MAX_ELEMENTS = 10000000;std::向量< uint64_t > dataArray;std::設置< uint64_t > sortedSet;std::向量< uint64_t > sortedArray;void GenerateDataArray() {datarray .reserve(MAX_ELEMENTS);For (size_t I = 0;我< MAX_ELEMENTS;+ + i) {dataArray.emplace_back (std::蘭德());}} void BuildSortedSet() {for (auto e: dataArray) {sortedSet.emplace(e);}} void BuildSortedArray() {for (auto e: dataArray) {sortedArray.emplace_back(e); } std::sort(sortedArray.begin(), sortedArray.end()); auto last = std::unique(sortedArray.begin(), sortedArray.end()); sortedArray.erase(last, sortedArray.end()); } int main(int argc, char* argv[]) { std::cout << std::setprecision(3); Timer timer; { TimerContext tc(timer); GenerateDataArray(); } std::cout << "GenerateDataArray " << timer.DeltaS() << "s" << std::endl; { TimerContext tc(timer); BuildSortedArray(); } std::cout << "BuildSortedArray " << timer.DeltaS() << "s" << std::endl; { TimerContext tc(timer); BuildSortedSet(); } std::cout << "BuildSortedSet " << timer.DeltaS() << "s" << std::endl; return 0; }

對於1000萬個元素，這是我的開發機器上的結果。基於數組的方法比基於樹的方法快3.7倍以上。

BuildSortedArray 3.99s BuildSortedSet 14.7s

一旦我們有了一個索引項的排序數組，就沒有意義將它們逐個插入b樹。我們從下往上建立b樹。我們首先將已排序的條目劃分為葉節點，然後在它們上麵構建樹形結構。

因為我們可以預先計算樹節點的高度和數量，所以我們可以用最小的內存分配數量有效地批量分配樹節點。我們隻需要為每個父-子節點鏈接分配一次。我們從不需要重新平衡樹，或分裂或合並節點。

現在索引構建器的實現看起來像這樣:
1)將文件掃描分配到工作線程池中。
2)每個工作線程從其分配的數據文件集合中提取索引項，並將它們推入私有工作緩衝區。
3)將工作緩衝區合並並排序為單個排序數組。
4)自下而上構建b樹。

接下來，我們將進一步了解索引構建器是如何管理內存的。

改進3:優化工作緩衝區數據結構

讓我們考慮一下這個步驟的實現，“將工作緩衝區合並並排序到一個已排序的數組中。”我們應該使用什麼數據結構來實現工作緩衝區和排序緩衝區?

由於這些數據結構是數組，我們可以天真地選擇使用std::vector。這種方法的一些缺點是:
一個std::vector需要一個連續的內存分配。這可能適用於較小的工作緩衝區，但不適用於更大的排序緩衝區。1千萬個條目的索引大約需要80 MB。
•如果我們需要增加或縮小一個std::vector，我們需要將它的所有內容從一個相鄰的塊複製到另一個塊。
•合並一個std::vector到另一個的唯一方法是複製它的所有數據。
vector分配額外的內存以減少增長的成本，因為增長會浪費大量內存。

我們決定使用混合數據結構，這是一個小數組的鏈表。下麵是數據結構定義。

模板 struct BufferNode {uint64_t mData[block_sz];uint64_t沉思;struct BufferNode * mNext;};模板 struct Buffer {size_t mUsed;size_t mReserved;BufferNode < block_sz > * mHead;BufferNode < block_sz > * mTail;}；

Buffer結構的好處是:
•我們不需要能夠分配大塊連續的內存。
•種植成本低，截斷成本也低。
合並緩衝區的成本很低。我們隻是拚接BufferNode列表。
•我們可以綁定浪費的內存。

事實證明，Buffer結構是實現工作緩衝區和排序緩衝區的一種有效方法，因為它補充了我們接下來將要討論的排序實現。

改進4:自適應歸並排序

我們需要選擇一種算法來合並和排序工作緩衝區。考慮到問題的性質，歸並排序是一個明顯的選擇。

歸並排序也適用於存儲在Buffer結構中的數據，因為它是線性訪問數據的。快速排序和插入排序不能很好地工作，因為它們需要隨機訪問。

回想一下，期望的索引大小是雙峰式的:有些索引可能很小，以至於std::qsort完全可以處理它們。

由於未排序的索引項可能有較小的本地運行，我們可以通過按運行組織合並來減少所需的比較數量。我們還可以通過對工作緩衝區的片段使用std::qsort開始運行。

這就給我們留下了一個簡單的自適應歸並排序算法:
•使用標準庫函數(如std::qsort)對每個BufferNode進行排序和惟一化，這對小型數組很有效。
•拚接工作緩衝區，並將初始未排序的索引條目拆分為運行。
•以成對的運行方式遍曆拚接數據。將每對運行合並為一個較長的運行。
•重複步驟3，直到數據隻包含一次運行。

改進5:優化排序內存管理

分析顯示，在排序階段剩下的惟一開銷很大的操作是內存分配。我們可以做一些最後的改進，以減少對內存分配器的調用數量。

1)由於每個線程的工作緩衝區使用與排序緩衝區相同的Buffer結構，我們可以很容易地拚接工作緩衝區並將其作為排序緩衝區重用。我們隻需要分配一個額外的排序緩衝區。

2)每次歸並排序都需要一個源緩衝區和目標緩衝區。使用“雙緩衝區”方法為每次歸並排序重用相同的排序緩衝區。例如，如果N從緩衝區#1合並到緩衝區#2，那麼(N+1)則反向合並，從緩衝區#2合並到緩衝區#1。

3)由於我們知道合並索引項的最大可能大小，我們預先分配整個排序緩衝區。我們還連續地分配buffernode的大塊，這減少了所需的內存分配數量。

經驗教訓

以下是我從這項任務中學到的一些東西。
•管理內存分配。內存分配非常昂貴，幾乎可以支配任何直接算法代碼的性能。它也可能是並行性的瓶頸。因此，盡可能謹慎地分配內存。
•如果一個算法可以很容易地轉換成分治模式，那麼並行化它是最簡單的優化。

最後:實現自定義排序算法的選擇是有爭議的。絕大多數情況下，我建議重用現有的實現。當我在處理這個任務時，我主要關注內存管理，排序算法自然地遵循數據結構的選擇。後來我才知道，事實上，我的確是在重新發明輪子——我偶然發現了一個原始版本的Timsort！

最後一件事。如果你喜歡你在這裏讀到的，並且認為我們是那種你想加入的團隊，Kinaxis正在招人!我們很樂意收到你的來信。訪問://www.70soh.com/en/careers空缺職位。