学习VictoriaMetrics源码的时候发现，VictoriaMetrics的缓存部分，使用了同一产品下的fastcache。下面分享阅读fastcache源码的的结论：
1.官方介绍
fastcache是一个用go语言实现的，很快的，线程安全的，内存缓存的，用于大量对象缓存的组件。
它的特点是：
- 快！CPU核越多越快，不信你看我下面的benchmark。
- 线程安全。多个协程可以同时读写单个cache实例。
- fastcache用于存储大量的cache实体，而且不会被GC扫描。
- 当设定的cache空间满了以后，fastcache会自动淘汰老数据。
- API贼简单。
- 源码也贼简单。
- cache还可以保存在文件中，需要的时候能加载。
- 在Google的云服务上也能跑得起来。（说明未使用很特殊的操作系统API）
作者valyala是fasthttp和VictoriaMetrics等作品的主要开发者。valyala大神有极其强悍的工程能力，很多看来已经很简单的成熟组件被他又一次妙手生花，YYDS!
2. 性能
究竟有多快呢？作者做了一个对比：(这里主要看set操作)
- golang的标准map: 6.21 M次/s
- sync.Map库：2.65 M次/s
- BigCache库：6.20 M次/s
- fastcache库：17.21 M次/s
换个角度看：
- 比golang的标准map快2.77倍
- 比sync.Map库快6.49倍
- 比BigCache快2.78倍
快得我都不知道说啥好了……
3. 限制
当然也不是快就完美了，也是有些限制的。要根据这些限制来确定fastcache是否适合引入你的业务环境中：
- key和value都只能是[]byte类型，不是的话要自己序列化
- key长度+value长度+4不能超过64KB，否则就要使用额外的SetBig()方法
- 没有缓存过期机制。只有在cache满了以后才能淘汰旧数据。
- 可以自己把过期时间存储在value中，读出来的时候判断一下。如果过期了，手动调用Del()方法来删除。
- cache的总容量是预先设置好的，超过这个容量就要淘汰最早插入的值。
- 当然了，cache嘛，仅适合cache场景，不能用于无损的数据存储。
- 最后：hash冲突的处理上，整个cache分为512个桶。如果两个key的hashcode完全相同的话，新插入的值会替换掉旧的值，导致前一个值丢失……
- 发生hash冲突时仅仅只是原子累加到监控变量，让你知道曾经发生过……
- 我认为这一点很不合理，给作者提了个issue
4. 源码解读
4.1 使用mmap分配内存
malloc_mmap.go中使用了unix.Mmap()来分配内存：
-
内存映射的方式可以直接向操作系统申请内存，这块区域不归GC管。所以不管你在这块内存缓存了多少数据，都不会因为GC扫描而影响性能。
-
每次使用mmap申请内存的时候，申请了1024*64KB=64MB内存。
- 每64KB称为一个chunk
- 所有的chunk放在一个队列中
- 当队列中所有的chunk都用完后，再申请64MB
-
chunk的管理：
var (
freeChunks []*[chunkSize]byte //相当于一个队列，保存了所有未使用的chunk
freeChunksLock sync.Mutex //chunk的锁
)
可以通过 func getChunk() []byte 函数获取一个64KB的块。如果freeChunks中没有chunk了，就再通过mmap申请64MB。
- chunk的归还
func putChunk(chunk []byte)函数把有效的chunk放回freeChunks队列。
绕过GC能带来性能上的好处，但是这里分配的内存再也不会被释放，直到进程重启。
4.2 Cache类的实现
fastcache.go中是fastcache的主要代码。
4.2.1 cache对象的结构
type Cache struct {
buckets [bucketsCount]bucketbigStats BigStats
}
- bucketsCount这个常量值为512 。也就是说，cache对象的内部分布了512个桶。
- bigStats 是用于内部的监控上报的
4.2.2 新建cache对象
// func New(maxBytes int) *Cache
c := New(1024*1024*32) //cache的最小容量是32MB
New的源码如下：
func New(maxBytes int) *Cache {
if maxBytes <= 0 {
panic(fmt.Errorf("maxBytes must be greater than 0; got %d", maxBytes))
}
var c Cache
maxBucketBytes := uint64((maxBytes + bucketsCount - 1) / bucketsCount)
for i := range c.buckets[:] {
c.buckets[i].Init(maxBucketBytes)
}
return &c
}
- maxBytes先按照512字节向上对齐
- 然后划分成512份
- 假设申请内存512MB，则每份1MB。也就是每个bucket 1MB内存。
- 分为512个桶，每个桶再单独初始化
4.2.3 Set方法
func (c *Cache) Set(k, v []byte) {
h := xxhash.Sum64(k)
idx := h % bucketsCount
c.buckets[idx].Set(k, v, h)
}
非常简单：对key计算一个hash值，然后对hash值取模，转到具体的bucket对象里面去处理。
xxhash库用汇编实现，是目前最快的hashcode计算的库
4.3 bucket类的实现
4.3.1 bucket的结构
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 uint64getCalls uint64 // 以下都是用于统计的变量
setCalls uint64
misses uint64
collisions uint64
corruptions uint64
}
-
mu sync.RWMutex: 每个bucket有一个读写锁来处理并发。- 和sync.Map比起来，原理上也没什么神秘的。把数据分散到512个桶，相当于竞争变为原来的1/512。
-
chunks [][]byte: 这个是存储数据的chunk的数组- chunk是上面提到的通过mmap分配的64KB的一个块
- key+value的数据会被顺序的放在chunk中，并记录位于数组中的下标
- 一个chunk的空间用完后，会再通过
getChunk()再申请64KB的块。直到块达到用户规定的上限。- 假设每个bucket 1MB, 则共有1MB/64KB=16个chunk
- 第15个chunk满了以后，又回到第0个chunk存储，同时gen字段增加，说明是新的一代
-
m map[uint64]uint64: 这里存储每个hashcode对应的chunk中的偏移量。 -
idx uint64: 这里记录下次插入chunk的位置，插入完成后跳转到数据的末位。 -
gen uint64: 当所有的chunks都写满以后，gen的值加1，从第0块开始淘汰旧数据。
这里有个明显的缺点：假设hashcode都分布在较少的几个bucket中，那么就导致某几个bucket的数据频繁淘汰，而其他的bucket还剩挺多空间。不过，这只是假设，并未有数据证明会有这种现象。
4.3.2 Set过程
源码太多，此处直接贴结论：
- 每set 16384(2的14次方)次，执行一次clean操作
- clean操作遍历整个map，移除chunk中因为回绕淘汰的数据
- key+value序列化的方式很简单，顺序存储以下内容：
- 2字节key长度
- 2字节value长度
- key的内容
- value的内容
- 写入chunk的时候加入了写锁
- 通过bucket的idx字段找到插入位置，然后按照上述序列化的方式拷贝数据
- 插入完成后得到了偏移位置，把key的hashcode作为键，把chunks中的偏移量为值，写入字段m的map中
- value这里还有个细节：value是64位的uint64, value的低40位存储偏移量，value的高24位存储generation的信息。
4.3.3 Get过程
搞清楚了Set，Get就更简单了：
- 首先在Cache类中，根据key的hashcode，确定选择哪个bucket
- 查询前加读锁
- 在m字段的map中，根据hashcode找到下标
- 根据下标确定key的位置
- 比较key的内容是否相等
- 最后返回value
4.3.4 Del过程
del仅删除map中的key，而chunks中对应的位置只能等到下次回绕才能清理。
删除的动作是滞后的，因此fastcache不适合删除很多的业务场景。
5.总结
fastcache为什么快，因为用了这些手段：
-
使用mmap来成块的分配内存。
- 每次直接向操作系统要64MB，这些内存都绕开了GC。
- 每次以64KB为单位请求一个块
- 在64KB的块内顺序存储，相当于更简单的自己实现的分配算法
-
整个cache分成512个bucket
- 相当于有了512个map+512个读写锁，通过这样减少了竞争
- map类型的key和value都是整形，容量小，且对GC友好
- 淘汰用轮换的方法+固定次数的set后再清理，解决了（或者说绕开了）碎片的问题
希望对你有用，have fun
来自我的公众号：原文链接
