talk_concurrent_hashmap

发表于 更新于 分类于
深入解析 Folly 中 ConcurrentHashMap 和 AtomicHashMap 的底层实现原理，包括分片锁机制、无锁读取、CAS 操作、hazard pointer 内存回收等。

简介

Folly 是 Facebook 开源的 C++ 基础库，其中提供了两种高性能并发哈希表：

  • AtomicHashMap：基于 CAS + 开放寻址，适合 int32/int64 键的高并发场景
  • ConcurrentHashMap：基于分片锁 + hazard pointer，支持任意键值类型

本文深入解析两者的底层实现。

ConcurrentHashMap 架构

ConcurrentHashMap 是 Folly 中功能最完整的并发哈希表，与 std::unordered_map 接口相近，但线程安全。

模板参数

template <
    typename KeyType,
    typename ValueType,
    typename Hash = std::hash<KeyType>,
    typename KeyEqual = std::equal_to<KeyType>,
    typename Allocator = std::allocator<uint8_t>,
    uint8_t ShardBits = 8,   // 分片位数
    typename BucketT = folly::MicroLock,
    bool ApplyPriority = false
>
class ConcurrentHashMap;

关键参数：

  • ShardBits：控制分片数量，默认 8，即 256 个 Segment
  • BucketT：每个 bucket 的锁类型，默认用 MicroLock（4 字节自旋锁）

分片锁（Sharded Locking）设计

这是 ConcurrentHashMap 最核心的设计思想。

┌─────────────────────────┐
│   ConcurrentHashMap     │
│                         │
│  Segment[0]             │
│    ┌─────────────────┐  │
│    │ Bucket[0]  lock │  │
│    │ Bucket[1]  lock │  │
│    │ Bucket[2]  lock │  │
│    │      ...        │  │
│    └─────────────────┘  │
│  Segment[1]             │
│    ┌─────────────────┐  │
│    │ Bucket[0]  lock │  │
│    │ Bucket[1]  lock │  │
│    │      ...        │  │
│    └─────────────────┘  │
│  Segment[2..255]        │
└─────────────────────────┘

设计要点：

  1. 两级分片：ShardBits 决定 Segment 数量，每个 Segment 内再分 Bucket
  2. 默认 256 个 Segment：哈希值的高 ShardBits 位决定落到哪个 Segment，低位决定 Bucket
  3. 每 Bucket 一把锁：锁粒度细到 bucket 级别，最大程度减少竞争
  4. MicroLock：仅 4 字节的自旋锁，嵌入在 bucket 结构中，零额外内存开销

哈希值的使用

hash_value = Hash(key);

// 高 ShardBits 位 → Segment 索引
segment_idx = hash_value >> (64 - ShardBits);

// 剩余低位 → Bucket 索引（取模 Segment 内 bucket 数）
bucket_idx  = lower_bits % num_buckets_per_segment;

这样设计的好处是：同一个 Segment 内的 bucket 有相似的高位哈希值，理论上会竞争同一把 Segment 级别的资源，但实际的锁粒度在 Bucket 级，避免了热点。

并发操作实现

读取（find）

读取完全无等待（wait-free），不获取任何锁：

  1. 哈希定位到 Segment + Bucket
  2. 遍历 bucket 链表，原子读取节点
  3. 通过 hazard pointer 保护正在读取的节点不被回收
// 伪代码：读取路径
auto result = find(key);
// 1. 计算 hash
// 2. 定位 segment[bucket_idx]
// 3. 遍历链表，原子读每个节点的 key
// 4. 匹配成功 → 返回值或引用
// 5. 匹配失败 → 返回 end()
// 全程无锁！

读取路径不使用锁的关键在于 hazard pointer：读线程将正在访问的节点指针发布到 hazard pointer 列表，删除线程在回收节点前检查 hazard pointer，确保不会释放正在被读的节点。

插入（insert / insert_or_assign）

插入需要获取 bucket 级别的锁：

  1. 哈希定位到 Segment + Bucket
  2. 获取该 Bucket 的 MicroLock
  3. 遍历链表查找 key
    • 存在 → 更新 value（insert_or_assign 模式）
    • 不存在 → 创建新节点插入链表头部
  4. 释放锁
// 伪代码：插入路径
auto result = insert(key, value);
// 1. 计算 hash，定位 bucket
// 2. lock(bucket.microLock)
// 3. 遍历链表，查找 key
// 4. 如果存在 → 返回 {iterator, false}
// 5. 如果不存在 → new Node{key, value}，插入链表头
// 6. unlock(bucket.microLock)
// 7. 返回 {iterator, true}

删除（erase）

同样获取 bucket 锁，但涉及 hazard pointer 安全回收：

  1. 定位 Bucket，获取锁
  2. 遍历链表找到目标节点
  3. 从链表中摘除节点
  4. 释放锁
  5. 将节点放入 retire 列表（延迟回收）
  6. 当确定没有读线程持有该节点的 hazard pointer 时，安全释放内存
// 伪代码：删除路径
auto result = erase(key);
// 1. 定位 bucket，lock
// 2. 找到节点，从链表摘除
// 3. unlock
// 4. retire(node)  // 加入待回收列表
// 5. reclaim()      // 检查 hazard pointers，安全释放

assign_if_equal（原子条件更新）

这是 ConcurrentHashMap 的独特方法，允许原子地进行”如果当前值等于期望值，则更新为新值”：

// 如果 map[key] == expected，则 map[key] = desired
// 整个操作在锁保护下原子完成
auto result = map.assign_if_equal(key, expected, desired);

这在需要 CAS 语义的并发场景中非常实用，比如：

  • 状态机的原子状态转换
  • 引用计数的线程安全更新

Hazard Pointer 内存回收

传统并发哈希表的一个痛点：删除节点时，可能有读线程正在访问该节点。直接删除会导致 use-after-free。

ConcurrentHashMap 使用 hazard pointer 解决：

读线程                           删除线程
────────                        ────────
读取节点 A                      删除节点 A
↓                               ↓
hazptr.protect(&A)             从链表摘除 A
↓                               ↓
读取 A 的数据...                  retire(A) → 放入退休列表
↓                               ↓
hazptr.clear()                  扫描所有读线程的 hazard pointer
                                ↓
                                如果 A 不在任何 hazptr 中
                                ↓
                                delete A

关键点：

  • 读线程通过 hazard pointer 声明”我正在用这个节点”
  • 删除线程等待所有对节点的引用消失后才真正释放
  • 实现了安全的、无锁的读路径

AtomicHashMap 架构

AtomicHashMap 是 Folly 中另一种并发哈希表的实现，采用完全不同的设计哲学。

核心设计

AtomicHashMap 由多个 AtomicHashArray (AHA) 子表串联而成：

  • 初始只有一个 AHA
  • 填满后追加新的 AHA，形成子表链表
  • 元素永不移动：扩容通过追加而非 rehash
┌─────────────────┐     ┌─────────────────┐
│ AtomicHashArray │ →──→│ AtomicHashArray │ →──→ ...
│    (Submap 0)   │     │    (Submap 1)   │
│  [slot0]        │     │  [slot0]        │
│  [slot1]        │     │  [slot1]        │
│  ...            │     │  ...            │
└─────────────────┘     └─────────────────┘

AHA：开放寻址 + CAS

每个 AHA 是固定大小的开放寻址哈希表，核心操作都用 CAS 原子完成：

插入：

  1. 哈希取模定位到 slot
  2. CAS 将 slot 的 key 从 EMPTY 改为 LOCKED（特殊的哨兵值）
  3. CAS 成功 → 写入 value → 将 key 从 LOCKED 改为真实 key（解锁）
  4. CAS 失败 → 线性探测下一个 slot

查找（无锁）：

  1. 哈希定位 + 线性探测
  2. 读取 slot key，比较匹配 / 空 / 继续探测
  3. 完全无等待，因为元素始终处于有效状态

删除：

  1. 找到 slot
  2. CAS 将 key 改为 ERASED（墓碑值）
  3. 墓碑永不回收，这是该设计的最大代价

限制

特性 AtomicHashMap ConcurrentHashMap
键类型 仅 int32/int64 任意类型
删除后内存回收 永不回收（墓碑） Hazard Pointer 回收
扩容方式 追加子表（性能递减） 可重新分配
读并发 Wait-free Wait-free
写并发 Key 级 CAS Bucket 级锁
迭代器稳定性 永远有效 Hazard Pointer 保证

为什么 AtomicHashMap 更快（特定场景）

  • 读路径无需任何原子指令，直接内存读取
  • 写路径仅 CAS，无锁开销
  • 无内存分配/释放（墓碑机制）
  • 适合键不删除或删除很少的场景

性能对比

以下是 8 线程、100 万条目的基准对比：

操作 ConcurrentHashMap AtomicHashMap tbb::concurrent_hash_map
插入（50% 负载） — 0.19 μs ~0.5 μs
查找（50% 负载） — 0.05 μs ~0.15 μs
读并发 Wait-free Wait-free 有锁

AtomicHashMap 比 tbb::concurrent_hash_map 快 2-5 倍。

使用建议

选 ConcurrentHashMap 的场景：

  • 键类型不是整数
  • 需要频繁增删
  • 需要 assign_if_equal 原子条件更新
  • 需要类似 std::unordered_map 的接口

选 AtomicHashMap 的场景：

  • 键是 32/64 位整数
  • 删除极少或从不删除
  • 对读/写延迟要求极高的场景
  • 能接受固定的哨兵键值（EMPTY、LOCKED、ERASED）

总结

Folly 的两套并发哈希表体现了两种经典的并发设计思路：

  • ConcurrentHashMap：分片锁 + hazard pointer，通用性强，适合大多数场景
  • AtomicHashMap：CAS + 开放寻址 + 追加子表，极致性能，适用于特定约束场景

共同的设计精髓是 读路径无锁：通过精心设计的并发协议（hazard pointer / 原子状态机），让最频繁的读操作完全不阻塞，从而在高并发下获得近乎线性的扩展性。