皮皮网

【官网微信源码】【祈福源码】【印章源码】ringbuffer源码分析

来源:模糊查询 网页源码 时间:2024-12-24 10:35:52

1.golang本地缓存(bigcache/freecache/fastcache等)选型对比及原理总结
2.简单概括Linux内核源码高速缓存原理(图例解析)
3.百度 UidGenerator 源码解析
4.Linux内核源码解析---EPOLL实现4之唤醒等待进程与惊群问题
5.golang chan 最详细原理剖析,源码全面源码分析!分析看完不可能不懂的源码!
6.eBPF 程序编写 - libbpf

ringbuffer源码分析

golang本地缓存(bigcache/freecache/fastcache等)选型对比及原理总结

       以下内容来自腾讯后台研发工程师jayden

       导语:提到本地缓存大家都不陌生,分析只要是源码个有点经验的后台开发人员,都知道缓存的分析官网微信源码作用和弊端。本篇文章我们就来简单聊聊在golang做业务开发的源码过程中,本地缓存的分析一些可选的开源方案,分析它们的源码特点,以及内部的分析实现原理。

       1.本地缓存需求分析

       首先来梳理一下业务开发过程中经常面临的源码本地缓存的一些需求。我们一般做缓存就是分析为了能提高系统的读写性能,缓存的源码命中率越高,也就意味着缓存的分析效果越好。其次本地缓存一般都受限于本地内存的源码大小,所有全量的数据一般存不下。那基于这样的场景一方面是想缓存的数据越多,则命中率理论上也会随着缓存数据的增多而提高;另外一方面是想,既然所有的数据存不下那就想办法利用有限的内存存储有限的数据。这些有限的数据需要是经常访问的,同时有一定时效性(不会频繁改变)的。基于这两个点展开,我们一般对本地缓存会要求其满足支持过期时间、支持淘汰策略。最后再使用自动管理内存的语言例如golang等开发时,还需要考虑在加入本地缓存后引发的GC问题。

       分析完我们日常本地缓存的诉求,再结合我们日常开发用到的golang语言,我们可以提炼得到golang本地缓存组件必须具备以下几个能力:

       分析清楚了我们的需求,也明确了我们需要的能力。那自然优先考虑golang内置的标准库中是否存在这样的组件可以直接使用呢?很遗憾,没有。golang中内置的可以直接用来做本地缓存的无非就是map和sync.Map。而这两者中,map是非并发安全的数据结构,在使用时需要加锁;而sync.Map虽然是线程安全的。但是需要在并发读写时加锁。此外二者均无法支持数据的过期和淘汰,同时在存储大量数据时,又会产生比较频繁的GC问题,更严重的情况下导致线上服务无法稳定运行。

       既然标准库中没有我们满足上述需求的本地缓存组件,那我们就想只有两种解决方案了

       那首先面临的第一个问题就是方案的调研和选型,没有合适的方案时自己再来动手构建。下面我们就来给大家介绍下golang中哪些可以直接来使用的本地缓存组件吧。

       2.golang本地缓存组件概览

       golang中本地缓存方案可选的有如下一些:

       下面通过笔者一段时间的调研和研究,将golang可选的开源本地缓存组件汇总为下表,方便大家在方案选型时作参考。

       在上述方案中,freecache、bigcache、fastcache、ristretto、祈福源码groupcache这几个大家根据实际的业务场景首选,offheap有定制需求时可考虑。

       通过上表的总结,个人想再此再谈几点关于本地缓存组件的理解:

       (1)上述本地缓存组件中,实现零GC的方案主要就两种:

       a.无GC:分配堆外内存(Mmap)

       b.避免GC:map非指针优化(map[uint]uint)或者采用slice实现一套无指针的map

       c.避免GC:数据存入[]byte slice(可考虑底层采用环形队列封装循环使用空间)

       (2)实现高性能的关键在于:

       a.数据分片(降低锁的粒度)

       3. 主流缓存组件实现原理剖析

       在本节中我们会重点分析下freecache、bigcache、fastcache、offheap这几个组件内部的实现原理。

       3.1 freecache实现原理

       首先分析下freecache的内部实现原理。在freecache中它通过segment来进行对数据分片,freecache内部包含个segment,每个segment维护一把互斥锁,每一条kv数据进来后首先会根据k进行计算其hash值,然后根据hash值决定当前的这条数据落入到哪个segment中。

       对于每个segment而言,它由索引、数据两部分构成。

       索引:其中索引最简单的方式采用map来维护,例如map[uint]uint这种。而freecache并没有采用这种做法,而是通过采用slice来底层实现一套无指针的map,以此避免GC扫描。

       数据:数据采用环形缓冲区来循环使用,底层采用[]byte进行封装实现。数据写入环形缓冲区后,记录写入的位置index作为索引,读取时首先读取数据header信息,然后再读取kv数据。

       在freecache中数据的传递过程是:freecache->segment->(slot,ringbuffer) 下图是freecache的内部实现框架图。

       总结: freecache通过利用数据分片减小锁的粒度,然后再存储时索引并没有采用内置的map来维护而是采用自建map减少指针来避免GC,同时数据存储时采用预先分配内存然后后边循环使用。通过上述两种方法保证了在堆上分配内存同时减少GC对系统性能的影响。

       3.2 bigcache实现原理

       bigcache和freecache类似,也是一个零GC、高性能的cache组件,但是它的实现和freecache还是有些差异,这儿有篇 英文博客介绍bigcache设计原理的,内容稍长感兴趣的可以阅读下,下面我们介绍一下bigcache的实现原理。

       bigcache同样是采用分片的方式构成,一个bigcache对象包含2^n 个cacheShard对象,默认是个。每个cacheShard对象维护着一把sync.RWLock锁(读写锁)。所有的数据会分散到不同的cacheShard中。

       每个cacheShard同样由索引和数据构成。索引采用map[uint]uint来存储,数据采用entry([]byte)环形队列存储。索引中存储的是该条数据在entryBuffer写入的位置pos。每条kv数据按照TLV的格式写入队列。

       不过值得注意的是,和bigcache和freecache不同的印章源码一点在于它的环形队列可以自动扩容。同时bigcache中数据的过期是通过全局的时间窗口维护的,每个单独的kv无法设置不同的过期时间。

       下面是bigcache的内容实现原理框架图。

       总结:bigcache思路和freecache大体相同,只不过在索引存储时更为巧妙,直接采用内置的map结构加上基础数据类型来实现。同时底层存储数据的队列也可以根据空间大小来决定是否扩容。唯一的缺陷是无法针对每个key进行设置不同的过期时间。这个个人认为如果想用bigcache同时想要这个特性,可以进行二次开发一下。

       通过 性能测试数据来看,bigcache性能要比freecache稍微好一点。大家可以思考下他们性能的差异可能会在哪里呢?

       3.3 fastcache实现原理

       本节介绍下fastcache的实现原理,根据fastcache官方文档介绍,它的灵感来自于bigcache。所以整体的思路和bigcache很类似,数据通过bucket进行分片。fastcache由个bucket构成。每个bucket维护一把读写锁。在bucket内部数据同理是索引、数据两部分构成。索引用map[uint]uint存储。数据采用chunks二维的切片(二维数组)存储。不过值得注意的是fastcache有一个很大的特性是,它的内存分配是在堆外分配的,而不是在堆上分配的。堆外分配的内存。这样做也就避免了golang GC的影响。下图是fastcache内部实现框架图。

       总结: fastcache一方面充分利用了分片来降低锁的粒度,另一方面在索引存储时采用了对map的优化,同时在分配内存时,直接从堆外申请内存,自己实现了分配和释放内存的逻辑。通过上述手段使得GC的影响降到了最低。fastcache唯一的缺陷是官方提供的版本没有提供针对kv数据的过期时间这个特性。所以如果需要这个特性的话,需要自己动手二次开发。整体从性能上来看是比bigcache和freecache都更优。

       3.4 offheap实现原理

       本节介绍下offheap的相关内容,offheap其实功能就比较简单了,就是一个基于堆外内存构建的哈希表。它通过直接调用系统调用函数来分配内存。然后在内部通过数组来实现哈希表。实现过程中当发生哈希冲突时,它是采用探测法来解决。由于是在堆外分配的内存上构建的哈希表。导致它的GC开销非常的小。下图是offheap的内部实现框架图。

       总结:offheap内部由于是采用探测法解决哈希冲突的,所以当哈希冲突严重时数据删除、查询都会带来非常复杂的打车源码处理流程。而且性能也会有一些损耗。可以作为学习和研究的项目还是非常不错的。

       4.总结

       本文主要从日常需求出发,分析了日常业务过程中对本地缓存的需求,再调研了业界可选的一些组件并进行了对比,希望对本地缓存选型上起到一些参考和帮助。最后再对其中比较重要的几个组件如freecache、bigcache、fastcache、offheap等做了内部实现的简单介绍。上述内容只是从架构层面展开介绍,后续有时间再从源码层面做一些分析。由于篇幅限制本篇内容并未对map、sync.Map、go-cache、groupcache进行介绍。感兴趣的读者可以自行搜索资料进行阅读。如果大致理解了上述原理的童鞋也可以自己动手实践起来,造个轮子看看。

       5.参考资料

       欢迎点赞分享,关注 @鹅厂架构师,一起探索更多业界领先产品技术。

简单概括Linux内核源码高速缓存原理(图例解析)

       高速缓存(cache)概念和原理涉及在处理器附近增加一个小容量快速存储器(cache),基于SRAM,由硬件自动管理。其基本思想为将频繁访问的数据块存储在cache中,CPU首先在cache中查找想访问的数据,而不是直接访问主存,以期数据存放在cache中。

       Cache的基本概念包括块(block),CPU从内存中读取数据到Cache的时候是以块(CPU Line)为单位进行的,这一块块的数据被称为CPU Line,是CPU从内存读取数据到Cache的单位。

       在访问某个不在cache中的block b时,从内存中取出block b并将block b放置在cache中。放置策略决定block b将被放置在哪里,而替换策略则决定哪个block将被替换。

       Cache层次结构中,Intel Core i7提供一个例子。cache包含dCache(数据缓存)和iCache(指令缓存),解决关键问题包括判断数据在cache中的位置,数据查找(Data Identification),地址映射(Address Mapping),替换策略(Placement Policy),以及保证cache与memory一致性的问题,即写入策略(Write Policy)。

       主存与Cache的地址映射通过某种方法或规则将主存块定位到cache。映射方法包括直接(mapped)、全相联(fully-associated)、一对多映射等。直接映射优点是地址变换速度快,一对一映射,vuex源码替换算法简单,但缺点是容易冲突,cache利用率低,命中率低。全相联映射的优点是提高命中率,缺点是硬件开销增加,相应替换算法复杂。组相联映射是一种特例,优点是提高cache利用率,缺点是替换算法复杂。

       cache的容量决定了映射方式的选取。小容量cache采用组相联或全相联映射,大容量cache采用直接映射方式,查找速度快,但命中率相对较低。cache的访问速度取决于映射方式,要求高的场合采用直接映射,要求低的场合采用组相联或全相联映射。

       Cache伪共享问题发生在多核心CPU中,两个不同线程同时访问和修改同一cache line中的不同变量时,会导致cache失效。解决伪共享的方法是避免数据正好位于同一cache line,或者使用特定宏定义如__cacheline_aligned_in_smp。Java并发框架Disruptor通过字节填充+继承的方式,避免伪共享,RingBuffer类中的RingBufferPad类和RingBufferFields类设计确保了cache line的连续性和稳定性,从而避免了伪共享问题。

百度 UidGenerator 源码解析

       雪花算法(Snowflake)是一种生成分布式全局唯一 ID 的算法,用于推文 ID 的生成,并在 Discord 和 Instagram 等平台采用其修改版本。一个 Snowflake ID 由 位组成,其中前 位表示时间戳(毫秒数),接下来的 位用于标识计算机, 位作为序列号,以确保同一毫秒内生成的多个 ID。此算法基于时间生成,按时间排序,允许通过 ID 推断生成时间。Snowflake ID 的生成包括时间戳、工作机器 ID 和序列号,确保了分布式环境中的全局唯一性。

       在 Java 中实现的 UidGenerator 基于 Snowflake 算法,支持自定义工作机器 ID 位数和初始化策略。它通过使用未来时间解决序列号的并发限制,采用 RingBuffer 缓存已生成的 UID,进行并行生产和消费,并对 CacheLine 进行补全以避免硬件级「伪共享」问题。在 Docker 等虚拟化环境下,UidGenerator 支持实例自动重启和漂移场景,单机 QPS 可达 万。

       UidGenerator 采用不同的实现策略,如 DefaultUidGenerator 和 CachedUidGenerator。DefaultUidGenerator 提供了基础的 Snowflake ID 生成模式,无需预存 UID,即时计算。而 CachedUidGenerator 则预先缓存 UID,通过 RingBuffer 提前填充并设置阈值自动填充机制,以提高生成效率。

       RingBuffer 是 UidGenerator 的核心组件,用于缓存和管理 UID 的生成。在 DefaultUidGenerator 中,时间基点通过 epochStr 参数定义,用于计算时间戳。Worker ID 分配器在初始化阶段自动为每个工作机器分配唯一的 ID。核心生成方法处理异常情况,如时钟回拨,通过二进制运算生成最终的 UID。

       CachedUidGenerator 则利用 RingBuffer 进行 UID 的缓存,根据填充阈值自动填充,以减少实时生成和计算的开销。RingBuffer 的设计考虑了伪共享问题,通过 CacheLine 补齐策略优化读写性能,确保在并发环境中高效生成 UID。

       总结而言,Snowflake 算法和 UidGenerator 的设计旨在提供高性能、分布式且全局唯一的 ID 生成解决方案,适用于多种场景,包括高并发环境和分布式系统中。通过精心设计的组件和策略,确保了 ID 的生成效率和一致性,满足现代应用对 ID 管理的严格要求。

Linux内核源码解析---EPOLL实现4之唤醒等待进程与惊群问题

       在Linux内核源码的EPOLL实现中,第四部分着重探讨了数据到来时如何唤醒等待进程以及惊群问题。当网卡接收到数据,DMA技术将数据复制到内存RingBuffer,通过硬中断通知CPU,然后由ksoftirqd线程处理,最终数据会进入socket接收队列。虽然ksoftirqd的创建过程不在本节讨论,但核心是理解数据如何从协议层传递到socket buffer。

       在tcp_ipv4.c中,当接收到socket buffer时,会首先在连接表和监听表中寻找对应的socket。一旦找到,进入tcp_rcv_established函数,这里会检查socket是否准备好接收数据,通过调用sock_data_ready,其初始值为sock_def_readable,进而进入wake_up函数,唤醒之前挂上的wait_queue_t节点。

       在wake_up方法中,会遍历链表并回调ep_poll_callback,这个函数是epoll的核心逻辑。然而,如果epoll的设置没有启用WQ_FLAG_EXCLUSIVE,就会导致惊群效应,即唤醒所有阻塞在当前epoll的进程。这在default_wake_function函数中体现,如果没有特殊标记,进程会立即被唤醒并进入调度。

       总结来说,epoll的唤醒过程涉及socket buffer、协议层处理、链表操作以及回调函数,其中惊群问题与默认的唤醒策略密切相关。理解这些细节,有助于深入理解Linux内核中EPOLL的异步操作机制。

golang chan 最详细原理剖析,全面源码分析!看完不可能不懂的!

       大纲

       概述

       chan 是 golang 的核心结构,是与其他高级语言区别的显著特色之一,也是 goroutine 通信的关键要素。尽管广泛使用,但对其深入理解的人却不多。本文将从源码编译器的视角,全面剖析 channel 的用法。

       channel 的本质

       从实现角度来看,golang 的 channel 实质上是环形队列(ringbuffer)的实现。我们将 chan 称为管理结构,channel 中可以放置任何类型的对象,称为元素。

       channel 的使用方法

       我们从 channel 的使用方式入手,详细介绍 channel 的使用方法。

       channel 的创建

       创建 channel 时,用户通常有两种选择:创建带有缓冲区和不带缓冲区的 channel。这对应于 runtime/chan.go 文件中的 makechan 函数。

       channel 入队

       用户使用姿势:对应函数实现为 chansend,位于 runtime/chan.go 文件。

       channel 出队

       用户使用姿势:对应函数分别是 chanrecv1 和 chanrecv2,位于 runtime/chan.go 文件。

       结合 select 语句

       用户使用姿势:对应函数实现为 selectnbsend,位于 runtime/chan.go 文件中。

       结合 for-range 语句

       用户使用姿势:对应使用函数 chanrecv2,位于 runtime/chan.go 文件中。

       源码解析

       以上,我们通过宏观的用户使用姿势,了解了不同使用姿势对应的不同实现函数,接下来将详细分析这些函数的实现。

       makechan 函数

       负责 channel 的创建。在 go 程序中,当我们写类似 v := make(chan int) 的初始化语句时,就会调用不同类型对应的初始化函数,其中 channel 的初始化函数就是 makechen。

       runtime.makechan

       定义原型:

       通过这个,我们可以了解到,声明创建一个 channel 实际上是得到了一个 hchan 的指针,因此 channel 的核心结构就是基于 hchan 实现的。

       其中,t 参数指定元素类型,size 指定 channel 缓冲区槽位数量。如果是带缓冲区的 channel,那么 size 就是槽位数;如果没有指定,那么就是 0。

       makechan 函数执行了以下两件事:

       1. 参数校验:主要是越界或 limit 的校验。

       2. 初始化 hchan:分为三种情况:

       所以,我们看到除了 hchan 结构体本身的内存分配,该结构体初始化的关键在于四个字段:

       hchan 结构

       makechan 函数负责创建了 chan 的核心结构-hchan,接下来我们将详细分析 hchan 结构体本身。

       在 makechan 中,初始化时实际上只初始化了四个核心字段:

       我们使用 channel 时知道,channel 常常会因为两种情况而阻塞:1)投递时没有空间;2)取出时还没有元素。

       从以上描述来看,就涉及到 goroutine 阻塞和 goroutine 唤醒,这个功能与 recvq,sendq 这两个字段有关。

       waitq 类型实际上是一个双向列表的实现,与 linux 中的 LIST 实现非常相似。

       chansend 函数

       chansend 函数是在编译器解析到 c <- x 这样的代码时插入的,本质上就是把一个用户元素投递到 hchan 的 ringbuffer 中。chansend 调用时,一般用户会遇到两种情况:

       接下来,我们看看 chansend 究竟做了什么。

       当我们在 golang 中执行 c <- x 这样的代码,意图将一个元素投递到 channel 时,实际上调用的是 chansend 函数。这个函数分几个场景来处理,总结来说:

       关于返回值:chansend 返回值标明元素是否成功入队,成功则返回 true,否则 false。

       select 的提前揭秘:

       golang 源代码经过编译会变成类似如下:

       而 selectnbasend 只是一个代理:

       小结:没错,chansend 功能就是这么简单,本质上就是一句话:将元素投递到 channel 中。

       chanrecv 函数

       对应的 golang 语句是 <- c。该函数实现了 channel 的元素出队功能。举个例子,编译对应一般如下:

       golang 语句:

       对应:

       golang 语句(这次的区别在于是否有返回值):

       对应:

       编译器在遇到 <- c 和 v, ok := <- c 的语句时,会换成对应的 chanrecv1,chanrecv2 函数,这两个函数本质上都是一个简单的封装,元素出队的实现函数是 chanrecv,我们详细分析这个函数。

       chanrecv 函数的返回值有两个值,selected,received,其中 selected 一般作为 select 结合的函数返回值,指明是否要进入 select-case 的代码分支,received 表明是否从队列中成功获取到元素,有几种情况:

       selectnbsend 函数

       该函数是 c <- v 结合到 select 时的函数,我们使用 select 的 case 里面如果是一个 chan 的表达式,那么编译器会转换成对应的 selectnbsend 函数,如下:

       对应编译函数逻辑如下:

       selectnbsend 本质上也就是个 chansend 的封装:

       chansend 的内部逻辑上面已经详细说明过,唯一不同的就是 block 参数被赋值为 false,也就是说,在 ringbuffer 没有空间的情况下也不会阻塞,直接返回。划重点:chan 在这里不会切走执行权限。

       selectnbrecv 函数

       该函数是 v := <- c 结合到 select 时的函数,我们使用 select 的 case 里面如果是一个 chan 的表达式,那么编译器会转换成对应的 selectnbsrecv 函数,如下:

       对应编译函数逻辑如下:

       selectnbrecv 本质上也就是个 chanrecv 的封装:

       chanrecv 的内部逻辑上面已经详细说明过,在 ringbuffer 没有元素的情况下也不会阻塞,直接返回。这里不会因此而切走调度权限。

       selectnbrecv2 函数

       该函数是 v, ok = <- c 结合到 select 时的函数,我们使用 select 的 case 里面如果是一个 chan 的表达式,那么编译器会转换成对应的 selectnbrecv2 函数,如下:

       对应编译函数逻辑如下:

       selectnbrecv2 本质上是个 chanrecv 的封装,只不过返回值不一样而已:

       chanrecv 的内部逻辑上面已经详细说明过,在 ringbuffer 没有元素的情况下也不会阻塞,直接返回。这里不会因此而切走调度权限。selectnbrecv2 与 selectnbrecv 函数的不同之处在于还有一个 ok 参数指明是否获取到了元素。

       chanrecv2 函数

       chan 可以与 for-range 结合使用,编译器会识别这种语法。如下:

       这个本质上是个 for 循环,我们知道 for 循环关键是拆分成三个部分:初始化、条件判断、条件递进。

       那么在我们 for-range 和 chan 结合起来之后,这三个关键因素又是怎么理解的呢?简述如下:

       init 初始化:无

       condition 条件判断:

       increment 条件递进:无

       当编译器遇到上面 chan 结合 for-range 写法时,会转换成 chanrecv2 的函数调用。目的是从 channel 中出队元素,返回值为 received。首先看下 chanrecv2 的实现:

       chan 结合 for-range 编译之后的伪代码如下:

       划重点:从这个实现中,我们可以获取一个非常重要的信息,for-range 和 chan 的结束条件只有这个 chan 被 close 了,否则一直会处于这个死循环内部。为什么?注意看 chanrecv 接收的参数是 block=true,并且这个 for-range 是一个死循环,除非 chanrecv2 返回值为 false,才有可能跳出循环,而 chanrecv2 在 block=true 场景下返回值为 false 的唯一原因只有:这个 chan 是 close 状态。

       总结

       golang 的 chan 使用非常简单,这些简单的语法糖背后其实都是对应了相应的函数实现,这个翻译由编译器来完成。深入理解这些函数的实现,对于彻底理解 chan 的使用和限制条件是必不可少的。深入理解原理,知其然知其所以然,你才能随心所欲地使用 golang。

eBPF 程序编写 - libbpf

       eBPF程序编写通过内核的bpf系统调用加载ebpf二进制,实现对MAP的增删改操作。ebpf源代码使用C语言编译生成bpf字节码。eBPF程序能够访问MAP,调用内核函数,访问内核与用户态内存,并进行计算与分支控制,但需避免死循环。

       eBPF程序在加载后,与内核的特定hook点结合,被动执行,如tracepoint、kprobe、uprobe、cgroup等,提供高效的数据通信机制,如输出数据到perf_buffer或ringbuffer。

       eBPF程序还能通过修改hook函数的返回值,实现函数劫持。但此功能仅适用于标有ERR_INJECT的函数。

       libbpf作为辅助工具简化bpf编程,用户态与内核态逻辑分离,框架负责通信、加载与卸载bpf程序。它提供丰富的helper函数,并实现CO-RE,确保bpf程序跨内核版本运行。

       libbpf通过记录relocation信息于bpf程序的.BTF section,配合clang编译bpf后端增加的builtin函数,实现程序跨内核版本运行。编译后,bpf程序以用户态可执行二进制形式存在,内核态程序作为ro数据段嵌入其中,形成独立可部署的文件。

       libbpf的CORE方式相较于其他工具集有显著优势,例如bcc-tools工具集合采用libbpf重写。编写eBPF程序时,参照libbpf-bootstrap/examples/c模板,通常需要两个文件:BTF记录数据结构信息,确保程序在不同内核版本上运行的兼容性。