这篇文章根据16年学习hazard_pointer写的笔记扩展而来的。
最近读了这篇介绍hazard_pointer的文章，回想起了进实验室做的第一个关于分布式路由的项目，其中我用了RCU替换了路由表的读写锁。这两者都是适用于读多写少的场景，一样都适合在某些情况下替换掉读写锁。故写下这篇记录，对比下RCU和hazard_pointer这两种无锁编程技术。
读写锁
先说说读写锁，在服务器多线程应用中，并发的读写一个全局变量是非常常见的场景。一般这个时候我们都会加上互斥锁或者读写锁，防止data-race。这里要注意的是，并不能简单的说读写锁就一定优于互斥锁，不信？ 看这里。但是文章中的判断只具有指导意义，实际情况中最好做BenchMark视情况而定。
但是有的时候，读写锁在高并发的情况下存在一些局限，一方面对锁的争用会带来性能上的问题，另一方面，读者或者写者也有被饿死的危险。尤其是第二个问题，让我们自然而然的想到了用无锁编程的技巧来替换掉读写锁。
RCU
RCU全称Read-Copy Update，是早在linux 2.6的内核中就引进的一种新的高性能的机制。
RCU的名字很容易让人联想到COW(Copy On Write)，其实现上也确实和cow有点类似。对于被RCU保护的共享数据结构，读者不需要获得任何锁就可以访问它，但写者在访问它时首先拷贝一个副本，然后对副本进行修改，最后使用一个回调（callback）机制在适当的时机把指向原来数据的指针重新指向新的被修改的数据。
这里有一个内核实现上的小trick，就是如何判断没有读者在将要被释放的数据上。内核限制了RCU的使用，在读者使用RCU保护的数据期间，不能发生阻塞，如果没有阻塞，那么就没有切换。内核判断如果所有CPU上都经历了一次切换，就没有读者引用旧的数据，就可以安全修改指针指向新的数据。
在使用了RCU后，读者几乎没有什么同步开销，没有锁，没有原子变量，在X86下甚至不用考虑memory order，不会被饿死。由于读者几乎没有开销，那对于写者，就需要承担更多的开销，它需要复制被修改的数据结构，同时要确定没有读者在引用被修改的原内容后，释放掉原来的数据，但是RCU并不拒绝多个写者的同时写入，这是读写锁所做不到的，当然多个写者之间还是要考虑适当的同步。
使用了RCU带来了相对于读写锁如此多的好处，那是不是所有出现读写锁的地方都可以使用RCU呢？当然不是的，如果RCU没有其他side effect那就真没有读写锁什么事了，可现实是RCU要求读者在持有读数据期间不能阻塞，同时，由于写者较大的开销，在写者很多的情况下，读的高性能不能弥补写的开销带来的损失。
而且，RCU允许读者继续在旧的数据上操作直到离开，那并不是所有应用都能允许这一点，但是在某些应用中是可以的，比如路由表的更新，暂时读到旧的路由是没有关系的，如果发现路由失效读者就会再次读取路由表，这时就会读到新的路由了。这也就是为什么我可以在实验室的项目中用RCU替换掉路由表的读写锁的原因。
hazard_pointer
明白了RCU的基本操作原理，hazard_pointer也就没那么难懂了。hazard_pointer包裹了原始的pointer，读者要访问共享变量前要先保存到读线程局部变量(thread_local)，然后再访问，访问完成后从线程局部移除。而要释放一个共享对象时，则要先遍历所有读线程保存了hazard_pointer的局部变量,只要有一个读线程thread_local保存有这个共享对象的hazard_pointer，说明这个线程有可能将要访问这个对象，因此不能释放，只有所有读线程的thread_local信息中都没有保存这个共享对象的hazard_pointer情况下，才能将其释放。
其实现上也有一个小trick，读的操作中有一个double check的过程，就是在拿到全局变量加入thread_local后需要再判断一次全局变量是否还在。如果想知道为什么这么做可以去看看Reference里的原始文章，在这里我就不复述了。
hazard_pointer的问题是每次都要遍历所有读线程的thread local，这个耗时在读线程较多的时候会相当可观。为了减少耗时，可以采取同pipeline相同的思想，只有在需要写的变量操作一定的数量后才开始遍历的操作，这样可以减少写的耗时。
另外有了hazard_pointer后，我们顺便其实还解决了无锁编程中的ABA问题，这在不方便使用传统方法解决(比如加上版本号)的情况下不失为另外一种好的办法。
RCU不光只是在内核态有，在用户态也有。如果一定要对比下这两种无锁编程的技术，那就是hazard_pointer比较难用，还需要考虑很多的问题。比如究竟需要多少hazard_pointer，在很多时候，我们并不一定需要hazard_pointer，比如如果我们从不解引用指针等等一些情况。遗憾的是我也没有在实际工程中使用过hazard_pointer，以后如果有机会使用过了，我会再回来补上使用的体验。