高并发内存池优化：基数树替代哈希表解决锁竞争

1. 高并发内存池性能瓶颈分析

在构建高并发内存池时，PageCache层的锁竞争问题往往成为系统性能的主要瓶颈。传统实现中，我们通常使用哈希表来维护页ID到Span的映射关系，这种设计在单线程环境下表现良好，但在高并发场景下会暴露出严重问题。

1.1 锁竞争问题的本质

当多个线程同时访问PageCache时，由于哈希表结构的特性，我们必须对整个数据结构加锁。这种粗粒度的锁机制导致：

1. 任何查找操作（get）都需要获取锁，即使只是读取数据
2. 修改操作（set）会阻塞所有其他访问
3. 线程在等待锁释放时处于空闲状态，CPU资源被浪费

特别是在内存分配/释放频繁的场景下，这种锁竞争会导致线程频繁切换，系统吞吐量急剧下降。我在实际测试中发现，当并发线程数超过4个时，性能下降幅度可达50%以上。

1.2 哈希表方案的局限性

传统哈希表方案存在几个无法回避的问题：

• 写操作导致结构变化：扩容时的rehash操作会改变整个数据结构
• 读写互斥：即使使用读写锁，写操作仍会阻塞所有读操作
• 缓存不友好：哈希表的随机访问特性导致缓存命中率低

这些问题在高并发环境下会被放大，使得哈希表成为系统性能的瓶颈。我们需要一种能够实现真正无锁访问的数据结构来替代哈希表。

2. 基数树原理与实现

2.1 基数树的核心思想

基数树（Radix Tree）是一种多叉树结构，特别适合用于构建静态的键值映射。它的核心优势在于：

1. 结构稳定性：一旦建立，树的结构不会改变
2. 读写分离：读操作完全不需要加锁
3. 确定性访问路径：通过键值可以直接计算出访问路径

在TCMalloc的实现中，Google工程师设计了三种不同层级的基数树模板，分别适用于不同规模的地址空间。我们的内存池主要使用前两种：

• 单层数组（PageMap1）
• 双层基数树（PageMap2）

2.2 单层基数树实现

单层基数树本质上是一个大数组，适用于地址空间较小的场景（通常32位系统）：

cpp复制template <int BITS>
class TCMalloc_PageMap1 {
private:
    static const int LENGTH = 1 << BITS