导语 | 在召回排序业务中,由于上游请求量较大,对下游存储服务造成较大压力,业务场景要求高性能和非强一致性,所以我采用golang并发安全k-v缓存开源库进行性能优化,以下是对其调研、对比分析。如有错误,请多指正。


一、Golang map

(一)并发读写测试

在Golang中原生map在并发场景下,同时读写是线程不安全的,无论key是否一样。以下是测试代码:


如上图的demo,并发读写map的不同key,运行结果如下:


map读的时候会检查hashWriting标志,如果有这个标志,就会报并发错误。写的时候会设置这个标志:h.flags|=hashWriting.设置完之后会取消这个标记。map的并发问题不是那么容易被发现, 可以利用-race参数来检查。map并发读写冲突检测机制不是本文的重点,不过感兴趣的同学可以通过以下链接深入了解下。

编译时的选项-race,为何能分析出并发问题,详见:

视频讲解:


(二)map+读写锁

在官方库sync.map没出来前,Go maps in action推荐的做法是使用map+RWLock,比如定义一个匿名struct变量,其包含map、RWLock,如下所示:

可以这样从counter中读数据

可以这样往counter中写数据

那Go 1.9版本实现的sync.map和上面的这种实现方式有什么不同?它适用于哪些场景呢?它在哪些方面做了性能优化呢?


二、sync.map


sync.map是用读写分离实现的,其思想是空间换时间。和map+RWLock的实现方式相比,它做了一些优化:可以无锁访问read map,而且会优先操作read map,倘若只操作read map就可以满足要求(增删改查遍历),那就不用去操作write map(它的读写都要加锁),所以在某些特定场景中它发生锁竞争的频率会远远小于map+RWLock的实现方式。

接下来着重介绍下sync.map的源码,以了解其运作原理。

(一)变量介绍

  • 结构体Map


  • 结构体readOnly

第一点的结构read存的就是readOnly,m是一个map,key是interface,value是指针entry,其指向真实数据的地址,amended等于true代表dirty中有readOnly.m中不存在的entry。


  • 结构体entry

entry中的指针p指向真正的value所在的地址,dirty和readOnly.m存的值类型就是*entry。这里的nil和expunged有什么作用呢?只要nil不可以吗?对于这些问题后面会一一解读。


(二)函数介绍


下面介绍下sync.Map的四个方法:LoadStoreDeleteRange

  • Load方法


  • 图解



  • 源码分析

Load方法用来加载sync.Map中的值,入参是key,返回值是对应的value以及value存在与否


Map.dirty是如何提升为Map.read的呢?让我们来看下missLocked方法


小结

  • Load方法会优先无锁访问readOnly,未命中后如果Map.dirty中可能存在这个数据就会加锁访问Map.dirty。
  • Load方法如果访问readOnly中不存在但dirty中存在的key,就要加锁访问Map.dirty从而带来额外开销。


  • Store方法


  • 图解



  • 源码解析

Store方法往Map里添加新的key和value或者更新value





小结

  • Store方法优先无锁访问readOnly,未命中会加锁访问dirty。
  • Store方法中的双重检测机制在下面的Load、Delete、Range方法中都会用到,原因是:加锁前Map.dirty可能已被提升为Map.read,所以加锁后还要再次检查key是否存在于Map.read中。
  • dirtyLocked方法在dirty为nil(刚被提升成readOnly或者Map初始化时)会从readOnly中拷贝数据,如果readOnly中数据量很大,可能偶尔会出现性能抖动
  • sync.map不适合用于频繁插入新key-value的场景,因为此操作会频繁加锁访问dirty会导致性能下降。更新操作在key存在于readOnly中且值没有被标记为删除(expunged)的场景下会用无锁操作CAS进行性能优化,否则也会加锁访问dirty。


  • Delete方法


  • 图解



  • 源码解析

Delete方法把key从Map中删掉,返回被删除的值和是否删除成功,它底层调用的是LoadAndDelete



小结

  • 删除readOnly中存在的key,可以不用加锁。
  • 如果删除readOnly中不存在的或者Map中不存在的key,都需要加锁。



  • Range方法


  • 图解


  • 源码解析

Range方法可遍历Map,参数是个函数(入参:key和value,返回值:是否停止遍历Range方法)


小结

  • Range方法Map的全部key都存在于readOnly中时,是无锁遍历的,性能最高。
  • Range方法在readOnly只存在Map中的部分key时,会一次性加锁拷贝dirty的元素到readOnly,减少多次加锁访问dirty中的数据。


(三)sync.map总结

  • 使用场景


sync.Map更适合读多更新多而插入新值少的场景(appendOnly模式,尤其是key存一次,多次读而且不删除的情况),因为在key存在的情况下读写删操作可以不用加锁直接访问readOnly不适合反复插入与读取新值的场景,因为这种场景会频繁操作dirty,需要频繁加锁和更新read【此场景github开源库orcaman/concurrent-map更合适】


  • 设计点:expunged


entry.p取值有3种,nilexpunged指向真实值。那expunged出现在什么时候呢?为什么要有expunged的设计呢?它有什么作用呢?


  • 什么时候expunged会出现呢?


当用Store方法插入新key时,会加锁访问dirty,并把readOnly中的未被标记为删除的所有entry指针复制到dirty,此时之前被Delete方法标记为软删除的entry(entry.p被置为nil)都变为expunged,那这些被标记为expunged的entry将不会出现在dirty中。


  • 反向思维,如果没有expunged,只有nil会出现什么结果呢?


  • 直接删掉entry==nil的元素,而不是置为expunged:在用Store方法插入新key时,readOnly数据拷贝到dirty时直接把为ni的entry删掉。但这要对readOnly加锁,sync.map设计理念是读写分离,所以访问readOnly不能加锁


  • 不删除entry==nil的元素,全部拷贝:在用Store方法插入新key时,readOnly中entry.p为nil的数据全部拷贝到dirty中。那么在dirty提升为readOnly后这些已被删除的脏数据仍会保留,也就是说它们会永远得不到清除,占用的内存会越来越大


  • 不拷贝entry.p==nil的元素:在用Store方法插入新key时,不把readOnly中entry.p为nil的数据拷贝到dirty中,那在用Store更新值时,就会出现readOnly和dirty不同步的状态,即readOnly中存在dirty中不存在的key,那dirty提升为readOnly时会出现数据丢失的问题



(四)sync.map的其他问题


为什么sync.map不实现len方法?个人觉得还是成本和收益的权衡。


  • 实现len方法要统计readOnly和dirty的数据量,势必会引入锁竞争,导致性能下降,还会额外增加代码实现复杂度。


  • 对sync.map的并发操作导致其数据量可能变化很快,len方法的统计结果参考价值不大。



三、orcanman/concurrent-map


orcaman/concurrent-map的适用场景是:反复插入与读取新值,其实现思路是:对go原生map进行分片加锁,降低锁粒度,从而达到最少的锁等待时间(锁冲突)。





它的实现比较简单,截取部分源码如下:

(一)数据结构


(二)函数介绍

  • GET方法


  • SET方法


  • Remove方法


  • Count方法


  • Upsert方法



四、后续


当然在其他业务场景中,我们可能更需要的是本地kv缓存组件库并要求它们支持键过期时间设置、淘汰策略、存储优化、gc优化等。这时候可能我们就需要去了解freecache、gocache、fastcache、bigcache、groupcache等组件库了。


参考资料:

1.Golang fatal error: concurrent map read and map write.

2.sync: add Map.Len method?

3.concurrent map.


作者简介

clancyliang

腾讯后台开发工程师。