golang freecache源码分析
golang freecache源码分析
go的cache有很多实现，其中freecache号称零GC开销，是怎么做到的呢？我们从源码来进行分析，freecache的地址为：
https://github.com/coocood/freecache
go在一定程度消除了堆和栈的区别，因为go在编译的时候进行逃逸分析，来决定一个对象放栈上还是放堆上，不逃逸的对象放栈上，可能逃逸的放堆上。编译参数加入 -gcflags '-m -l'，开启逃逸分析日志。
逃逸场景
1， 指针逃逸
Go可以返回局部变量指针，这其实是一个典型的变量逃逸案例
2 ，栈空间不足逃逸（空间开辟过大）
当栈空间不足以存放当前对象时或无法判断当前切片长度时会将对象分配到堆中。
3， 动态类型逃逸（不确定长度大小）
4， 闭包引用对象逃逸
避免gc要从上面四个方面入手考虑，那么freecache是怎么做到的呢，先看下整体的数据结构：
cache对象维护了两个长度为256的数组
type Cache struct {
locks [segmentCount]sync.Mutex // 每个segment都有自己的同步控制锁
segments [segmentCount]segment // 缓存划分为256个segment
}整体思路是：
1，把key进行hash得到64位的hash值
// xxhash算法，算出64位哈希值
func hashFunc(data []byte) uint64 {
return xxhash.Sum64(data)
}2，按照最低的8位分segment，刚好256个segment
segID := hashVal & segmentAndOpValfunc (cache *Cache) Get(key []byte) (value []byte, err error) {
// 1. 算出key的64位哈希值
hashVal := hashFunc(key)
// 2. 取低8位，得到segId
segID := hashVal & segmentAndOpVal
// 找到对应的segment，只对segment加锁
// 同个segment的操作是串行进行，不同segment的操作是并行进行的
cache.locks[segID].Lock()
value, _, err = cache.segments[segID].get(key, nil, hashVal, false)
cache.locks[segID].Unlock()
return
}3，取右数第二个8位分slot，刚好256个slot
slotId := uint8(hashVal >> 8)4,取右数第三个、第四个8位最为hash16值，用于初步过滤
hash16 := uint16(hashVal >> 16)5，接着看下，如何定位slot
slot := seg.getSlot(slotId)
idx, match := seg.lookup(slot, hash16, key)看之前我们看下segment的数据结构
type segment struct {
// 环形缓冲区RingBuf，由一个固定容量的切片实现
rb RingBuf
segId int
_ uint32
missCount int64
hitCount int64
entryCount int64
totalCount int64
totalTime int64
timer Timer
totalEvacuate int64
totalExpired int64
overwrites int64
touched int64
vacuumLen int64
slotLens [256]int32
slotCap int32
// entry索引切片，容量动态扩展
slotsData []entryPtr
}其中slotsData存了entryPtr，查找元素的过程如下：
首先在slotsData里面根据slotId和cap来取切片
func (seg *segment) getSlot(slotId uint8) []entryPtr {
slotOff := int32(slotId) * seg.slotCap
return seg.slotsData[slotOff : slotOff+seg.slotLens[slotId] : slotOff+seg.slotCap]
}然后通过hash16值和key来进行匹配
idx, match := seg.lookup(slot, hash16, key)具体匹配过程如下
A，通过二分查找，粗匹配到hash16值相等的位置
func entryPtrIdx(slot []entryPtr, hash16 uint16) (idx int) {
high := len(slot)
for idx < high {
mid := (idx + high) >> 1
oldEntry := &slot[mid]
if oldEntry.hash16 < hash16 {
idx = mid + 1
} else {
high = mid
}
}
return
}B，然后通过key相等且entryPtr相等来做精确定位
func (seg *segment) lookup(slot []entryPtr, hash16 uint16, key []byte) (idx int, match bool) {
idx = entryPtrIdx(slot, hash16)
for idx < len(slot) {
ptr := &slot[idx]
if ptr.hash16 != hash16 {
break
}
match = int(ptr.keyLen) == len(key) && seg.rb.EqualAt(key, ptr.offset+ENTRY_HDR_SIZE)
if match {
return
}
idx++
}
return
}其中entryPtr定义如下
type entryPtr struct {
offset int64 // entry offset in ring buffer
hash16 uint16 // entries are ordered by hash16 in a slot.
keyLen uint16 // used to compare a key
reserved uint32
}其中offset 定义了，数据的key和value在ringbuffer里的偏移量
6，有了偏移量，我们就可以很方便地在ringbuffer里存取数据
读：
matchedPtr := &slot[idx]
seg.rb.ReadAt(hdrBuf[:], matchedPtr.offset)写：
seg.rb.WriteAt(hdrBuf[:], matchedPtr.offset)
seg.rb.WriteAt(value, matchedPtr.offset+ENTRY_HDR_SIZE+int64(hdr.keyLen))7，最后看下ringBuffer的数据结构
// Ring buffer has a fixed size, when data exceeds the
// size, old data will be overwritten by new data.
// It only contains the data in the stream from begin to end
type RingBuf struct {
begin int64 // beginning offset of the data stream.
end int64 // ending offset of the data stream.
data []byte
index int //range from '0' to 'len(rb.data)-1'
}本质是一个数组（一块在栈上连续的内存）
总结：
通过以上分析，我们可知，freecache，通过对key的hash64值的后32位巧妙利用来进行寻址，做初步定位，有效提高了查找效率，同时由于只分配了256个segment和256个slots指针，对于大量缓存机构体来说几乎可以忽略，所以几乎不会被GC扫描，可以认为是0GC的，有效缓解了GC带来的性能问题。
本文分享自 golang算法架构leetcode技术php 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！
腾讯云开发者
