Sync.Pool无锁ringbuffer队列+双向链表构建高性能缓存池

简介: Sync.Pool无锁ringbuffer队列+双向链表构建高性能缓存池

640.png

Sync.Pool核心原理剖析



上篇文章主要是聊了下Pool的使用相关,这篇文章主要从源码角度剖析Pool如何表现的这么优秀,它背后的设计理念有哪些值得我们学习,那么这篇文章就相对很干了,言归正传开始正题。


干货

  1. ringbuffer-无锁竞争
  2. 双向链表-动态扩容和P相互之间易窃取
  3. victim cache-两轮GC保证和提升GC性能
  4. 伪共享-cacheline内存优化
  5. 缓存池与P绑定-尽量减少竞争和利用多核特性
  6. 数据竞争-cas原子操作比Mutex性能好
  7. 位操作-性能优化极致(pack,unpack,cas),想想epoll事件位操作


1. Pool结构


type Pool struct {
  //noCopy标明该pool不应该被复制,结合go vet可实现代码检测
 noCopy noCopy 
  //local+localSize决定poolLocal
 local     unsafe.Pointer 
 localSize uintptr        
  //victim+victimSize接管poolLocal负责GC相关
 victim     unsafe.Pointer 
 victimSize uintptr        
  //构造新对象方法
 New func() interface{}
}


poolLocal结构

type poolLocal struct {
 poolLocalInternal
  //pad对齐 防止伪共享(false sharing) 后面单独介绍
 pad [128 - unsafe.Sizeof(poolLocalInternal{})%128]byte
}


poolLocalInternal结构

type poolLocalInternal struct {
 private interface{}  //只能被owner P所使用.
 shared  poolChain //owner P 可以 pushHead/popHead操作; 其他P只允许popTail.
}


poolChain结构

// poolChain的实现是一个双向队列,其中每个元素是前一个的双倍 
type poolChain struct {
  // head节点只能被producer访问,所以不需要同步机制 
  head *poolChainElt
  // tail节点被consumers访问,所以必须读写保证原子操作 
  tail *poolChainElt
}


poolChainElt结构

type poolChainElt struct {
  poolDequeue
  next, prev *poolChainElt
}


poolDequeue结构

//poolDequeue是一个无锁的固定大小单生产者,多消费者队列。 
type poolDequeue struct {
  headTail uint64 //存储head tail索引,通过mask和cas实现
  vals []eface //存储真正对象的数组
}


上面的pad属性介绍:


pad 属性,从这个属性的定义方式来看,明显是为了凑齐了 128 Byte 的整数倍。为什么会这么做呢?


这里是为了避免 CPU Cache 的 false sharing 问题:CPU Cache Line 通常是以 64 byte 或 128 byte 为单位。在我们的场景中,各个 P 的 poolLocal 是以数组形式存在一起。假设 CPU Cache Line 为 128 byte,而 poolLocal 不足 128 byte 时,那 cacheline 将会带上其他 P 的 poolLocal 的内存数据,以凑齐一整个 Cache Line。如果这时,两个相邻的 P 同时在两个不同的 CPU 核上运行,将会同时去覆盖刷新 CacheLine,造成 Cacheline 的反复失效,那 CPU Cache 将失去了作用。


CPU Cache 是距离 CPU 最近的 cache,如果能将其运用好,会极大提升程序性能。Golang 这里为了防止出现 false sharing 问题,主动使用 pad 的方式凑齐 128 个 byte 的整数倍,这样就不会和其他 P 的 poolLocal 共享一套 CacheLine。


因此pad属性是防止cpu 伪共享出现,提升程序性能的


2. 结构图

640.png


图片左边部分介绍:

  • Pool管理poolLocal,而poolLocal是长度为localSize(近似P的数量,通过runtime.GOMAXPROCS获取)的数组local的类型,这里面存储着各个P对应的本地对象池,可以看成是[P]poolLocal这种形式。
  • poolLocal有两个属性,一个是private,一个是share。private比较简单,因为他是owner P特持有的,不和其他P共享,重点介绍share。


图片中间部分介绍:

  • share是拥有poolChain这样结构的双向链表,有头尾指针,每个节点是一个poolDequeue结构


图片最后一部分介绍:

  • poolDequeue就是实现了ringbuffer结构的无锁队列,它是一个固定大小的单生产者,多消费者队列
  • 队列有头尾指针,不过因为底层是vals []eface数组,因此消费和添加都是通过headTail索引来实现的,操作需要cas保证。
  • head和tail之间的是可用对象,用绿色标识的部分。


为什么 poolChain 是这么一个双向链表 + ring buffer 的复杂结构呢?简单的每个链表项为单一元素不行吗


  1. 使用 ring buffer 是因为它有以下优点:
    ring buffer的下面两个特性,非常适合于sync.Pool的应用场景
  • 1. 预先分配好内存,且分配的内存项可不断复用
  • 2. 由于ring buffer 本质上是个数组,是连续内存结构,非常利于 CPU Cache。在访问poolDequeue 某一项时,其附近的数据项都有可能加载到统一 Cache Line 中,访问速度更快
  • 我们再注意看一个细节,poolDequeue 作为一个 ring buffer,自然需要记录下其 head 和 tail 的值。但在 poolDequeue 的定义中,head 和 tail 并不是独立的两个变量,只有一个 uint64 的 headTail 变量。
  • 这是因为 headTail 变量将 head 和 tail 打包在了一起:其中高 32 位是 head 变量,低 32 位是 tail 变量。如下图所示:
    为什么会有这个复杂的打包操作呢?这个其实是个非常常见的lock free(无锁)优化手段。
    对于一个 poolDequeue 来说,可能会被多个 P 同时访问(具体原因见下文 Get 函数中的对象窃取逻辑),这个时候就会带来并发问题。
    例如:当 ring buffer 空间仅剩一个的时候,即 head - tail = 1。如果多个 P 同时访问 ring buffer,在没有任何并发措施的情况下,两个 P 都可能会拿到对象,这肯定是不符合预期的。
    在不引入 Mutex 锁的前提下,sync.Pool 是怎么实现的呢?sync.Pool 利用了 atomic 包中的 CAS 操作。两个 P 都可能会拿到对象,但在最终设置 headTail 的时候,只会有一个 P 调用 CAS 成功,另外一个 CAS 失败。


ptrs2 := d.pack(head, tail+1)
    if atomic.CompareAndSwapUint64(&d.headTail, ptrs, ptrs2) {
       // Success.
       slot = &d.vals[tail&uint32(len(d.vals)-1)]
       break
  }
  • 在更新 head 和 tail 的时候,也是通过原子变量 + 位运算进行操作的。例如,当实现 head-- 的时候,需要通过以下代码实现:
head--
  ptrs2 := d.pack(head, tail)
  if atomic.CompareAndSwapUint64(&d.headTail, ptrs, ptrs2) {
     // We successfully took back slot.
     slot = &d.vals[head&uint32(len(d.vals)-1)]
     break
  }
  1. 使用双向链表是因为它有以下优点:
  • 当前P的缓存池为空的时候,那么将尝试从其他P的缓存池中窃取对象。窃取的时候是从别的P的缓存池中尾部开始取的。
  • 当前P的缓存池不为空就从自己的缓存池中头部开始取的。
  • 所以一个是从后向前遍历,另一个是从前向后遍历,因此只有双向链表适合这种形式
  • 如果长度为8的poolDequeue装满了,可以申请2倍大小的poolDequeue,让head指向它,这种动态扩容的方式链表很合适啊。
  • 还有就是P如果是自己pushHead/popHead它自己的缓存池是不用加锁的,这样效率更高。


3. Put/Get源码


Get

func (p *Pool) Get() interface{} {
  // 获取当前P的对象池和Pid
 l, pid := p.pin()
 x := l.private
 l.private = nil
 if x == nil {
  //尝试从本地share队列头部pop
    x, _ = l.shared.popHead()
    if x == nil {
        //如果空,尝试从其他P的share队列尾部pop 窃取
       x = p.getSlow(pid)
     }
   }
  // 解绑groutine和P
 runtime_procUnpin()
  //如果还没有获取到对象,那么尝试构造新对象
 if x == nil && p.New != nil {
   x = p.New()
 }
 return x
}
func (p *Pool) getSlow(pid int) interface{} {
 size := runtime_LoadAcquintptr(&p.localSize)
 locals := p.local    
  // Try to steal one element from other procs.
  //尝试从其他P偷取一个对象
 for i := 0; i < int(size); i++ {
   l := indexLocal(locals, (pid+i+1)%int(size))
   if x, _ := l.shared.popTail(); x != nil {
      return x
  }
 }
 //尝试从victim cache中获取。因为我们尽可能想淘汰victim中的对象
  // 所以在尝试从所有的primary cache中获取失败后操作
 size = atomic.LoadUintptr(&p.victimSize)
 if uintptr(pid) >= size {
   return nil
 }
 locals = p.victim
 l := indexLocal(locals, pid)
 if x := l.private; x != nil {
   l.private = nil
   return x
 }
  //从victim cache中窃取一个对象
 for i := 0; i < int(size); i++ {
   l := indexLocal(locals, (pid+i)%int(size))
    if x, _ := l.shared.popTail(); x != nil {
      return x
   }
 }
 //Mark the victim cache as empty
 //标记victim cache为空 即清理victim cache
 atomic.StoreUintptr(&p.victimSize, 0)
 return nil
}


Put

func (p *Pool) Put(x interface{}) {
 if x == nil {
  return
 }
 //返回当前groutine所绑定的p,并且固定当前P和groutine的绑定
 l, _ := p.pin()
 //首先给private 
 if l.private == nil {
  l.private = x
  x = nil
 }
 //private不为空,就插入到当前head指向的双向链表节点的ringbuffer的head位置,并更新head索引。
 if x != nil {
  l.shared.pushHead(x)
 }
 //解绑P和当前groutine的固定关系
 runtime_procUnpin()
}


4. GC清理


func poolCleanup() {
 // 函数将在gc开始前被调用.
 // 在gc stop word阶段,pool将不会产生外部函数调用分配对象的行为. 
 // 从oldPools中删除所有的victim cache.
 for _, p := range oldPools {
   p.victim = nil
   p.victimSize = 0
 }
 // 移动local cache到victim cache.
 //victim接管local
 for _, p := range allPools {
   p.victim = p.local
   p.victimSize = p.localSize
   p.local = nil
   p.localSize = 0
 }
 // 现在所有的local cache被移动到了victim cache中,local cache为空
 oldPools, allPools = allPools, nil
}


经历两轮GC,第一轮GC让victim cache接管local cache;第二轮GC就是全部清除victim cache,为什么这么设计?因为假如第一轮就全部清除,那么之后再获取对象的时候性能就会下降,因为很有可能在大量创建对象了,所以它GC第一轮先放到victim cache中,等到第二轮在处理。当然如果经历了第一轮GC之后又从victim cache中获取了一些对象,那么在第二轮的时候就不会删除,想想LRU的机制。。。victim的设计也间接提升了GC的性能,因为相对来说Sync.Pool池化的对象是long-live的,而GC的主要对象是short-live的,所以会减少GC的执行执行。


5. 小结


此篇文章主要是介绍了Sync.Pool核心原理,因为涉及到的源码比较多,需要大家好好消化。还有就是从源码中学到了很多NB的技术和思想,这种探索非常值得,内卷不是说我看了很多源码就不了了之,更重要的是从其中真正学到了什么,如果学不到我还研究它有何意义?只是单纯为了内卷?


参考连接:

https://lenshood.github.io/2021/04/19/lock-free-ring-buffer/https://www.cyhone.com/articles/think-in-sync-pool/https://developpaper.com/understand-the-design-and-implementation-of-sync-pool-in-go-1-13/https://go-review.googlesource.com/c/go/+/166961/https://coolshell.cn/articles/20793.htmlhttps://gist.github.com/sunhay/9e946ff157ffe1d2fa6499049c284651


相关文章
|
2月前
|
消息中间件 缓存 NoSQL
Redis 是一个高性能的键值对存储系统,常用于缓存、消息队列和会话管理等场景。
【10月更文挑战第4天】Redis 是一个高性能的键值对存储系统,常用于缓存、消息队列和会话管理等场景。随着数据增长,有时需要将 Redis 数据导出以进行分析、备份或迁移。本文详细介绍几种导出方法:1)使用 Redis 命令与重定向;2)利用 Redis 的 RDB 和 AOF 持久化功能;3)借助第三方工具如 `redis-dump`。每种方法均附有示例代码,帮助你轻松完成数据导出任务。无论数据量大小,总有一款适合你。
84 6
|
4月前
|
缓存 NoSQL Java
Redis深度解析:解锁高性能缓存的终极武器,让你的应用飞起来
【8月更文挑战第29天】本文从基本概念入手,通过实战示例、原理解析和高级使用技巧,全面讲解Redis这一高性能键值对数据库。Redis基于内存存储,支持多种数据结构,如字符串、列表和哈希表等,常用于数据库、缓存及消息队列。文中详细介绍了如何在Spring Boot项目中集成Redis,并展示了其工作原理、缓存实现方法及高级特性,如事务、发布/订阅、Lua脚本和集群等,帮助读者从入门到精通Redis,大幅提升应用性能与可扩展性。
91 0
|
28天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
54 5
|
1月前
|
缓存 NoSQL PHP
Redis作为PHP缓存解决方案的优势、实现方式及注意事项。Redis凭借其高性能、丰富的数据结构、数据持久化和分布式支持等特点,在提升应用响应速度和处理能力方面表现突出
本文深入探讨了Redis作为PHP缓存解决方案的优势、实现方式及注意事项。Redis凭借其高性能、丰富的数据结构、数据持久化和分布式支持等特点,在提升应用响应速度和处理能力方面表现突出。文章还介绍了Redis在页面缓存、数据缓存和会话缓存等应用场景中的使用,并强调了缓存数据一致性、过期时间设置、容量控制和安全问题的重要性。
43 5
|
1月前
|
缓存 NoSQL 数据库
运用云数据库 Tair 构建缓存为应用提速,完成任务得苹果音响、充电套装等好礼!
本活动将带大家了解云数据库 Tair(兼容 Redis),通过体验构建缓存以提速应用,完成任务,即可领取罗马仕安卓充电套装,限量1000个,先到先得。邀请好友共同参与活动,还可赢取苹果 HomePod mini、小米蓝牙耳机等精美好礼!
|
1月前
|
存储 缓存 前端开发
利用 Webpack 5 的持久化缓存来提高构建效率
【10月更文挑战第23天】利用 Webpack 5 的持久化缓存是提高构建效率的有效手段。通过合理的配置和管理,我们可以充分发挥缓存的优势,为项目的构建和开发带来更大的便利和效率提升。你可以根据项目的实际情况,结合以上步骤和方法,进一步优化和完善利用持久化缓存的策略,以达到最佳的构建效果。同时,不断探索和实践新的方法和技术,以适应不断变化的前端开发环境和需求。
|
2月前
|
存储 缓存 NoSQL
构建高性能Web应用:缓存的重要性及其实现
构建高性能Web应用:缓存的重要性及其实现
|
3月前
|
缓存 监控 Java
造轮子能力大提升:基于SpringBoot打造高性能缓存组件
在快节奏的软件开发领域,"不重复造轮子" 常常被视为提高效率的金科玉律。然而,在某些特定场景下,定制化的高性能缓存组件却是提升系统性能、优化用户体验的关键。今天,我们将深入探讨如何利用SpringBoot框架,从零开始打造一款符合项目需求的高性能缓存组件,分享我在这一过程中的技术心得与学习体会。
74 6
|
4月前
|
Java 开发者 JavaScript
Struts 2 开发者的秘籍:隐藏的表单标签库功能,能否成为你下个项目的大杀器?
【8月更文挑战第31天】Struts 2表单标签库是提升Web页面交互体验的神器。它提供丰富的标签,如`&lt;s:textfield&gt;`和`&lt;s:select&gt;`,简化表单元素创建与管理,支持数据验证和动态选项展示。结合示例代码,如创建文本输入框并与Action类属性绑定,显著提升开发效率和用户体验。通过自定义按钮样式等功能,Struts 2表单标签库让开发者更专注于业务逻辑实现。
53 0
|
4月前
|
缓存 NoSQL 数据库
【超实用秘籍】FastAPI高手教你如何通过最佳实践构建高效Web应用:从代码组织到异步编程与缓存优化的全方位指南!
【8月更文挑战第31天】FastAPI凭借出色性能和易用性成为现代Web应用的首选框架。本文通过示例代码介绍构建高效FastAPI应用的最佳实践,包括开发环境搭建、代码模块化组织、异步编程及性能优化等。通过模块化设计和异步数据库操作,结合缓存技术,大幅提升应用性能与可维护性,助您轻松应对高并发场景。
341 0