每周性能技巧 #26：借助哈希表分析来修复问题

本节阅读量:

本文翻译自 Abseil 官网的 Performance Tip of the Week #26: Fixing things with hashtable profiling。

原文发布于 2020 年 5 月 20 日，作者 Chris Kennelly 和 Zie Weaver，更新于 2025 年 7 月 16 日。

Matt Kulukundis 在他的 2019 CppCon 演讲中讨论过：单靠 CPU profile 识别一个“慢”的哈希表并不容易。Abseil 的 C++ 哈希表内置了 profiler。本篇介绍它可以提供哪些关于哈希函数质量和哈希冲突的洞见，让这些问题在规模化环境中变得可见。我们也会看几个案例：这些信息如何用于提升 Google 生产 fleet 的效率。

开始分析

我们可以从生产环境中的服务器收集哈希表 profile，并加载到 pprof 中。

这些数据可以用于识别有问题的哈希表。糟糕的哈希表通常来自低熵哈希函数，或者把同一个哈希函数同时用于表内查找和跨实例分片。可以通过下面方式处理：

使用 absl::Hash 提供混合良好的哈希函数。
通过给哈希加盐，使用不同的哈希函数。

找到固定不变的位

固定不变的位，是指在每个哈希值中都从不变化的 bit。自然地，固定 bit 越多，冲突概率就会以指数级上升。

下面通过几个例子展示固定哈希位的来源。

案例研究：`InternalSubscriber::MessageReceived`

这个函数在搜索固定 bit 时出现了多次。它位于一个被许多服务器使用的客户端库中。

我们看到它向名为 pending_ack_callbacks 的索引数组插入数据：

1

pending_ack_callbacks_[i].shard.insert(ack_cb, ack_callback);

它的定义是一个哈希表数组：

1
2
3


struct {
  ABSL_CACHELINE_ALIGNED absl::flat_hash_map<Closure*, Closure*> shard;
} pending_ack_callbacks_[kNumPendingAckShards];

其中 kNumPendingAckShards = 256。可疑的是，我们看到的固定 bit 是 0xff。分片选择基于哈希值：

1
2
3
4
5


/* static */
int InternalSubscriber::ClosureAddressToShard(Closure *address) {
  absl::flat_hash_set<Closure*>::hasher h;
  return h(address) % kNumPendingAckShards;
}

对于任意一个分片内的哈希表，低位 bit 按定义都是相同的。哈希表又使用这些相同 bit 来决定新值插入位置，因此冲突会导致性能变差。

修复方式是给用于分片的哈希加盐：

1
2


absl::Hash<std::pair<Closure*, int>> h;
return h(std::pair(address, 42)) % kNumPendingAckShards;

这种加盐技巧为分片查找和表内查找提供了不同的哈希函数。它让这个库中的插入成本减半。

案例研究：`ProcessWatchDone`

在另一个库中，我们发现了一个异常的固定 bit 模式：0x4030802800000000。修复之前，代码中有这样的声明：

1
2


typedef absl::node_hash_map<NamespaceKey, int64, NamespaceKeyHash>
    NsKeyRequestIdMap;

因为代码之前使用 std::unordered_map，而 NamespaceKey 不能用 std::hash 哈希，所以它指定了自定义 hasher NamespaceKeyHash。这个 hasher 使用了 GoodFastHash：

1
2
3


size_t NamespaceKeyHash::operator()(const NamespaceKey& ns_key) const {
  return GoodFastHash<NamespaceKey>()(ns_key);
}

NamespaceKey 是一对 Cord。但 GoodFastHash 没有为 std::pair 正确混合 bit：

1

typedef std::pair<absl::Cord, absl::Cord> NamespaceKey;

迁移到 absl::Hash 后，std::pair 的 bit 混合质量得到改善，这个问题也随之修复。

找到冲突很多的表

当哈希表冲突更多时，查找某个元素需要做更多 probe。冲突更多时，查找性能会从 O(1) 退化到 O(n)。所需内存加载也可能无法命中缓存，从而伤害性能。

理想 probe length 是 0，意味着第一次查找的位置正好就是目标对象。如果平均 probe length 大于 0.1，说明表进行 probe 的频率已经高于应有水平，大约 10% 的 key 遇到了冲突。平均 probe length 可以通过 total_probe_length 除以 num_erases 和 size 的和来计算，这两个数字共同捕捉了已经插入表中的元素总数。

案例研究：`PortMapperImpl::UpdateActiveMap`

这个案例显示 max probe length 为 133，平均 probe length 为 8.4。很多查找实际上已经接近线性搜索。

我们可以看一下修改表的位置：

1
2
3


// 分配新的 ConnLabel 元素并更新计数器。
iter = active_map_->find_or_insert(*flow);
iter->second = new ConnLabel;

active_map_ 的定义指向：

1
2
3


typedef priority_hash_map<IpFlow,
                          ConnLabel*,
                          IpFlowPrioritizer> ClientPortMap;

priority_hash_map 是包装 SwissMap 的自定义类型，但默认参数并不理想：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


template<class _Key,
         class _Val,
         class _PriorityFunc,
         class _PriorityKey = int,
         class _PriorityHash = hash<_PriorityKey>,
         class _PriorityEqual = std::equal_to<_PriorityKey>,
         class _PriorityCompare = std::less<_PriorityKey>,
         class _KeyHash = hash<_Key>,
         class _KeyEqual = std::equal_to<_Key> >
class priority_hash_map {
 public:
  typedef absl::flat_hash_map<_Key, _Val, _KeyHash, _KeyEqual> hash_map_type;
  ...

_PriorityHash 和 _KeyHash 使用 hash<>，后者提供了一个自定义哈希特化：

1
2
3
4
5
6
7


template<> struct hash<IpFlow> {
  size_t operator()(const IpFlow& flow) const {
    return flow.remote_ip()
           (flow.proto() << 24) ^ flow.local_port() ^
           (flow.remote_port() << 16);
 }
};

这些被 xor 到一起的 bit 可能导致混合很差。例如，只需要一个 IP 10.0.0.33 使用端口 2038，另一个 IP 10.0.0.32 使用端口 2039，就可能产生冲突。为了修复它，我们为 IpFlow 实现了 AbslHashValue，使 priority_hash_map 可以切换到 absl::Hash：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


// 允许这个类型作为哈希表 key 使用。
template<typename H>
friend H AbslHashValue(H h, const IpFlow& flow) {
 return H::combine(
     std::move(h),
     flow.remote_ip(),
     flow.proto(),
     flow.local_port(),
     flow.remote_port());
}

哈希表统计信息

对于每个被 profile 的哈希表，我们会在若干 tag 中记录统计信息：

capacity 表示哈希表的精确容量。
size 是哈希表当前元素数量。
probe length 统计信息（max_probe_length、total_probe_length）告诉我们，为了找到元素额外做了多少次查找。在理想哈希表中，第一次查找就找到目标元素（probe length = 0）。如果存在冲突，probe length 会更高。max_probe_length 表示哈希表中任意元素的最坏 probe length。total_probe_length 是表中所有元素 probe length 的总和。
stuck_bits 是一个 bitmask，表示表中哈希码有哪些 bit 只见过一个值（全为 0 或全为 1）。对于好的哈希函数，任何大于 10 个元素的表都应该为 0。它实现为“所有哈希的运行时 &”与“所有哈希的运行时 | 的取反”再取 |。固定 bit 表明哈希函数可能没有提供足够熵。
num_rehashes 记录表 rehash 的次数。用接近真实大小的合适值调用 reserve 可以减少 rehash。
max_reserve 记录这个实例传给 reserve 的最大大小；如果从未调用则为 0。这可以用于识别过大的表（size << capacity），因为它们曾以过大的大小调用 reserve。类似地，rehash 很多的表可以通过用足够大小调用 reserve 节省 rehash 成本。
num_erases 是自上次 rehash 以来从哈希表删除的元素数量。num_erases 与 size 的和表示自上次 rehash 以来加入表中的元素数量。
inline_element_size 是数组 flat 部分中元素的大小。对于 flat 哈希表，这是键值对大小；对于 node 哈希表，这是指向键值对的指针大小。
key_size 等于表的 sizeof(key_type)。
value_size 等于表的 sizeof(value_type)。在 set 中，sizeof(key_type) == sizeof(value_type)。在 map 中，value_type 同时保存 key_type 和 mapped_type，并包含合适的对齐填充。
soo_capacity 是表的小对象优化（SOO）中可容纳的元素数量。
table_age 报告表的年龄，单位是微秒。

在单元测试中检测糟糕哈希表

一个额外防线是：我们可以在运行测试时启用 profiler。这需要带上环境变量 ABSL_CONTAINER_FORCE_HASHTABLEZ_SAMPLE=1。

由于这会触发测试失败，它的告警阈值相当高。单元测试可能不会向哈希表插入足够多的元素来产生冲突。

结语

仅从 CPU profile 找到哈希表问题很困难，因为机会点可能不会在 profile 中显眼出现。SwissMap 内置的哈希表 profiling 让我们能够观察多种哈希表属性，从而找到低质量哈希函数、冲突或过度 rehash。

上一篇：每周性能技巧 #98：测量也有投资回报率

下一篇：每周性能技巧 #95：远距离的诡异作用

本节目录