Folly原子哈希：原子哈希表与并发映射实现

【免费下载链接】folly An open-source C++ library developed and used at Facebook. 项目地址: https://gitcode.com/GitHub_Trending/fol/folly

概述

在现代高并发系统中，传统哈希表往往成为性能瓶颈。Facebook开发的Folly库提供了AtomicHashArray和AtomicHashMap两个高性能并发哈希容器，专为多线程环境设计，提供无锁（lock-free）查找和原子插入操作。

核心设计理念

原子操作基础

Folly原子哈希基于CAS（Compare-And-Swap）原子操作实现线程安全，避免了传统互斥锁的开销：

// 核心CAS操作示例
inline bool tryLockCell(value_type* const cell) {
  KeyT expect = kEmptyKey_;
  return cellKeyPtr(*cell)->compare_exchange_strong(
      expect, kLockedKey_, std::memory_order_acq_rel);
}

内存模型

使用std::memory_order内存序保证数据一致性：

• memory_order_acquire: 保证后续读操作不会重排序到之前
• memory_order_release: 保证前面的写操作不会重排序到之后
• memory_order_acq_rel: 结合acquire和release语义

AtomicHashArray：基础构建块

核心特性

• 固定大小: 初始化后容量不可变
• 无锁查找: 完全等待自由的查找操作
• 原子插入: 使用CAS保证插入的原子性
• 高效内存: 连续内存布局减少缓存失效

数据结构定义

template <
    class KeyT,
    class ValueT,
    class HashFcn = std::hash<KeyT>,
    class EqualFcn = std::equal_to<KeyT>,
    class Allocator = std::allocator<char>,
    class ProbeFcn = AtomicHashArrayLinearProbeFcn,
    class KeyConvertFcn = Identity>
class AtomicHashArray {
  // 核心成员变量
  const size_t capacity_;
  const KeyT kEmptyKey_;
  const KeyT kLockedKey_;
  const KeyT kErasedKey_;
  ThreadCachedInt<uint64_t> numEntries_;
  value_type cells_[0]; // 柔性数组
};

探针策略

Folly提供两种探针策略：

// 线性探针
struct AtomicHashArrayLinearProbeFcn {
  inline size_t operator()(size_t idx, size_t /* numProbes */, size_t capacity) const {
    idx += 1;
    return FOLLY_LIKELY(idx < capacity) ? idx : (idx - capacity);
  }
};

// 二次探针  
struct AtomicHashArrayQuadraticProbeFcn {
  inline size_t operator()(size_t idx, size_t numProbes, size_t capacity) const {
    idx += numProbes; // 二次探测
    return FOLLY_LIKELY(idx < capacity) ? idx : (idx - capacity);
  }
};

AtomicHashMap：可扩展的并发映射

架构设计

核心特性对比

特性	AtomicHashArray	AtomicHashMap
容量	固定	可动态增长
性能	更高	相对较低
内存	连续分配	分段分配
使用场景	容量确定的高性能场景	需要扩展的通用场景

子映射管理

// 子映射索引编码
static inline uint32_t encodeIndex(uint32_t subMap, uint32_t subMapIdx) {
  return (subMap << kSubMapIndexShift_) | 
         (subMapIdx & kSubMapIndexMask_);
}

// 子映射数组
std::atomic<SubMap*> subMaps_[kNumSubMaps_];
std::atomic<uint32_t> numMapsAllocated_;

关键算法实现

查找算法

template <typename LookupKeyT, typename LookupHashFcn, typename LookupEqualFcn>
SimpleRetT findInternal(const LookupKeyT key) {
  size_t idx = keyToAnchorIdx<LookupKeyT, LookupHashFcn>(key);
  size_t numProbes = 0;
  
  while (true) {
    value_type* cell = &cells_[idx];
    KeyT cellKey = acquireLoadKey(*cell);
    
    if (cellKey == kEmptyKey_) {
      return SimpleRetT(idx, false);
    }
    if (cellKey != kLockedKey_ && 
        LookupEqualFcn()(cellKey, key)) {
      return SimpleRetT(idx, true);
    }
    
    idx = ProbeFcn()(idx, ++numProbes, capacity_);
  }
}

插入算法

template <typename LookupKeyT, typename LookupHashFcn, 
          typename LookupEqualFcn, typename LookupKeyToKeyFcn, typename... ArgTs>
SimpleRetT insertInternal(LookupKeyT key, ArgTs&&... vCtorArgs) {
  size_t idx = keyToAnchorIdx<LookupKeyT, LookupHashFcn>(key);
  size_t numProbes = 0;
  
  while (true) {
    value_type* cell = &cells_[idx];
    KeyT cellKey = acquireLoadKey(*cell);
    
    if (cellKey == kEmptyKey_) {
      if (tryLockCell(cell)) {
        // 成功获取锁，执行插入
        ::new (&cell->second) ValueT(std::forward<ArgTs>(vCtorArgs)...);
        KeyT newKey = LookupKeyToKeyFcn()(key);
        unlockCell(cell, newKey);
        numEntries_.increment(1);
        return SimpleRetT(idx, true);
      }
      // 锁竞争失败，重试
      continue;
    }
    
    if (cellKey != kLockedKey_ && LookupEqualFcn()(cellKey, key)) {
      return SimpleRetT(idx, false); // 键已存在
    }
    
    idx = ProbeFcn()(idx, ++numProbes, capacity_);
    if (numProbes >= capacity_) {
      return SimpleRetT(capacity_, false); // 表已满
    }
  }
}

性能优化技术

线程本地计数

// 使用ThreadCachedInt减少原子操作开销
ThreadCachedInt<uint64_t> numEntries_; // 成功插入计数
ThreadCachedInt<uint64_t> numPendingEntries_; // 待处理插入计数

// 定期刷新线程本地计数到主计数器
size_t size() const {
  return numEntries_.readFull() - numErases_.load(std::memory_order_relaxed);
}

内存访问优化

// 避免昂贵的模运算
inline size_t keyToAnchorIdx(const LookupKeyT k) const {
  const size_t hashVal = LookupHashFcn()(k);
  const size_t probe = hashVal & kAnchorMask_;
  return FOLLY_LIKELY(probe < capacity_) ? probe : hashVal % capacity_;
}

使用示例

基本用法

#include <folly/AtomicHashMap.h>

// 创建原子哈希映射
folly::AtomicHashMap<uint64_t, std::string> map(1000);

// 并发插入
std::thread t1([&] {
  map.insert(1, "value1");
});

std::thread t2([&] {
  map.insert(2, "value2");  
});

t1.join();
t2.join();

// 安全查找
auto it = map.find(1);
if (it != map.end()) {
  std::cout << "Found: " << it->second << std::endl;
}

高级特性使用

// 使用不同的键类型进行查找
struct CustomHash {
  size_t operator()(const std::string_view& sv) const {
    return std::hash<std::string_view>()(sv);
  }
};

struct CustomEqual {
  bool operator()(uint64_t stored, const std::string_view& lookup) const {
    return std::to_string(stored) == lookup;
  }
};

// 使用自定义比较函数
auto it = map.find<std::string_view, CustomHash, CustomEqual>("1");

性能基准测试

根据Folly官方测试数据（8线程，100万次操作）：

负载因子	内存效率	插入时间(μs)	查找时间(μs)
50%	50%	0.19	0.05
85%	85%	0.20	0.06
90%	90%	0.23	0.08
95%	95%	0.27	0.10

最佳实践

1. 容量规划

// 根据预期元素数量和负载因子计算初始容量
size_t expectedElements = 1000000;
double targetLoadFactor = 0.75;
size_t initialCapacity = expectedElements / targetLoadFactor;

folly::AtomicHashMap<uint64_t, Data> map(initialCapacity);

2. 键选择策略

• 使用原生32位或64位整数类型
• 避免使用需要复杂哈希计算的类型
• 确保空键、锁定键和删除键的值唯一

3. 错误处理

try {
  auto result = map.insert(key, value);
  if (!result.second) {
    // 处理键冲突
  }
} catch (const folly::AtomicHashMapFullError& e) {
  // 处理映射已满的情况
}

适用场景

推荐使用场景

• 高并发计数器: 需要原子递增的统计场景
• 对象缓存: 线程安全的对象存储和检索
• ID映射: 整数ID到对象的快速映射
• 实时数据处理: 低延迟的并发数据访问

不适用场景

• 需要频繁删除和内存回收的场景
• 键类型复杂的场景（推荐使用std::unordered_map）
• 需要精确容量控制的场景

总结

Folly的原子哈希容器为C++高并发编程提供了强大的工具集。AtomicHashArray提供极致的性能但容量固定，而AtomicHashMap在保持高性能的同时支持动态扩展。通过精心设计的无锁算法、内存访问优化和线程本地计数等技术，这些容器在多线程环境中表现出色。

选择合适的哈希容器需要根据具体的性能要求、容量需求和并发模式来决定。对于大多数高并发应用场景，AtomicHashMap提供了最佳的性能和灵活性的平衡。

【免费下载链接】folly An open-source C++ library developed and used at Facebook. 项目地址: https://gitcode.com/GitHub_Trending/fol/folly