高性能数组支持的 LRU 哈希表 并发 LRU 哈希表的优化: - 多核心可扩展性 - 可预测的尾延迟 - NUMA 架构 - 零运行时分配 目录 - 问题: 标准库瓶颈 - 解决方案: 核心架构与算法 - 基准测试与扩展性能 - 该表何时不适合 - 快速开始 - API 概述 - 项目结构 - 构建测试代码 - 结论与未来 - 硬件推断 - 许可证与贡献 这是一个为严格的系统编程工作负载（如缓存层、网络基础设施和内核组件）设计的高性能并发 LRU 哈希表。通过利用基于分片的并行性和友好的内存布局，实施在标准库容器在竞争下会降级的环境中提供高吞吐率。 核心架构亮点 - 零运行时分配: 预先分配的扁平数组消除了堆碎片和操作系统级别的锁停顿。 - 自定义 TTAS 自旋锁: 替代 std::shared_mutex，消除操作系统上下文切换，实现 14 倍以上的吞吐量和亚微秒的尾延迟。（注意: 用户模式使用自定义 TTAS 自旋锁以提高原生速度，而内核模式依赖于 EX_PUSH_LOCK）。 - 分片架构: 消除了全局锁车队，随着物理 CPU 核心计数线性扩展。 - NUMA 感知内存: 在物理 CPU 插槽间分配分片，以最大化内存控制器带宽。 - 无锁销毁: 有效载荷在同步边界外显式销毁，确保平坦的尾延迟。 - 惰性 LRU 提升: 可调的“安全区”绕过热读取时的独占锁提升，带来约 20% 的吞吐量提升。 - 自定义分配器（用户模式）: 支持用于特定领域内存管理的模板注入分配器。 - 双环境就绪: 完整的跨平台用户模式支持以及专用的 Windows 10+ 内核实现（IRQL < DISPATCH_LEVEL）。 该实现优先考虑机械同情、缓存局部性、锁的可扩展性以及可预测的内存行为，使其适用于以下严格环境: - 高频交易 (HFT) 基础设施 - 存储子系统缓存 - 实时网络路由 - 内核/驱动组件 - 高吞吐量网络服务器 该实现为插入、查找和移除提供 O(1) 的平均时间操作，同时保持严格或概率的最近最少使用 (LRU) 驱逐策略。 问题: 标准库瓶颈 典型的并发 LRU 实现（例如，结合 std::unordered_map + std::list 由全局 std::shared_mutex 保护）在现代高核心 CPU 上存在严重的架构缺陷: - 全局锁争用: 单个锁创建了灾难性的“锁车队”，添加线程实际上降低了总体吞吐量。 - 指针追逐: 跨堆节点的遍历破坏了 L1/L2 缓存局部性。 - 分配器开销: 每次插入/驱逐都会触发堆分配/释放 (new/delete)，导致内存碎片和操作系统级别的锁停顿。 - 虚假共享: 不对齐的内存结构导致相邻的 CPU 核心使彼此的 L1 缓存行失效，默默破坏性能。 解决方案: 核心架构与算法 该项目通过分片、扁平数组内存管理和无锁销毁技术解决标准库瓶颈。该图展示了一个 LRU 哈希表的架构，通过将数据分区为独立、缓存对齐的分片，消除了全局锁争用。每个分片自主操作，拥有自己的独占 TTAS 自旋锁、元数据计数器以及包含桶和节点数组的连续“巨型块”内存。在这些数组中，哈希冲突链和双向链路 LRU 队列都是使用 32 位数组索引构建，而不是标准的 64 位指针，这将结构内存开销减半，并在热路径操作期间提高 L1/L2 缓存局部性。整体上，该表被分割为独立的分片，每个分片管理自己的哈希表和 LRU 链: