剖析Golang Bigcache的极致性能优化

func (c *BigCache) Set(key string, entry []byte) error {
hashedKey := c.hash.Sum64(key)
shard := c.getShard(hashedKey)
return shard.set(key, hashedKey, entry)
}

func (c *BigCache) getShard(hashedKey uint64) (shard *cacheShard) {
    // shardMask:  uint64(config.Shards - 1)
return c.shards[hashedKey&c.shardMask]
}

type cacheShard struct {
...
hashmap     map[uint64]uint32
entries     queue.BytesQueue
...
}

cache.Set("my-unique-key", []byte("value"...剩余内容已隐藏
查看完整文章以阅读更多
查看完整文章
🍊
柑橘 RSS
订阅源浏览器信息
编程沉思录
编程沉思录
马上订阅 编程沉思录 RSS 更新: https://www.cyhone.com/atom.xml
剖析Golang Bigcache的极致性能优化
2023年11月25日 19:25
Bigcache是用Golang实现的本地内存缓存的开源库，主打的就是可缓存数据量大，查询速度快。 在其官方的介绍文章《Writing a very fast cache service with millions of entries in Go》一文中，明确提出了bigcache的设计目标：
多： 缓存的元素数量非常大，可以达到百万级或千万级。
快： 对延迟有非常高的要求，平均延迟要求在5毫秒以内。redis、memcached之类的就不考虑在内了，毕竟用Redis还要多走一遍网络IO。
稳： 99.9分位延迟应在10毫秒左右，99.999分位延迟应在400毫秒左右。
目前有许多开源的cache库，大部分都是基于map实现的，例如go-cache,ttl-cache等。bigcache明确指出，当数据量巨大时，直接基于map实现的cache库将出现严重的性能问题，这也是他们设计了一个全新的cache库的原因。
本文将通过分析bigcache v3.1.0的源码，揭秘bigcache如何解决现有map库的性能缺陷，以极致的性能优化，实现超高性能的缓存库。
 bigcache的设计思想
 如何避免GC对map的影响
当map里面数据量非常大时，会出现性能瓶颈。这是因为在Golang进行GC时，会扫描map中的每个元素。当map足够大时，GC时间过长，会对程序的性能造成巨大影响。
根据bigcache介绍文章的测试，在缓存数据达到数百万条时，接口的99th百分位延迟超过了一秒。监测指标显示堆中超过4,000万个对象，GC的标记和扫描阶段耗时超过了4秒。这样的延迟对于bigcache来说是完全无法接受的。
这个问题在Go 1.5版本中有一项专门的优化(issue-9477)：如果map的key和value中使用没有指针，那么GC时将无需遍历map。例如map[int]int、map[int]bool。这是当时的pull request: go-review.googlesource.com/c/go/+/3288。里面提到：
Currently scanning of a map[int]int with 2e8 entries (~8GB heap)
takes ~8 seconds. With this change scanning takes negligible time.
对2e8个元素的map[int]int上进行了测试，GC扫描时间从8秒减少到0。
为什么当map的key和value不包含指针时，可以省去对元素的遍历扫描呢？这是因为map中的int、bool这种不可能会和外部变量有引用关系：
int、bool这种在map中存储的就是值本身。
map的key和value不可被寻址。也就是说，以map[int]int为例，外部没有办法取到这个key和value的指针，那也就无从引用了。
这个优化听起来非常强大好用，但是在Golang中指针无处不见，结构体指针、切片甚至字符串的底层实现都包含指针。一旦在map中使用它们（例如map[int][]byte、map[string]int），同样会触发垃圾回收器的遍历扫描。
 bigcache的整体设计
bigcache整体设计的出发点都是基于上文提到的Golang对Map GC优化，整个设计思路包含几个方面：
数据分片存储，以降低锁冲突并提升并发量。
避免在map中存储指针，从而避免在GC时对map进行遍历扫描。
采用FIFO式的Ring Buffer设计，简化整体内存设计逻辑。
 数据分shard
这是一个非常常见的数据存储优化手段。表面上bigcache中所有的数据是存在一个大cache里面，但实际上底层数据分成了N个不互重合的部分，每一个部分称为一个shard。
在Set或者Get数据时，先对key计算hash值，根据hash值取余得到目标shard，之后所有的读写操作都是在各自的shard上进行。
以Set方法为例：
1
2
3
4
5
func (c *BigCache) Set(key string, entry []byte) error {
hashedKey := c.hash.Sum64(key)
shard := c.getShard(hashedKey)
return shard.set(key, hashedKey, entry)
}
这么做的优势是可以减少锁冲突，提升并发量：当一个shard被加上Lock的时候，其他shard的读写不受影响。
在bigcache的设计中，对于shard有如下要求：
一旦建好，shard将不改变。这带来的两点好处：不用再考虑shard变化时的数据迁移问题。
因为shard数组是固定不变的，因此从shard数组中根据hash值取目标shard的时候，就无需加锁了。
shard个数必须是2的平方数。这么做的好处是，对2的平方数取余可以改成位运算，会比传统的%快很多（根据不权威的benchmark，计算速度大概会有2倍左右的差距）。
1
2
3
4
func (c *BigCache) getShard(hashedKey uint64) (shard *cacheShard) {
    // shardMask:  uint64(config.Shards - 1)
return c.shards[hashedKey&c.shardMask]
}
bigcache的shard数默认值是1024。
 map不存原始数据，避免GC遍历扫描
前文提到，map的key和value一旦涉及指针相关的类型，GC时就会触发遍历扫描。
因此在bigcache的设计中，shard中的map直接定义为了map[uint64]uint32 ，避免了存储任何指针。shard的结构体定义如下:
1
2
3
4
5
6
type cacheShard struct {
...
hashmap     map[uint64]uint32
entries     queue.BytesQueue
...
}
其中：hashmap的key是cache key的hash值，而value仅仅是个uint32。这显然不是我们Set的时候value的原始byte数组。
那value的原始值存在了哪里？答案是cacheShard中的另外一个属性entries queue.BytesQueue。
queue.BytesQueue是一个ring buffer的内存结构，本质上就是个超大的[]byte数组，里面存放了所有的原始数据。每个原始数据就存放在这个大[]byte数组中的其中一段。
hashmap中uint32的value值存放的就是value的原始值在BytesQueue中的数组下标。(其实并不只是原始的value值，里面也包含了key、插入时间戳等信息）
之所以用一个大的[]byte数组和ring buffer结构，除了方便管理和复用内存之外，一个更重要的原因是：对于[]byte数组, GC时只用看做一个变量扫描，无需再遍历全部数组。这样又避免了海量数据对GC造成的负担。
 FIFO式的内存结构设计
bigcache在内存结构设计上完全遵循FIFO原则：
新增数据以及对旧数据的修改，都是直接Append新数据到BytesQueue中。基本不直接对内存进行修改和删除等。
每个数据项不可以定制单独的缓存时长，必须全部保持一致。这对数据淘汰非常友好，下文会详细讲述。
这样一整套设计约定下来，bigcache的逻辑变成非常简洁明了，但这样同时造成了bigcache的局限性。
 Set过程
1
cache.Set("my-unique-key", []byte("value"...剩余内容已隐藏
查看完整文章以阅读更多
查看完整文章
🍊
柑橘 RSS
订阅源浏览器信息
编程沉思录
编程沉思录
马上订阅 编程沉思录 RSS 更新: https://www.cyhone.com/atom.xml
剖析Golang Bigcache的极致性能优化
2023年11月25日 19:25
Bigcache是用Golang实现的本地内存缓存的开源库，主打的就是可缓存数据量大，查询速度快。 在其官方的介绍文章《Writing a very fast cache service with millions of entries in Go》一文中，明确提出了bigcache的设计目标：
多： 缓存的元素数量非常大，可以达到百万级或千万级。
快： 对延迟有非常高的要求，平均延迟要求在5毫秒以内。redis、memcached之类的就不考虑在内了，毕竟用Redis还要多走一遍网络IO。
稳： 99.9分位延迟应在10毫秒左右，99.999分位延迟应在400毫秒左右。
目前有许多开源的cache库，大部分都是基于map实现的，例如go-cache,ttl-cache等。bigcache明确指出，当数据量巨大时，直接基于map实现的cache库将出现严重的性能问题，这也是他们设计了一个全新的cache库的原因。
本文将通过分析bigcache v3.1.0的源码，揭秘bigcache如何解决现有map库的性能缺陷，以极致的性能优化，实现超高性能的缓存库。
 bigcache的设计思想
 如何避免GC对map的影响
当map里面数据量非常大时，会出现性能瓶颈。这是因为在Golang进行GC时，会扫描map中的每个元素。当map足够大时，GC时间过长，会对程序的性能造成巨大影响。
根据bigcache介绍文章的测试，在缓存数据达到数百万条时，接口的99th百分位延迟超过了一秒。监测指标显示堆中超过4,000万个对象，GC的标记和扫描阶段耗时超过了4秒。这样的延迟对于bigcache来说是完全无法接受的。
这个问题在Go 1.5版本中有一项专门的优化(issue-9477)：如果map的key和value中使用没有指针，那么GC时将无需遍历map。例如map[int]int、map[int]bool。这是当时的pull request: go-review.googlesource.com/c/go/+/3288。里面提到：
Currently scanning of a map[int]int with 2e8 entries (~8GB heap)
takes ~8 seconds. With this change scanning takes negligible time.
对2e8个元素的map[int]int上进行了测试，GC扫描时间从8秒减少到0。
为什么当map的key和value不包含指针时，可以省去对元素的遍历扫描呢？这是因为map中的int、bool这种不可能会和外部变量有引用关系：
int、bool这种在map中存储的就是值本身。
map的key和value不可被寻址。也就是说，以map[int]int为例，外部没有办法取到这个key和value的指针，那也就无从引用了。
这个优化听起来非常强大好用，但是在Golang中指针无处不见，结构体指针、切片甚至字符串的底层实现都包含指针。一旦在map中使用它们（例如map[int][]byte、map[string]int），同样会触发垃圾回收器的遍历扫描。
 bigcache的整体设计
bigcache整体设计的出发点都是基于上文提到的Golang对Map GC优化，整个设计思路包含几个方面：
数据分片存储，以降低锁冲突并提升并发量。
避免在map中存储指针，从而避免在GC时对map进行遍历扫描。
采用FIFO式的Ring Buffer设计，简化整体内存设计逻辑。
 数据分shard
这是一个非常常见的数据存储优化手段。表面上bigcache中所有的数据是存在一个大cache里面，但实际上底层数据分成了N个不互重合的部分，每一个部分称为一个shard。
在Set或者Get数据时，先对key计算hash值，根据hash值取余得到目标shard，之后所有的读写操作都是在各自的shard上进行。
以Set方法为例：
1
2
3
4
5
func (c *BigCache) Set(key string, entry []byte) error {
hashedKey := c.hash.Sum64(key)
shard := c.getShard(hashedKey)
return shard.set(key, hashedKey, entry)
}
这么做的优势是可以减少锁冲突，提升并发量：当一个shard被加上Lock的时候，其他shard的读写不受影响。
在bigcache的设计中，对于shard有如下要求：
一旦建好，shard将不改变。这带来的两点好处：不用再考虑shard变化时的数据迁移问题。
因为shard数组是固定不变的，因此从shard数组中根据hash值取目标shard的时候，就无需加锁了。
shard个数必须是2的平方数。这么做的好处是，对2的平方数取余可以改成位运算，会比传统的%快很多（根据不权威的benchmark，计算速度大概会有2倍左右的差距）。
1
2
3
4
func (c *BigCache) getShard(hashedKey uint64) (shard *cacheShard) {
    // shardMask:  uint64(config.Shards - 1)
return c.shards[hashedKey&c.shardMask]
}
bigcache的shard数默认值是1024。
 map不存原始数据，避免GC遍历扫描
前文提到，map的key和value一旦涉及指针相关的类型，GC时就会触发遍历扫描。
因此在bigcache的设计中，shard中的map直接定义为了map[uint64]uint32 ，避免了存储任何指针。shard的结构体定义如下:
1
2
3
4
5
6
type cacheShard struct {
...
hashmap     map[uint64]uint32
entries     queue.BytesQueue
...
}
其中：hashmap的key是cache key的hash值，而value仅仅是个uint32。这显然不是我们Set的时候value的原始byte数组。
那value的原始值存在了哪里？答案是cacheShard中的另外一个属性entries queue.BytesQueue。
queue.BytesQueue是一个ring buffer的内存结构，本质上就是个超大的[]byte数组，里面存放了所有的原始数据。每个原始数据就存放在这个大[]byte数组中的其中一段。
hashmap中uint32的value值存放的就是value的原始值在BytesQueue中的数组下标。(其实并不只是原始的value值，里面也包含了key、插入时间戳等信息）
之所以用一个大的[]byte数组和ring buffer结构，除了方便管理和复用内存之外，一个更重要的原因是：对于[]byte数组, GC时只用看做一个变量扫描，无需再遍历全部数组。这样又避免了海量数据对GC造成的负担。
 FIFO式的内存结构设计
bigcache在内存结构设计上完全遵循FIFO原则：
新增数据以及对旧数据的修改，都是直接Append新数据到BytesQueue中。基本不直接对内存进行修改和删除等。
每个数据项不可以定制单独的缓存时长，必须全部保持一致。这对数据淘汰非常友好，下文会详细讲述。
这样一整套设计约定下来，bigcache的逻辑变成非常简洁明了，但这样同时造成了bigcache的局限性。
 Set过程
1
cache.Set("my-unique-key", []byte("value"...剩余内容已隐藏
查看完整文章以阅读更多
查看完整文章