ClickHouse 中的哈希表和 C++ 零成本抽象

哈希表是数据结构中的“明星”。在优化过程中，没有其他数据结构比它更容易引入错误。在这篇博文中，我们将探讨 ClickHouse 中如何使用哈希表。我们将展示现代 C++ 中零成本抽象是如何工作的，以及如何通过一些小技巧从一个通用的代码库中获取各种数据结构。基于通用的构建块，我们可以构建一个快速清理的哈希表、几种类型的 LRU 缓存、没有哈希的查找表以及字符串的哈希表。我们还将展示如何在特定场景中确保最佳性能，以及在测试性能时如何避免犯错。这些都是我们在 ClickHouse 中喜欢的底层优化！

首先，让我们讨论为什么需要哈希表，它们可以在数据库中在哪里使用，以及如何使它们最优化。然后我们将查看互联网上各种哈希表的基准测试，并解释如何正确实现它们。最后，我们将讨论我们的零成本 C++ 框架，它为特定用例生成理想的哈希表。

ClickHouse 以其能够以闪电般的速度聚合海量数据的能力而闻名。SQL 中的聚合由 GROUP BY 子句表示。大多数数据库，包括 ClickHouse，都使用哈希聚合算法的某种变体来实现 GROUP BY，其中输入行存储在一个哈希表中，分组列作为键。选择正确的哈希表类型对于性能至关重要。它取决于分组列的数据类型（例如固定宽度整数、可变宽度字符串等）、唯一键的数量、它们的总数以及其他因素。ClickHouse 针对 GROUP BY 子句拥有超过 40 种不同的优化，其中每一种都以不同的方式使用高度优化的哈希表，并利用一个强大的框架来生成最适合该工作的哈希表！

如果我们说我们只有一个哈希表，那是不正确的。我们有很多哈希表，它们都是围绕灵活强大的框架构建的。这些变体主要用于执行 GROUP BY 和 JOIN 操作。

哈希表是一种数据结构，它为插入、查找和删除操作提供恒定的平均性能。对于 GROUP BY 聚合场景，删除操作对我们来说并不重要。

让我们看看上图。大多数开发人员会从早期的计算机科学课程中了解哈希表的结构。我们获取一个想要插入的特定键，使用哈希函数对其进行哈希处理，并使用数组长度除法的余数计算插入到数组中的位置。

哈希表在不同层次上需要许多设计决策，并且是微妙而复杂的数据结构。每个设计决策对哈希表本身都有重要的影响，但多个设计决策的交互方式也会产生影响。设计阶段的错误可能导致您的实现效率低下，并明显降低性能。哈希表由哈希函数、冲突解决方法、调整大小策略以及各种在内存中排列其单元格的可能性组成。

让我们从选择哈希函数开始。这是一个非常重要的设计决策，由于 潜在选择数量众多，许多人经常会犯错，所有这些选择似乎都能产生同样好的随机值。我们将概述此决策过程的主要问题。

首先，对于整数类型，许多人通常使用恒等哈希函数。这是错误的，因为真实数据的分布并不相同，并且您将有大量的冲突。此外，一些哈希函数针对整数进行了优化，如果您的数据允许，请使用它们而不是通用哈希函数。此外，除非您预计会受到攻击，否则请不要使用各种加密哈希函数，因为这些函数在计算上更昂贵。例如，假设您使用吞吐量约为 1 GB/s 的加密 Sip Hash 函数，而 City Hash 函数的吞吐量约为 10 GB/s。这意味着您的表的吞吐量将限制为 1 GB/s。

此外，不要使用像 FNV1a 这样的旧版哈希函数，因为它们速度慢且相对于竞争对手而言分布较差。此特定哈希函数用于 GCC 标准库，并且已弃用。GitHub 上的 SMHasher 存储库 包含各种哈希函数的测试，并表明 FNV1a 未能通过任何严肃的测试。

在 ClickHouse 中，默认情况下，我们使用尽管分布相对较差但对哈希表来说很好的哈希函数。例如，对于整数类型，我们使用 CRC-32C。此哈希函数占用很少的 CPU 时间并且非常快，因为它可以使用 专用指令 实现，这些指令仅使用两到三个周期。对于字符串，我们使用基于 CRC-32C 的自定义哈希函数。如果您不使用它，您可以使用一些标准的哈希函数，例如 Farm Hash。

让我们谈谈冲突解决。在任何哈希表中，根据 生日悖论，都会出现相同键落入相同槽中的情况。假设我们插入了键 K1，它进入了表的第三个槽。现在我们尝试插入 K2 键，根据除法的余数，它落入了与上面所示相同的槽中。我们需要弄清楚接下来该怎么办。有几种方法可以解决这种情况。

第一种方法是使用 链式地址法，其中表单元格将使用列表或数组，我们将使用底层数据结构将下一个键放入相同的单元格中。

或者，我们可以使用 开放地址法。在这种情况下，我们将键放入后续的表槽之一。

当然，还有更复杂的方法，比如布谷鸟哈希或双向哈希。然而，这些方法存在一个问题：它们通常难以实现，需要额外的内存读取操作，并且在大规模场景下通常会变慢。例如，即使在热点路径上添加大量代码也会显著降低哈希表中的查找速度。

让我们从最简单的方法开始——链地址法。这种方法利用一个列表来存储哈希到相同单元格的键。假设第一个键已经插入，则第二个键将追加到该第一个键下面的列表中。稍后在查找过程中，会检查主单元格及其子列表中是否存在键。

这就是std::unordered_map的使用方式。为什么这种方法不是有效的？它不是缓存友好的，这会导致性能下降。它的优点在于它适用于所有情况，并且对使用的哈希函数不挑剔。即使在负载因子很高的情况下也能正常工作。但是，不幸的是，它会给分配器带来很大的压力，因为即使在哈希表中的热点路径查找中调用任何函数都会非常昂贵。因此，所有现代哈希表都使用开放地址法。

在这篇博客中，我将讨论三个值得关注的哈希表。其中两个是 Google Flat Hash Map 和 Google Abseil Hash Map。Abseil 是 Google 的一个较新的框架，它对哈希表采用了略微不同的方法。我们还将讨论 ClickHouse 中的哈希表。所有这些哈希表都使用开放寻址法。对于此方法，当第二个键被哈希并分配到与第一个键相同的槽位时，我们将它放入数组中的下一个槽位之一，如上所示。

下一个槽位的选择取决于许多因素。我们可以使用线性探测；也就是说，我们简单地选择下一个槽位。还可能存在二次探测，其中我们使用乘数 2 选择下一个槽位，即 1、2、4、8 等。这提供了理想的缓存局部性，因为数据是按处理器中的缓存行读取的。这意味着一个哈希键查找只转换为一次内存读取操作。此方法的主要问题是它需要一个适合您的数据的好的哈希函数。

让我们假设我们选择了一个糟糕的哈希函数。很容易假设，在某些时刻，我们的数组中会出现“粘连在一起”的集群。当这种情况发生时，我们将开始检查与我们正在查找的值无关的键。此方法也不适合大型对象，因为它们会破坏所有缓存局部性，使其主要优势失效。我们如何解决这个问题？我们将大型对象序列化到某个地方，并在哈希表中存储指向它们的指针。

另一个非常重要的概念是调整大小。首先，您需要决定调整大小的次数。有两种方法。第一种是按 2 的幂调整大小。这种方法的优点是查找表期间在除法上花费的时间最少，如果表存在于缓存中，则以纳秒为单位执行。如果您不使用 2 的幂，则会发生除法运算，这非常昂贵。但是，如果表大小始终是 2 的幂，则需要确定哈希值在哈希映射中的位置的昂贵的除法运算 (%) 可以替换为廉价的位移运算 (<<)。还有一种更理论上的理由来使用接近 2 的幂但也是素数的幂。缺点是您需要弄清楚如何避免除法。为此，我们可以使用某种常量开关或像libdivide这样的库。

关于负载因子，ClickHouse 和所有 Google 哈希表（除了 Abseil Hash Map）都使用 0.5 的负载因子。这是一个您可以用于哈希表的好的负载因子。Abseil Hash Map 使用大约 0.9 的负载因子。

最有趣的是单元格在内存中的排列方式，以及这些决策对于保持哈希表功能的重要性。

为什么我们需要一种特殊的方式来在内存中放置单元格？一旦有人第一次开始尝试编写自己的开放寻址哈希表，他们就会面临这种情况。想象一下：您正在编写代码并试图插入并处理第二个键落入第一个槽位但发生冲突的情况。我们需要弄清楚接下来该做什么。

首先，我们将不得不遍历这些单元格，判断每个单元格是否为空，我们是否可以写入它或者它是否已被删除。假设内存已初始化，我们需要能够区分单元格为空（即未分配值或由于删除而为空）还是仅仅包含 Null 值，例如在 ClickHouse 中，我们支持可空类型。

在这种情况下，有几种选择。第一种选择是要求哈希映射的用户提供一些键值来指示空单元格，以及用于已删除单元格的墓碑键。用户永远无法将这些值插入哈希表，即它不在真实数据中，因此我们可以用它来识别单元格是空的还是已删除的。

此方法用于 Google Flat Hash Map。此方法的主要缺点是我们必须让客户端选择一些在其数据中不会出现的值。有时很容易找到键，有时很难，但总的来说，它使 API 变得复杂。这在图片中大致可见：哈希表中有槽位，其中一些是空键，一些是墓碑。这样，我们可以安全地检查该槽位是否为空。

ClickHouse 使用了一种更高级的方法，如上所示。我们不在哈希表中保留 Null 单元格。我们为 Null 元素保留了一些特殊的单元格，并将它们分开。在插入或查找哈希表之前，我们首先检查值是否为 Null，并分别处理它。缺点是出现了一个额外的分支，但在实践中，CPU 中的分支预测器非常有效地隐藏了额外的成本，因此我们的性能不受影响。

还有一种相当复杂的方法，它用于 Google 的最新哈希表。为了达到这种方法，您需要从更简单的情况开始。例如，我们希望在某个地方保留有关单元格是已删除还是空的的信息。如果我们尝试将此信息写入哈希表，我们将浪费额外的内存。因此，我们将把它保存在其他地方，例如一些元数据中。

但由于事实证明我们只需要两个比特，因此为这些信息花费它们是昂贵的。我们可以尝试一个完整的字节，但其他比特呢？在 Google 的实现中，哈希函数的前 53 位用于搜索带有元数据的单元格，而哈希函数的低位位于元数据中。

为什么这可能有用？我们可以将这些数据放在寄存器中，并快速检查是否应该查看关联的单元格——例如，使用 SSE 指令。

如果您决定查看哪个哈希表是最好的，那么互联网上每两个人中就有一个写过他们最快的哈希表。如果您开始更深入地挖掘，您会发现事实并非如此。许多基准测试没有涵盖重要的事项，也没有使用任何特定场景。因此，目前尚不清楚哈希表是否快速。

基准测试的主要问题是什么？它们通常不是基于真实数据而是基于随机数。随机数的分布与真实数据不符。此外，很多时候，没有考虑特定的场景。同样频繁的是，它们没有显示基准代码，只显示各种图表，并且无法重复基准测试。

基准测试应该如何进行？它们需要在真实数据和真实场景上进行。在 ClickHouse 中，真实场景是数据聚合，我们从网络分析数据集中获取数据本身，您可以从我们的网站下载它。

现在让我们看一下基准测试，并尝试分析不同的设计决策如何影响哈希表的性能。

以下结果基于包含大约 2,071,4865 个唯一值的 WatchId 列。这些数据不适合 CPU 缓存，并且占用大约 600 MB，迫使访问主内存。这里的计时代表聚合所有值的总运行时间。

哈希表	时间（秒）
ClickHouse HashMap	7,366 秒
Google DenseMap	10,089 秒
Abseil HashMap	9,011 秒
std::unordered_map	44,758 秒

如果我们查看此基准测试，我们会发现 ClickHouse 和哈希表远远领先于 std::unordered_map。为什么？因为，正如我所说，std::unordered_map 不是缓存友好的；具体来说，这些数据没有放置在 Lx 缓存中。我们可以使用perf stat查看这一点，以确认我们的假设，即 std::unordered_map 具有更多缓存未命中，这导致它的速度变慢。

哈希表	缓存未命中
ClickHouse HashMap	329,644,616
Google DenseMap	383,350,820
Abseil HashMap	415,869,669
std::unordered_map	1,939,811,017

我们还可以查看一些数字，这些数字证实了访问主内存与 L1 或 L2 缓存的成本更高。我们可以假设，为了使哈希表以最大速度工作，它必须针对缓存局部性进行优化。

让我们进行一个略有不同的基准测试，其中所有数据都进入缓存。在这种情况下，我们看到std::unordered_map的速度不再下降那么多。在这种情况下，我们使用了一个 RegionID 列，该列包含来自 9040 个唯一值集合的重复值，这些值适合 Lx 缓存。

哈希表	时间（秒）
ClickHouse HashMap	0.201 秒
Google DenseMap	0.261 秒
Abseil HashMap	0.307 秒
std::unordered_map	0.466 秒

到目前为止，我们一直专注于解决方案的算法设计。但是，为了使所有这些都能正常工作，我们需要开发一个灵活且强大的 C++ 包装器。

我们的哈希表包装器利用基于策略的设计，即每个设计选择都成为哈希表接口的一部分。主要的接口包括哈希函数、分配器、单元格（这是我们表中的一个重要元素）、增长器（调整大小策略的接口）以及哈希表本身，它将所有这些组件组合在一起。

让我们从哈希函数开始。这与 C++11 中引入的std::hash相同的接口，没有什么新东西。

template <typename T>
struct Hash {
    size_t operator () (T key) const 
    { 
        return DefaultHash<T>(key);
    }
};

分配器是标准库分配器的一个稍微修改过的接口，因为我们的版本支持realloc。为什么我们需要realloc？在 Linux 上，我们对大型哈希表使用mmap和mremap。为了支持这一点，我们需要在我们的接口中提供一个realloc方法。

以下分配器对大型内存块使用mmap和mremap。

class Allocator
{
    void * alloc(size_t size, size_t alignment);
    void free(void * buf, size_t size);
    void * realloc(void * buf, size t old size, size_t new size);
};

当我们为其使用自定义策略时，也存在一个从一开始就在栈上分配内存的分配器。

AllocatorWithStackMemory<HashTableAllocator, initialbytes>

哈希表单元格是我们哈希表的一个完整元素；您可以在其中写入哈希值，从中获取哈希值，并检查它是否为空。此外，单元格本身可以为哈希表提供信息，即它了解哈希表内部的内容，因为它由其状态参数化。

template <typename Key, typename Mapped, typename HashTableState> 
struct HashTableCell {
    ...
    void setHash(size_t hash_value); 
    size_t getHash(const Hash & hash) const;
    bool isZero(const State & state); 
    void setZero();
    ...
};

以下是我们的调整大小策略的接口，其中包含获取哈希表中位置、移动到下一个元素、检查插入下一个元素是否会导致表溢出以及调整大小本身的方法。让我们在代码中定义它们。

struct HashTableGrower
    size_t place(size_t x) const; 
    size_t next(size_t pos) const; 
    bool willNextElementOverflow() const; 
    void increaseSize();
};

哈希表是由一个 C++ 模板生成的，该模板通过继承这些接口来组合所有这些接口。与使用虚函数在运行时进行组合不同，这种方法确保了最佳性能，因为编译器能够单独优化每个生成的哈希表。

template
<
    typename Key, 
    typename Cell, 
    typename Hash, 
    typename Grower, 
    typename Allocator

>
class HashTable :
    protected Hash, 
    protected Allocator, 
    protected Cell::State; 
    protected ZeroValueStorage<Cell::need_zero_value_storage, Cell>

例如，我们如何使用零值存储？如果其中一个基类不包含数据，我们不会浪费额外的内存来存储它。例如，我们上面提到 ClickHouse 单独生成零值单元格并将其放置在特殊的零值存储中。但这仅在某些情况下是必要的。假设我们不需要它，在这种情况下，零值存储是一个什么都不做的专门化，编译器会删除不必要的代码，并且没有任何东西会减慢速度。

template ‹bool need_zero_value_storage, typename Cell> 
struct ZeroValueStorage;

template <typename Cell> 
struct ZeroValueStorage<true, Cell>
{ 
    ...
};

template <typename Cell>
struct ZeroValueStorage<false, Cell>
{ 
    ...
};

自定义调整大小策略能给我们带来什么？具有固定大小且不解决哈希冲突的自定义调整大小策略会生成非常适合缓存最近元素的哈希表。使用步长不等于 1 的调整大小策略，我们可以获得例如二次探测，这对于检查各种基准测试可能很方便。

能够在单元格中存储状态有助于我们在单元格中存储有用的信息，例如哈希值。它有什么用？对于我们不想在字符串哈希表的情况下重新计算哈希函数的情况。

struct HashMapCellWithSavedHash : public HashMapCell
{

    size_t saved_hash; 
    void setHash(size_t hash_value) { saved_hash = hash_value; } 
    size_t getHash(const Hash &) const { return saved_hash; }

};

我们还可以创建一个可以快速清除的哈希表。当我们有一个巨大的哈希表，我们已经用数据填充了它，现在我们想重用它时，这很有用。为了删除哈希表中的所有元素，我们使用表的版本作为状态 - 我们将版本存储在单元格和表本身中。在检查单元格是否为空时，我们只需比较单元格和哈希表的版本。如果我们需要快速删除，我们将哈希表版本加 1。这比尝试删除哈希表中的所有单元格更有效，这将需要我们遍历它并导致大量的缓存未命中 - 从而导致性能下降。

strut FixedClearableHashMapCell 
{ 
    strut ClearableHashSetState 
    { 
        UInt32 version = 1; 
    }; 
    
    using State = ClearableHashSetState; 
    
    UInt32 version = 1; 
    
    bool isZero(const State & st) const { return version ! = st.version; }
    
    void setZero() { version = 0; }

}

另一个有趣的技巧是 LRU 缓存。这是LRU 排除策略的实现。通常，这实现为一个双向链接的 LRU 列表和一个哈希表，它提供从键到列表中位置的快速映射。每次我们引用特定键时，都需要将值移动到列表的“最新”端并更新哈希映射中值的映射。如果元素尚未存储在 LRU 缓存中，我们将逐出列表“最旧”端的元素并插入新的元素。当列表满时，我们从列表开头删除元素。这样，列表将始终包含最新的元素。

使用单独的列表和哈希表的 LRU 缓存的实现不是最佳的，因为它使用了两个容器。在 ClickHouse 的情况下，我们想出了如何在单个容器中做到这一点。在哈希表单元格中，我们存储指向下一个和上一个元素的指针，从而在哈希表内部形成一个双向链接列表。

struct LRUHashMapCell 
{ 
    static bool constexpr need_to_notify_cell_during_move = true; 
    
    static void move(LRUHashMapCell * old_loc, LRUHashMapCell * new_loc); 
    
    LRUHashMapCell * next = nullptr;
    
    LRUHashMapCell * prev =  nullptr;
    
};

为了实现这一点，我们存储两个指针并使用 Boost Intrusive 库。下面我们展示了这方面最重要的部分。我们创建了一个侵入式列表并将其用作列表。我们在单元格中声明了指向下一个和上一个元素的指针这一事实足以让我们在单元格顶部创建一个侵入式列表。

using LRUList = boost:: intrusive:: list
    <
        Cell,
        boost::intrusive::value_traits<LRUHashMapCellIntrusiveValueTraits>,
        boost::intrusive::constant_time_size<false>
    >;
    
LRUList ru_list ;

我们针对各种场景提供了一些专门的哈希表。例如，小型表是一个哈希表，它是一个数组。它有什么用？它位于 L1 缓存中，并实现了哈希表接口。如果我们需要实现一个简单的算法，这很有用。

template <typename Key, typename Cell, size_t capacity> 
class SmallTable : protected Cell:: State 
{

    size_t m_size = 0; 
    Cell buf[capacity];
    ...
}

我们还有一个更有趣的哈希表 - 字符串哈希表。它是由一位来自中国的研究生贡献给我们的。这些是用于不同长度字符串的四个哈希表，我们为它们使用不同的哈希函数。更具体地说，这个哈希表由 4 个哈希表组成

• 用于大小为 0-8 字节的字符串
• 用于大小为 9-16 字节的字符串
• 用于大小为 17-24 字节的字符串
• 用于大于 24 字节的字符串

另一个非常有趣的哈希表是二级哈希表。它由 256 个哈希表组成。如果您不喜欢哈希表，为什么可能需要这样做？例如，当我们执行 GROUP BY 操作时，我们希望在多个线程中执行它。因此，我们需要填充表然后合并它们。我们可以使用无锁哈希表，但我们团队中没有人喜欢无锁，所以我们使用二级哈希表。

它的工作原理是在每个线程中创建二级哈希表。例如，如果我们有四个流，我们将得到一个 256 列（表）和四行（流）的矩阵。我们正在将数据插入其中一个表中。例如，我们根据如下所示的公式进行分配。然后，当我们需要连接表时，我们使用最少的同步并按列连接它们。最后，这里没有任何东西会减慢速度。

size_t getBucketFromHash(size_t hash_value) {

    return (hash_value >> (32 - BITS_FOR_BUCKET)) & MAX_BUCKET;

}

因此，我们编写了自己的相当灵活和强大的框架来实现哈希表。从它可以获得适用于不同场景的哈希表。

我想承认：我真的很喜欢哈希表。对于那些设法改进我们的基准测试的人 - 例如，创建一个比我们的哈希表更快的哈希表，我们将提供一件独特的“ClickHouse 不减速连帽衫”！