lock-free 在召回引擎中的实现

大家好，我是雨乐！

在我们的工作中，多线程编程是一件太稀松平常的事。在多线程环境下操作一个变量或者一块缓存，如果不对其操作加以限制，轻则变量值或者缓存内容不符合预期，重则会产生异常，导致进程崩溃。为了解决这个问题，操作系统提供了锁、信号量以及条件变量等几种线程同步机制供我们使用。如果每次操作都使用上述机制，在某些条件下(系统调用在很多情况下不会陷入内核)，系统调用会陷入内核从而导致上下文切换，这样就会对我们的程序性能造成影响。

今天，借助此文，分享一下去年引擎优化的一个点，最终优化结果就是在多线程环境下访问某个变量，实现了无锁(lock-free)操作。

背景

对于后端开发者来说，服务稳定性第一，性能第二，二者相辅相成，缺一不可。

作为 IT 开发人员，秉承着一句话:只要程序正常运行，就不要随便动。所以程序优化就一直被搁置，因为没有压力，所以就没有动力嘛😁。在去年的时候，随着广告订单数量越来越多，导致服务 rt 上涨，光报警邮件每天都能收到上百封，于是痛定思痛，决定优化一版。

秉承小步快跑的理念，决定从各个角度逐步优化，从简单到困难，逐个击破。所以在分析了代码之后，准备从锁这个角度入手，看看能否进行优化。

在进行具体的问题分析以及优化之前，先看下现有召回引擎的实现方案，后面的方案是针对现有方案的优化。

• 广告订单以 HTTP 方式推送给消息系统

• 消息系统收到广告订单消息后

• 将广告订单消息格式化后推送给消息队列 kafka(第 1 步)

• 将广告订单消息持久化到 DB(第 2 步)

• 召回引擎订阅 kafka 的 topic

• 从 kafka 中实时获取广告订单消息，建立并实时更建立维度索引(第 3 步)

• 召回引擎接收 pv 流量，实时计算，并返回满足定向后的广告候选集(第 4 步)

从上面图中可以看出，召回引擎是一个多线程应用，一方面有个线程专门从 kafka 中获取最新的广告订单消息建立维度索引(此为写线程)，另一方面，接收线上流量，根据流量属性，获取广告候选集(此为读线程)。因为召回引擎涉及到同时读和写同一块变量，因此读写不能同时操作。

概述

在多线程环境下，对同一个变量访问，大致分为以下几种情况：

• 多个线程同时读

• 多个线程同时写

• 一个线程写，一个线程读

• 一个线程写，多个线程读

• 多个线程写，一个线程读

• 多个线程写，多个线程读

在上述几种情况中，多个线程同时读显然是线程安全的，而对于其他几种情况，则需要保证其_互斥排他_性，即读写不能同时进行，管他几个线程读几个线程写，代码走起。

thread1{  std::lock_guard<std::mutex> lock(mtx);  // do sth(read or write)}
thread2{  std::lock_guard<std::mutex> lock(mtx);  // do sth(read or write)}
threadN{  std::lock_guard<std::mutex> lock(mtx);  // do sth(read or write)}

在上述代码中，每一个线程对共享变量的访问，都会通过 mutex 来加锁操作，这样完全就避免了共享变量竞争的问题。

如果对于性能要求不是很高的业务，上述实现完全满足需求，但是对于性能要求很高的业务，上述实现就不是很好，所以可以考虑通过其他方式来实现。

我们设想一个场景，假如某个业务，写操作次数远远小于读操作次数，例如我们的召回引擎，那么我们完全可以使用读写锁来实现该功能，换句话说_读写锁适合于读多写少的场景_。

读写锁其实还是一种锁，是给一段临界区代码加锁，但是此加锁是在进行写操作的时候才会互斥，而在进行读的时候是可以共享的进行访问临界区的，其本质上是一种自旋锁。

代码实现也比较简单，如下：

writer thread {  pthread_rwlock_wrlock(&rwlock);  // do write operation  pthread_rwlock_unlock(&rwlock);}
reader thread2 {  pthread_rwlock_rdlock(&rwlock);  // do read operation  pthread_rwlock_unlock(&rwlock);}
reader threadN {  pthread_rwlock_rdlock(&rwlock)  // do read operation  pthread_rwlock_unlock(&rwlock);}

在此，说下读写锁的特性：

• 读和读指针没有竞争关系

• 写和写之间是互斥关系

• 读和写之间是同步互斥关系(这里的同步指的是写优先，即读写都在竞争锁的时候，写优先获得锁)

那么，对于一写多读的场景，还有没有可能进行再次优化呢？

答案是：有的。

下面，我们将针对一写多读，读多写少的场景，进行优化。

方案

在上一节中，我们提到对于多线程访问，可以使用 mutex 对共享变量进行加锁访问。对于一写多读的场景，使用读写锁进行优化，使用读写锁，在读的时候，是不进行加锁操作的，但是当有写操作的时候，就需要加锁，这样难免也会产生性能上的影响，在本节，我们提供终极优化版本，目的是在写少读多的场景下实现 lock-free。

如何在读写都存在的场景下实现 lock-free 呢？假设如果有两个共享变量，一个变量用来专供写线程来写，一个共享变量用来专供读线程来读，这样就不存在读写同步的问题了，如下所示：

在上节中，我们有提到，多个线程对一个变量同时进行读操作，是线程安全的。一个线程对一个变量进行写操作也是线程安全的(这不废话么，都没人跟它竞争)，那么结合上述两点，上图就是线程安全的(多个线程读一个资源，一个线程写另外一个资源)。

好了，截止到现在，我们 lock-free 的雏形已经出来了，就是_使用双变量_来实现 lock-free 的目标。那么 reader 线程是如何第一时间能够访问 writer 更新后的数据呢？

假设有两个共享资源 A 和 B，当前情况下，读线程正在读资源 A。突然在某一个时刻，写线程需要更新资源，写线程发现资源 A 正在被访问，那么其更新资源 B，更新完资源 B 后，进行切换，让读线程读资源 B，然后写线程继续写资源 A，这样就能完全实现了 lock-free 的目标，此种方案也可以成为双 buffer 方式。

实现

在上节中，我们提出了使用双 buffer 来实现 lock-free 的目标，那么如何实现读写 buffer 无损切换呢？

指针互换

假设有两个资源，其指针分别为 ptrA 和 ptrB，在某一时刻，ptrA 所指向的资源正在被多个线程读，而 ptrB 所指向的资源则作为备份资源，此时，如果有写线程进行写操作，按照我们之前的思路，写完之后，马上启用 ptrA 作为读资源，然后写线程继续写 ptrB 所指向的资源，这样会有什么问题呢？

我们就以 std::vector<Obj>为例，如下图所示：

在上图左半部分，假设 ptr 指向读对象的指针，也就是说读操作只能访问 ptr 所指向的对象。

某一时刻，需要对对象进行写操作(删除对象 Obj4)，因为此时 ptr = ptrA，因此写操作只能操作 ptrB 所指向的对象，在写操作执行完后，将 ptr 赋值为 ptrB(保证后面所有的读操作都是在 ptrB 上)，即保证当前 ptr 所指向的对象永远为最新操作，然后写操作去删除 ptrA 中的 Obj4，但是此时，有个线程正在访问 ptrA 的 Obj4，自然而然会轻则当前线程获取的数据为非法数据，重则程序崩溃。

此方案不可行，主要是因为在写操作的时候，没有判断当前是否还有读操作。

原子性

在上述方案中，简单的变量交换，最终仍然可能存在读写同一个变量，进而导致崩溃。那么如果保证在写的时候，没有读是不是就能解决上述问题了呢？如果是的话，那么应该如何做呢？

显然，此问题就转换成如何判断一个对象上存在线程读操作。

用过 std::shared_ptr 的都知道，其内部有个成员函数 use_count()来判断当前智能指针所指向变量的访问个数，代码如下：

long      _M_get_use_count() const noexcept      {        // No memory barrier is used here so there is no synchronization        // with other threads.        return __atomic_load_n(&_M_use_count, __ATOMIC_RELAXED);      }

那么，我们可以考虑采用智能指针的方案，代码也比较简单，如下：

std::atomic_size_t curr_idx = 0;
std::vector<std::shared_ptr<Obj>> obj_buffers;obj_buffers.emplace_back(std::make_shared<Obj>(...));obj_buffers.emplace_back(std::make_shared<Obj>(...));
// write thread {   size_t prepare = 1 - curr_idx.load();   while (obj_buffers[prepare].use_count() > 1) {     continue;   }     obj_buffers[prepare]->load();   curr_idx = prepare; } 
  // read thread   {     auto tmp = obj_buffers[curr_idx.load()];     // do sth  } 

在上述代码中

• 首先创建一个 vector，其内有两个 Obj 的智能指针，这俩智能指针所指向的 Obj 对象一个供读线程进行读操作，一个供写线程进行写操作

• curr_idx 代表当前可供读操作对象在 obj_buffers 的索引，即 obj_buffers[curr_idx.load()]所指对象供读线程进行读操作

• 那么相应的，obj_buffers[1- curr_idx.load()]所指对象供写线程进行写操作

• 在读线程中

• 通过 auto tmp = obj_buffers[curr_idx.load()];获取一个拷贝，由于 obj_buffers 中存储的是 shared_ptr 那么，该对象的引用计数+1

• 在 tmp 上进行读操作

• 在写线程中

• prepare = 1 - curr_idx.load();在上面我有提到 curr_idx 指向可读对象在 obj_buffers 的索引，换句话说，1 - curr_idx.load()就是另外一个对象即可写对象在 obj_buffers 中的索引

• 通过 while 循环判断另外一个对象的引用计数是否大于 1(如果大于 1 证明还有读线程正在进行读操作)

好了，截止到此，lock-free 的实现目标基本已经完成。实现原理也也相对来说比较简单，重点是要保证_写的时候没有读操作_即可。


上图是召回引擎做了 lock-free 优化后的效果图，从图上来看，效果还是很明显的。

扩展

双 buffer 方案在“一写多读”的场景下能够实现 lock-free 的目标，那么对于“多写一读”或者“多写多读”场景，是否也能够满足呢？

答案是不太适合，主要是以下两个原因：

• 在多写的场景下，多个写之间需要通过锁来进行同步，虽然避免了对读写互斥情况加锁，但是多线程写时通常对数据的实时性要求较高，如果使用双 buffer，所有新数据必须要等到索引切换时候才能使用，很可能达不到实时性要求

• 多线程写时若用双 buffer 模式，则在索引切换时候也需要给对应的对象加锁，并且也要用类似于上面的 while 循环保证没有现成在执行写入操作时才能进行指针切换，而且此时也要等待读操作完成才能进行切换，这时候就对备用对象的锁定时间过长，在数据更新频繁的情况下是不合适的。

缺点

通过前面的章节，我们知道通过双 buffer 方式可以实现在一写多读场景下的 lock-free，该方式要求两个对象或者 buffer 最终持有的数据是完全一致的，也就是说在单 buffer 情况下，只需要一个 buffer 持有数据就行，但是双 buffer 情况下，需要持有两份数据，所以存在内存浪费的情况。

其实说白了，双 buffer 实现 lock-free，就是采用的空间换时间的方式。

结语

双 buffer 方案在多线程环境下能较好的解决 “一写多读” 时的数据更新问题，特别是适用于数据需要定期更新，且一次更新数据量较大的情形。

性能优化是一个漫长的不断自我提升的过程，项目中的一点点优化往往就可以使得性能得到质的提升。

好了，今天的文章就到这，我们下期见。