你应该学会的 bigcache 优化技巧

2019-12-19

本文作者：鸟窝 smallnest

原文链接：https://colobu.com/2019/11/18/how-is-the-bigcache-is-fast/

最近看到 yoko 翻译的一篇文章: [译] Go 开源项目 BigCache 如何加速并发访问以及避免高额的 GC 开销[1]，翻译自 How BigCache avoids expensive GC cycles and speeds up concurrent access in Go[2], 应该是 Douglas Makey Mendez Molero 在阅读了 bigcache 的作者写的 bigcache 设计文章Writing a very fast cache service with millions of entries in Go[3]做的一些调研和总结。

我在刚读取这篇文档的时候，顺着连接把相关的文章都找出来细细读了一遍，结合 bigcache 的代码，仔细学习了相关的优化设计，感觉设计非常的精妙，所以特意根据自己的理解又总结了一篇。

bigcache 的精妙的设计也吸引了 fasthttp 的作者 Aliaksandr Valialkin，他在 bigcache 的基础上，结合自己的公司的使用场景，进一步的做了相应的优化，也开源了这个项目 fastcache[4], 本文在最后也做了介绍。

设计 BigCache 的初衷

bigcache 的作者也不是想当然的开发一个库，而且项目遇到了需求。需求如下：

支持 http 协议
支持 10K RPS (5k 写，5k 读)
cache 对象至少保持 10 分钟
相应时间平均 5ms, p99.9 10 毫秒， p99.999 400 毫秒
其它 HTTP 的一些需求

为了满足这些需求，要求开发的 cache 库要保证：

即使有百万的缓存对象也要非常快
支持大并发访问
一定时间后支持剔除

作者考察了一番缓存框架比如 memcached、redis、couchbase 等，发觉都不太满足需求，因为这些都是独立的程序，访问它们需要网络的开销，延时无法保障，作者需要一个进程内的基于内存的 cache 库。虽然 Go 生态圈有众多的 cache 库如 LRU groups cache[5], go-cache[6], ttlcache[7], freecache[8]，但是只有 freecache 满足需求，不过作者最后还是决定自己取开发一个 cache 库。

以上是 bigcache 诞生的背景，接下来我们欣赏一下 bigcache 和其它库优美的设计。

处理大并发访问

cache 就像一个大的 hashtable, 可不可以使用一个map[string][]byte + sync.RWMutex实现满足需求的 cache 呢？

sync.RWMutex虽然对读写进行了优化，但是对于并发的读，最终还是把写变成了串行，一旦写的并发量大的时候，即使写不同的 key, 对应的 goroutine 也会 block 住，只允许一个写执行，这是一个瓶颈，并且不可控。

解决并发的问题有一个方法叫做 shard (分片)，每个分片一把锁。很多大并发场景下为了减小并发的压力都会采用这种方法，大的场景比如数据库的分片，小的场景就如刚才的场景。JAVA 8 之前的 ConcurrentMap 就是采用分片(segment)的方式减少竞争, Go 也有一个类似思想设计的 map 库:concurrent-map[9]。

对于每一个缓存对象，根据它的 key 计算它的哈希值: hash(key) % N, N是分片数量。理想情况下 N 个 goroutine 每次请求正好平均落在各自的分片上，这样就不会有竞争了，即使有多个 goroutine 落在同一个分片上，如果 hash 比较平均的话，单个 shard 的压力也会比较小。

竞争小了有什么好处？延迟可以大大提高，因为等待获取锁的时间变小了。

当然这里有一些要考虑的地方：

1、N 的选择

既然分片可以很好的降低锁的竞争，那么 N 是不是越大越好呢？当然不是，如果 N 非常大，比如每个缓存对象一个锁，那么会带来很多额外的不必要的开销。可以选择一个不太大的值，在性能和花销上寻找一个平衡。

另外, N 是 2 的幂，比如 16、32、64。这样设计的好处就是计算余数可以使用位运算快速计算。

func (c *BigCache) getShard(hashedKey uint64) (shard *cacheShard) {
	return c.shards[hashedKey&c.shardMask]
}

因为对于 2 的幂 N，对于任意的x, 下面的公式成立:

x mod N = (x & (N − 1))

所以只需要使用一次按位 AND (&)就可以求得它的余数。

2、选择 hash 算法

以前已经有非常多的哈希算法，最近几年也出现了一些新的哈希算法，也被人使用 Go 语言来实现。

很显然，一个优秀的哈希算法要保证:

哈希值应该比较随机 (质量)
哈希速度比较快 (速度)
尽量不产生额外的内存分配，避免对垃圾回收产生压力 (耗费资源少)

项目hash-bench[10]对常用的几种 Hash 算法进行了比较。

bigcache 提供了一个默认的 Hash 的实现，采用 fnv64a 算法。这个算法的好处是采用位运算的方式在栈上进行运算，避免在堆上分配。

type fnv64a struct{}

const (

	// offset64 FNVa offset basis. See https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function#FNV-1a_hash
	offset64 = 14695981039346656037

	// prime64 FNVa prime value. See https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function#FNV-1a_hash
	prime64 = 1099511628211
)

// Sum64 gets the string and returns its uint64 hash value.
func (f fnv64a) Sum64(key string) uint64 {
	var hash uint64 = offset64
	for i := 0; i < len(key); i++ {
		hash ^= uint64(key[i])
		hash *= prime64
	}

	return hash
}

忽略内存开销

对于 Go 语言中的 map, 垃圾回收器在 mark 和 scan 阶段检查 map 中的每一个元素, 如果缓存中包含数百万的缓存对象，垃圾回收器对这些对象的无意义的检查导致不必要的时间开销。

bigcache 的作者做了测试。他们测试了简单的 HTTP/JSON 序列化(不会访问 cache)。在 cache 为空的时候 1 万的 QPS 的耗时大约 10 毫秒。当 cache 填满的时候， 99% 的请求都会超过 1 秒。监控显示堆中包含 4 千万的对象， GC 过程中的 mark 和 scan 也需要 4 秒。

我们可以很容易测试这种状况，比如下面的代码：

package main

import "time"

type Item struct {
	A string
	B string
	C string
	D string
	E string
	F string
	G G
}

type G struct {
	H int
	I int
	K int
	L int
	M int
	N int
}

func main() {
	m := make(map[int]*Item, 10*1024*1024)

	for i := 0; i < 1024*1024; i++ {
		m[i] = &Item{}
	}

	for i := 0; ; i++ {
		delete(m, i)
		m[1024*1024+i] = &Item{}
		time.Sleep(10 * time.Millisecond)
	}
}

只有一个 map 对象，里面包含一百万的元素，每 10 毫秒删一个放一个。

并发量相当小，并且单个的 goroutine 也没有竞争，但是由于元素的数量巨大，垃圾回收在mark/scan阶段需要花费上百毫秒进行标记和遍历。

那么如何解决这个问题呢？

我们知道垃圾回收器检查的是堆上的资源，如果不把对象放在堆上，不就解决这个问题了吗？还真有这样的项目offheap[11]，它提供了定制的Malloc() 和 Free()，但是你的缓存需要基于这些方法定制。当然一些基于垃圾回收的编程语言为了减少垃圾回收的时间，都会提供相应的库，比如Java: ChronicleMap, Part 1: Go Off-Heap[12]。堆外内存很容易产生内存泄漏。

第二种方式是使用 freecache[13]。freecache 通过减少指针的数量以零 GC 开销实现 map。它将键和值保存在ringbuffer中，并使用索引查找对象。

第三种优化方法是和 Go 1.5 中一个修复有关(#9477[14]), 这个 issue 还描述了包含大量对象的 map 的垃圾回收时的耗时问题，Go 的开发者优化了垃圾回收时对于 map 的处理，如果 map 对象中的 key 和 value 不包含指针，那么垃圾回收器就会对它们进行优化：

runtime: do not scan maps when k/v do not contain pointers

Currently we scan maps even if k/v does not contain pointers. This is required because overflow buckets are hanging off the main table. This change introduces a separate array that contains pointers to all overflow buckets and keeps them alive. Buckets themselves are marked as containing no pointers and are not scanned by GC (if k/v does not contain pointers).

This brings maps in line with slices and chans -- GC does not scan their contents if elements do not contain pointers.

Currently scanning of a map[int]int with 2e8 entries (~8GB heap) takes ~8 seconds. With this change scanning takes negligible time.

https://go-review.googlesource.com/c/go/+/3288

所以如果我们的对象不包含指针，虽然也是分配在堆上，但是垃圾回收可以无视它们。

如果我们把 map 定义成 map[int]int，就会发现 gc 的耗时就会降下来了。

遗憾的是，我们没办法要求用户的缓存对象只能包含int、bool这样的基本数据类型。

解决办法就是使用哈希值作为map[int]int的 key。把缓存对象序列化后放到一个预先分配的大的字节数组中，然后将它在数组中的 offset 作为map[int]int的 value。

type cacheShard struct {
	hashmap     map[uint64]uint32
	entries     queue.BytesQueue
	lock        sync.RWMutex
	entryBuffer []byte
	onRemove    onRemoveCallback
	isVerbose    bool
	statsEnabled bool
	logger       Logger
	clock        clock
	lifeWindow   uint64
	hashmapStats map[uint64]uint32
	stats        Stats
}
func (s *cacheShard) set(key string, hashedKey uint64, entry []byte) error {
	currentTimestamp := uint64(s.clock.epoch())
	s.lock.Lock()
    // 查找是否已经存在了对应的缓存对象，如果存在，将它的值置为空
	if previousIndex := s.hashmap[hashedKey]; previousIndex != 0 {
		if previousEntry, err := s.entries.Get(int(previousIndex)); err == nil {
			resetKeyFromEntry(previousEntry)
		}
	}
    // 触发是否要移除最老的缓存对象
	if oldestEntry, err := s.entries.Peek(); err == nil {
		s.onEvict(oldestEntry, currentTimestamp, s.removeOldestEntry)
	}
    // 将对象放入到一个字节数组中，如果已有的字节数组(slice)可以放得下此对象，则重用，否则新建一个字节数组
	w := wrapEntry(currentTimestamp, hashedKey, key, entry, &s.entryBuffer)
	for {
        // 尝试放入到字节队列中，成功则加入到map中
		if index, err := s.entries.Push(w); err == nil {
			s.hashmap[hashedKey] = uint32(index)
			s.lock.Unlock()
			return nil
        }
        // 如果空间不足，移除最老的元素
		if s.removeOldestEntry(NoSpace) != nil {
			s.lock.Unlock()
			return fmt.Errorf("entry is bigger than max shard size")
		}
	}
}
func wrapEntry(timestamp uint64, hash uint64, key string, entry []byte, buffer *[]byte) []byte {
	keyLength := len(key)
	blobLength := len(entry) + headersSizeInBytes + keyLength
	if blobLength > len(*buffer) {
		*buffer = make([]byte, blobLength)
	}
	blob := *buffer
	binary.LittleEndian.PutUint64(blob, timestamp)
	binary.LittleEndian.PutUint64(blob[timestampSizeInBytes:], hash)
	binary.LittleEndian.PutUint16(blob[timestampSizeInBytes+hashSizeInBytes:], uint16(keyLength))
	copy(blob[headersSizeInBytes:], key)
	copy(blob[headersSizeInBytes+keyLength:], entry)
	return blob[:blobLength]
}

queue.BytesQueue 是一个字节数组，可以做到按需分配。当加入一个[]byte时，它会把数据 copy 到尾部。

值得注意的是删除缓存元素的时候 bigcache 只是把它的索引从map[uint64]uint32中删除了，并把它在queue.BytesQueue队列中的长度置为 0。那么删除操作会不会在queue.BytesQueue中造成很多的“虫洞”？从它的实现上来看，会, 而且这些"虫洞"不会被整理，也不会被移除。因为它的底层是使用一个字节数组实现的，"虫洞"的移除是一个耗时的操作，会导致锁的持有时间过长。那么寻找合适的"虫洞"重用呢？虽然遍历的方法寻找"虫洞"也是一个比较耗时的操作，我觉得这里有优化的空间。

bigcache 只能等待清理最老的元素的时候把这些"虫洞"删除掉。

剔除

对于 bigcache 来说，剔除还有意义吗？或许有。如果我们不想使用某个 key 的缓存对象，我们可以把它删除。

首先，在增加一个元素之前，会检查最老的元素要不要删除。

if oldestEntry, err := s.entries.Peek(); err == nil {
	s.onEvict(oldestEntry, currentTimestamp, s.removeOldestEntry)
}

其次，在添加一个元素失败后，会清理空间删除最老的元素。

同时，还会专门有一个定时的清理 goroutine, 负责移除过期数据。

另外需要注意的是缓存对象没有读取的时候刷新过期时间的功能，所以放入的缓存对象最终免不了过期的命运。

另外所有的缓存对象的 lifewindow 都是一样的，比如 30 分钟、两小时。

所以，如果你真的使用 bigcache, 还是得需要注意它的这些设计，看看这些设计是否和你的场景相吻合。

fastcache

bigcache 在特定时候还是有问题，就是当 queue.BytesQueue 的容量不够的时候，它会进行扩展，扩展是一个很重的操作，它会复制原来的数据到新的字节数组上。

fasthttp 的作者采用类似 bigcache 的思想实现了fastcache[15]，他使用 chunks [][]byte替换 queue.BytesQueue，chunk 是一个 ring buffer, 每个 chunk 64KB。

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
}

虽然chunks [][]byte也包含很多的 chunk, 但是由于 chunk 的 size 比较大，所以可以大大缩小垃圾回收需要 mark/scan 的对象的数量。带来的好处就是扩容的时候只需要增加更多的 chunk 即可。

删除还是一样，只是从 map 中删除，不会从chunks中删除。

fastcache 没有过期的概念，所以缓存对象不会被过期剔除。

参考文档

http://allegro.tech/2016/03/writing-fast-cache-service-in-go.html
https://github.com/allegro/bigcache
https://dev.to/douglasmakey/how-bigcache-avoids-expensive-gc-cycles-and-speeds-up-concurrent-access-in-go-12bb
https://pengrl.com/p/35302/
https://github.com/VictoriaMetrics/fastcache
https://www.openmymind.net/Shard-Your-Hash-table-to-reduce-write-locks/
https://medium.com/@itsromiljain/curious-case-of-concurrenthashmap-90249632d335
https://segmentfault.com/a/1190000012926722
https://github.com/coocood/freecache

文中链接

[1]

[译] Go开源项目BigCache如何加速并发访问以及避免高额的GC开销: https://pengrl.com/p/35302/

[2]

How BigCache avoids expensive GC cycles and speeds up concurrent access in Go: https://dev.to/douglasmakey/how-bigcache-avoids-expensive-gc-cycles-and-speeds-up-concurrent-access-in-go-12bb

[3]

Writing a very fast cache service with millions of entries in Go: https://allegro.tech/2016/03/writing-fast-cache-service-in-go.html

[4]

fastcache: https://github.com/VictoriaMetrics/fastcache

[5]

LRU groups cache: https://github.com/golang/groupcache/tree/master/lru

[6]

go-cache: https://github.com/patrickmn/go-cache

[7]

ttlcache: https://github.com/diegobernardes/ttlcache

[8]

freecache: https://github.com/coocood/freecache

[9]

concurrent-map: https://github.com/orcaman/concurrent-map

[10]

hash-bench: https://github.com/smallnest/hash-bench

[11]

offheap: https://godoc.org/github.com/glycerine/offheap

[12]

Java: ChronicleMap, Part 1: Go Off-Heap: https://dzone.com/articles/java-chroniclemap-part-1-go-off-heap

[13]

freecache: https://github.com/coocood/freecache

[14]

#9477: https://github.com/golang/go/issues/9477

[15]

fastcache: https://github.com/VictoriaMetrics/fastcache