非死book Folly源代码分析

jopen 12年前

        Folly 是 非死book 的一个开源C++11组件库,它提供了类似 Boost 库和 STL 的功能,包括散列、字符串、向量、内存分配、位处理等,用于满足大规模高性能的需求。

        6月初,非死book 宣布将其内部使用的底层 C++ 组件库 Folly 开源,本文尝试对 Folly 库中的几个重要的数据结构代码进行分析,包括一些实现细节的讨论、特点和不足的分析,以及在工程上的应用。本文将首先分析 RWSpinlock.h 和 ThreadLocal.h 的源代码。

        RWSpinlock.h

        顾名思义,RWSpinlock 就是使用自旋方式进行临界区资源等待的读写锁,它与 pthread_rwlock_t有三个比较重要的区别。

  • 通常情况下等待锁的线程不会主动让出 CPU,而是循环中不断地尝试获取锁。
  • 使用原子操作处理读者计数或写者状态,避免 pthread_rwlock_t无论读写的加锁解锁都要在互斥锁的保护下进行。
  • 提供类似数据库中”更新锁”的机制,在尽量提供更高并发的情况下,避免死锁。

    非死book Folly源代码分析

    表 1 读写锁状态相容矩阵

        RWSpinlock 实现中几处值得关注的地方如下。

        自旋锁在锁粒度较小的情况下,使用自选等待方式等锁,可以避免较高的上下文切换代价。而为了自适应多次获取锁失败的情况,可以主动让出 CPU。Folly 的实现比较简单,硬编码为在自旋 1000 次后仍无法获取锁的情况下,以后的每次循环都调用 sched_yield 主动让出 CPU 以调度其他线程上来运行(要研究更复杂的自适应锁机制,可以参考 Solaris 内部实现的 Adaptive locks 或注 1 提到的论文)。但在获取读锁次数远大于写锁次数的情况下,RWSpinlock 的读优先机制可能造成写者的饥饿,而主动让出 CPU 的机制则可能加重写者的饥饿程度。因此 Folly 中同时实现了可配置为写者优先的 RWTicketSpinLockT 锁。

        与通常对读计数器加 1 的思路不同,RWSpinlock 使用 int32_t的高 30 位保存读计数,而使用最低两位保存 upgrade 和 write 标记。在加解读锁时直接对 int32_t的锁状态原子加减0×4,直接避开了对最低两位的修改,执行原子加0×4后再根据原子操作前的最低两位是否有效,来决定是否需要回滚(减 0×4)。在多数只获取读锁的情况下,不需要回滚,一次 ATOMIC_ADD 即完成读锁的加解锁。

非死book Folly源代码分析

图 1 使用比 ATOMIC_CAS 更高效的 ATOMIC_ADD 处理读锁的加锁和解锁

        Folly 中的 RWSpinlock 还提供了类似数据库中“更新锁”的 upgrade 锁,用于对锁保护对象先读后改时避免死锁的需求,它与读写锁的状态相容矩阵如表 1 所示。

        Write/Read/Upgrade 三种锁状态除了可以和初始状态进行加解锁的双向转换外,也可以在某些锁状态之间进行转换,即原子的释放原来的锁并获取到新的锁,锁状态转换如图 2 所示。

非死book Folly源代码分析

图 2 锁状态转换

        可以看出,除读写状态外,其他任意两个状态之间都是双向的转换,只有读写之间是单向转换,即在持有写锁的情况下,可以降级为读锁,而在持有读锁 的情况下却不能升级为写锁。原因很简单,在两个及以上线程都持有读锁,并尝试获取写锁的情况下,由于释放读锁和获取写锁必须原子性的完成,而要获取写锁就 要等待其他线程释放读锁,在这种情况下线程将进入死锁状态。

        因此某些对锁保护对象需要先读取再决定是否修改的情况,只能在读取之前就加上写锁, 而在读取后需要修改的情况很少时,这种方式代价就比较大,因为它阻塞了其他线程获取读锁。Upgrade 就应运而生,从相容性矩阵可以看到,Upgrade 锁与读锁相容,而与其他 upgrade 和写锁不相容,线程在读取数据之前可以先获取 upgrade,读取数据之后,如果决定需要修改, 就升级为写锁。

        一个具体的使用示例如下,如图 3 所示,考虑实现一个在结点上加锁的B+tree。

非死book Folly源代码分析

图 3 结点加锁B+tree 查询

        查询操作,按照如下操作顺序从根节点开始加锁和查询:

        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,与作者沟通,他的解释如下:

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,加解锁逻辑如下。

        1. 通过对 read 和 user 原子加一,获取读锁,同时封锁了加写锁的条件。

        2. 通过对 read 原子加一,获取写锁,同时也就封锁了加读锁的条件;这里通过先对 read 加一,封锁了后续读锁的条件,然后再等待写锁的条件被满足,实现了写锁优先的逻辑。

        3. 通过对 write 原子加一,释放读锁,同时恢复写锁的加锁条件。

        4. 通过对 read 和 write 原子加一,释放写锁,同时恢复读锁的加锁条件。

        可以看出写锁的获取和读锁的释放可以避免使用 CAS,而用一个原子加即可实现。

        ThreadLocal.h

        在服务器编程中,通常会遇到需要为每个线程都分配不同对象的情况,如线程处理一个请求需要使用的临时内存、远程调用需要临时构造的参数等等。在 需要的时候临时构造,不仅要付出构造成本,还会有内存申请释放的代价,而使用线程主函数的栈对象,每一层都要传递参数也让代码很不便维护。

        Folly 中实现的 ThreadLocal.h 提供了对象的线程局部存储和访问,其功能与 pthread_getspecific 相似,提供了更方便友好的调用方式, 线程退出后自动析构本线程内所欲的私有对象,并且提供遍历所有线程私有对象的接口。实现上使用了 GCC 内置特性,实现比 pthread 库更快的线程私有对象访问。

        ThreadLocal 内存布局如图 4 所示,主要由 StaticMeta、ThreadEntry 和 ElementWrapper 三者组成。

非死book Folly源代码分析

图 4 ThreadLocal 内存布局

  • StaticMeta 为全局唯一结构,主要包括各个线程管理结构组成的链表的头指针和对象 ID 生成器,用于全局析构和遍历所有线程的私有对象。
  • ThreadEntry 为线程私有结构,每线程对应一个,主要包括线程线程私有对象的指针数组,管理所有线程私有对象的指针,通过 ID 获取指定对象的指针。
  • ElementWrapper 是线程私有对象管理器,每个对象实例对应一个,主要包括指向对象实例的指针和对象的析构方法。

        假设要管理的线程私有类型为T,初始化和访问线程私有对象的流程如下。

        1. ThreadLocalPtr 对象构造时即从 StaticMeta 为它管理的类型申请了唯一 ID。

        2. 使用 TheadLocalPtr::get 方法通过 ID 从 ThreadEntry 管理的 ElementWrapper 数组中获取一个 ElementWrapper 对象。

        3. 如果 ElementWrapper 中T的指针为空,则构造一个T的对象,指针和析构方法保存在 ElementWrapper 对象中。

        4. 如果 ElementWrapper 中的T指针不为空,则直接返回。

        在 Folly 的实现中值得注意的是:ThreadEntry 对象在每个线程中有一个,使用 gcc 内置的 static __thread 方式声明 ThreadEntry,即可实现同一个名字在不同线程访问到的是不同对象,需要注意的是这种方式仅适用于 POD 类型。由于直接访问对象,这种方式比调用 pthread 库的 pthread_getspecific 函数调用方式效率要更高。

        但由于 ThreadEntry 是 POD 类型,在线程退出时不能自动析构释放它管理的线程私有对象,因此在 StaticMeta 构造时会申请一个 pthread_key_t注册线程退出时的回调函数,在回调函数中遍历当前线程 ThreadEntry 管理的所有私有对象,依次调用它们的析构方法。因此在 Folly 的实现中,对 pthread 库函数仅仅使用了它在线程退出时调用回调函数的功能。

        此外还有两处细节值得借鉴。

        ●ThreadLocal 还区分了单个线程退出和整体析构情况下,传给析构方法不同的参数,以便用户在必要的情况下区别这两种情况下析构方法的实现。

        ●提供了指定立即析构释放当前线程私有对象的方法,而不必等待线程退出时才释放,这一点在单元测试多个 case 的情况下可能会使测试变得比较方便。

        注释

        注1: Adaptive Locks: Combining Transactions and Locks for Efficient Concurrency

        注2: Using Spin-Loops on Intel® Pentium® 4 Processor and Intel® XeonTM Processor

        注3: A Provably Correct Scalable Concurrent Skip

        注4: Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects

        注5: Doug Lea. ConcurrentSkipListMap. In java.util.concurrent

        作者李凯,现任淘宝核心系统部存储组技术专家,花名郁白。2007-2010年曾参与百度分布式文件系统研发,2010年至今参与淘宝 Oceanbase 项目研发。