介绍一个golang库:fastcache

学习VictoriaMetrics源码的时候发现,VictoriaMetrics的缓存部分,使用了同一产品下的fastcache。下面分享阅读fastcache源码的的结论:

1.官方介绍

fastcache是一个用go语言实现的,很快的,线程安全的,内存缓存的,用于大量对象缓存的组件。

它的特点是:

  • 快!CPU核越多越快,不信你看我下面的benchmark。
  • 线程安全。多个协程可以同时读写单个cache实例。
  • fastcache用于存储大量的cache实体,而且不会被GC扫描。
  • 当设定的cache空间满了以后,fastcache会自动淘汰老数据。
  • API贼简单。
  • 源码也贼简单。
  • cache还可以保存在文件中,需要的时候能加载。
  • 在Google的云服务上也能跑得起来。(说明未使用很特殊的操作系统API)

作者valyala是fasthttp和VictoriaMetrics等作品的主要开发者。valyala大神有极其强悍的工程能力,很多看来已经很简单的成熟组件被他又一次妙手生花,YYDS!

2. 性能

究竟有多快呢?作者做了一个对比:(这里主要看set操作)

  • golang的标准map: 6.21 M次/s
  • sync.Map库:2.65 M次/s
  • BigCache库:6.20 M次/s
  • fastcache库:17.21 M次/s

换个角度看:

  • 比golang的标准map快2.77倍
  • 比sync.Map库快6.49倍
  • 比BigCache快2.78倍

快得我都不知道说啥好了……

3. 限制

当然也不是快就完美了,也是有些限制的。要根据这些限制来确定fastcache是否适合引入你的业务环境中:

  • key和value都只能是[]byte类型,不是的话要自己序列化
  • key长度+value长度+4不能超过64KB,否则就要使用额外的SetBig()方法
  • 没有缓存过期机制。只有在cache满了以后才能淘汰旧数据。
    • 可以自己把过期时间存储在value中,读出来的时候判断一下。如果过期了,手动调用Del()方法来删除。
  • cache的总容量是预先设置好的,超过这个容量就要淘汰最早插入的值。
    • 当然了,cache嘛,仅适合cache场景,不能用于无损的数据存储。
  • 最后:hash冲突的处理上,整个cache分为512个桶。如果两个key的hashcode完全相同的话,新插入的值会替换掉旧的值,导致前一个值丢失……
    • 发生hash冲突时仅仅只是原子累加到监控变量,让你知道曾经发生过……
    • 我认为这一点很不合理,给作者提了个issue

4. 源码解读

4.1 使用mmap分配内存

malloc_mmap.go中使用了unix.Mmap()来分配内存:

  1. 内存映射的方式可以直接向操作系统申请内存,这块区域不归GC管。所以不管你在这块内存缓存了多少数据,都不会因为GC扫描而影响性能。

  2. 每次使用mmap申请内存的时候,申请了1024*64KB=64MB内存。

    • 每64KB称为一个chunk
    • 所有的chunk放在一个队列中
    • 当队列中所有的chunk都用完后,再申请64MB
  3. chunk的管理:

var (
	freeChunks     []*[chunkSize]byte  //相当于一个队列,保存了所有未使用的chunk
	freeChunksLock sync.Mutex  //chunk的锁
)

可以通过 func getChunk() []byte 函数获取一个64KB的块。如果freeChunks中没有chunk了,就再通过mmap申请64MB。

  1. chunk的归还
    func putChunk(chunk []byte) 函数把有效的chunk放回freeChunks队列。

绕过GC能带来性能上的好处,但是这里分配的内存再也不会被释放,直到进程重启。

4.2 Cache类的实现

fastcache.go中是fastcache的主要代码。

4.2.1 cache对象的结构

type Cache struct {
	buckets [bucketsCount]bucket

	bigStats BigStats
}
  • bucketsCount这个常量值为512 。也就是说,cache对象的内部分布了512个桶。
  • bigStats 是用于内部的监控上报的

4.2.2 新建cache对象

// func New(maxBytes int) *Cache
c := New(1024*1024*32)  //cache的最小容量是32MB

New的源码如下:

func New(maxBytes int) *Cache {
	if maxBytes <= 0 {
		panic(fmt.Errorf("maxBytes must be greater than 0; got %d", maxBytes))
	}
	var c Cache
	maxBucketBytes := uint64((maxBytes + bucketsCount - 1) / bucketsCount)
	for i := range c.buckets[:] {
		c.buckets[i].Init(maxBucketBytes)
	}
	return &c
}
  • maxBytes先按照512字节向上对齐
  • 然后划分成512份
    • 假设申请内存512MB,则每份1MB。也就是每个bucket 1MB内存。
  • 分为512个桶,每个桶再单独初始化

4.2.3 Set方法

func (c *Cache) Set(k, v []byte) {
	h := xxhash.Sum64(k)
	idx := h % bucketsCount
	c.buckets[idx].Set(k, v, h)
}

非常简单:对key计算一个hash值,然后对hash值取模,转到具体的bucket对象里面去处理。

xxhash库用汇编实现,是目前最快的hashcode计算的库

4.3 bucket类的实现

4.3.1 bucket的结构

type bucket struct {
	mu sync.RWMutex

	// chunks is a ring buffer with encoded (k, v) pairs.
	// It consists of 64KB chunks.
	chunks [][]byte

	// m maps hash(k) to idx of (k, v) pair in chunks.
	m map[uint64]uint64

	// idx points to chunks for writing the next (k, v) pair.
	idx uint64

	// gen is the generation of chunks.
	gen uint64

	getCalls    uint64  // 以下都是用于统计的变量
	setCalls    uint64
	misses      uint64
	collisions  uint64
	corruptions uint64
}
  • mu sync.RWMutex : 每个bucket有一个读写锁来处理并发。

    • 和sync.Map比起来,原理上也没什么神秘的。把数据分散到512个桶,相当于竞争变为原来的1/512。
  • chunks [][]byte: 这个是存储数据的chunk的数组

    • chunk是上面提到的通过mmap分配的64KB的一个块
    • key+value的数据会被顺序的放在chunk中,并记录位于数组中的下标
    • 一个chunk的空间用完后,会再通过getChunk()再申请64KB的块。直到块达到用户规定的上限。
      • 假设每个bucket 1MB, 则共有1MB/64KB=16个chunk
      • 第15个chunk满了以后,又回到第0个chunk存储,同时gen字段增加,说明是新的一代
  • m map[uint64]uint64: 这里存储每个hashcode对应的chunk中的偏移量。

  • idx uint64: 这里记录下次插入chunk的位置,插入完成后跳转到数据的末位。

  • gen uint64: 当所有的chunks都写满以后,gen的值加1,从第0块开始淘汰旧数据。

这里有个明显的缺点:假设hashcode都分布在较少的几个bucket中,那么就导致某几个bucket的数据频繁淘汰,而其他的bucket还剩挺多空间。不过,这只是假设,并未有数据证明会有这种现象。

4.3.2 Set过程

源码太多,此处直接贴结论:

  • 每set 16384(2的14次方)次,执行一次clean操作
    • clean操作遍历整个map,移除chunk中因为回绕淘汰的数据
  • key+value序列化的方式很简单,顺序存储以下内容:
    • 2字节key长度
    • 2字节value长度
    • key的内容
    • value的内容
  • 写入chunk的时候加入了写锁
  • 通过bucket的idx字段找到插入位置,然后按照上述序列化的方式拷贝数据
  • 插入完成后得到了偏移位置,把key的hashcode作为键,把chunks中的偏移量为值,写入字段m的map中
    • value这里还有个细节:value是64位的uint64, value的低40位存储偏移量,value的高24位存储generation的信息。

4.3.3 Get过程

搞清楚了Set,Get就更简单了:

  • 首先在Cache类中,根据key的hashcode,确定选择哪个bucket
  • 查询前加读锁
  • 在m字段的map中,根据hashcode找到下标
  • 根据下标确定key的位置
  • 比较key的内容是否相等
  • 最后返回value

4.3.4 Del过程

del仅删除map中的key,而chunks中对应的位置只能等到下次回绕才能清理。

删除的动作是滞后的,因此fastcache不适合删除很多的业务场景。

5.总结

fastcache为什么快,因为用了这些手段:

  1. 使用mmap来成块的分配内存。

    • 每次直接向操作系统要64MB,这些内存都绕开了GC。
    • 每次以64KB为单位请求一个块
    • 在64KB的块内顺序存储,相当于更简单的自己实现的分配算法
  2. 整个cache分成512个bucket

    • 相当于有了512个map+512个读写锁,通过这样减少了竞争
    • map类型的key和value都是整形,容量小,且对GC友好
    • 淘汰用轮换的方法+固定次数的set后再清理,解决了(或者说绕开了)碎片的问题

希望对你有用,have fun 😃

来自我的公众号:原文链接

原文链接:,转发请注明来源!