淺談 Go 語言高性能哈希表的設計與實現

目錄

1. MatrixOne 數據庫是什麼?

2. 哈希表數據結構基礎

3. 哈希表基本設計與對性能的影響

    3.1 鏈地址法

    3.2 開放尋址法

    3.3 碰撞處理

    3.4 Max load factor

    3.5 Growth factor

    3.6 空閒桶探測方法

4. 一些常見的哈希表實現

    4.1C++ 

    4.2std::unordered_map/boost::unordered_map

    4.3 go map

    4.4 swisstable

    4.5 ClickHouse 的哈希表實現

5. 高效哈希表的設計與實現

    5.1 基本設計與參數選擇

    5.2 哈希函數

    5.3 特殊優化

    5.4 具體實現代碼

6. 性能測試

    6.1 測試環境

    6.2 測試內容

    6.3 整數 key 結果

    6.4 字符串 key 結果

7. 總結

1 MatrixOne 數據庫是什麼?

MatrixOne 是一個新一代超融合異構數據庫，致力於打造單一架構處理 TP、AP、流計算等多種負載的極簡大數據引擎。MatrixOne 由 Go 語言所開發，並已於 2021 年 10 月開源，目前已經 release 到 0.3 版本。在 MatrixOne 已發佈的性能報告中，與業界領先的 OLAP 數據庫 Clickhouse 相比也不落下風。作爲一款 Go 語言實現的數據庫，居然可以與 C++ 實現的頂級 OLAP 數據庫性能媲美，這其中就涉及到了很多方面的優化，包括高性能哈希表的實現，本文就將詳細說明 MatrixOne 是如何用 Go 實現高性能哈希表的。

Github 地址：https://github.com/matrixorigin/matrixone

2 哈希表數據結構基礎

哈希表（Hashtable）是一種非常基礎的數據結構，對於數據庫的分組聚合和 Join 查詢的性能至關重要。以如下的分組聚合爲例 (備註，圖引自參考文獻 1)：

SELECT col, count(*) FROM table GROUP BY col

它包含兩個處理階段：第 1 階段是使用數據源的數據建立一個哈希表。哈希表中的每條記錄都與一個計數器有關。如果記錄是新插入的，相關的計數器被設置爲 1；否則，計數器被遞增。第二階段是將哈希表中的記錄集合成一種可用於進一步查詢處理的格式。

對於 Join 查詢而言，以如下 SQL 爲例：

SELECT A.left_col, B.right_col FROM A JOIN B USING (key_col)

它同樣也有兩個階段：第一階段是使用 Join 語句右側表的數據建立一個哈希表，第二階段是從左側表中讀取數據，並快速探測剛剛建立的哈希表。構建階段與上面的分組實現類似，但每個哈希表的槽位都存儲了對右邊列的引用。

由此可見，哈希表對於數據庫的 SQL 基礎能力起着很關鍵的作用 ，本文討論哈希表的基本設計與對性能的影響，比較各種常見哈希表實現，然後介紹我們爲 MatrixOne 實現的哈希表的設計選擇與工程優化，最後是性能測試結果。

我們預設讀者已經對文中提到哈希表相關的概念有所瞭解，主要討論其對性能的影響，不做詳細科普。如果對基本概念並不瞭解，請從其他來源獲取相關知識，例如維基百科。

3 哈希表基本設計與對性能的影響

碰撞處理

不同的 key 經哈希函數映射到同一個桶，稱作哈希碰撞。各種實現中最常見的碰撞處理機制是鏈地址法（chaining）和開放尋址法（open-addressing）。

鏈地址法

在哈希表中，每個桶存儲一個鏈表，把相同哈希值的不同元素放在鏈表中。這是 C++ 標準容器通常採用的方式。

優點：

• 實現最簡單直觀

• 空間浪費較少

開放尋址法

若插入時發生碰撞，從碰撞發生的那個哈希桶開始，按照一定的次序，找出一個空閒的桶。

優點：

• 每次插入或查找操作只有一次指針跳轉，對 CPU 緩存更友好

• 所有數據存放在一塊連續內存中，內存碎片更少

當 max load factor 較大時，性能不如鏈地址法。然而當我們主動犧牲內存，選擇較小的 max load factor 時（例如 0.5），形勢就發生逆轉，開放尋址法反而性能更好。因爲這時哈希碰撞的概率大大減小，緩存友好的優勢得以凸顯。

值得注意的是，C++ 標準容器實現不採用開放尋址法是由 C++ 標準決定，而非根據性能考量（詳細可見這個 boost 文檔）。

Max load factor

對鏈地址法哈希表，指平均每個桶所含元素個數上限。

對開放尋址法哈希表，指已填充的桶個數佔總的桶個數的最大比值。

max load factor 越小，哈希碰撞的概率越小，同時浪費的空間也越多。

Growth factor

指當已填充的桶達到 max load factor 限定的上限，哈希表需要 rehash 時，內存擴張的倍數。growth factor 越大，哈希表 rehash 的次數越少，但是內存浪費越多。

空閒桶探測方法

在開放尋址法中，若哈希函數返回的桶已經被其他 key 佔據，需要通過預設規則去臨近的桶中尋找空閒桶。最常見有以下方法（假設一共 | T | 個桶，哈希函數爲 H(k)）：

• 線性探測（linear probing）：對 i = 0, 1, 2...，依次探測第 H(k, i) = H(k) + ci mod |T | 個桶。

• 平方探測（quadratic probing）：對 i = 0, 1, 2...，依次探測 H(k, i) = H(k) + c1i + c2i2 mod |T|。其中 c2 不能爲 0，否則退化成線性探測。

• 雙重哈希（double hashing）：使用兩個不同哈希函數，依次探測 H(k, i) = (H1(k) + i * H2(k)) mod |T|。

線性探測法對比其他方法，平均需要探測的桶數量最多。但是線性探測法訪問內存總是順序連續訪問，最爲緩存友好。因此，在衝突概率不大的時候（max load factor 較小），線性探測法是最快的方式。

其他還有一些更精巧的探測方法，例如 cuckoo hashing，hopscotch hashing，robin hood hashing（文章開頭給的維基百科頁面裏都有介紹）。然而它們都是爲 max load factor 較大（0.6 以上）的情形設計的。在 max load factor = 0.5 的時候，實際測試中性能都不如最原始最直接的線性探測。

4 一些常見的哈希表實現

C++ std::unordered_map/boost::unordered_map

基於上面提到的原因，處理碰撞使用鏈地址法。默認 max load factor = 1，growth factor = 2。設計簡單，不用多說。

go map

通過閱讀 golang 庫的代碼得知，golang 內置的 map 採用鏈地址法。

swisstable

來自於 Google 推出的 abseil 庫，是一款性能十分優秀的針對通用場景的哈希表實現。碰撞處理方式使用開放尋址，地址探測方法是在分塊內部做平方探測。parallel-hashmap，以及 rust 語言標準庫的哈希表實現，都是基於 swisstable。更多信息可參考此處。

ClickHouse 的哈希表實現

採用開放尋址，線性探測。max load factor 爲 0.5，growth factor 在桶數量小於 2^24 時爲 4，否則爲 2。

針對 key 爲字符串的情形，ClickHouse 還有專門的根據字符串長度自適應的哈希表實現，具體參見論文，這裏不展開。

5 高效哈希表的設計與實現

MatrixOne 是使用 go 語言開發的數據庫，市面上的知名哈希表實現我們都無緣直接使用，而在初始的實現中，我們採用了 go 語言自帶的 map，結果高基數的分組 (比如多屬性分組很容易做到高基數) 性能相比 ClickHouse 差距會接近一個數量級，低基數也慢不少，所以我們必須實現自己的版本。

基本設計與參數選擇

ClickHouse 的哈希表在自帶的 benchmark 中表現出了最高的性能，因此借鑑其具體實現成爲十分自然的選擇。我們照搬了 ClickHouse 的如下設計：

• 開放尋址

• 線性探測

• max load factor = 0.5，growth factor = 4

• 整數哈希函數基於 CRC32 指令

具體原因前面已經提到，當 max load factor 不大時，開放尋址法要優於鏈地制法，同時線性探測法又優於其他的探測方法。

並做了如下修改（優化）：

• 字符串哈希函數基於 AESENC 指令

• 插入、查找、擴張時批量計算哈希函數

• 擴張時直接遍歷舊錶插入新表

• ClickHouse 是先把舊錶整體 memcpy 到新表中，再遍歷調整位置。沒找到如此設計的原因，但是經測試性能不如我們的方式。

哈希函數

哈希函數的作用是將任意的 key 映射到哈希表的一個地址，是哈希表插入和查找過程的第一步。數據庫場景中使用的哈希函數，應該滿足：

• 速度儘量快

• 打散得儘量均勻（避免聚集），這樣使得碰撞概率儘量小，若哈希表做分區的話也可保證分得均勻

• 不需要考慮密碼學安全性

在 ClickHouse 的實現中，主要使用現代 CPU（amd64 或者 arm64）自帶的 CRC32 指令來實現哈希函數。

inline DB::UInt64 intHashCRC32(DB::UInt64 x)
{
#ifdef __SSE4_2__
 return _mm_crc32_u64(-1ULL, x);
#elif defined(__aarch64__) && defined(__ARM_FEATURE_CRC32)
 return __crc32cd(-1U, x);
#else
    /// On other platforms we do not have CRC32. NOTE This can be confusing.
 return intHash64(x);
#endif
}

經實測，打散效果非常不錯，而且每個 64 位整數只需一條 CPU 指令，已經達到理論極限，速度遠超 xxhash， Murmur3 等一系列沒有使用特殊指令的 “普通” 哈希函數。

我們的整數哈希函數也使用同樣的方法實現。

TEXT ·Crc32Int64Hash(SB), NOSPLIT, $0-16
 MOVQ   $-1, SI
 CRC32Q data+0(FP), SI
 MOVQ   SI, ret+8(FP)

 RET

值得注意的是，go 語言不具有 C/C++/rust 的 intrinsics 函數庫，因此要使用某些特殊的指令，只能用 go 彙編自己實現。而且 go 彙編函數目前無法內聯，因此爲了最大化性能，需要把計算哈希函數的過程做成批量化。這點將在後續的文章中具體介紹。

包含 CRC32 指令的 SSE4.2 最早見於 2008 年發佈的 Nehalem 架構 CPU。因此我們假設用戶的 CPU 都支持這一指令，畢竟更老的設備用來跑 AP 數據庫似乎不太合適了。

對於字符串類型的哈希函數，ClickHouse 仍然通過 CRC32 指令實現。我們經過調研，選擇基於 AESENC 指令來實現。AESENC 包含在 AES-NI 指令集中，由 Intel 於 2010 年發佈的 Westmere 架構中首次引入，單條指令執行 AES 加密過程中的一個 round。AESENC 平均一條指令處理 128 位數據，比 CRC32 更快，而且提供 128 位結果，適應更多應用場景（對比 CRC32 只有 32 位）。在實測中基於 AESENC 的哈希函數打散效果同樣優秀。網絡上基於 AESENC 指令實現的哈希函數已經有不少，例如 nabhash，meowhash，aHash。我們自己的實現在這裏（amd64）和這裏（arm64）。

特殊優化

我們針對字符串 key，使用了一種非常規的設計：不在哈希表中保存原始的 key，而是存兩個不同的基於 AESENC 指令的哈希函數，其中一個 64 位的結果當作哈希值，另一個 128 位的結果當作 “key”。192 位再加上 64 位的 value，每個桶寬度正好是 32 字節，可完全與 CPU 的 cacheline 對齊。在碰撞處理中，不比較原始 key，而是比較這 192 位的數據。不同的字符串兩個哈希值同時碰撞的概率極低，在 AP 系統中可以忽略不計。這樣做的優勢是把變長字符串比較變成了定長的 3 個 64 位整數比較，而且還省掉一次指針跳轉開銷，大大加速碰撞檢測的過程。

代碼片段：

type StringHashMapCell struct {
 HashState [3]uint64
 Mapped    uint64
}

...

func (ht *StringHashMap) findCell(state *[3]uint64) *StringHashMapCell {
 mask := ht.cellCnt - 1
 idx := state[0] & mask
 for {
  cell := &ht.cells[idx]
  if cell.Mapped == 0 || cell.HashState == *state {
   return cell
  }
  idx = (idx + 1) & mask
 }
 return nil
}

具體實現代碼

• https://github.com/matrixorigin/matrixone/tree/main/pkg/container/hashtable

6 性能測試

測試環境

• CPU：AMD Ryzen 9 5900X

• 內存：DDR4-3200 32GB

• 操作系統：Manjaro 21.2

• 內核版本：5.16.11

• 數據：ClickHouse 提供的一億行 Yandex.Metrica 數據集

測試內容

每個測試都是順序插入一億條記錄，再以相同順序查找一億條記錄。過程類似如下代碼所展示：

...
// Insert
for (auto k : data) {
 hash_map.emplace(k, hash_map.size() + 1);
}
...
// Find
size_t sum = 0;
for (auto k : data) {
 sum += hash_map[k]
}
...

整數 key 結果

下表中記錄了一些哈希表實現對 Yandex.Metrica 數據集不同屬性 insert/find 所用的時間，單位毫秒（ms）。

hja9iY

可以看出當基數非常小的時候，ClickHouse 實現最快。在基數較大時，MatrixOrigin 的實現最快，且基數越大領先得越多。

字符串 key 結果

NA2Kra

結果與整數 key 類似，基數越大我們的實現領先越多。

7 總結

以上性能測試結果已經大大超出了我們最初的預期。我們從移植 ClickHouse 自帶哈希表出發，預計由於語言差異，最終能達到 C++ 原版 70~80% 的性能。隨着反覆的迭代優化，以及不斷嘗試改變 ClickHouse 原本的一些設計，最終在哈希表的插入和查找性能上竟然超越了 C++ 版本。

這說明哪怕是一些非常基礎的通常被認爲早已研究透了的數據結構，通過針對特定應用場景仔細的設計和部分使用匯編加速，也可讓 go 實現的版本在性能上一點不輸 C/C++/rust 版本。這也爲我們堅持用 go 語言開發高性能數據庫提供了更多信心。

8 參考文獻

1. Tianqi Zheng, Zhibin Zhang, and Xueqi Cheng. 2020. SAHA: A String Adaptive Hash Table for Analytical Databases. Applied Sciences 10, 6 (2020). https: //doi.org/10.3390/app10061915

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/KB-VwshP7FlzO-OutuT-2w