【性能优化】lockfree在召回引擎中的实现

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

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

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

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

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

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

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

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

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

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

• 召回引擎订阅kafka的topic

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

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

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

在多线程环境下&＃xff0c;对同一个变量访问&＃xff0c;大致分为以下几种情况&＃xff1a;

• 多个线程同时读

• 多个线程同时写

• 一个线程写&＃xff0c;一个线程读

• 一个线程写&＃xff0c;多个线程读

• 多个线程写&＃xff0c;一个线程读

• 多个线程写&＃xff0c;多个线程读

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

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


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

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

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

❝

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

❞

代码实现也比较简单&＃xff0c;如下&＃xff1a;

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


在此&＃xff0c;说下读写锁的特性&＃xff1a;

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

• 写和写之间是互斥关系

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

那么&＃xff0c;对于一写多读的场景&＃xff0c;还有没有可能进行再次优化呢&＃xff1f;

答案是&＃xff1a;有的。

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

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

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

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

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

❝

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

❞

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

指针互换

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

我们就以std::vector 为例&＃xff0c;如下图所示&＃xff1a;

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

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

❝

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

❞

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

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

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

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);}


那么&＃xff0c;我们可以考虑采用智能指针的方案&＃xff0c;代码也比较简单&＃xff0c;如下&＃xff1a;

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


在上述代码中

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

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

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

• 在读线程中

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

  • 在tmp上进行读操作

• 在写线程中

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

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

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

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

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

答案是 不太适合 &＃xff0c;主要是以下两个原因&＃xff1a;

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

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

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

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

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

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

好了&＃xff0c;今天的文章就到这&＃xff0c;我们下期见。