Facebook Folly源代码分析
Folly是Facebook的一个开源C++11组件库,它提供了类似Boost库和STL的功能,包括散列、字符串、向量、内存分配、位处理等,用于满足大规模高性能的需求。6月初,Facebook宣布将其内部使用的底层C++组件库Folly开源,本文尝试对Folly库中的几个重要的数据结构代码进行分析,包括一些实现细节的讨论、特点和不足的分析,以及在工程上的应用。本文将首先分析RWSpinlock..
·
Folly是Facebook的一个开源C++11组件库,它提供了类似Boost库和STL的功能,包括散列、字符串、向量、内存分配、位处理等,用于满足大规模高性能的需求。 6月初,Facebook宣布将其内部使用的底层C++组件库Folly开源,本文尝试对Folly库中的几个重要的数据结构代码进行分析,包括一些实现细节的讨论、特点和不足的分析,以及在工程上的应用。本文将首先分析RWSpinlock.h和ThreadLocal.h的源代码。
RWSpinlock.h 顾名思义,RWSpinlock就是使用自旋方式进行临界区资源等待的读写锁,它与pthread_rwlock_t有三个比较重要的区别。
[/caption] Folly中的RWSpinlock还提供了类似数据库中“更新锁”的upgrade锁,用于对锁保护对象先读后改时避免死锁的需求,它与读写锁的状态相容矩阵如表1所示。 Write/Read/Upgrade三种锁状态除了可以和初始状态进行加解锁的双向转换外,也可以在某些锁状态之间进行转换,即原子的释放原来的锁并获取到新的锁,锁状态转换如图2所示。 [caption id="attachment_12599" align="aligncenter" width="431" caption="图2 锁状态转换"]
[/caption] 可以看出,除读写状态外,其他任意两个状态之间都是双向的转换,只有读写之间是单向转换,即在持有写锁的情况下,可以降级为读锁,而在持有读锁的情 况下却不能升级为写锁。原因很简单,在两个及以上线程都持有读锁,并尝试获取写锁的情况下,由于释放读锁和获取写锁必须原子性的完成,而要获取写锁就要等 待其他线程释放读锁,在这种情况下线程将进入死锁状态。 因此某些对锁保护对象需要先读取再决定是否修改的情况,只能在读取之前就加上写锁, 而在读取后需要修改的情况很少时,这种方式代价就比较大,因为它阻塞了其他线程获取读锁。Upgrade就应运而生,从相容性矩阵可以看到,Upgrade锁与读锁相容,而与其他upgrade和写锁不相容,线程在读取数据之前可以先获取upgrade,读取数据之后,如果决定需要修改, 就升级为写锁。 一个具体的使用示例如下,如图3所示,考虑实现一个在结点上加锁的B+tree。 [caption id="attachment_12601" align="aligncenter" width="362" caption="图3 结点加锁B+tree查询"]
[/caption] 查询操作,按照如下操作顺序从根节点开始加锁和查询: 1. 对父节点加读锁; 2. 获取子节点的读锁; 3. 释放父节点读锁。 继续在当前节点上执行第二步,直到查询到叶子节点。 更新操作,按照如下操作顺序从根节点开始加锁和查询: 1. 对父节点加upgrade锁; 2. 获取子节点的upgrade锁; 3. 判断子节点如果可能需要分裂或合并,升级父子节点为写锁; 4. 执行子节点分裂或合并,并修改父节点内容; 5. 释放父节点锁; 6. 继续在当前节点上执行第二步,直到叶子节点,对叶子节点执行插入/删除/修改。 因此在B+tree的应用中,由于索引节点的分裂合并操作比较少见,使用upgrade锁,避免与读锁的竞争,只有在必要时才升级为写锁。 关 于C++0x中atomic对象中的memory_order,RWSpinlock使用std::atomic保存上面提到的读锁计数、写锁标记、 upgrade锁标记,使用了fetch_add、fetch_and、fetch_or、compare_exchange_strong这几个原子操 作函数来修改锁状态。作者在不同的场景下使用了三种不同的memory_order,与作者沟通,他的解释如下:
[/caption]
- 通常情况下等待锁的线程不会主动让出CPU,而是循环中不断地尝试获取锁。
- 使用原子操作处理读者计数或写者状态,避免pthread_rwlock_t无论读写的加锁解锁都要在互斥锁的保护下进行。
- 提供类似数据库中”更新锁”的机制,在尽量提供更高并发的情况下,避免死锁。 [caption id="attachment_12592" align="aligncenter" width="400" caption="表1 读写锁状态相容矩阵"]
[/caption]
![图1 使用比ATOMIC_CAS更高效的ATOMIC_ADD处理读锁的加锁和解锁](http://www.programmer.com.cn/wp-content/uploads/2012/07/25.jpg)
![图2 锁状态转换](http://www.programmer.com.cn/wp-content/uploads/2012/07/37.jpg)
![图3 结点加锁B+tree查询](http://www.programmer.com.cn/wp-content/uploads/2012/07/41.jpg)
For example, unlock_shared() can be delayed to other memory_order_release (or memory_order_relaxed), but not memory_order_acquire, which means it ok for the compiler (and machine) to reordering unlock_shared() from different threads.但从gcc4.6.3中std::atomic的实现和生成的汇编代码来看,上面提到的几个原子操 作函数,直接使用了gcc提供的几个以__sync开头的内置原子操作,忽略掉了传入的memory_order参数。而只有store函数的行为针对不 同的memory_order只有是否增加mfence指令的差别。最后,笔者的建议是在性能影响不大的的情况下,直接使用std::atomic默认的 高级别的memory_order,因为通过分析复杂的原子操作指令优化时序,来决定memory_order,收益可能不及它带来的风险。 写 者优先的RWTicketSpinLockT锁,提供写锁优先的调度机制,在有线程等待获取写锁的情况下,不再授予读锁,避免在大量加读锁的场景下,写锁 很难获取的问题。使用了gcc内置的原子操作__sync_fetch_and_add和__sync_bool_compare_and_swap替代 std::atomic,并且也没有用到其他C++0x特性,使用旧版本gcc的项目可以使用这个锁。 Folly注重效率,因此RWTicketSpinLockT中也有几处值得关注的细节。
- 在等待获取锁的自旋中使用pause指令,一方面可以降低CPU的功耗,另一方面还可以帮助CPU优化指令流效率,具体可以参考注2的Intel白皮书。 而在写锁不优先的情况下,由于pause带来的延迟可能导致写锁更不容易被获取,因此获取非优先的写锁不使用pause指令。
- 使用SSE并行指令,对多个地址连续的整数一个指令完成++操作。
- 减少分支判断。见源码try_lock_shared()的old.users = old.read。将users与read是否相等的逻辑延迟到CAS操作时顺便判断,尽管在加不上读锁的情况下,要多执行两个自加和一个CAS操作,但 在加读锁成功的多数情况下,省去了一次分支判断。
- 使用__sync_fetch_and_add代替 __sync_bool_compare_and_swap。RWTicketSpinLockT使用了名为Write、Read、User的三个计数器 用来保存读锁计数和写锁标记,方法比较巧妙。读锁需要在user等于read的情况下才可以加上,而写锁则需要满足user等于write,加解锁逻辑如下。
![图4 ThreadLocal内存布局](http://www.programmer.com.cn/wp-content/uploads/2012/07/51.jpg)
- StaticMeta为全局唯一结构,主要包括各个线程管理结构组成的链表的头指针和对象ID生成器,用于全局析构和遍历所有线程的私有对象。
- ThreadEntry为线程私有结构,每线程对应一个,主要包括线程线程私有对象的指针数组,管理所有线程私有对象的指针,通过ID获取指定对象的指针。
- ElementWrapper是线程私有对象管理器,每个对象实例对应一个,主要包括指向对象实例的指针和对象的析构方法。
更多推荐
所有评论(0)