前段时间做系统重构，需要一个快速的本地缓存，类似于黑名单，读多写少的那种。
之前一直用的是哈希表加读写锁的方案，如果出现大规模的写操作，会导致读操作被阻塞。
想找一个更高效的ag真人游戏的解决方案，最好是无锁。
linux kernel中的rcu
以前听说过radix tree，linux用它来管理路由表，和我面临的场景有些类似，相信linux选用的肯定是高效的。所以打算研究一下，找一些启发。
研究时发现使用的是radix tree rcu来解决的。感觉推开了新世界的大门。
以链表为例，通过无锁操作可以无锁的更新链表，如图：
初始链表
申请新节点内存
复制要更新的节点
修改next指针
修改新节点中的内容
将其插入链表
以上所有操作都不需要加锁，但是有一个问题，何时可以释放p指向的节点？因为不确定是否还有其他“线程”在读这块内存。
这好像是一个内存回收的问题，在带有gc的语音中，这似乎不是问题，但是c/c 中不行。
利用一些内存回收技术可以解决这一问题，比如智能指针或者qsbr(quiescent state-based reclamation)。
智能指针
智能指针是一个简单易行的方案，但是智能指针的赋值不是原子的，需要对其加锁。
qsbr
qsbr的核心思想就是识别出线程的不活动(quiescent)状态，那么什么时候才算是不活动的状态呢？这个状态和临界区状态是相对的，线程离开临界区就是不活动的状态了。
简单的说就是每个读线程在离开临界区时记录一下自己的状态，写线程检查这个状态，当所有线程都离开临界区时就可以释放旧节点了。
在服务中使用rcu-qsbr
幸好有urcu这个开源实现。如前文所说，数据可以通过copy的方式进行原子更新，难点在于合适释放被替换的节点。利用rcu-qsbr我们可以在服务线程返回请求时标记自己退出临界区。这样做虽然扩大了临界区的范围，但是对应用层是透明的，应用层的开发者感知不到rcu的存在。