[译] Go开源项目BigCache如何加速并发访问以及避免高额的GC开销
发表于 2019-11-02 | 分类于
Go| 字数统计: 2.5k
几天前,我读了一篇关于BigCache
的文章,我对它是如何做到以下两点十分感兴趣:
于是我去阅读了它的代码。我觉得它的做法很赞,所以我写了这篇文章来与你分享。
BigCache 是一个快速,支持并发访问,自淘汰的内存型缓存,可以在存储大量元素时依然保持高性能。BigCache将元素保存在堆上却避免了GC的开销。 —— 摘自《BigCache README 中的简介》
1 2 3 4 5 6 7 8 9 10
| // BigCache README 中的简单使用示例
import "github.com/allegro/bigcache"
cache, _ := bigcache.NewBigCache(bigcache.DefaultConfig(10 * time.Minute))
cache.Set("my-unique-key", []byte("value"))
entry, _ := cache.Get("my-unique-key") fmt.Println(string(entry))
|
BigCache github地址
一个缓存,支持并发访问是必须的,无论是程序使用了协程,还是 HTTP 服务器为每个请求分配的协程,都可能并发访问缓存。最常见的解决方案是使用读写锁(sync.RWMutex
)来保证在一个时间点只允许一个协程修改缓存内容。但是如果这样做,锁可能会阻塞后续的操作,导致缓存性能下降。
为了解决这个问题,BigCache
使用了shards
(译者yoko注:单词意思为碎片,可以理解为桶或分片或分区),shard
是什么?一个shard
是一个结构体,它包含了一个带锁的cache
实例。
BigCache
使用了一个元素个数为N的shard
数组,然后将数据打散到不同的shard
中,所以当你从缓存中读写数据时,缓存会选取其中的一个shard
使用(选取策略下文会说)。使用这种方式,锁粒度被大幅度减小,因为锁范围从全局缓存缩小到了单个shard
中。(译者yoko注:对shard
数组的访问是不需要加锁的,因为该数组在初始化时创建,后续大小就不会变了,即后续对数组的访问只有读,当然,对数组中的元素shard
是有读有写的,但是这已经和数组没关系了)
高额GC开销
Go中实现缓存最简单最常见的方式是使用一个map来存储元素,但是如果使用map,GC(垃圾回收器)会在标记阶段访问map中的每一个元素,当map非常大时这会对程序性能带来非常大的开销。
go 1.5版本之后,如果你使用的map的key和value中都不包含指针,那么GC会忽略这个map。
为避免这个问题,BigCache
使用了一个key和value都不包含指针的map,这样,GC就会忽略掉这个map。具体做法为:
map的key为存入缓存中的key经过hash函数后得到的值。
map的value比较值得一说,BigCache
并不是直接把存入缓存的value作为map的value,而是将存入缓存的value序列化成二进制的[]byte
,然后将序列化后的[]byte
追加到一个全局的[]byte
中(一个shard包含一个全局[]byte
)。map中存储的是该序列化后数据在全局[]byte
中的下标。
使用全局的[]byte
是非常聪明的做法,因为这样做,只会给GC增加了一个额外对象,由于字节切片除了自身对象并不包含其他指针数据,所以GC对于整个对象的标记时间是O(1)的。
译者yoko注
英文原文写到这,基本上关于优化方面的思想已经说明白了。大致是以下两点:
第一,将元素非常多的容器通过hash打散到各个桶(子容器)中。这是一种比较常见通用的减小锁粒度,提高性能的手段。
第二,就是把map的key和value都弄成了无指针类型,具体做法上面已经说了。这种做法说白了是针对Go GC的特性所做的针对性优化。
另外,值得一提的是,关于第二点,由于桶中的全局的[]byte
使用的是数组类型,那么显然从中间删除元素的开销是很大的。我去看了看BigCache
的实现,它也确实没有提供删除指定key的接口。这种缓存,一般来说,删除元素靠的是全局过期时间(注意,是先进先出的过期,并不能为每个key单独指定不同的过期时间)或缓存总大小达到一定阈值后删除,也即把数组当队列用。所以,这种实现的前提是,缓存是自淘汰类型,而非可手动删除指定元素类型的。
后期补充:感谢读者 aixiaoxiang 的提醒,他说 BigCache 提供了删除指定 key 的接口。以下是针对该问题我的回复:
译者yoko的回复:
我刚才去看了下 BigCache 的源码,它确实提供了删除 key 的接口。
但是它删除 key 时是只删除 map 中的 key(即key为用户指定的key,value为大 buffer 下标位置的那个map),并没有删除底层那个大 buffer 中存储的该 key 对应的 value。
原因估计和我文中所说的那样,删除大 buffer 中间位置的内容代价太大。
从面相使用者的角度,对外表现来说,确实是提供了删除的接口。
从底层存储来说,还是占用了内存。
我文中写不提供删除的接口,是我从底层设计倒退得出的接口设计,是我的思维太局限了。
英文原文的后续部分,是英文作者在BigCache
的基础上自己写了一个简单版本的cache,然后通过代码来说明上面原理。如果你看到这觉得ok了,后面的内容就不用看了。
以下是我写的一个cache的简单实现,我去掉了关于过期淘汰,容量等功能,只为了更好的演示我上面所说的内容。
首先,哈希函数是从BigCache
中抄的,这个哈希实现是零堆内存申请的。
hasher.go
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| package main
// newDefaultHasher returns a new 64-bit FNV-1a Hasher which makes no memory allocations. // Its Sum64 method will lay the value out in big-endian byte order. // See https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function func newDefaultHasher() fnv64a { return 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 }
|
然后,cache结构体包含了获取shard的逻辑,以及get和set方法。
在前文并发访问
小节中,提到了为数据选取特定shard的函数,该函数的实现是首先通过前面的哈希函数将key转换成一个hash值,然后用hash值与shard的数量计算出shard数组的下标。值得一提的是,这里不是用取余运算得到结果,而是通过按位与计算的。
译者yoko注
按位与比取余效率更高,需要的指令更少。但是用这种方式有个前提,数组大小必须是2的幂方,不然会导致有的下标永远不会被计算得到。
下面举例说明为什么数组大小不是2的幂方有问题。
比如假设数组大小为15(二进制为 1111),减1后为14(二进制为 1110),那么任何数字和 1110 按位与,都无法得到0~1110
中第1位为1的数字,比如0001,0011等等。
1 2 3 4 5
| hashedkey&mask
0111 AND 1101 (mask) = 0101
|
cache.go
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| package main
var minShards = 1024
type cache struct { shards []*cacheShard hash fnv64a }
func newCache() *cache { cache := &cache{ hash: newDefaultHasher(), shards: make([]*cacheShard, minShards), } for i := 0; i < minShards; i++ { cache.shards[i] = initNewShard() }
return cache }
func (c *cache) getShard(hashedKey uint64) (shard *cacheShard) { return c.shards[hashedKey&uint64(minShards-1)] }
func (c *cache) set(key string, value []byte) { hashedKey := c.hash.Sum64(key) shard := c.getShard(hashedKey) shard.set(hashedKey, value) }
func (c *cache) get(key string) ([]byte, error) { hashedKey := c.hash.Sum64(key) shard := c.getShard(hashedKey) return shard.get(key, hashedKey) }
|
最后,也就是最赞的地方,在每个shard中有一个字符数组[]byte
和一个map[uint64]uint32
。在map中,存储每个键值对的值在全局字符数组中的下标,在字符数组中存储键值对的值。
使用tail
变量来保存字符数组的尾部下标。
shard.go
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88
| package main
import ( "encoding/binary" "errors" "sync" )
const ( headerEntrySize = 4 defaultValue = 1024 // For this example we use 1024 like default value. )
type cacheShard struct { items map[uint64]uint32 lock sync.RWMutex array []byte tail int headerBuffer []byte }
func initNewShard() *cacheShard { return &cacheShard{ items: make(map[uint64]uint32, defaultValue), array: make([]byte, defaultValue), tail: 1, headerBuffer: make([]byte, headerEntrySize), } }
func (s *cacheShard) set(hashedKey uint64, entry []byte) { w := wrapEntry(entry) s.lock.Lock() index := s.push(w) s.items[hashedKey] = uint32(index) s.lock.Unlock() }
func (s *cacheShard) push(data []byte) int { dataLen := len(data) index := s.tail s.save(data, dataLen) return index }
func (s *cacheShard) save(data []byte, len int) { // Put in the first 4 bytes the size of the value binary.LittleEndian.PutUint32(s.headerBuffer, uint32(len)) s.copy(s.headerBuffer, headerEntrySize) s.copy(data, len) }
func (s *cacheShard) copy(data []byte, len int) { // Using the tail to keep the order to write in the array s.tail += copy(s.array[s.tail:], data[:len]) }
func (s *cacheShard) get(key string, hashedKey uint64) ([]byte, error) { s.lock.RLock() itemIndex := int(s.items[hashedKey]) if itemIndex == 0 { s.lock.RUnlock() return nil, errors.New("key not found") }
// Read the first 4 bytes after the index, remember these 4 bytes have the size of the value, so // you can use this to get the size and get the value in the array using index+blockSize to know until what point // you need to read blockSize := int(binary.LittleEndian.Uint32(s.array[itemIndex : itemIndex+headerEntrySize])) entry := s.array[itemIndex+headerEntrySize : itemIndex+headerEntrySize+blockSize] s.lock.RUnlock() return readEntry(entry), nil }
func readEntry(data []byte) []byte { dst := make([]byte, len(data)) copy(dst, data)
return dst }
func wrapEntry(entry []byte) []byte { // You can put more information like a timestamp if you want. blobLength := len(entry) blob := make([]byte, blobLength) copy(blob, entry) return blob }
|
main.go
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| package main
import "fmt"
func main() { cache := newCache() cache.set("key", []byte("the value"))
value, err := cache.get("key") if err != nil { fmt.Println(err) }
fmt.Println(string(value)) // OUTPUT: // the value }
|
英文原文地址: How BigCache avoids expensive GC cycles and speeds up concurrent access in Go
本文完,作者yoko,尊重劳动人民成果,转载请注明原文出处: https://pengrl.com/p/35302/