RCU设计原理

[toc]

概要

RCU全名 Read, Copy, Update

是一种针对多线程读多写少的数据的更新方法

它的读性能高于读写锁和自旋锁

通过牺牲写性能，让读性能最大化

rcu-performence_cmp

设计

std::atomic<node*> head;

Reader

原子遍历链表

node* p = head.load(std::memory_order_acquire);
do_search(p);

Writer

原子更新需要修改的节点

写入需要加mutex lock，避免多个线程冲突修改数据结构

mutex_lock();
node* new_node = new node(…);
new_node->next =
head.load(std::memory_order_relaxed)->next;
head.store(new_node, std::memory_order_release);

rcu-write

旧版本节点内存回收

可以通过share_pointer来管理每个节点

• 优点，写的速度比较快，不会阻塞
• 缺点：频繁更新原子计算，导致读性能下降

通过以版本号为单位来做引用计数

• 每次更新节点后，版本号自增一
• 每次需要读，都对对应的版本的引用计数加一
• 读完需要释放，把对应版本的引用计数减一
• gc时判断历史版本的计数是不是为零，为零则可以回收对应版本的内存

代码如下：

Reader代码

每次操作数据时需要调用rcu_read_lock，来把对应版本的引用加一

操作完数据后需要调用rcu_read_unlock，来把对应版本的引用减一

rcu_read_lock();
node* p = head.load(std::memory_order_acquire);
do_search(p);
rcu_read_unlock();

lock和unlock的实现如下：

std::atomic<unsigned long> generation;
std::atomic<unsigned long> refcount[max_generations];
class handle_t {…}; // Contains reader generation
handle_t rcu_read_lock() {
 size_t cg=generation;
 ++refcount[cg];
 return handle_t(cg);
}
void rcu_read_unlock(handle_t handle) {
 --refcount[handle.get()];
}

Writer代码

内存回收需要判断旧版本的引用计数是否为零

为零则回收

std::atomic<unsigned long> generation;
std::atomic<unsigned long> refcount[max_generations];
std::queue<data_t*> garbage[max_generations];
unsigned long last_gc_gen = 0;
void synchronize_rcu() {
 unsigned long last_gen = generation++;
 while (last_gc_gen < last_gen) {
 while (refcount[last_gc_gen] > 0) wait();
 delete_garbage(garbage[last_gc_gen]);
 ++last_gc_gen;
 }
}

某线程长时间持有节点的内存

需要有超时策略，超时则强制回收内存，回收后的内存不做delete操作，而是复用到新版本的节点，在读操作后，需要判断内存是否已被修改，如果修改了，则需要redo

reader：

do {
    rcu_read_lock();
    node* p = head.load(std::memory_order_acquire);
    do_search(p);
} while(rcu_read_unlock());

多线程（读线程）共享一个原子变量带来的性能问题

通过cache line对齐，减少伪共享带来的性能问题

struct alignas(64) GenHash {
    std::atomic<unsigned long> ref_count;
};
std::atomic<unsigned long> generation;
vector<GenHash> refcount[max_generations];

性能对比

	RCU	Atomic shared_ptr
Readers	fast	slow
Writers	slow	fast
Reclamation	blocking	lock-free
Garbage	blocking	lock-free
Ease of use	very easy	easy

RCU在不同场景下的应用选择比较

rcu-use