Golang高性能内存缓存库BigCache设计与分析

简介: 【2月更文挑战第4天】分析Golang高性能内存缓存库BigCache设计

项目地址

BigCache 是一个快速,支持并发访问,自淘汰的内存型缓存,可以在存储大量元素时依然保持高性能。BigCache将元素保存在堆上却避免了GC的开销。

背景介绍

BigCache的作者在项目里遇到了如下的需求:

  • 支持http协议
  • 支持$10k$RPS ,其中读写各占一半
  • cache缓存至少$10$分钟
  • 平均$rt=5ms,p99<=10ms,p999<=400ms$
    开发的缓存库需要保证:
  • 即使有百万的缓存对象速度也要很快
  • 支持高并发访问
  • 支持过期自动删除

    简单入门

func Test_BigCache(t *testing.T) {
   
    cache, _ := bigcache.New(context.Background(), bigcache.DefaultConfig(10*time.Minute)) //定义cache
    cache.Set("my-unique-key", []byte("value")) //设置k,v键值对
    entry, _ := cache.Get("my-unique-key") //获取k,v键值对
    t.Log(string(entry))
}

配置文件

config字段说明

字段名 类型 含义
Shards int 缓存分片数,值必须是 2 的幂
LifeWindow time.Duration 条目可以被逐出的时间,近似可以理解为缓存时间
CleanWindow time.Duration 删除过期条目(清理)之间的间隔。如果设置为 <= 0,则不执行任何操作。设置为 < 1 秒会适得其反,因为 bigcache 的分辨率为 1 秒。
MaxEntriesInWindow int 生命周期窗口中的最大条目数。仅用于计算缓存分片的初始大小。如果设置了适当的值,则不会发生额外的内存分配。
MaxEntrySize int 条目的最大大小(以字节为单位)。仅用于计算缓存分片的初始大小。
StatsEnabled bool StatsEnabled如果为true,则计算请求缓存资源的次数。
Verbose bool 是否以详细模式打印有关新内存分配的信息
Hasher Hasher 哈希程序用于在字符串键和无符号 64 位整数之间进行映射,默认情况下使用 fnv64 哈希
HardMaxCacheSize int 是BytesQueue 大小的限制 MB。它可以防止应用程序占用计算机上的所有可用内存,从而防止运行 OOM Killer。
OnRemove func(key string, entry []byte) OnRemove 是当最旧的条目由于过期时间或没有为新条目留出空间或调用 delete 而被删除时触发的回调。如果指定了 OnRemoveWithMetadata,则忽略。
OnRemoveWithMetadata func(key string, entry []byte, keyMetadata Metadata) OnRemoveWithMetadata 是当最旧的条目由于过期时间或没有为新条目留出空间或调用 delete 而被删除时触发的回调,携带有关该特定条目的详细信息的结构。
OnRemoveWithReason func(key string, entry []byte, reason RemoveReason) OnRemoveWithReason 是当最旧的条目由于过期时间或没有为新条目留出空间或调用了 delete 而被删除时触发的回调,将传递一个表示原因的常量。如果指定了 OnRemove,则忽略。
onRemoveFilter int 和OnRemoveWithReason一起使用,阻止 bigcache 解包它们,从而节省 CPU
Logger Logger 日志记录接口

说明:

  • LifeWindow 是一个时间。在此之后,条目可以称为死条目,但不能删除。
  • CleanWindow 是一个时间。在此之后,将删除所有无效条目,但不会删除仍具有生命的条目。
  • HardMaxCacheSize 默认值为 0,表示大小不受限制。当限制高于 0 并达到时,新条目将覆盖最旧的条目。由于 Shards 的额外内存,最大内存消耗将大于 HardMaxCacheSize。每个分片都会消耗额外的内存来映射键和统计信息 (map[uint64]uint32),此映射的大小等于缓存中的条目数 ~ 2×(64+32)×n 位 + 开销或映射本身。
  • OnRemove,OnRemoveWithMetadata ,OnRemoveWithReason 这三个跟删除有关的属性默认值为 nil,表示没有回调,并且会阻止解开最早的条目。

配置代码文件


// Config for BigCache
type Config struct {
   
    // Number of cache shards, value must be a power of two
    Shards int
    // Time after which entry can be evicted
    LifeWindow time.Duration
    // Interval between removing expired entries (clean up).
    // If set to <= 0 then no action is performed. Setting to < 1 second is counterproductive — bigcache has a one second resolution.
    CleanWindow time.Duration
    // Max number of entries in life window. Used only to calculate initial size for cache shards.
    // When proper value is set then additional memory allocation does not occur.
    MaxEntriesInWindow int
    // Max size of entry in bytes. Used only to calculate initial size for cache shards.
    MaxEntrySize int
    // StatsEnabled if true calculate the number of times a cached resource was requested.
    StatsEnabled bool
    // Verbose mode prints information about new memory allocation
    Verbose bool
    // Hasher used to map between string keys and unsigned 64bit integers, by default fnv64 hashing is used.
    Hasher Hasher
    // HardMaxCacheSize is a limit for BytesQueue size in MB.
    // It can protect application from consuming all available memory on machine, therefore from running OOM Killer.
    // Default value is 0 which means unlimited size. When the limit is higher than 0 and reached then
    // the oldest entries are overridden for the new ones. The max memory consumption will be bigger than
    // HardMaxCacheSize due to Shards' s additional memory. Every Shard consumes additional memory for map of keys
    // and statistics (map[uint64]uint32) the size of this map is equal to number of entries in
    // cache ~ 2×(64+32)×n bits + overhead or map itself.
    HardMaxCacheSize int
    // OnRemove is a callback fired when the oldest entry is removed because of its expiration time or no space left
    // for the new entry, or because delete was called.
    // Default value is nil which means no callback and it prevents from unwrapping the oldest entry.
    // ignored if OnRemoveWithMetadata is specified.
    OnRemove func(key string, entry []byte)
    // OnRemoveWithMetadata is a callback fired when the oldest entry is removed because of its expiration time or no space left
    // for the new entry, or because delete was called. A structure representing details about that specific entry.
    // Default value is nil which means no callback and it prevents from unwrapping the oldest entry.
    OnRemoveWithMetadata func(key string, entry []byte, keyMetadata Metadata)
    // OnRemoveWithReason is a callback fired when the oldest entry is removed because of its expiration time or no space left
    // for the new entry, or because delete was called. A constant representing the reason will be passed through.
    // Default value is nil which means no callback and it prevents from unwrapping the oldest entry.
    // Ignored if OnRemove is specified.
    OnRemoveWithReason func(key string, entry []byte, reason RemoveReason)

    onRemoveFilter int

    // Logger is a logging interface and used in combination with `Verbose`
    // Defaults to `DefaultLogger()`
    Logger Logger
}

默认配置

DefaultConfig 使用默认值初始化配置。当可以提前预测 BigCache 的负载时,最好使用自定义配置
|字段名| 值|含义 |
|--|--|--|
|Shards |1024 | 缓存分片数是1024 |
|LifeWindow |eviction | 自定义过期时间|
|CleanWindow | 1 time.Second | 每隔1秒就清理失效数据 |
|MaxEntriesInWindow |1000
10 * 60 | 生命周期窗口中的最大条目数为6e5|
|MaxEntrySize | 500 | 条目的最大大小为500字节 |
|StatsEnabled |false |不计算请求缓存资源的次数 |
|Verbose |true |以详细模式打印有关新内存分配的信息 |
|Hasher |fnv64 |哈希程序,fnv64 哈希 |
| HardMaxCacheSize|0 |BytesQueue 大小无限制 |
| Logger| DefaultLogger| 日志记录接口|

优点:支持自定义过期时间,清理失效数据的间隔为最小间隔、效率高
缺点:BytesQueue 大小无限制,容易造成内存占用过高
默认配置代码:

func DefaultConfig(eviction time.Duration) Config {
   
    return Config{
   
        Shards:             1024,
        LifeWindow:         eviction,
        CleanWindow:        1 * time.Second,
        MaxEntriesInWindow: 1000 * 10 * 60,
        MaxEntrySize:       500,
        StatsEnabled:       false,
        Verbose:            true,
        Hasher:             newDefaultHasher(),
        HardMaxCacheSize:   0,
        Logger:             DefaultLogger(),
    }
}

数据结构

前提说明:BigCache 是快速、并发、逐出缓存,旨在保留大量条目而不影响性能。它将条目保留在堆上,但省略了它们的 GC。为了实现这一点,操作发生在字节数组上,因此在大多数用例中,都需要在缓存前面进行条目(反序列化)

BigCache数据结构

字段名 类型 含义
shards []*cacheShard 缓存分片数据
lifeWindow uint64 缓存时间,对应配置里的LifeWindow
clock clock 时间计算函数
hash Hasher 哈希函数
config Config 配置文件
shardMask uint64 值为(config.Shards-1),寻找分片位置时使用的参数,可以理解为对config.Shards取余后的最大值
close chan struct{} 关闭通道
type BigCache struct {
   
    shards     []*cacheShard
    lifeWindow uint64
    clock      clock
    hash       Hasher
    config     Config
    shardMask  uint64
    close      chan struct{
   }
}

cacheShard数据结构

字段名 类型 含义
hashmap map[uint64]uint32 索引列表,key为存储的key,value为该key在entries里的位置
entries queue.BytesQueue 实际数据存储的地方
lock sync.RWMutex 互斥锁,用于并发读写
entryBuffer []byte 入口缓冲区
onRemove onRemoveCallback 删除回调函数
isVerbose bool 是否详细模式打印有关新内存分配的信息
statsEnabled bool 是否计算请求缓存资源的次数
logger Logger 日志记录函数
clock clock 时间计算函数
lifeWindow uint64 缓存时间,对应配置里的LifeWindow
hashmapStats map[uint64]uint32 存储缓存请求次数
stats Stats 存储缓存统计信息
cleanEnabled bool 是否可清理,由config.CleanWindow决定
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
    cleanEnabled bool
}

BytesQueue数据结构

BytesQueue 是一种基于 bytes 数组的 fifo 非线程安全队列类型。对于每个推送操作,都会返回条目的索引。它可用于稍后读取条目。
|字段名| 类型|含义 |
|--|--|--|
| full | bool |队列是否已满 |
| array | []byte | 实际数据存储的地方 |
|capacity | int| 容量|
|maxCapacity |int |最大容量 |
|head |int |队首位置 |
|tail |int | 下次可以插入的元素位置|
| count| int|当前存在的元素数量 |
|rightMargin | int|右边界 |
| headerBuffer| []byte | 插入时的临时缓冲区|
| verbose| bool|是否详细模式打印有关新内存分配的信息 |

type BytesQueue struct {
   
    full         bool
    array        []byte
    capacity     int
    maxCapacity  int
    head         int
    tail         int
    count        int
    rightMargin  int
    headerBuffer []byte
    verbose      bool
}

优秀设计

处理并发访问

设计点1:将数据打散后存储

通用解法: 缓存支持并发访问是很基本的要求,比较常见的解决访问是对缓存整体加读写锁,在同一时间只允许一个协程修改缓存内容。这样的缺点是锁可能会阻塞后续的操作,而且高频的加锁、解锁操作会导致缓存性能降低。

设计点: $BigCache$使用一个$shard$数组来存储数据,将数据打散到不同的$shard$里,每个$shard$里都有一个小的$lock$,从而减小了锁的粒度,提高访问性能。

设计点2:打散数据过程中借助位运算加快计算速度

接下来看一下将某个数据放到缓存的过程的源代码:

// Set saves entry under the key
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) {
   
    return c.shards[hashedKey&c.shardMask]
}

可以得到$set$的过程如下:

  • 进行$hash$操作,将$string$类型$key$哈希为一个$uint64$类型的$hashedKey$
  • 根据$hashedKey$做$sharding$,最后落到的$shard$的下标为$hashedKey\%n$,其中$n$是分片数量。理想情况下,每次请求会均匀地落在各自的分片上,单个$shard$的压力就会很小。
  • 调用对应$shard$的set方法来设置缓存

设计点:
当$n$为$2$的幂次方的时候,对于任意的$x$,下面的公式都成立的。
$$x\ mod\ N = (x \& (N − 1))$$
所以可以借助位运算快速计算余数,因此倒推回去 缓存分片数必须要设置为$2$的幂次方

设计点3 避免栈上的内存分配

默认的哈希算法为$fnv64$算法,该算法采用位运算的方式在栈上运算,避免了在堆上分配内存

package bigcache

// 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() Hasher {
   
    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
}

减少GC开销

设计点1:利用go1.5+特性,减少GC扫描

$golang$里实现缓存最简单的方式是$map$来存储元素,比如$map[string]Item$。
使用$map$的缺点为垃圾回收器$GC$会在标记阶段访问$map$里的每一个元素,当$map$里存储了大量数据的时候会降低程序性能。

$BigCache$使用了$go1.5$版本以后的特性:如果使用的map的key和value中都不包含指针,那么GC会忽略这个map
具体而言,$BigCache$使用$map[uint64]uint32$
来存储数据,不包含指针,$GC$就会自动忽略这个$map$。

$map$的$key$存储的是缓存的$key$经过$hash$函数后得到的值
$map$的$value$存储的是序列化后的数据在全局$[]byte$中的下标。
因为$BigCache$是将存入缓存的$value$序列化为$byte$数组,然后将该数组追加到全局的$byte$数组里(说明:结合前面的打散思想可以得知一个$shard$对应一个全局的$byte$数组
这样做的缺点是删除元素的开销会很大,因此$BigCache$里也没有提供删除指定$key$的接口,删除元素靠的是全局的过期时间或是缓存的容量上限,是先进先出的队列类型的过期。

参考
妙到颠毫: bigcache优化技巧
[译] Go开源项目BigCache如何加速并发访问以及避免高额的GC开销

目录
相关文章
|
12天前
|
Web App开发 监控 JavaScript
监控和分析 JavaScript 内存使用情况
【10月更文挑战第30天】通过使用上述的浏览器开发者工具、性能分析工具和内存泄漏检测工具,可以有效地监控和分析JavaScript内存使用情况,及时发现和解决内存泄漏、过度内存消耗等问题,从而提高JavaScript应用程序的性能和稳定性。在实际开发中,可以根据具体的需求和场景选择合适的工具和方法来进行内存监控和分析。
|
1月前
|
编译器 C语言
动态内存分配与管理详解(附加笔试题分析)(上)
动态内存分配与管理详解(附加笔试题分析)
49 1
|
21天前
|
缓存 Java Shell
Android 系统缓存扫描与清理方法分析
Android 系统缓存从原理探索到实现。
45 15
Android 系统缓存扫描与清理方法分析
|
7天前
|
开发框架 监控 .NET
【Azure App Service】部署在App Service上的.NET应用内存消耗不能超过2GB的情况分析
x64 dotnet runtime is not installed on the app service by default. Since we had the app service running in x64, it was proxying the request to a 32 bit dotnet process which was throwing an OutOfMemoryException with requests >100MB. It worked on the IaaS servers because we had the x64 runtime install
|
13天前
|
存储 Cloud Native Shell
go库介绍:Golang中的Viper库
Viper 是 Golang 中的一个强大配置管理库,支持环境变量、命令行参数、远程配置等多种配置来源。本文详细介绍了 Viper 的核心特点、应用场景及使用方法,并通过示例展示了其强大功能。无论是简单的 CLI 工具还是复杂的分布式系统,Viper 都能提供优雅的配置管理方案。
|
17天前
|
Web App开发 JavaScript 前端开发
使用 Chrome 浏览器的内存分析工具来检测 JavaScript 中的内存泄漏
【10月更文挑战第25天】利用 Chrome 浏览器的内存分析工具,可以较为准确地检测 JavaScript 中的内存泄漏问题,并帮助我们找出潜在的泄漏点,以便采取相应的解决措施。
114 9
|
19天前
|
缓存 监控 NoSQL
Redis 缓存穿透的检测方法与分析
【10月更文挑战第23天】通过以上对 Redis 缓存穿透检测方法的深入探讨,我们对如何及时发现和处理这一问题有了更全面的认识。在实际应用中,我们需要综合运用多种检测手段,并结合业务场景和实际情况进行分析,以确保能够准确、及时地检测到缓存穿透现象,并采取有效的措施加以解决。同时,要不断优化和改进检测方法,提高检测的准确性和效率,为系统的稳定运行提供有力保障。
47 5
|
16天前
|
存储 缓存 监控
|
21天前
|
并行计算 算法 IDE
【灵码助力Cuda算法分析】分析共享内存的矩阵乘法优化
本文介绍了如何利用通义灵码在Visual Studio 2022中对基于CUDA的共享内存矩阵乘法优化代码进行深入分析。文章从整体程序结构入手,逐步深入到线程调度、矩阵分块、循环展开等关键细节,最后通过带入具体值的方式进一步解析复杂循环逻辑,展示了通义灵码在辅助理解和优化CUDA编程中的强大功能。
|
1月前
|
程序员 编译器 C语言
动态内存分配与管理详解(附加笔试题分析)(下)
动态内存分配与管理详解(附加笔试题分析)(下)
46 2