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 标准库中使用了这种特定的哈希函数，并且已被弃用。SMHasher 存储库 在 GitHub 上包含各种哈希函数的测试，并表明 FNV1a 未能通过任何严格的测试。

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

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

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

或者，我们可以使用开放 寻址法。在这种情况下，我们将键放在以下表槽之一中。

还有更复杂的方法，例如 Cuckoo 哈希 或双向哈希。但是，这些方法存在一个问题：它们通常难以实现，需要从内存中额外获取数据，并且通常会降低规模。例如，即使是热路径上的大量代码也会显着减慢哈希表中的查找速度。

让我们从最简单的方法开始——链式法。这利用列表来存储哈希到同一单元格的键。假设已插入第一个键，则第二个键将附加到此第一个键下方的列表中。稍后在查找期间，将检查主单元格及其子列表是否存在键。

这就是 std::unordered_map 的使用方式。为什么这种方法无效？它不是缓存本地的，这将导致性能不佳。它的有效性在于它在所有情况下都有效，并且对所使用的哈希函数不太挑剔。即使在高 负载因子 的情况下，它也有效。但是，不幸的是，它会非常严重地加载分配器，因为即使在哈希表中的热路径查找中调用任何函数也会非常昂贵。因此，所有现代哈希表都使用开放寻址法。

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

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

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

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

关于负载因子，ClickHouse 和除 Abseil 哈希映射之外的所有 Google 哈希表都使用 0.5 的负载因子。这是一个很好的负载因子，您可以在哈希表中使用它。Abseil 哈希映射使用的负载因子约为 0.9。

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

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

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

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

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

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

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

但由于事实证明我们只需要两位，因此将它们用于此信息的成本很高。我们可以尝试一个完整的字节，但其余位呢？在 Google 的实现中，哈希函数的前 53 位用于搜索带有元数据的单元格，哈希函数的低位在元数据中。

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

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

基准测试的主要问题是什么？它们通常不是在真实数据上进行的，而是在随机数上进行的。随机数的分布与真实数据不符。此外，通常情况下，没有考虑特定的场景。同样常见的是，他们不显示基准测试代码，只显示各种图表，使得无法重复基准测试。

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

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

以下结果基于包含大约 2,0714,865 个唯一值的 WatchId 列。这些值不适合 CPU 缓存，占用约 600 MB，强制访问主内存。此处的计时表示聚合所有值的总运行时间。

哈希表	时间 (秒)
ClickHouse 哈希映射	7,366 秒
Google DenseMap	10,089 秒
Abseil 哈希映射	9,011 秒
std::unordered_map	44,758 秒

如果我们看一下这个基准测试，我们会发现 ClickHouse 和哈希表远远领先于 std::unordered_map。为什么？因为，正如我所说，std::unordered_map 不是缓存本地的；特别是，此数据未放置在 Lx 缓存中。我们可以使用 perf stat 来查看以确认我们的假设，即 std::unordered_map 具有更多的缓存未命中，从而减慢了速度。

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

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

让我们进行一个稍微不同的基准测试，其中所有数据都进入缓存。在这种情况下，我们看到 std::unordered_map 不再像以前那样减速了。在这种情况下，我们使用 RegionID 列，该列具有来自一组 9040 个唯一值的重复值，这些值适合 Lx 缓存。

哈希表	时间 (秒)
ClickHouse 哈希映射	0.201 秒
Google DenseMap	0.261 秒
Abseil 哈希映射	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 Instrusive 库。下面我们展示了其中最重要的部分。我们创建一个侵入式列表并将其用作列表。事实上，我们在单元格中声明了指向下一个和上一个元素的指针，这足以让我们在单元格之上创建一个侵入式列表。

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 不会减速”连帽衫！