请人开发网站多少钱,成都住建局官网网上办事大厅,做网站毕业答辩会问什么,小程序微信如何开发项目地址
BigCache 是一个快速#xff0c;支持并发访问#xff0c;自淘汰的内存型缓存#xff0c;可以在存储大量元素时依然保持高性能。BigCache将元素保存在堆上却避免了GC的开销。
背景介绍
BigCache的作者在项目里遇到了如下的需求#xff1a;
支持http协议支持 10…项目地址
BigCache 是一个快速支持并发访问自淘汰的内存型缓存可以在存储大量元素时依然保持高性能。BigCache将元素保存在堆上却避免了GC的开销。
背景介绍
BigCache的作者在项目里遇到了如下的需求
支持http协议支持 10 k 10k 10kRPS 其中读写各占一半cache缓存至少 10 10 10分钟平均 r t 5 m s , p 99 10 m s , p 999 400 m s rt5ms,p9910ms,p999400ms rt5ms,p9910ms,p999400ms 开发的缓存库需要保证即使有百万的缓存对象速度也要很快支持高并发访问支持过期自动删除
简单入门
func Test_BigCache(t *testing.T) {cache, _ : bigcache.New(context.Background(), bigcache.DefaultConfig(10*time.Minute)) //定义cachecache.Set(my-unique-key, []byte(value)) //设置k,v键值对entry, _ : cache.Get(my-unique-key) //获取k,v键值对t.Log(string(entry))
}配置文件
config字段说明
字段名类型含义Shardsint缓存分片数值必须是 2 的幂LifeWindowtime.Duration条目可以被逐出的时间近似可以理解为缓存时间CleanWindowtime.Duration删除过期条目清理之间的间隔。如果设置为 0则不执行任何操作。设置为 1 秒会适得其反因为 bigcache 的分辨率为 1 秒。MaxEntriesInWindowint生命周期窗口中的最大条目数。仅用于计算缓存分片的初始大小。如果设置了适当的值则不会发生额外的内存分配。MaxEntrySizeint条目的最大大小以字节为单位。仅用于计算缓存分片的初始大小。StatsEnabledboolStatsEnabled如果为true则计算请求缓存资源的次数。Verbosebool是否以详细模式打印有关新内存分配的信息HasherHasher哈希程序用于在字符串键和无符号 64 位整数之间进行映射默认情况下使用 fnv64 哈希。HardMaxCacheSizeint是BytesQueue 大小的限制 MB。它可以防止应用程序占用计算机上的所有可用内存从而防止运行 OOM Killer。OnRemovefunc(key string, entry []byte)OnRemove 是当最旧的条目由于过期时间或没有为新条目留出空间或调用 delete 而被删除时触发的回调。如果指定了 OnRemoveWithMetadata则忽略。OnRemoveWithMetadatafunc(key string, entry []byte, keyMetadata Metadata)OnRemoveWithMetadata 是当最旧的条目由于过期时间或没有为新条目留出空间或调用 delete 而被删除时触发的回调携带有关该特定条目的详细信息的结构。OnRemoveWithReasonfunc(key string, entry []byte, reason RemoveReason)OnRemoveWithReason 是当最旧的条目由于过期时间或没有为新条目留出空间或调用了 delete 而被删除时触发的回调将传递一个表示原因的常量。如果指定了 OnRemove则忽略。onRemoveFilterint和OnRemoveWithReason一起使用阻止 bigcache 解包它们从而节省 CPU。LoggerLogger日志记录接口
说明
LifeWindow 是一个时间。在此之后条目可以称为死条目但不能删除。CleanWindow 是一个时间。在此之后将删除所有无效条目但不会删除仍具有生命的条目。HardMaxCacheSize 默认值为 0表示大小不受限制。当限制高于 0 并达到时新条目将覆盖最旧的条目。由于 Shards 的额外内存最大内存消耗将大于 HardMaxCacheSize。每个分片都会消耗额外的内存来映射键和统计信息 map[uint64]uint32此映射的大小等于缓存中的条目数 ~ 2×6432×n 位 开销或映射本身。OnRemoveOnRemoveWithMetadata OnRemoveWithReason 这三个跟删除有关的属性默认值为 nil表示没有回调并且会阻止解开最早的条目。
配置代码文件 // Config for BigCache
type Config struct {// Number of cache shards, value must be a power of twoShards int// Time after which entry can be evictedLifeWindow 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 allocationVerbose 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×(6432)×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 的负载时最好使用自定义配置。
字段名值含义Shards1024缓存分片数是1024LifeWindoweviction自定义过期时间CleanWindow1 * time.Second每隔1秒就清理失效数据MaxEntriesInWindow1000 * 10 * 60生命周期窗口中的最大条目数为6e5MaxEntrySize500条目的最大大小为500字节StatsEnabledfalse不计算请求缓存资源的次数Verbosetrue以详细模式打印有关新内存分配的信息Hasherfnv64哈希程序fnv64 哈希HardMaxCacheSize0BytesQueue 大小无限制LoggerDefaultLogger日志记录接口
优点支持自定义过期时间清理失效数据的间隔为最小间隔、效率高 缺点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缓存分片数据lifeWindowuint64缓存时间对应配置里的LifeWindowclockclock时间计算函数hashHasher哈希函数configConfig配置文件shardMaskuint64值为(config.Shards-1)寻找分片位置时使用的参数可以理解为对config.Shards取余后的最大值closechan struct{}关闭通道
type BigCache struct {shards []*cacheShardlifeWindow uint64clock clockhash Hasherconfig ConfigshardMask uint64close chan struct{}
}cacheShard数据结构
字段名类型含义hashmapmap[uint64]uint32索引列表key为存储的keyvalue为该key在entries里的位置entriesqueue.BytesQueue实际数据存储的地方locksync.RWMutex互斥锁用于并发读写entryBuffer[]byte入口缓冲区onRemoveonRemoveCallback删除回调函数isVerbosebool是否详细模式打印有关新内存分配的信息statsEnabledbool是否计算请求缓存资源的次数loggerLogger日志记录函数clockclock时间计算函数lifeWindowuint64缓存时间对应配置里的LifeWindowhashmapStatsmap[uint64]uint32存储缓存请求次数statsStats存储缓存统计信息cleanEnabledbool是否可清理由config.CleanWindow决定
type cacheShard struct {hashmap map[uint64]uint32entries queue.BytesQueuelock sync.RWMutexentryBuffer []byteonRemove onRemoveCallbackisVerbose boolstatsEnabled boollogger Loggerclock clocklifeWindow uint64hashmapStats map[uint64]uint32stats StatscleanEnabled bool
}BytesQueue数据结构
BytesQueue 是一种基于 bytes 数组的 fifo 非线程安全队列类型。对于每个推送操作都会返回条目的索引。它可用于稍后读取条目。
字段名类型含义fullbool队列是否已满array[]byte实际数据存储的地方capacityint容量maxCapacityint最大容量headint队首位置tailint下次可以插入的元素位置countint当前存在的元素数量rightMarginint右边界headerBuffer[]byte插入时的临时缓冲区verbosebool是否详细模式打印有关新内存分配的信息
type BytesQueue struct {full boolarray []bytecapacity intmaxCapacity inthead inttail intcount intrightMargin intheaderBuffer []byteverbose bool
}
优秀设计
处理并发访问
设计点1将数据打散后存储
通用解法 缓存支持并发访问是很基本的要求比较常见的解决访问是对缓存整体加读写锁在同一时间只允许一个协程修改缓存内容。这样的缺点是锁可能会阻塞后续的操作而且高频的加锁、解锁操作会导致缓存性能降低。
设计点 B i g C a c h e BigCache BigCache使用一个 s h a r d shard shard数组来存储数据将数据打散到不同的 s h a r d shard shard里每个 s h a r d shard shard里都有一个小的 l o c k lock 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[hashedKeyc.shardMask]
}
可以得到 s e t set set的过程如下
进行 h a s h hash hash操作将 s t r i n g string string类型 k e y key key哈希为一个 u i n t 64 uint64 uint64类型的 h a s h e d K e y hashedKey hashedKey根据 h a s h e d K e y hashedKey hashedKey做 s h a r d i n g sharding sharding最后落到的 s h a r d shard shard的下标为 h a s h e d K e y % n hashedKey\%n hashedKey%n,其中 n n n是分片数量。理想情况下每次请求会均匀地落在各自的分片上单个 s h a r d shard shard的压力就会很小。调用对应 s h a r d shard shard的set方法来设置缓存
设计点 当 n n n为 2 2 2的幂次方的时候对于任意的 x x x下面的公式都成立的。 x m o d N ( x ( N − 1 ) ) x\ mod\ N (x \ (N − 1)) x mod N(x(N−1)) 所以可以借助位运算快速计算余数因此倒推回去 缓存分片数必须要设置为 2 2 2的幂次方。
设计点3 避免栈上的内存分配
默认的哈希算法为 f n v 64 fnv64 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_hashoffset64 14695981039346656037// prime64 FNVa prime value. See https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function#FNV-1a_hashprime64 1099511628211
)// Sum64 gets the string and returns its uint64 hash value.
func (f fnv64a) Sum64(key string) uint64 {var hash uint64 offset64for i : 0; i len(key); i {hash ^ uint64(key[i])hash * prime64}return hash
}
减少GC开销
设计点1利用go1.5特性减少GC扫描 g o l a n g golang golang里实现缓存最简单的方式是 m a p map map来存储元素比如 m a p [ s t r i n g ] I t e m map[string]Item map[string]Item。 使用 m a p map map的缺点为垃圾回收器 G C GC GC会在标记阶段访问 m a p map map里的每一个元素当 m a p map map里存储了大量数据的时候会降低程序性能。 B i g C a c h e BigCache BigCache使用了 g o 1.5 go1.5 go1.5版本以后的特性如果使用的map的key和value中都不包含指针那么GC会忽略这个map 具体而言 B i g C a c h e BigCache BigCache使用 m a p [ u i n t 64 ] u i n t 32 map[uint64]uint32 map[uint64]uint32 来存储数据不包含指针 G C GC GC就会自动忽略这个 m a p map map。 m a p map map的 k e y key key存储的是缓存的 k e y key key经过 h a s h hash hash函数后得到的值 m a p map map的 v a l u e value value存储的是序列化后的数据在全局 [ ] b y t e []byte []byte中的下标。 因为 B i g C a c h e BigCache BigCache是将存入缓存的 v a l u e value value序列化为 b y t e byte byte数组然后将该数组追加到全局的 b y t e byte byte数组里说明结合前面的打散思想可以得知一个 s h a r d shard shard对应一个全局的 b y t e byte byte数组 这样做的缺点是删除元素的开销会很大因此 B i g C a c h e BigCache BigCache里也没有提供删除指定 k e y key key的接口删除元素靠的是全局的过期时间或是缓存的容量上限是先进先出的队列类型的过期。
性能测试
项目开发者给出了项目和主流缓存方案的 B e n c h m a r k s Benchmarks Benchmarks结果和 G C GC GC测试结果 测试文件链接 参考 妙到颠毫: bigcache优化技巧 [译] Go开源项目BigCache如何加速并发访问以及避免高额的GC开销
