13. 并发数据结构：无锁队列、读写锁、RCU、并发哈希表

并发编程，说白了就是让多个线程同时干活，还不打架。但打架是常态，不打架才需要技术。我早年做网络中间件的时候，一个多线程日志模块让我调了整整两周，最后发现是锁竞争把性能拖垮了。从那以后，我对并发数据结构就特别上心。

今天咱们聊四个核心的并发数据结构：无锁队列、读写锁、RCU、并发哈希表。每个都是实战中高频出现的利器。

13.1 无锁队列：CAS 与 ABA 问题

无锁队列，核心思想就是不用互斥锁，靠原子操作来保证线程安全。最常见的实现是基于 CAS（Compare-And-Swap）。

CAS 操作长这样：

bool atomic_compare_exchange_strong(atomic_int* p, int* expected, int desired);

它会比较 *p 和 expected，如果相等就把 *p 改成 desired，返回 true；否则把 *p 写回 expected，返回 false。整个过程是原子的。

一个简单的无锁队列（单生产者单消费者）可以这样写：

#include <stdatomic.h>

typedef struct {
    int data;
} node_t;

typedef struct {
    atomic_int head;
    atomic_int tail;
    node_t* buffer;
    int capacity;
} lockfree_queue_t;

void lockfree_queue_init(lockfree_queue_t* q, int cap) {
    q->head = 0;
    q->tail = 0;
    q->buffer = (node_t*)malloc(cap * sizeof(node_t));
    q->capacity = cap;
}

int lockfree_queue_push(lockfree_queue_t* q, int val) {
    int tail = atomic_load(&q->tail);
    int head = atomic_load(&q->head);
    if (tail - head >= q->capacity) return -1; // 队列满
    q->buffer[tail % q->capacity].data = val;
    atomic_store(&q->tail, tail + 1);
    return 0;
}

int lockfree_queue_pop(lockfree_queue_t* q, int* val) {
    int head = atomic_load(&q->head);
    int tail = atomic_load(&q->tail);
    if (head >= tail) return -1; // 队列空
    *val = q->buffer[head % q->capacity].data;
    atomic_store(&q->head, head + 1);
    return 0;
}

嗯，这里要注意：上面的代码只适用于单生产者单消费者场景。多生产者多消费者要复杂得多，需要处理 ABA 问题。

解决 ABA 问题，常见做法是使用带标签的指针（tagged pointer），每次 CAS 同时比较地址和版本号。

13.2 读写锁：读多写少的场景利器

读写锁，说白了就是允许多个线程同时读，但写的时候只能有一个线程，且不能有读者。

为什么需要它？你想想看，很多业务场景是读多写少。比如配置表，99% 的时间在查询，只有 1% 的时间在更新。如果用普通互斥锁，读线程之间也会互相阻塞，白白浪费 CPU。

POSIX 线程库提供了读写锁：

#include <pthread.h>

pthread_rwlock_t rwlock = PTHREAD_RWLOCK_INITIALIZER;

// 读锁
pthread_rwlock_rdlock(&rwlock);
// 读取共享数据...
pthread_rwlock_unlock(&rwlock);

// 写锁
pthread_rwlock_wrlock(&rwlock);
// 修改共享数据...
pthread_rwlock_unlock(&rwlock);

读写锁的性能对比：

场景	普通互斥锁	读写锁
读多写少（9:1）	慢	快
读写均衡（5:5）	中等	中等
写多读少（1:9）	快	慢（写锁竞争）

13.3 RCU：读端无锁的终极方案

RCU（Read-Copy-Update）是 Linux 内核里的一把利器。它的核心思想是：读操作完全不加锁，写操作通过“复制-修改-替换”的方式完成，然后等待所有读者退出后再释放旧数据。

为什么能做到读端无锁？因为 RCU 利用了“指针赋值是原子的”这个特性。读者只需要读取一个指针，不需要任何锁。写者先复制一份数据，修改，然后原子地更新指针。

一个简化的 RCU 示例：

#include <stdatomic.h>
#include <stdlib.h>

typedef struct {
    int key;
    int value;
} data_t;

atomic_intptr_t g_ptr; // 全局指针，指向当前有效数据

// 读操作：无锁
int rcu_read(int key) {
    data_t* p = (data_t*)atomic_load(&g_ptr);
    // 这里假设 key 匹配，实际需要遍历
    return p->value;
}

// 写操作：复制-修改-替换
void rcu_update(int key, int new_val) {
    data_t* old = (data_t*)atomic_load(&g_ptr);
    data_t* new_data = (data_t*)malloc(sizeof(data_t));
    *new_data = *old; // 复制
    new_data->value = new_val; // 修改
    atomic_store(&g_ptr, (intptr_t)new_data); // 替换
    // 等待所有读者退出（synchronize_rcu）
    free(old); // 释放旧数据
}

RCU 的适用场景：

• 读操作极其频繁，写操作极少（如路由表、配置表）
• 对读延迟要求极高，不能容忍任何锁开销
• 数据结构更新不频繁，但更新时允许短暂阻塞

我曾经在一个金融交易系统中使用 RCU 管理订单簿，读延迟从 200ns 降到了 50ns，效果非常明显。

13.4 并发哈希表：分桶锁与无锁设计

并发哈希表，说白了就是让多个线程同时操作哈希表，不打架。最常见的实现是分桶锁（bucket lock）——每个桶一把锁，不同桶的线程可以并行操作。

分桶锁的代码骨架：

#include <pthread.h>
#include <stdlib.h>

#define BUCKET_COUNT 1024

typedef struct entry {
    int key;
    int value;
    struct entry* next;
} entry_t;

typedef struct {
    entry_t* head;
    pthread_mutex_t lock;
} bucket_t;

bucket_t hashtable[BUCKET_COUNT];

void hashtable_init() {
    for (int i = 0; i < BUCKET_COUNT; i++) {
        hashtable[i].head = NULL;
        pthread_mutex_init(&hashtable[i].lock, NULL);
    }
}

int hashtable_insert(int key, int value) {
    int idx = key % BUCKET_COUNT;
    pthread_mutex_lock(&hashtable[idx].lock);
    // 插入或更新链表
    entry_t* e = hashtable[idx].head;
    while (e) {
        if (e->key == key) {
            e->value = value;
            pthread_mutex_unlock(&hashtable[idx].lock);
            return 0;
        }
        e = e->next;
    }
    entry_t* new_e = malloc(sizeof(entry_t));
    new_e->key = key;
    new_e->value = value;
    new_e->next = hashtable[idx].head;
    hashtable[idx].head = new_e;
    pthread_mutex_unlock(&hashtable[idx].lock);
    return 1;
}

分桶锁的优点是简单、可控。缺点是如果哈希函数不好，某个桶的链表太长，性能会下降。

更高级的方案是无锁哈希表。它结合了无锁链表和 CAS 操作，实现起来相当复杂。我建议除非性能要求极其苛刻，否则先用分桶锁。

13.5 知识体系总览

下面这张图总结了四种并发数据结构的核心逻辑和适用场景：

13.6 实战中的选择

说了这么多，到底怎么选？我个人的经验是：

• 先跑起来，再优化。不要一开始就上无锁方案，先用分桶锁或读写锁把功能做对。
• 测量是王道。用 perf 或火焰图看看锁竞争到底占了多少时间。有时候瓶颈根本不在锁上。
• RCU 是双刃剑。它读端快，但写端要等待所有读者退出，延迟不稳定。实时系统慎用。
• 无锁队列适合流水线。如果数据流是单向的，无锁队列能发挥最大威力。

---

公众号:蓝海资料掘金营，微信deep3321