)
新版本文章请移步王者荣耀日志组件BqLog为什么这么快之2——从环形队列到自适应数据总线-CSDN博客BqLog可能是全球最快的日志库源自最成功的手游之一《王者荣耀》客户端轻量级适用于PC、移动设备和服务器支持C#、Java、C并对Unity、Unreal引擎做了良好适配。GitHub地址GitHub - Tencent/BqLog: Maybe the worlds fastest logging library, originating from the client of the top mobile game Honor of Kings, is lightweight, works on PC, mobile, and servers, supports C#, Java, and C, and is well adapted to Unity and Unreal engines. 可能是全球最快的日志库源自最成功的手游之一《王者荣耀》客户端轻量级适用于PC、移动设备和服务器支持C#、Java、C并对Unity、Unreal引擎做了良好适配。系列文章王者荣耀国际服日志组件BqLog为何如此快 1 - 高性能实时压缩日志格式-CSDN博客王者荣耀国际服日志组件BqLog为什么这么快 2 - 创新型的WaitFree并发队列-CSDN博客支持平台Windows 64 bitMacOSLinuxiOSAndroid(X86_64, arm64-v8a、armeabi-v7a)Unix(在FreeBSD上通过测试)支持编程语言CJavaKotlinC#特点对比现有开源日志库有巨大的性能优势见Benchmark不仅适用于服务器客户端也非常适合移动端设备内存消耗少在Benchmark的用例中10线程20000000条日志BqLog本身内存消耗在1M以内。提供高性能高压缩比的实时压缩日志格式可以在游戏引擎UnityUnreal中正常使用其中对Unreal提供了常用类型的支持支持utf8,utf16,utf32的字符和字符串支持bool,float,double各种长度和类型的整数等常用参数类型支持C20的format规范异步日志支持Crash复盘避免丢失数据灵感来自XLog尺寸极小Android编译后动态库仅有200k左右在Java和C#上可以不额外产生Heap Alloc不会随着运行不停new对象。仅依赖标准C语言库和平台API可以在安卓的ANDROID_STL none的模式下通过编译支持C11及以后的编译标准可以在-Wall -Wextra -pedantic -Werror的严格要求下通过编译编译模块基于Cmake并提供不同平台的编译脚本使用方便支持自定义参数类型对代码提示非常友好在追求极致性能的系统中减少一切不必要的计算是优化的核心。以手游为例帧率和流畅度是其基础体验的关键而游戏的发行版本往往被一个“不可能三角”所困扰性能足够好日志少写方便追述问题日志应写尽写节约存储空间日志最好就别写由于面向全球的软件会面临发行背景面临时差、语言和隐私观念等问题在遇到疑难杂症时很难直接与用户沟通。这种时候我们就需要一种产品能帮助我们“既要又要”打破这个不可能三角。BqLog就是在这样的背景下诞生的。前言关于BqLog的性能现在业界内常见的以性能著称的日志组件一般有以下选手JavaLog4j2LogbackC#NLoglog4netCSpdLog多语言mars-xlog英雄不问出身不管日志组件是用什么写的我们都使用相同的场景和测试用例进行性能对比每种组件均选取性能最高的模式如异步模式。最终Log4j2以绝对的性能优势胜出。那么如果BqLog与Log4j2的异步模式进行对比呢下图展示了一个直观的对比结果每条日志带4个参数的总耗时单位毫秒1线程2线程3线程4线程5线程6线程7线程8线程9线程10线程BqLog Compress(C)1552503104065156227618859721007BqLog Text(C)38476811361716202027833578388340324383BqLog Compress(Java)66478293191198910551107122912881336BqLog Text(Java)70699311651582191225722779327542494591Log4J2 Text1065258342494843506861956424794387949254从结果可以看出在每个线程写入200万条日志每条日志包含4个格式化参数且附带日志级别、时间戳和线程信息的情况下C版本的BqLog性能是Log4j2的9倍左右Java版本的BqLog也达到了Log4j2的7倍左右。测试用例和双方的代码配置请参见此链接 Benchmark那么BqLog的性能提升背后的关键是什么呢BqLog的性能提升关键措施缓存行隔离避免False Sharing内存模型(Memory Order)的高效使用利用AMD uProf一类的专业CPU Profiler工具找到memory access中的瓶颈所在IO操作合并避免运行时format提高CPU Cache命中率其他优化……BqLog的性能优化已经达到一个阶段性极限——大部分开销集中在操作系统的IO操作上。甚至容器函数是否内联都会对最终性能产生显著影响。要详述其中的每个性能优化点可能还需要很多篇文章对于各位大牛来说这些技术细节或许并无新意而对于萌新网上也有丰富的资料可供参考即便是直接看BqLog的源码也有很多注释和说明。所以就不再浪费篇幅。本文聚焦BqLog自实现的高并发队列的创新点探讨其如何抛弃传统并发队列中的CAS (Compare And Swap)操作从Lock-Free进化到Wait-Free以实现更高效的并发处理。此方案已在BqLog开源前申请了专利。前置知识消息队列本章针对初学者主要介绍Linux的kFifo和LMAX Disruptor方案已经了解的同学可以直接跳到BqLog Ring Buffer本文专注于CAS (Compare And Swap)的替代所以关于内存屏障Memory Barrier内存模型Memory Order等的相关内容都会刻意一笔带过有需要的同学可以去网上搜索相关文章1. Linux kFifokFifo是Linux内核提供的一种循环队列FIFO的实现广泛用于内核模块、驱动开发和设备间的高效通信。它通过环形队列ring buffer来管理数据确保生产者与消费者的高效交互并且能够在多线程场景下保证数据安全。经典的kFifo只适用于一个线程读一个线程写不能支持更多的并发。工作原理kFifo基于环形队列ring buffer的设计利用in和out两个指针管理数据的写入和读取。数据写入时in指针向前推进读取数据时out指针前进。当指针达到缓冲区末尾时循环回到缓冲区的开头从而实现数据的“环形”流动。其伪码如下/// summary /// 写线程调用 /// /summary /// param namefifofifo对象提前创建好的/param /// param namebuf需要写入的数据源头/param /// param namelen需要写入的数据大小/param /// returns实际写入的数据大小/returns unsigned int kfifo_in(struct kfifo *fifo, const void *buf, unsigned int len) { unsigned int l; l min(len, fifo-size - fifo-in fifo-out); //先看看还剩多少空间能够写入 memcpy(fifo-buffer (fifo-in (fifo-size - 1)), buf, l); //写入 memory_barrier(); // 内存屏障确保读线程读到最新的fifo-in的时候他前面的数据已经成功写入了可以开始读取了 fifo-in l; //更新fifo-in这样读线程知道最新的数据已经写到这里了 return l; //实际写入成功的数据长度 } /// summary /// 读线程调用 /// /summary /// param namefifofifo对象提前创建好的/param /// param namebuf需要需要读入的数据拷贝目标缓存/param /// param namelen需要读入的数据大小/param /// returns实际读入的数据大小/returns unsigned int kfifo_out(struct kfifo *fifo, void *buf, unsigned int len) { unsigned int l; l min(len, fifo-in - fifo-out); //先看看队列里到底还有多少数据 memcpy(buf, fifo-buffer (fifo-out (fifo-size - 1)), l); //读入 memory_barrier(); // 内存屏障确保写线程读到最新的fifo-out的时候他前面的数据已经都被读走了可以作为空白区域写入新的数据了 fifo-out l; //更新fifo-out这样写线程知道这之前的数据都已经被读走了可以覆盖了 return l; //实际读到的数据长度 }kFifo分析kFifo通过环形队列ring buffer设计和简洁的指针管理实现高效读写操作。生产者写线程通过推进in指针将数据写入缓冲区消费者读线程则通过移动out指针读取数据。当in和out指针到达缓冲区末尾时它们自动回绕至起始位置形成环形结构。此设计的核心优势在于简化了读写操作写线程仅更新in指针以指示写入位置读线程仅更新out指针以指示读取位置从而实现生产者和消费者之间的有效协作。这样的极简设计避免了两者同时操作同一变量而引发的竞态条件。在多线程场景下kFifo依赖的同步机制非常轻量仅通过内存屏障保证顺序性而不需要复杂的锁或CAS (Compare And Swap)操作。这种简洁的同步方式正是kFifo性能高效的原因之一。内存屏障(Memory Barrier)在多核系统中指令的执行顺序可能与编程顺序不同。为保证数据的正确性内存屏障用于确保读写操作的顺序符合预期。虽然内存屏障是确保数据一致性的关键但其本身是一个较为底层的概念kFifo的逻辑并不依赖复杂的同步机制。除了内存屏障之外所有的操作都相当简单。局限性kFifo的这种“你追我赶”模式虽然高效但也有其局限性。它最适合于单个生产者和单个消费者的场景。在这种情况下生产者只需关注自己的in指针消费者只需关注自己的out指针。然而如果有多个生产者或多个消费者参与竞争这种简化的设计就不再适用了。在高并发的场景下kFifo并不能很好地扩展。举个例子有两个线程在同时进行写操作看代码:unsigned int kfifo_in(struct kfifo *fifo, const void *buf, unsigned int len) { unsigned int l; l min(len, fifo-size - fifo-in fifo-out); memcpy(fifo-buffer (fifo-in (fifo-size - 1)), buf, l); //问题所在如果两个线程同时在写入两个线程可能会对同一个地址进行memcpy memory_barrier(); fifo-in l; return l; }2. LMAX DisruptorLMAX Disruptor是近年来备受推崇的高性能并发框架之一由英国LMAX交易所开发解决了在金融交易系统中处理高吞吐量、低延迟场景的挑战。其优异的性能表现使得它在多并发环境中脱颖而出成为许多高并发系统的首选框架。也是Log4j2的默认消息队列实现。其代码和文档都已经在Github开源LMAX-Exchange-disruptor。为什么Disruptor如此优秀在处理数百万条消息的场景下Disruptor展示出极低的延迟和极高的吞吐量。传统的队列在多生产者和多消费者的场景下通常会因为锁竞争、内存分配和同步机制导致性能下降。而Disruptor通过无锁并发模型解决了这些问题极大提升了性能。在并发环境中Disruptor通过两大核心机制实现了高效的多生产者并发CASCompare-And-Swap操作和内存标记机制。这两者紧密结合实现了Lock-Free保证了在高并发环境中数据的正确性和安全性。A. CAS操作Compare-And-Swap保证并发写入CAS是一种无锁的同步原语用于解决并发编程中的共享数据更新问题。它通过比较和交换的机制确保只有一个线程能够成功地更新变量避免了多个线程在同一时刻对同一数据进行修改。CAS的基本操作如下比较检查某个内存地址中的当前值是否等于预期值。交换如果相等则将这个地址的值更新为新的值如果不相等说明其他线程已经修改了这个值当前线程的操作失败需要重试。CAS操作具有原子性这意味着它要么完全成功更新要么完全失败不会出现中间状态。这种无锁的方式非常适合多线程并发场景下的变量更新尤其是用于解决“竞争条件”race condition问题。让我们回到之前kFifo的例子我们尝试改一下kfifo_in函数让它可以支持并发写入。假设我们希望将kFifo_in函数修改为支持多线程并发写入那么需要解决的问题是如何让多个线程安全地申请缓冲区中的空间而不互相覆盖。在单线程的情况下in指针可以直接增加来表示写入的区域但是在多线程环境中多个线程可能会同时尝试修改这个指针导致数据冲突。我们可以使用CAS操作来解决这个问题每个线程在写入数据之前通过CAS申请空间确保指针的正确更新。下面是将kFifo_in修改为支持并发写入的示例代码unsigned int kfifo_in_concurrent(struct kfifo *fifo, const void *buf, unsigned int len) { unsigned int old_in, new_in, free_space; do { // 1. 获取当前的in指针位置 old_in fifo-in; // 2. 计算ring_buffer剩余的可用空间 free_space fifo-size - (fifo-in - fifo-out); if (len free_space) { return 0; // 如果空间不足写入失败 } // 3. 计算新的in指针位置 new_in old_in len; // 4. 尝试通过CAS更新in指针 // 如果当前的in值还是old_in那么成功更新为new_in否则需要重试 } while (!__sync_bool_compare_and_swap(fifo-in, old_in, new_in)); // 5. 现在已经安全地申请到空间开始写入数据从fifo-in开始的len个字节已经被当前线程占有 write_data_to(fifo-in/*to*/, buf/*from*/, len/*size*/); return len; }为什么CAS能够解决并发写入问题在多线程并发写入的场景中多个线程可能会同时尝试修改in指针导致写入冲突。CAS通过对比和交换机制确保只有一个线程能够成功更新指针并且失败的线程可以通过重试机制重新申请空闲空间。这种设计保证了并发写入时生产者不会写入相同的内存区域。每个生产者通过CAS操作确保它有一个独立的空间可以安全地写入数据。相较于传统的加锁机制CAS避免了锁的竞争和开销极大地提升了并发性能。B. 内存标记保证正确读取在Disruptor中生产者首先通过CAS操作申请一个内存位置然后再进行数据的写入。这与kFifo中“先写入再申请”的设计不同。这种设计的优势在于生产者在写入前已经确保了它拥有独立的内存区域可以写入避免了多生产者写入时数据被覆盖的风险。而且在并发场景下CAS能够有效地减少竞争避免传统锁机制带来的性能损耗。但是这样也带来了一些问题在kFifo中由于是先写内存再更新索引所以in可以代表数据最新写到的位置但是现在的Disruptor采取的是跟上面一样的先申请内存空间再写入数据的方式in就不再具备这个功能了具体可以看下图。图示为Disruptor的消息队列内存其中out代表已经读完的位置而in的情况就变了。我们可以看到三个线程ThreadA, ThreadB和ThreadC分别在消息队列上申请了3块空间。其中ThreadA和ThreadC已经成功将数据刷进了消息队列中而ThreadB还没完成这个操作。这种情况下如果我们依然用in作为读取的最终位置无疑是错误的。in现在唯一的作用就是标记下一次生产者写入的起始位置。所以我们需要一种新的机制去知道当前消费者线程能够读到哪里。为了解决这个问题Disruptor新开辟了一块内存用于按顺序标记每块内存Slot是否写入完成读取的时候每读一块内存就需要去验证一下对应的标记是否填入。由于Java的对象都是引用所以每一个标记正好对应一个指针数据大小这种方案是可行的。换成直接把数据拷贝在消息队列上的编程环境方案则需要做一些修改。当然了这个话题不是本文重点有兴趣的同学可以去看Disruptor的源码和文档。3. BqLog Ring BufferDisruptor的CAS操作其实已经成为了并发编程中的标配尤其在高并发场景下大家普遍追求无锁Lock-Free的实现方式。然而尽管Lock-Free带来了性能提升但它并非完美的解决方案在一些关键场景中它依然存在问题。为什么Lock-Free没有想象中那么好Lock-Free设计的核心是避免线程因锁的争用而阻塞借助CAS等原子操作多个线程可以自由竞争更新共享数据。这种方式的确减少了传统锁带来的上下文切换和锁竞争问题因此在高并发环境下表现出色。然而Lock-Free并不意味着所有线程都能以相同的效率完成操作。因为CAS操作依赖竞争失败的线程需要重新尝试这会带来潜在的延迟和不确定性。特别是在高度竞争的情况下线程可能不断地进行失败的CAS操作导致整体性能下降。此外Lock-Free并不能保证每个线程都能在有限的时间内完成其任务。举个例子在一个高度并发的环境中某个线程可能一直在竞争中失败导致它永远无法完成更新。这种情况下虽然系统不会完全陷入死锁但部分线程的进度会受到极大的阻碍。最终系统的整体吞吐量和延迟表现可能并不如预期。为什么Wait-Free才是最优解相比于Lock-FreeWait-Free设计更进一步保证每个线程都能在有限的步骤内完成其操作而不需要依赖竞争和重试逻辑。在Wait-Free的并发模型中线程不必等待其他线程的操作完成所有的线程在规定的时间内都能完成任务。这种确定性使得Wait-Free在性能和响应时间上都有显著优势尤其适合高实时性、高并发的场景。Wait-Free的核心在于它不仅消除了锁还消除了等待的概念。每个线程通过某种策略确保其操作总是能够在固定步骤内完成从而避免了竞争中的不确定性。虽然Wait-Free算法的实现复杂度更高但它带来了更加稳定和高效的性能表现。BqLog的Wait-Free实现BqLog的消息队列bq::ring_buffer通过自创的一种算法实现了Wait-Free该算法用fetch_add替代CAS并且设计了一个空间不足时候的回滚算法确保在高并发的情况下生产者和消费者都能够在固定的步骤内完成日志的写入和读取。其代码实现可以参考BqLog/src/bq_log/types/ring_buffer.h at main · Tencent/BqLog · GitHubBqLog/src/bq_log/types/ring_buffer.cpp at main · Tencent/BqLog · GitHubfetch_add和优势fetch_add是另外一种无锁的原子操作它在并发编程中非常重要。它通过两个步骤完成操作获取当前值获取变量操作前的旧值。执行加法将指定值加到变量上并原子地更新该值。返回之前的值返回执行add前该变量实际的值。fetch_add保证了每次操作不会失败因此即使多个线程同时操作也能确保每个线程安全地更新变量而不需要重试或等待。与CAS不同fetch_add没有重试机制因为它不会失败。每个线程都会获取一个唯一的值然后直接执行加法并更新变量。这意味着每个线程的操作都能在固定步骤内完成不会因为竞争而被阻塞因此符合Wait-Free的要求。让我们看看用fetch_add改写的kfifo_in_concurrent函数unsigned int kfifo_in_concurrent(struct kfifo *fifo, const void *buf, unsigned int len) { // 1. 计算ring_buffer剩余的可用空间 unsigned int free_space fifo-size - (fifo-in - fifo-out); if (len free_space) { return 0; // 如果空间不足写入失败 } // 2. 申请内存最后申请到的内存就是从from开始的len长度内存 unsigned int from __sync_fetch_add(fifo-in, len); // 3. 现在已经安全地申请到空间开始写入数据从fifo-in开始的len个字节已经被当前线程占有 write_data_to(from/*to*/, buf/*from*/, len/*size*/); } unsigned int allocated_A kfifo_in_concurrent(fifo, buf, 10);//从线程A调用 unsigned int allocated_B kfifo_in_concurrent(fifo, buf, 5);//从线程B调用 unsigned int allocated_C kfifo_in_concurrent(fifo, buf, 15);//从线程C调用假设fifo-in的初始值是0三个线程同时执行后它们分别对应的内存开始位置可能是线程A0。线程B10。线程C15。fifo-in:30也可能是线程A20。线程B0。线程C5。fifo-in:30可以看下图表示这样三个线程在并发情况下分别获取了它们独占的内存段每个线程都申请到了一块不同的内存区间并且这些操作是无锁的无需等待或重试。通过fetch_add每个线程都能够原子地申请到一个唯一的位置从而实现真正的Wait-Free操作。fetch_add的不足和回滚方案既然fetch_add如此方便就实现了Wait-Free那为什么几乎所有的消息队列都用CAS呢因为前者有一个致命缺陷。依然看刚才的例子。假如说buffer最大的空间只有25。而ABC三个线程同时执行kfifo_in_concurrent大家一起做了剩余空间判断都发现剩余空间还有25足够自己写入。但是到了最后执行fetch_add的时候三个线程都以为自己成功申请到了内存。而实际上排在最后那个线程申请到的内存是无效的。反观CAS就不会有这个问题因为每一次最后申请的时候必须是没有其他线程申请过内存in的值和之前判断剩余空间时完全一致才算申请成功。为了解决这个问题既要Wait-Free又要结果正确bq::ring_buffer发明了一种回滚机制当发生空间不足的时候可以做一次Rollback。然后返回空间不足的错误。其内存申请的伪码如下void* bq::ring_buffer::alloc(size_t len) { // 1. 计算ring_buffer剩余的可用空间 size_t free_space this-size_ - (this-in_ - this-out_); if (len free_space) { return nullptr; // 如果空间不足写入失败 } // 2. 申请内存最后申请到的内存就是从from开始的len长度内存 size_t from __sync_fetch_add(this-in_, len); // 3. check一下申请到的这个内存是否真的有效 while(from len this-out_ this-size_) { // 4. 已经空间不足了只能做回滚Rollback了 size_t expected_in from len; if(__sync_bool_compare_and_swap(expected_in, this-in_, from))//如果in_的值等于from len就把他回滚成from否则就自旋继续重新尝试回滚 { //回滚成功 return nullptr; //返回空间不足 } yield(); //让出时间片不要大家疯狂浪费计算资源 } // 5. 内存有效直接返回(可能是申请的时候就有效也可能是尝试回滚过程中消费者腾出新的空间导致这块内存又可用了) return to_addr(from); }这段代码不仅演示了bq::ring_buffer是如何做到Wait-Free的还演示了当空间不足时候的回滚算法。可能大家会有质疑觉得这个回滚算法性能好像很差也不再是Wait-Free的了。但是我们需要知道当回滚逻辑发生的时候说明消息队列的空间已经不足了这个时候系统的性能瓶颈将变成业务需要对消息队列扩容或者阻塞等待消费者线程取走数据腾出空间。这种时候这个CAS性能消耗反而变得无足轻重了。接下来重点说一下回滚算法的思路。为什么回滚算法需要是CAS的而不是直接fetch_add(this-in_, -len)这样把自己加上去的数值减掉。我们要知道回退的难度在于当in在fetch_add超标之后每个生产者线程都不知道应该将in回退到多少最合适会不会回退过多会不会回退过少。举例来说看下图的案例这一轮分配之前in的值为1000剩余数据12字节也就是说可以分配到1012但是由于ABC三个线程都同时在申请导致最终in被撑到了1030其中B和C两个线程发现自己拿到的数据段是超标的准备分别自行回滚。假如说我们采取直接对in减去自己分配的长度。如果线程B先执行可能会发生下面的一系列事故线程B先执行fetch_add(this-in_, -5)把in减小到1025。消费者线程D忽然消化了一大截数据剩余空间可以允许我们把in分配到1040了。线程B马上再次尝试分配5字节就获取到了1025到1030的数据段于是开始拷贝数据进去这个时候in变成了1030线程C进入回滚流程忽然发现自己拿的1015到1030的数据段其实没有超标就直接开始写入数据 最终的车祸现场如下图可以见到线程B和线程C分配的数据发生了冲突。那么基于CAS的回滚算法的核心原理就是让in从后往前一个一个回退每个线程一直在那里等着负责回退自己分配的那一段。如果回退过程中发现空间足够了就不用再回退了。方案总结BqLog的fetch_addrollback方案事实上完成了一个Wait-Free的并发队列模型。从最终benchmark的数据来看单说吞吐量和延迟在多并发情况下已经超越了LMAX Disruptor。虽然在客户端应用上该优化实际作用不大但是在server或者其他高并发环境该思路是有其正面价值的。
